An Efficient Streaming Algorithm for Approximating Graphlet Distributions∗
arXiv:2604.25400v1 [cs.DS] 28 Apr 2026
Marco Bressan†
T-H. Hubert Chan‡
Qipeng Kuang‡
Mauro Sozio§
Abstract In recent years, the problem of computing the frequencies of the induced k-vertex subgraphs of a graph, or k-graphlets, has become central. One approach for this problem is to sample kgraphlets randomly. Classic algorithms for k-graphlet sampling require loading the entire graph into main memory, making them impractical for massive graphs. To bypass this limitation, Bourreau et al. (NeurIPS 2024) introduced a streaming algorithm that through nontrivial techniques makes only O(log n) passes using O(n log n) memory. In this work we break their O(log n)-pass bound by giving an algorithm that, for any fixed c > 0, makes O(1/c) passes using Õ(n1+c ) memory. As a consequence of their lower bound, our algorithm is optimal up to a factor of Õ(nc ) in the memory usage. We use this sampling algorithm to obtain an efficient method of approximating k-graphlet distributions. Experiments on real-world and synthetic graphs show that our algorithm is always at least as good as the one of Bourreau et al., and outperforms it by orders of magnitude on mildly dense graphs.
1
Introduction
A k-graphlet of a simple graph G is a connected, induced subgraph formed by exactly k vertices. Two k-vertex subsets are equivalent if their induced subgraphs are isomorphic. The so-called k-graphlet distribution of G is the frequency vector that provides the relative size of each such equivalence class. It is known that the k-graphlet distribution captures important structural information [34] that is relevant in many real-world applications, such as graph classification [43], graph kernels [40], graph neural networks [37], and federated learning [23]. In this work, we study the problem of approximating the k-graphlet distribution when the input graph cannot be stored in memory. A first major distinction must be made between exact and approximate algorithms. A trivial exact algorithm is the one that enumerates and checks all k-vertex subsets of the input graph. This algorithm is obviously inefficient, and there is strong evidence that one cannot perform substantially better (see classic lower bounds from parameterized complexity, such as [18] or [26]). Our focus is instead on approximate algorithms, which (roughly speaking) compute the k-graphlet distribution within some small additive error α > 0. It is clear that this problem can be reduced, in the obvious way, to sampling k-graphlets randomly from the underlying graph. Many algorithms for sampling kgraphlets have been proposed, broadly divided in those based on random walks [1, 7, 19, 24, 38, 44] and those based on color coding [13, 14, 15, 16]. Eventually, [9, 12] described Ugs, an algorithm that preprocesses the graph with n vertices and m edges in time O(nk2 log k+m) and then produces ∗
Authors appear in alphabetical order. University of Milan. ‡ The University of Hong Kong. § LUISS University. †
1
independent uniform k-graphlets in kO(k) log n time per sample, yielding an efficient algorithm to approximate the k-graphlet distribution. Although Ugs allows one to sample k-graphlets efficiently, it does so only in the standard RAM model, where the input must fit entirely in memory. Unfortunately, in practice the graph is often too large for the machine’s memory; this is commonplace for real-world graphs, such as those representing social networks, the Web, the human brain and many others. In these cases, Ugs simply does not work, and the same holds for the other algorithms listed above. To bypass these limitations, [8] has recently initiated the study of the k-graphlet sampling problem in the streaming model. In this model, the input edges can only be accessed sequentially in an arbitrary order, while using an amount of memory sublinear in the size of the input graph. Streaming algorithms process the graph over multiple passes, with each pass involving the processing of all edges in the input graph. Studying the k-graphlet distribution problem in the streaming model avoids the obstacle of storing the graph in memory, and turns the optimization target to the number of passes versus the memory usage. The bottleneck of the algorithm provided by [8] is in the preprocessing phase, called ApproxDD, which computes an approximate degree-dominating order of vertices—a vertex ordering where each vertex has approximately the highest degree in the subgraph induced by its suffix. This preprocessing phase uses O(n log n) memory and O(log n) passes or, alternatively, O(n) memory and O(log n · log log n) passes. (This regime, where the memory allowed is linear or near-linear in n, is called the semi-streaming model). Unfortunately, ApproxDD is still inefficient for at least two reasons. The first reason is that it requires O(log n) passes. It is not clear that this is optimal; the very lower bounds from [8] only rule out O(1) passes with o(n) memory, but not, say, O(1) or O(log log n) passes with O(n) or O(n log n) memory. The second reason is that, as shown by our experiments, ApproxDD basically breaks down on mildly dense graphs: it takes thousands of passes, or even fails to run, even with a memory of (say) 10% the size of the input graph. In this work we aim at bypassing these limitations, by seeking an algorithm that runs in O(1) passes and guarantees good performance regardless of the density of the graph.
1.1
Contributions
We develop a streaming algorithm to approximate the k-graphlet distribution, with the following guarantees: Theorem 1.1. There is a two-phase semi-streaming algorithm with the following guarantees. Given c > 0, a simple graph G, a positive integer k ≥ 3, an error parameter α ∈ (0, 1) and a failure probability δ ∈ (0, 1), the algorithm returns a distribution p̂ such that: • The first phase (“preprocessing”) uses O (1/c) passes and Õ n1+c bits of memory1 , with probability at least 1 − n1 . O(k) • The second phase (“sampling”) always uses O kα4 M ln 1δ passes and M bits of memory. • The L∞ distance between p̂ and the k-graphlet distribution of G is at most α, with probability at least 1 − δ. Our algorithm follows the stream-Ugs framework introduced by Bourreau et al. [8]: 1
The standard Õ(·) notation hides poly log(·) factors.
2
Preprocessing Phase (a) Compute an approximate degree-dominating order (DD order, see Definition 2.1), a special total order of the vertices that enables fast uniform graphlet sampling [9, 12]; (b) Compute the initial probabilities; Sampling Phase (c) Repeatedly sample k-graphlets. (d) Either (i) execute probabilistic rejection (in [8]), or (ii) obtain the k-graphlet distribution (in this work).
On the theoretical side, the main contribution behind Theorem 1.1 is a new streaming algorithm for computing a DD order in Step (a). Unlike the algorithm of [8], which intrinsically requires O(log n) passes because of its “halving degree” strategy, our algorithm requires only O(1/c) passes2 , at the cost of higher memory usage. This is thanks to a strategy that, speaking broadly, consists in sampling enough edges from the input graph so as to make, in a single pass, much more progress than the algorithm of [8]. We remark that, by a lower bound of [8], no algorithm using O(1) passes and o(n) memory can even decide if the input graph contains some k-graphlet, for a fixed k ≥ 2. Since computing the graphlet distribution implies solving such a decision problem, the memory used by our graphlet distribution algorithm is optimal up to a factor of Õ(nc ). Our algorithm also differs from the corresponding algorithm in [8] in Step (d): in particular, our work employs the Horvitz-Thompson-based algorithm [25] to approximate the k-graphlet distribution within L∞ distance α, whereas [8] focuses on uniform k-graphlet sampling using probabilistic rejection. On the practical side, although our memory usage goes with n1+c rather than just n, it turns out that picking c small enough makes our algorithm very competitive compared to [8]. In our experiments, by choosing c = 0.1, our algorithm makes around 20 preprocessing passes on most datasets, and yet its memory usage is always within one and a half times that of [8]. In fact, on datasets that are only mildly dense, our algorithm drastically outperforms the one of [8]. For example, on a dataset with n ≈ 2 × 105 vertices and average degree ≈ 500 = 0.0025n, both algorithms use around 20MB of memory, but ours makes less than 20 passes and the one of [8] more than 3000. Our algorithm thus performs well both in theory and in practice, and is scalable and predictable regardless of the structure of the input graph.
1.2
Related Work
Counting and sampling triangles can be considered as a special case of computing the k-graphlet distribution as k = 3. Most streaming algorithms for this task in the literature, such as [4, 5, 36, 2, 27, 41, 31], do not generalize or give guarantees for k > 3. Streaming algorithms for counting or sampling k-graphlets for a generic k exist, such as [28] and [42]. Notice that their streaming setting is different from ours, as they consider only single-pass algorithms, they ask to maintain 2
Note that the guarantees of [8] are probabilistic for number of passes and deterministic for the memory, while our guarantees are probabilistic for both.
3
a good approximation throughout the entire stream, and they have stricter memory requirements. The downside is that both works give guarantees only for specific graphlets. Many algorithms exist for counting and sampling k-graphlets, or estimating the k-graphlet distribution, in the standard computation model [1, 7, 13, 14, 15, 16, 19, 24, 32, 35, 38, 44]. All those algorithms have poor memory consumption, as they need to store the whole graph in memory. Among those algorithms, one that is still relatively efficient is Motivo [16], which is based on the color-coding technique. Motivo has formal approximation guarantees, and in practice it can approximate well the k-graphlet distribution on large graphs in a matter of minutes or hours (depending on k) when running on a workstation. In this work we use it to compute the groundtruth k-graphlet distributions for our experiments. Topological orders play an important role in subgraph mining problems. For example, the degeneracy (or core) order, one of the most commonly used orders, enables efficient subgraphcounting algorithms [33, 20, 11, 6]. There are also streaming algorithms involving computing topological orders [3, 39, 8]. We remark that computing the core order is technically different from computing the degree-dominating order that is used in this work. Indeed, while a core order is obtained by repeatedly removing a vertex of minimum degree, a degree-dominating order is obtained by removing one of maximum degree, and it is easy to find examples where the two orders are not obviously related in any way. Therefore, existing streaming algorithms for core orders [3, 39] cannot be employed here. We face a technical challenge similar to the one of [22], where the authors approximate the k-core decomposition in parallel: keeping accurate estimates of vertex degrees while iteratively removing vertices in a large graph. Maintaining the degrees by scanning the entire edge list after each removal would require too many passes. Their solution is to work on a sub-sampled graph, produced by sampling each edge with an appropriate probability p. On the one hand, by standard concentration results, the degrees in the sub-sampled graph provide a good estimate of the true degree. On the other hand, only a small fraction of edges is sampled, thus one may fit the memory requirements of the streaming algorithm. We use a Horvitz–Thompson estimator [25] to estimate the distribution of a set of objects when only a non-uniform sampling of the objects can be accessed. This estimator helps us approximate the k-graphlet distribution without sampling k-graphlets uniformly at random; see also [16].
1.3
Organization
We define notation and key notions in Section 2. The new algorithm for computing the DD order is presented in Section 3. The algorithm for estimating the k-graphlet distribution is then completed in Section 4. Finally, the experiments to evaluate our algorithm and compare with existing work are shown in Section 5.
2
Preliminaries
This section introduces basic notation and the main technical concepts.
2.1
Notation and Computational Model
Let G = (V, E) be a simple graph and let n = |V |. For a subset U ⊆ V of vertices, G[U ] denotes the subgraph of G induced by U , and G − U denotes the subgraph G[V \ U ]. For a total order ≺ over V , we let G(v) be the subgraph G[{u : v u}]. For u ∈ V , we denote by du the degree of u in G; if H is a subgraph of G and u ∈ V (H), then we denote by d(u|H) the degree of u in H. 4
4 1
4 : 11
2
6 : 11
3 5
1 : 11
6
Figure 1: A toy graph (left) and its 4-graphlet distribution (right). 4-graphlets with probability 0 are not shown. 4
1
3 5
6 G(1)
4
2
2
3 5
4
6
5 6 G(2)
G(3)
2
4 5 6 G(5)
1 Figure 2: Computation of a 1.5 -DD ordering of a toy graph, by iterative removal of a high-degree 1 -DD ordering is 1 ≺ 3 ≺ 2 ≺ 5 ≺ 6 ≺ 4. vertex. The resulting 1.5
This applies in particular to H = G(v), so we may write d(u|G(v)). We denote by ∆ the maximum degree of G. The smallest value for which the problem is non-trivial is k ≥ 3. A k-graphlet of G is an induced, connected, k-vertex subgraph of G. We denote by g1 , · · · , gmk , the representatives of the isomorphism classes of connected graphs on k vertices, in any order. Thus, every k-graphlet of G is isomorphic to precisely one gi . For i = 1, . . . , mk let li be the number of induced subgraphs Peach k of G isomorphic to gi , and let L = m l . i=1 i The k-graphlet distribution of G is the vector µk , (µ1 , · · · , µmk )
where µi = lLi for each i. Our goal is to estimate µk . An example of the k-graphlet distribution is presented in Figure 1. A notion central to this approach is the degree-dominating ordering (DD-ordering) introduced in [10], as well as its approximate version from [8]. Definition 2.1 ((Approximate) DD-ordering). Given a simple graph G = (V, E), a total order ≺ over V is degree-dominating if, for each v ∈ V , the maximum degree in G(v) is achieved by v itself; in other words, d(v|G(v)) ≥ d(u|G(v)) for all u v. For ϑ > 0, a ϑ-DD order ≺ is a total order over V such that, for all v ∈ V with d(v|G(v)) ≥ 1 and all u v, it holds that d(v|G(v)) ≥ ϑ · d(u|G(v)). 1 We often use ϑ = 1+ǫ for some ǫ > 0. An example of DD-ordering is shown in Figure 2. A 1 possible 1.5 -DD order of the graph is 1 ≺ 3 ≺ 2 ≺ 5 ≺ 6 ≺ 4. Note that for the first position of the order, we have d(1|G(1)) = 3 and maxu1 d(u|G(1)) = d(3|G(1)) = 4, which satisfies 1 · maxu1 d(u|G(1)). d(1|G(1)) ≥ 1.5 We consider the semi-streaming model of [21]. In this model, the memory consists of M = Õ(n1+c ) words of O(log n) bits for some constant c > 0 (for example, c = 0.1). The algorithm can access the graph by scanning its edges, sequentially, in what is called a pass. The order in which edges appear in each pass is arbitrary (that is, decided by an adversary), and the algorithm can make any number of passes. We assume m = Ω(M ) to avoid trivialities. All computation will be in the standard RAM model.
5
2.2
Uniform Graphlet Sampling
Our work builds on stream-Ugs, the streaming algorithm of Bourreau et al. [8]. stream-Ugs consists of a preprocessing phase and a sampling phase. The preprocessing phase is run once, 1 for some desired ǫ > 0, together with an initial and computes a ϑ-DD order ≺, where ϑ = 1+ǫ distribution p over V . With ≺ and p one can then implement a k-pass sampling routine ensuring that any given k-graphlet of G has the same sampling probability except for a multiplicative factor of ((1 + ǫ)k)O(k) . Using rejection sampling one can remove that factor and get truly uniform sampling, with an overhead of ((1+ǫ)k)O(k) expected trials per sample. The crucial part is therefore computing ≺ and p with as few passes as possible. Computing the ϑ-DD order. ≺ with high As shown in [8, Theorem 3.1], one can compute log n log n log n probability in O ǫ2 log ǫ passes by using memory O(n), or in O ǫ2 passes by using n ∆ memory O n log , where . The idea is to select a subset S of vertices that have degree at least 1+ǫ ǫ ∆ is the maximum degree of G. This can be done with high probability with a constant number of passes. The set S is then appended to ≺ in arbitrary order, and S is removed from G (meaning that the algorithm keeps track, in some way, of the subgraph obtained by removing S). Therefore, 1 . As a consequence, the every O(1) passes the maximum degree of G decreases by a factor 1+ǫ algorithm terminates within log 1 n passes. 1+ǫ
1 -DD order, let Nv be the number of k-graphlets in G(v) Initial Distribution. Given a 1+ǫ containing v. Computing d(v|G(v)) and deciding whether Nv > 0 for all vertices in V can be done in 1 pass and O(kn) memory by [8, Lemma 3.3]. After that, the normalization parameter X Z= d(v|G(v))k−1 v∈V, Nv >0
as well as the initial distribution p = {p(v)|v ∈ V } such that ( d(v|G(v))k−1 , Nv > 0, Z p(v) = 0, Nv = 0 can be computed without any pass. This subroutine is formally described in Algorithm 1. The initial distribution will be used later to select the starting vertex and compute the relevant sampling probability in the sampling phase. Algorithm 1: Initial Distribution [8, Algorithm 2] 1 Function InitDistrib (G, ≺) 2 3 4 5
Compute d(v|G(v)) and decide whether Nv > 0 for each v ∈ V P Z ← v∈V, Nv >0 d(v|G(v))k−1 ( d(v|G(v))k−1 , Nv > 0, Z p(v) ← 0, Nv = 0 return p = {p(v)|v ∈ V }
Rejection Sampling. At a high level, we first sample a k-graphlet of G and then accept it with some probability so that the probability of each k-graphlet being sampled and accepted is the same. The first sampling step goes as follows. We sample a vertex v according to the initial distribution p = {p(v)|v ∈ V } and let S = {v}. Then we “grow” S for k − 1 times, each time by selecting 6
uniformly at random an edge in G(v) with exactly one endpoint in S, and adding the other endpoint to S. In this way, we obtain a k-graphlet S with probability p(S) = p(v) · p(S|v), where p(S|v) is the probability of obtaining S from v. All those probabilities can be computed efficiently. This sampling algorithm is formally described in Algorithm 2. Algorithm 2: Sampling A Graphlet [8, Algorithm 3] 1 Function SampleGraphlet (G, ≺, k, p)
6
Sample v from the distribution p S ← {v} for i ← 1 to k − 1 do Uniformly sample an edge (x, y) in G(v) such that x ∈ S and y 6∈ S S ← S ∪ {y}
7
return S
2 3 4 5
To achieve uniform sampling, let Γ be some constant such that 0 < Γ ≤ minS p(S), where S Γ , ranges over all k-tuples of vertices such that p(S) > 0. We then accept S with probability p(S) otherwise reject S and sample again. By [8, Lemma C.1], with high constant probability (say 0.99), after (k(1 + ǫ))O(k) trials of sampling we accept a k-graphlet, and that k-graphlet is drawn from the uniform distribution. Parallel sampling. As Algorithm 2 uses memory O(k2 ), by using memory M one can run Θ M 2 k M instances in parallel, and produce with high probability Θ (k(1+ǫ)) independent uniformly O(k) random k-graphlets. Moreover, [8, Theorem 3.4] gives a trade-off between running time and number of passes: the parallel sampling can be achieved either in k passes and O(M |E|) time, or in 2k − 1 passes and O(M 2k + k|E| log n) time.
2.3
Concentration Inequalities
Let B(m, p) denote the binomial distribution with parameters m, p. We use the following Chernoffstyle bounds in our analysis. Fact 2.1 (Chernoff Bound Variant I). Let X ∼ B(m, p) and 0 < ǫ < 1. Then, we have the following: • If m ≥ N , Pr [X ≤ (1 − ǫ)N p] ≤ exp − 31 ǫ2 N p. • If m ≤ N , Pr [X ≥ (1 + ǫ)N p] ≤ exp − 31 ǫ2 N p .
Fact 2.1 follows from stochastic dominance together with another variant of the Chernoff Bound.
Lemma 2.2 (Stochastic Dominance). Let n ≤ m, let X ∼ B(n, p) and Y ∼ B(m, p). For any c, Pr [X > c] ≤ Pr [Y > c]. P Proof. Let x1 , · · · , xm be Bernoulli variables with positive probability p. Let A = ni=1 xi , B = P m i=n+1 xi , and C = A + B. Thus A and X have the same distribution, and C and Y have the same distribution. Now observe that, for any c, Pr [X > c] = Pr [A > c] ≤ Pr [C > c] = Pr [Y > c] .
7
Fact 2.2 (Chernoff Bound = ri ] = pi for Pm Variant II). Let D be the distribution given by Pr [X P m i = 1, · · · , m where i=1 pi = 1. A variable following D has expectation E = i=1 pi ri . Let X1 , · · · , XT be i.i.d. variables following D. For any 0 < ǫ < 1, we have the following inequality: # " P T ǫ2 T E X i=1 i − E ≥ ǫE ≤ 2 exp − . Pr T 3 maxm i=1 ri We also use Hoeffding’s inequality. Fact 2.3 (Hoeffding’s inequality). Let D be the distribution given by P Pr [X = ri ] = pi for i = P m p = 1. A variable following D has expectation E = 1, · · · , m where m i=1 i i=1 pi ri . Let X1 , · · · , XT be i.i.d. variables following D. For any 0 < α < 1, we have the following inequality: # " P ! T 2 X 2T α i i=1 − E ≥ α ≤ 2 exp − Pr . 2 T (maxm i=1 ri )
3
Improved Algorithms to Compute the Degree-Dominating Order
As recalled above, the sampling phase of the algorithm of [8] requires just k or 2k − 1 passes, depending on the implementation. The preprocessing phase is the one that dominates the streaming complexity, with O(log n) passes or O(log n log log n) passes depending on the desired memory usage. The idea of [8], described in Section 2.2, is to use every pass to detect and remove the subset of ∆ , where ∆ is the current maximum degree of the graph. This leads vertices with degree at least 1+ǫ the maximum degree of G to decrease by a multiplicative factor of (1 + ǫ) at each pass, making the algorithm terminate within O(log1+ǫ n) passes, and at the same time the removal sequence yields 1 -DD ordering. precisely a 1+ǫ Our key challenge is to break through the O(log n) passes bound. In order to do that we must, ∆ at each pass, make more progress than just removing the vertices with degree at least 1+ǫ . Note that, whenever any vertex is removed, the degrees of the remaining vertices can change. Therefore there is a delicate tradeoff between (a) how many vertices one removes, and (b) how good the current degree estimates still are. In the approach of [8] described above, this tradeoff still works, because after each vertex-removal pass the degrees are recomputed exactly using one additional pass. In our case, however, we can make such a pass only O(1/c) times. Using similar ideas to [22], we modify the algorithm of [8] by computing, in a single pass, several approximations of the input graph, each one obtained by sub-sampling edges with a different probability. We then employ these sub-sampled graphs to provide the degree estimates required by several subsequent vertex-removal passes of [8]. In this way we are essentially “accelerating” the algorithm of [8] by performing several passes at once. For the sake in Section 3.1 a “warm-up” algorithm which ofreadability, we start by introducing log n n n passes and O ǫ2 log ǫδ memory. Then, in Section 3.2, we show how for any still uses O ǫ 1+c n desired c > 0 we can bring the passes down to O 1c passes at the price of using O nǫ3 log ǫδ memory.
3.1
A Simple Approach Using O(log n) Passes
The idea of the algorithm is as follows. We sample a directed graph G̃ by adding each direction of each edge of G into G̃ with some probability p. By picking an appropriate p, we have that: (1) the number of edges in G̃ is small with high probability; and (2) the out-going degree of each vertex is 8
a good estimate of its degree. As we sample the two directions of the original edge independently, the estimations of vertex degrees are independent, even if vertices are removed sequentially. We state a warm-up algorithm in Algorithm 3. Let U be the set of vertices of G, ǫ be the parameter of the DD order, and ≺ be an empty list. Define a probability p and we sample G̃ from G[U ] as described above using one pass such that with high probability, G̃ contains Õ ǫn2 edges. The degree of a vertex v in the subgraph G[H] for any H ⊆ U is then estimated by p1 times the out-degree of v in G̃[H]. Then we execute a subroutine Select-Large to append vertices with large estimated degree to ≺ and remove them from U , where a vertex is said to have large estimated ∆ for the maximum degree ∆ of the current graph G degree if its estimated degree is at least 1+Θ(ǫ) (or its estimation). Vertices are scanned in an arbitrary order. When a vertex v is considered, if ∆ , then we are supposed to its estimated degree in the current remaining graph is at least 1+Θ(ǫ) add v to ≺ and remove v together with its incident edges. In this way, we claim that after an ∆ will be appended to execution of Select-Large, only vertices with actual degree larger than 1+ǫ 1 ≺ and removed from U and thus ≺ is always a 1+ǫ -DD order. Moreover, the remaining vertices ∆ 1 have actual degree at most 1+Θ(ǫ) so that the maximum degree of G decreases by a factor 1+Θ(ǫ) . Algorithm 3: Approximate DD Order via Edge Sampling I 1 Function ApproxDD-Warmup (G = (V, E), ǫ, δ) 2 ≺← empty list 3 U ←V ǫ 4 ǫ̂ ← 4+3ǫ 5 ∆←n−1 ⊲ Max degree estimate; alternatively, computed with one pass. ∆ 6 K ←1+ǫ ⊲ A removed vertex should have current degree at least K 7 T ← log1+ ǫ n ⊲ Estimated number of iterations in while loop 2 8 while U 6= ∅ do 9 Using one pass on the edge list, construct a directed graph G̃ on U by sampling each direction each edge in G[U ] independently with probability p: 3K of2nT p = min ǫ̂2 ∆ ln δ , 1 10 (U, ≺) ← Select-Large(U, G̃, p, ∆, ≺) ∆ 11 ∆ ← 1+ ǫ 2
12
return ≺
13 Function Select-Large (U, G̃, p, ∆, ≺) 14 α ← 3ǫ 4 15 H←U 16 17 18 19 20 21
foreach v ∈ U in an arbitrary order do ˆ ← 1 × (Out-degree of v in G̃[H]) d(v)
⊲ Unbiased degree estimator in G[H]
p
ˆ ≥ ∆ then if d(v) 1+α Append v to ≺ H ← H \ {v}
⊲ Remove vertex v
return (H, ≺)
1 -DD order using O Theorem 3.1. With probability at least 1 − δ, Algorithm 3 returns a 1+ǫ n n passes and O ǫ2 log ǫδ words of memory.
9
log n ǫ
Proof. Proof structure. The proof separates the probabilistic part from the deterministic part. In the probabilistic part, we first define a small set of bad events that, if they occur, could violate either (i) the memory bound, (ii) the pass bound, or (iii) correctness of the returned order. We then bound the probability of each bad event using Chernoff bounds (Fact 2.1) and take a union bound over all vertices and all iterations. In the deterministic part, we condition on the event that none of these bad events occur in the first T iterations, and prove deterministically that the algorithm 1 -DD order, (a) makes geometric progress in ∆ and thus terminates in T iterations, (b) outputs a 1+ǫ and (c) never exceeds the claimed space. Bad Events in One Iteration. Suppose the maximum degree of G[U ] at the beginning of Select-Large is at most ∆. To simplify the notation, for a vertex v ∈ U at the moment it is considered in Select-Large, we use dv to denote its true degree in the remaining graph G[H] and dˆv to denote the unbiased estimation of dv , which has the distribution p1 × B(dv , p). The algorithm makes decisions using only the sampled graph G̃ and the estimates dˆv . Thus, there are two distinct failure modes to control: (1) G̃ can be too large (breaking the memory budget), and (2) dˆv can deviate enough to change a peel/keep decision (breaking progress or correctness). Accordingly, we consider the following bad events. Type I: The sampled directed graph G̃ has more than (1 + ǫ̂) · n∆p = Θ δ . Fact 2.1, this happens with probability at most exp − 31 ǫ̂2 n∆p ≤ 2T
n n log ǫδ ǫ2
edges. By
Intuition. The number of sampled directed edges is a sum of independent Bernoulli variables. At the start of the iteration, the total number of directed edges in G[U ] is at most n∆, and each is kept with probability p, so the expectation is at most n∆p. A multiplicative Chernoff bound then shows that exceeding (1 + ǫ̂)n∆p has exponentially small probability, which is n why choosing p so that n∆p = Θ ǫn2 log ǫδ suffices for a union bound over T iterations.
∆ ∆ , the bad event is dˆv < (1 − ǫ̂) · dv ; if dv < K Type II: For a vertex v, if dv ≥ K , the badevent is ∆ dˆv ≥ (1 + ǫ̂) · . By Fact 2.1, the bad event for each vertex is at most exp − 1 ǫ̂2 ∆p ≤ δ . K
3
K
2nT
Intuition. We split Type II into two cases because the harmful direction of estimation error depends on the true degree. If dv is large (dv ≥ ∆/K), then underestimating it could prevent peeling a vertex that should be removed, slowing the decrease of ∆. If dv is small (dv < ∆/K), then overestimating it could wrongly peel v, which would violate the DD property. The Chernoff bound is applied to the binomial B(dv , p), and we upper bound the failure probability uniformly by lower bounding the relevant mean by (∆/K)p, enabling a union bound over all vertices and all iterations. Figure 3 helps to illustrate the area of type II bad events.
The union of all bad events within one iteration has probability at most Tδ . Therefore, it suffices to show that if no bad event happens within the first T iterations, then the algorithm must terminate and return a correct result within the required memory. The Number of Passes. We consider one execution of Select-Large. If no type II bad event happens, we argue that if a vertex v is not removed, it must be the case that at the moment it is ∆ considered, we have dv ≤ 1+ ǫ , whose degree may drop even further as other vertices are removed 2 later. ∆ ∆ ∆ We do not need to worry about the case dv < K < 1+ ǫ . For the case dv ≥ K , since v is not 2 removed, we have dˆv < ∆ . Moreover, the type II bad event at v does not happen, and so we have 1+α dˆv ∆ ∆ dv ≤ 1−ǫ̂ < (1+α)(1−ǫ̂) = 1+ ǫ . This corresponds to the blue triangle area in Figure 3. 2
10
dˆv dˆv = (1 − ǫ̂)dv
bad ∆ 1+α
small must remain
bad ∆ dv 1 + 2ǫ
∆ K
Figure 3: The relation between the true degree dv and the estimated degree dˆv . The area of bad events is filled in gray. The blue triangle area indicates that if v is not removed in ∆ ∆ Select-Large, we have dv ≤ 1+ ǫ . The orange rectangle area indicates that if dv < K , v must 2 remain after Select-Large. Therefore, If no type II bad event happens within the first T iterations, any vertex that survives ∆ the scan already has degree at most 1+ ǫ at the moment it is considered. This means that ∆ will 2 drop below 1 after T = log1+ ǫ n = O logǫ n iterations at which point the algorithm must terminate. 2
Since each iteration uses 1 pass to build G̃, the total passes are T . Correctness. Within one iteration of Select-Large, it suffices to show that only vertices v ∆ satisfying dv ≥ K could possibly be removed, since for any other vertex u remaining before this 1 ∆ ≥ 1+ǫ d(u|G(v)). iteration, we have d(u|G(v)) ≤ ∆ and hence d(v|G(v)) = dv ≥ K ∆ Since the type II bad event for a vertex v satisfying dv < K does not happen, we must have ∆ ∆ ˆ = 1+α , which means such a vertex v will not be appended to ≺ when being dv < (1 + ǫ̂) · K considered. This corresponds to the orange rectangle area in Figure 3. 1 -DD Therefore, if no type II bad event happens within the first T iterations, then ≺ is a 1+ǫ order. Memory. The memory usage is dominated by the number of edges in the sampled graph G̃ in each iteration. Since the type I bad event does not happen within the first T iterations, we conclude n . that the number of edges sampled in each iteration is at most O ǫn2 log ǫδ
3.2
From O(log n) to O(1/c) Passes
One idea to decrease the number of passes in Algorithm 3 is to generate and remember several sampled directed graphs during a single pass, at the cost of using more memory. In Algorithm 4, instead of having one pass per iteration, a pass is made every q = ⌊log1+ ǫ nc ⌋ iterations for some 2 constant c > 0. The sampling probabilities are computed by the estimated maximum degree for each graph assuming its dropping by a factor of 1 + 2ǫ . The same subroutine Select-Large is executed on the sampled graphs sequentially. By choosing the appropriate c, we ensure that it 1 decreases the number of passes to O c , and each pass can lead to a factor nc decrease in the maximum degree ∆.
11
Algorithm 4: Approximate DD Order via Edge Sampling II 1 Function ApproxDD-ES (G = (V, E), ǫ, δ, c) 2 3 4 5 6 7 8 9 10 11 12 13 14
15 16 17 18 19
≺← empty list U ←V ǫ ǫ̂ ← 4+3ǫ ∆←n−1 ⊲ Max degree estimate; alternatively, computed with one pass. K ←1+ǫ T ← log1+ ǫ n ⊲ Estimated number of sampled directed graphs 2 c q, i ← ⌊log1+ ǫ n ⌋ 2 while U 6= ∅ do if i = q then for j from 0 to q − 1 do ⊲ Using one pass on edge list, sample q directed graphs. ∆j ← (1+∆ǫ )j o n2 2nT , 1 pj = min ǫ̂3K ln 2∆ δ j Construct a directed graph G̃j on U by sampling each direction of each edge in G[U ] independently with probability pj
i←0 (U, ≺) ← Select-Large(U, G̃i , pi , ∆i , ≺) i←i+1 if i = q then ∆q−1 ∆ ← 1+ ǫ
⊲ Same subroutine as in Algorithm 3
2
20
return ≺
1 Theorem 3.2. With probability at least 1 − δ, Algorithm 4 returns a 1+ǫ -DD order using O 1+c n n passes and O ǫ3 log ǫδ words of memory.
1 c
Proof. Observe that the difference between Algorithms 3 and 4 is that in Algorithm 4, during one pass of the edge lists, random directed graphs from several iterations are sampled and saved. Correctness and the Number of Passes. The key idea is a coupling argument via the directed edge sampling in each iteration: even though Algorithm 4 samples multiple graphs in one pass, it can be seen as using exactly the same randomness that Algorithm 3 would have used over the corresponding iterations. Therefore, the two algorithms produce exactly the same order ≺, and the correctness follows from Theorem 3.1. As before, given that there is no bad event in the first T iterations, the algorithm must terminate and uses O( Tq ) = O( 1c ) passes. Memory. Recall that in each pass, we sample and save q directed subgraphs. Assuming that no bad event has occurred in previous passes, the maximum degree of G[U ] is at most ∆ at the beginning of the current pass. For the i-th graph, the expected number of sampled directed edges is on the order of n∆ · pi . Hence, in this pass, the expected number of sampled edges in all the q subgraphs is at most: q−1 X i=0
n∆pi ≤ O
n n1+c log ǫ3 ǫδ
12
.
To get a high probability statement for memory usage, observe that we are no worse than the situation in Theorem 3.1. First, the expected number of saved edges is larger in each pass, which means Chernoff Bound will give a smaller failure probability for each pass. Second, the number of passes are fewer, which means there are fewer terms in the union bound. In conclusion, with probability at least 1 − δ, all the required properties as stated are satisfied.
4
Approximating the k-Graphlet Distribution
1 -DD order ≺ of a graph G, one can compute an initial As stated in Section 2.2, provided a 1+ǫ distribution p and use it to sample a k-graphlet S of G with probability p(S). In this section, we complete the task of approximating the k-graphlet distribution µk = (µ1 , · · · , µmk ) of G based on this k-graphlet sampling.
4.1
Sampling with Counters
The approximation to the k-graphlet distribution is described in Algorithm 5. Using Algorithm 2, a graphlet S can be sampled with some probability p(S) computed by the initial distribution p. The original algorithm in [8] further achieves uniform sampling by accepting the sampling of S with Γ for a constant Γ smaller than every p(S). In our algorithm, we do not reject any probability p(S) sampling, but employ the technique of Horvitz–Thompson estimators. We maintain a collection of counters c1 , · · · , cmk for isomorphism classes 1, · · · , mk respectively. When we sample a graphlet S, recall that there is precisely one integer r ∈ [1, mk ] such that gr is isomorphic to S. We then 1 to cr . The graphlet distribution is then obtained by normalizing these counters. add p(S) Algorithm 5: Approximate k-Graphlet Distribution via Counters (Abstract Description) 1 Function Counter (G, ≺, k, p, T ) 2 3 4 5 6 7 8 9
c1 , · · · , cmk ← 0 for i ← 1 to T do (sequentially/in parallel) S ← SampleGraphlet (G, ≺, k, p) ⊲ Sample a k-graphlet S with probability p(S) r ← the index such that S is isomorphic to gr 1 cr ← cr + p(S) P k Ĉ ← m i=1 ci µ̂i ← ci for each 1 ≤ i ≤ mk Ĉ return µ̂1 , · · · , µ̂mk
1 -DD order ≺, Z defined in Section 2.2 is the sum of d(v|G(v))k−1 over Recall that given a 1+ǫ 1 those vertices v with Nv > 0. We will use the property that both p(S) and the number L of graphlets in G are bounded by Z.
Fact 4.1. ([8, Lemma C.1]) For each k-graphlet S, it holds that 1 ≤ (k − 1)!(1 + ǫ)k−1 Z. p(S) Lemma 4.1. It holds that L≥
Z . (k − 1)k−1 13
To prove Lemma 4.1, we need the following lemma from [12]. Fact 4.2. ([12, Lemma 24]) For every v ∈ V such that Nv > 0, we have Nv ≥
d(v|G(v))k−1 . (k − 1)k−1
Proof of Lemma 4.1. By Fact 4.2, we have L=
X
X
Nv ≥
v∈V, Nv >0
v∈V, Nv >0
Z d(v|G(v))k−1 = . k−1 (k − 1) (k − 1)k−1
We give the analysis of Algorithm 5. 1 -DD order, k and 0 < ǫ0 , δ < 1, let T be a positive integer satisfying Lemma 4.2. For any 1+ǫ
T ≥
3(k − 1)!(k − 1)k−1 (1 + ǫ)k−1 2 ln , δ ǫ20
then Algorithm 5 computes Ĉ such that
Ĉ T −L
< ǫ0 L with probability at least 1 − δ.
P 1 Proof. Let X1 , · · · , XT be the value of p(S) of each iteration. Then we have Ĉ = Ti=1 Xi . In fact, 1 X1 , · · · , XT are independent random variables such that Xi takes value p(S) with probability p(S) k−1 for each k-graphlet S in G. Each Xi is at most (k − 1)!(1 + ǫ) Z by Fact 4.1 and has expectation L. By Fact 2.2 and lemma 4.1 we have " # Ĉ ǫ20 LT Pr − L ≥ ǫ0 L ≤ 2 exp − T 3(k − 1)!(1 + ǫ)k−1 Z ǫ20 T ≤ 2 exp − 3(k − 1)!(k − 1)k−1 (1 + ǫ)k−1 = δ.
1 Theorem 4.3. For any 1+ǫ -DD order, k and 0 < α, δ < 1, let T be a positive integer satisfying
T ≥
12((k − 1)!)2 (k − 1)2k−2 (1 + ǫ)2k−2 4mk ln , α2 (1 − α)2 δ
then Algorithm 5 computes µ̂1 , · · · , µ̂mk such that with probability at least 1 − δ, |µ̂i − µi | ≤ α for each 1 ≤ i ≤ mk . Proof. We want to bound the deviation of each normalized counter µ̂i = ci /Ĉ from the true proportion µi = li /L, uniformly over all isomorphism classes i ∈ [mk ]. The main technical issue is that µ̂i is a ratio with random denominator Ĉ. To handle this cleanly, we first condition on the event that Ĉ concentrates around its mean (so the denominator is well-controlled), and then apply a concentration bound to each numerator ci . Finally we union bound over the mk classes and combine with the probability that the conditioning event holds.
14
α Assume that the condition | Ĉ T − L| < 2 L holds. Then Ĉ lies in the interval [(1 − α/2)LT, (1 + li where li is the number of k-graphlets in G which α/2)LT ]. For each 1 ≤ i ≤ mk , recall that µi = L are isomorphic to gi . We have " # " # ci ci ci li li li Pr [|µ̂i − µi | ≥ α] = Pr ≥ α ≤ Pr − − − ≥ α + Pr ≥α . L L L 1 − α2 LT 1 + α2 LT Ĉ (1)
We analyze Pr
terms of cTi :
ci
(1− α2 )LT
"
− lLi ≥ α , and the other side is similar. We rewrite the deviation in
# hc α i α li i Pr l ≥ α 1 − L ≥ α = Pr − 1 − − i L T 2 2 1 − α2 LT hc α i α i = Pr L − li − li ≥ α 1 − 2 i 2 h cT α i ≤ Pr − li ≥ (1 − α)L , T 2 where the last inequality is due to li ≤ L. SimilarlyPto the proof of Lemma 4.2, let X1 , · · · , XT be the increment of ci after each iteration, i.e., ci = Tj=1 Xj . In fact, X1 , · · · , XT are independent 1 with probability p(S) for each k-graphlet S in G random variables such that Xj takes value p(S) ci
that is isomorphic to gi , and 0 with the rest probability. Each Xi is at most (k − 1)!(1 + ǫ)k−1 Z by Fact 4.1 and has expectation li . By Fact 2.3 and lemma 4.1, hc i α T α2 (1 − α)2 L2 i Pr − li ≥ (1 − α)L ≤2 exp − T 2 2((k − 1)!(1 + ǫ)k−1 Z)2 δ T α2 (1 − α)2 . ≤ ≤2 exp − 2 2k−2 2k−2 2((k − 1)!) (1 + ǫ) (k − 1) 4mk One can argue similarly that "
# li ci δ Pr − . ≥α ≤ α L 4mk 1 + 2 LT
α Recall that the computation above is conditioned on | Ĉ T − L| < 2 L. We denote this condition by C. Applying a union bound to both sides of Equation (1) for each 1 ≤ i ≤ mk , we obtain that [ δ |µ̂i − µi | > α C ≤ . Pr 2 i∈[mk ]
Also note that
12(k − 1)!(k − 1)k−1 (1 + ǫ)k−1 4 ln , α2 δ δ ¯ which gives Pr C ≤ 2 by Lemma 4.2. Therefore, we have the upper bound for overall failure probability: [ [ Pr |µ̂i − µi | > α ≤ Pr C¯ + Pr |µ̂i − µi | > α C ≤ δ. T ≥
i∈[mk ]
i∈[mk ]
15
Now consider the number of passes of Algorithm 5. Recall that, with a memory of M words, M we can run Algorithm 5 in parallel so that it returns Θ k2 samples using O(k) passes as described O(k) 1 in Section 2.2. Therefore, by Theorem 4.3, O (k(1+ǫ)) passes are sufficient to obtain an ln δ α4 M estimated k-graphlet distribution with probability at least 1 − δ in which each probability in the distribution differs at most α from the standard one.
4.2
Counters vs. Rejection: a Variance View
As mentioned before, the algorithm originally described in [8] uses rejection in the sense that Γ it accepts the sampling of S with probability p(S) where Γ ≤ minS p(S). One can transform this algorithm into an approximation of the k-graphlet distribution: set a collection of counters Γ c1 , · · · , cmk , and whenever a graphlet S is sampled and accepted with probability p(S) , add 1 to cr where gr is isomorphic to S. The pseudocode of this algorithm is shown in Algorithm 6. Algorithm 6: Approximate k-Graphlet Distribution via Rejection (Abstract Description) 1 Function Rejection (k, p, T ) 2 3 4 5 6 7 8 9
c1 , · · · , cmk ← 0 for i ← 1 to T do (sequentially/in parallel) Sample a k-graphlet S uniformly r ← the index such that S is isomorphic to gr cr ← cr + 1 P k Ĉ ← m i=1 ci ci µ̂i ← for each 1 ≤ i ≤ mk Ĉ return µ̂1 , · · · , µ̂mk
We give an intuitive explanation of why using Counter in place of Rejection can only increase the concentration of the frequency estimates. To this end, consider a modified version of Counter 1 Γ that, instead of adding p(S) to the counter of the isomorphism class of S, adds p(S) , where Γ is the same used by Rejection. Note that this modification is immaterial as far as the output is concerned: since the output estimates are always rescaled in order to sum to 1, multiplying all counters by a constant Γ does not make any difference. However, now one can see how Rejection is the randomized version of Counter. Indeed, while Rejection increases the counter of S by Γ Γ , Counter increases it deterministically by p(S) . Thus, both algorithms one with probability p(S) increase the counter by the same amount in expectation, but Rejection adds the variance of a coin toss. This implies Counter can only yield higher concentration.
4.3
The Complete Algorithm
Algorithm 7 gives the complete pseudocode for approximating the k-graphlet distribution. It first 1 -DD ordering with probability at least calls Algorithm 4 to compute a vertex ordering that is a 1+ǫ 1 − δ. Then it calls Algorithm 1 to obtain the initial distribution (see Section 2.2 for the definition). Finally, it calls Algorithm 5 to estimate the k-graphlet distribution. By combining Theorems 3.2 and 4.3, one can easily verify that Algorithm 7 satisfies Theorem 1.1.
16
Algorithm 7: Approximate k-Graphlet Distribution Input: an undirected graph G, the size of graphlets k, parameters ǫ, δ, c, T Output: the estimated k-graphlet distribution µ̂1 , · · · , µ̂mk 1 ≺← ApproxDD-ES (G, ǫ, δ, c) 2 p ← InitDistrib (G, ≺) 3 µ̂1 , · · · , µ̂mk ← Counter (G, ≺, k, p, T ) 4 return µ̂1 , · · · , µ̂mk
5
Experiments
We conducted experiments to evaluate the practical performance of our algorithm and compare it to the algorithm of [8]. Our experiments are designed to answer the following questions: (Q1) How do the preprocessing phase (computing an approximate DD order) of ApproxDD-ES and ApproxDD compare in terms of number of passes, peak memory and the quality of DD order? (Q2) How is the performance of the overall algorithm (for estimating the k-graphlet distribution to achieve a target accuracy) in terms of number of passes and overall peak memory, and how do the “counter” variants compare to the “rejection” variant? We organize the remainder of this section around these objectives: Section 5.2 addresses (Q1), and Section 5.3 addresses (Q2). All algorithms were implemented in C++ (including our re-implementation of the baselines from [8] for a fair comparison) and experiments were run on an Ubuntu server equipped with an Intel Xeon Silver 4108 CPU (1.80GHz) and 28GB of main memory. 3
5.1
Datasets
The computation of the graphlet distribution is relevant not only for sparse graphs, which are common in real-world data, but also for dense graphs such as the similarity graph among facial images. Our theoretical guarantee in Theorem 1.1 holds regardless of graph density. Therefore, we ran experiments on both sparse and dense graphs from various sources to show that our algorithm scales well in both cases. Table 1 reports all dataset statistics. The datasets were prepared as follows: • NY Times, Twitter(WWW), Twitter(MPI) and Friendster are from the KONECT website [29]4 . We removed edge directions, weights, self-loops, duplicate edges and any other irrelevant data, so as to retain only a list of undirected edges. • Sim-0 through Sim-7 are constructed from the database CelebA5 , which consists of 202599 human face images, each one tagged with 40 binary attributes. We represent each image by a vertex, and add an edge between two vertices if the corresponding images differ in at most 0, . . . , 7 attributes. 3
Our implementation is available at: https://github.com/l2l7l9p/GD-Streaming. http://konect.cc/networks/ 5 https://mmlab.ie.cuhk.edu.hk/projects/CelebA.html
4
17
Table 1: Dataset statistics. The first 4 graphs are real-world large graphs. Sim-* are the graphs indicating the similarity among images. ER-* are synthetic random graphs. Dataset NY Times [29] Twitter(WWW) [30] Twitter(MPI) [17] Friendster [29] Sim-0 Sim-1 Sim-2 Sim-3 Sim-4 Sim-5 Sim-6 Sim-7 ER-0 ER-1 ER-2 ER-3 ER-4 ER-5 ER-6
|V | 401,388 41,652,230 52,579,682 68,349,466 202,599 ” ” ” ” ” ” ” 202,599 ” ” ” ” ” ”
|E| 69,654,798 1,202,513,046 1,614,106,187 1,811,849,342 948,690 9,825,190 51,840,951 185,601,680 507,709,457 1,134,892,538 2,165,414,225 3,637,218,904 949,312 9,821,921 51,843,003 185,602,510 507,715,524 1,134,903,860 2,165,448,192
|E|/|V | 173.53 28.87 30.70 26.51 4.68 48.50 255.88 916.10 2505.98 5601.67 10688.18 17592.80 4.69 48.48 255.89 916.11 2506.01 5601.72 10688.35
• ER-0 through ER-6 are synthetic graphs, on the same number of vertices as Sim-*. Let ni and mi be the number of vertices and the number of edges of Sim-i respectively. Each ER-i is generated according to the Erdős-Rényi model by drawing each edge independently with i probability ni (nm so that the expected density of ER-i is consistent with Sim-i. i −1)/2 This section gives plots for a representative subset of datasets; the remaining ones are similar and are available in Section A.
5.2
Computing the DD Order
Setup. We evaluate ApproxDD-ES (our algorithm) and ApproxDD (the competitor from [8]) 1 for computing a 1+ǫ -DD order, fixing ǫ = 0.1. To test the passes-vs-memory tradeoff predicted by Theorem 1.1, we varied c ∈ [0, 0.5] (the performance of ApproxDD does not depend on c and is therefore constant across the single plot). Each point shown in Figure 4 is the average of 5 executions; executions were terminated after 36 hours if still running.
18
12000
25
0.5
0.0
0.1
0.2
0.3
(a) NY Times 0
10000
0
20
000
15
000
10
4000 #Pass(ApproxDD-ES) #Pass(ApproxDD) Mem(ApproxDD-ES) Mem(ApproxDD)
5
0.0
0.1
0.2
0.3
0.4
0.5
0
30
20
0.0
0.1
0.2
10
0
0
0.0
0.1
0.2
0.3
0.4
0.5
3200
0.4
0.5
0
0
3400
0
3300
0 50
30
100
20
50
10
0
0
0.0
0.1
10
0.0
0.1
0.2
40
Num of Passes
0
100
0.3
(f) Sim-2
0.2
0.3
0.4
0.5
0.4
0
0.5
100 #Pass(ApproxDD-ES) #Pass(ApproxDD) Mem(ApproxDD-ES) Mem(ApproxDD)
3200
0 0
200 40 100
0
20
0.0
0.1
0.2
0.3
0.4
0.5
0
c
(i) Sim-5 10
200
#Pass(ApproxDD-ES) Mem(ApproxDD-ES)
14
15
Memory (MB)
0
Memory (MB)
Memory (MB)
Num of Passes
0
40
250
50
200
150 125
150
100
5
100
140 12 120 10 100
#Pass(ApproxDD-ES) #Pass(ApproxDD) Mem(ApproxDD-ES) Mem(ApproxDD)
0 0
50
4
40
25
2
20
0
0
50 20
0.3
0.4
0.5
0.3
0.4
0.5
0.0
0.1
0.2
0.3
(j) Sim-6
(k) Sim-7
(l) ER-0
150 20
100
10
50
0.2
0.3
0.4
0.5
0
0.4
0.5
0
350
250
30
0.1
0.2
c
200
0.0
0.1
c
#Pass(ApproxDD-ES) #Pass(ApproxDD) Mem(ApproxDD-ES) Mem(ApproxDD)
40
0.0
c
300
1500
250
#Pass(ApproxDD-ES) #Pass(ApproxDD) Mem(ApproxDD-ES) Mem(ApproxDD)
1450 1400
200
0
150
40
100
20
50
0
0
0.0
0.1
0.2
0.3
2400
0.4
0.5
300 #Pass(ApproxDD-ES) #Pass(ApproxDD) Mem(ApproxDD-ES) Mem(ApproxDD)
2300
250 200
0
150
40
100
20
50
0
0.0
0.1
0.2
0.3
c
c
c
(m) ER-1
(n) ER-2
(o) ER-3
0.4
0.5
Memory (MB)
0.2
0
Num of Passes
0.1
0
Memory (MB)
0.0
50
Num of Passes
20
(e) Sim-1
120 100
0
20
(h) Sim-4 140
150
0
30
40
10
150
(g) Sim-3 200
50
0
c
#Pass(ApproxDD-ES) Mem(ApproxDD-ES)
0
40
c
c
Num of Passes
0.3
#Pass(ApproxDD-ES) #Pass(ApproxDD) Mem(ApproxDD-ES) Mem(ApproxDD)
3300
Num of Passes
50
Memory (MB)
Num of Passes
20
100
0.5
0
c
3400
30
0.4
100 40
3500
50
150
0.3
#Pass(ApproxDD-ES) #Pass(ApproxDD) Mem(ApproxDD-ES) Mem(ApproxDD)
120 50
30
0
40
0.2
20
0
5
0.1
(c) Twitter(MPI)
#Pass(ApproxDD-ES) #Pass(ApproxDD) Mem(ApproxDD-ES) Mem(ApproxDD)
(d) Friendster
00
0.0
2000
(b) Twitter(WWW)
c
#Pass(ApproxDD-ES) #Pass(ApproxDD) Mem(ApproxDD-ES) Mem(ApproxDD)
4000 #Pass(ApproxDD-ES) #Pass(ApproxDD) Mem(ApproxDD-ES) Mem(ApproxDD)
c
40
10
25
10
0
50
2000
50
0
Memory (MB)
0
Num of Passes
25
12000
Memory (MB)
Num of Passes
30
0.5
000
c
0
35
0.4
15
Memory (MB)
0.4
c
000
Memory (MB)
0.3
0
20
5
Memory (MB)
0.2
0
2000
#Pass(ApproxDD-ES) #Pass(ApproxDD) Mem(ApproxDD-ES) Mem(ApproxDD)
5
Memory (MB)
0.1
10
Memory (MB)
0.0
4000
Num of Passes
0
15
Num of Passes
10
#Pass(ApproxDD-ES) #Pass(ApproxDD) Mem(ApproxDD-ES) Mem(ApproxDD)
000
10000
Num of Passes
5
20
Num of Passes
20
10
Num of Passes
30
15
Memory (MB)
Num of Passes
000
40
20
25
Memory (MB)
25
0
Figure 4: Number of passes and peak memory usage, as a function of c, for ApproxDD and ApproxDD-ES. Each point shown is the average of 5 executions. Missing points for ApproxDD mean it did not terminate within 36 hours. 19
50
200 150
40
100
20
50
0
0
0.0
0.1
0.2
0.3
0.4
0.5
3400
250 200 150
40 100
250 30 200 150
20
100 10
20 0
300
Memory (MB)
250
Memory (MB)
200
300 #Pass(ApproxDD-ES) #Pass(ApproxDD) Mem(ApproxDD-ES) Mem(ApproxDD)
3500
350
40
Num of Passes
300
300 #Pass(ApproxDD-ES) #Pass(ApproxDD) Mem(ApproxDD-ES) Mem(ApproxDD)
3000
#Pass(ApproxDD-ES) Mem(ApproxDD-ES)
350
Memory (MB)
3100
Num of Passes
3 00
350
Num of Passes
3200
50
50
0.0
0.1
0.2
0.3
0.4
0.5
0
0
0.0
0.1
0.2
0.3
c
c
c
(p) ER-4
(q) ER-5
(r) ER-6
0.4
0.5
0
Figure 4: (Continued) Number of passes and peak memory usage, as a function of c, for ApproxDD and ApproxDD-ES. Each point shown is the average of 5 executions. Missing points for ApproxDD mean it did not terminate within 36 hours. For both algorithms we implemented the heuristic in [8, Appendix E], so as to improve the running time on large sparse graphs. Roughly speaking, at the beginning of each iteration, the heuristic sorts the vertices in nonincreasing order of degree and selects the largest prefix whose induced graph fits in memory. It then compares (i) running the next iteration of the peeling procedure (i.e., the while-loop in Algorithm 4) on this induced subgraph versus (ii) removing vertices in the prefix optimally, and keeps the option that leads to the largest drop in the current maximum degree. We additionally evaluate the quality of the DD order produced by ApproxDD-ES under different choices of c. Given a graph G = (V, E) and a vertex order ≺, for each vertex v such that d(v|G(v)) > 0, define d(v|G(v)) ϑv := . ∆(G(v)) By definition, minv∈V : d(v|G(v))>0 ϑv is exactly the largest value ϑ for which ≺ is a ϑ-DD order. To compute ϑv efficiently, write ≺ as u1 , . . . , un and index each edge {ui , uj } (i < j) by (i, j). Using an external sorting, we process edges in reverse-lexicographic order of (i, j) while maintaining the current local degree of each vertex and the maximum local degree seen so far. Whenever all edges of G(v) have been processed for some v, we obtain ϑv = d(v|G(v))/∆(G(v)). For readability we 1 report ǫv := ϑ−1 v − 1, i.e., ≺ is a 1+maxv∈V : d(v|G(v))>0 ǫv -DD order. For each graph, we compute the empirical distribution of ǫv and take the average of 5 executions. Passes–Memory Tradeoff. Figure 4 shows the passes–memory tradeoff of ApproxDD-ES and compares it to ApproxDD (which is insensitive to c). Two remarks are in order. The first one is that the results agree with Theorem 3.2: ApproxDD-ES exhibits a clear memory-passes tradeoff, and the number of passes is very stable across different datasets (e.g., at most 25 for c = 0.1) in agreement with the O(1/c) bound. In contrast, the number of passes used by ApproxDD goes with log n, and therefore explodes on large datasets. The second remark is that ApproxDD-ES outperforms ApproxDD. On most datasets, for c = 0.1, ApproxDD-ES uses at least 32% fewer passes than ApproxDD by using at most 45% more memory. The advantage of ApproxDD-ES is amplified on relatively dense graphs. On the Similarity and ER families (see Figures 4e to 4r and Figure 5), increasing density causes ApproxDD to require dramatically more passes (and to fail to terminate within 36 hours on Sim-6 and Sim7), whereas ApproxDD-ES remains within a small constant number of passes for c = 0.1. For example, on Sim-3 and Sim-5, ApproxDD-ES for c = 0.1 uses marginally more memory than ApproxDD, and yet it makes 20× and 110× fewer passes.
20
3000
#Pass(ApproxDD-ES) #Pass(ApproxDD)
3000
2000
#Pass(ApproxDD-ES) #Pass(ApproxDD)
2000
1000
Num of Passes
Num of Passes
1000
100
50
0
S m-0
S m-1
S m-2
S m-3
S m-4
S m-5
40
20
0
E -0
E -1
E -2
E -3
E -4
E -5
Figure 5: Number of passes on graphs of increasing densities using ApproxDD and ApproxDD-ES, when c = 0.1. 1 Finally, Table 2 reports the memory used for computing a 1+ǫ -DD order on all datasets when c = 0.1. Across datasets, ApproxDD-ES uses moderately more memory than ApproxDD, matching the tradeoff suggested by Theorem 1.1. 1 -DD order, Table 2: Memory used (in MB) by ApproxDD and ApproxDD-ES to compute a 1+ǫ with ǫ = c = 0.1. The memory is expressed both in megabytes and (bracketed) as a fraction of the dataset size on disk (which uses 8 bytes per edge).
Dataset NY Times Twitter(WWW) Twitter(MPI) Friendster Sim-0 Sim-1 Sim-2 Sim-3 Sim-4 Sim-5 Sim-6 Sim-7 ER-0 ER-1 ER-2 ER-3 ER-4 ER-5 ER-6
ApproxDD
ApproxDD-ES
34.96 (6.58%) 2432.10 (26.51%) 2904.21 (23.58%) 3832.49 (27.72%) 17.10 (236.26%) 17.37 (23.17%) 20.64 (5.22%) 16.42 (1.16%) 19.14 (0.49%) 15.86 (0.18%) 9.31 (128.54%) 16.98 (22.66%) 16.29 (4.12%) 17.43 (1.23%) 17.96 (0.46%) 21.16 (0.24%) -
38.38 (7.22%) 3177.75 (34.64%) 3735.16 (30.33%) 5568.79 (40.29%) 9.87 (136.36%) 17.44 (23.27%) 17.71 (4.48%) 17.77 (1.26%) 18.10 (0.47%) 18.01 (0.21%) 17.84 (0.11%) 19.15 (0.07%) 7.76 (107.14%) 19.14 (25.54%) 19.07 (4.82%) 20.66 (1.46%) 21.03 (0.54%) 20.86 (0.24%) 21.00 (0.13%)
DD Order Quality. Figure 6 shows the empirical distribution of ǫv . On large sparse graphs (NY Times, Twitter(WWW), Friendster), ApproxDD-ES typically outputs orders that are extremely close to a perfect DD order: for small and moderate c, the mass is concentrated in the smallest ǫ bin (near 0). On dense graphs (ER and Sim), the distribution remains tightly concentrated on small ǫ (e.g., mostly ǫ ≤ 0.4 for ER and mostly ǫ ≤ 4 for Sim). Overall, these results suggest that ApproxDD-ES produces high-quality DD orders in practice. 21
)*0.01 )*0.05 )*0.1
1.0
$
0.
)*0.2 )*0.3 )*0.4
)*0.5
re ue
re ue
2 1
0.2
0.4
0 0.004)
0.004 0.00! 0.01 0.04 0.0! 0.00!) 0.01) 0.04) 0.0! ) 0.1)
0.1
0.4)
"
0.4 0.! )
0.! 1)
1
4)
4 !)
!
10)
10 100)
0.0
100 1000)
+,
0 0.004)
+0.004, +0.00-, +0.01, +0.04, +0.0-, +0.1, 0.00-) 0.01) 0.04) 0.0- ) 0.1) 0.4)
(a) NY Times <
AB0.2 AB0.3 AB0.4
AB0.5
+0.4, 0.-)
+0.-, 1)
+ 1, 4)
+ 4, -)
MN0.01 MN0.05 MN0.1
1.0
ApproxDD
H
0.
+-,
+ ,
10 100)
10)
+
,
100 1000)
MN0.2 MN0.3 MN0.4
MN0.5 ApproxDD
L 0.G
y
y
K
;
0.
re ue
re ue
=
.
(b) Twitter(WWW) AB0.01 AB0.05 AB0.1
0.
>
ApproxDD
0.2
1.0
@?
560.5
3 0./
0.4
0.0
560.2 560.3 560.4
y
y
4
' 0.# %
0
0.
( &
560.01 560.05 560.1
1.0
ApproxDD
J 0.4
0.4
I
0.2
0.2 0.0
78
0 0.004)
70.0048 70.0098 70.018 70.048 70.098 70.18 0.009) 0.01) 0.04) 0.09 ) 0.1) 0.4)
:
70.48 0.9 )
70.98 1)
718 4)
748 9)
798
10)
7 8
10 100)
7
0.0
8
100 1000)
CD
0 0.004)
C0.004D C0.00ED C0.01D C0.04D C0.0ED C0.1D 0.00E) 0.01) 0.04) 0.0E ) 0.1) 0.4)
(c) Twitter(MPI)
F
C0.4D 0.E)
C0.ED 1)
C 1D 4)
C 4D E)
CED
C D
10 100)
10)
C
D
100 1000)
(d) Friendster YZ0.01 YZ0.05 YZ0.1
T
0.
YZ0.2 YZ0.3 YZ0.4
YZ0.5
de0.2 de0.3 de0.4
de0.5
ApproxDD
y
y re ue
cb 0.5
re ue
XW 0.S
de0.01 de0.05 de0.1
] 0._ 0.
ApproxDD
V 0.4
0.4
a 0.3
U
`
0.2
0.2
0.1 0.0
O0P
O0.004P O0.00QP O0.01P O0.04P O0.0QP O0.1P 0.004) 0.00Q) 0.01) 0.04) 0.0Q ) 0.1) 0.4)
R
O0.4P 0.Q )
O0.QP 1)
O1P 4)
O4P Q)
OQP
10)
O10P
100)
0.0
O100P
1000)
[\
0 0.004)
[0.004\ [0.00]\ [0.01\ [0.04\ [0.0]\ [0.1\ 0.00]) 0.01) 0.04) 0.0] ) 0.1) 0.4)
(e) Sim-1 h 0.j 0.
0.5
op0.2 op0.3 op0.4
ApproxDD
z{0.01 z{0.05 z{0.1
i
f0.4g 0.h )
f0.hg 1)
f1g 4)
f4g h)
fhg
10)
f10g
100)
0.0
f100g
1000)
0.5
0.2 0.3 0.4
z{0.2 z{0.3
q 4r s)
10)
\
q
r
z{0.4 z{0.5
qr
0 0.004)
q0.004r q0.00sr q0.01r q0.04r q0.0sr q0.1r 0.00s) 0.01) 0.04) 0.0s ) 0.1) 0.4)
t
q0.4r 0.s)
1)
4)
0.
re ue
re ue
y
0.3
0.2
0.01 0.05 0.1
0.
0.5 ApproxDD
0.4
y
q 1r
[
100 1000)
qsr
q r
10 100)
100 1000)
(h) Sim-7 0.01 0.05 0.1
0.2 0.3 0.4
0.5 ApproxDD
0.5 0.4 0.3 0.2
0.1
0.1
|}
0 0.004)
|0.004} |0.00~} |0.01} |0.04} |0.0~} |0.1} 0.00~) 0.01) 0.04) 0.0~ ) 0.1) 0.4)
|0.4} 0.~ )
|0.~} 1)
|1} 4)
|4} ~)
|~}
10)
| }
10 100)
|
0.0
}
100 1000)
0 0.004)
(i) ER-1
0.004 0.00 0.01 0.04 0.0 0.1 0.00) 0.01) 0.04) 0.0 ) 0.1) 0.4)
0.4 0.)
0. 1)
1 4)
4 )
10 100)
10)
100 1000)
(j) ER-2 0.01 0.05 0.1
0. 0.
0.2 0.3 0.4
0.5
¥¦0.01 ¥¦0.05 ¥¦0.1
0.5
ApproxDD
0.4
¥¦0.2 ¥¦0.3
¥¦0.4 ¥¦0.5
y
£¤ 0.3
0.5
re ue
y
q0.sr
[ \
10 100)
0.1
f0.004g f0.00hg f0.01g f0.04g f0.0hg f0.1g 0.004) 0.00h) 0.01) 0.04) 0.0h ) 0.1) 0.4) f0g
0.
re ue
[]\
0.5
(g) Sim-5
10)
re ue
re ue
0.1
[ 4\ ])
4)
v 0.2
k 0.2
[ 1\
1)
w 0.3
l 0.3
0.0
[0.]\
xy 0.4
m 0.4
0.0
[0.4\ 0.])
(f) Sim-3 s 0.u 0.
op0.5 y
y
n
op0.01 op0.05 op0.1
^
0.4
¢
0.3
¡
0.2
0.2 0.1
0.1 0.0
0
0.004 0.00 0.01 0.04 0.0 0.1 0.004) 0.00) 0.01) 0.04) 0.0 ) 0.1) 0.4)
0.4 0. )
0. 1)
1 4)
4 )
10)
10
100)
0.0
100
1000)
0 0.004)
(k) ER-4
0.004 0.00 0.01 0.04 0.0 0.1 0.00) 0.01) 0.04) 0.0 ) 0.1) 0.4)
0.4 0.)
0. 1)
1 4)
4 )
10)
10 100)
100 1000)
(l) ER-6
Figure 6: Empirical distribution of ǫv under different c, using ApproxDD-ES.
5.3
Computing the Graphlet Distribution
We test the performance of our full algorithm for approximating the k-graphlet distribution, ApproxDD-ES +Counter (Algorithm 7), and of its competitor ApproxDD +Counter (the algorithm of [8]). 22
Note that the algorithm originally described in [8] actually uses rejection, rather than using counters. We also test this “default” competitor, ApproxDD +Rejection, where Rejection is introduced in Algorithm 6. As expected, ApproxDD +Rejection is much more inefficient than the “counter” variants, as it gains information only upon accepting a graphlet, which happens with probability only k−O(k) . We ran the algorithms for k = 4, 5, 6, using as ground truth the average of 5 runs of Motivo [15]. We set the parameters of our algorithms to ǫ = 0.1, c = 0.1, and δ = 0.02. For each algorithm and 1 -DD order. We then ran 5 batches of parallel sampling. each dataset, we start by computing a 1+ǫ After each batch, we computed the L∞ distance between (i) the ground truth and (ii) the k-graphlet distribution estimate obtained so far. This experiment was then repeated 5 times, and we took the average. Accuracy versus passes. Figure 7 shows the number of passes versus L∞ distance achieved by the algorithms. (Due to space limitations we show the plots only for a representative subset of datasets). Note that the number of passes is the sum of the passes taken by preprocessing and of 2k − 1 passes for each sampling batch. The first observation is that, on every dataset and for every value of k, save a few exceptions at k = 4, ApproxDD-ES +Counter and ApproxDD +Counter yield an error smaller than ApproxDD +Rejection. The gap between the two errors increases with k, with ApproxDD +Rejection lagging much behind ApproxDD-ES +Counter and ApproxDD +Counter for k = 6. This is explained by the aforementioned k−O(k) acceptance probability of ApproxDD +Rejection, and confirms that the “counter” approach is significantly better than the “rejection” approach. The second observation is that, again, ApproxDD-ES +Counter uses fewer passes than ApproxDD +Counter, outperforming it by orders of magnitude on dense graphs. Note that the sampling phase is identical between the two algorithms (but is ran with different DD-orders), and seems to have a relatively small impact on the error-vs-passes tradeoff, if compared with the preprocessing phase. This is coherent with the results of Section 5.2 and with our theoretical bounds. Overall, ApproxDD-ES +Counter ensures an L∞ error of at most 0.01 with < 50 passes for k = 4, of at most 0.02 with < 60 passes for k = 5, and at most 0.05 with < 80 passes for k = 6. Memory usage. Table 3 shows the memory usage of all algorithms. In fact, in all our experiments, the total memory usage of ApproxDD-ES +Counter and ApproxDD +(Rejection or Counter) was dominated by the memory required for the preprocessing (which is already shown graphically in Section 5.2). Again, the memory usage of ApproxDD-ES +Counter is slightly worse than ApproxDD +Rejection and ApproxDD +Counter, but not by large factors. This confirms that ApproxDD-ES +Counter is competitive.
6
Conclusion
This paper presents a novel streaming algorithm for approximating k-graphlet distributions in large graphs that cannot fit entirely in memory. By introducing an improved method for computing an approximate degree-dominating (DD) order—a key preprocessing step—our algorithm reduces the number of passes from O(log n) (as in prior work) to O(1/c), using Õ(n1+c ) memory. This result is nearly optimal, as a lower bound rules out O(1)-pass algorithms with sublinear memory. Empirical evaluations on real-world and synthetic graphs demonstrate that our algorithm significantly outperforms the state-of-the-art, especially on moderately dense graphs, where it reduces the number of passes by orders of magnitude while maintaining comparable memory usage. The integration of a Horvitz–Thompson estimator further enhances efficiency by avoiding the high rejection rates of earlier sampling methods. 23
ApproxDDª«eje¬ion ApproxDDª®ouner ApproxDD-ESª®ouner
0.010 0.00© 0.00§ 0.004
0.·
0.0°
ApproxDD²³eje´µion ApproxDD²¶ounµer ApproxDD-ES²¶ ounµer
0.04
0.5
0.02 0.002 0.000
25 22 0 Num of Passes ( ef
0.00
15 30 45 §0 ¨5 Prepro essing igh Sampling)
¸¹ º» ¸¼ » ¸¼ »
ApproxDD eje ion ApproxDD oun er ApproxDD-ES oun er
0.0± A erage Max Error
A erage Max Error
0.012
A erage Max Error
0.014
25 22 0 1¯ 34 51 °± ±5 Num of Passes ( ef Prepro essing igh Sampling)
(a) NY Times, k = 4
0.015 0.010 0.005 0.000
25 22
(b) NY Times, k = 5
1½ 3¾ 5¿ Num of Passes
0
0.0003 0.0002
0.0000
Â0
Ã5 Sampling)
1Ë 34 51 Prepro essing igh
ÌÉ
É5 Sampling)
0.00012 0.00010 0.0000Ý 0.0000Û 0.00004
0.000å
0.0004
0.0000
Û0
Ü5 Sampling)
(g) Twitter(MPI), k = 4
2â 20 0 Num of Passes ( eft
1ã 34 51 äå å5 Prepro essing ight Sampling)
0.0003 0.0002
0.0025
ApproxDDýþejeÿtion ApproxDDý ounter ApproxDD-ESý ounter
0.0020 0.0015
0.0005
0.0000
0.0000
ó0
ô5 Sampling)
34 1ù 0 Num of Passes ( eft
(j) Friendster, k = 4
0.015
0.010
ûü
ü5 Sampling)
î5
0.002 0.001 0.000
1
34
0
1 3 5 Num of Passes
5
(l) Friendster, k = 6
0.10 0.0 0.0
!
ApproxDD eje tion ApproxDD ounter ApproxDD-ES ounter
0.
!
0.
0.4
0.2
0.02
ApproxDD eje tion ApproxDD ounter ApproxDD-ES ounter
0 15 Sampling)
ðñ
0.003
ApproxDD eje tion ApproxDD ounter ApproxDD-ES ounter
0.04
2 ight
1î 3ï 5ð Num of Passes
A erage Max Error
0.020
A erage Max Error
A erage Max Error
1ú 34 51 Prepro essing ight
0.12
1 Prepro essing
0
ApproxDD eje tion ApproxDD ounter ApproxDD-ES ounter
(k) Friendster, k = 5
0.025
0.000
2î 20
(i) Twitter(MPI), k = 6
0.0010
Num of Passes ( eft
0.0000
0.0030
0.0001
0.005
0.0001
0.015
0.0004
15 30 45 Prepro essing ight
Ø5
êë ì êí êí
0.0035
0.0005
34 1ò 0 Num of Passes ( eft
ÙÒ
ApproxDD eje tion ApproxDD ounter ApproxDD-ES ounter
0.020
0.0040
A erage Max Error
0.000ó
1Ø 3Ó 5Ù Num of Passes
0.0002
(h) Twitter(MPI), k = 5
ApproxDDõöeje÷tion ApproxDDõøounter ApproxDD-ESõøounter
0.000ô
0
0.002
0.000ä
A erage Max Error
15 30 45 Prepro essing ight
2Ó 1Ø
0.003
0.0002
2Ú 20 0 Num of Passes ( eft
0.0000
0.004
0.00002 0.00000
0.0001
(f) Twitter(WWW), k = 6
ApproxDDæçejeètion ApproxDDæéounter ApproxDD-ESæéounter
0.0010
A erage Max Error
A erage Max Error
2É 1Ê 0 Num of Passes ( ef
0.0002
(e) Twitter(WWW), k = 5
ApproxDDÞßejeàtion ApproxDDÞáounter ApproxDD-ESÞáounter
0.00014
0.000Ì
0.002
0.0002
(d) Twitter(WWW), k = 4 0.0001Û
0.000É
A erage Max Error
15 30 45 Prepro essing igh
ApproxDDÍÎejeÏÐion ApproxDDÍÑounÐer ApproxDD-ESÍÑounÐer
0.0004
ApproxDDÄÅejeÆÇion ApproxDDÄÈounÇer ApproxDD-ESÄÈounÇer
2À 1Á 0 Num of Passes ( ef
0.004
0.0010
A erage Max Error
0.0004
0.0001
A erage Max Error
ÔÕ Ö Ô× Ô×
ApproxDD eje tion ApproxDD ounter ApproxDD-ES ounter
0.00Ò
0.0012 A erage Max Error
A erage Max Error
0.0014
0.0005
0.0000
½5
(c) NY Times, k = 6 0.00Ó
0.000Â
¿·
30
(m) Sim-3, k = 4
45
0
5
0.00 Num of Passes ( eft
1 Prepro essing
2 ight
0 1 Sampling)
34
(n) Sim-3, k = 5
51
5
0.0 Num of Passes ( eft
2 1 Prepro essing ight
0 1 Sampling)
3
5
5
(o) Sim-3, k = 6
Figure 7: L∞ distance between the ground-truth and the estimated k-graphlet distribution as a function of the number of passes for sampling. The X-axis shows the number of passes (preprocessing on the left, sampling on the right). Missing points for ApproxDD mean it did not terminate within 36 hours. 24
0.040
0.025
'( ) '* '*
ApproxDD eje tion ApproxDD ounter ApproxDD-ES ounter
0.020 0.015
0.10 0.0-
A erage Max Error
0.030
A erage Max Error
A erage Max Error
#
9: ; 9< 9<
1.0
ApproxDD eje tion ApproxDD ounter ApproxDD-ES ounter
0.12
0.035
01 2 03 03
ApproxDD eje tion ApproxDD ounter ApproxDD-ES ounter
0.0,
. 0.04
7
0.6 0.5
0.4
0.010
0.000 Num of Passes ( eft
0.2
0.02
0.005 32"5 Prepro essing
2$ ight
0 15 Sampling)
30
45
0.00
%0 & 5
Num of Passes ( eft
(p) Sim-5, k = 4 0.012
32+5 Prepro essing
2ight
0 1/ Sampling)
34
51
,-
-5
0.0 Num of Passes ( eft
(q) Sim-5, k = 5
ApproxDD-ES@Aounter
3245 26 Prepro essing ight
36
0 14 Sampling)
58
85
45
(r) Sim-5, k = 6
ApproxDD-ESEFounter
ApproxDD-ESKLounter
0.0G
0.025
0.00= 0.00> 0.004
A erage Max Error
A erage Max Error
A erage Max Error
0.010 0.020
0.015
0.010
0.0J
0.04
0.02 0.005
0.002
2= 0 Num of Passes ( eft
0.000
15 30 45 >0 ?5 Prepro essing ight Sampling)
2B 0 Num of Passes ( eft
(s) Sim-7, k = 4
RS T RU RU
145M 1N Prepro essing ight
0 15 30 Sampling)
45
0.00X 0.00W
0.000
Q5
Num of Passes ( eft
(v) ER-2, k = 4 0.01h
[\ ] [^ [^ 51 WX
ApproxDD eje tion ApproxDD ounter ApproxDD-ES ounter
145V 1W 0 1Z 34 Prepro essing ight Sampling)
0.05 0.04 0.03 0.02 0.01
X5
0.00 Num of Passes ( eft
(w) ER-2, k = 5 lm n lo lo
ApproxDD eje tion ApproxDD ounter ApproxDD-ES ounter
0.014
b
0.002
N0
A erage Max Error
0.010 0.00i 0.00h
0.020 0.015
0.000
0.000
Num of Passes ( eft
3053 1h Prepro essing ight
0 15 30 Sampling)
45
h0
k5
Num of Passes ( eft
(y) ER-4, k = 4
x
51
qs
0.005 0.004 0.003
s5
Num of Passes ( eft
z5
0.030
0.0125 0.0100 0.005
0.025 0.020 0.015
0.0050
0.010
0.001
0.0025
0.005
0.000
0.0000
(ab) ER-6, k = 4
|y
ApproxDD-ESounter
0.035
0.002
1 0 15 30 45 0 5 Num of Passes ( eft Prepro essing ight Sampling)
3053 1y 0 Prepro essing ight Sampling)
(aa) ER-4, k = 6
ApproxDD-ESounter
0.0150
0.00
A erage Max Error
A erage Max Error
3053 1q 0 1r 34 Prepro essing ight Sampling)
0.015
0.00
}~ } } 1z 3{
ApproxDD eje tion ApproxDD ounter ApproxDD-ES ounter
A erage Max Error
0.00
5|
0.02
0.00
(z) ER-4, k = 5
ApproxDD-ES ounter
_5
0.03
0.01 0.005
a`
0.04
0.025
0.002
5a
0.05
p 0.010
0.004
145_ 1` 0 1_ 3c Prepro essing ight Sampling)
(x) ER-2, k = 6 tu v tw tw
ApproxDD eje tion ApproxDD ounter ApproxDD-ES ounter
0.030
0.012
ApproxDD eje tion ApproxDD ounter ApproxDD-ES ounter
0.0`
Y 0.004
ApproxDD eje tion ApproxDD ounter ApproxDD-ES ounter
de f dg dg
0.0a
A erage Max Error
A erage Max Error
A erage Max Error
0.00N
0.002
A erage Max Error
(u) Sim-7, k = 6
0.010
P 0.004
j
2G 0 1H 3G 5I IJ H5 Num of Passes ( eft Prepro essing ight Sampling)
0.012
0.00O
Num of Passes ( eft
0.00
(t) Sim-7, k = 5
0.010
0.000
1C 34 51 DB B5 Prepro essing ight Sampling)
A erage Max Error
0.000
1 0 1 34 51 5 Num of Passes ( eft Prepro essing ight Sampling)
(ac) ER-6, k = 5
0.000
1 0 1 Num of Passes ( eft
3 5 Prepro essing
ight
5 Sampling)
(ad) ER-6, k = 6
Figure 7: (Continued) L∞ distance between the ground-truth and the estimated k-graphlet distribution as a function of the number of passes for sampling. The X-axis shows the number of passes (preprocessing on the left, sampling on the right). Missing points for ApproxDD mean it did not terminate within 36 hours.
25
Table 3: Overall memory usage of the algorithms (in MB). The percentages in brackets represent the ratio of memory usage over the disk size of the graph (each edge is represented in 8 bytes). Dataset
ApproxDD-ES +Counter
ApproxDD +(Rejection or Counter)
k=4
Motivo k=5
k=6
NY Times Twitter (WWW) Twitter (MPI) Friendster Sim-0 Sim-1 Sim-2 Sim-3 Sim-4 Sim-5 Sim-6 Sim-7 ER-0 ER-1 ER-2 ER-3 ER-4 ER-5 ER-6
38.83 (7.31%) 3370.27 (36.74%) 4391.69 (35.66%) 5895.11 (42.65%) 16.50 (227.90%) 17.46 (23.29%) 18.25 (4.61%) 18.84 (1.33%) 19.16 (0.49%) 19.39 (0.22%) 19.82 (0.12%) 20.05 (0.07%) 18.22 (251.50%) 20.96 (27.97%) 20.55 (5.20%) 21.18 (1.50%) 21.05 (0.54%) 21.66 (0.25%) 21.69 (0.13%)
34.97 (6.58%) 2691.84 (29.34%) 3382.18 (27.46%) 4429.02 (32.04%) 17.98 (248.37%) 18.33 (24.45%) 19.17 (4.85%) 19.81 (1.40%) 20.16 (0.52%) 20.40 (0.24%) 17.78 (245.55%) 19.99 (26.67%) 20.40 (5.16%) 20.31 (1.43%) 20.16 (0.52%) 20.43 (0.24%) -
856.60 (161.19%) 12407.77 (135.24%) 17173.68 (139.46%) 20857.70 (150.89%) 99.21 (1370.71%) 181.23 (241.77%) 508.91 (128.67%) 1531.61 (108.16%) 3984.58 (102.87%) 8692.20 (100.39%) 17176.55 (103.97%) 28061.98 (101.13%) 125.80 (1736.88%) 194.11 (259.04%) 511.20 (129.24%) 1531.78 (108.17%) 3985.01 (102.88%) 8692.22 (100.39%) 16902.60 (102.31%)
913.18 (171.84%) 16687.46 (181.89%) 24232.61 (196.78%) 26691.57 (193.09%) 122.89 (1697.89%) 260.64 (347.71%) 611.73 (154.67%) 1638.01 (115.68%) 4097.13 (105.77%) 8766.39 (101.25%) 17297.12 (104.70%) 28112.06 (101.31%) 214.46 (2961.11%) 298.66 (398.56%) 618.41 (156.35%) 1638.54 (115.71%) 4101.33 (105.88%) 8801.50 (101.65%) 16999.68 (102.90%)
1115.45 (209.90%) 32576.35 (355.08%) 48619.79 (394.81%) 45527.43 (329.35%) 192.33 (2657.24%) 513.17 (684.59%) 932.91 (235.87%) 1978.04 (139.69%) 4440.09 (114.63%) 9158.10 (105.77%) 17656.74 (106.88%) 28305.63 (102.00%) 504.20 (6961.54%) 643.80 (859.14%) 964.53 (243.86%) 1982.57 (140.01%) 4441.28 (114.66%) 9193.64 (106.18%) 17619.79 (106.65%)
Overall, our work provides a scalable, predictable, and theoretically sound solution for graphlet analysis in the streaming model, bridging the gap between theoretical guarantees and practical performance.
References [1] Matteo Agostini, Marco Bressan, and Shahrzad Haddadan. Mixing time bounds for graphlet random walks. Information Processing Letters, 152:105851, 2019. [2] Nesreen K. Ahmed, Nick G. Duffield, Jennifer Neville, and Ramana Rao Kompella. Graph sample and hold: a framework for big-graph analytics. In KDD, pages 1446–1455. ACM, 2014. [3] Bahman Bahmani, Ravi Kumar, and Sergei Vassilvitskii. Densest subgraph in streaming and MapReduce. Proceedings of the VLDB Endowment, 5(5):454–465, January 2012. [4] Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In SODA, pages 623–632. ACM/SIAM, 2002. [5] Luca Becchetti, Paolo Boldi, Carlos Castillo, and Aristides Gionis. Efficient semi-streaming algorithms for local triangle counting in massive graphs. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 16–24, Las Vegas Nevada USA, August 2008. ACM. [6] Suman K. Bera, Lior Gishboliner, Yevgeny Levanzov, C. Seshadhri, and Asaf Shapira. Counting subgraphs in degenerate graphs. J. ACM, 69(3):23:1–23:21, 2022. [7] Mansurul A. Bhuiyan, Mahmudur Rahman, Mahmuda Rahman, and Mohammad Al Hasan. Guise: Uniform sampling of graphlets for large graph analysis. In Proc. of IEEE ICDM 2012, pages 91–100, 2012.
26
[8] Yann Bourreau, Marco Bressan, T.-H. Hubert Chan, Qipeng Kuang, and Mauro Sozio. Efficient streaming algorithms for graphlet sampling. In NeurIPS, 2024. [9] Marco Bressan. Efficient and near-optimal algorithms for sampling connected subgraphs. In Proc. of ACM STOC, page 1132–1143, 2021. [10] Marco Bressan. Efficient and near-optimal algorithms for sampling connected subgraphs, 2021. [11] Marco Bressan. Faster algorithms for counting subgraphs in sparse graphs. Algorithmica, 2021. [12] Marco Bressan. Efficient and near-optimal algorithms for sampling small connected subgraphs. ACM Trans. Algorithms, 19(3), jun 2023. [13] Marco Bressan, Flavio Chierichetti, Ravi Kumar, Stefano Leucci, and Alessandro Panconesi. Counting graphlets: Space vs time. In Proc. of ACM WSDM, pages 557–566, 2017. [14] Marco Bressan, Flavio Chierichetti, Ravi Kumar, Stefano Leucci, and Alessandro Panconesi. Motif counting beyond five nodes. ACM Trans. Knowl. Discov. Data, 12(4), April 2018. [15] Marco Bressan, Stefano Leucci, and Alessandro Panconesi. Motivo: Fast motif counting via succinct color coding and adaptive sampling. Proc. VLDB Endow., 12(11):1651–1663, July 2019. [16] Marco Bressan, Stefano Leucci, and Alessandro Panconesi. Faster motif counting via succinct color coding and adaptive sampling. ACM Trans. Knowl. Discov. Data, 15(6), May 2021. [17] Meeyoung Cha, Hamed Haddadi, Fabrı́cio Benevenuto, and P. Krishna Gummadi. Measuring user influence in twitter: The million follower fallacy. In ICWSM. The AAAI Press, 2010. [18] Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia. Strong computational lower bounds via parameterized complexity. Journal of Computer and System Sciences, 72(8):1346 – 1367, 2006. [19] Xiaowei Chen, Yongkun Li, Pinghui Wang, and John C. S. Lui. A general framework for estimating graphlet statistics via random walk. Proc. VLDB Endow., 10(3):253–264, November 2016. [20] Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM J. Comput., 14(1):210–223, 1985. [21] Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in a semi-streaming model. Theoretical Computer Science, 348(2-3):207–216, December 2005. [22] Mohsen Ghaffari, Silvio Lattanzi, and Slobodan Mitrovic. Improved parallel algorithms for density-based network clustering. In ICML, volume 97 of Proceedings of Machine Learning Research, pages 2201–2210. PMLR, 2019. [23] Avishek Ghosh, Jichan Chung, Dong Yin, and Kannan Ramchandran. An efficient framework for clustered federated learning. IEEE Trans. Inf. Theory, 68(12):8076–8091, 2022. [24] Guyue Han and Harish Sethu. Waddling random walk: Fast and accurate mining of motif statistics in large graphs. In Proc. of IEEE ICDM, pages 181–190, 2016. 27
[25] Daniel G Horvitz and Donovan J Thompson. A generalization of sampling without replacement from a finite universe. Journal of the American statistical Association, 47(260):663–685, 1952. [26] Mark Jerrum and Kitty Meeks. The parameterised complexity of counting connected subgraphs and graph motifs. J. Comput. Syst. Sci., 81(4):702–716, 2015. [27] Madhav Jha, C. Seshadhri, and Ali Pinar. A space-efficient streaming algorithm for estimating transitivity and triangle counts using the birthday paradox. ACM Trans. Knowl. Discov. Data, 9(3):15:1–15:21, 2015. [28] Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, and He Sun. Counting arbitrary subgraphs in data streams. In ICALP (2), volume 7392 of Lecture Notes in Computer Science, pages 598–609. Springer, 2012. [29] Jérôme Kunegis. KONECT: the koblenz network collection. In WWW (Companion Volume), pages 1343–1350. International World Wide Web Conferences Steering Committee / ACM, 2013. [30] Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue B. Moon. What is twitter, a social network or a news media? In WWW, pages 591–600. ACM, 2010. [31] Yongsub Lim, Minsoo Jung, and U. Kang. Memory-Efficient and Accurate Sampling for Counting Local Triangles in Graph Streams: From Simple to Multigraphs. ACM Transactions on Knowledge Discovery from Data, 12(1):1–28, February 2018. [32] Ryuta Matsuno and Aristides Gionis. Improved mixing time for k-subgraph sampling. In Proc. of SIAM SDM, pages 568–576, 2020. [33] David W. Matula and Leland L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. J. ACM, 30(3):417–427, July 1983. [34] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. Network motifs: Simple building blocks of complex networks. Science, 298(5594):824–827, 2002. [35] Kirill Paramonov, Dmitry Shemetov, and James Sharpnack. Estimating graphlet statistics via lifting. In Proc. of ACM KDD, page 587–595, 2019. [36] A. Pavan, Kanat Tangwongsan, Srikanta Tirthapura, and Kun-Lung Wu. Counting and sampling triangles from a graph stream. Proceedings of the VLDB Endowment, 6(14):1870– 1881, September 2013. [37] Hao Peng, Jianxin Li, Qiran Gong, Yuanxin Ning, Senzhang Wang, and Lifang He. Motifmatching based subgraph-level attentional convolutional network for graph classification. Proc. of AAAI, 34(04):5387–5394, Apr. 2020. [38] Tanay Kumar Saha and Mohammad Al Hasan. Finding network motifs using mcmc sampling. In Proc. of CompleNet, pages 13–24, 2015. [39] Ahmet Erdem Sarı́yüce, Buğra Gedik, Gabriela Jacques-Silva, Kun-Lung Wu, and Ümit V. Çatalyürek. Streaming algorithms for k-core decomposition. Proceedings of the VLDB Endowment, 6(6):433–444, April 2013.
28
[40] Nino Shervashidze, S. V. N. Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten M. Borgwardt. Efficient graphlet kernels for large graph comparison. In AISTATS, volume 5 of JMLR Proceedings, pages 488–495. JMLR.org, 2009. [41] Lorenzo De Stefani, Alessandro Epasto, Matteo Riondato, and Eli Upfal. Triest: Counting local and global triangles in fully dynamic streams with fixed memory size. ACM TKDD, 11(4):43, 2017. [42] Lorenzo De Stefani, Erisa Terolli, and Eli Upfal. Tiered sampling: An efficient method for approximate counting sparse motifs in massive graph streams. In IEEE BigData, pages 776– 786. IEEE Computer Society, 2017. [43] Kun Tu, Jian Li, Don Towsley, Dave Braines, and Liam D. Turner. Gl2vec: Learning feature representation using graphlets for directed networks. In Proc. of IEEE/ACM ASONAM, page 216–221, 2019. [44] Pinghui Wang, John C. S. Lui, Bruno Ribeiro, Don Towsley, Junzhou Zhao, and Xiaohong Guan. Efficiently estimating motif statistics of large networks. ACM TKDD, 9(2):8:1–8:27, 2014.
29
A
Additional Figures
Figures 8 and 9 show the figures omitted from the experiments in Section 5. 0.01 0.05 0.1
1.0
0.
0.2 0.3 0.4
¡
0.5
¤
re uen y
re uen y
0.
0.
¢
0 0.004)
0.004 0.00 0.01 0.04 0.0 0.1 0.00) 0.01) 0.04) 0.0 ) 0.1) 0.4)
0.4 0. )
0. 1)
1 4)
4 )
10)
10 100)
0.0
100 1000)
0 0.004)
0.004 0.00 0.01 0.04 0.0 0.1 0.00) 0.01) 0.04) 0.0 ) 0.1) 0.4)
(a) Sim-0 ¯°0.01 ¯°0.05 ¯°0.1
«
0.
0.5
¯°0.2 ¯°0.3 ¯°0.4
ApproxDD
0.4 0.)
0.
1
4 )
10)
±0.³²
± 1²
± 4² ³)
10)
1)
4)
10 100)
±
²
100 1000)
(b) Sim-2
¯°0.5
¹º0.01 ¹º0.05 ¹º0.1
µ
0.
ApproxDD
0.5
¹º0.2 ¹º0.3
¹º0.4 ¹º0.5
re uen y
¸ 0.4
re uen y
® 0.4 0.3
· 0.3 ¶ 0.2
¬ 0.2
0.1
0.1
§¨
0 0.004)
§0.004¨ §0.00©¨ §0.01¨ §0.04¨ §0.0©¨ §0.1¨ 0.00©) 0.01) 0.04) 0.0© ) 0.1) 0.4)
ª
§0.4¨ 0.© )
§0.©¨ 1)
§1¨ 4)
§4¨ ©)
§©¨
10)
§ ¨
10 100)
§
¨
0.0
100 1000)
±²
0 0.004)
±0.004² ±0.00³² ±0.01² ±0.04² ±0.0³² ±0.1² 0.00³) 0.01) 0.04) 0.0³ ) 0.1) 0.4)
(c) Sim-4
´
±0.4² 0.³)
1)
4)
±³²
± ²
10 100)
100 1000)
(d) Sim-6 ÄÅ0.01 ÄÅ0.05 ÄÅ0.1
1.0
À
0.
ÄÅ0.2 ÄÅ0.3 ÄÅ0.4
ÄÅ0.5
ÏÐ0.01 ÏÐ0.05 ÏÐ0.1
Ë
0.
ApproxDD
Î
re uen y
re uen y
à 0.¿
Ê
ÏÐ0.2 ÏÐ0.3 ÏÐ0.4
ÏÐ0.5
ApproxDD
0.
Í 0.4
 0.4 Á
