让图编辑距离自动学习编辑成本，更准确匹配真实图结构。
GEDAN: Learning the Edit Costs for Graph Edit Distance
- 用神经网络端到端学习图编辑的细粒度成本，不再假设所有操作代价相同。
- 在分子分析等任务中显著提升图匹配准确性，结果可解释性强。
- 适合需要精准图相似性度量的研究者，如化学、生物信息学领域。
图编辑距离（GED）定义为将一个图转化为另一个图所需的最小代价，是衡量图间差异性的广泛采用指标。其主要问题在于计算复杂度为NP难，导致发展出多种近似方法，包括基于神经网络（NN）的方法。然而，多数神经网络方法假设编辑操作具有单位代价，这一限制性且常不现实的简化忽略了拓扑与功能距离在真实数据中的差异。本文提出一种全端到端的图神经网络框架，用于在细粒度层面学习图编辑距离的编辑成本，使拓扑结构与任务特定相似性对齐。该方法结合无监督自组织机制进行GED近似，并引入广义加性模型以灵活学习上下文相关的编辑成本。实验表明，本方法克服了非端到端方法的局限，实现直接可解释的图匹配，揭示复杂图中的有意义结构，并在分子分析等场景中表现出强适用性。
原文摘要 · Abstract (English)
Graph Edit Distance (GED) is defined as the minimum cost transformation of one graph into another and is a widely adopted metric for measuring the dissimilarity between graphs. The major problem of GED is that its computation is NP-hard, which has in turn led to the development of various approximation methods, including approaches based on neural networks (NN). However, most NN methods assume a unit cost for edit operations -- a restrictive and often unrealistic simplification, since topological and functional distances rarely coincide in real-world data. In this paper, we propose a fully end-to-end Graph Neural Network framework for learning the edit costs for GED, at a fine-grained level, aligning topological and task-specific similarity. Our method combines an unsupervised self-organizing mechanism for GED approximation with a Generalized Additive Model that flexibly learns contextualized edit costs. Experiments demonstrate that our approach overcomes the limitations of non-end-to-end methods, yielding directly interpretable graph matchings, uncovering meaningful structures in complex graphs, and showing strong applicability to domains such as molecular analysis.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。