# MATA*: Combining Learnable Node Matching with A* Algorithm for Approximate Graph Edit Distance Computation

arXiv: https://arxiv.org/abs/2311.02356 · HTML: https://mlsanity.com/paper/2311.02356/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 42 references that are in the map.
- First posted on arXiv 4 Nov 2023.

## Builds on (most cited first, 10 of 10)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Graph Matching Networks for Learning the Similarity of Graph Structured Objects](https://mlsanity.com/paper/1904.12787/) (2019)
- [GraphiT: Encoding Graph Structure in Transformers](https://mlsanity.com/paper/2106.05667/) (2021)
- [Learning Combinatorial Embedding Networks for Deep Graph Matching](https://mlsanity.com/paper/1904.00597/) (2019)
- [Deep Graph Matching Consensus](https://mlsanity.com/paper/2001.09621/) (2020)
- [Learning-based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matching](https://mlsanity.com/paper/1809.04440/) (2018)
- [GREED: A Neural Framework for Learning Graph Distance Functions](https://mlsanity.com/paper/2112.13143/) (2021)
- [Combinatorial Learning of Graph Edit Distance via Dynamic Embedding](https://mlsanity.com/paper/2011.15039/) (2020)
- [kHGCN: Tree-likeness Modeling via Continuous and Discrete Curvature Learning](https://mlsanity.com/paper/2212.01793/) (2022)

## Built on by (most cited first, 10 of 10)

- [SEFraud: Graph-based Self-Explainable Fraud Detection via Interpretative Mask Learning](https://mlsanity.com/paper/2406.11389/) (2024)
- [Computing Approximate Graph Edit Distance via Optimal Transport](https://mlsanity.com/paper/2412.18857/) (2024)
- [Graph Neural Networks for Databases: A Survey](https://mlsanity.com/paper/2502.12908/) (2025)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [Towards Unsupervised Training of Matching-based Graph Edit Distance Solver via Preference-aware GAN](https://mlsanity.com/paper/2506.01977/) (2025)
- [DiffGED: Computing Graph Edit Distance via Diffusion-based Graph Matching](https://mlsanity.com/paper/2503.18245/) (2025)
- [Rethinking Flexible Graph Similarity Computation: One-step Alignment with Global Guidance](https://mlsanity.com/paper/2504.06533/) (2025)
- [Dynamic Stratified Contrastive Learning with Upstream Augmentation for MILP Branching](https://mlsanity.com/paper/2511.21107/) (2025)
- [SEGMN: A Structure-Enhanced Graph Matching Network for Graph Similarity Learning](https://mlsanity.com/paper/2411.03624/) (2024)
- [Revisiting the Generalization of Neural Graph Edit Distance Models](https://mlsanity.com/paper/2610.04644/) (2026)

## Abstract (arXiv)

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-enhanced GNN is firstly designed to jointly learn local and high-order structural information for node embeddings for node matchings. Second, top-k candidate nodes are produced via a differentiable top-k operation to enable the training for node matchings, which is adhering to another property of GED, i.e., multiple optimal node matchings. Third, benefiting from the candidate nodes, MATA* only performs on the promising search directions, reaching the solution efficiently. Finally, extensive experiments show the superiority of MATA* as it significantly outperforms the combinatorial search-based, learning-based and hybrid methods and scales well to large-size graphs.