![[2504.06533] Rethinking Flexible Graph Similarity Computation: One-step Alignment with Global Guidance](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2504.06533] Rethinking Flexible Graph Similarity Computation: One-step Alignment with Global Guidance
Summary
The paper presents a novel approach to graph similarity computation through the Graph Edit Network (GEN), which integrates cost-aware estimations with global guidance, achieving significant improvements in accuracy and efficiency over traditional methods.
Why It Matters
This research addresses the limitations of existing graph similarity measures, particularly the Graph Edit Distance (GED), by proposing a more efficient and accurate method. The findings are relevant for fields that rely on graph analysis, such as social network analysis, bioinformatics, and computer vision, where precise graph matching is crucial.
Key Takeaways
- GEN integrates operation costs into node matching, enhancing accuracy.
- The new approach eliminates the need for iterative refinement, improving efficiency.
- GEN shows up to a 37.8% reduction in predictive errors compared to existing methods.
- Increased inference throughput by up to 414x demonstrates practical applicability.
- The proposed framework sets the stage for future advancements in learning-based GED approximation.
Computer Science > Machine Learning arXiv:2504.06533 (cs) [Submitted on 9 Apr 2025 (v1), last revised 25 Feb 2026 (this version, v3)] Title:Rethinking Flexible Graph Similarity Computation: One-step Alignment with Global Guidance Authors:Zhouyang Liu, Ning Liu, Yixin Chen, Jiezhong He, Shuai Ma, Dongsheng Li View a PDF of the paper titled Rethinking Flexible Graph Similarity Computation: One-step Alignment with Global Guidance, by Zhouyang Liu and 5 other authors View PDF HTML (experimental) Abstract: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 a...
