Research map / Graph learning / Graph algorithms and clustering
Towards Unsupervised Training of Matching-based Graph Edit Distance Solver via Preference-aware GAN
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 GEDRanker, a GAN-style unsupervised training framework that trains a diffusion-based node-matching GED solver using a preference-aware (BPR-ranking) discriminator over edit-path costs, without ground-truth matchings.
Problem
Supervised hybrid GED solvers need ground-truth node matchings and GED values, which are costly or infeasible to obtain due to NP-hardness; unsupervised training of such matching-based GED solvers is underexplored.
Approach
Replace supervised reconstruction with a GAN where a discriminator is trained with a BPR ranking loss to prefer node matchings yielding shorter edit paths (against the current best and last decoded matchings), while the diffusion solver uses Gumbel-Sinkhorn relaxation to be trained to maximize the discriminator score, combined with a reconstruction loss on the best-so-far matching.
Key results
- On AIDS700, GEDRanker reaches 92.6% accuracy and MAE 0.088 versus DiffGED's 98% and 0.022 (supervised), outperforming other supervised baselines such as GEDGNN (52.5%).
- On Linux, GEDRanker achieves 99.5% accuracy and MAE 0.01, close to DiffGED's 100%.
- On IMDB, GEDRanker achieves 94% accuracy vs. DiffGED's 94.6%, and on IMDB-large it reaches average GED 140.138 vs. GEDGW's 140.278, with lower time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train the DiffGED-based solver without ground-truth labels using GEDRanker | DiffGED · AIDS700 | MAE: 0.022 -> 0.088 | Hurt |
| Train the DiffGED-based solver without ground-truth labels using GEDRanker | DiffGED · Linux | MAE: 0.0 -> 0.01 | Hurt |
| Train the DiffGED-based solver without ground-truth labels using GEDRanker | DiffGED · IMDB | Spearman rank correlation: 0.982 -> 0.999 | Helped |
| Add exploration to current-best-solution recovery (ablation) | GEDRanker · AIDS700 | MAE: 0.549 -> 0.088 | Helped |
| Add exploration to current-best-solution recovery (ablation) | GEDRanker · Linux | MAE: 0.079 -> 0.01 | Helped |
| Replace REINFORCE exploration with the preference-aware GAN objective (ablation) | GEDRanker · AIDS700 | MAE: 0.458 -> 0.088 | Helped |
| Replace REINFORCE exploration with the preference-aware GAN objective (ablation) | GEDRanker · Linux | MAE: 0.04 -> 0.01 | Helped |
| Use a preference-aware discriminator instead of direct edit-path-length estimation (ablation) | GEDRanker · AIDS700 | MAE: 0.237 -> 0.088 | Helped |
| Use a preference-aware discriminator instead of direct edit-path-length estimation (ablation) | GEDRanker · Linux | MAE: 0.017 -> 0.01 | Helped |
| Replace BPR with Hinge ranking loss (ablation) | GEDRanker · AIDS700 | MAE: 0.088 -> 0.114 | Hurt |
| Replace BPR with Hinge ranking loss (ablation) | GEDRanker · Linux | MAE: 0.01 -> 0.002 | Helped |
| Replace the pair-interaction discriminator with matching-cost architecture (ablation) | GEDRanker · AIDS700 | MAE: 0.088 -> 0.528 | Hurt |
Surprising findings
- Setting the loss weight lambda fixed at 1 (pure exploration throughout training) performs very poorly on AIDS700 (39.3% accuracy), so annealing lambda to 0 is necessary.
- A discriminator that outputs a linear cost-matrix score <pi, C> performs much worse than the AGNN-based discriminator (66.3% vs 92.6% accuracy on AIDS700).
Limitations
- No error bars or statistical significance reported across runs.
- Performance remains slightly below supervised DiffGED on AIDS700 and IMDB.
- Training on large graphs relies on synthetic/approximate GED labels for evaluation (IMDB approximated ground truth).
Experimental setup
Datasets: AIDS700 Linux IMDB IMDB-large
Benchmarks: AIDS700 Linux IMDB IMDB-large
Metrics: MAE Accuracy Spearman rho Kendall tau precision@10 precision@20 time (s)
Baselines: Hungarian VJ GEDGW Noah GENN-A* MATA* GEDGNN GEDIOT DiffGED REINFORCE-based variant
Builds on: DiffGED REINFORCE Gumbel-Sinkhorn Bayesian Personalized Ranking GIN AGNN
Closest papers by meaning
- Position: Graph Matching Systems Deserve Better Benchmarks (ICML 2025 · similarity 0.93)
- Towards Generative Graph Matching for Graph Edit Distance Computation (ICML 2026 · similarity 0.92)
- Graph Edit Distance with General Costs Using Neural Set Divergence (NeurIPS 2024 · similarity 0.88)
- GRAIL: Graph Edit Distance and Node Alignment using LLM-Generated Code (ICML 2025 · similarity 0.87)
- Learning Partial Graph Matching via Optimal Partial Transport (ICLR 2025 · similarity 0.86)
- GraSP: Simple Yet Effective Graph Similarity Predictions (AAAI 2025 · 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.