Research map / Graph learning / Graph algorithms and clustering
GRAIL: Graph Edit Distance and Node Alignment using LLM-Generated Code
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.
Grail uses Gemini-1.5 Pro with FunSearch-style evolutionary prompt tuning to generate programs that output node-weight matrices for bipartite matching, yielding a GED upper bound without ground-truth GED supervision.
Problem
Approximating graph edit distance (GED), an NP-hard and APX-hard problem, with methods that are accurate, interpretable, cross-domain generalizable, and do not require expensive NP-hard ground-truth GED labels.
Approach
Instead of training a neural network to predict GED, an LLM evolves programs that compute node-similarity weight matrices; each program yields a bipartite node mapping whose edit cost is a polynomial-time upper bound on GED. A greedy submodular selection picks a budget of b programs, and the objective (sum of upper bounds on training pairs) serves as the loss, eliminating the need for ground-truth
Key results
- Grail achieves RMSE 0.57 on AIDS, 0.13 on Linux and 0.55 on IMDB, ranking top-2 on average (avg rank 2) against neural and non-neural baselines.
- Grail-Mix attains the best average rank among methods in the RMSE table (2.17) and EMR 0.80 on AIDS, approximately 1 on Linux and IMDB.
- Grail-Mix on IMDB case study predicts GED 4 matching ground truth while GedGNN predicts 20.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| train on a mixture of graph pairs from multiple datasets instead of dataset-specific training | GRAIL · AIDS | RMSE: 0.57 -> 0.64 | Hurt |
| train on a mixture of graph pairs from multiple datasets instead of dataset-specific training | GRAIL · Linux | RMSE: 0.13 -> 0.11 | Helped |
| train on a mixture of graph pairs from multiple datasets instead of dataset-specific training | GRAIL · IMDB | RMSE: 0.55 -> 0.53 | Helped |
| train on a mixture of graph pairs from multiple datasets instead of dataset-specific training | GRAIL · ogbg-molhiv | RMSE: 2.96* -> 2.96 | No clear effect |
| train on a mixture of graph pairs from multiple datasets instead of dataset-specific training | GRAIL · ogbg-code2 | RMSE: 4.22 -> 4.10 | Helped |
| train on a mixture of graph pairs from multiple datasets instead of dataset-specific training | GRAIL · ogbg-molpcba | RMSE: 3.18 -> 3.40 | Hurt |
| select the top-b programs using individual upper bounds rather than greedy submodular optimization (ablation) | GRAIL · AIDS | RMSE | Hurt |
| increase the number of programs per LLM response beyond 2 (ablation) | GRAIL · multiple datasets | quality metrics | No clear effect |
| increase the function budget to approximately 15 mappings (ablation) | GRAIL · multiple datasets | upper bound | Helped |
| use GRAIL-Mix programs rather than GRAIL programs across datasets | GRAIL · multiple datasets | RMSE | Mixed |
| use GRAIL-Mix rather than GEDGNN | GED approximation on the IMDB case study · IMDB case study | GED: 20 -> 4 | Helped |
| train on one dataset and evaluate on other datasets rather than matching train and test datasets | GRAIL · inter-domain datasets | RMSE | No clear effect |
Surprising findings
- Grail trained without any ground-truth GED outperforms neural methods trained on 10,000 NP-hard-labeled pairs on several datasets.
- Neural GNN methods (GedGNN) perform poorly on unlabeled, dense IMDB graphs, which the authors attribute to oversquashing.
Limitations
- Inference slower on larger, denser datasets (IMDB, ogbg) due to mapping computation overhead.
- Relies on proprietary Gemini-1.5 Pro LLM calls, reproducibility depends on API access.
- Interpretability of generated programs not analysed with domain experts.
Experimental setup
Datasets: AIDS Linux IMDB ogbg-molhiv ogbg-molpcba ogbg-code2 ogbg-ppa
Benchmarks: AIDS Linux IMDB ogbg-molhiv ogbg-code2 ogbg-molpcba
Metrics: RMSE Exact Match Ratio
Baselines: Greed GedGNN ERIC GraphEdX H2MN Adj-IP Node LP-GED-F2 Branch-Tight Compact-MIP IPFP
Builds on: FunSearch Neighbor-biased mapper MIP-F2
Closest papers by meaning
- Graph Edit Distance with General Costs Using Neural Set Divergence (NeurIPS 2024 · similarity 0.91)
- Position: Graph Matching Systems Deserve Better Benchmarks (ICML 2025 · similarity 0.89)
- Towards Unsupervised Training of Matching-based Graph Edit Distance Solver via Preference-aware GAN (NeurIPS 2025 · similarity 0.87)
- GraSP: Simple Yet Effective Graph Similarity Predictions (AAAI 2025 · similarity 0.87)
- A Unified Graph Language Model for Multi-Domain Multi-Task Graph Alignment Instruction Tuning (NeurIPS 2026 · similarity 0.86)
- On the Benefits of Attribute-Driven Graph Domain Adaptation (ICLR 2025 · similarity 0.84)
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.