We consider the graph similarity computation (GSC) task based on graph edit
distance (GED) estimation. State-of-the-art methods treat GSC as a
learning-based prediction task using Graph Neural Networks (GNNs). To capture
fine-grained interactions between pair-wise graphs, these methods mostly
contain a node-level matching module in the end-to-end learning pipeline, which
causes high computational costs in both the training and inference stages. We
show that the expensive node-to-node matching module is not necessary for GSC,
and high-quality learning can be attained with a simple yet powerful
regularization technique, which we call the Alignment Regularization (AReg). In
the training stage, the AReg term imposes a node-graph correspondence
constraint on the GNN encoder. In the inference stage, the graph-level
representations learned by the GNN encoder are directly used to compute the
similarity score without using AReg again to speed up inference. We further
propose a multi-scale GED discriminator to enhance the expressive ability of
the learned representations. Extensive experiments on real-world datasets
demonstrate the effectiveness, efficiency and transferability of our approach.

本研究讨论了基于图编辑距离（GED）估计的图相似度计算（GSC）任务，提出了一种简单而强大的正则化技术，叫做对齐正则化（AReg），该技术通过在训练阶段为图神经网络（GNN）编码器施加节点 - 图对应约束来提高学习质量，并且在推理阶段，直接使用 GNN 编码器学习的图级表示来计算相似度得分，而无需再次使用 AReg 进行加速，同时还提出了一种多尺度 GED 鉴别器来增强学习表示的表达能力。实验证明了我们的方法的有效性、高效性和可迁移性。

具有对齐正则化的高效图相似性计算

Efficient Graph Similarity Computation with Alignment Regularization

Graph similarity computation is one of the core operations in many
graph-based applications, such as graph similarity search, graph database
analysis, graph clustering, etc. Since computing the exact distance/similarity
between two graphs is typically NP-hard, a series of approximate methods have
been proposed with a trade-off between accuracy and speed. Recently, several
data-driven approaches based on neural networks have been proposed, most of
which model the graph-graph similarity as the inner product of their
graph-level representations, with different techniques proposed for generating
one embedding per graph. However, using one fixed-dimensional embedding per
graph may fail to fully capture graphs in varying sizes and link structures, a
limitation that is especially problematic for the task of graph similarity
computation, where the goal is to find the fine-grained difference between two
graphs. In this paper, we address the problem of graph similarity computation
from another perspective, by directly matching two sets of node embeddings
without the need to use fixed-dimensional vectors to represent whole graphs for
their similarity computation. The model, GraphSim, achieves the
state-of-the-art performance on four real-world graph datasets under six out of
eight settings (here we count a specific dataset and metric combination as one
setting), compared to existing popular methods for approximate Graph Edit
Distance (GED) and Maximum Common Subgraph (MCS) computation.

本文介绍了 GraphSim 模型，该模型从直接匹配两组节点嵌入的角度解决了图相似性计算问题，获得了在四个真实世界图数据集上的最先进性能。