# xNeuSM: Explainable Neural Subgraph Matching with Graph Learnable Multi-hop Attention Networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 40 references that are in the map.
- First posted on arXiv 4 Dec 2023.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2010.05788/) (2020)
- [Cross-lingual Knowledge Graph Alignment via Graph Matching Neural Network](https://mlsanity.com/paper/1905.11605/) (2019)
- [Neural Subgraph Matching](https://mlsanity.com/paper/2007.03092/) (2020)
- [Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph Matching](https://mlsanity.com/paper/2301.02780/) (2023)
- [Convolutional Set Matching for Graph Similarity](https://mlsanity.com/paper/1810.10866/) (2018)
- [Efficient Algorithms for Personalized PageRank](https://mlsanity.com/paper/1512.04633/) (2015)

## Abstract (arXiv)

Subgraph matching is a challenging problem with a wide range of applications in database systems, biochemistry, and cognitive science. It involves determining whether a given query graph is present within a larger target graph. Traditional graph-matching algorithms provide precise results but face challenges in large graph instances due to the NP-complete problem, limiting their practical applicability. In contrast, recent neural network-based approximations offer more scalable solutions, but often lack interpretable node correspondences. To address these limitations, this article presents xNeuSM: Explainable Neural Subgraph Matching which introduces Graph Learnable Multi-hop Attention Networks (GLeMA) that adaptively learns the parameters governing the attention factor decay for each node across hops rather than relying on fixed hyperparameters. We provide a theoretical analysis establishing error bounds for GLeMA's approximation of multi-hop attention as a function of the number of hops. Additionally, we prove that learning distinct attention decay factors for each node leads to a correct approximation of multi-hop attention. Empirical evaluation on real-world datasets shows that xNeuSM achieves substantial improvements in prediction accuracy of up to 34% compared to approximate baselines and, notably, at least a seven-fold faster query time than exact algorithms. The source code of our implementation is available at https://github.com/martinakaduc/xNeuSM.