提出一步对齐的图相似性计算方法,显著提升精度与速度。
Rethinking Flexible Graph Similarity Computation: One-step Alignment with Global Guidance
- 通过全局引导的一步对齐,融合操作代价与匹配依赖关系。
- 相比现有方法,预测误差降低37.8%,推理速度提升414倍。
- 适合需要高效高精度图匹配的应用场景。
图编辑距离(GED)是一种广泛使用的图相似性度量,因其能通过操作代价灵活编码领域知识而受到青睐。然而,现有的学习型近似方法遵循将局部候选匹配选择与操作代价及匹配间全局依赖解耦的建模范式,这削弱了其捕捉GED内在灵活性的能力,常需依赖昂贵的迭代优化以获得准确对齐。本文重新审视GED的定义,修正了主流范式,提出图编辑网络(GEN),一种实现新范式的模型,其将代价感知的节点匹配代价估计与全局引导的一步对齐紧密集成。具体而言,GEN将操作代价融入节点匹配成本估计中,确保匹配决策符合指定代价设定;同时,建模图内及跨图的匹配依赖关系,捕捉每一对匹配对整体对齐的影响。这些设计使GEN无需迭代优化即可实现高精度的GED近似。在真实世界和合成基准上的大量实验表明,GEN将GED预测误差最高降低37.8%,推理吞吐量最高提升414倍。结果凸显了该方法的实用性与有效性。除该实现外,本研究提出的范式为推进学习型GED近似提供了原则性框架。
原文摘要 · Abstract (English)
Graph Edit Distance (GED) is a widely used measure of graph similarity, valued for its flexibility in encoding domain knowledge through operation costs. However, existing learning-based approximation methods follow a modeling paradigm that decouples local candidate match selection from both operation costs and global dependencies between matches. This decoupling undermines their ability to capture the intrinsic flexibility of GED and often forces them to rely on costly iterative refinement to obtain accurate alignments. In this work, we revisit the formulation of GED and revise the prevailing paradigm, and propose Graph Edit Network (GEN), an implementation of the revised formulation that tightly integrates cost-aware expense estimation with globally guided one-step alignment. Specifically, GEN incorporates operation costs into node matching expenses estimation, ensuring match decisions respect the specified cost setting. Furthermore, GEN models match dependencies within and across graphs, capturing each match's impact on the overall alignment. These designs enable accurate GED approximation without iterative refinement. Extensive experiments on real-world and synthetic benchmarks demonstrate that GEN achieves up to a 37.8% reduction in GED predictive errors, while increasing inference throughput by up to 414x. These results highlight GEN's practical efficiency and the effectiveness of the revision. Beyond this implementation, our revision provides a principled framework for advancing learning-based GED approximation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。