# Towards Unsupervised Training of Matching-based Graph Edit Distance Solver via Preference-aware GAN

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 41 references that are in the map.
- First posted on arXiv 16 May 2025.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Learning Latent Permutations with Gumbel-Sinkhorn Networks](https://mlsanity.com/paper/1802.08665/) (2018)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training](https://mlsanity.com/paper/2009.03294/) (2020)
- [Learning the Travelling Salesperson Problem Requires Rethinking Generalization](https://mlsanity.com/paper/2006.07054/) (2020)
- [SimGNN: A Neural Network Approach to Fast Graph Similarity Computation](https://mlsanity.com/paper/1808.05689/) (2018)
- [Learning-based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matching](https://mlsanity.com/paper/1809.04440/) (2018)
- [Multilevel Graph Matching Networks for Deep Graph Similarity Learning](https://mlsanity.com/paper/2007.04395/) (2020)
- [Efficient Graph Similarity Computation with Alignment Regularization](https://mlsanity.com/paper/2406.14929/) (2024)
- [Combinatorial Learning of Graph Edit Distance via Dynamic Embedding](https://mlsanity.com/paper/2011.15039/) (2020)
- [Graph Edit Distance Reward: Learning to Edit Scene Graph](https://mlsanity.com/paper/2008.06651/) (2020)
- [MATA*: Combining Learnable Node Matching with A* Algorithm for Approximate Graph Edit Distance Computation](https://mlsanity.com/paper/2311.02356/) (2023)
- [Computing Approximate Graph Edit Distance via Optimal Transport](https://mlsanity.com/paper/2412.18857/) (2024)
- [DiffGED: Computing Graph Edit Distance via Diffusion-based Graph Matching](https://mlsanity.com/paper/2503.18245/) (2025)

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

- [GraViti: Graph-Level Variational Autoencoders with Relaxed Permutation Invariance](https://mlsanity.com/paper/2605.16668/) (2026)
- [GCCM: Enhancing Generative Graph Prediction via Contrastive Consistency Model](https://mlsanity.com/paper/2605.05689/) (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 fundamental graph similarity metric widely used in various applications. However, computing GED is an NP-hard problem. Recent state-of-the-art hybrid GED solver has shown promising performance by formulating GED as a bipartite graph matching problem, then leveraging a generative diffusion model to predict node matching between two graphs, from which both the GED and its corresponding edit path can be extracted using a traditional algorithm. However, such methods typically rely heavily on ground-truth supervision, where the ground-truth node matchings are often costly to obtain in real-world scenarios. In this paper, we propose GEDRanker, a novel unsupervised GAN-based framework for GED computation. Specifically, GEDRanker consists of a matching-based GED solver and introduces an interpretable preference-aware discriminator. By leveraging preference signals over different node matchings derived from edit path lengths, the discriminator can guide the matching-based solver toward generating high-quality node matching without the need for ground-truth supervision. Extensive experiments on benchmark datasets demonstrate that our GEDRanker enables the matching-based GED solver to achieve near-optimal solution quality without any ground-truth supervision.