.png){kind=icon}
.png){kind=icon}
Return
Fragmented Graph Pattern Matching on Large Graphs
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2026.3700606.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 (<inline-formula><tex-math notation="LaTeX">$\mathsf {FPM}$</tex-math></inline-formula> for short) on large graphs, a typical problem of fragmented knowledge management. Given several query graphs, <inline-formula><tex-math notation="LaTeX">$\mathsf {FPM}$</tex-math></inline-formula> searches for matches whose subgraphs are isomorphic to the given query graphs and these subgraphs are connected in a specified way. <inline-formula><tex-math notation="LaTeX">$\mathsf {FPM}$</tex-math></inline-formula> plays a crucial role in detecting financial crime, identifying abnormal behavior and mining latent knowledge. We propose an algorithm <inline-formula><tex-math notation="LaTeX">$\mathsf {FraMatch}$</tex-math></inline-formula>, 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 <inline-formula><tex-math notation="LaTeX">$\mathsf {FraMatch}$</tex-math></inline-formula>, an index, represented as a <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-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 <inline-formula><tex-math notation="LaTeX">$\mathsf {FraMatch}$</tex-math></inline-formula>. The results demonstrate that <inline-formula><tex-math notation="LaTeX">$\mathsf {FraMatch}$</tex-math></inline-formula> 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 <inline-formula><tex-math notation="LaTeX">$\mathsf {FPM}$</tex-math></inline-formula>. To the best of our knowledge, this is the first study on <inline-formula><tex-math notation="LaTeX">$\mathsf {FPM}$</tex-math></inline-formula> on large graphs.
Keywords:
Fragmented knowledge
subgraph isomorphism
large graphs
$k$ k -partite graph
Journal
IF:
10.4
Papers:
6.7K
Citations:
3.2W