Accelerating Subgraph Matching Through Advanced Compression and Label Filtering

Efficiently identifying subgraphs that match a given query graph within large-scale graphs has become a critical focus in both academic and industrial research. Subgraph matching, a fundamental problem in graph algorithms, facilitates the effective querying of graph data and is fundamentally based on the subgraph isomorphism problem, which is known to be NP-complete. Among the various stages of subgraph matching, the filtering phase is particularly crucial as it directly affects the overall efficiency of the algorithm. A robust filtering mechanism can rapidly identify candidate nodes that satisfy the query criteria, thereby significantly reducing computational costs in the subsequent stages. The analysis of existing subgraph matching techniques reveals several challenges in the filtering stage: (1) redundant enumeration of equivalent nodes; (2) incomplete filtering due to structural limitations; and (3) excessive redundant validations during the verification phase. To overcome these issues, we propose an adaptive subgraph matching (ASM) framework that integrates efficient compressed graph nodes (CGNs) and a novel label count filter (LCF) algorithm. These innovations enhance the filtering process, resulting in significant improvements in query processing performance. Experimental evaluations demonstrate that our approach achieves substantial gains, outperforming state-of-the-art subgraph search and matching algorithms by several orders of magnitude in query processing time.