Reproduce “GRAIL: Graph Edit Distance and Node Alignment Using LLM-Generated Code” on OpenResearch

About this paper

Samidha Verma, Arushi Goyal, Ananya Mathur, Ankit Anand, Sayan Ranu

GRAIL, developed by researchers from IIT Delhi and Google DeepMind, introduces a framework that uses large language models to generate executable programs for approximating Graph Edit Distance, achieving superior approximation quality (e.g., 0.55 RMSE on IMDB compared to 4.8 for the next best method) and robust cross-domain generalization without requiring computationally intensive ground-truth labels for training.

Key insights

• Leveraging LLMs to generate executable code for combinatorial problems can yield highly interpretable and generalizable solutions, moving beyond black-box predictive models.
• Reframing an NP-hard problem like GED to optimize a polynomial-time computable upper bound enables effective learning without expensive ground-truth supervision.
• An evolutionary, self-tuning framework that selects a diverse set of programs can achieve superior approximation quality and robust generalization across different graph types, sizes, and domains.

Summary by alphaXiv.