# Accurate and Fast Approximate Graph Pattern Mining at Scale

Anna Arpaci-Dusseau, Zixiang Zhou, Xuhao Chen  Massachusetts Institute of
Technology32 Vassar StCambridgeMA02139USA annaad, zpeter<EMAIL_ADDRESS>
###### Abstract.

Approximate graph pattern mining (A-GPM) is an important data analysis tool
for numerous graph-based applications. There exist sampling-based A-GPM
systems to provide automation and generalization over a wide variety of use
cases. Despite improved usability, there are two major obstacles that prevent
existing A-GPM systems being adopted in practice. First, the termination
mechanism that decides when to terminate sampling lacks theoretical backup on
confidence, and performs significantly unstable and thus slow in practice.
Second, they particularly suffer poor performance when dealing with the
“needle-in-the-hay” cases, because a huge number of samples are required to
converge, given the extremely low hit rate of their lazy-pruning strategy and
fixed sampling schemes.

We build ScaleGPM, an accurate and fast A-GPM system that removes the two
obstacles. First, we propose a novel on-the-fly convergence detection
mechanism to achieve stable termination and provide theoretical guarantee on
the confidence, with negligible online overhead. Second, we propose two
techniques to deal with the “needle-in-the-hay” problem, eager-verify and
hybrid sampling. Our eager-verify method drastically improves sampling hit
rate by pruning unpromising candidates as early as possible. Hybrid sampling
further improves performance by automatically choosing the better scheme
between fine-grained and coarse-grained sampling schemes. Experiments show
that our online convergence detection mechanism can precisely detect
convergence, and results in stable and rapid termination with theoretically
guaranteed confidence. We also show the effectiveness of eager-verify in
improving the hit rate, and the scheme-selection mechanism in correctly
choosing the better scheme for various cases. Overall, ScaleGPM achieves an
geomean average of $565\times$ (up to $610169\times$) speedup over the state-
of-the-art A-GPM system, Arya. In particular, ScaleGPM handles billion-scale
graphs in seconds, where existing systems either run out of memory or fail to
complete in hours.

##  1\. Introduction

Graph Pattern Mining (GPM) (Teixeira et al., 2015; Wang et al., 2018; Jamshidi
et al., 2020; Mawhirter and Wu, 2019; Dias et al., 2019; Shi et al., 2020b;
Chen et al., 2021; Xuhao Chen and Arvind, fpdf), which searches for instances
of small patterns (e.g., triangles) in a data graph, is a key building block
in graph-based data mining. Despite its wide adoption in real-world
applications, GPM is hard to scale to large problem size as it is
computationally quite expensive (Xuhao Chen and Arvind, fpdf). Fortunately,
many real-world use cases do not require exact GPM solutions. For instance, to
characterize network structures in biochemistry, ecology and engineering (Milo
et al., 2002), we need only to estimate the pattern (a.k.a motif) frequency
distribution, instead of exactly counting motifs. Therefore we only need
Approximate GPM (A-GPM), which trades accuracy for speed, as long as some
error bound is met in a given application context.

There have been A-GPM systems, e.g., ASAP (Iyer et al., 2018) and Arya (Zhu et
al., 2023), that are built to simplify programming and improve usability. The
system responsibility is two fold. First, they provide generalized sampling
techniques for arbitrary patterns and programming APIs to support a wide
variety of use cases. Second, they provide automated mechanisms to determine
key sampling parameters, e.g., how many samples required to draw for a given
error bound.

However, existing A-GPM systems have two major limitations that prevent them
from being adopted in practice. First, the automated termination mechanism to
determine when it is confident enough to terminate sampling, does not have
strong theoretical backup on confidence, and thus is significantly unstable
and slow in practice (see Section 3.1 for detail). In existing systems,
sampling is terminated when the predicted number of samples $N_{s}$ have been
drawn. They predict $N_{s}$ based on an offline error-latency profiling (ELP)
procedure before launching the sampling. However, the ELP prediction of
$N_{s}$ is dependent on the true count, which is supposed to be estimated on
the $N_{s}$ samples, creating a circular dependency. Therefore, the ELP cannot
theoretically guarantee confidence in bounding the error. Also, the ELP
returns _unstable_ predictions, i.e., huge variances or even failures in
predicting $N_{s}$, which leads to poor performance.

The second limitation is the poor performance when dealing with the extremely
sparse, a.k.a, needle-in-the-hay cases, where only a small number of matches
of the pattern exist in a big graph (see Fig. 2). In this case, neighbor
sampling (NS), the sampling scheme used in ASAP and Arya, fails to hit a match
in most of the samples, leading to a very low sampling hit rate, e.g.,
0.0000017%. This results in slow convergence as a huge number of samples are
required to meet the error bound. In some extreme cases, we observe that Arya
can be even slower than exact GPM solutions.

To address the unstable termination problem, we propose a novel on-the-fly
convergence detection method for NS. Instead of offline predicting the
termination condition before execution, our online method dynamically collects
statistics and predicts errors during the sampling execution, until
convergence. The convergence is detected when the predicted error is below the
user specified error bound. We prove formally in Theorem 1 that the
probability of the true error being smaller than our predicted error is
$1-\delta$, for a given confidence $1-\delta$. This provides us theoretical
guarantee in confidence, which prior systems lack. Meanwhile, our detected
termination points are stable across different runs while the ELP method in
prior systems is highly unstable. Therefore, our online method can
significantly accelerate the execution, because it needs much fewer samples
than prior systems, while causing negligible online overhead as statistics can
be trivially collected.

As for the low hit rate problem in NS, we find that the root cause is the
delayed check on pattern closure in prior systems, which we call lazy-verify.
We then introduce eager-verify that applying pruning at its earliest possible
point to avoid unpromising candidates and thus improve hit rates. We prove
theoretically that eager-verify is unbiased, and show that it drastically
improves the sampling hit rate, which in turn significantly accelerate
convergence. Furthermore, for extremely sparse cases where the fine-grained NS
sampling scheme can not handle, we propose a hybrid sampling method by
adaptively selecting the better sampling scheme, between NS and a coarse-
grained scheme, graph sparsification (GS), for various graphs and patterns.
For scheme selection, we build a cost model for each sampling scheme to
estimate the execution time. With our models, hybrid sampling manages to
always select the cheaper one from NS and GS for a wide variety of test cases.

We then build ScaleGPM, an accurate and fast A-GPM system that incorporates
our proposed mechanisms: online convergence detection, eager-verify and hybrid
sampling. ScaleGPM efficiently leverages parallel hardware and provides
flexible modes to meet various accuracy requirements with confidence. Our
experiments on a multicore CPU show that, with orders-of-magnitude reduction
in required samples and improvement in hit rates, ScaleGPM achieves an average
of $565\times$ (up to $610169\times$) speedup over the state-of-the-art A-GPM
system, Arya. The hybrid method further improves performance by $61\times$ on
extremely hard (i.e. sparse) cases. Particularly, ScaleGPM handles billion-
scale graphs in seconds where previous frameworks either run out of memory or
fail to complete in hours. This paper makes the following contributions:

  * •

We conduct analysis and empirical study on sampling schemes, and identify the
two major limitations and their root causes in existing A-GPM systems.

  * •

We propose a novel on-the-fly convergence detection method for the NS sampling
scheme, which is the first to provide theoretical guarantee on confidence.

  * •

We introduce the eager-verify mechanism to improve hit rate of the NS scheme
and thus achieve faster convergence speed.

  * •

We propose hybrid sampling to further improve performance, by adaptively
selecting a better scheme based on cost models.

  * •

We build ScaleGPM that incorporates the above novel mechanisms, and evaluation
shows that it significantly outperforms the state-of-the-art system, and
efficiently handles huge graphs.

##  2\. Background

###  2.1. Approximate Graph Pattern Mining

Graph Pattern Mining (GPM) finds subgraphs that match given pattern(s)
$\mathcal{P}$ in a given data graph $\mathcal{G}$. There exist explicit GPM
tasks like subgraph counting (SC) and motif counting (MC), and implicit tasks
like frequent subgraph mining (FSM) (Chen et al., 2020). GPM has numerous
applications in AI and big-data (Xuhao Chen and Arvind, fpdf), including
bioinformatics, chemical engineering, fraud detection, social network
analysis, recommender systems, etc.

Exact GPM is solved by enumerating subgraphs in the data graph and searching
for matches. The search space can be defined as a subgraph tree: each node in
the tree is a subgraph of the data graph $\mathcal{G}$. A subgraph $H$ in
level $l$ of the tree have $l$ vertices. The root (level 0) is an empty
subgraph. A parent node $H$ at level $i$ can be extended to a child node
$H^{\prime}$, by adding a vertex/edge in $H$’s neighborhood in $\mathcal{G}$,
i.e., $H^{\prime}=H+\\{v\\}$, $v\in\mathcal{N}(H)$. Each leaf of the tree is a
candidate of match, which is then compared with the pattern $\mathcal{P}$, to
test if it is a match. Pruning schemes, e.g., matching order (Xuhao Chen and
Arvind, fpdf; Jamshidi et al., 2020; Mawhirter and Wu, 2019), symmetry
breaking (Mawhirter et al., 2021; Chen et al., 2020, 2021) and decomposition
(Pinar et al., 2017; Chen and Qian, 2022), are applied to reduce the search
space (i.e., prune the subgraph tree). Nevertheless, this search is extremely
expensive, as the computational complexity increases exponentially in the size
of the pattern.

Many real-world use cases do not require exact GPM solutions. For example,
when we use motif (a.k.a graphlet) distribution as a “signature” (e.g., graph
similarity) for social network analysis or fraud detection, it is quite
sufficient to just provide approximate counts of the motifs. Also in FSM the
users only want to find those frequent patterns whose occurrences are above
some user specified threshold, or simply top-$K$ most frequent patterns, where
estimated counts would be sufficient to give high quality solutions.
Therefore, for all these use cases, we can perform Approximate GPM (A-GPM)
instead to substantially reduce the total amount of computation.

In this paper we focus on sampling based A-GPM approaches. Generally, such an
approach first samples a portion of the graph, searches for match in the
sample, and makes the estimation by scaling the sampled result. This process
can be repeated multiple times to improve the confidence of estimation.
Formally, given $\mathcal{G}$ and $\mathcal{P}$, an A-GPM solver aims to use a
randomized ($\epsilon$, $\delta$)-approximation scheme, which estimates the
number of (non-induced or induced) occurrences of $\mathcal{P}$ in
$\mathcal{G}$ within a factor of ($1\pm\epsilon$), with probability at least
$1-\delta$, where $\epsilon$ and $\delta$ are user defined parameters. There
are a large volume of studies on A-GPM applications, such as triangle counting
(Buriol et al., 2006; Pagh and Tsourakakis, 2012; Tsourakakis et al., 2011,
2009; Pavan et al., 2013; Turk and Turkoglu, 2019; Bera and Seshadhri, 2020;
Chen et al., 2022; Ahmed et al., 2014), clique/cycle counting (Ye et al.,
2022; Shi et al., 2022; Chen et al., 2022), motif counting (Elenberg et al.,
2015; Jha et al., 2015; Slota and Madduri, 2013; Bhuiyan et al., 2012; Bressan
et al., 2018, 2019, 2017; Paramonov et al., 2019; Wang et al., 2014; Zhao et
al., 2010; Alon et al., 2008), butterfly counting (Sanei-Mehri et al., 2018),
frequent subgraph mining (Kuramochi and Karypis, 2004; Preti et al., 2021;
Abdelhamid et al., 2016; Bhatia and Rani, 2018; Purohit et al., 2017). They
all use sampling to reduce computation, though their sampling schemes are
customized for the specific problems. These custom implementations do not
offer system support, like automated termination, generic APIs, or choices in
speed and error trade-off.

###  2.2. Sampling Schemes for GPM Problems

Algorithm 1 Neighbor Sampling

1:for each sampler $i\in$ [1, $N_{s}$] do

2: $C_{i}\leftarrow 0,\alpha\leftarrow m$

3: Sample an edge $e_{1}$ from $\mathcal{E}$, let $E_{1}\leftarrow\\{e_{1}\\}$

4: for $j$ in [2, $k-1$] do

5: Sample a neighboring edge $e_{j}$ from $E_{j-1}$’s neighborhood

6: $E_{j}\leftarrow E_{j-1}\bigcup\\{e_{j}\\}$, $\alpha\leftarrow\alpha\times
c_{j}$ $\triangleright$ $c_{j}$ is the neighborhood size

