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 鉴别器来增强学习表示的表达能力。实验证明了我们的方法的有效性、高效性和可迁移性。