Fragmented Graph Pattern Matching on Large Graphs
IEEE Transactions on Knowledge and Data Engineering · 2026-08 · 38 (8) · 5127-5141
DOI: 10.1109/tkde.2026.3700606 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Knowledge and Data Engineering, 2026-08. Verfasst von Faming Li und 4 weiteren Autor:innen. Die Arbeit nennt 44 Literaturangaben. Gefördert von: National Key Research and Development Program of China, National Natural Science Foundation of China, Fundamental Research Funds for the Central Universities.
Abstract (Originalsprache)
The corpus of knowledge that we have amassed is often fragmented in nature. That is, we only possess a mere fraction of understanding regarding various objects and lack a holistic view of the interconnections between them. Graph, a widely used model to represent data and relationships between data, encompasses significant amounts of fragmented knowledge. In this paper, we study fragmented graph pattern matching ( $\mathsf {FPM}$ FPM for short) on large graphs, a typical problem of fragmented knowledge management. Given several query graphs, $\mathsf {FPM}$ FPM searches for matches whose subgraphs are isomorphic to the given query graphs and these subgraphs are connected in a specified way. $\mathsf {FPM}$ FPM plays a crucial role in detecting financial crime, identifying abnormal behavior and mining latent knowledge. We propose an algorithm $\mathsf {FraMatch}$ FraMatch , which adopts a traversal-based manner to adaptively identify matches for the given query graphs and enumerates the interconnections among these matches. To improve the efficiency of $\mathsf {FraMatch}$ FraMatch , an index, represented as a $k$ k -partite graph, is constructed to help organize the candidate matches. Additionally, several methods, including four filtering strategies, parallel optimization and a dynamic loading strategy, are proposed to further accelerate the algorithm and reduce memory usage. We conducted extensive experiments on 4 real graphs to validate $\mathsf {FraMatch}$ FraMatch . The results demonstrate that $\mathsf {FraMatch}$ FraMatch outperforms its comparisons 2000× in running time and reduces memory usage by 8% on average. A real application on anti-money laundering further verifies the effectiveness of $\mathsf {FPM}$ FPM . To the best of our knowledge, this is the first study on $\mathsf {FPM}$ FPM on large graphs.
Förderung
- National Key Research and Development Program of China
- National Natural Science Foundation of China
- Fundamental Research Funds for the Central Universities
- Liaoning Provincial United Natural Science Foundation
- CCF-ApsaraDB Research Fund
- CCF Alibaba Cloud Yaochi Research Fund
Zitieren
APA
Li, F., Qiu, S., Yang, X., Wang, B., & Li, J. (2026). Fragmented Graph Pattern Matching on Large Graphs. IEEE Transactions on Knowledge and Data Engineering, 38(8), 5127-5141. https://doi.org/10.1109/tkde.2026.3700606
Vancouver
Li F, Qiu S, Yang X, Wang B, Li J. Fragmented Graph Pattern Matching on Large Graphs. IEEE Transactions on Knowledge and Data Engineering. 2026;38(8):5127-5141. doi:10.1109/tkde.2026.3700606
BibTeX
@article{Li2026,
author = {Li, Faming and Qiu, Shengli and Yang, Xiaochun and Wang, Bin and Li, Jianzhong},
title = {Fragmented Graph Pattern Matching on Large Graphs},
journal = {IEEE Transactions on Knowledge and Data Engineering},
year = {2026},
volume = {38},
number = {8},
pages = {5127--5141},
doi = {10.1109/tkde.2026.3700606}
}
EUVIMED