A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis]

Subgraph matching is a fundamental problem in graph analysis with a wide range of real-world applications. As subgraph matching techniques evolve, the existing mainstream filter-order-enumeration framework falls short in two aspects: (i) this filter-order-enumeration perspective overlooks an emerging line of compiler-based approaches with caching and validation-based orderings. (ii) The recent rise of complex pruning techniques has shifted the focus of core optimizations beyond filtering and enumeration. This paper advocates the need for a comprehensive survey that not only thoroughly discusses the compiler-based approaches (i.e., cache-based methods and their ordering techniques), but also reframes algorithm-level optimizations such that the role of pruning is adequately addressed. This survey revisits 17 representative exploration-based subgraph matching methods-including both algorithm-level techniques and compiler-based ones-and establishes two optimization pillars, i.e., redundancy reduction and order generation, that can inherently summarize all these efforts. This newly established perspective permits us to systematically organize various optimization techniques and analyze how they interact with each other in the same implementation framework. Our contributions are: (i) Cache-, filter-, and prune-based strategies can remove both overlapping and different redundancies, sending our performance up to 1.81× faster than existing state-of-the-art (SOTA) settings, and (ii) heuristic and validation-based orderings, though grounded in fundamentally different design principles, often converge to similar behavior, leading to comparable performance in practice. Finally, (iii) we provide empirical guidance on when and how different strategies are most effective across diverse graph scenarios.