Efficient Graph Similarity Computation with Alignment Regularization

本文探讨了基于图编辑距离（GED）估计的图相似度计算（GSC）任务。现有的最先进方法将GSC视为使用图神经网络（GNN）进行基于学习的预测任务。为了捕捉成对图之间的细粒度交互，这些方法大多包含一个节点级匹配模块，导致在训练和推理阶段都具有高计算成本。我们展示了昂贵的节点对节点匹配模块对于GSC并非必要，可以使用一种简单而强大的正则化技术，我们称之为对齐正则化（AReg）来获得高质量的学习。在训练阶段，AReg项对GNN编码器施加了一个节点-图对应约束。在推理阶段，GNN编码器学习的图级表示直接用于计算相似度分数，无需再次使用AReg以加速推理。我们进一步提出了多尺度GED鉴别器来增强学习表示的表达能力。在真实世界数据集上进行的广泛实验表明了我们方法的有效性，效率和可迁移性。

本文旨在解决基于图编辑距离（GED）估计的图相似性计算（GSC）任务。现有的方法使用图神经网络（GNN）将GSC视为学习预测任务，但大多数方法在端到端学习流程中包含节点级匹配模块，导致训练和推理阶段的计算成本高。

本文提出了一种称为对齐正则化（AReg）的简单而强大的正则化技术，用于在训练阶段对GNN编码器施加节点-图对应约束。在推理阶段，直接使用GNN编码器学习的图级表示来计算相似性得分，而不再使用AReg来加速推理。此外，本文还提出了一种多尺度GED鉴别器来增强所学表示的表达能力。

本文的实验结果表明，AReg技术可以在不使用昂贵的节点到节点匹配模块的情况下实现高质量的学习，从而提高了计算效率。作者在多个真实数据集上进行了广泛的实验，证明了他们的方法的有效性、效率和可迁移性。

在这个领域中，最近的相关研究包括：'Graph Similarity Learning with Adaptive Pooling Networks'，'Deep Graph Similarity Learning with Edge-Label Attention'，'Graph Similarity Learning via Triplet Network with Spatial Constraints'等。