Files and links (1)
CC BY V4.0, Open Access
Journal article
Explainable Neural Subgraph Matching With Learnable Multi-Hop Attention
IEEE access, Vol.12, pp.130474-130492
2024
Abstract
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
- Title
- Explainable Neural Subgraph Matching With Learnable Multi-Hop Attention
- Authors/Creators
- Duc Q. Nguyen - Faculty of Computer Science and Engineering, Ho Chi Minh City University of Technology-VNU-HCM, Ho Chi Minh City, VietnamThanh Toan Nguyen - HUTECH UniversityJun Jo - Griffith UniversityFlorent Poux - University of LiègeShikha Anirban - Murdoch University, School of Information TechnologyTho T. Quan - Ho Chi Minh City University of Technology
- Publication Details
- IEEE access, Vol.12, pp.130474-130492
- Publisher
- IEEE
- Number of pages
- 19
- Grant note
- IZVSZ2.203310 / Vietnam National Foundation for Science and Technology Development (NAFOSTED) (10.13039/100007224) VINIF.2022.ThS.023 / master’s and Ph.D. Scholarship Programme of Vingroup Innovation Foundation (VINIF)
- Identifiers
- 991005707270007891
- Copyright
- © 2024 The Authors.
- Murdoch Affiliation
- School of Information Technology
- Language
- English
- Resource Type
- Journal article
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