Research map / Graph learning / Graph algorithms and clustering

Position: Graph Matching Systems Deserve Better Benchmarks

ICML 2025 · Graph learning › Graph algorithms and clustering · approach: Deep learning for graph matching

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.

Shows that widely used graph edit distance (GED) datasets suffer from isomorphism-based train-test leakage, proposes leakage-free pair generation, cost-invariant data augmentation and adversarial cost-variant test sets, and benchmarks neural GED models showing poor generalization.

Problem

Neural graph edit distance (GED) and graph matching benchmarks are small, reused for years, contain isomorphic graphs across train and test splits (leakage), and only use uniform edit costs, so reported gains may reflect memorization rather than generalization.

Approach

Shows that the optimal node alignment for GED is invariant across cost settings with zero substitution cost and positive other costs, enabling cheap ground-truth GED for many cost variants from one solver run, plus isomorphism-filtered splits and cost-varied adversarial test sets.

Key results

• Removing isomorphic leakage raises MSE across models; e.g., ISONET's MSE on LINUX rises from 0.323 to 5.146 with Ktau dropping from 0.903 to 0.646 (intra-test).
• Intra-test pair leakage reaches 91.3% on LINUX and cross-train-test leakage reaches 94.8% on LINUX.
• On Code2 under cost-variant tests (C0-C6), most models show Ktau fluctuations up to 0.4, and GRAPHEDX stays best on high edge-cost settings.

Measured effects reported in the paper

Surprising findings

• Leakage from isomorphic graphs inflates reported performance, and GEDGNN's Ktau is near zero or negative even on standard splits.
• Node-centric models degrade sharply as edge edit costs grow, despite low MSE on equal-cost settings.

Limitations

• Theorem 4.2 holds only under the assumption cNS=0 and other costs positive; general cost settings are not covered.
• Leakage analysis is limited to small benchmark datasets (LINUX, IMDB, AIDS) and a few neural baselines.

Experimental setup

Datasets: LINUX IMDB AIDS Code2 Mutag Molhiv Molpcba

Benchmarks: LINUX AIDS IMDB Code2 Mutag Molhiv Molpcba

Metrics: MSE Kendall's Tau

Baselines: GMN-Match GMN-Embed SimGNN GraphSim GREED GEDGNN ISONET H2MN EGSC ERIC GRAPHEDX

Builds on: SimGNN GRAPHEDX GMN F2 exact GED solver Sinkhorn/Gumbel-Sinkhorn alignment

Closest papers by meaning

• Towards Unsupervised Training of Matching-based Graph Edit Distance Solver via Preference-aware GAN (NeurIPS 2025 · similarity 0.93)
• Graph Edit Distance with General Costs Using Neural Set Divergence (NeurIPS 2024 · similarity 0.92)
• GRAIL: Graph Edit Distance and Node Alignment using LLM-Generated Code (ICML 2025 · similarity 0.89)
• GraSP: Simple Yet Effective Graph Similarity Predictions (AAAI 2025 · similarity 0.88)
• No Metric to Rule Them All: Toward Principled Evaluations of Graph-Learning Datasets (ICML 2025 · similarity 0.86)
• Charting the Design Space of Neural Graph Representations for Subgraph Matching (ICLR 2025 · similarity 0.86)