Scholarlink

<p>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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(149\times \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>149</mn> <mo>×</mo> </mrow> </math></EquationSource> </InlineEquation>. Additionally, on standard datasets from prior studies, TriFMatch successfully solves all queries within a limited time frame.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

TriFMatch: a flash subgraph matching algorithm with effective filtering techniques

  • 期刊论文

  • 发表日期：

    2025年10月24日

查看全文
  • Jiezhong He,
  • Yixin Chen,
  • Menghan Jia,
  • Zhouyang Liu,
  • Dongsheng Li,
  • Kian-Lee Tan

摘要

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 \) 149 × . Additionally, on standard datasets from prior studies, TriFMatch successfully solves all queries within a limited time frame.