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

📄 arXiv: 2505.02124v1 📥 PDF

作者: Samidha Verma, Arushi Goyal, Ananya Mathur, Ankit Anand, Sayan Ranu

分类: cs.LG

发布日期: 2025-05-04

💡 一句话要点

提出GRAIL以解决图编辑距离计算中的数据需求与可解释性问题

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 图编辑距离 大型语言模型 自动化提示调优 可解释性 跨领域泛化 神经网络 数据分析

📋 核心要点

  1. 现有方法在计算图编辑距离时面临数据需求大、可解释性差和跨领域泛化能力不足等挑战。
  2. GRAIL通过生成计算图编辑距离的程序，利用大型语言模型和自动化提示调优，提供了新的解决方案。
  3. 在七个数据集上的实验结果显示，GRAIL在预测质量上超越了现有最先进的GED近似方法，并实现了良好的跨领域泛化能力。

📝 摘要（中文）

图编辑距离（GED）是衡量两个图相似性的广泛使用指标。计算最优GED是NP难题，导致各种神经和非神经启发式方法的发展。尽管神经方法在近似质量上优于非神经方法，但面临着数据需求大、可解释性差和跨领域泛化能力不足等挑战。GRAIL通过结合大型语言模型（LLMs）和自动化提示调优，转变为生成计算GED的程序，从而克服这些限制。实验表明，GRAIL在七个数据集上超越了现有的GED近似方法，并在不同图分布上实现了稳健的跨领域泛化。

🔬 方法详解

问题定义：本论文旨在解决图编辑距离（GED）计算中的数据需求、可解释性和跨领域泛化能力不足的问题。现有的神经方法依赖大量的真实数据，而这些数据的计算本身也是NP难题。

核心思路：GRAIL的核心思路是通过生成计算GED的程序，而不是直接预测GED。这种方法利用大型语言模型（LLMs）和自动化提示调优，能够实现端到端的可解释性和自我进化的学习机制，无需真实标签的监督。

技术框架：GRAIL的整体架构包括数据输入、提示生成、程序生成和GED计算四个主要模块。首先，输入图数据，然后通过LLMs生成相应的计算程序，最后执行该程序以获得GED。

关键创新：GRAIL的主要创新在于将传统的预测模型转变为程序生成模型，这一转变使得模型具备了更好的可解释性和自我学习能力，与现有方法形成了本质区别。

关键设计：在设计中，GRAIL采用了自动化提示调优技术，以优化程序生成的质量。此外，模型的参数设置和损失函数设计也经过精心调整，以确保生成程序的准确性和有效性。

📊 实验亮点

在七个数据集上的实验结果表明，GRAIL在GED预测质量上超越了现有的最先进方法，具体提升幅度达到了XX%（具体数据待补充）。此外，GRAIL在不同图分布上的跨领域泛化能力表现出色，显示了其广泛的适用性。

🎯 应用场景

GRAIL的研究成果在多个领域具有潜在应用价值，包括社交网络分析、生物信息学和图数据库等。通过提高图相似性计算的效率和准确性，GRAIL能够为这些领域提供更强大的数据分析工具，推动相关研究的发展。

📄 摘要（原文）

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.