Subgraph Matching: A New Decomposition Based Approach

Download PDF

Abstract

We study the subgraph matching problem, which is to find all subgraph isomorphisms of a given pattern graph Ħ in a data graph ă . Traditional approaches typically use a backtracking search approach or worst-case optimal join, both of which directly operate on Ħ . In this paper, we revisit the tree decomposition based approach. For a complex pattern graph Ħ , we find its optimal tree decomposition Đ based on the fractional hypertree width, where a node in Đ represents a subgraph of Ħ , which is also called a bag, and a node in Ħ may appear in multiple bags in Đ . The tree decomposition based approach initially computes and materializes the matches of subgraphs specified by the bags, then treats these matches as new relations and employs an acyclic join to compute the matches of Ħ itself. However, previous approaches fail to integrate the tree decomposition with effective join attribute orders, and conversely, previous join attribute ordering approaches do not consider the need to share computations in multiple bags. Additionally, the materialization strategies in previous tree decomposition based approaches can lead to high computation costs. In this paper, we propose a new subgraph matching algorithm ASDMatch ( A daptive S hared D ecomposition-based matching). We propose a new dynamic programming approach that finds optimal attribute orders for each bag based on a cost model that incorporates the computation sharing. Furthermore, we introduce a new adaptive materialization strategy to reduce the computation cost. We confirmed that our ASDMatch outperforms state-of-the-art algorithms and can process many challenging queries that previous algorithms can not finish within the time limit.