# GRAIL: Graph Edit Distance and Node Alignment Using LLM-Generated Code

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 May 2025.

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

- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [(X)-evolve: Solution space evolution powered by large language models](https://mlsanity.com/paper/2508.07932/) (2025)
- [Automating modeling in mechanics: LLMs as designers of physics-constrained neural networks for constitutive modeling of materials](https://mlsanity.com/paper/2512.01735/) (2025)
- [Closing Reasoning Gaps in Clinical Agents with Differential Reasoning Learning](https://mlsanity.com/paper/2602.09945/) (2026)
- [ReLU Networks for Exact Generation of Similar Graphs](https://mlsanity.com/paper/2604.05929/) (2026)
- [Towards Metric-Faithful Neural Graph Matching](https://mlsanity.com/paper/2605.06588/) (2026)
- [LLM-driven design of physics-constrained constitutive models: two agents are better than one](https://mlsanity.com/paper/2605.23754/) (2026)
- [Project Auto-World: Towards Automated Benchmarking of Neural Relational Reasoners](https://mlsanity.com/paper/2606.24965/) (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 widely used metric for measuring similarity between two graphs. Computing the optimal GED is NP-hard, leading to the development of various neural and non-neural heuristics. While neural methods have achieved improved approximation quality compared to non-neural approaches, they face significant challenges: (1) They require large amounts of ground truth data, which is itself NP-hard to compute. (2) They operate as black boxes, offering limited interpretability. (3) They lack cross-domain generalization, necessitating expensive retraining for each new dataset. We address these limitations with GRAIL, introducing a paradigm shift in this domain. Instead of training a neural model to predict GED, GRAIL employs a novel combination of large language models (LLMs) and automated prompt tuning to generate a program that is used to compute GED. This shift from predicting GED to generating programs imparts various advantages, including end-to-end interpretability and an autonomous self-evolutionary learning mechanism without ground-truth supervision. Extensive experiments on seven datasets confirm that GRAIL not only surpasses state-of-the-art GED approximation methods in prediction quality but also achieves robust cross-domain generalization across diverse graph distributions.