摘要
图编辑距离 (GED) 用于衡量两个给定图之间的(不)相似度,其定义为将一个图转换为另一个图所需的最小成本编辑序列。然而,精确计算 GED 是 NP-Hard 问题,这近年来促使人们设计用于 GED 估计的神经方法。然而,这些方法并没有明确地考虑不同成本的编辑操作。为了解决这个问题,我们提出了 GRAPHEDX,这是一种神经 GED 估计器,它可以处理为四种编辑操作(即边删除、边添加、节点删除和节点添加)指定的通用成本。我们首先将 GED 表示为一个二次分配问题 (QAP),该问题包含这四种成本。然后,我们将每个图表示为一组节点和边嵌入,并使用它们来设计一系列神经集合差异代理。我们将对应于每个操作的 QAP 项替换为它们的代理。计算这种神经集合差异需要对两个图的节点和边进行对齐。我们使用 Gumbel-Sinkhorn 置换生成器来学习这些对齐,并确保节点和边对齐彼此一致。此外,这些对齐不仅考虑节点对之间边是否存在,还考虑边是否不存在。在各种编辑成本设置下,对多个数据集进行的实验表明,在预测误差方面,GRAPHEDX 始终优于最先进的方法和启发式方法。