7: if closing edges for ($E_{k-1}$, $\mathcal{P}$) exist in $\mathcal{G}$ then
$C_{i}\leftarrow\alpha$ $\triangleright$ closure check

8:$C^{\prime}=\sum C_{i}/N_{s}$ is the estimated count

####  2.2.1. Neighbor Sampling (NS)

Algorithm 1 shows how neighbor sampling works. For each sample, it starts with
sampling one edge from $\mathcal{G}$ uniformly at random (3), and then
repetitively samples one more edge from the neighborhood of the currently
sampled edges (5), until the size (number of sampled vertices) is the same as
the pattern. It then does closure check (7), i.e., check in $\mathcal{G}$ the
existence of the closing edges, which form a match of the pattern together
with existing edges. We can draw multiple samples (1) in parallel, and average
them for improved accuracy (8).

For a given match $\hat{M}$ where $\hat{e_{1}}$ is the first edge,
$Pr[\hat{M}]=\frac{1}{m\cdot\prod_{2}^{k-1}c_{j}}$, where
$c_{j}=|\mathcal{N}(H_{j-1})|$, $H_{j-1}$ is the $E_{j-1}$ induced subgraph,
and $\mathcal{N}(H)$ is the neighbor set of $H$. So the count is scaled by
$\alpha=m\cdot\prod_{2}^{k-1}c_{j}$ (6). Apparently $\alpha$ varies in
different samples, meaning matches are not equally likely to be sampled. Thus
$\alpha$ is maintained for each sample and used for normalization.

NS has been widely used in A-GPM applications (Pavan et al., 2013; Bressan,
2021; Paramonov et al., 2019; Turk and Turkoglu, 2019) with customized
optimizations. In NS, each time an arbitrary neighbor is sampled from
$H_{i}$’s neighborhood, which may lead to a high failure rate in the closure
check. Therefore, restrictions are added to make the sampled subgraph more
likely be a match. For example, if $\mathcal{P}$ is a cycle, we can sample a
path (Jha et al., 2015), i.e., restrict the next neighbor to be from the two
endpoints’ neighborhood. For an arbitrary pattern $\mathcal{P}$, we can do
neighbor sampling following $\mathcal{P}$’s spanning tree (Bressan et al.,
2018). Furthermore, automorphism check can be added to avoid redundant
subgraphs (Jiang et al., 2023). More generally, we can sample multiple
neighbors each time, instead of a single neighbor (Jiang et al., 2023).

Algorithm 2 Edge Sparsification

1:Randomly select a subset $E^{\prime}$ of $p\times m$ edges from $E$,
$m=|E|$, $0<p\leq 1$

2:Generate an induced subgraph $G^{\prime}$ = ($V$, $E^{\prime}$)

3:$C^{\prime}$ += ExactCounting($\mathcal{G}^{\prime}$, $\mathcal{P}$)
$\triangleright$ Exact counting on $\mathcal{G}^{\prime}$

4:$C=C^{\prime}\times p^{-l}$ is the estimated count in $\mathcal{G}$
$\triangleright$ $l$ is # of edges in $\mathcal{P}$

####  2.2.2. Subgraph Sampling

The idea of subgraph sampling is to sample a subset of vertices or edges from
$\mathcal{G}$ with some probability $p$, to form a subgraph $G^{\prime}$, and
then do exact search in $G^{\prime}$, and finally scale the count based on
$p$. One popular way to sample a subgraph is to use the graph sparsification
(GS) technique (Benczúr and Karger, 1996; Fung et al., 2011; Spielman and
Teng, 2004; Spielman and Srivastava, 2011; Spielman and Teng, 2011), which
sparsifies $\mathcal{G}$ by randomly removing some edges. Bernoulli Edge
Sparsification (BES) (Tsourakakis et al., 2009) is such an example, as shown
in Algorithm 2. For each edge in $\mathcal{G}$, include it with probability
$p$ (1) to get graph $G^{\prime}$ (2). For each match $M$ of $\mathcal{P}$ in
$\mathcal{G}$, the probability that $M$ exists in $G^{\prime}$ is $p^{l}$,
hence the expected count in $G^{\prime}$ is $C^{\prime}=p^{l}\times C$. BES is
simple and easy to implement, and can be trivially parallelized.

Color Sparsification (Pagh and Tsourakakis, 2012) (CS), another GS approach,
sparsifies $\mathcal{G}$ by first randomly assigning a color from {1, 2,
$\cdots$ , $c$} to each vertex and then only preserving edges whose two
endpoints are in the same color. The probability of choosing an edge is
$p=1/c$, and the probability of choosing a match is $p^{l-1}$. Hence the
expected count in $G^{\prime}$ is $C^{\prime}=p^{l-1}\times C$. Apparently,
the probability of preserving a match of $\mathcal{P}$ is higher than that in
BES. In other words, it could meet the same error bound with more edges
removed, thus less computation. The downside is that different edges are not
independent of each other any more, which means potentially higher variance.
Usually a single sampler is used for sparsification, though more samplers can
be used to improve confidence.

Another way to sample a subgraph is Egonet Sampling (Rossi et al., 2019;
Sanei-Mehri et al., 2018), in which an element (vertex or edge) of
$\mathcal{G}$ is sampled and the egonet, i.e., the local neighborhood, of this
element is extracted as a subgraph. It often requires many samplers.

One advantage of subgraph sampling is that a state-of-the-art exact counting
algorithm can be applied on the sampled subgraph. But the cost is extra time
and space to extract the subgraph(s), and the time complexity is still
exponential in the size of pattern $k$. Subgraph sampling has only been used
in A-GPM applications for specific patterns (Tsourakakis et al., 2009; Pagh
and Tsourakakis, 2012; Tsourakakis et al., 2011; Shi et al., 2020a; Sanei-
Mehri et al., 2018; Shi et al., 2022; Rossi et al., 2019).

###  2.3. Approximate GPM Systems

A-GPM systems, such as ASAP (Iyer et al., 2018) and Arya (Zhu et al., 2023),
have been proposed to simplify A-GPM programming. These systems provide APIs
to the users for them to easily compose various A-GPM applications. As opposed
to those case-by-case customized implementations, an A-GPM system provides a
generalized, sampling-based approximation method, for arbitrary patterns.
Moreover, instead of hand tuning the key sampling parameters, e.g., the number
of samples, in hand-implemented applications, these systems provide the Error-
Latency Profile (ELP) method to automatically choose the values of the
sampling parameters for each specific case, e.g., input data graph and
pattern, to meet the user specified error bound.

Nevertheless, all the prior systems use fixed sampling schemes to make
approximation. For example, ASAP uses the NS scheme, and implements NS in the
edge streaming fashion (Bar-Yossef et al., 2002; Kallaugher et al., 2019;
Aliakbarpour et al., 2018; Assadi et al., 2018; Chen et al., [n. d.]) where
edges are streamed in as a sequence, instead of loaded all at once, to save
memory space. Arya is also based on NS, but adds pattern decomposition on top
of ASAP, to reduce the amount of work in each sample for large, easy-to-
decompose patterns. Since both ASAP and Arya are based on NS, they both suffer
the shortcomings of NS, which are discussed in detail next.

##  3\. Understanding Sampling Tradeoffs

###  3.1. Termination Condition and Confidence

Figure 1. Three different runs (three curves) of Arya’s ELP prediction given
the LiveJ graph and triangle pattern. With an error bound of 10%, the curves
give dramatically different prediction on the number of samples $N_{s}$:
5,260, 26,510 and 121,210. This leads to a 25$\times$ performance difference
in the sampling execution phase.

A major responsibility of an A-GPM system is to decide when the sampling can
be terminated with enough confidence to meet the error bound. Existing A-GPM
systems use error-latency profile (ELP), before the execution of the sampling
procedure, to pre-determine the number of samples $N_{s}$ required. The
execution is then terminated simply when $N_{s}$ samples have been drawn.
However, we observe that the value of $N_{s}$ that ELP predicts vary
dramatically across different runs of ELP. Fig. 1 shows the results of three
runs of ELP. Each curve represents the prediction of one ELP run. We get
predictions of $N_{s}$ as 5,260, 26,510 and 121,210, respectively. This huge
prediction difference leads to a 25$\times$ performance difference in the
sampling execution phase.

More importantly, the ELP method for termination condition adds an indirection
between the error estimation and the confidence. Originally, the required
number of samples $N_{s}$ is derived from the Chernoff bound in ASAP (Iyer et
al., 2018) or Chebyshev’s inequality in Arya (Zhu et al., 2023). For example,
given $\epsilon$ and $\delta$, the lower bound in Arya is
$N_{s}\geq\frac{K\cdot m\cdot\rho}{C\cdot\epsilon^{2}\delta}$, where $K$ is a
constant, $m=|E|$, $\rho$ is a pattern specific constant, and $C$ is the true
count. The problem is, this bound contains the true count $C$, which is the
output that is supposed to be estimated. Therefore, what ELP does is to
essentially first estimate $C$ without theoretical confidence-error
($\delta$-$\epsilon$) guarantees, then feed it into the lower bound to get
$N_{s}$. $N_{s}$ is then used to do sampling and estimate a more accurate $C$.
Note that ELP estimates $C$ by sampling in a sparsified graph and iteratively
updating the parameters and the estimates until convergence. Although the
bound inequation used to calculate $N_{s}$ contains $\delta$, estimating $C$
by ELP has no involvement of $\delta$. It means the estimation of $N_{s}$
loses connection to the confidence. The root cause is the _circular
dependency_ between $C$ and $N_{s}$, i.e., $C$ is used to estimate $N_{s}$,
and $N_{s}$ is used to estimate $C$, which is fundamentally unavoidable in the
ELP based approach.

Due to the _circular dependency_ , ELP provides only a heuristic rather than a
strong theoretical bound. Another limitation of ELP is its own convergence
speed. We observe that in some cases, ELP fails to converge within 10 hours
(see details in Table 2).

Figure 2. Sample hits and misses in Arya, on Twitter40 (top) and Friendster
(bottom) graphs. The pattern is 4-clique for both. In total $10^{8}$ samples
are drawn in both cases. Each green point is a hit sample, while each red
point is a miss sample. For Twitter40, there are 7,033 hits with a hit rate of
$7\times 10^{-5}$. For Friendster, there are only 5 hits with a $5\times
10^{-8}$ hit rate (i.e. needle in the hay).

###  3.2. Characterizing Neighbor Sampling

For the sampling based approximation approach, the estimation difficulty
depends on the density and distribution of the matches of $\mathcal{P}$ in the
graph $\mathcal{G}$. When there are plenty of matches, defined as the dense
case, it is easier to make estimation than the sparse case, where there exist
only a few matches. This is because it is more likely to draw a successful
sample (i.e., find a match) if there are more matches, and the confidence to
meet an error bound depends on seeing enough number of successful samples.
Note that the extremely sparse case is known as finding the needle in the hay.

We call a sample that finds a match a hit, otherwise a miss. Fig. 2 shows how
the hits and misses are distributed in $1\times 10^{8}$ samples drawn by Arya
(Zhu et al., 2023), for the 4-clique pattern on graphs Twitter (top) and
Friendster (bottom). The two graphs have similar sizes but quite different
degree distribution (see maximum degree in Table 1), and thus different hit
rates. There are 7,033 hits in Twitter ($7\times 10^{-5}$ hit rate), while
only 5 hits appeared in Friendster ($5\times 10^{-8}$ hit rate) which is a
typical needle-in-the-hay case. Since the execution time is roughly linear in
$N_{s}$, this difference in hit rates would result in a $\sim$700$\times$
execution time difference in practice, assuming the same average time per
sample.

It is known that NS works poorly in the sparse case, for example, when
$\mathcal{P}$ is dense and $\mathcal{G}$ is sparse, and particularly in the
case of needle in the hay (Zhu et al., 2023). One can expect that in this
case, the closure check fails frequently, which means a large number of
samples $N_{s}$ is required to meet a certain error bound. Moreover, dense
patterns are particularly problematic for Arya (Zhu et al., 2023) which
decomposes the pattern into sub-patterns, as a dense pattern would be split
with many edgecuts, and checking closure is quite expensive. Arya thus suffers
significant slowdown in those cases, and in some extreme cases it is even
slower than the exact solution.

(a) house on fr with 0.1% error

(b) 5path on livej with 2% error

Figure 3. Execution time variance of Neighbor Sampling (NS) and Graph
Sparsification (GS), under the same error bounds.

