# GEDAN: Learning the Edit Costs for Graph Edit Distance

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 84 references that are in the map.
- First posted on arXiv 5 Aug 2025.

## Builds on (most cited first, 30 of 32)

- [Fast R-CNN](https://mlsanity.com/paper/1504.08083/) (2015)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [FaceNet: A Unified Embedding for Face Recognition and Clustering](https://mlsanity.com/paper/1503.03832/) (2015)
- [Graph Contrastive Learning with Augmentations](https://mlsanity.com/paper/2010.13902/) (2020)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [Automatic chemical design using a data-driven continuous representation of molecules](https://mlsanity.com/paper/1610.02415/) (2016)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Deep Metric Learning via Lifted Structured Feature Embedding](https://mlsanity.com/paper/1511.06452/) (2015)
- [Parameterized Explainer for Graph Neural Network](https://mlsanity.com/paper/2011.04573/) (2020)
- [Multi-Similarity Loss with General Pair Weighting for Deep Metric Learning](https://mlsanity.com/paper/1904.06627/) (2019)
- [OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs](https://mlsanity.com/paper/2103.09430/) (2021)
- [On Explainability of Graph Neural Networks via Subgraph Explorations](https://mlsanity.com/paper/2102.05152/) (2021)
- [Markerless tracking of user-defined features with deep learning](https://mlsanity.com/paper/1804.03142/) (2018)
- [Learning Latent Permutations with Gumbel-Sinkhorn Networks](https://mlsanity.com/paper/1802.08665/) (2018)
- [Interpreting Graph Neural Networks for NLP With Differentiable Edge Masking](https://mlsanity.com/paper/2010.00577/) (2020)
- [SimGNN: A Neural Network Approach to Fast Graph Similarity Computation](https://mlsanity.com/paper/1808.05689/) (2018)
- [A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learning](https://mlsanity.com/paper/2110.01515/) (2021)
- [Ranked List Loss for Deep Metric Learning](https://mlsanity.com/paper/1903.03238/) (2019)
- [GKAN: Graph Kolmogorov-Arnold Networks](https://mlsanity.com/paper/2406.06470/) (2024)
- [Graph2Seq: Graph to Sequence Learning with Attention-based Neural Networks](https://mlsanity.com/paper/1804.00823/) (2018)
- [Residual Connections and Normalization Can Provably Prevent Oversmoothing in GNNs](https://mlsanity.com/paper/2406.02997/) (2024)
- [GREED: A Neural Framework for Learning Graph Distance Functions](https://mlsanity.com/paper/2112.13143/) (2021)
- [Efficient Graph Similarity Computation with Alignment Regularization](https://mlsanity.com/paper/2406.14929/) (2024)
- [The Interpretable and Effective Graph Neural Additive Networks](https://mlsanity.com/paper/2406.01317/) (2024)
- [Accelerating Sinkhorn Algorithm with Sparse Newton Iterations](https://mlsanity.com/paper/2401.12253/) (2024)
- [Graph Edit Distance with General Costs Using Neural Set Divergence](https://mlsanity.com/paper/2409.17687/) (2024)
- [mathbbX-Sample Contrastive Loss: Improving Contrastive Learning with Sample Similarity Graphs](https://mlsanity.com/paper/2407.18134/) (2024)

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

- [Towards Metric-Faithful Neural Graph Matching](https://mlsanity.com/paper/2605.06588/) (2026)

## Abstract (arXiv)

Graph Edit Distance (GED) is defined as the minimum cost transformation of one graph into another and is a widely adopted metric for measuring the dissimilarity between graphs. The major problem of GED is that its computation is NP-hard, which has in turn led to the development of various approximation methods, including approaches based on neural networks (NN). However, most NN methods assume a unit cost for edit operations -- a restrictive and often unrealistic simplification, since topological and functional distances rarely coincide in real-world data. In this paper, we propose a fully end-to-end Graph Neural Network framework for learning the edit costs for GED, at a fine-grained level, aligning topological and task-specific similarity. Our method combines an unsupervised self-organizing mechanism for GED approximation with a Generalized Additive Model that flexibly learns contextualized edit costs. Experiments demonstrate that our approach overcomes the limitations of non-end-to-end methods, yielding directly interpretable graph matchings, uncovering meaningful structures in complex graphs, and showing strong applicability to domains such as molecular analysis.