Ì
0.2
0.2
»¼
0 0.004)
»0.004¼ »0.00½¼ »0.01¼ »0.04¼ »0.0½¼ »0.1¼ 0.00½) 0.01) 0.04) 0.0½ ) 0.1) 0.4)
¾
»0.½¼
»0.4¼ 0.½ )
1)
»1¼ 4)
»4¼ ½)
»½¼
10)
» ¼
10 100)
»
0.0
¼
100 1000)
ÆÇ
0 0.004)
Æ0.004Ç Æ0.00ÈÇ Æ0.01Ç Æ0.04Ç Æ0.0ÈÇ Æ0.1Ç 0.00È) 0.01) 0.04) 0.0È ) 0.1) 0.4)
(e) ER-0
× Ö
É
Æ0.4Ç 0.È)
Æ0.ÈÇ 1)
Æ 1Ç 4)
Æ 4Ç È)
ÆÈÇ
10)
(f) ER-3 ÙÚ0.01 ÙÚ0.05 ÙÚ0.1
0.Ó 0.Õ Ø 0.5
re uen y
0.0
¥¦0.5
0.2
0.2
0.0
¥¦0.2 ¥¦0.3 ¥¦0.4
£ 0.4
0.4
0.0
¥¦0.01 ¥¦0.05 ¥¦0.1
0.
ApproxDD
ÙÚ0.2 ÙÚ0.3 ÙÚ0.4
ÙÚ0.5
ApproxDD
0.4 0.3 0.2 0.1 0.0
ÑÒ
0 0.004)
Ñ0.004Ò Ñ0.00ÓÒ Ñ0.01Ò Ñ0.04Ò Ñ0.0ÓÒ Ñ0.1Ò 0.00Ó) 0.01) 0.04) 0.0Ó) 0.1) 0.4)
Ô
Ñ0.4Ò 0.Ó)
Ñ0.ÓÒ 1)
Ñ1Ò 4)
Ñ4Ò Ó)
ÑÓÒ
10)
Ñ Ò
10 100)
Ñ
Ò
100 1000)
(g) ER-5
Figure 8: Empirical distribution of ǫv under different c, using ApproxDD-ES.
30
Æ Ç
10 100)
Æ
Ç
100 1000)
0.í
0.05
0.5
0.020
ApproxDDÞßejeàtion ApproxDDÞáounter ApproxDD-ESÞáounter
0.015 0.010 0.005
0.04 ApproxDDæçejeètion ApproxDDæéounter ApproxDD-ESæé ounter
0.03 0.02
0.00
22 0 15 30 45 Ý0 Û 5 Prepro essing ight Sampling)
22 0 1â 34 51 âã Num of Passes ( eft Prepro essing ight
(a) Sim-1, k = 4 õö ÷ õø õø
A erage Max Error
A erage Max Error
0.015
ó 0.010
ü
0.005 2ô ight
0 15 Sampling)
30
45
ô0
ò5
0.0û 0.0ú
Num of Passes ( eft
A erage Max Error
A erage Max Error
0.020 0.015
0.010
0 1ù Sampling)
34
2 ight
0 15 Sampling)
úû
û5
0.3 0.2
0.0 Num of Passes ( eft
30
45
0
5
0.04
332 Prepro essing
2 ight
0 1 Sampling)
34
51
5
5
5
0.2
332 2 Prepro essing ight
0 1 Sampling)
3
(i) Sim-4, k = 6 0.0-
ApproxDD-ES+,ounter
ApproxDD-ES12ounter
0.0/ A erage Max Error
A erage Max Error
0.004
ApproxDD eje!tion ApproxDD "ounter ApproxDD-ES "ounter
0.3
Num of Passes ( eft
0.025
0.00$
5
0.4
0.0
5
(h) Sim-4, k = 5
0.00#
3
0.1
0.030
ApproxDD-ES&'ounter
0 1 Sampling)
0.5
0.0
Num of Passes ( eft
12 2 Prepro essing ight
(f) Sim-2, k = 6 ApproxDDejetion ApproxDDounter ApproxDD-ESounter
0.0
0.00
(g) Sim-4, k = 4 0.010
51
0.02
ApproxDDeje tion ApproxDD ounter ApproxDD-ES ounter
ApproxDDejetion ApproxDD ounter ApproxDD-ES ounter
0.4
(e) Sim-2, k = 5
0.025
332 Prepro essing
0.5
0.1 12ù 2ú Prepro essing ight
0.10
0.005
A erage Max Error
0.04
0.00
0.030
Num of Passes ( eft
0.
0.10
(d) Sim-2, k = 4
0.000
0.
0.02 12ò Prepro essing
êí ë5 Sampling)
(c) Sim-1, k = 6 ApproxDD eje tion ApproxDD ounter ApproxDD-ES ounter
0.12
0.020
Num of Passes ( eft
22 0 1ë 3ì 5ê êë Num of Passes ( eft Prepro essing ight
ýþ ÿ ý ý
0.14
0.025
0.000
0.0
äå å5 Sampling)
(b) Sim-1, k = 5 ApproxDD eje tion ApproxDD ounter ApproxDD-ES ounter
0.030
0.2
A erage Max Error
ÛÜ
0.3
0.1
0.01
Num of Passes ( eft
ApproxDDîïejeðtion ApproxDDîñounter ApproxDD-ESîñounter
0.4
A erage Max Error
0.000
A erage Max Error
0.0ä
0.025
A erage Max Error
A erage Max Error
0.030
0.020 0.015 0.010
0.00 0.05 0.04 0.03 0.02
0.002
0.000
0.005
2# 0 Num of Passes ( eft
0.000
15 30 45 $0 %5 Prepro essing ight Sampling)
(j) Sim-6, k = 4
0.01 2( 0 Num of Passes ( eft
(k) Sim-6, k = 5
0.005
0.005 0.004 0.003 0.002 0.001 0.000
ApproxDD67eje8tion ApproxDD69ounter ApproxDD-ES69ounter
13 13 0 15 30 45 30 45 Num of Passes ( eft Prepro essing ight Sampling)
(m) ER-0, k = 4
0.0C A erage Max Error
A erage Max Error
A erage Max Error
0.025 0.020 0.015 0.010
20 1. 35/ /0 .5 Num of Passes ( eft Prepro essing ight Sampling)
(l) Sim-6, k = 6
ApproxDD=>eje?tion ApproxDD=@ounter ApproxDD-ES=@ounter
0.030
0.004 0.003
0.00
1) 34 51 *( (5 Prepro essing ight Sampling)
0.0A ApproxDDEFejeGtion ApproxDDEHounter ApproxDD-ESEHounter
0.04
0.02 0.005 0.000
1: 13 0 1; 34 51 :< <5 Num of Passes ( eft Prepro essing ight Sampling)
(n) ER-0, k = 5
0.00
1A 13 0 1B Num of Passes ( eft
3C 5D Prepro essing
DA
ight
B5 Sampling)
(o) ER-0, k = 6
Figure 9: L∞ distance between the ground-truth and the estimated k-graphlet distribution as a function of the number of passes for sampling. The X-axis shows the number of passes (preprocessing on the left, sampling on the right). Missing points for ApproxDD mean it did not terminate within 36 hours. 31
0.00K
0.05
0.025
0.005 0.004 0.003 0.002 ApproxDDLMejeNtion ApproxDDLOounter ApproxDD-ESLOounter
0.001 0.000
4I 1J Num of Passes ( eft
A erage Max Error
A erage Max Error
A erage Max Error
0.00J 0.020
0.015
0.010 ApproxDDTUejeVtion ApproxDDTWounter ApproxDD-ESTWounter
0.005
0 15 30 Prepro essing
45 ight
J0
K5 Sampling)
0.000
4P 1Q 0 1R 34 Num of Passes ( eft Prepro essing
(p) ER-1, k = 4
0.04 ApproxDD\]eje^tion ApproxDD\_ounter ApproxDD-ES\_ounter
0.03 0.02 0.01
51 ight
S5 Sampling)
QS
0.00
4X 1Y 0 1X 3Z 5[ Num of Passes ( eft Prepro essing ight
(q) ER-1, k = 5
X5 Sampling)
[Y
(r) ER-1, k = 6
0.01h5 0.00b 0.0150
0.00a 0.005 0.004
c 0.003
i
0.002
ApproxDDdeejeftion ApproxDDdgounter ApproxDD-ESdgounter
0.001
Num of Passes ( eft
233` 1a Prepro essing ight
0 15 30 Sampling)
45
0.0125 0.0100 0.00h5
0.0025
a0
0.0000
`5
Num of Passes ( eft
(s) ER-3, k = 4
A erage Max Error
A erage Max Error {
0.00y 0.004
0.002
0.000 Num of Passes ( eft
233h 1j 0 1h 34 Prepro essing ight Sampling)
ApproxDD}~ejetion ApproxDD}ounter ApproxDD-ES}ounter
3525 1y Prepro essing ight
0 15 30 Sampling)
(v) ER-5, k = 4
jk
51
0.00
k5
Num of Passes ( eft
y0
|5
0.020 0.015
0.000
pr
s5
0.0
0.05 0.04 0.03
0.010
Num of Passes ( eft
5p
0.0
0.025
0.005
45
ApproxDDuvejewtion ApproxDDuxounter ApproxDD-ESuxounter
233p 1r 0 1s 3t Prepro essing ight Sampling)
(u) ER-3, k = 6
ApproxDD eje tion ApproxDD ounter ApproxDD-ES ounter
0.030
0.00z
0.02
0.01
ApproxDDlmejention ApproxDDloounter ApproxDD-ESlo ounter
(t) ER-3, k = 5
0.010
0.03
q
0.0050
A erage Max Error
0.000
0.04 A erage Max Error
A erage Max Error
A erage Max Error
0.00`
0.02 0.01
3525 1 0 1 34 Prepro essing ight Sampling)
(w) ER-5, k = 5
51
5
0.00 Num of Passes ( eft
ApproxDDejetion ApproxDDounter ApproxDD-ESounter
3525 1 0 1 3 Prepro essing ight Sampling)
5
5
(x) ER-5, k = 6
Figure 9: (Continued) L∞ distance between the ground-truth and the estimated k-graphlet distribution as a function of the number of passes for sampling. The X-axis shows the number of passes (preprocessing on the left, sampling on the right). Missing points for ApproxDD mean it did not terminate within 36 hours.
32