# Graph Edit Distance with General Costs Using Neural Set Divergence

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 62 references that are in the map.
- First posted on arXiv 26 Sep 2024.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Input Convex Neural Networks](https://mlsanity.com/paper/1609.07152/) (2016)
- [Graph Matching Networks for Learning the Similarity of Graph Structured Objects](https://mlsanity.com/paper/1904.12787/) (2019)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Learning Latent Permutations with Gumbel-Sinkhorn Networks](https://mlsanity.com/paper/1802.08665/) (2018)
- [Large-Scale Optimal Transport and Mapping Estimation](https://mlsanity.com/paper/1711.02283/) (2017)
- [SimGNN: A Neural Network Approach to Fast Graph Similarity Computation](https://mlsanity.com/paper/1808.05689/) (2018)
- [Score-based Generative Neural Networks for Large-Scale Optimal Transport](https://mlsanity.com/paper/2110.03237/) (2021)
- [Banach Wasserstein GAN](https://mlsanity.com/paper/1806.06621/) (2018)
- [Neural Subgraph Matching](https://mlsanity.com/paper/2007.03092/) (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)
- [On Scalable and Efficient Computation of Large Scale Optimal Transport](https://mlsanity.com/paper/1905.00158/) (2019)
- [Efficient Graph Similarity Computation with Alignment Regularization](https://mlsanity.com/paper/2406.14929/) (2024)
- [Scalable Nearest Neighbor Search for Optimal Transport](https://mlsanity.com/paper/1910.04126/) (2019)
- [Understanding Isomorphism Bias in Graph Data Sets](https://mlsanity.com/paper/1910.12091/) (2019)
- [Maximum Common Subgraph Guided Graph Retrieval: Late and Early Interaction Networks](https://mlsanity.com/paper/2210.11020/) (2022)
- [New Techniques for Graph Edit Distance Computation](https://mlsanity.com/paper/1908.00265/) (2019)
- [Non-Metric Space Library Manual](https://mlsanity.com/paper/1508.05470/) (2015)
- [Efficient Graph Edit Distance Computation and Verification via Anchor-aware Lower Bound Estimation](https://mlsanity.com/paper/1709.06810/) (2017)

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

- [The quest for the GRAph Level autoEncoder (GRALE)](https://mlsanity.com/paper/2505.22109/) (2025)
- [STED and Consistency Scoring: A Framework for Evaluating LLM Structured Output Reliability](https://mlsanity.com/paper/2512.23712/) (2025)
- [Rethinking Flexible Graph Similarity Computation: One-step Alignment with Global Guidance](https://mlsanity.com/paper/2504.06533/) (2025)
- [GEDAN: Learning the Edit Costs for Graph Edit Distance](https://mlsanity.com/paper/2508.03111/) (2025)
- [Instruction set for the representation of graphs](https://mlsanity.com/paper/2603.11039/) (2026)
- [HeGMN: Heterogeneous Graph Matching Network for Learning Graph Similarity](https://mlsanity.com/paper/2503.08739/) (2025)
- [Contextual Tokenization for Graph Inverted Indices](https://mlsanity.com/paper/2510.22479/) (2025)
- [Towards Metric-Faithful Neural Graph Matching](https://mlsanity.com/paper/2605.06588/) (2026)
- [Agents for Experiments, Experiments for Agents: A Design Grammar for AI-Enabled Experimental Science](https://mlsanity.com/paper/2605.17746/) (2026)
- [Alignment-Guided Largest Table Overlap Size Estimation](https://mlsanity.com/paper/2607.03049/) (2026)
- [Revisiting the Generalization of Neural Graph Edit Distance Models](https://mlsanity.com/paper/2610.04644/) (2026)

## Abstract (arXiv)

Graph Edit Distance (GED) measures the (dis-)similarity between two given graphs, in terms of the minimum-cost edit sequence that transforms one graph to the other. However, the exact computation of GED is NP-Hard, which has recently motivated the design of neural methods for GED estimation. However, they do not explicitly account for edit operations with different costs. In response, we propose GRAPHEDX, a neural GED estimator that can work with general costs specified for the four edit operations, viz., edge deletion, edge addition, node deletion and node addition. We first present GED as a quadratic assignment problem (QAP) that incorporates these four costs. Then, we represent each graph as a set of node and edge embeddings and use them to design a family of neural set divergence surrogates. We replace the QAP terms corresponding to each operation with their surrogates. Computing such neural set divergence require aligning nodes and edges of the two graphs. We learn these alignments using a Gumbel-Sinkhorn permutation generator, additionally ensuring that the node and edge alignments are consistent with each other. Moreover, these alignments are cognizant of both the presence and absence of edges between node-pairs. Experiments on several datasets, under a variety of edit cost settings, show that GRAPHEDX consistently outperforms state-of-the-art methods and heuristics in terms of prediction error.