More Interpretable Graph Similarity Computation Via Maximum Common Subgraph Inference

Zixun Lan, Binjie Hong, Ye Ma, Fei Ma

Research output: Contribution to journalArticlepeer-review


Graph similarity measurement is a fundamental task in various graph-related applications. However, recent learning-based approaches lack interpretability as they directly transform interaction information between two graphs into a hidden vector, making it difficult to understand how the similarity score is derived. To address this issue, we propose an end-to-end paradigm for graph similarity learning called Similarity Computation via Maximum Common Subgraph Inference (INFMCS), which is more interpretable. Our key insight is that the similarity score has a strong correlation with the Maximum Common Subgraph (MCS). We implicitly infer the MCS to obtain the normalized MCS size, with only the similarity score being used as supervision information during training. To capture more global information, we stack vanilla transformer encoder layers with graph convolution layers and propose a novel permutation-invariant node Positional Encoding. Our entire model is simple yet effective. Comprehensive experiments demonstrate that INFMCS consistently outperforms state-of-the-art baselines for graph-graph classification and graph-graph regression tasks. Ablation experiments verify the effectiveness of our proposed computation paradigm and other components. Additionally, visualization and statistical analysis of results demonstrate the interpretability of INFMCS.

Original languageEnglish
Pages (from-to)1-12
Number of pages12
JournalIEEE Transactions on Knowledge and Data Engineering
Publication statusAccepted/In press - 2024
Externally publishedYes


  • Convolution
  • Encoding
  • Feature extraction
  • Graph neural network
  • graph similarity learning
  • Task analysis
  • Transformers
  • Transforms
  • Vectors


Dive into the research topics of 'More Interpretable Graph Similarity Computation Via Maximum Common Subgraph Inference'. Together they form a unique fingerprint.

Cite this