用大模型生成代码计算图编辑距离，无需标注数据且可跨领域通用
GRAIL: Graph Edit Distance and Node Alignment Using LLM-Generated Code
- 通过大模型生成计算图编辑距离的程序，替代传统神经网络预测
- 在7个数据集上超越现有方法，在不同图分布下表现稳定
- 无需标注数据即可自进化，结果可解释且支持跨领域迁移
图编辑距离（GED）是衡量两图相似性的常用指标。计算最优GED为NP难问题，催生了多种神经与非神经启发式方法。尽管神经方法相比非神经方法提升了近似质量，但仍面临三大挑战：(1) 需要大量真实标签数据，而真实标签本身即为NP难计算；(2) 作为黑箱模型，可解释性差；(3) 缺乏跨领域泛化能力，需针对每个新数据集重新训练。为此，我们提出GRAIL，实现范式转变：不直接训练模型预测GED，而是利用大语言模型（LLM）与自动提示调优生成用于计算GED的程序。该方法从预测转向生成，带来端到端可解释性及无需真实标签监督的自主自演化学习机制。在7个数据集上的大量实验表明，GRAIL不仅在近似质量上超越当前最优方法，还在多种图分布间表现出稳健的跨领域泛化能力。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。