# Efficient Graph Similarity Computation with Alignment Regularization

arXiv: https://arxiv.org/abs/2406.14929 · HTML: https://mlsanity.com/paper/2406.14929/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 41 references that are in the map.
- First posted on arXiv 21 Jun 2024.

## Builds on (most cited first, 9 of 9)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Graph Matching Networks for Learning the Similarity of Graph Structured Objects](https://mlsanity.com/paper/1904.12787/) (2019)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)
- [SimGNN: A Neural Network Approach to Fast Graph Similarity Computation](https://mlsanity.com/paper/1808.05689/) (2018)
- [Learning-based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matching](https://mlsanity.com/paper/1809.04440/) (2018)
- [Multilevel Graph Matching Networks for Deep Graph Similarity Learning](https://mlsanity.com/paper/2007.04395/) (2020)
- [Combinatorial Learning of Graph Edit Distance via Dynamic Embedding](https://mlsanity.com/paper/2011.15039/) (2020)

## Built on by (most cited first, 26 of 26)

- [Partitioning Message Passing for Graph Fraud Detection](https://mlsanity.com/paper/2412.00020/) (2024)
- [Graph Edit Distance with General Costs Using Neural Set Divergence](https://mlsanity.com/paper/2409.17687/) (2024)
- [IE-NeRF: Inpainting Enhanced Neural Radiance Fields in the Wild](https://mlsanity.com/paper/2407.10695/) (2024)
- [Graph Neural Networks for Databases: A Survey](https://mlsanity.com/paper/2502.12908/) (2025)
- [Commute Graph Neural Networks](https://mlsanity.com/paper/2407.01635/) (2024)
- [Towards Unsupervised Training of Matching-based Graph Edit Distance Solver via Preference-aware GAN](https://mlsanity.com/paper/2506.01977/) (2025)
- [Modality-free Graph In-context Alignment](https://mlsanity.com/paper/2603.13434/) (2026)
- [DiffGED: Computing Graph Edit Distance via Diffusion-based Graph Matching](https://mlsanity.com/paper/2503.18245/) (2025)
- [SCENIR: Visual Semantic Clarity through Unsupervised Scene Graph Retrieval](https://mlsanity.com/paper/2505.15867/) (2025)
- [Iteratively Refined Early Interaction Alignment for Subgraph Matching based Graph Retrieval](https://mlsanity.com/paper/2510.22538/) (2025)
- [FuncEvalGMN: Evaluating Functional Correctness of SQL via Graph Matching Network](https://mlsanity.com/paper/2407.14530/) (2024)
- [Rethinking Flexible Graph Similarity Computation: One-step Alignment with Global Guidance](https://mlsanity.com/paper/2504.06533/) (2025)
- [Personalized Subgraph Federated Learning with Differentiable Auxiliary Projections](https://mlsanity.com/paper/2505.23864/) (2025)
- [GEDAN: Learning the Edit Costs for Graph Edit Distance](https://mlsanity.com/paper/2508.03111/) (2025)
- [Graph2Region: Efficient Graph Similarity Learning with Structure and Scale Restoration](https://mlsanity.com/paper/2510.00394/) (2025)
- [Hierarchy-Aware Neural Subgraph Matching with Enhanced Similarity Measure](https://mlsanity.com/paper/2510.00402/) (2025)
- [SPRig: Self-Supervised Pose-Invariant Rigging from Mesh Sequences](https://mlsanity.com/paper/2602.12740/) (2026)
- [Graph Similarity Computation via Interpretable Neural Node Alignment](https://mlsanity.com/paper/2412.12185/) (2024)
- [HeGMN: Heterogeneous Graph Matching Network for Learning Graph Similarity](https://mlsanity.com/paper/2503.08739/) (2025)
- [Contextual Tokenization for Graph Inverted Indices](https://mlsanity.com/paper/2510.22479/) (2025)
- [Charting the Design Space of Neural Graph Representations for Subgraph Matching](https://mlsanity.com/paper/2510.22897/) (2025)
- [GED-Consistent Disentanglement of Aligned and Unaligned Substructures for Graph Similarity Learning](https://mlsanity.com/paper/2511.19837/) (2025)
- [Through the PRISm: Importance-Aware Scene Graphs for Image Retrieval](https://mlsanity.com/paper/2512.18407/) (2025)
- [Towards Metric-Faithful Neural Graph Matching](https://mlsanity.com/paper/2605.06588/) (2026)
- [Alignment-Guided Largest Table Overlap Size Estimation](https://mlsanity.com/paper/2607.03049/) (2026)
- [Revisiting the Generalization of Neural Graph Edit Distance Models](https://mlsanity.com/paper/2610.04644/) (2026)

## Abstract (arXiv)

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.