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：利用LLM生成代码进行图编辑距离计算和节点对齐

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

关键词: 图编辑距离 大型语言模型 代码生成 提示工程 图相似度 跨领域泛化 自进化学习

📋 核心要点

  1. 现有神经图编辑距离计算方法需要大量标注数据，且计算标注数据本身是NP难问题。
  2. GRAIL利用大型语言模型生成计算图编辑距离的程序，而非直接预测，实现可解释性和自进化学习。
  3. 实验表明，GRAIL在预测质量和跨领域泛化能力上均优于现有方法，无需为新数据集重新训练。

📝 摘要（中文）

图编辑距离(GED)是衡量两个图之间相似度的常用指标。计算最优GED是NP难问题，因此涌现了各种神经和非神经启发式方法。虽然神经方法在近似质量上优于非神经方法，但它们面临着重大挑战：(1)需要大量的ground truth数据，而这些数据本身的计算也是NP难的。(2)它们作为黑盒运行，可解释性有限。(3)缺乏跨领域泛化能力，需要为每个新数据集进行昂贵的重新训练。我们通过GRAIL解决了这些限制，引入了该领域的范式转变。GRAIL没有训练神经模型来预测GED，而是采用大型语言模型(LLM)和自动提示调优的新颖组合来生成用于计算GED的程序。这种从预测GED到生成程序的转变带来了各种优势，包括端到端的可解释性和无需ground truth监督的自主自进化学习机制。在七个数据集上的大量实验证实，GRAIL不仅在预测质量上超越了最先进的GED近似方法，而且在不同的图分布中实现了强大的跨领域泛化。

🔬 方法详解

问题定义：论文旨在解决图编辑距离（GED）计算的难题。现有神经方法依赖大量标注数据，而获取这些数据本身是NP难的。此外，这些方法通常是黑盒模型，缺乏可解释性，且泛化能力差，需要为新数据集重新训练。

核心思路：论文的核心思路是利用大型语言模型（LLM）的代码生成能力，将GED计算问题转化为程序生成问题。通过提示工程，引导LLM生成能够计算GED的程序，而非直接预测GED值。这样既避免了对大量标注数据的依赖，又提高了模型的可解释性和泛化能力。

技术框架：GRAIL的技术框架主要包括以下几个阶段：1) 提示构建：设计合适的提示，引导LLM生成GED计算程序。2) 代码生成：利用LLM根据提示生成Python代码。3) 代码执行：执行生成的代码，得到GED的计算结果。4) 自动提示调优：通过某种机制（具体细节未知），自动优化提示，提高生成代码的质量和GED计算的准确性。

关键创新：最重要的技术创新在于将GED计算问题转化为程序生成问题，并利用LLM的代码生成能力解决该问题。与现有神经方法相比，GRAIL无需大量标注数据，具有更好的可解释性和泛化能力。此外，GRAIL还引入了自动提示调优机制，使其能够自主学习和进化。

关键设计：论文的关键设计包括：1) 如何设计有效的提示，引导LLM生成正确的GED计算程序。2) 如何选择合适的LLM，并对其进行微调或提示工程。3) 如何设计自动提示调优机制，使其能够有效地提高生成代码的质量。4) 具体使用的损失函数、网络结构等技术细节未知。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

GRAIL在七个数据集上进行了广泛的实验，结果表明其在GED预测质量上超越了最先进的方法。更重要的是，GRAIL在不同的图分布中实现了强大的跨领域泛化能力，无需为每个新数据集进行重新训练。具体的性能数据和提升幅度在摘要中未明确给出，但强调了其优于现有方法的结论。

🎯 应用场景

GRAIL在生物信息学、社交网络分析、化学信息学等领域具有广泛的应用前景。例如，可以用于比较蛋白质结构、识别相似的社交网络、发现具有相似性质的化合物。该研究的实际价值在于降低了GED计算的成本和难度，提高了其在实际应用中的可行性。未来，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.