###  3.3. Coarse-grain vs. Fine-grain Sampling

A key difference between NS and GS is the granularity of each sample. Since
each sample contains at most one match, we classify NS to be a fine-grain
sampling scheme, as opposite to coarse-grain sampling schemes, each of whose
samples can contain multiple matches. For NS, each sample is in the size of
the pattern size $k$, and each sample task is lightweight. But we need a lot
of samples, i.e., $N_{s}\gg 1$, to get a meaningful estimation, since each
sample contains at most one match. In contrast, subgraph sampling schemes,
including GS, are coarse grained. In GS, a sample is a sparsified graph, which
could potentially contain many matches in it. As the sample granularity in GS
is much larger, it performs better than NS when given a sparse case, as it is
more likely to hit matches in a big region of the graph. However, this
advantage comes at the cost of several drawbacks. First, each sample in GS is
a much larger computational task, and the complexity is exponential in the
pattern size. Second, as multiple matches appear in the same sample, GS may
yield worse variance than NS in the worst case.

To summarize, given the distinct characteristics in the input data (graph and
pattern), none of these sampling schemes can always be the best solution. Fig.
3 compares the running time of NS with GS, when given the same error bound. On
the left we mine the house pattern on the Friendster graph with an error bound
of 0.1%, where GS is 6.7$\times$ faster than NS. On the right we mine the
5-path pattern in the Livej graph with an error bound of 2%, where GS is
10$\times$ slower than NS.

##  4\. Proposed Mechanisms

To achieve stable termination with confidence, we propose a novel on-the-fly
convergence detection mechanism in Section 4.1 that is fundamentally different
from the existing ELP approach. To improve hit rate in NS, we introduce eager-
verify and prove it unbiased in Section 4.2. To further improve performance in
handling needle-in-the-hay cases, we propose a hybrid method that adaptively
selects the best-performing sampling scheme. For scheme selection, we
establish cost models (a.k.a. performance models) for the NS (Section 4.3) and
GS (Section 4.4) scheme to estimate their execution time, and select the
faster one. We only focus on the two schemes, but this hybrid method can be
extended to include other schemes in the future.

###  4.1. Online Convergence Detection

Due to the circular dependency issue (Section 3.1), the ELP method breaks the
theoretical guarantee on confidence. Also, it is fundamentally hard for ELP to
establish confidence because it is done before execution, and there is little
information we can leverage. Therefore, we propose an on-the-fly approach to
establish confidence. This is based on our observation in NS sampling
procedures, that the estimation errors tend to converge over time (see Fig.
10). Instead of predetermining the required number of samples offline (i.e.
before execution), we detect online if the estimates have converged, and then
terminate the execution subsequently. However, convergence detection is not
trivial. A straightforward method is to check if the difference of the error
curve is small enough, i.e., within a fixed threshold. But this does not work
because the termination point depends on the user defined confidence and error
bound. The key challenge is then how to decide termination to meet error bound
with confidence.

To address it, we propose to predict the error online periodically with
confidence, and terminate when the predicted error is below the error bound.
To make predictions with confidence, we collect online statistics during
execution, which allows us to formally derive predicted errors based on the
probability theory. Our key insight is that confidence can be established by
the normal distribution of sampled means (formally proved in Theorem 1), as
shown in Fig. 4. Specifically, we keep track of the mean $\mu$ of the
estimated counts and the standard deviation $\sigma$ of the means, and then
use $\mu$, $\sigma$ and $\delta$ to compute a relative error $\hat{\epsilon}$
using Eq. 1, where $\Phi^{-1}$ is inverse of the cumulative distribution
function of the standard normal. Note that $\mu$ is also used as the estimate
of the true count $C$.

(1) $\hat{\epsilon}=\frac{\Phi^{-1}(1-\frac{\delta}{2})\sigma}{\mu}$

When we detect that $\hat{\epsilon}$ is below the user specified error bound
$\epsilon$, according to Theorem 1, we can safely terminate the sampling, and
conclude that $\mu$ is an estimate of $C$, under an error bound $\epsilon$
with a confidence of $1-\delta$. We refer our approach as NS-online.

###### Theorem 1.

Given $\delta$, $n$ samples $X_{1},\dots,X_{n}$ drawn by using the NS sampling
scheme, and the mean of sampled counts $\mu=\frac{1}{n}\sum_{i=1}^{n}X_{i}$,
let $C$ be the true count and $\hat{\epsilon}$ be the estimated error computed
by Eq. 1. As $n\to\infty$, the probability of the true relative error being
smaller than the estimated relative error is
$\text{I\kern-1.49994ptP}\left(\frac{|\mu-C|}{C}<\hat{\epsilon}\right)=1-\delta$.

Figure 4.  The normal distribution of the means of sampled counts (i.e. our
predicted counts) using neighbor sampling (NS). We ran NS to collect $10^{6}$
samples on LiveJ, 4-clique. We obtained a predicted count by taking the mean
of a random subset of 100 of these underlying samples. We simulated 1000 of
these predicted counts. Although the underlying distribution of the sampled
counts (green bars) is not a normal distribution, their means (purple bars),
which are our predicted counts, do follow a normal distribution (dashed red
line).

###### Proof.

Let $D$ be the distribution $X_{1},\dots,X_{n}$ are sampled from. Since the NS
estimator is unbiased, the true count $C$ is the mean of the distribution $D$.
Our estimator of $C$ is $\mu:=\frac{1}{n}\sum_{i=1}^{n}X_{i}$. This estimator
satisfies
$\mathbb{E}[\mu]=\mathbb{E}[\frac{1}{n}\sum_{i=1}^{n}X_{i}]=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}[X_{i}]=\frac{1}{n}\sum_{i=1}^{n}C=C$
and
$\mathbb{V}ar[\mu]=\mathbb{V}ar[\frac{1}{n}\sum_{i=1}^{n}X_{i}]=\frac{1}{n^{2}}\sum_{i=1}^{n}\mathbb{V}ar[X_{i}]=\frac{1}{n}\mathbb{V}ar[X_{1}]$.
Because $\mu$ is the average of $n$ samples from a distribution $D$ (which
clearly has finite mean and variance), the central limit theorem (CLT)
applies, so $\mu$ follows the normal distribution. Formally,
$\frac{\mu-\mathbb{E}[\mu]}{\sqrt{\mathbb{V}ar[\mu]}}$ converges in
distribution to a standard normal as $n\to\infty$.

By the law of large numbers, as $n\to\infty$, the sample variance
$\frac{1}{n}\sum_{i=1}^{n}X_{i}^{2}-\mu^{2}$ converges in probability to
$\mathbb{V}ar[X_{1}]$. Letting
$\sigma^{2}:=\frac{1}{n}\left(\frac{1}{n}\sum_{i=1}^{n}X_{i}^{2}-\mu^{2}\right)$,
this means that
$\frac{\mathbb{V}ar[\mu]}{\sigma^{2}}=\frac{\frac{1}{n}\mathbb{V}ar[X_{1}]}{\frac{1}{n}\left(\frac{1}{n}\sum_{i=1}^{n}X_{i}^{2}-\mu^{2}\right)}=\frac{\mathbb{V}ar[X_{1}]}{\left(\frac{1}{n}\sum_{i=1}^{n}X_{i}^{2}-\mu^{2}\right)}$
converges in probability to $1$. Additionally, $\mu$ converges in probability
to $C$, so $\frac{\mu}{C}$ converges in probability to $1$. Therefore, by
Slutsky’s Theorem,
$\frac{\mu-\mathbb{E}[\mu]}{\sqrt{\mathbb{V}ar[\mu]}}\cdot\sqrt{\frac{\mathbb{V}ar[\mu]}{\sigma^{2}}}\cdot\frac{\mu}{C}=\frac{\mu-C}{C}\cdot\frac{\mu}{\sigma}$
converges in distribution to a standard normal. This means that for any fixed
$x$, we have

$\text{I\kern-1.49994ptP}\left(\frac{\mu-C}{C}\cdot\frac{\mu}{\sigma}<x\right)\to\Phi(x)\text{
as }n\to\infty.$

This implies that

$\text{I\kern-1.49994ptP}\left(\left|\frac{\mu-C}{C}\cdot\frac{\mu}{\sigma}\right|<x\right)\to
2\Phi(x)-1\text{ as }n\to\infty.$

Plugging in $x=\Phi^{-1}(1-\frac{\delta}{2})$, we get

$\text{I\kern-1.49994ptP}\left(\left|\frac{\mu-C}{C}\cdot\frac{\mu}{\sigma}\right|<\Phi^{-1}(1-\frac{\delta}{2})\right)\to
2\Phi\left(\Phi^{-1}(1-\frac{\delta}{2})\right)-1\text{ as }n\to\infty.$

Rearranging terms and simplifying yields

$\text{I\kern-1.49994ptP}\left(\left|\frac{\mu-C}{C}\right|<\frac{\Phi^{-1}(1-\frac{\delta}{2})\sigma}{\mu}\right)\to
2\left(1-\frac{\delta}{2}\right)-1\text{ as }n\to\infty$
$\implies\text{I\kern-1.49994ptP}\left(\left|\frac{\mu-C}{C}\right|<\hat{\epsilon}\right)\to
1-\delta\text{ as }n\to\infty.$

∎

Algorithm 3 NS-online convergence detection

1:sum $\leftarrow 0$, squaredSum $\leftarrow 0$, $n=0$, $W\leftarrow N_{min}$

2:while $\hat{\epsilon}$ ¿ $\epsilon$ do

3: for each sampler $i\in$ [1, $W$] do $\triangleright$ $W$ is the window size

4: $X_{i}\leftarrow\textsc{DrawASample}()$ $\triangleright$ $X_{i}$ is the
$i$-th sampled count

5: sum $\leftarrow$ sum $+X_{i}$ $\triangleright$ $\sum_{i=1}^{n}X_{i}$

6: squaredSum $\leftarrow$ squaredSum $+X_{i}*X_{i}$ $\triangleright$
$\sum_{i=1}^{n}X_{i}^{2}$

7: $n\leftarrow n+1$

8: $\mu\leftarrow$ sum / $n$ $\triangleright$ mean of sampled counts

9: var $\leftarrow$ squaredSum / $n-\mu*\mu$ $\triangleright$ variance of
sampled counts

10: $\sigma\leftarrow$ sqrt(var/$n$) $\triangleright$ standard deviation

11: $\hat{\epsilon}\leftarrow\Phi^{-1}(1-\frac{\delta}{2})*\sigma/\mu$
$\triangleright$ predicted error

Algorithm 3 shows the NS-online algorithm. Each time we draw a sample (4), the
only information we need to keep track of is the accumulated sum
$\sum_{i=1}^{n}X_{i}$ (5) and the accumulated squared sum
$\sum_{i=1}^{n}X_{i}^{2}$ (6). At the end of each interval (i.e. $W$ samples
in 3), we compute the standard deviation $\sigma$ (10) and predict the error
$\hat{\epsilon}$ (11). If $\hat{\epsilon}$ is below the user’s error bound
(2), sampling is then terminated and it reports the estimated count $\mu$.

###  4.2. Eager Verify for Neighbor Sampling

A major drawback of NS in prior systems is the low hit rate in dealing with
sparse cases. By looking at individual samples, we find that most of these
samples fail to pass the closure check (7 in Algorithm 1). Therefore we looked
deeper into the failures (i.e. missed samples). Our key observation is that
many of the failures have been unpromising candidates even at the early stage
of the sampling. For example, if we search for 6-cliques, and the first four
vertices in the sample does not form a 4-clique, this sample is impossible to
form a 6-clique. Therefore, in general, the low hit rate in ASAP and Arya is
because the closure check is delayed to the very last step, which we refer to
as lazy-verify. Based on this understanding, we propose a eager-verify
approach to improve NS performance. The key idea is to sample from promising
candidates by verifying the pattern’s connectivity constraints as early as
possible. This strategy has two advantages. First, since unpromising
candidates are pruned at early stage, and we only sample from promising
candidates, each sample is more likely to succeed, i.e., hit a match. Second,
if a sample starts from an edge whose neighborhood contains no or very few
matches (unlikely to hit), eager-verify can minimize the work as this sample
would fail at its early stage, while lazy-verify will have to proceed until
the end and fail.

