# Computing Approximate Graph Edit Distance via Optimal Transport

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 70 references that are in the map.
- First posted on arXiv 25 Dec 2024.

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

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018)
- [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019)
- [Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical properties](https://mlsanity.com/paper/1811.02834/) (2018)
- [SimGNN: A Neural Network Approach to Fast Graph Similarity Computation](https://mlsanity.com/paper/1808.05689/) (2018)
- [GOT: An Optimal Transport framework for Graph comparison](https://mlsanity.com/paper/1906.02085/) (2019)
- [Vocabulary Learning via Optimal Transport for Neural Machine Translation](https://mlsanity.com/paper/2012.15671/) (2020)
- [GREED: A Neural Framework for Learning Graph Distance Functions](https://mlsanity.com/paper/2112.13143/) (2021)
- [Inverse optimal transport](https://mlsanity.com/paper/1905.03950/) (2019)
- [Combinatorial Learning of Graph Edit Distance via Dynamic Embedding](https://mlsanity.com/paper/2011.15039/) (2020)
- [Learning to Match via Inverse Optimal Transport](https://mlsanity.com/paper/1802.03644/) (2018)
- [Explainable Legal Case Matching via Inverse Optimal Transport-based Rationale Extraction](https://mlsanity.com/paper/2207.04182/) (2022)
- [COPT: Coordinated Optimal Transport for Graph Sketching](https://mlsanity.com/paper/2003.03892/) (2020)
- [MATA*: Combining Learnable Node Matching with A* Algorithm for Approximate Graph Edit Distance Computation](https://mlsanity.com/paper/2311.02356/) (2023)
- [Double-Bounded Optimal Transport for Advanced Clustering and Classification](https://mlsanity.com/paper/2401.11418/) (2024)
- [Neural Attributed Community Search at Billion Scale](https://mlsanity.com/paper/2403.18874/) (2024)
- [Fast Gradient Computation for Gromov-Wasserstein Distance](https://mlsanity.com/paper/2404.08970/) (2024)

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

- [Towards Unsupervised Training of Matching-based Graph Edit Distance Solver via Preference-aware GAN](https://mlsanity.com/paper/2506.01977/) (2025)
- [Optimal Transport for Brain-Image Alignment: Unveiling Redundancy and Synergy in Neural Information Processing](https://mlsanity.com/paper/2503.10663/) (2025)
- [Rethinking Flexible Graph Similarity Computation: One-step Alignment with Global Guidance](https://mlsanity.com/paper/2504.06533/) (2025)
- [GED-Consistent Disentanglement of Aligned and Unaligned Substructures for Graph Similarity Learning](https://mlsanity.com/paper/2511.19837/) (2025)
- [U-CECE: A Universal Multi-Resolution Framework for Conceptual Counterfactual Explanations](https://mlsanity.com/paper/2604.08295/) (2026)
- [Revisiting the Generalization of Neural Graph Edit Distance Models](https://mlsanity.com/paper/2610.04644/) (2026)

## Abstract (arXiv)

Given a graph pair (G1, G2), graph edit distance (GED) is defined as the minimum number of edit operations converting G1 to G2. GED is a fundamental operation widely used in many applications, but its exact computation is NP-hard, so the approximation of GED has gained a lot of attention. Data-driven learning-based methods have been found to provide superior results compared to classical approximate algorithms, but they directly fit the coupling relationship between a pair of vertices from their vertex features. We argue that while pairwise vertex features can capture the coupling cost (discrepancy) of a pair of vertices, the vertex coupling matrix should be derived from the vertex-pair cost matrix through a more well-established method that is aware of the global context of the graph pair, such as optimal transport. In this paper, we propose an ensemble approach that integrates a supervised learning-based method and an unsupervised method, both based on optimal transport. Our learning method, GEDIOT, is based on inverse optimal transport that leverages a learnable Sinkhorn algorithm to generate the coupling matrix. Our unsupervised method, GEDGW, models GED computation as a linear combination of optimal transport and its variant, Gromov-Wasserstein discrepancy, for node and edge operations, respectively, which can be solved efficiently without needing the ground truth. Our ensemble method, GEDHOT, combines GEDIOT and GEDGW to further boost the performance. Extensive experiments demonstrate that our methods significantly outperform the existing methods in terms of the performance of GED computation, edit path generation, and model generalizability.