# Learning-based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matching

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

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Sep 2018.

## Built on by (most cited first, 30 of 46)

- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Hybrid Relation Guided Set Matching for Few-shot Action Recognition](https://mlsanity.com/paper/2204.13423/) (2022)
- [GREED: A Neural Framework for Learning Graph Distance Functions](https://mlsanity.com/paper/2112.13143/) (2021)
- [Efficient Graph Similarity Computation with Alignment Regularization](https://mlsanity.com/paper/2406.14929/) (2024)
- [Understanding the Uncertainty of LLM Explanations: A Perspective Based on Reasoning Topology](https://mlsanity.com/paper/2502.17026/) (2025)
- [Conditional Graph Information Bottleneck for Molecular Relational Learning](https://mlsanity.com/paper/2305.01520/) (2023)
- [Graph Self-supervised Learning with Accurate Discrepancy Learning](https://mlsanity.com/paper/2202.02989/) (2022)
- [Shift-Robust Molecular Relational Learning with Causal Substructure](https://mlsanity.com/paper/2305.18451/) (2023)
- [Learning to Count Isomorphisms with Graph Neural Networks](https://mlsanity.com/paper/2302.03266/) (2023)
- [HyRSM++: Hybrid Relation Guided Temporal Set Matching for Few-shot Action Recognition](https://mlsanity.com/paper/2301.03330/) (2023)
- [Zero-shot Item-based Recommendation via Multi-task Product Knowledge Graph Pre-Training](https://mlsanity.com/paper/2305.07633/) (2023)
- [Graph Edit Distance with General Costs Using Neural Set Divergence](https://mlsanity.com/paper/2409.17687/) (2024)
- [MATA*: Combining Learnable Node Matching with A* Algorithm for Approximate Graph Edit Distance Computation](https://mlsanity.com/paper/2311.02356/) (2023)
- [More Interpretable Graph Similarity Computation via Maximum Common Subgraph Inference](https://mlsanity.com/paper/2208.04580/) (2022)
- [Maximum Common Subgraph Guided Graph Retrieval: Late and Early Interaction Networks](https://mlsanity.com/paper/2210.11020/) (2022)
- [Graph Neural Networks for Databases: A Survey](https://mlsanity.com/paper/2502.12908/) (2025)
- [A Unified Framework for Combinatorial Optimization Based on Graph Neural Networks](https://mlsanity.com/paper/2406.13125/) (2024)
- [Towards Accurate Subgraph Similarity Computation via Neural Graph Pruning](https://mlsanity.com/paper/2210.10643/) (2022)
- [D2Match: Leveraging Deep Learning and Degeneracy for Subgraph Matching](https://mlsanity.com/paper/2306.06380/) (2023)
- [Towards Unsupervised Training of Matching-based Graph Edit Distance Solver via Preference-aware GAN](https://mlsanity.com/paper/2506.01977/) (2025)
- [Privacy-Preserved Neural Graph Similarity Learning](https://mlsanity.com/paper/2210.11730/) (2022)
- [Rapid and Precise Topological Comparison with Merge Tree Neural Networks](https://mlsanity.com/paper/2404.05879/) (2024)
- [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)
- [ATEX-CF: Attack-Informed Counterfactual Explanations for Graph Neural Networks](https://mlsanity.com/paper/2602.06240/) (2026)
- [Graph Edit Distance Learning via Different Attention](https://mlsanity.com/paper/2308.13871/) (2023)
- [Network Interdiction Goes Neural](https://mlsanity.com/paper/2405.16409/) (2024)
- [FuncEvalGMN: Evaluating Functional Correctness of SQL via Graph Matching Network](https://mlsanity.com/paper/2407.14530/) (2024)

## Abstract (arXiv)

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.