The challenge in implementing eager-verify is how to avoid unpromising
candidates but still retain unbiasedness in sampling. Based on the subgraph
tree abstraction (Section 2.1), our key finding is that each leaf in the tree
corresponds to a unique path. As long as the pruning does not change this one-
to-one mapping, we can prove that the sampler is unbiased. We find that two
typical pruning techniques, symmetry breaking (Mawhirter et al., 2021) and
matching order (Xuhao Chen and Arvind, fpdf), meet this requirement. There
exist other pruning schemes in the literature (Chen and Qian, 2022; Mhedhbi
and Salihoglu, 2019), which could be applied as well, but we leave this as a
future work. We refer NS used in ASAP as NS-base, and NS with the two pruning
techniques as NS-prune. We first give an example to show how pruning avoids
unpromising candidates, and then prove NS-prune an unbiased estimator in Lemma
2. Algorithm 4 shows the pseudo-code for finding 4-cycle using NS-prune. In 6
we compute a set intersection $N(v_{0})$ & $N(v_{2})$ which is the candidate
set of the third vertex $v_{3}$, because $v_{3}$ is a common neighbor of
$v_{0}$ and $v_{2}$ in the 4-cycle pattern. In contrast, in NS-base, because
both $v_{0}$’s and $v_{2}$’s neighbors are possible candidates, $v_{3}$ is
sampled from set union $N(v_{0})\cup N(v_{2})$, and in the final step it
checks closure between $v_{3}$ and $v_{2}$ if $v_{3}$ is from $v_{0}$’s
neighborhood, otherwise it checks closure between $v_{3}$ with $v_{0}$. If the
closure check fails, it is a miss. However, in NS-prune the closure check is
unnecessary because $v_{3}$ is guaranteed to be connected to $v_{0}$ and
$v_{2}$, and thus much more likely to hit a match.

Algorithm 4 NS-prune for 4-cycle

1:for each sampler $i\in$ [1, $N_{s}$] do

2: $e(v_{0},v_{1})\leftarrow$ sample($\mathcal{E}$) , $\alpha\leftarrow 0$
$\triangleright$ sample an edge $(v_{0},v_{1})$

3: $A\leftarrow$ $N(v_{1})$ \- {$v_{0}$, $v_{1}$}, bound by $v_{0}$
$\triangleright$ set difference

4: if —A— = 0 then break

5: $v_{2}\leftarrow$ sample($A$) $\triangleright$ sample node $v_{2}$ from set
$A$

6: $B\leftarrow$ $N(v_{0})$ & $N(v_{2})$, bound by $v_{1}$ $\triangleright$
set intersection

7: if —B— = 0 then break

8: $v_{3}\leftarrow$ sample($B$) $\triangleright$ sample node $v_{3}$ from set
$B$

9: $X_{i}\leftarrow m*|A|*|B|$ $\triangleright$ sampled count

###### Lemma 2.

NS-prune is an unbiased estimator.

###### Proof.

Let $(v_{0},\dots,v_{k-1})$ be the vertices of an occurrence, i.e., a match,
of the pattern $\mathcal{P}$ in the matching order (e.g. for 4-cycle,
$(v_{0},v_{1}),(v_{1},v_{2}),(v_{2},v_{3}),(v_{3},v_{0})\in E$). Each match
corresponds to a unique $k$-tuple $(v_{0},\dots,v_{k-1})$, e.g., for 4-cycle,
we enforce $v_{0}=\max(v_{0},v_{1},v_{2},v_{3})$ and $v_{3}<v_{1}$. During the
execution of NS-prune, the probability that $v_{0}$ and $v_{1}$ are chosen is
$1/m$ (see 2 in Algorithm 4), as all edges are equally likely. The probability
that $v_{2}$ is chosen (see 5) is $1/|A|$ as $v_{2}\in A$. In general, the
probability that $v_{i}$ is chosen is $1/|S_{i}|$, where $S_{i}$ is the
candidate set that $v_{i}$ is drawn from. Therefore the probability that this
particular match is sampled by NS-prune is the product of these probabilities
(e.g. $1/(m\cdot|A|\cdot|B|)$ for 4-cycle). The scaling factor $\alpha$ is the
inverse of this probability, so the expected contribution of this match to the
estimated count for one sampler is $\frac{1}{\alpha}\cdot\alpha=1$. Let $C$ be
the true count of $\mathcal{P}$ in $\mathcal{G}$, and let
$X_{ij}=\alpha=(m\cdot|S_{2}|\cdots|S_{k-1}|)$ if the $i$th sample hits the
$j$th match of $\mathcal{P}$, otherwise $X_{ij}=0$, where $1\leq i\leq
N_{s},1\leq j\leq C$. The estimated count is
$\mathbb{E}\left(\frac{1}{N_{s}}\sum_{i,j}X_{ij}\right)=\frac{1}{N_{s}}\left(\sum_{i,j}\mathbb{E}(X_{ij})\right)=\frac{1}{N_{s}}\sum_{i,j}1=C$.
Therefore NS-prune is an unbiased estimator. ∎

Figure 5. Comparing the hit rate of NS-prune with NS-base, with the 4-clique
pattern on various graphs.

Note that the scaling factor in NS-prune tends to be much smaller than that in
NS-base, because it involves the sizes of intersection instead of union sets.
This results in lower variances and more stable and faster convergence, as we
will show in Section 6.

###  4.3. Cost Model for Neighbor Sampling

In NS, the total work is $\sum_{i=1}^{N_{s}}W_{i}$, where $W_{i}$ is the work
of the $i$-th sample $s_{i}$. Given that $N_{s}\gg 1$ in the NS scheme, it is
reasonable to assume that the NS execution time is linear in the number of
samples $N_{s}$. So we can predict the execution time as
$t_{tot}=t_{avg}*N_{s}=c*W_{avg}*N_{s}$, where $W_{avg}$ is the average work
per sample, and $c$ is a hardware specific constant factor to translate work
to time. We estimate $N_{s}$ by profiling Section 5.3. As this is only used
for performance prediction, it does not affect error and confidence. To
estimate $c$, a simple profiler can be run on each hardware machine to
determine this constant scale factor. This profiling overhead is negligible,
as it can be determined by running only once per machine or once per graph on
only a small number of points.

The challenge, however, is to estimate $W_{avg}$ for the given $\mathcal{G}$
and $\mathcal{P}$, as $W_{i}$ varies for different samples. In fact $W_{i}$
depends on the local neighborhood structure of $s_{i}$. More specifically, the
task of each sample is a sequence of set operations and sample operations, for
example, see Algorithm 4. Given a specific pattern $\mathcal{P}$, this
sequence of operations is fixed, but each set operation in the sequence may
take different (worse-case) time depending on the cardinality of the input
sets, which overall depends on the structure of $\mathcal{G}$. So it is
difficult to get an accurate estimation of $W_{avg}$, i.e., the slope the
linear relationship, without really running NS.

At each break point (e.g., LABEL:algo:ns-base:line:breakA in
LABEL:algo:ns-4cycle), we must consider the possibility of an early-exit from
the sampling procedure. Each break point is triggered based on the probability
of being empty based on the candidate set size. However, it can be hard to
predict this probability in practice, as certain graphs have many dense
clustered areas, when sampled in few breakpoints occur, whereas others
frequently terminate early. To address this, we model the performance as a
performance cone (see example in Fig. 13) consisting of two slopes instead of
one, where the performance is upper bounded by none of the breakpoints
triggering (completing the full work of the sampling procedure) and lower
bounded by the first break point.

###  4.4. Cost Model for Graph Sparsification

Figure 6. The execution time for 6clique-Friendster using Color Sparsification
under different numbers of colors. Each point is one run. Red region is the
stabilization window.

GS running time contains two parts, one is the preprocessing time to generate
the sparsified graph $G^{\prime}$, the other is the time spent on exact search
in the sparsified graph $G^{\prime}$.

Preprocessing involves looping over every edge in order to remove edges.
Therefore, the total work is $|E|\cdot(w_{1}+p\times w_{2})$, where $p$ is the
probability that an edge is kept, $w_{1}$ is the work on every edge, $w_{2}$
is the work on kept edges. In our implementation $w_{1}$ is one read
operation, $w_{2}$ is one write operation.

For exact search in $G^{\prime}$, our estimation is again based on set
operations. But instead of a sequence of operations in NS, the work in GS
consists of nested loops, each of which corresponds to one vertex in the
pattern and iterates over the candidates of that vertex. The candidate vertex
set is computed by set operations. If we describe a GPM algorithm as a
sequence of nested for loops $M=(X_{1},\dots,X_{n})$, which refine the
candidate set to a possible match. Each nested loop can be described as
$X_{j}=(o_{j},i_{j})$. Where $o_{i}$ is the number of operations performed in
the inner body of that loop to refine the candidate set. $i_{j}$ is the number
of iterations for the $j$th loop. $i_{j}=|Z_{i}|$, the size of the candidate
set at the $j$th level. $o_{i}$ is the work of the operations to generate the
candidate set $|Z_{i+1}|$. Then the total work can be described as
$\prod_{j}^{i_{j}}o_{j}=\prod_{j}^{|Z_{j}|}o_{j}$. To estimate $i_{j}$ and
$o_{j}$, we need to estimate the cardinality of each candidate set $Z$.

If $Z=A-B$, i.e., set difference, $|Z|$ is bounded by $|A|$, which can be
simply estimated as the average degree, $|V|/|E|$. If $Z=A\cap B$, i.e., set
intersection, $|Z|$ is bounded by $\min(|A|,|B|)$. To get a better bound, we
can use the method in GraphPi (Shi et al., 2020b) and estimate $|Z|$ as
$|V|\cdot p_{1}\cdot p_{2}^{n-1}$, where $p_{1}=\frac{2\cdot|E|}{|V|^{2}}$,
$p_{2}=\frac{T\cdot|V|}{2\cdot|E|^{2}}$ and $T$ is the triangle count in
$\mathcal{G}$. Intuitively, $p_{1}$ is the probability of any pair of vertices
being neighbors. $p_{2}$ is the probability of any pair of vertices in a
neighborhood being directly connected to each other. To use this estimation
for GS, we need to make the following adjustments. Note that in a sparsified
graph $G^{\prime}$, $|V^{\prime}|=|V|$ and $|E^{\prime}|=|E|\times p$, and we
have $T^{\prime}$ = $T\times p^{2}$ as discussed in Section 2.2.2. Then if
$Z=A-B$, $|Z|$ is estimated as $\frac{|V|}{|E|\cdot p}$. If $Z=A\cap B$, $|Z|$
is estimated as $|V|\cdot p_{1}\cdot p_{2}^{n-1}$, where
$p_{1}=\frac{2\cdot|E|\cdot
p}{|V|^{2}},p_{2}=\frac{T\cdot|V|}{2\cdot|E|^{2}\cdot p^{4}}$.

##  5\. System Design and Implementation

We give an overview of the ScaleGPM system in Section 5.1, describe details of
the GS engine in Section 5.2 and our proposed profiling mechanism in Section
5.3, and other implementation details in Section 5.4.

