# More Interpretable Graph Similarity Computation via Maximum Common Subgraph Inference

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 52 references that are in the map.
- First posted on arXiv 9 Aug 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Effective Approaches to Attention-based Neural Machine Translation](https://mlsanity.com/paper/1508.04025/) (2015)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs](https://mlsanity.com/paper/2103.09430/) (2021)
- [A Structured Self-attentive Sentence Embedding](https://mlsanity.com/paper/1703.03130/) (2017)
- [Graph Matching Networks for Learning the Similarity of Graph Structured Objects](https://mlsanity.com/paper/1904.12787/) (2019)
- [SimGNN: A Neural Network Approach to Fast Graph Similarity Computation](https://mlsanity.com/paper/1808.05689/) (2018)
- [Attention Interpretability Across NLP Tasks](https://mlsanity.com/paper/1909.11218/) (2019)
- [Learning-based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matching](https://mlsanity.com/paper/1809.04440/) (2018)
- [Distance Metric Learning using Graph Convolutional Networks: Application to Functional Brain Networks](https://mlsanity.com/paper/1703.02161/) (2017)
- [Multilevel Graph Matching Networks for Deep Graph Similarity Learning](https://mlsanity.com/paper/2007.04395/) (2020)
- [Interpreting Recurrent and Attention-Based Neural Models: a Case Study on Natural Language Inference](https://mlsanity.com/paper/1808.03894/) (2018)
- [Learning Structured Text Representations](https://mlsanity.com/paper/1705.09207/) (2017)
- [Graph Partitioning and Graph Neural Network based Hierarchical Graph Matching for Graph Similarity Computation](https://mlsanity.com/paper/2005.08008/) (2020)
- [Global-aware Beam Search for Neural Abstractive Summarization](https://mlsanity.com/paper/2009.06891/) (2020)
- [Heterogeneous Graph Matching Networks](https://mlsanity.com/paper/1910.08074/) (2019)

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

- [RCsearcher: Reaction Center Identification in Retrosynthesis via Deep Q-Learning](https://mlsanity.com/paper/2301.12071/) (2023)
- [From GNNs to Trees: Multi-Granular Interpretability for Graph Neural Networks](https://mlsanity.com/paper/2505.00364/) (2025)
- [Neural Graduated Assignment for Maximum Common Edge Subgraphs](https://mlsanity.com/paper/2505.12325/) (2025)
- [Retrosynthesis Prediction via Search in (Hyper) Graph](https://mlsanity.com/paper/2402.06772/) (2024)
- [Neural Network Graph Similarity Computation Based on Graph Fusion](https://mlsanity.com/paper/2502.18291/) (2025)
- [Use neural networks to recognize students' handwritten letters and incorrect symbols](https://mlsanity.com/paper/2309.06221/) (2023)
- [FRAM: Frobenius-Regularized Assignment Matching with Mixed-Precision Computing](https://mlsanity.com/paper/2508.00887/) (2025)
- [Equivariant Neural Primal-Dual Assignment for Maximum Common Edge Subgraphs](https://mlsanity.com/paper/2609.32661/) (2026)

## Abstract (arXiv)

Graph similarity measurement, which computes the distance/similarity between two graphs, arises in various graph-related tasks. Recent learning-based methods lack interpretability, as they directly transform interaction information between two graphs into one hidden vector and then map it to similarity. To cope with this problem, this study proposes a more interpretable end-to-end paradigm for graph similarity learning, named Similarity Computation via Maximum Common Subgraph Inference (INFMCS). Our critical insight into INFMCS is the strong correlation between similarity score and Maximum Common Subgraph (MCS). We implicitly infer MCS to obtain the normalized MCS size, with the supervision information being only the similarity score during training. To capture more global information, we also stack some vanilla transformer encoder layers with graph convolution layers and propose a novel permutation-invariant node Positional Encoding. The entire model is quite simple yet effective. Comprehensive experiments demonstrate that INFMCS consistently outperforms state-of-the-art baselines for graph-graph classification and regression tasks. Ablation experiments verify the effectiveness of the proposed computation paradigm and other components. Also, visualization and statistics of results reveal the interpretability of INFMCS.