Efficient Subgraph Matching via Iterative Candidate Refinement and Vertex Cover-Based Ordering
Heng Xiao · 2024
Subgraph matching is a fundamental problem in graph analysis with wide-ranging applications across various domains. While extensive research has been conducted to develop practical solutions, the well-established filtering-ordering-enumerating framework still faces challenges in real-world scenarios. Even state-of-the-art algorithms demonstrate constrained performance in terms of response time and scalability when applied to complex, large-scale datasets. To address these limitations, we propose two novel techniques: 1) iterative candidate set refinement and 2) matching order with minimum vertex cover prioritization. Through comprehensive experiments conducted on diverse real-world datasets, we demonstrate that our proposed algorithm substantially outperforms existing state-of-the-art methods. The performance improvements are remarkable, with our algorithm achieving speedups of several orders of magnitude in both elapsed time and the number of recursive calls.