Research map / Graph learning / Graph algorithms and clustering
Graph Edit Distance with General Costs Using Neural Set Divergence
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GraphEdX, a neural graph edit distance estimator that handles general (non-uniform) costs for node/edge insertion and deletion by replacing the QAP terms with neural set-divergence surrogates over node and node-pair embeddings, aligned via a Gumbel-Sinkhorn permutation generator.
Problem
Neural GED estimation has largely assumed uniform edit costs or used Euclidean distances between graph embeddings, so it cannot model edit operations with different costs.
Approach
Formulate GED under four general costs as a QAP, relax it into three families of differentiable set-divergence surrogates (MSM, MMS, XOR) over embeddings of all node pairs (edges and non-edges), and learn node alignments with a Gumbel-Sinkhorn generator whose node-pair alignment is derived from the node alignment for consistency.
Key results
- Under uniform costs, GraphEdX achieves test MSE of 0.492 on Mutag, 0.429 on Code2, 0.781 on Molhiv, 0.764 on Molpcba and 0.565 on AIDS, beating all nine neural baselines.
- Under non-uniform costs (node deletion 3, node addition 1, edge deletion 2, edge addition 1), GraphEdX reaches MSE 1.478 on Code2 versus 3.025 for the best baseline (ISONET), a margin of about 30% or more.
- Adapting baselines' distances to the proposed cost-guided set distance reduces their MSE in most cases, but GraphEdX still outperforms them.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GraphEdX instead of the strongest listed baseline | GED estimation · Mutag, uniform cost | MSE: 0.719 -> 0.492 | Helped |
| Use GraphEdX instead of the strongest listed baseline | GED estimation · Code2, uniform cost | MSE: 0.879 -> 0.429 | Helped |
| Use GraphEdX instead of the strongest listed baseline | GED estimation · Molhiv, uniform cost | MSE: 1.138 -> 0.781 | Helped |
| Use GraphEdX instead of the strongest listed baseline | GED estimation · Molpcba, uniform cost | MSE: 0.862 -> 0.764 | Helped |
| Use GraphEdX instead of the strongest listed baseline | GED estimation · AIDS, uniform cost | MSE: 0.627 -> 0.565 | Helped |
| Use GraphEdX instead of the strongest listed baseline | GED estimation · Mutag, non-uniform cost | MSE: 1.758 -> 1.134 | Helped |
| Use GraphEdX instead of the strongest listed baseline | GED estimation · Code2, non-uniform cost | MSE: 3.025 -> 1.478 | Helped |
| Use GraphEdX instead of the strongest listed baseline | GED estimation · Molhiv, non-uniform cost | MSE: 2.371 -> 1.804 | Helped |
| Use GraphEdX instead of the strongest listed baseline | GED estimation · Molpcba, non-uniform cost | MSE: 2.057 -> 1.677 | Helped |
| Use GraphEdX instead of the strongest listed baseline | GED estimation · AIDS, non-uniform cost | MSE: 1.581 -> 1.252 | Helped |
| Add trainable representations for non-edges and use all node-pairs (ablation) | GraphEdX · Mutag, Code2, and Molhiv, uniform cost | MSE: 0.566 -> 0.492; 0.683 -> 0.429; 0.858 -> 0.781 | Helped |
| Add trainable representations for non-edges and use all node-pairs (ablation) | GraphEdX · Mutag, Code2, and Molhiv, uniform cost | MSE: 0.596 -> 0.492; 0.760 -> 0.429; 0.862 -> 0.781 | Helped |
Surprising findings
- Adding cost-guided distance to baselines such as GMN-Match improves them substantially, showing that the Euclidean distance itself is a poor fit for GED.
Limitations
- Memory cost grows with the number of node pairs (N choose 2 by N choose 2), which may be prohibitive for large graphs.
- Assumes fixed edit costs across all graph pairs in a dataset.
- Experiments restricted to unattributed graphs or label substitution; extension to richly attributed graphs left to future work.
Experimental setup
Datasets: Mutagenicity Ogbg-Code2 Ogbg-Molhiv Ogbg-Molpcba AIDS Linux Yeast
Benchmarks: Mutagenicity Ogbg-Code2 Ogbg-Molhiv Ogbg-Molpcba AIDS
Metrics: MSE
Baselines: GMN-Match GMN-Embed ISONET GREED ERIC SimGNN H2MN GraphSim EGSC
Builds on: Gumbel-Sinkhorn GMN ISONET GREED
Closest papers by meaning
- Position: Graph Matching Systems Deserve Better Benchmarks (ICML 2025 · similarity 0.92)
- GRAIL: Graph Edit Distance and Node Alignment using LLM-Generated Code (ICML 2025 · similarity 0.91)
- Towards Unsupervised Training of Matching-based Graph Edit Distance Solver via Preference-aware GAN (NeurIPS 2025 · similarity 0.88)
- GraSP: Simple Yet Effective Graph Similarity Predictions (AAAI 2025 · similarity 0.86)
- Gradient Rewiring for Editable Graph Neural Network Training (NeurIPS 2024 · similarity 0.86)
- Neural Gaussian Similarity Modeling for Differential Graph Structure Learning (AAAI 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.