# Combinatorial Learning of Graph Edit Distance via Dynamic Embedding

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Nov 2020.

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

- [GREED: A Neural Framework for Learning Graph Distance Functions](https://mlsanity.com/paper/2112.13143/) (2021)
- [A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2106.04927/) (2021)
- [Efficient Graph Similarity Computation with Alignment Regularization](https://mlsanity.com/paper/2406.14929/) (2024)
- [LinSATNet: The Positive Linear Satisfiability Neural Networks](https://mlsanity.com/paper/2407.13917/) (2024)
- [Learning to Count Isomorphisms with Graph Neural Networks](https://mlsanity.com/paper/2302.03266/) (2023)
- [MATA*: Combining Learnable Node Matching with A* Algorithm for Approximate Graph Edit Distance Computation](https://mlsanity.com/paper/2311.02356/) (2023)
- [CGMN: A Contrastive Graph Matching Network for Self-Supervised Graph Similarity Learning](https://mlsanity.com/paper/2205.15083/) (2022)
- [The quest for the GRAph Level autoEncoder (GRALE)](https://mlsanity.com/paper/2505.22109/) (2025)
- [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)
- [EPIC: Graph Augmentation with Edit Path Interpolation via Learnable Cost](https://mlsanity.com/paper/2306.01310/) (2023)
- [DocTTT: Test-Time Training for Handwritten Document Recognition Using Meta-Auxiliary Learning](https://mlsanity.com/paper/2501.12898/) (2025)
- [Towards Unsupervised Training of Matching-based Graph Edit Distance Solver via Preference-aware GAN](https://mlsanity.com/paper/2506.01977/) (2025)
- [DOTIN: Dropping Task-Irrelevant Nodes for GNNs](https://mlsanity.com/paper/2204.13429/) (2022)
- [Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networks](https://mlsanity.com/paper/2409.04495/) (2024)
- [DiffGED: Computing Graph Edit Distance via Diffusion-based Graph Matching](https://mlsanity.com/paper/2503.18245/) (2025)
- [Graph Edit Distance Learning via Different Attention](https://mlsanity.com/paper/2308.13871/) (2023)
- [Rethinking Flexible Graph Similarity Computation: One-step Alignment with Global Guidance](https://mlsanity.com/paper/2504.06533/) (2025)
- [Co-attention Graph Pooling for Efficient Pairwise Graph Interaction Learning](https://mlsanity.com/paper/2307.15377/) (2023)
- [EUGENE: Explainable Structure-aware Graph Edit Distance Estimation with Generalized Edit Costs](https://mlsanity.com/paper/2402.05885/) (2024)
- [SEGMN: A Structure-Enhanced Graph Matching Network for Graph Similarity Learning](https://mlsanity.com/paper/2411.03624/) (2024)
- [GED-Consistent Disentanglement of Aligned and Unaligned Substructures for Graph Similarity Learning](https://mlsanity.com/paper/2511.19837/) (2025)
- [Projecting Latent RL Actions: Towards Generalizable and Scalable Graph Combinatorial Optimization](https://mlsanity.com/paper/2605.19721/) (2026)
- [GLACIER: Rethinking Mass Spectrum Prediction as an Object Detection Problem](https://mlsanity.com/paper/2606.29161/) (2026)
- [Revisiting the Generalization of Neural Graph Edit Distance Models](https://mlsanity.com/paper/2610.04644/) (2026)

## Abstract (arXiv)

Graph Edit Distance (GED) is a popular similarity measurement for pairwise graphs and it also refers to the recovery of the edit path from the source graph to the target graph. Traditional A* algorithm suffers scalability issues due to its exhaustive nature, whose search heuristics heavily rely on human prior knowledge. This paper presents a hybrid approach by combing the interpretability of traditional search-based techniques for producing the edit path, as well as the efficiency and adaptivity of deep embedding models to achieve a cost-effective GED solver. Inspired by dynamic programming, node-level embedding is designated in a dynamic reuse fashion and suboptimal branches are encouraged to be pruned. To this end, our method can be readily integrated into A* procedure in a dynamic fashion, as well as significantly reduce the computational burden with a learned heuristic. Experimental results on different graph datasets show that our approach can remarkably ease the search process of A* without sacrificing much accuracy. To our best knowledge, this work is also the first deep learning-based GED method for recovering the edit path.