Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration

Subgraph matching is a fundamental yet NP-hard problem in graph algorithms. Modern multi-core shared-memory architectures present substantial opportunities to accelerate subgraph matching through parallelism. However, while several parallel subgraph matching algorithms have been proposed, it warrants a systematic empirical study to evaluate: (1) the interaction effect of different parallel strategies, (2) their scalability, (3) underlying performance factors, and (4) the potential for efficiently parallelizing existing sequential algorithms. In this paper, we present a comprehensive study of parallel subgraph matching by analyzing three key components: task splitting, task scheduling, and match enumeration. To investigate their interplay, we evaluate 100 feasible combinations of representative techniques for each component. We further assess scalability across varying thread counts and explore performance variations under diverse query and data graph characteristics.