Details
| Originalsprache | Englisch |
|---|---|
| Titel des Sammelwerks | 2023 International Joint Conference on Neural Networks (IJCNN) |
| Herausgeber (Verlag) | Institute of Electrical and Electronics Engineers Inc. |
| ISBN (elektronisch) | 9781665488679 |
| ISBN (Print) | 978-1-6654-8868-6 |
| Publikationsstatus | Veröffentlicht - 2023 |
| Veranstaltung | International Joint Conference on Neural Networks, IJCNN 2023 - Gold Coast, Australien Dauer: 18 Juni 2023 → 23 Juni 2023 |
Publikationsreihe
| Name | Proceedings of the International Joint Conference on Neural Networks |
|---|---|
| Band | 2023-June |
| ISSN (Print) | 2161-4393 |
| ISSN (elektronisch) | 2161-4407 |
Abstract
The goal of subgraph matching is to determine the presence of a particular query pattern within a large collection of data graphs. Despite being a hard problem, subgraph matching is essential in various disciplines, including bioinformatics, text matching, and graph retrieval. Although traditional approaches could provide exact solutions, their computations are known to be NP-complete, leading to an overwhelmingly querying latency. While recent neural-based approaches have been shown to improve the response time, the oversimplified assumption of the first-order network may neglect the generalisability of fully capturing patterns in varying sizes, causing the performance to drop significantly in datasets in various domains. To overcome these limitations, this paper proposes xDualSM, a dual matching neural network model with interleaved diffusion attention. Specifically, we first embed the structural information of graphs into different adjacency matrices, which explicitly capture the intra-graph and cross-graph structures between the query pattern and the target graph. Then, we introduce a dual matching network with interleaved diffusion attention to carefully capture intra-graph and cross-graph information while reducing computational complexity. Empirically, our proposed framework not only boosted the speed of subgraph matching more than 10x compared to the fastest baseline but also achieved significant improvements of 47.64% in Recall and 34.39% in F1-score compared to the state-of-the-art approximation approach on COX2 dataset. In addition, our results are comparable with exact methods.
ASJC Scopus Sachgebiete
- Informatik (insg.)
- Software
- Informatik (insg.)
- Artificial intelligence
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
2023 International Joint Conference on Neural Networks (IJCNN). Institute of Electrical and Electronics Engineers Inc., 2023. (Proceedings of the International Joint Conference on Neural Networks; Band 2023-June).
Publikation: Beitrag in Buch/Bericht/Sammelwerk/Konferenzband › Aufsatz in Konferenzband › Forschung › Peer-Review
}
TY - GEN
T1 - 10X Faster Subgraph Matching
T2 - International Joint Conference on Neural Networks, IJCNN 2023
AU - Nguyen, Quang Duc
AU - Ren, Zhao
AU - Jo, Jun
AU - Nguyen, Quoc Viet Hung
AU - Toan Nguyen, Thanh
AU - Tam Nguyen, Thanh
PY - 2023
Y1 - 2023
N2 - The goal of subgraph matching is to determine the presence of a particular query pattern within a large collection of data graphs. Despite being a hard problem, subgraph matching is essential in various disciplines, including bioinformatics, text matching, and graph retrieval. Although traditional approaches could provide exact solutions, their computations are known to be NP-complete, leading to an overwhelmingly querying latency. While recent neural-based approaches have been shown to improve the response time, the oversimplified assumption of the first-order network may neglect the generalisability of fully capturing patterns in varying sizes, causing the performance to drop significantly in datasets in various domains. To overcome these limitations, this paper proposes xDualSM, a dual matching neural network model with interleaved diffusion attention. Specifically, we first embed the structural information of graphs into different adjacency matrices, which explicitly capture the intra-graph and cross-graph structures between the query pattern and the target graph. Then, we introduce a dual matching network with interleaved diffusion attention to carefully capture intra-graph and cross-graph information while reducing computational complexity. Empirically, our proposed framework not only boosted the speed of subgraph matching more than 10x compared to the fastest baseline but also achieved significant improvements of 47.64% in Recall and 34.39% in F1-score compared to the state-of-the-art approximation approach on COX2 dataset. In addition, our results are comparable with exact methods.
AB - The goal of subgraph matching is to determine the presence of a particular query pattern within a large collection of data graphs. Despite being a hard problem, subgraph matching is essential in various disciplines, including bioinformatics, text matching, and graph retrieval. Although traditional approaches could provide exact solutions, their computations are known to be NP-complete, leading to an overwhelmingly querying latency. While recent neural-based approaches have been shown to improve the response time, the oversimplified assumption of the first-order network may neglect the generalisability of fully capturing patterns in varying sizes, causing the performance to drop significantly in datasets in various domains. To overcome these limitations, this paper proposes xDualSM, a dual matching neural network model with interleaved diffusion attention. Specifically, we first embed the structural information of graphs into different adjacency matrices, which explicitly capture the intra-graph and cross-graph structures between the query pattern and the target graph. Then, we introduce a dual matching network with interleaved diffusion attention to carefully capture intra-graph and cross-graph information while reducing computational complexity. Empirically, our proposed framework not only boosted the speed of subgraph matching more than 10x compared to the fastest baseline but also achieved significant improvements of 47.64% in Recall and 34.39% in F1-score compared to the state-of-the-art approximation approach on COX2 dataset. In addition, our results are comparable with exact methods.
KW - diffusion attention
KW - graph mining
KW - graph neural networks
KW - matching by embedding
KW - subgraph matching
UR - http://www.scopus.com/inward/record.url?scp=85169594176&partnerID=8YFLogxK
U2 - 10.1109/IJCNN54540.2023.10191159
DO - 10.1109/IJCNN54540.2023.10191159
M3 - Conference contribution
AN - SCOPUS:85169594176
SN - 978-1-6654-8868-6
T3 - Proceedings of the International Joint Conference on Neural Networks
BT - 2023 International Joint Conference on Neural Networks (IJCNN)
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 18 June 2023 through 23 June 2023
ER -