EUVIMEDEUVIMED entdecken
Crossref

Fragmented Graph Pattern Matching on Large Graphs

Faming Li, Shengli Qiu, Xiaochun Yang, Bin Wang, Jianzhong Li

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →