xNeuSM: Explainable Neural Subgraph Matching with Graph Learnable
  Multi-hop Attention Networks
Duc Q. Nguyen Thanh Toan Nguyen Tho quan
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.