Efficient Subgraph Matching with Adaptive Filtering and Core-Set Prioritization

Subgraph matching is a fundamental problem in graph analysis. Recently, many algorithms have been developed, often using backtracking search. However, existing subgraph matching algorithms suffer from significant limitations, including prohibitive computational costs for large-scale graphs, inefficient pruning strategies that fail to scale with real-world network complexities, and suboptimal search orders that amplify computational overhead. To address these challenges, we propose an efficient framework with three key innovations: (1) multi-round candidate filtering, iteratively pruning the search space until reduction is less than 1% of the previous set; (2) core-driven dynamic programming, prioritizing core vertices to optimize the matching order and enhance efficiency; and (3) early pruning techniques to eliminate nonpromising branches. Extensive experiments on real-world datasets demonstrate that our approach outperforms state-of-the-art algorithms by one to two orders of magnitude in most cases.