Efficient Graph Similarity Computation with Alignment Regularization
<|reference_start|>Efficient Graph Similarity Computation with Alignment Regularization: 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.<|reference_end|>
@article{zhuo2024efficient,
    title={Efficient Graph Similarity Computation with Alignment Regularization},
    author={Wei Zhuo, Guang Tan},
    journal={arXiv preprint arXiv:2406.14929},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.14929},
    primaryClass={cs.LG}
}