MATA*: Combining Learnable Node Matching With A* Algorithm For Approximate Graph Edit Distance Computation

Abstract

Graph Edit Distance (GED) is a general and domain-agnostic metric to measure graph similarity, widely used in graph search or retrieving tasks. However, the exact GED computation is known to be NP-complete. For instance, the widely used A* algorithms explore the entire search space to find the optimal solution which inevitably suffers scalability issues. Learning-based methods apply graph representation techniques to learn the GED by formulating a regression task, which can not recover the edit path and lead to inaccurate GED approximation (i.e., the predicted GED is smaller than the exact). To this end, in this work, we present a data-driven hybrid approach MATA* for approximate GED computation based on Graph Neural Networks (GNNs) and A* algorithms, which models from the perspective of learning to match nodes instead of directly regressing GED. Specifically, aware of the structure-dominant operations (i.e.,node and edge insertion/deletion) property in GED computation, a structure-enh

Stats

• citations6
• S2 citations—
• github stars0
• HF likes0
• heat score6.34
• arxiv keyliu2023mata

Related papers

• Simgnn: A Neural Network Approach To Fast Graph Similarity Computation (2018)0.00
• Hierarchical Graph Matching Network For Graph Similarity Computation (2020)0.00
• Learning Graph Edit Distance By Graph Neural Networks (2020)10.85
• SEGMN: A Structure-enhanced Graph Matching Network For Graph Similarity Learning (2024)2.26
• Sub-gmn: The Neural Subgraph Matching Network Model (2021)6.34
• Graph2region: Efficient Graph Similarity Learning With Structure And Scale Restoration (2025)0.00
• S\(^3\)GND: An Effective Learning-based Approach For Subgraph Similarity Search Under Generalized Neighbor Difference Semantics (technical Report) (2026)0.00
• Understanding And Generalizing Monotonic Proximity Graphs For Approximate Nearest Neighbor Search (2021)0.00