# Graph Partitioning and Graph Neural Network based Hierarchical Graph Matching for Graph Similarity Computation

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 May 2020.

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

- [LEGO-Learn: Label-Efficient Graph Open-Set Learning](https://mlsanity.com/paper/2410.16386/) (2024)
- [More Interpretable Graph Similarity Computation via Maximum Common Subgraph Inference](https://mlsanity.com/paper/2208.04580/) (2022)
- [Graph Synthetic Out-of-Distribution Exposure with Large Language Models](https://mlsanity.com/paper/2504.21198/) (2025)
- [Agglomeration of Polygonal Grids using Graph Neural Networks with applications to Multigrid solvers](https://mlsanity.com/paper/2210.17457/) (2022)
- [Permutation-Invariant Graph Partitioning:How Graph Neural Networks Capture Structural Interactions?](https://mlsanity.com/paper/2312.08671/) (2023)
- [DynaGraph: Interpretable Multi-Label Prediction from EHRs via Dynamic Graph Learning and Contrastive Augmentation](https://mlsanity.com/paper/2503.22257/) (2025)
- [A Systematic Study of Model Extraction Attacks on Graph Foundation Models](https://mlsanity.com/paper/2511.11912/) (2025)
- [Graph Similarity Computation via Interpretable Neural Node Alignment](https://mlsanity.com/paper/2412.12185/) (2024)

## Abstract (arXiv)

Graph similarity computation aims to predict a similarity score between one pair of graphs to facilitate downstream applications, such as finding the most similar chemical compounds similar to a query compound or Fewshot 3D Action Recognition. Recently, some graph similarity computation models based on neural networks have been proposed, which are either based on graph-level interaction or node-level comparison. However, when the number of nodes in the graph increases, it will inevitably bring about reduced representation ability or high computation cost. Motivated by this observation, we propose a graph partitioning and graph neural network-based model, called PSimGNN, to effectively resolve this issue. Specifically, each of the input graphs is partitioned into a set of subgraphs to extract the local structural features directly. Next, a novel graph neural network with an attention mechanism is designed to map each subgraph into an embedding vector. Some of these subgraph pairs are automatically selected for node-level comparison to supplement the subgraph-level embedding with fine-grained information. Finally, coarse-grained interaction information among subgraphs and fine-grained comparison information among nodes in different subgraphs are integrated to predict the final similarity score. Experimental results on graph datasets with different graph sizes demonstrate that PSimGNN outperforms state-of-the-art methods in graph similarity computation tasks using approximate Graph Edit Distance (GED) as the graph similarity metric.