Figure 7. ScaleGPM system overview. The three red boxes are our proposed novel
techniques: online convergence detection, early pruning and hybrid sampling.
NS: neighbor sampling. GS: graph sparsification. The system execution flow is
① fast profiler estimates input parameters (e.g., #colors, #samples), ② cost
models predict performance and select from NS and GS sampling schemes, and ③
the selected (NS or GS) engine is invoked to conduct sampling.

###  5.1. System Overview and Interface

Fig. 7 illustrates the major components in our system. ScaleGPM is composed of
a fast profiler, two cost models and two execution engines for NS and and GS
respectively. The cost models have been described in Section 4.3 and Section
4.4 respectively. The NS engine is enhanced with our novel convergence
detection mechanism (Section 4.1) and is significantly improved by our proven
unbiased optimizations (Section 4.2). Our GS engine is the first generalized
color sparsification for arbitrary patterns, as all prior GS-based work are
customized for specific patterns, e.g., triangle. To generalize the GS
approach for an arbitrary pattern $\mathcal{P}$, we need to (1) generate a
pattern specific exact search program, (2) determine the scaling factor for
$\mathcal{P}$ and (3) determine the values of its key parameter, i.e., the
sparsify probability $p$ or the number of colors $c$ ($c=\frac{1}{p}$). For
(1) we can leverage the state-of-art compiler based approach (Mawhirter et
al., 2021). For (2) we explain in Section 5.2. For (3) our fast profiler in
Section 5.3 determines it.

To meet various accuracy requirements in applications, ScaleGPM provides two
modes for the user to choose, strict mode (default) and loose mode. The strict
mode uses only the NS engine with online convergence detection to guarantee
high confidence. In this mode the fast profiling and cost models are bypassed.
The loose mode, however, employs our proposed hybrid approach. It uses the
fast profiler and cost models to determine if the GS or NS engine is used.
When comparing the predicted performance of NS and GS, ScaleGPM uses a
thresholding mechanism to check if the predicted performance of GS overlaps
with the performance cone of NS, i.e., it is either entirely above or entirely
below the cone. If not, ScaleGPM chooses the faster one and activates the
corresponding engine. Otherwise, the two schemes should perform similarly
well, hence ScaleGPM chooses NS to guarantee high confidence.

###  5.2. Tradeoff in the GS Engine

For simplicity, we discuss edge sparsification, while color sparsification is
similar. The estimated count is $\hat{C}=Y\cdot p^{-l}$, where the random
variable $Y$ denotes the number of matches in the sampled graph $G^{\prime}$,
which is sparsified from $\mathcal{G}$ with probability $p$. For each match
$M$ in $\mathcal{G}$, the probability that $M$ exists in $G^{\prime}$ is
$p^{l}$, hence the expected number of matches in $G^{\prime}$ is
$\mathop{\mathbb{E}}[Y]=p^{l}C$, i.e., $\mathop{\mathbb{E}}[Y\cdot p^{-l}]=C$,
so we have $\mathop{\mathbb{E}}[\hat{C}]=C$. Although the edges are sampled
independently, the matches are not. Consider an edge $e$ shared between two
matches $M_{i}$ and $M_{j}$ of $\mathcal{P}$. When $e$ gets removed during
sparsification, necessarily both $M_{i}$ and $M_{j}$ will not be counted. So
the Chernoff bounds do not apply directly for GS. We can use Chebyshev’s
bounds instead. $\mathop{\mathbb{V}ar}[\hat{C}]$
$=C\cdot(p^{-l}-1)+\mathop{\mathbb{C}ov}$, where $\mathop{\mathbb{C}ov}=$
$\sum_{z=2}^{k-1}t_{z}\cdot(p^{1-z}-1)$ and $t_{z}$ is the number of pairs of
matches that share $z$ vertices. The variance depends on both the number of
matches $C$ in $\mathcal{G}$ and the number of pairs of matches that share one
or more edges.

Apparently, the key knob to tune accuracy is $p$. As we increase $p$, the
variance decreases and accuracy increases. Since GS speed is insensitive to
the number of colors $c=\frac{1}{p}$ within a wide stabilization window (Fig.
6), we can pick a large $p$ to achieve better accuracy. Note that the variance
increases exponentially in the pattern size $k$. This means larger patterns
are more difficult to estimate accurately, and so we may need a larger $p$, to
guarantee the same error bound.

###  5.3. Fast Profiling for Cost Models

To predict performance in our cost models, we need the number of samples
$N_{s}$ for NS and the number of colors $c$ for GS. Our fast profiler is used
to quickly determine the values of these parameters. Note that $N_{s}$ here is
only used in the NS cost model, not used for NS sampling (as our NS-online
does not need to predict $N_{s}$). The profiler first generates a sparsified
graph $G^{\prime}$, e.g., 10% of the original graph. Then, it runs our NS-
online engine with an internal error bound (50%) and confidence (99%). By
detecting convergence, we can determine
$N_{s}=\frac{{N_{o}}\cdot\hat{\epsilon}\cdot{\mu}\cdot\rho(P,G)}{\overline{S}\cdot\epsilon^{2}\cdot\rho(P,G^{\prime})}$,
where $N_{o}$ is the number of samples NS-online converged with, $\mu$ is the
count returned by NS-online, $\overline{S}$ is the scaled count from
$G^{\prime}$ to $G$ (see 2.2.2), $\hat{\epsilon}$ is the final predicted error
by NS-online, $\rho(P,G)$ is the probability of sampling pattern $P$ in $G$,
which is used in prior systems (Iyer et al., 2018; Zhu et al., 2023), and
determined by properties of $G$, e.g., $\Delta$ and $|E|$.

###  5.4. Parallel Implementation Details

Our NS and GS engines are both parallelized. In GS, because sparsification
creates non-overlapping subgraph partitions, each partition can be searched
independently. Within each partition, we further parallelize it over each
vertex in the subgraph, which provides enough parallelism. In NS, as each
sample is an independent task, it can be embarrassingly parallelized across
samples. Note that our NS-online requires a barrier synchronization at the end
of each interval $W$ (3 in Algorithm 3). If $W$ is too small, we have limited
parallelism and too much synchronization overhead. But if $W$ is too large, we
may end up with drawing more samples than necessary. Thus, we want $W$ to be
large enough to maximize parallelism and minimize synchronization overhead,
and small enough to minimize redundant work. We set $W$ to be a fixed percent
of the estimate of $N_{s}$ returned from the fast profiler (e.g. 10% of
$N_{s}$).

##  6\. Evaluation

Graph | Source | —V— | —E— | Avg deg. | Max deg.
---|---|---|---|---|---
lj | liveJournal (Leskovec, 2013) | 4.8M | 43M | 17.7 | 20,333
tw | twitter40 (Kwak et al., 2010) | 42M | 2.4B | 57.7 | 2,997,487
fr | friendster (Yang and Leskovec, 2012) | 66M | 3.6B | 55.1 | 5,214
uk | uk2007 (Boldi et al., 2008) | 106M | 6.6B | 62.4 | 975,419
gsh | gsh-2015 (Boldi and Vigna, 2004) | 988M | 51B | 52.0 | 58,860,305
cw | clueweb12 (Boldi and Vigna, 2004) | 978M | 75B | 76.4 | 75,611,696
|  |  |  |  |

Table 1. Data graphs (symmetric, no loops or duplicate edges). Maximum degrees
are smaller when orientation is applied for cliques.

We implement ScaleGPM in C++ and OpenMP for parallelization. We use ScaleGPM-
NS, ScaleGPM-GS, ScaleGPM-HY to represent the NS, GS, and hybrid mode of our
system respectively. In this evaluation we focus on comparing with prior A-GPM
systems that provide both generalization and automation (see Section 7 for
discussion on non-systematic solutions). We compare ScaleGPM with the state-
of-the-art A-GPM system, Arya (Zhu et al., 2023), and exact GPM system,
GraphZero (Mawhirter et al., 2021). We do not include ASAP since Arya always
outperforms ASAP. We test on a 3.0 GHz, 48-core (2-sockets, 24 cores per
socket) Intel CPU without hyperthreading, with up to 1TB of memory. Table 1
shows the graphs used in our experiments, which are representative real-world
graphs with varying sizes and topology characteristics. In ScaleGPM, graphs
are represented in the Compressed Sparse Row (CSR) format. We evaluate two
types of GPM tasks: subgraph counting (edge-induced) and motif counting
(vertex-induced). For subgraph counting, we test on patterns including
$k$-cliques, 5-path, house, and dumbbell. We do not include even larger non-
clique patterns, because we can not verify the errors as their exact counts
are unknown for most of the graphs. In all the experiments, we time out at 10
hours. We then conservatively use 10 hours for the timed-out cases when
calculating speedups.

We first compare the overall performance of ScaleGPM with state-of-the-art
systems in Section 6.1. We show how our convergence detection performs in
Section 6.2, and the accuracy the NS and GS cost models in Section 6.3. We
discuss system efficiency in Section 6.4.

###  6.1. Sampling Performance vs. State-of-the-Art

We compare sampling performance with Arya and GraphZero. For the hybrid mode
we discuss its profiling time in Section 6.4. For ScaleGPM-GS, we do include
the preprocessing time spent on sparsifying the data graph. We use an error
bound of 10% and confidence of 99%, which is the common practice in ASAP and
Arya.

Pattern | 3-clique (triangle) | 4-clique | 6-clique
---|---|---|---
Graph | Lj | Tw | Fr | Lj | Tw | Fr | Lj | Tw | Fr
| time (sec) | 0.001 | 0.046 | 0.026 | 0.003 | 0.068 | 0.090 | 0.059 | 0.707 | 1.132
ScaleGPM-NS | hit rate | 18% | 55% | 53% | 7.3% | 46% | 31% | 6.4% | 46% | 16%
| # samples | 1e4 | 2e4 | 1e4 | 8e4 | 2e5 | 5e4 | 2.1e6 | 4.1e6 | 7.7e7
| time (sec) | 0.014 | 1.193 | 0.017 | 94.2 | 9656.9 | 2057.7 | TO | TO | TO
Arya | hit rate | 10.6% | 3.9% | 2.9% | 3.2e-3% | 2.7e-3% | 1.7e-6% | – | – | –
| # samples | 4.3e4 | 6.3e4 | 4.6e4 | 3.3e8 | 2.6e8 | 5.1e9 | $\times$ | $\times$ | $\times$
GraphZero | time (sec) | 0.434 | 58.0 | 83.0 | 2.1 | 4004.5 | 73.1 | 2502.5 | TO | 160.4
|  |  |  |  |  |  |  |  |  |

Table 2. $k$-clique performance (10% error). TO: timed out. Arya uses ELP.
$\times$: ELP does not converge. Fastest time in bold.

Table 2 compares the $k$-clique ($k$=3,4,6) running time of ScaleGPM with Arya
and GraphZero. Overall cliques, ScaleGPM achieves a geomean average speedup of
$2747\times$ (up to $610169\times$) against Arya, and $4045\times$ over (up to
$65525\times$) GraphZero respectively. In general, the speedup of ScaleGPM-NS
over Arya comes from two parts. First, our online convergence detection gives
stable and precise termination condition (demonstrated later in Fig. 8 and
Fig. 9), while ELP in Arya could suggest very conservative termination
conditions that do way more samples than necessary (see Fig. 11). Second, our
NS-prune approach dramatically improves the hit rate over NS-base and thus the
total number of samples is reduced. This is evidenced in Fig. 5 and further
confirmed in Fig. 10. The significant speedups over Arya are expected because
(1) Arya is based on pattern decomposition and cliques are hard to decompose,
(2) cliques are more likely to fall in the needle-in-the-hay cases which Arya
handles poorly. The speedups are further evidenced by the hit rate and number
of samples $N_{s}$ used. In particular, for 4-clique, Arya requires 3 to 5
orders of magnitude more samples, while its hit rates are extremely low, e.g.,
1.7$\times 10^{-6}$% for Fr. Notably, Arya is 28$\times$ slower than GraphZero
for the sparse case 4-clique on Fr. Moreover, Arya’s ELP can not converge
within 10 hours for the even more sparse case, 6-clique on Fr, emphasizing the
limitation of ELP. For triangle on Fr, ScaleGPM-NS is slightly slower than
Arya due to synchronization overhead.

Pattern | 5-path | 5-house | 6-dumbbell
---|---|---|---
Graph | Lj | Tw | Fr | Lj | Tw | Fr | Lj | Tw | Fr
| time (sec) | 0.004 | 0.91 | 0.10 | 0.008 | 944.6* | 0.159 | 0.017 | 159.3 | 0.331
ScaleGPM-NS | hit rate | 29% | 99% | 90% | 43% | 43% | 15% | 16% | 43% | 32%
| # samples | 3e4 | 1e4 | 2e4 | 5e4 | 1.9e7 | 3.3e5 | 1.5e5 | 1.6e7 | 6.9e5
| time (sec) | 4.422 | 13.78 | 77.93 | 395.6 | 1297.4 | TO | 346.2 | 4644.4 | TO
Arya | hit rate | 0.04% | 5.8e-03% | 1.7% | 2.6e-3% | 0.02% | – | 0.04% | 2.2e-3% | –
| # samples | 1.1e7 | 1.4e7 | 3.4e5 | 1.5e9 | 6.8e7 | $\times$ | 2.1e8 | 1.1e9 | $\times$
GraphZero | time (sec) | 262.1 | TO | TO | TO | TO | TO | TO | TO | TO
|  |  |  |  |  |  |  |  |  |

Table 3. Non-clique pattern performance (10% error). TO: timed out. $\times$:
ELP does not converge. * GS is selected by our hybrid method.

Table 3 compares performance on large, non-clique patterns, including 5-path,
5-house and 6-dumbbell. Note that it is well known that for exact GPM solvers
(e.g. GraphZero) it is much more expensive to search for these patterns than
cliques, as they are sparser and their sizes are beyond 4. We observe that
GraphZero is timed out for most of the cases, which shows that it is critical
to use approximation for large (sparse) patterns. Arya enjoys fairly good
speedups over GraphZero. This is because, compared to cliques, these patterns
are easier to decompose, which is the case that favors Arya. However, for Fr,
Arya still suffers extremely high $N_{s}$ and low hit rate, and hence runs
more than 10 hours for 5-house and 6-dumbbell. In all these cases, ScaleGPM
significantly improves hit rates and reduces $N_{s}$, which lead to fast
convergence speed. Across these patterns, ScaleGPM achieves an geomean average
of $599\times$ and $27641\times$ speedup against Arya and GraphZero
respectively. Note that for Tw on house, as shown in Table 5(a), ScaleGPM-HY
selects the GS engine in this case, since GS is predicted to be faster, based
on our prediction on the number of samples and time per sample.

Pattern | 3-motif | 4-motif
---|---|---
Graph | Lj | Tw | Fr | Lj | Tw | Fr
ScaleGPM-NS | 0.004 | 0.5 | 0.14 | 0.06 | 82.7 | 0.2
Arya | 0.020 | 1.9 | 0.08 | 231.63 | 13180.2 | 6157.9
GraphZero | 1.283 | 16316.2 | 242.62 | 1927.27 | TO | TO
|  |  |  |  |  |

(a) Performance on Motif Counting.

Pattern | triangle | 4-clique |  5-path*
---|---|---|---
Graph | uk | gsh | cw | uk | gsh | cw | uk | gsh | cw
ScaleGPM-NS | 0.09 | 0.28 | 0.19 | 0.11 | 0.88 | 1.09 | 0.1 | 11.2 | 156.0
Arya | 0.2 | 0.7 | OoM | 175.5 | $\times$ | OoM | 4.2 | $\times$ | OoM
GraphZero | 73.3 | 153.6 | 198.2 | TO | TO | TO | TO | TO | TO
|  |  |  |  |  |  |  |  |

(b) Performance on huge graphs.

Table 4. Running time (sec) (10% error). TO: timed out. $\times$: ELP does not
converge. * the true count is unknown, so accuracy is not verified.

Table 4(a) reports the motif counting performance. Note that in motif
counting, we look for vertex-induced subgraphs, unlike cases in Table 3 which
search for edge-induced subgraphs. The key difference in computation is that
we need both set intersection and set difference to find vertex-induced
subgraphs, but only set intersection is needed for edge-induced subgraphs.
Despite more computation needed, ScaleGPM is still significantly faster than
Arya. Across motifs, ScaleGPM achieves a geomean speedup of $125\times$
speedup against Arya, and $10563\times$ speedup over GraphZero.

Table 4(b) compares performance on huge graphs, i.e., uk2007 (uk) gsh-2015
(gsh) and clueweb12 (cw). Note that Arya mostly runs out of memory for cw
because (1) it has to maintain the set union results (for each of the parallel
threads) in memory, and (2) its internal representation of the graph stream is
implemented in COO-like format, which is less compact than CSR. ScaleGPM
achieves a geomean average $130\times$ compared to Arya and a $7245\times$
speedup compared to GraphZero.

Table 5(a) shows the cases where ScaleGPM-HY selects the GS mode. Notably, for
Fr and $k=9$ (sparse graph and big dense pattern) which is a needle-in-the-hay
case for NS, ScaleGPM successfully choose to use GS instead of NS. This switch
from NS to GS brings us a $61\times$ performance improvement. Over all the
cases where the GS engine is selected, the GS engine leads to a geomean
average $13\times$ speedup over the NS engine.

Pattern | 8-clique | 9-clique | 5-house
---|---|---|---
Graph | lj | fr | lj | fr | tw
ScaleGPM\- NS | 3.0 | 1663.6 | 17.4 | 8358.0 | 944.6
ScaleGPM\- GS | 0.7 | 43.4 | 2.1 | 134.9 | 200.1
|  |  |  |  |

(a) running time (sec) of NS and GS

Pattern-Graph | house – Lj | 4-clique – Tw
---|---|---
Error bound | 10% | 5% | 2% | 1% | 10% | 5% | 2% | 1%
ScaleGPM-NS | 0.008 | 0.053 | 0.3 | 1.1 | 0.07 | 0.13 | 0.69 | 2.68
Arya | 395.6 | 1639.6 | 9873.8 | TO | 9656.8 | TO | TO | TO
|  |  |  |  |  |  |  |

(b) running time (sec) under error bounds from 10% to 1%

Table 5. (a) Comparing NS and GS performance when ScaleGPM-HY selects GS; (b)
performance changes when varying error bounds.

Table 5(b) shows Arya and ScaleGPM running time with varied error bounds. We
observe that the performance gap between Arya and ScaleGPM remains huge
(ranging from 31 to 49 thousand times) as we decrease the error bound.

Overall, we achieve $565\times$ speedup over Arya, and four orders of
magnitude speedup over GraphZero.

###  6.2. Effectiveness of Convergence Detection

Figure 8. Comparing ScaleGPM-NS’s estimated errors (black curves) with actual
errors (red and blue curves). We do two runs of 4-clique counting on two
graphs Fr and Tw.

Fig. 8 compares the error predicted by ScaleGPM-NS with the actual error
throughout the sampling procedure, to show the effectiveness of ScaleGPM-NS’s
online convergence detection. We illustrate two cases here, but we have
verified the same trend for all our test cases in the evaluation. In Fig. 8 we
observe that for both cases, the predicted error curves strictly bound the
actual error, which verifies the high confidence that our method achieves. In
addition to our theoretical proof in Section 4.1, this empirical study further
demonstrates that our method provides strong guarantee on confidence, which is
critical in applications where users want to have strict accuracy requirement.

Figure 9. Predicted errors in our convergence detection mechanism across three
different runs (4-clique on Lj) are extremely stable.

Fig. 9 shows the stability of the error estimation method in ScaleGPM-NS. We
do three repeated runs on the 4-clique pattern and Lj graph. In contrast to
the unstable predictions (Fig. 1) given by ELP in prior systems, our estimated
errors are almost the same across three independent runs. Moreover, our online
mechanism never fails, while ELP suffers convergence issue that may lead to
endless preprocessing (e.g., for 6-clique in Table 2). We observe the same
trend in stability on other graphs and patterns. This experiment further
demonstrates that our method is highly reliable and can be adopted in
practice.

Figure 10. Comparison between the convergence rate of NS-prune and NS-base.
The same formula (with two standard deviations of confidence) was used to
generate the error estimate curves.

Fig. 10 compares the convergence rate of NS-prune and NS-base, both under our
online detection framework. We observe that our proposed early-pruning
mechanism employed in NS-prune result in roughly an order of magnitude lower
error for the same number of samples. Therefore, with pruning, our system can
converge much faster that ASAP and Arya, which is the other major reason why
ScaleGPM achieves much better performance.

Fig. 11 shows the reduction on the number of samples $N_{s}$, by incrementally
applying online convergence detection (orange) and eager-verify (green),
against ELP in Arya (blue). Note that in Table 2 and Table 3 we report $N_{s}$
only for NS-online-prune, but here we breakdown the contributions of online
detection and pruning. We observe that our online method reduces $N_{s}$
sharply over Arya. Applying pruning in eager-verify further reduces $N_{s}$ by
a significant amount. Together, we can meet the same error bound with much few
samples, and more importantly, with confidence.

Figure 11. The reduction on the number of samples.

###  6.3. Prediction Accuracy of Cost Models

Fig. 12 shows the effectiveness of our cost model in predicting the running
time of the GS engine in ScaleGPM. As we increase the number of colors
$c=\frac{1}{p}$ used in GS, the total work is exponentially decreased. Thus,
the GS execution time rapidly becomes dominated by the preprocessing time
spent on sparsifying the graph. For 4clique and house on Lj and Fr, we see
that the cost model precisely captures the exponential trend, as well as the
stabilization window of the GS engine that we discussed in Fig. 6. Note that
when $c$ is extremely small, e.g., $c<5$, it is hard to accurately model the
performance due to the steep slope in that curve. However, in this case (which
is a needle-in-the-hay case) we would favor the use of NS or even exact
counting, as GS with a small $c$ won’t be much faster than exact counting.

Figure 12. The quality of performance prediction for ScaleGPM’s GS Engine. The
red lines are our predictions, while blue dots are actual time.  Figure 13.
The quality of performance prediction for ScaleGPM’s NS Engine. The red lines
are our predictions, while blue dots are actual time.

Fig. 13 shows the effectiveness of our NS cost model. We see that our proposed
performance cone correctly captures the running time of the NS engine at
varying numbers of samples. Note that for Fr, a relatively sparse graph, the
execution time approaches the bottom of the performance cone as expected. We
find in practice, that GS and NS are often predicted to have very distinct
performance, so the width of the cone is not an obstacle in making the correct
choice. The fluctuation in the sparse case 4clique-Fr is also expected, as
sample hits are less frequent and thus more randomness is involved.

###  6.4. System Efficiency

Figure 14. End-to-end time breakdown of ScaleGPM.

Timing Breakdown. Fig. 14 shows the breakdown of the execution time spent on
different components of ScaleGPM. We consider the profiling time, the GS
preprocessing time, and the sampling time (either exact counting in GS or
drawing samples in NS). We see that profiling remains a low percentage of the
overall runtime. As for the sampling time, Lj-8clique requires less time using
the GS engine, while Fr-dumbbell is processed faster using the NS engine,
which aligns with our cost model prediction and thus ScaleGPM-HY makes the
correct thresholding decision.

Figure 15. ScaleGPM speedup scaling over single-thread.

Scalability. Fig. 15 shows how the performance of GS engine and NS engine in
ScaleGPM (error bound of 10%) scales in response to the increase of parallel
cores (i.e., the number of threads). We evaluate the NS engine on 5path-Lj
which is a case that favors the use of the NS engine (i.e., NS is faster than
GS). GS is evaluated on 8clique-Fr as 8-clique is a dense pattern and is rare
in Fr, preferably executed in GS. In both cases, we observe strong scaling
that the execution time of both engines increases linearly as we range the
number of cores from 1 to 48.

##  7\. Related Work

There exist many sampling methods other than neighbor sampling and graph
sparsification. We discuss some of the typical methods in the following. We do
not compare with them in Section 6 because they do not provide either
generalization or automated termination (with confidence). However, they can
potentially be used to replace the GS engine in ScaleGPM. We leave it as a
future work.

Color Coding. It first colors each vertex in $\mathcal{G}$ using a color
randomly chosen from {1,2,$\dots$,$c$} ($c\geq k$), and then counts colorful
matches, i.e., every vertex in the matched subgraph has a unique color. The
requirement of distinct colors allows for heavy pruning: the number of
colorful matches $Z$ can be naturally determined by a dynamic programming
based counting routine (Slota and Madduri, 2013). Color-coding is originally
for finding paths or cycles (Alon et al., 1994, 1995), and is then adapted for
motif counting (Zhao et al., 2010; Alon et al., 2008; Hüffner et al., 2008).
There also exist many parallel and distributed implementations (Slota and
Madduri, 2013, 2015; Chakaravarthy et al., 2016; Zhao et al., 2012). In
addition, the colorful matches can be further sampled (Bressan et al., 2019,
2017, 2018), instead of exactly counted, to reduce computation. Like GS,
color-coding is also a coarse-grain scheme, which can be included in ScaleGPM.

Loop Perforation. SampleMine (Jiang et al., 2023) proposed to perforate the
nested for loops in GPM programs, with a certain probability $p_{i}$ for the
$i$-th loop. The count is then scaled based on the $p_{i}$. SampleMine can be
thought of as a generalization of the vanilla NS scheme, as it collectively
samples multiple candidates, instead of a single one, at a time. Although it
has larger sampling granularity than the vanilla NS, its granularity is still
limited by the egonet of a vertex or edge, similar to Egonet Sampling (Rossi
et al., 2019). More importantly, SampleMine does not provide a systematic way
for sampling termination, which is instead hand-tuned by executing the
sampling procedure multiple times and manually observing convergence (i.e.
small variance).

Other Schemes and Approaches. Monte Carlo Markov Chain (MCMC) (Bhuiyan et al.,
2012; Bera and Seshadhri, 2020; Chen et al., 2016; Wang et al., 2014) defines
a random walk over the set of subgraphs until it reaches stationarity. MCMC
has been used for motif counting. However, it has been shown that MCMC can be
extremely inefficient as the random walk may take a huge amount of steps to
reach stationarity (Bressan et al., 2018, 2017, 2019).

##  8\. Conclusion

Approximate graph pattern mining (A-GPM) systems can be the backbone to
support numerous real-world data analytics applications. The key obstacles
that prevent A-GPM systems from being adopted in practice is a) the lack of
stable, confident termination mechanism and b) poor performance and
scalability when dealing with the “hard” cases. We present ScaleGPM, an
accurate, high performance and scalable A-GPM systems. ScaleGPM involves two
key innovations that remove the obstacles. First, we propose a novel online
convergence detection mechanism, which can provide theoretical guarantee on
prediction confidence and also yield stable termination condition. Second, we
introduce pruning techniques into sampling to improve its success rate, and
propose a hybrid method to adaptively select the best-performing sampling
scheme from two complementary schemes, based on our proposed cost models. The
resulting system, ScaleGPM, achieves an average of $565\times$ speedup over
the state-of-the-art A-GPM systems, and manages to rapidly mine billion-scale
graphs.

