Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation

Graph pattern cardinality estimation is the problem of estimating the number of embeddings |M| of a query graph in a data graph. This fundamental problem arises, for example, during query planning in subgraph matching algorithms. There are two major approaches to solving the problem: sampling and synopsis. Synopsis (or summary)-based methods are fast and accurate if synopses capture information of graphs well. However, these methods suffer from large errors due to loss of information during summarization and inherent assumptions. Sampling-based methods are unbiased but suffer from large estimation variance due to large sample space.

To address these limitations, we propose Alley, a hybrid method that combines both sampling and synopses. Alley employs 1) a novel sampling strategy, random walk with intersection, which effectively reduces the sample space, 2) branching to further reduce variance, and 3) a novel mining approach that extracts and indexes tangled patterns as synopses which are inherently difficult to estimate by sampling. By using them in the online estimation phase, we can effectively reduce the sample space while still ensuring unbiasedness. We establish that Alley has worst-case optimal runtime and approximation quality guarantees for any given error bound 𝜖 and required confidence 𝜇. In addition to the theoretical aspect of Alley, our extensive experiments show that Alley outperforms the state-of-the-art methods by up to orders of magnitude higher accuracy with similar efficiency.

• corresponding author used in fast approximate query answering when calculating the exact answer takes too long, and approximate results are sufficient for data analytics. An online aggregation method can even progress the estimation towards a more accurate answer [28].

In this paper, we focus on combining two major approachessampling and synopses -to solve the graph pattern cardinality estimation problem. Synopsis-based methods pre-build summary structures in the offline phase and use the structures to perform cardinality estimation in the online phase. Sampling-based methods perform sampling, calculate weights of samples, and aggregate these weights to estimate the cardinality in the online phase.

Synopsis-based methods have been mainly developed for RDF graphs. C-SET [35] summarizes the data graph into a set of starshaped structures, while SumRDF summarizes it into a smaller graph. These methods are fast and accurate if synopses capture information of data graphs well. However, it is a well-known problem that the information loss in summarization and the ad-hoc assumptions (e.g., uniformity and independence) in computing the estimates may produce large errors [27,31,38]. On various real and synthetic datasets, a very recent work by Park et al. [38] shows that these methods actually suffer from serious under-estimation problems due to these limitations.

Sampling-based methods have been mainly developed for relational data, but show good performance on graph data. Park and colleagues further show that, surprisingly, an online aggregation method designed for relational data, WanderJoin, significantly outperforms all techniques designed for graph data [38]. However, sampling-based methods suffer from large sample space that leads to large estimation variance and a high probability of sampling failures (i.e., samples have zero-weights). The failures lead to significant under-estimation in sampling-based methods, including WanderJoin, which we will show in Section 3. Here, the sample space is the set of all possible random walks following a particular sampling strategy and order. The set of candidates for each vertex/edge in order is called the local sample space. We illustrate these problems using an example in Figure 1 and WanderJoin.

WanderJoin for relational data can be translated into an estimator for graph data which performs edge-at-a-time sampling, by regarding query edges as relations and overlapping query vertices as join keys. For example, the query graph in Figure 1a is equivalent to a join graph in Figure 1c. WanderJoin first determines the order of query edges, e.g., ⟨(𝑢 1 , 𝑢 2 ), (𝑢 2 , 𝑢 4 ), (𝑢 1 , 𝑢 4 ), (𝑢 1 , 𝑢 3 ), (𝑢 3 , 𝑢 4 ), (𝑢 4 , 𝑢 5 )⟩. Following the order, it breaks cycles and transforms the query graph into a tree with split vertices, as in Figure 1b. For example, 𝑢 4 is first split into 𝑢 4 and 𝑢 ′ 4 since the first three edges form a cycle and 𝑢 4 is the latest visited. 𝑢 4 is then split into 𝑢 4 and 𝑢 ′′ 4 again due to (𝑢 3 , 𝑢 4 ). The sampling order is defined on the edges