.png){kind=icon}
.png){kind=icon}
Return
TriFMatch: a flash subgraph matching algorithm with effective filtering techniques
.png){kind=icon}
PRE
AI
DOI：10.1007/s10115-025-02608-x.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Subgraph matching, as a fundamental operation for graph analysis, aims to extract all subgraphs in a data graph that are identical to a query graph. This task is computationally expensive due to its vast search space. However, existing optimizations face limitations, including insufficient branch pruning, low compression ratios, and over-pruning risks. To overcome these limitations, we propose TriFMatch, featuring three optimizations: (1) a novel query compression technique using successor equivalency, which generalizes existing methods based on neighbor equivalency; (2) a failure-driven filter; and (3) a containment-driven filter. These filters leverage dynamically computed candidates to maximize pruning efficiency. We theoretically and experimentally prove the correctness of all our methods. Experimental results reveal that TriFMatch outperforms state-of-the-art method on both large query and data graphs, achieving speedups of up to $$149\times $$ . Additionally, on standard datasets from prior studies, TriFMatch successfully solves all queries within a limited time frame.
Keywords:
Subgraph isomorphism
Subgraph matching
Branch pruning
Large subgraph query
Journal
IF:
3.1
Papers:
517
Citations:
5.2K