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
this https URL

xNeuSM 是一种可解释的神经子图匹配方法，通过引入适应性学习多跳关注网络（GLeMA）来解决图匹配算法在大型图实例上的限制，实现了预测准确率的显著提升并且查询时间至少是精确算法的七倍快。