Algorithmic and Learning-based Approaches to Subgraph Matching and Counting: A Survey

Subgraph matching and subgraph counting are fundamental graph analysis problems that underpin many graph analytics tasks. However, subgraph isomorphism is NP-complete, making both exact and approximate solutions computationally challenging on large, complex, and dynamic graphs. A large body of work ranges from classical backtracking and decomposition-based algorithms to samplingand synopsis-based estimators, learning-based approaches built on graph neural networks, and GPU-accelerated frameworks. This survey provides a unified and structured overview of recent advances in subgraph matching and subgraph counting. We categorise existing methods into two general templates: a Filter-Order-Enumerate (FoE) framework for subgraph matching and a Preprocess-Filter-Feature-Aggregate (PFFA) framework for subgraph counting. Within these templates, we classify algorithmic and learning-based techniques, discuss key design choices such as candidate filtering, query ordering, search-space enumeration, estimator construction, and parallelization, and summarize representative GPU-based accelerators. We conclude by outlining current trends and open problems, and highlighting connections between matching and counting that can guide future research.