BEE: Towards Redundancy Reduction via Block-Separator Decomposition for Subgraph Matching

Subgraph matching is a fundamental problem in graph analysis, with many algorithms developed to reduce redundancy during backtracking search.However, existing methods for redundancy detection are constrained in their scope, as they primarily target local redundancies (such as sibling nodes within the search tree) and rely on complete-level pruning (which only eliminates subtrees when they are fully identical), limiting their overall effectiveness. To address these limitations, we propose a novel backtracking approach, namely BEE, that minimizes duplicate searches during backtracking through block-s eparator d ecomposition. BEE effectively detects and eliminates redundancies at both the global scope and partial level. We formalize the problem of optimizing the block-separator tree for subgraph matching and prove its NP-hardness. Thus, an efficient greedy method is developed to decompose the query graph into smaller blocks, enabling the detection of finer-grained redundancies.Furthermore, we propose a block reference structure that efficiently reduces repeated searches by retrieving embeddings whenever redundancies are identified.Extensive experimental results demonstrate that BEE significantly outperforms existing state-of-the-art algorithms, achieving speedups of multiple orders of magnitude under the EPS (embeddings per second) metric.