## References

  * (1)
  * Abdelhamid et al. (2016) Ehab Abdelhamid, Ibrahim Abdelaziz, Panos Kalnis, Zuhair Khayyat, and Fuad Jamour. 2016.  Scalemine: Scalable Parallel Frequent Subgraph Mining in a Single Large Graph. In _Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis_ (Salt Lake City, Utah) _(SC ’16)_. IEEE Press, Piscataway, NJ, USA, Article 61, 12 pages.  http://dl.acm.org/citation.cfm?id=3014904.3014986
  * Ahmed et al. (2014) Nesreen K. Ahmed, Nick Duffield, Jennifer Neville, and Ramana Kompella. 2014.  Graph Sample and Hold: A Framework for Big-Graph Analytics. In _Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ (New York, New York, USA) _(KDD ’14)_. Association for Computing Machinery, New York, NY, USA, 1446–1455.  https://doi.org/10.1145/2623330.2623757
  * Aliakbarpour et al. (2018) Maryam Aliakbarpour, Amartya Shankha Biswas, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, and Anak Yodpinyanee. 2018.  Sublinear-Time Algorithms for Counting Star Subgraphs via Edge Sampling.  _Algorithmica_ 80, 2 (feb 2018), 668–697.  https://doi.org/10.1007/s00453-017-0287-3
  * Alon et al. (2008) Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, and S Cenk Sahinalp. 2008\.  Biomolecular network motif counting and discovery by color coding.  _Bioinformatics_ 24, 13 (2008), i241–i249.
  * Alon et al. (1994) Noga Alon, Raphy Yuster, and Uri Zwick. 1994.  Color-coding: A New Method for Finding Simple Paths, Cycles and Other Small Subgraphs Within Large Graphs. In _Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing_ (Montreal, Quebec, Canada) _(STOC ’94)_. ACM, New York, NY, USA, 326–335.  https://doi.org/10.1145/195058.195179
  * Alon et al. (1995) Noga Alon, Raphael Yuster, and Uri Zwick. 1995.  Color-Coding.  _J. ACM_ 42, 4 (jul 1995), 844–856.  https://doi.org/10.1145/210332.210337
  * Assadi et al. (2018) Sepehr Assadi, Mikhail Kapralov, and Sanjeev Khanna. 2018\.  A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling. In _Information Technology Convergence and Services_.
  * Bar-Yossef et al. (2002) Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. 2002\.  Reductions in Streaming Algorithms, with an Application to Counting Triangles in Graphs. In _Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms_ (San Francisco, California) _(SODA ’02)_. Society for Industrial and Applied Mathematics, USA, 623–632.
  * Benczúr and Karger (1996) András A. Benczúr and David R. Karger. 1996.  Approximating S-t Minimum Cuts in Õ(N2) Time. In _Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing_ (Philadelphia, Pennsylvania, USA) _(STOC ’96)_. Association for Computing Machinery, New York, NY, USA, 47–55.  https://doi.org/10.1145/237814.237827
  * Bera and Seshadhri (2020) Suman K. Bera and C. Seshadhri. 2020.  How to Count Triangles, without Seeing the Whole Graph. In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_ (Virtual Event, CA, USA) _(KDD ’20)_. Association for Computing Machinery, New York, NY, USA, 306–316.  https://doi.org/10.1145/3394486.3403073
  * Bhatia and Rani (2018) Vandana Bhatia and Rinkle Rani. 2018.  Ap-FSM: A parallel algorithm for approximate frequent subgraph mining using Pregel.  _Expert Systems with Applications_ 106 (2018), 217–232.  https://doi.org/10.1016/j.eswa.2018.04.010
  * Bhuiyan et al. (2012) Mansurul A. Bhuiyan, Mahmudur Rahman, Mahmuda Rahman, and Mohammad Al Hasan. 2012.  GUISE: Uniform Sampling of Graphlets for Large Graph Analysis. In _2012 IEEE 12th International Conference on Data Mining_. 91–100.  https://doi.org/10.1109/ICDM.2012.87
  * Boldi et al. (2008) Paolo Boldi, Massimo Santini, and Sebastiano Vigna. 2008\.  A Large Time-Aware Graph.  _SIGIR Forum_ 42, 2 (2008), 33–38.
  * Boldi and Vigna (2004) Paolo Boldi and Sebastiano Vigna. 2004.  The WebGraph Framework I: Compression Techniques. In _Proceedings of the 13th International Conference on World Wide Web_ (New York, NY, USA) _(WWW ’04)_. ACM, New York, NY, USA, 595–602.  https://doi.org/10.1145/988672.988752
  * Bressan (2021) Marco Bressan. 2021\.  Efficient and Near-Optimal Algorithms for Sampling Connected Subgraphs. In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ (Virtual, Italy) _(STOC 2021)_. Association for Computing Machinery, New York, NY, USA, 1132–1143.  https://doi.org/10.1145/3406325.3451042
  * Bressan et al. (2017) Marco Bressan, Flavio Chierichetti, Ravi Kumar, Stefano Leucci, and Alessandro Panconesi. 2017\.  Counting Graphlets: Space vs Time. In _Proceedings of the Tenth ACM International Conference on Web Search and Data Mining_ (Cambridge, United Kingdom) _(WSDM ’17)_. ACM, New York, NY, USA, 557–566.  https://doi.org/10.1145/3018661.3018732
  * Bressan et al. (2018) Marco Bressan, Flavio Chierichetti, Ravi Kumar, Stefano Leucci, and Alessandro Panconesi. 2018\.  Motif Counting Beyond Five Nodes.  _ACM Trans. Knowl. Discov. Data_ 12, 4, Article 48 (April 2018), 25 pages.  https://doi.org/10.1145/3186586
  * Bressan et al. (2019) Marco Bressan, Stefano Leucci, and Alessandro Panconesi. 2019\.  Motivo: Fast Motif Counting via Succinct Color Coding and Adaptive Sampling.  _Proc. VLDB Endow._ 12, 11 (July 2019), 1651–1663.  https://doi.org/10.14778/3342263.3342640
  * Buriol et al. (2006) Luciana S. Buriol, Gereon Frahling, Stefano Leonardi, Alberto Marchetti-Spaccamela, and Christian Sohler. 2006\.  Counting Triangles in Data Streams. In _Proceedings of the Twenty-Fifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems_ (Chicago, IL, USA) _(PODS ’06)_. Association for Computing Machinery, New York, NY, USA, 253–262.  https://doi.org/10.1145/1142351.1142388
  * Chakaravarthy et al. (2016) V. T. Chakaravarthy, M. Kapralov, P. Murali, F. Petrini, X. Que, Y. Sabharwal, and B. Schieber. 2016.  Subgraph Counting: Color Coding Beyond Trees. In _2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS)_. IEEE Computer Society, Los Alamitos, CA, USA, 2–11.  https://doi.org/10.1109/IPDPS.2016.122
  * Chen et al. ([n. d.]) J. Chen, T. Eden, P. Indyk, S. Narayanan, R. Rubinfeld, S. Silwal, D. Woodruff, and M. Zhang. [n. d.].  Triangle and Four Cycle Counting with Predictions in Graph Streams.  _Tenth International Conference on Learning Representations (ICLR 2022)_ ([n. d.]).  https://par.nsf.gov/biblio/10338743
  * Chen and Qian (2022) Jingji Chen and Xuehai Qian. 2022.  DecoMine: A Compilation-Based Graph Pattern Mining System with Pattern Decomposition. In _Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 1_ (Vancouver, BC, Canada) _(ASPLOS 2023)_. Association for Computing Machinery, New York, NY, USA, 47–61.  https://doi.org/10.1145/3567955.3567956
  * Chen et al. (2022) Justin Y Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David Woodruff, and Michael Zhang. 2022\.  Triangle and Four Cycle Counting with Predictions in Graph Streams. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=8in_5gN9I0
  * Chen et al. (2021) Xuhao Chen, Roshan Dathathri, Gurbinder Gill, Loc Hoang, and Keshav Pingali. 2021.  Sandslash: A Two-Level Framework for Efficient Graph Pattern Mining. In _Proceedings of the 35th ACM International Conference on Supercomputing_ _(ICS ’21)_. 14 pages.
  * Chen et al. (2020) Xuhao Chen, Roshan Dathathri, Gurbinder Gill, and Keshav Pingali. 2020.  Pangolin: An Efficient and Flexible Graph Mining System on CPU and GPU.  _Proc. VLDB Endow._ 13, 8 (Aug. 2020).  https://doi.org/10.14778/3389133.3389137
  * Chen et al. (2016) Xiaowei Chen, Yongkun Li, Pinghui Wang, and John C. S. Lui. 2016\.  A General Framework for Estimating Graphlet Statistics via Random Walk.  _Proc. VLDB Endow._ 10, 3 (nov 2016), 253–264.  https://doi.org/10.14778/3021924.3021940
  * Dias et al. (2019) Vinicius Dias, Carlos H. C. Teixeira, Dorgival Guedes, Wagner Meira, and Srinivasan Parthasarathy. 2019\.  Fractal: A General-Purpose Graph Pattern Mining System. In _Proceedings of the 2019 International Conference on Management of Data_ (Amsterdam, Netherlands) _(SIGMOD ’19)_. ACM, New York, NY, USA, 1357–1374.  https://doi.org/10.1145/3299869.3319875
  * Elenberg et al. (2015) Ethan R. Elenberg, Karthikeyan Shanmugam, Michael Borokhovich, and Alexandros G. Dimakis. 2015\.  Beyond Triangles: A Distributed Framework for Estimating 3-profiles of Large Graphs. In _Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ (Sydney, NSW, Australia) _(KDD ’15)_. ACM, New York, NY, USA, 229–238.  https://doi.org/10.1145/2783258.2783413
  * Fung et al. (2011) Wai Shing Fung, Ramesh Hariharan, Nicholas J.A. Harvey, and Debmalya Panigrahi. 2011.  A General Framework for Graph Sparsification. In _Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing_ (San Jose, California, USA) _(STOC ’11)_. Association for Computing Machinery, New York, NY, USA, 71–80.  https://doi.org/10.1145/1993636.1993647
  * Hüffner et al. (2008) Falk Hüffner, Sebastian Wernicke, and Thomas Zichner. 2008.  Algorithm engineering for color-coding with applications to signaling pathway detection.  _Algorithmica_ 52 (2008), 114–132.
  * Iyer et al. (2018) Anand Padmanabha Iyer, Zaoxing Liu, Xin Jin, Shivaram Venkataraman, Vladimir Braverman, and Ion Stoica. 2018\.  ASAP: Fast, Approximate Graph Pattern Mining at Scale. In _Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation_ (Carlsbad, CA, USA) _(OSDI’18)_. USENIX Association, Berkeley, CA, USA, 745–761.  http://dl.acm.org/citation.cfm?id=3291168.3291224
  * Jamshidi et al. (2020) Kasra Jamshidi, Rakesh Mahadasa, and Keval Vora. 2020\.  Peregrine: A Pattern-Aware Graph Mining System. In _Proceedings of the Fifteenth EuroSys Conference_ _(EuroSys ’20)_.
  * Jha et al. (2015) Madhav Jha, C. Seshadhri, and Ali Pinar. 2015.  Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts. In _Proceedings of the 24th International Conference on World Wide Web_ (Florence, Italy) _(WWW ’15)_. International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, Switzerland, 495–505.  https://doi.org/10.1145/2736277.2741101
  * Jiang et al. (2023) Peng Jiang, Yihua Wei, Jiya Su, Rujia Wang, and Bo Wu. 2023.  SampleMine: A Framework for Applying Random Sampling to Subgraph Pattern Mining through Loop Perforation. In _Proceedings of the International Conference on Parallel Architectures and Compilation Techniques_ (Chicago, Illinois) _(PACT ’22)_. Association for Computing Machinery, New York, NY, USA, 185–197.  https://doi.org/10.1145/3559009.3569658
  * Kallaugher et al. (2019) John Kallaugher, Andrew McGregor, Eric Price, and Sofya Vorotnikova. 2019.  The Complexity of Counting Cycles in the Adjacency List Streaming Model. In _Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems_ (Amsterdam, Netherlands) _(PODS ’19)_. Association for Computing Machinery, New York, NY, USA, 119–133.  https://doi.org/10.1145/3294052.3319706
  * Kuramochi and Karypis (2004) Michihiro Kuramochi and George Karypis. 2004.  GREW-A Scalable Frequent Subgraph Discovery Algorithm. In _Proceedings of the Fourth IEEE International Conference on Data Mining_ _(ICDM ’04)_. IEEE Computer Society, USA, 439–442.
  * Kwak et al. (2010) Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. 2010\.  What is Twitter, a Social Network or a News Media?. In _Proceedings of the 19th International Conference on World Wide Web_ (Raleigh, North Carolina, USA) _(WWW ’10)_. ACM, New York, NY, USA, 591–600.  https://doi.org/10.1145/1772690.1772751
  * Leskovec (2013) J. Leskovec. 2013\.  SNAP: Stanford Network Analysis Platform.  http://snap.stanford.edu/data/index.html
  * Mawhirter et al. (2021) Daniel Mawhirter, Sam Reinehr, Connor Holmes, Tongping Liu, and Bo Wu. 2021.  GraphZero: A High-Performance Subgraph Matching System.  _SIGOPS Oper. Syst. Rev._ 55, 1 (June 2021), 21–37.  https://doi.org/10.1145/3469379.3469383
  * Mawhirter and Wu (2019) Daniel Mawhirter and Bo Wu. 2019.  AutoMine: Harmonizing High-level Abstraction and High Performance for Graph Mining. In _Proceedings of the 27th ACM Symposium on Operating Systems Principles_ (Huntsville, Ontario, Canada) _(SOSP ’19)_. ACM, New York, NY, USA, 509–523.  https://doi.org/10.1145/3341301.3359633
  * Mhedhbi and Salihoglu (2019) Amine Mhedhbi and Semih Salihoglu. 2019.  Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins.  _Proc. VLDB Endow._ 12, 11 (July 2019), 1692–1704.  https://doi.org/10.14778/3342263.3342643
  * Milo et al. (2002) R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. 2002\.  Network Motifs: Simple Building Blocks of Complex Networks.  _Science_ 298, 5594 (2002), 824–827.  https://doi.org/10.1126/science.298.5594.824 arXiv:https://science.sciencemag.org/content/298/5594/824.full.pdf
  * Pagh and Tsourakakis (2012) Rasmus Pagh and Charalampos E. Tsourakakis. 2012\.  Colorful Triangle Counting and a MapReduce Implementation.  _Inf. Process. Lett._ 112, 7 (mar 2012), 277–281.  https://doi.org/10.1016/j.ipl.2011.12.007
  * Paramonov et al. (2019) Kirill Paramonov, Dmitry Shemetov, and James Sharpnack. 2019\.  Estimating Graphlet Statistics via Lifting. In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_ (Anchorage, AK, USA) _(KDD ’19)_. Association for Computing Machinery, New York, NY, USA, 587–595.  https://doi.org/10.1145/3292500.3330995
  * Pavan et al. (2013) A. Pavan, Kanat Tangwongsan, Srikanta Tirthapura, and Kun-Lung Wu. 2013.  Counting and Sampling Triangles from a Graph Stream.  _Proc. VLDB Endow._ 6, 14 (sep 2013), 1870–1881.  https://doi.org/10.14778/2556549.2556569
  * Pinar et al. (2017) Ali Pinar, C. Seshadhri, and Vaidyanathan Vishal. 2017\.  ESCAPE: Efficiently Counting All 5-Vertex Subgraphs. In _Proceedings of the 26th International Conference on World Wide Web_ (Perth, Australia) _(WWW ’17)_. International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, Switzerland, 1431–1440.  https://doi.org/10.1145/3038912.3052597
  * Preti et al. (2021) Giulia Preti, Gianmarco De Francisci Morales, and Matteo Riondato. 2021\.  MaNIACS: Approximate Mining of Frequent Subgraph Patterns through Sampling. In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_ (Virtual Event, Singapore) _(KDD ’21)_. Association for Computing Machinery, New York, NY, USA, 1348–1358.  https://doi.org/10.1145/3447548.3467344
  * Purohit et al. (2017) Sumit Purohit, Sutanay Choudhury, and Lawrence B. Holder. 2017\.  Application-specific graph sampling for frequent subgraph mining and community detection. In _2017 IEEE International Conference on Big Data (Big Data)_. 1000–1005.  https://doi.org/10.1109/BigData.2017.8258022
  * Rossi et al. (2019) Ryan A. Rossi, Rong Zhou, and Nesreen K. Ahmed. 2019.  Estimation of Graphlet Counts in Massive Networks.  _IEEE Transactions on Neural Networks and Learning Systems_ 30, 1 (2019), 44–57.  https://doi.org/10.1109/TNNLS.2018.2826529
  * Sanei-Mehri et al. (2018) Seyed-Vahid Sanei-Mehri, Ahmet Erdem Sariyuce, and Srikanta Tirthapura. 2018.  Butterfly Counting in Bipartite Networks. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_ (London, United Kingdom) _(KDD ’18)_. Association for Computing Machinery, New York, NY, USA, 2150–2159.  https://doi.org/10.1145/3219819.3220097
  * Shi et al. (2020a) Jessica Shi, Laxman Dhulipala, and Julian Shun. 2020a.  Parallel Clique Counting and Peeling Algorithms. In _Conference on Applied and Computational Discrete Algorithms_.
  * Shi et al. (2022) Jessica Shi, Louisa Ruixue Huang, and Julian Shun. 2022\.  Parallel Five-Cycle Counting Algorithms.  _ACM J. Exp. Algorithmics_ 27, Article 4.1 (oct 2022), 23 pages.  https://doi.org/10.1145/3556541
  * Shi et al. (2020b) Tianhui Shi, Mingshu Zhai, Yi Xu, and Jidong Zhai. 2020b.  GraphPi: High Performance Graph Pattern Matching through Effective Redundancy Elimination. In _Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis_ (Atlanta, Georgia) _(SC ’20)_. IEEE Press, Article 100, 14 pages.
  * Slota and Madduri (2013) George M. Slota and Kamesh Madduri. 2013.  Fast Approximate Subgraph Counting and Enumeration. In _2013 42nd International Conference on Parallel Processing_. 210–219.  https://doi.org/10.1109/ICPP.2013.30
  * Slota and Madduri (2015) George M. Slota and Kamesh Madduri. 2015.  Parallel color-coding.  _Parallel Comput._ 47 (2015), 51–69.  https://doi.org/10.1016/j.parco.2015.02.004 Graph analysis for scientific discovery.
  * Spielman and Srivastava (2011) Daniel A. Spielman and Nikhil Srivastava. 2011.  Graph Sparsification by Effective Resistances.  _SIAM J. Comput._ 40, 6 (2011), 1913–1926.  https://doi.org/10.1137/080734029 arXiv:https://doi.org/10.1137/080734029
  * Spielman and Teng (2004) Daniel A Spielman and Shang-Hua Teng. 2004.  Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In _Proceedings of the thirty-sixth annual ACM symposium on Theory of computing_. 81–90.
  * Spielman and Teng (2011) Daniel A Spielman and Shang-Hua Teng. 2011.  Spectral sparsification of graphs.  _SIAM J. Comput._ 40, 4 (2011), 981–1025.
  * Teixeira et al. (2015) Carlos H. C. Teixeira, Alexandre J. Fonseca, Marco Serafini, Georgos Siganos, Mohammed J. Zaki, and Ashraf Aboulnaga. 2015.  Arabesque: A System for Distributed Graph Mining. In _Proceedings of the 25th Symposium on Operating Systems Principles_ (Monterey, California) _(SOSP ’15)_. ACM, New York, NY, USA, 425–440.  https://doi.org/10.1145/2815400.2815410
  * Tsourakakis et al. (2011) Charalampos E Tsourakakis, Petros Drineas, Eirinaios Michelakis, Ioannis Koutis, and Christos Faloutsos. 2011.  Spectral counting of triangles via element-wise sparsification and triangle-based link recommendation.  _Social Network Analysis and Mining_ 1 (2011), 75–81.
  * Tsourakakis et al. (2009) Charalampos E. Tsourakakis, U. Kang, Gary L. Miller, and Christos Faloutsos. 2009.  DOULION: Counting Triangles in Massive Graphs with a Coin. In _Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ (Paris, France) _(KDD ’09)_. Association for Computing Machinery, New York, NY, USA, 837–846.  https://doi.org/10.1145/1557019.1557111
  * Turk and Turkoglu (2019) Ata Turk and Duru Turkoglu. 2019.  Revisiting Wedge Sampling for Triangle Counting. In _The World Wide Web Conference_ (San Francisco, CA, USA) _(WWW ’19)_. Association for Computing Machinery, New York, NY, USA, 1875–1885.  https://doi.org/10.1145/3308558.3313534
  * Xuhao Chen and Arvind (fpdf) Xuhao Chen and Arvind. 2022 [pdf].  Efficient and Scalable Graph Pattern Mining on GPUs. In _Proceedings of the 16th USENIX Symposium on Operating Systems Design and Implementation(OSDI)_.
  * Wang et al. (2018) Kai Wang, Zhiqiang Zuo, John Thorpe, Tien Quang Nguyen, and Guoqing Harry Xu. 2018.  RStream: Marrying Relational Algebra with Streaming for Efficient Graph Mining on a Single Machine. In _Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation_ (Carlsbad, CA, USA) _(OSDI’18)_. USENIX Association, Berkeley, CA, USA, 763–782.  http://dl.acm.org/citation.cfm?id=3291168.3291225
  * Wang et al. (2014) Pinghui Wang, John C. S. Lui, Bruno Ribeiro, Don Towsley, Junzhou Zhao, and Xiaohong Guan. 2014\.  Efficiently Estimating Motif Statistics of Large Networks.  _ACM Trans. Knowl. Discov. Data_ 9, 2, Article 8 (sep 2014), 27 pages.  https://doi.org/10.1145/2629564
  * Yang and Leskovec (2012) Jaewon Yang and Jure Leskovec. 2012.  Defining and Evaluating Network Communities based on Ground-truth.  _CoRR_ abs/1205.6233 (2012).  arXiv:1205.6233 http://arxiv.org/abs/1205.6233
  * Ye et al. (2022) Xiaowei Ye, Rong-Hua Li, Qiangqiang Dai, Hongzhi Chen, and Guoren Wang. 2022.  Lightning Fast and Space Efficient K-Clique Counting. In _Proceedings of the ACM Web Conference 2022_ (Virtual Event, Lyon, France) _(WWW ’22)_. Association for Computing Machinery, New York, NY, USA, 1191–1202.  https://doi.org/10.1145/3485447.3512167
  * Zhao et al. (2010) Zhao Zhao, Maleq Khan, V. S. Anil Kumar, and Madhav V. Marathe. 2010.  Subgraph Enumeration in Large Social Contact Networks Using Parallel Color Coding and Streaming. In _2010 39th International Conference on Parallel Processing_. 594–603.  https://doi.org/10.1109/ICPP.2010.67
  * Zhao et al. (2012) Zhao Zhao, Guanying Wang, Ali R. Butt, Maleq Khan, V.S. Anil Kumar, and Madhav V. Marathe. 2012.  SAHAD: Subgraph Analysis in Massive Networks Using Hadoop. In _2012 IEEE 26th International Parallel and Distributed Processing Symposium_. 390–401.  https://doi.org/10.1109/IPDPS.2012.44
  * Zhu et al. (2023) Zeying Zhu, Kan Wu, and Zaoxing Liu. 2023.  Arya: Arbitrary Graph Pattern Mining with Decomposition-based Sampling. In _Proceedings of the 20th USENIX Symposium on Networked Systems Design and Implementation_ _(NSDI’23)_.