Subgraph matching, the task of identifying all subgraphs within a data graph that are isomorphic to a given query graph, is an NP-hard problem requiring substantial computational resources. Traditional serial algorithms using DFS are inefficient for large-scale graphs due to exponential search space growth. Parallel algorithms, while promising, often suffer from load imbalance and high communication costs. To address these challenges, we propose an adaptive branch-level parallel strategy based on DFS. This approach dynamically allocates search tree branches according to thread workload and task progress. Each thread independently expands partial mappings using DFS, while work-stealing and task-splitting ensure balanced load distribution. We also employ advanced pruning techniques to eliminate unnecessary searches. Additionally, we introduce neighborhood-aware multi-node filtering and a two-level dynamic node selection to further optimize performance. Experiments on diverse large-scale graph datasets demonstrate that our algorithm consistently outperforms advanced methods, achieving up to two orders of magnitude faster processing times.

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

GAP: Adaptive DFS Branch-Level Parallel Subgraph Matching

  • Boping Ran,
  • Xinbiao Gan

摘要

Subgraph matching, the task of identifying all subgraphs within a data graph that are isomorphic to a given query graph, is an NP-hard problem requiring substantial computational resources. Traditional serial algorithms using DFS are inefficient for large-scale graphs due to exponential search space growth. Parallel algorithms, while promising, often suffer from load imbalance and high communication costs. To address these challenges, we propose an adaptive branch-level parallel strategy based on DFS. This approach dynamically allocates search tree branches according to thread workload and task progress. Each thread independently expands partial mappings using DFS, while work-stealing and task-splitting ensure balanced load distribution. We also employ advanced pruning techniques to eliminate unnecessary searches. Additionally, we introduce neighborhood-aware multi-node filtering and a two-level dynamic node selection to further optimize performance. Experiments on diverse large-scale graph datasets demonstrate that our algorithm consistently outperforms advanced methods, achieving up to two orders of magnitude faster processing times.