Logo image
Explainable Neural Subgraph Matching With Learnable Multi-Hop Attention
Journal article   Open access   Peer reviewed

Explainable Neural Subgraph Matching With Learnable Multi-Hop Attention

Duc Q. Nguyen, Thanh Toan Nguyen, Jun Jo, Florent Poux, Shikha Anirban and Tho T. Quan
IEEE access, Vol.12, pp.130474-130492
2024
pdf
Published1.91 MBDownloadView
CC BY V4.0 Open Access

Abstract

Adaptation models Explainability Graph neural networks learnable multi-hop attention Multitasking Object recognition Pattern matching Spread spectrum communication subgraph matching
Subgraph matching is a challenging problem with a wide range of applications in drug discovery, social network analysis, 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 nature of the 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 a multi-task learning framework called xNeuSM: Explainable Neural Subgraph Matching, which introduces Graph Learnable Multi-hop Attention Networks (GLeMA) that adaptively learn the parameters governing the attention factor decay for each node across hops rather than relying on fixed hyperparameters. Our framework jointly optimizes both subgraph matching and finding subgraph-isomorphism mappings. 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 F1 score of up to 34% compared to approximate baselines and, notably, at least a seven-fold faster query time than exact algorithms. With these results, xNeuSM can be applied to solve matching problems in various domains spanning from biochemistry to social science.

Details

Metrics

6 File views/ downloads
45 Record Views

InCites Highlights

These are selected metrics from InCites Benchmarking & Analytics tool, related to this output

Collaboration types
Domestic collaboration
International collaboration
Citation topics
4 Electrical Engineering, Electronics & Computer Science
4.48 Knowledge Engineering & Representation
4.48.120 Complex Networks
Web Of Science research areas
Computer Science, Information Systems
Engineering, Electrical & Electronic
Telecommunications
ESI research areas
Engineering
Logo image