Efficient Streaming Algorithms for Graphlet Sampling

Authors: yann  bourreau
marco  bressan
t-h hubert chan
qipeng  kuang
mauro  sozio
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 05:56:30

Abstract: Given a graph $G$ and a positive integer $k$, the Graphlet Sampling problem asks to sample a connected induced $k$-vertex subgraph of $G$ uniformly at random.
Graphlet sampling enhances machine learning applications by transforming graph structures into feature vectors for tasks such as graph classification and subgraph identification, boosting neural network performance, and supporting clustered federated learning by capturing local structures and relationships.
A recent work has shown that the problem admits an algorithm that preprocesses $G$ in time $O(nk^2 \log k + m)$, and draws one sample in expected time $k^{O(k)} \log n$, where $n=|V(G)|$ and $m=|E(G)|$. Such an algorithm relies on the assumption that the input graph fits into main memory and it does not seem to be straightforward to adapt it to very large graphs. We consider Graphlet Sampling in the semi-streaming setting, where we have a memory of $M = \Omega(n \log n)$ words, and $G$ can be only read through sequential passes over the edge list. We develop a semi-streaming algorithm that preprocesses $G$ in $p={O}(\log n)$ passes and samples $\Theta(M k^{-O(k)})$ independent uniform $k$-graphlets in $O(k)$ passes. For constant $k$, both phases run in time $O((n+m)\log n)$. We also show that the tradeoff between memory and number of passes of our algorithms is near-optimal. Our extensive evaluation on very large graphs shows the effectiveness of our algorithms.

Main paper: 
 introduction: 
 Sampling and counting small subgraphs in large graphs is a central problem in graph mining and machine learning. Let G = (V, E) be a simple graph (where n = |V | and m = |E|) and k > 2 an integer. A k-graphlet of G is a connected, induced subgraph of G on k vertices. It is well known that the k-graphlet distribution (the relative frequency of k-cliques, k-paths, and so on) reveals key information about the structure of a graph [MSOI + 02] and can be transformed into the feature vector for graph classification and subgraph identification [TLT + 19]. Graphlet information also contributes to neural network in several ways. [PLG + 20] converted the graph to a matrix by sampling k-graphlets for a sequence of vertices so that convolutional neural networks can be applied.[TLT + 19] showed that using graphlet frequency as a node attribute improves the performance of diffusion-convolutional neural networks for node classification and graph classification. It is also at the heart of graph mining applications such as graph kernels [SVP + 09]. Furthermore, in clustered federated learning [GCYR22] , graphlet sampling can be applied to improve model performance by capturing the local structures and characteristics of the data distributed across various clients or devices. Specifically, graphlet distributions can be used to model relationships between clients or their data in a way that reflects the underlying graph structure, allowing for more informed clustering decisions. As a consequence, sampling k-graphlets uniformly at random from G has become a key primitive in graph mining and machine learning. This problem is called Graphlet Sampling, and many algorithms have been proposed for it [ABH19, BRRAH12, BCK + 17, BCK + 18, BLP19, BLP21, CLWL16, HS16, MG20, PSS19, SH15, WLR + 14].In this work we give efficient streaming algorithms for Graphlet Sampling. The computational model, called streaming model, is as follows. First, the graph G can only be read by scanning its edges sequentially, in an arbitrary order that is unknown to the algorithm. Each scan of the list is called a pass. Second, the algorithm is only granted M = o(|G|) words of memory of Θ(log n) bits each, where n = |V |. For the case M = o(n), the algorithm cannot even store the vertex set and is too restrictive. In this work, we consider the semi-streaming model, in which the algorithm has memory M = Ω(n) and the input graph is dense such that M = o(m). Hence, the algorithm can store the degrees of G but not the entire graph. The goal is to find an algorithm that makes a small number of passes, usually O(log n). This kind of algorithms is widely studied in graph mining, as they are useful when the input data are stored remotely or are too large to fit in main memory.Let us discuss the problem in more detail under the standard RAM model of computation. Sampling a k-vertex subgraph of G that is not necessarily connected is straightforward: just sample a k-vertex set S ⊆ V and return G [S] . The problem becomes nontrivial, though, when the subgraph must be connected (i.e., a k-graphlet). In this case, one very general approach is rejection sampling: one samples some connected subgraph G[S] from some distribution, and then accepts G[S] with some appropriate probability, so that the resulting distribution is as close to uniform as possible. For almost a decade, all known rejection sampling techniques had a worst-case running time of Θ(n k ), or sampled from a nonuniform distribution [BRRAH12, WLR + 14, SH15, BLP19, BLP21]. It was then shown that both issues can be avoided by using a simple two-phase algorithm, UGS (Uniform Graphlet Sampler) [Bre21a, Bre23] . The key idea behind UGS is to sort G topologically by repeatedly deleting a vertex of maximum degree; this takes time O(nk 2 log k + m) where m = |E|. Afterwards, one chooses a starting vertex v according to a certain distribution computed from the topological order, creates a k-graphlet g by exploring the graph surrounding v with vertices topologically no smaller than v in a randomized way, and accepts g with a certain probability (otherwise, the process is repeated). It can be shown that the distribution of the accepted graphlets is uniform, and that the expected time before accepting a graphlet is k O(k) log n.It is therefore natural to apply UGS to the streaming setting. This is not so immediate, though. One key obstacle is that the computation of the topological order of G seems inherently sequential: after deleting a maximum-degree vertex from G, one needs to update the degrees of its neighbors, and in the streaming model this would require one pass. We would thus make n passes in total, which is unacceptable. In this work we show how to overcome these kind of obstacles. We obtain an algorithm that in O(log n) passes computes an approximate topological order of G, and afterwards can sample Θ(M/k O(k) ) independent uniform random graphlets every O(k) passes, as long as the algorithm has M = Ω(kn) words of memory. We make several other nontrivial improvements that has practical impacts. For instance, while deciding if each vertex is contained in a sized-k graphlet takes k passes in a straightforward implementation, we show how to do that in only 1 pass. In the sampling phase, we show how to share computation between parallel trials such that the running time can be reduced by a factor of M (and thus a factor of n), even though the distributions of the parallel instances are still independent. Specifically, if there are Q parallel instances, instead of taking O(mQ) time per pass on the edge list, we reduce the running time to O(m log Q). This requires a careful orchestration of random number generation, sorting, and prefix sum computations. We also prove that any p-pass streaming algorithm for Graphlet Sampling requires memory Ω n p ; therefore, our algorithm is Space lower bounds for Graphlet Sampling. We complement our guarantees by formal lower bounds on the amount of memory M needed by any algorithm for Graphlet Sampling. We prove: Theorem 1.2. For k ≥ 3, any p-pass streaming algorithm for Graphlet Sampling requires Ω ( n /p) bits of memory.We also give a similar lower bound for the problem of computing the approximate topological order mentioned above. These lower bounds are obtained by suitable space-preserving reductions from the Set Disjointness, a well-known problem in communication complexity, and its multiparty variants. The full results are given in Section 4.Experimental evaluation. We conduct an experimental evaluation on real-world graphs containing up to 1.8 billion edges. In particular, we study several metrics as a function of the main parameters of our algorithms. Our evaluation shows that our algorithms are efficient in practice thereby providing a valuable tool in graph mining.Most streaming algorithms for counting or sampling k-graphlets are specifically developed for counting or sampling triangles, and do not give guarantees for k > 3 [BYKS02, BBCG08, PTTW13, ADNK14, JSP15, SERU17, LJK18]. The only algorithms that count or sample k-graphlets for k > 3 with formal guarantees, [KMSS12] and [DSTU17] , do not seem to guarantee uniform sampling.Their main goal is indeed to estimate the total number of occurrences of a given graphlet H in the graph G, and they use (biased) sampling as a subroutine. It is not clear that those algorithms can be adapted to yield efficient and truly uniform k-graphlet sampling.The only algorithm comparable to ours is MOTIVO [BLP19] , which is based on the celebrated color-coding technique of Alon, Yuster and Zwick. MOTIVO has a preprocessing phase and a sampling phase, and they can be implemented in O(k) passes over G using memory M = Ω(c k n) for some c > 0. Crucially, however, MOTIVO does not yield uniform samples: the only graphlets that are sampled with nonzero probability are those made colorful by the color-coding step in the preprocessing. Our algorithm, instead, returns truly uniform samples. We also note that, in practice, MOTIVO uses memory that becomes quickly prohibitive with k [BLP19], while STREAM-UGS uses memory independent of k.Exploiting topological orders of G is common in subgraph mining. The most used order is arguably the degeneracy order, or core order, that yields efficient subgraph-counting algorithms [MB83, CN85, Bre21b, BGL + 22], and for which efficient streaming algorithms exist [BKV12, SGJS + 13]. However, while a core order is obtained by repeatedly removing from G a vertex of minimum degree, our topological order requires to remove a vertex of maximum degree. The two orders may look related at a first glance; for instance, one may be the reversal of the other. It turns out that this resemblance is only apparent, see Section 2. Thus, the algorithms of [BKV12, SGJS + 13] seem not useful here, and we need to develop a new one.It should be noted that Graphlet Sampling is not the same problem as sampling from G the occurrences of a prescribed k-vertex pattern graph H. This can be seen by letting H be a k-vertex clique: in that case, sampling an occurrence of H in G solves the Clique problem, and this requires time n Ω(k) unless the widely-accepted Exponential Time Hypothesis fails [CHKX06] . Graphlet Sampling instead can be solved in FPT time, that is, timef (k) • n O(1), as [Bre21a, Bre23] and this work show.Finally, we follow the typical technique of proving the streaming lower bound by considering the communication complexity on the famous communication game [CKS03, BJKS04] . In such proof, the game is reduced to a streaming algorithm executed by players so that a better tradeoff between memory and number of passes implies a communication cost contradicted to its lower bound. An elaboration in detail is presented in Section 4. 
preliminaries: 
 Let G = (V, E) be a simple graph. We assume V = {1, . . . , n}. For a total order ≺ over V , we use G(v) to denote the subgraph of G induced by {u : u ⪰ v}, i.e., the subset of vertices containing v and all vertices after v in ≺. Given u ∈ V we let N (u|G(v)) = {w ⪰ v : {u, w} ∈ E} be the neighborhood of u in G(v), and d(u|G(v)) = |N (u|G(v))| be the degree of u in G(v). We denote by ∆ the maximum degree of G. The following notion will be crucial:Definition 2.1 (ϑ-DD Order). Let ϑ ∈ (0, 1]. A total order ≺ over V is a ϑ-degree-dominating order (ϑ-DD order) if, for all v ∈ V with d(v|G(v)) > 1 and all u ⪰ v, we have d(v|G(v)) ≥ ϑ•d(u|G(v)).The topological order used by UGS [Bre23] is a 1-DD order. A ϑ-DD order is an approximation of a 1-DD order. Using a ϑ-DD order yields the same guarantees of UGS, only with an acceptance probability scaled by ϑ k-1 (see Lemma C.1).Computational model. The algorithm has a memory of M words of Θ(log n) bits each. We require M = Ω(n) or M = Ω(n log n), depending on the case. The graph is stored as a list of edges in arbitrary (i.e., adversarial) order. With one pass, the algorithm can read the list sequentially. This is called semi-streaming model [FKM + 05]. To avoid trivialities we assume m = Ω(M ); otherwise, in one pass one can store G and run the algorithm of [Bre23] . For computation we assume the standard RAM model. We also assume that in time O(1) one can draw a random uniform integer in {1, . . . , c} for any c = poly(n), or a Bernoulli random variable B(p) for p = Ω(n -k ). When we run multiple instances of a subroutine in parallel, the running time is understood to be the total number of operations executed by all those instances.Graphlet size. Our algorithms are designed primarily for k = O(1), but they yield nontrivial guarantees also for k = ω(1); for instance, for k = √ log n. Our full statements make the dependence on k clear. DD orders vs. core orders. It should be noted that 1-DD orders and core orders do not seem related in any useful way. For example, let G be the disjoint union of a star with δ 1 leaves and a δ 2 -clique. If δ 1 > δ 2 , then the center of the star comes first in a 1-DD order, but in a core order it sits after the star's leaves and before the clique vertices. If δ 2 > δ 1 , instead, then in a core order the vertices of the star all come before the clique, while in a 1-DD ordering the center of the star sits after δ 2 -δ 1 vertices of the clique.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: As stated in all theorems, our results are under semi-streaming setting requiring Ω(n) or Ω(n log n) memory, which might not be satisfied in extremis. Though we gave theoretical bounds for time and memory complexity and the number of passes asymptotically, constant factors might be significant in some cases, which impairs the performance. Due to our limited computational resources, we only tested our algorithms on a few and relatively large datasets. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 5. Open access to data and code Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: We attached the code and instruction to our submission. • The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
a streaming-based graphlet sampling algorithm: 
 This section describes our semi-streaming algorithm, STREAM-UGS. STREAM-UGS is based on the approach of UGS [Bre23] , and runs in two phases: preprocessing and sampling.Preprocessing. This is done once, and involves two steps.P1 Computing a ϑ-DD order ≺ of G. The order defines implicitly the subgraphs G(v), see Section 2, as well as a certain distribution ⃗ p over V that is needed by the sampling phase, see below. P2 Computing the said probability distribution ⃗ p on V . Let G(v) be the set of all graphlets that are subgraphs of G(v) and contain v. This is called the bucket of v. The distribution ⃗ p can be seen as a distribution over the buckets G(v). For every v ∈ V , the probability p(v) is proportional to d(v|G(v)) k-1 if G(v) ̸ = ∅, and p(v) = 0 otherwise. The entry p(v) will be the probability that v is picked in the first step of the subsequent sampling.Sampling. This phase may report failure, but if it succeeds, it returns a uniformly random k-graphlet of G. The expected number of trials to successfully return a graphlet is ϑ 1-k • k O(k) . However, with enough memory, one can carry out independent trials in parallel. The phase consists of three steps. S1 Choosing a bucket G(v) according to the probability distribution ⃗ p. One can show that, if k) . Thus, we are choosing buckets with probability roughly proportional to the number of k-graphlets in them. S2 Sampling a random graphlet G[S] ∈ G(v). To this end let S 1 = {v}. For i = 1, 2, . . . , k -1, draw an edge uniformly at random from the cut between S i and G(v), and add the endpoint to S i ; this gives S i+1 . The final set S = S k defines the graphlet G[S]. Note that the sampling here is not uniform. Uniformity is ensured by the next step. S3 Accepting S with some probability p(S). If S is accepted then compute G[S] and return it; otherwise, report failure.G(v) ̸ = ∅, then |G(v)| equals d(v|G(v)) k-1 , up to factors k O(Technical Challenges. In the semi-streaming setting, we cannot store all the edges of G in the memory. Our contributions are how to implement each of the above steps with restricted memory using a small number of passes on the edge list.We present an algorithm, APPROX-DD (Algorithm 1), that given a graph G and a parameter 0 < ϵ = O(1), computes a ϑ-DD order of G, where ϑ = 1 1+ϵ . Our main result is: Theorem 3.1. In the semi-streaming model, APPROX-DD can be implemented so that with probability at least 1 -n -Θ(1) , it makesq = O log n ϵ 2 log log n ϵ passes if M = Ω(n), and q = O log n ϵ 2 passes if M = Ω n log n ϵ. In both cases the total running time is in O(q • m).The complete proof of Theorem 3.1 combines several technical lemmas and can be found in Appendix A. The rest of this section overviews APPROX-DD and sketches the proof. APPROX-DD maintains a list L, initially empty, which will eventually contain the vertices of V sorted by ≺. The algorithm proceeds in peeling rounds; every round deletes from G all vertices of degree at least ∆ 1+α , for some appropriate α, and places them in L in the right order. This "right order" is not simply any order; it is carefully computed by another procedure, called shaving, using random partitioning. Algorithm 1 gives the pseudocode of APPROX-DD. It assumes that δ G (•), and all other degrees, are updated as soon as the graphs are modified; except for ∆, which is explicitly recomputed when needed. In practice, updating the degrees amounts to running one pass over the edges of G. The algorithm has a triply nested loop structure, and we use the subroutines PEEL and SHAVE for clearer illustration.Algorithm 1 Approximate DD Order. The lines marked with a ▷ entail a recomputation of the degrees and, thus, one streaming pass.1: function APPROX-DD(G, ϵ) 2: L ← empty list 3: while V (G) ̸ = ∅ do 4: (G, L) ← PEEL(G, ϵ, L) 5: return L 6: function PEEL(G, ϵ, L) 7: ∆ ← max v∈V (G) d(v|G) ▷ 8: α ← ϵ 2 9: H ← {v ∈ V (G) : d(v|G) ≥ ∆ 1+α } 10: while H ̸ = ∅ do 11: (G, L, H) ← SHAVE(G, ϵ, ∆, L, H) 12:return (G, L)13: function SHAVE(G, ϵ, ∆, L, H) 14: β ← 2+2ϵ+ϵ 2 ϵ , ℓ ← ⌈2(1 + β)⌉ 15:let H 1 , . . . , H ℓ be a uniform random partition ofH 16: let R i ← {v ∈ H i : d(v|G[H i ]) ≤ ∆ 1+β } for i ∈ [ℓ] ▷ 17:for i = 1, . . . , ℓ do 18:S i ← {v ∈ R i : d(v|G) ≥ ∆ 1+α } 19:append the vertices of S i to L in arbitrary order 20:G ← G \ S i ▷ 21: H ← H \ ∪ i∈[ℓ] R i 22:return (G, L, H)Intuition for PEEL and SHAVE. Let H be the subset of vertices with degree at least ∆ 1+α in G (line 9). As a first attempt, we could remove all vertices in H from G in a single batch, which is appended to L in arbitrary order. This works if every vertex v has all of its neighbors come after itself in L, since in that case d(v|G(v)) ≥ 1 1+α ∆ ≥ 1 1+ϵ d(u|G(v)) for all u ⪰ v. However, in general this does not happen.To this end, we attempt to remove vertices in H from G in phases through SHAVE. Specifically, we assign each vertex in H to one of ℓ = ⌈2(1 + β)⌉ batches H 1 , . . . , H ℓ independently and uniformly at random. By Markov's inequality, each vertex has at most ∆ 1+β neighbors within H i with good probability; then, in phase i, every such vertex in H i that has current degree at least ∆ 1+α will be removed together in one batch from G (and appended to L in an arbitrary order). The degrees of the remaining vertices in G will then be updated. Each call to SHAVE has ℓ such phases.The procedure performed by SHAVE does not yet remove H from G; it removes only the vertices that have few neighbors in the same subset H i . To completely remove H, we need to iterate the procedure. This is what PEEL does at line 10. We shall see that there are two cases. When ∆ is large enough, then one call to SHAVE in line 11 will be sufficient to make H empty with high probability. When ∆ is small, we may instead need O(log n) calls to SHAVE in order for H to become empty. This is, technically speaking, what makes the whole algorithm APPROX-DD efficient. Formally, we prove the following (in Appendix A): Lemma 3.2. Let p ∈ (0, 1). With probability at least 1 -p, one execution of PEEL (Algorithm 1) calls SHAVE O log n p times, and at most once if ∆ ≥ 12(1 + α)(1 + β) ln n p .Algorithm 2 gives the pseudocode of COMPUTEDISTRIB, which computes the distribution ⃗ p and the normalization constant Γ needed by the sampling phase. As said above, the crux of COMPUTEDISTRIB is checking if G(v) ̸ = ∅ for each v ∈ V . To this end, it suffices to perform a BFS on all vertices in parallel, so as to check whether the connected component of v in G(v) has size at least k. A naive method would take k passes on the edge list, but with Ω(kn) words of memory, we can achieve this in 1 passes, as Lemma 3.3 proves.Algorithm 2 COMPUTEDISTRIB 1: function COMPUTEDISTRIB(≺) 2: for each v ∈ V do 3: compute d(v|G(v)) and 1 v := 1 G(v)̸ =∅ 4: set b v ← 1 v • d(v|G(v)) k-1 5: set Z ← v∈V b v 6: compute probability vector ⃗ p: for each v ∈ V , p(v) ← bv Z 7: set Γ ← 1 (k-1)! Z (1+ϵ) k-1 8: return (⃗ p, Γ)Lemma 3.3. In the semi-streaming model with M = Ω(kn), the routine COMPUTEDISTRIB (Algorithm 2) can be implemented so as to use 1 passes and time O(m + n • k 2 log k).Algorithm 3 gives the pseudocode of SAMPLE, the sampling phase of STREAM-UGS. The sampling phase works after invoking APPROX-DD and COMPUTEDISTRIB in turn (see the subroutine PREPROCESS in Algorithm 4, Appendix A). Note that Algorithm 3 gives only an abstract description of the routines. The concrete implementation details are rather involved, though, and we give them in the rest of the section. The reason for this complexity is that, since each sampling trial requires memory O(k 2 ), then with a memory of M words we can perform Θ(M/k 2 ) independent sampling trials in parallel. Doing so efficiently, though, is significantly less straightforward than one would think. However, we prove: Theorem 3.4. In the semi-streaming model with M = Ω(kn) words of memory, suppose the preprocessing routine PREPROCESS has been run with ϵ = 1 /2. Then, Q = Θ(M/k 2 ) parallel instances of SAMPLE can be run in a batch so that Q/k O(k) = Θ(M/k O(k) ) independent uniform random k-graphlets of G-O(k) (1+ϵ) k-1 = k -O(k). By standard concentration bounds, then, with high probability the number of uniform random k-graphlets returned overall is Θ(M/k O(k) ). The details of the subtroutines and data structures to achieve Theorem 3.4 are given in Appendix C. 
space lower bounds: 
 We show that the tradeoff between memory and number of passes of our algorithms is near-optimal. To this end, we use well known results from communication complexity. In the multi-party randomized communication model [CKS03, BJKS04] , there are t ≥ 2 players seeking to compute a function f :X 1 × X 2 • • • × X t → Ywhile exchanging messages according to a specified protocol Π. For each i ∈ [t], the i-th player has an input x i ∈ X i . Given x 1 , . . . , x t , the random variable Π(x 1 , . . . , x t ) denotes the message transcript (containing all messages) obtained when all players follow Π on Algorithm 3 SAMPLE (Abstract Description)1: function SAMPLE(≺, ⃗ p, Γ) ▷ ≺ is used to define G(v). 2:Sample v from the distribution ⃗ p.3:S ← RAND-GROW(v, ≺) 4: q S ← PROB(v, S, ≺) 5:With probability Γ p(v)•q S , return S;6:Otherwise, return "failure"7: function RAND-GROW(v, ≺) 8:S 1 ← {v} 9:for i = 1, . . . , k -1 do 10:let E i be the subset of edges in G(v) with exactly one endpoint in S i .11:sample an edge {u, u ′ } uniformly at random from E i , where u ∈ S i and u ′ / ∈ S i .12:S i+1 ← S i ∪ {u ′ } 13:return S k 14: function PROB(v, S, ≺)15:for i = 1, . . . , k do 16:q i ← an empty map from S i to R with default value 0 17:q 1 ({v}) ← 1 18: for i = 2, . . . , k do 19:for each S i ∈ S i and each w ∈ S i do 20:n i ← number of neighbors of w in S i 21: c i ← z∈Si\{w} (d(z|G(v)) -d(z|G[S i \ {w}])) 22: q i (S i ) ← q i (S i ) + q i-1 (S i \ {w}) • ni ci 23: return q k (S)inputs x 1 , . . . , x t , where the randomness is over the coins of the players. Π is a δ-error protocol for f if there is a deterministic function Π out such that, for all inputs x 1 , . . . , x t ,EQUATIONThe communication cost of Π, denoted by |Π|, is the maximum length of Π(x 1 , . . . , x t ) over all x 1 , . . . , x t and over all random choices of all players. The δ-error randomized communication complexity of f is the cost of the best δ-error protocol for f . In the one-way variant of such a model, the ith player sends exactly one message to the (i + 1)th player, throughout the protocol (we let t + 1 = 1).In the classical disjointness problem, the ith player has an n-bit vector (x i1 , . . . , x in ) ∈ {0, 1} n that corresponds to a subset of a sized-n ground set. The goal is to determine whether there is a common element among the subsets of all players, i.e. whether there is an index j such thatx ij = 1, for all i ∈ [t].It is known that this problem has Ω(n/t) communication complexity in the one-way multi-party randomized communication model (Theorem 2.6 of [CKS03] ). This holds even in the case when either the bit vectors represent pairwise disjoint sets or they have a unique common element but are otherwise pairwise disjoint.We show that any q-pass streaming algorithm requires memory M = Ω(n/q) even for the problem of computing a node with approximate maximum degree, that is, to compute a node with rank 1 in an approximate DD-order. We believe such a result is well-known, however, we could not find a reference for a general q-pass algorithm. For completeness, we provide the full proofs in Appendix D. Lemma 4.1. Given a graph G = (V, E), α ∈ (0, 1), any q-pass streaming algorithm computing anode v such that δ G (v) ≥ α max w∈V δ G (w) with probability at least 2 3 , requires memory Ω α 2 |V | q .Finally, we provide a lower bound on the memory requirement of any streaming algorithm for uniform k-graphlet sampling, k ≥ 3. Lemma 4.2. Given a graph G = (V, E), k ≥ 3, any q-pass streaming algorithm for the uniform  
experiments: 
 We implemented our algorithms in Python 3.9 and conducted experiments on a Ubuntu server with CPU Intel Xeon Silver 4108 (1.80GHz) and 28GB RAM. The implementation can be found in the online repository. 4Datasets. We run our experiments on several real-world graphs from the KONECT website [Kun13] 5 and a synthetic random dense graph generated by drawing each edge with probability 0.8 (we name it Dense). We removed edge directions, weights, self-loops, duplicate edges and any other irrelevant data, so as to retain only a list of undirected edges. Table 1 reports all dataset statistics after such a preprocessing phase.Streaming model. The stream of edges comes from a CSV file stored in the disk representing the edge list. Our algorithms make multiple sequential passes over the input data while never storing the set of edges in main memory. Note that from Theorem 3.4 we have two approaches to do sampling in parallel, among which we implemented the second one using 2k -1 passes and O(M 2 k + km log n) time.Methodology. We constrain the memory M by restricting the maximum number of edges that we can store during the computation of the DD order and sampling to be n 2 in all cases. In the sampling phase it is required to sample at least 100 graphlets successfully in order to reduce the error of sampling probability. We study several metrics as a function of ϵ and k, such as the number of passes, the memory usage, as well as the number of sampling trials to obtain 100 graphlets.A Heuristic Approach for PEEL. We develop a heuristic approach called APPROX-DD-HEURISTIC in Appendix E to speed up the running time of Algorithm 1. We evaluate APPROX-DD-HEURISTIC on large real-world graphs to show the scalability of our algorithms and then conduct a comparison between APPROX-DD and APPROX-DD-HEURISTIC on smaller graphs. APPROX-DD versus APPROX-DD-HEURISTIC. We conduct the comparison between APPROX-DD and APPROX-DD-HEURISTIC on NY Times, the real-world sparse graph and Dense, the synthetic dense graph. Figure 1 shows the number of passes and memory usage as a function of ϵ.In Figure 1a and 1b we can see that APPROX-DD-HEURISTIC delivers significantly better results for sparse graphs but has no significant advantage for dense graphs. This is expected, as PEEL-HEURISTIC can process at each step a relatively large chunk of the input graph, if such a graph is sparse. Moreover, consistently with our theoretical analysis in Section 3, we can observe that the number of passes for preprocessing decreases as a function of ϵ, while the number of passes for sampling increases. Concerning APPROX-DD-HEURISTIC, both the number of passes and memory usage are less sensitive to ϵ since in APPROX-DD-HEURISTIC the amount of available memory plays a more important role.As observed, APPROX-DD-HEURISTIC outperforms APPROX-DD on real-world sparse graphs. Hence, we will focus our attention on APPROX-DD-HEURISTIC in the following experiment.Running on Large Graphs. Figure 2 shows several metrics as a function of ϵ and k over real-world large graphs. Figure 2a and 2b show that around 30 passes are sufficient to complete the whole sampling task, while the memory usage is indeed less than the total size of the edge list. Figure 2c and 2d show the number of trials to obtain 100 graphlets as a function of ϵ and k, respectively. Observe that the success probability is significantly higher than the worst-case bound provided by Lemma C.1. For example, the actual success probability in Twitter(WWW) with ϵ = 1, k = 4 is 100/31230 ≈ 0.0032, which is significantly larger than 9.65 × 10 -5 provided by Lemma C.1. 
conclusion and future work: 
 We develop efficient semi-streaming algorithms for uniform graphlet sampling, requiring sublinear amount of memory and polylogarithmic number of passes in the size of the input data. We also provide a space lower bound showing that the tradeoff between memory and number of passes of our algorithms is near-optimal. Our theoretical results are complemented with an experimental evaluation on large real-world graphs showing the effectiveness of our algorithms and that they can provide a valuable tool in graph mining and data analysis. Our work paves the way for developing efficient algorithms in other computational model for large-scale processing, such as the MapReduce model.A Proofs for Section 3.1Lemma A.1. APPROX-DD(G, ϵ) computes a 1 1+ϵ -DD ordering of G.Proof. First, consider SHAVE. We claim that, just after the execution of line 18, every vertex in S i has at least ∆ 1+α -∆ 1+β and at most ∆ neighbors in V (G) \ S i . Consider indeed any v ∈ S i just after line 18 is executed. Note that v has by construction at least ∆ 1+α neighbors in V (G), and since S i ⊆ R i , it has at most ∆ 1+β neighbors in S i . The lower bound follows. For the upper bound just note that v has degree at most ∆ in V (G) and, thus, in V (G) \ S i . Now consider APPROX-DD(G, ϵ). Note that the final list L is obtained through the subroutine SHAVE by repeatedly computing some S i ⊆ V (G), appending S i to L, and deleting S i from G (lines 20 and 19). On the one hand this implies that the returned list L is a permutation of V (G) (i.e., every vertex of V (G) appears exactly once in L). On the other hand consider any vertex v ∈ V (G), and let ∆ be as in the subroutine PEEL when v was appended to L. By the arguments above and by the choice of α, β:d(v|G(v)) ≥ ∆ 1 + α - ∆ 1 + β ≥ ∆ 1 + ϵ (2)where G(v) is the subgraph of G induced by v and all vertices appearing after v in L. Moreover note that ∆ is an upper bound on d(u|G(v))for every u ∈ G(v). It follows that d(v|G(v)) ≥ d(u|G(v))1+ϵ for all v and all u ≻ v where ≻ is the ordering defined by L.Lemma A.2. Each call to SHAVE requires ℓ + 1 = O(ϵ + 1 ϵ ) invocations of COMPUTEALLDEG.Proof. Line 16 requires, for each i ∈ ℓ, one call to COMPUTEALLDEG on G[H i ]. For each one of the ℓ iterations of the loop at line 17, a call to COMPUTEALLDEG is needed after G is updated at line 20. Noting that ℓ = O(ϵ + 1 ϵ ) concludes the proof. Lemma 3.2. Let p ∈ (0, 1). With probability at least 1 -p, one execution of PEEL (Algorithm 1) calls SHAVE O log n p times, and at most once if∆ ≥ 12(1 + α)(1 + β) ln n p .Proof. Consider a generic iteration of the loop of line 10. Fix any v ∈ H i and write d Hi (v) as:EQUATIONwhere X i (u) is the indicator variable of the event u ∈ H i . Note that E[X i (u)] = 1 ℓ and thereforeEQUATIONand thereforeEQUATIONBy standard arguments this implies that, for all p > 0, with probability at least 1 -p after O(log n p ) iterations of the the loop of line 10 the set H becomes empty and thus the loop terminates.For the second claim, note that ℓ ≤ 4(1 + β) and d(v|G) ≥ ∆ 1+α implyEQUATIONNow consider again (3), and note that the random variablesEQUATIONare independent by construction of H i . By standard concentration bounds then:EQUATIONThus for ∆ ≥ 12(1 + α)(1 + β) ln n p we have Pr d(v|H i ) > ∆ (1+β) ≤ 1 n . By a union bound over all v ∈ H this implies that, with probability at least 1 -p, for all i ∈ [ℓ] we have R i = H i . If that is the case then H becomes empty when line 21 is executed, proving the claim.Lemma A.3. When the subroutine PEEL is called on a graph G with maximum degree ∆, it removes vertices from G so that, upon termination, G has maximum degree smaller than ∆ 1+α . Moreover, if ∆ < 1, then PEEL terminates after one iteration of the loop of line 10 and returns G = ∅.Proof. Denote by G ′ the value of G when the loop of line 10 ends. SupposeG ′ contains a vertex v such that d G ′ (v) ≥ ∆ 1+α . Since G ⊇ G ′ then d G (v) ≥ ∆ 1+α, and thus v ∈ H by line 9; and since the loop ends when H = ∅, then at some iteration v ∈ R i for some i ∈ [ℓ]. Consider then that iteration and let G be the current graph; obviouslyG ⊇ G ′ . If v ∈ S i then by line 20 v / ∈ G and thus v / ∈ G ′ . If instead v / ∈ S i then by line 18 d G ′ (v) ≤ d G (v) < ∆ 1+α .Both cases give a contradiction. For the second claim note that if ∆ < 1 then ∆ = 0. In that case H i = R i = S i for all i ∈ [ℓ], and the claim follows by construction of the algorithm.Lemma A.4. Consider one execution of APPROX-DD (G, ϵ) in Algorithm 1. For every p ∈ (0, 1),EQUATIONProof EQUATION)where we used T = O ϵ + 1 ϵ log n p . By one final union bound over the two cases ∆ ≥ T and ∆ < T , with probability 1 -p the expression in (13) bounds the total number of calls to SHAVE. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: In the sampling phase the algorithm is required to sample at least 100 graphlets successfully so that our experiments are statistically significant. Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: Resources were stated at the beginning of Section 5.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes]Justification: Since we are using public datasets and randomly generated dataset, we do not have issues of ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This work is about the streaming algorithm of graphlet sampling, which we believe will not lead to malicious uses directly.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This work poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes]Justification: We have cited the public online datasets that we used. No license has been found.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: The number of passes is dominated by the number of calls to the subroutine COMPUTEALLDEG. Indeed, since V = {1, . . . , n}, we can keep a global array of O(n) words that for every v ∈ V stores the following information: whether v is still in G, the index i of the subset H i or R i or S i containing v, as well as the degree of v in any of those subgraphs. After each pass, the whole array can be updated in linear time so to be ready for the next iteration. It is then easy to see that COMPUTEALLDEG can be ran on any graph G, H i , etc. using one pass and linear time: scan the edge list, and for each edge e = {u, v} increase the degree counters of both u and v iff they both belong to the target vertex set (which can be checked in time O(1) using the array). This also shows that the total running time per pass of APPROX-DD is in O(m).It remains to bound the total number of calls to COMPUTEALLDEG. First, assume M = Ω(n).In this case we simply run APPROX-DD until it terminates when V = ∅. By Lemma A.4, using p = n -Θ(1) , the total number of calls fo SHAVE is inEQUATIONAs by Lemma A.2 each call to SHAVE makes O(1/ϵ) invocation of COMPUTEALLDEG, the bound follows.Now assume M = Ω(n log n). Let again p = n -Θ(1) . In this case we let APPROX-DD stop as soon as ∆ < T , where B Proofs for Section 3.2 Lemma 3.3. In the semi-streaming model with M = Ω(kn), the routine COMPUTEDISTRIB (Algorithm 2) can be implemented so as to use 1 passes and time O(mEQUATION+ n • k 2 log k).Proof. Computing Z, ⃗ p, and Γ clearly takes time O(n), hence we focus on computing d(v|G(v))and 1 v for all v ∈ V . Consider the oriented graph ⃗ G = (V, A) constructed from G as follows. For every v ∈ V say that v is light if d(v|G(v)) < k -1 and heavy otherwise. For every light vertex v, add the arc (v, x) to A for every x ∈ N (v|G(v)) (let us call such arc a light arc). Moreover, if v is light and has heavy neighbors in G, then add to A the arc (v, y) where y is largest heavy neighbor of v in ≺ (let us call such arc a heavy arc). For every v assign a weight w(v) = 1 if v is light and w(v) = k if v is heavy. Moreover, for every v let ⃗ G(v) be the subset of vertices reachable from v in G(v) by following the arcs in ⃗ G. Finally, define ⃗ w(v) = u∈ ⃗ G(v) w(u). We claim that ⃗ w(v) ≥ k if and only if |G(v)| ̸ = ∅.To see this, note that both conditions are equivalent to the following one: in ⃗ G, starting from v and following forward arcs to vertices in G(v), one can reach at least k light vertices or at least one heavy vertex. Thus we need only to construct ⃗ G and, from each v ∈ V , run a truncated BFS to check if ⃗ w(v) ≥ k. Assuming ⃗ G is represented by adjacency lists, each BFS requires O(k 2 log k) operations, since it stops before seeing k 2 arcs. The total time for the BFS is thus n • k 2 log k.To construct G, we use a single pass to compute d(v|G(v)) for each vertex v as well as determine heavy vertices and light vertices. We initially mark all vertices as light vertices. As we process the edges, for each edge (v, x) from v to x ∈ N (v|G(v)) where v is light, we add it to A as a light arc. If v is heavy, we update the heavy arc of x if x is light. Once we detect any light vertex v having at least k -1 light arcs, we mark v as a heavy vertex, update the heavy arc of the other endpoint of each of these light arcs and remove them. This can clearly be implemented in time O(m).C Proofs for Section 3. k) . By standard concentration bounds, then, with high probability the number of uniform random k-graphlets returned overall is Θ(M/k O(k) ).-O(k) (1+ϵ) k-1 = k -O(We prove the two bounds on the number of passes and running time by describing two implementations of SAMPLE. Both implementations use the same approach for PROB, which is ran in parallel for all Q instances and takes only one pass. First, PROB computes G[S] (i.e., it retrieves the edges) as well as d(u|G(v)) for all u ∈ S. To this end each instance creates pairs (u, v), (v, u) for each {u, v} ∈ S Each instance of PROB can then conclude its execution by running the loop of line 18. This loop iterates over all subsets of S, which are at most 2 k , and performs O(k 2 ) operations for each of them. Summed over the Q = O(M/k 2 ) instances, this yields a time in O(2 k M ). Adding the bound above for computing G[S] and the degrees, we obtain a total running time of O(M 2 k + m log n) for all instances of PROB.First implementation. This is the straightforward approach in which the Q instances do not share any computation. The running time of RAND-GROW is dominated by the iteration of the loop at line 9. Every edge in the stream is sent to each of Q instances. The instance selects only the edges that belong to E i , which requires time O(k) per edge; and it uses reservoir sampling to sample from those edges uniformly at random. Hence, over the Q instances, the time for each pass is O(Qkm), and the time for making the k -1 passes is O(Qk 2 m) = O(M m).Since we consider k = o(log n) and M = Ω(nk), the time for PROB is O(M 2 k + m log n) = O(M m). Hence, the total running time to execute the batch is O(M m).Second implementation. For a given instance of RAND-GROW (v, ≺) consider a generic iteration of the loop at line 9. As in the original implementation of [Bre23] , we first sample a node u ∈ S i with probability proportional to the number of edges it has in E i , and then sample one of its edges {u, u ′ } in E i uniformly at random. to sample u, first we compute d(u|G(v)) for every u ∈ S, as well as G[S]. By using again SUBDEGREES and CHECKEDGES, this requires one pass and time O(m log n). Then, we can sample u with probability proportional to d(u|G(v)) -d(u|G[S]). This takes time O(k 2 ), as computing d(u|G[S]) for every u entails checking the edges of G[S]. Next, to draw an edge {u, v ′ } uniformly at random in E i , we draw a random uniform subset of i edges e 1 , . . . , e i incident with u in E i . Since at most i -1 of them can be incident with S i , it follows that at least one of them is not, and is therefore a random uniform edge incident with u in the cut of E i .To draw e 1 , . . . , e i we use SAMPLEEDGES (Algorithm 7). First, we draw a random uniform subset of i distinct integers j 1 , . . . , j i from {1, . . . , d(u|G(v))}. We then create i triplets (u, v, j 1 ), . . . , (u, v, j i ). For each h = 1, . . . , i we then create a global list T h consisting of the triplets (u, v, j h ). Finally, we execute SAMPLEEDGES(T h ) for all h = 1, . . . , i in parallel. Let F h be the dictionary returned by SAMPLEEDGES(T h ). By Lemma C.4, and by the choices of j 1 , . . . , j i , each e h = F h [(u, v)] is a random uniform edge between u and N (u|G(v)), for h = 1, . . . , i. Moreover, and crucially, Lemma C.4 guarantees that e 1 , . . . , e i are all distinct, since the instances of SAMPLEEDGES receive the same pairs (x, y); only the indices j differ. Thus e 1 , . . . , e i is a random uniform subset of i edges incident with u in E i , as desired. Again by Lemma C.4, asi h=1 |T h | is again bounded by M = O(m), the total time is in O(m log n).Therefore we have 2 passes for each one of the k -1 iterations of RAND-GROW, plus one pass for PROB, for a total of 2k -1 passes. The total running time is O(M 2 k + km log n).In this subsection, we elaborate the details for subroutines that are used in the proof of Theorem 3.4. First, we prove that SAMPLE returns independent uniform graphlets, and with a probability that is in(k(1 + ϵ)) -O(k) .Lemma C.1. After running PREPROCESS once, every invocation of SAMPLE returns a size-k set S with probability at least 1 (1+ϵ) k-1 ((k-1)!) 4 . Moreover, if SAMPLE succeeds, then the graphlet returned is drawn uniformly at random from the set of all k-graphlets of G.Proof. We adapt the claims and proofs of Section 6 of [Bre23] as follows. Suppose the vertices of G is sorted according to a 1 1+ϵ -DD ordering ≺, and suppose the subset S forms a k-graphlet of G, where v ∈ S is the earliest vertex among S in the ordering. First, one can verify that [Bre23, Lemma 24] can be generalized to yield the result that for vEQUATIONGiven v and ≺, suppose q S is the probability that RAND-GROW(v, ≺) returns S. Using the inequality in (16), one can verify that [Bre23, Lemma 25] can be generalized to yieldEQUATION)One can also check that PROB(v, S, ≺) computes precisely q S . Now consider the probability that S is accepted in line 5 of Algorithm 3, p acc (S) = Γ p(v) q S . The same arguments of [Bre23] show thatEQUATION)Moreover, the probability that S is sampled and returned by SAMPLE is p(v) • q S • p acc (S) = Γ, which is independent of S. This implies that given that SAMPLE successfully returns some subset S, S is drawn uniformly at random from the set of all k-graphlets of G.Next, we give a simple routine for checking efficiently for a set of edges, in parallel. This routine, and other ones below, operate on list of pairs of vertices (u, v). When we speak of an order over those pairs, we mean the lexicographic order induced by the approximate DD order ≺: Sort L and remove duplicates.EQUATION3:for each orientation (u, v) of every edge in the stream do 4:Search (u, v) ∈ L and, if present, mark it.Delete all unmarked elements from L.return LWe give two routines, SUBDEGREES and SAMPLEEDGES, that respectively compute a set of degrees d(u|G(v)) and sample a set of uniform random edges from subgraphs G(v). The routines make use of sorted lists L of tuples, where in each tuple the first two elements are vertices u, v. The segment L(u, v) is the sublist formed by all elements whose first two entries are u, v, in this order, and L(u) is the sublist formed by all sublists L(u, v). The maps returned by the algorithms are assumed to support lookup in time O(log |L|).Algorithm 6 SUBDEGREES 1: function SUBDEGREES(≺, L = (u 1 , v 1 ), . . . , (u t , v t )) 2:Sort L by ≺ and remove duplicates.Initialize c u,v ← 0 for every (u, v) ∈ L.for each orientation (u, v) of every edge in the stream do5: if ∃(u, v) ∈ L, (u, v) ⪯ (u, v) then 6:Let (u, v) be the largest such pair.Update c u,v ← c u,v + 1.Init dictionary D :V 2 → [n]. 9:for every segment L(u) and every (u, v) ∈ L(u) do Lemma C.4. Let T = {(u 1 , v 1 , j 1 ), . . . , (u t , v t , j t )} be such that, for every (u, v, j) ∈ T , we have Moreover, for every (u, v, j) ∈ T , the map F (u, v, j) returns the j-th edge incident to u in G(v), where the ordering of u's incident edges depends only on (i) the pairs (u i , v i ) appearing in T (i.e., the first two components of each triple in T ) and (ii) the order of the edges in the stream. We next prove correctness. For every (u, v) ∈ L, let E(u, G(v)) be the set of incident edges of u in G(v). We next specify an ordering on E(u, G(v)) that depends only on the (other) pairs in L and the order of the edges in the stream. Let L ⪰ (u) = {(u, v 1 ), . . . , (u, v h )} be the sorted list of pairsu, v ∈ V with v ⪯ u,(u, v i ) in L such that v i ⪰ v, where v = v 1 . Algorithm 7 SAMPLEEDGES 1: function SAMPLEEDGES(≺, T = (u 1 , v 1 , j 1 ), . . . , (u t , v t , j t )) 2:Compute the list L of distinct pairs (u, v) s.t. ∃(u, v, j) ∈ T , and sort L by ≺ 3:for each (u, v) ∈ L do 4:Compute the increasingly sorted list J(u, v) := {j : (u, v, j) ∈ T }.Use SUBDEGREES(≺, L) to compute d(u|G(v)), ∀(u, v) ∈ L.Init empty list L * .Init dictionary J * mapping each (u, v) ∈ L to an empty list.Init dictionary D * :V 2 × [n] → V 2 × [n] 9:for every (u, v) ∈ L and every j ∈ J(u, v) do 10:Find the largest (u, v ′ ) in L(u, v) such that d(u|G(v ′ )) -d(u|G(v)) + j ≥ 1.11:j ′ ← d(u|G(v ′ )) -d(u|G(v)) + j 12: Append (u, v ′ ) to L * 13: Append j ′ to J * (u, v ′ ) 14: D * (u, v, j) ← (u, v ′ , j ′ ) 15:Sort L * by ≺ and remove duplicaes 16:For each (u, v) ∈ L * , sort J * (u, v) in increasing order and remove duplicates 17:Init dictionary D :V 2 × [n] → E(G) 18: for each (u, v) ∈ L * do 19: init a counter c u,v = 0 20:for each orientation (u, v) of every edge in the stream do21: if ∃(u, v) ∈ L * with (u, v) ⪯ (u, v) then 22:Let (u, v) be the largest such pair 23:c u,v ← c u,v + 1 24:if the first element j of J * (u, v) is j = c u,v then 25:Set D(u, v, j) ← {u, v} 26:Delete j from the head of J * (u, v) Define dictionary F :V 2 × [n] → E(G) s.t. F (u, v, j) := D(D * (u, v, j)).return dictionary F For each i = 1, . . . , h, let E i (u, G(v)) be the subset of E(u, G(v)) formed by all edges (u, w) wherev i ⪯ w ≺ v i+1 (for i = h just consider v i ⪯ w). Clearly, the sets E i (u, G(v)) form a partition of E(u, G(v)); in fact, E i (u, G(v)) = E(u, G(v i )) \ E(u, G(v i+1 ))with again the exceptionE h (u, G(v)) = E(u, G(v h )).The order on E(u, G(v) is given as follows. Start with the elements of E 1 (u, G(v)) in the order they appear in the stream. Then, add the elements of E 2 (u, G(v)) in the order they appear in the stream, and so on until E h (u, G(v)). Note that this order depends only on the pairs (u, v) ∈ L, and on the order of the edges in the stream.Note that if j is uniform at random in {1, . . . , d(u|G(v))}, and independent from both L and the stream, then the j-th edge e j in that order is uniform at random in E(u, G(v)).E ij (u, G(v))that contains e j . By standard computations,i j = max{i : d(u|G(v i )) -d(u|G(v)) + j ≥ 1}Note that i j depends only on j, and on the sizes of the sets E i (u, G(v)), and not on the order of the elements in the stream. The vertex v ij is precisely the vertex v ′ computed by the algorithm at line 9. Moreover, the index j ′ computed at the same line is precisely:j ′ = j -d(u|G(v)) + d(u|G(v j ))It follows that, if we map (u, v) to the j ′ -th edge of E ij (u, G(v)) that appears in the stream, which is e j , then the algorithm is correct. This is precisely what the algorithm does in the loop of line 20. The counter c uv keeps track, for every i = 1, . . . , h as above, of the number of edges of E i (u, G(v)) seen so far; when c uv matches some j, it maps (u, v) to e j , as desired.Lemma 4.1. Given a graph G = (V, E), α ∈ (0, 1), any q-pass streaming algorithm computing a node v such that δ G (v) ≥ α max w∈V δ G (w) with probability at least 2 3 , requires memoryΩ α 2 |V | q .Proof. Let A be a q-pass s-space streaming algorithm for computing a vertex with degree being at least a fraction of α of the maximum degree. Without loss of generality, we assume that A computes its degree as well (as one additional pass and O(log n) memory suffices to compute the degree of a given node). We will use A to obtain a multi-agent protocol for the disjointness problem.Let t = ⌈ 1 α ⌉ + 1 be the number of agents in a one-way multi-party communication protocol. Recall that in the disjointness problem, we may assume that either the supports of the bit vectors are pairwise disjoint (NO instance) or they share one common element but are otherwise disjoint (YES instance). From the n-bit vectors from the t agents, we obtain a data stream of a bipartite graph G = (U, V, E) as follows.• V = {v 1 , . . . , v n } corresponding to the n bits • For each agent i, we introduce a set of vertices and edges associated with i as follows.For every x i , for every j ∈ [n] s.t. x ij = 1, there is a node u ij ∈ U as well as an edge (u ij , v j ) ∈ E.• The edges are arranged in the stream so that the edges associated with a same agent i appear next to each other in the stream while preceding the edges associated with agent i + 1. In other words, (u ij , v j ) precedes (u ℓ h , v h ) in the stream if i < ℓ, with all other edges being arranged in an arbitrary order.The protocol for the disjointness problem simulates A as follows. The first player executes A on the set of edges associated with her, i.e. {(u 1j , v j ) : j ∈ [n], (u 1j , v j ) ∈ E}. Then, she sends her memory snapshot (with size O(s)) to the second player that continues the execution of A on the set of edges {(u 2j , v j ) : j ∈ [n], (u 2j , v j ) ∈ E}. The second player in turn sends her memory snapshot to the third player and so forth until reaching the t-th player, which sends her memory snapshot back to the the 1st player. This procedure is iterated q times at the end of which the t-th player outputs "YES" if the degree of the node computed by A is ≥ 2, and "NO" otherwise.Such a protocol is a correct protocol for the disjointness problem, in that, by construction, the maximum degree of any node in G is either t ( in the YES instance ) or 1 ( in the NO instance ). Hence, with probability at least 2 3 , in a YES instance A finds a node with degree at least α • t > 1, while in a NO instance such a node has degree 1.Observe that the number of vertices in the bipartite graph is at least n = |V | while it holds that|U | + |V | = O(t + n) = O(n). Moreover, the communication cost |Π| of the protocol satisfies |Π| = O(s • t • q) = O s•q αby our arguments, and |Π| = Ω n t = Ω(αn) by the bounds above. From this, we derive s ∈ Ω α 2 n q . Lemma 4.2. Given a graph G = (V, E), k ≥ 3, any q-pass streaming algorithm for the uniform k-graphlet sampling problem on G requires memory Ω |V | q .Proof. We use the same construction of Lemma 4.1 while letting t = k -1. In such a case, a "NO" instance for the disjointness problem corresponds to a graph with maximum degree one (with each connected component consisting of either a singleton or a single edge), while a "YES" instance corresponds to a graph containing a connected component being a star with t + 1 = k nodes, with all other connected components having maximum degree one. Observe there is exactly one k-graphlet in the "YES" instance, with no k-graphlet in the "NO" instance. As a result, any streaming algorithm succeeding in sampling uniformly a k-graphlet with probability δ would also solve the disjointness problem.In this section we introduce a heuristic approach to substitute APPROX-DD, which efficiently reduces the number of passes while preserving the probabilistic upper bounds in Theorem 3.1.The heuristic approach aims to extract a large subgraph of high-degree vertices into memory, so that it can run a simple greedy algorithm that removes the vertex with the largest degree in each iteration without requiring any additional passes. The process starts from finding this subgraph and determining whether running the heuristic is worthwhile. First, we sort vertices in descending order of d(v|G). Let the sorted vertex list be v1 , • • • , v |V (G)| . We use a streaming pass to compute d(v i | Ḡ(v i )) for each vertex v i , where Ḡ(v i ) represents the induced subgraph of the prefix v 1 , • • • , v i . We know that i j=1 d(v j | Ḡ(v j ))is the number of edges in Ḡ(v i ). Let i * be the largest i such that edges in Ḡ(v i ) can be stored in memory, i.e.,i j=1 d(v j | Ḡ(v j )) ≤ M . If i * = |V (G)| or d(v i * +1 |G) ≤ ∆ 1+α, we run the heuristic algorithm PEEL-HEURISTIC instead, otherwise we still run PEEL.In PEEL-HEURISTIC, we first use a streaming pass to record all edges in Ḡ(v i * ). Then we repeatedly select the vertex v in Ḡ(v i * ) with the maximum d(v|G), append it to the DD order, remove it from Ḡ(v i * ) and update d(v ′ |G) for all vertices v ′ ∈ G(v i * ) that are connected to v. We continue this process until d(v|G) of every remaining vertex v in Ḡ(v i * ) are less thand(v i * +1 |G) 1+ϵ.The idea is summarized in Algorithm 8.It is easy to see that whenever we append v to L, it holds that d(v|G(v)) = d(v|G) ≥ d(u|G) = d(u|G(v)) for each u ∈ Ḡ(v i * ), and d(v|G(v)) ≥ d(v i * +1 |G) 1+ϵ ≥ d(vj |G(v)) 1+ϵfor each v j where j > i * , therefore the final order we obtain is indeed a 1 1+ϵ -DD order. Note that after an execution of PEEL-HEURISTIC, the degrees of all remaining vertices are no greater than d(v i * +1 |G) ≤ ∆ 1+α . This means that PEEL-HEURISTIC performs no worse than PEEL if the condition in line 9 is satisfied, and Theorem 3.1 still bounds the number of passes for APPROX-DD-HEURISTIC. However, since PEEL-HEURISTIC only requires 3 passes on average, and it removes more vertices and reduces the maximum degree more effectively than PEEL in sparse graphs, APPROX-DD-HEURISTIC performs much better than APPROX-DD in practice.Algorithm 8 Approximate DD order heuristically. The lines marked with a ▷ entail a streaming pass.1: function APPROX-DD-HEURISTIC(G, ϵ) for each v ′ ∈ P such that (v, v ′ ) ∈ E(P ) do 24:2: L ← empty list 3: α ← ϵ 2 4: while V (G) ̸ = ∅ do 5: compute d(v|G) for all v ∈ V (G) ▷ 6: v 1 , • • • , v |V (G)| ← the sorted list of V (G) in descending order of d(v|G) 7: compute d(v i | Ḡ(v i )) for each i ∈ [|V (G)|] ▷ 8: i * ← max{i| i j=1 d(v j | Ḡ(v j )) ≤ M } 9: if i * = |V (G)| ∨ d(v i * +1 |G) ≤ ∆ 1+α then 10: b ← d(v i * +1 |G) 1+ϵ if i * < |V (G)| otherwise 0 11: (G, L) ← PEEL-HEURISTIC(G, {v 1 , • • • , v i * }, b, ϵ, L) 12:d(v ′ |G) ← d(v ′ |G) -1 25: return (G, L)NeurIPS Paper Checklist 1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: Our setting and contributions including the upper bounds and lower bounds of the number of passes, time complexity and memory complexity were stated in the abstract and the introduction. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.We need k = o(log n), otherwise the bounds become vacuous. This is not a drawback of STREAM-UGS: all known algorithms pay a factor k O(k) in their guarantees.In this work, "high probability" means probability 1 -n -c where c > 0 is arbitrarily large but fixed.https://github.com/l2l7l9p/UGS-Streaminghttp://konect.cc/networks/ 


Decision: This paper gives an algorithm (and an almost matching lower bound) for the problem of sampling a connected k-vertex subgraph (graphlet) from a large graph in the semi-streaming model, where the algorithm is allowed to do several passes over the whole set of edges but can use only O(n log n) memory (where n denotes the number of nodes). The reviewers appreciate the interesting and nontrivial theoretical insights used to proved the main result, as well as the fact that it is supported by experiments. There are no major weaknesses that are not eventually addressed in the rebuttal. The only serious concern left is whether NeurIPS is the right venue for a graph mining paper. The authors mention several ML-related applications in their rebuttal, and I expect them to elaborate further on these applications in the camera-ready version.

Reviews: review: paper_summary: paper_summary: This paper studies uniform sampling of k-graphlets. Authors exttend UGS to the semi-streaming setting, and propose an time and space efficient framework that samples uniform k-grpahlets w.h.p. Authors also provide a lower bound on the memory requirement of any streaming algorithm for uniform k-graphlet sampling via the randomized communication model.Finally they conduct experiments on large scale dataset to verify the effectiveness.
strength_weakness: strength_weakness: In the related work, More sentences can be used to describe the UGS algorithm, especially the second phase. Currently there is no connection between the topological order and the sampling phase. Also random communication complexity can be introduced as it's the tool used for the lower bound proof.

Enlarge the font size of Figure legends.
questions: questions: Given any G, there should always be a node v at the end of the order, such that G(v) is only this node itself right? In that sense $d(v|G(v))=0$ that violates def 2.1. 

I agree with authors that DD order is not reverse of core order,
limitations: limitations: NA
paper_summary: paper_summary: Given a graph $G$, a $k$-graphlet is any connected subgraph on $k$ vertices. Orthogonal to sampling instances of isomorphism types of subgraphs (e.g., triangles), graphlet sampling asks to sample a connected subgraph of a specific size. In an offline setting, Uniform Graphlet Sampling (UGS) solves this problem in $k^{O(k)} \log n$ expected time with $O(nk^2 \log k + m)$ preprocessing time. The authors in this paper propose a semi-streaming version of UGS that uses $O(\log n)$ passes for preprocessing, and can repeatedly sample $\tilde{\Theta}(n / k^{O(k)})$ graphlets uniformly at random using $O(k)$ passes. The running time of the preprocessing is essentially linear in its passes, and the sampling runs $\tilde{O}(n 2^k + mk)$ time.

UGS relies on a total ordering of the vertices so that for any two vertices $u > v$, the degree of $u$ is at most the degree of $v$ in the graph induced by all $w$ such that $w \geq v$. In a streaming setting, the challenge of constructing such an ordering is storing a representation of these induced graphs is to costly. To remedy this problem, the authors relax the guarantees of the ordering by scaling the degree of $u$ by some parameter $\vartheta \in (0,1]$. The authors show that one can construct such an ordering by bucketizing the vertices by degree and carfully partitioning the buckets into sparse induced subgraphs, which correspond to intervals in this ordering. The second building block of the algorithm is a rejection sampling scheme that can be run in parallel on top of the ordering.

The authors develop a heuristic version of their algorithm and evaluate both versions experimentally. It shows that the heuristic version seems to perform significantly better on sparse graphs. On large real-world sparse graphs, the heuristic version has an much larger heuristic success probability. It uses roughly 30 passes on the Friendster and Twitter graphs to sample 100 graphlets.
strength_weakness: strength_weakness: While it can provide strong guarantees for dense graphs, the semi-streaming model has limited applications for sparse graphs. It's not entirely clear whether $\Omega(\log n + k)$ semi-streaming passes on a sparse graph have as many applications as in the dense graph model.
questions: questions: Could you elaborate on applications where $\log n$ passes are clearly superior to the potentially small increase of footprint for storing the whole graph in memory?
limitations: limitations: /
paper_summary: paper_summary: The paper presents algorithms for sampling a connected subgraph on k nodes, the so called k-graphlets, from a massive graph revealed as a stream of edges in arbitrary order. The algorithms work in the semi-streaming model of computation where one can only use linear space in the number of nodes. The algorithms are allowed several passes over the graph and sample k-graphlets uniformly at random. The computational complexity of the approach and the sampling guarantees are formally analyzed and several theorems show that the approach has a nearly optimal computational complexity.
strength_weakness: strength_weakness: Overall, I am not convinced that NeurIPS is the right venue for a graph mining paper. The weaknesses listed below are in the context of this context. 

- There is no attempt to connect the results to machine learning applications. Clearly, from an algorithmic point of view, uniform sampling of k-graphlets is an important problem. But does it yield anything useful for downstream applications? Maybe the k-graphlet distribution is dominated by k-paths and one would need many samples in order to estimate the distribution of the different kinds of k-graphlets that is necessary for graph classification algorithms to yield good results.
- I understand this is the first algorithm for the problem but I still believe it can be compared to some heuristics in order to show the advantages of uniform sampling. Off the top of my head, I can think of the monochromatic sampling approach by Pagh and Tsourakakis. For a sparsified graph, count the number of k-graphlets. The approach will not guarantee uniform sampling but might still yield useful estimates and might be more efficient.
questions: questions: Comment on the above weaknesses. How would you convince a machine learning researcher to read your paper?
limitations: limitations: The limitations are correctly addressed from an algorithmic point of view. But no attempt is made to consider the limitations when applying the approach in a machine learning setting, for example graph classification.

Comments: title: Response to author's rebuttal
comment: Yes, I agree, in practice there's a sharp instead of an asymptotic threshold where the input doesn't fit into memory any more, and theoretical graph models like sparse or dense graphs are less important. Thank you for taking the time to answer the rebuttal!
Thank you for your response!
I thank the authors for their response. Again, this is a strong paper and if the authors indeed put some effort into bridging the gap between algorithmic data mining and machine learning, I think it should be accepted. I am raising my score, I guess it is now in the hands of the area chair to decide if the paper would be interesting to the NeurIPS community.
You are correct that if the sparse graphs can be fit into the memory, then the semi-streaming model would not provide any benefit.  However, in practice the constants matter; for instance, if the memory is sufficient only to store half of the graph, then our approach will still make sense.
Thank you for your response! I agree with the application scenario, and actually I wouldn't challenge the advantages of semi-streaming for dense graphs. Am I further reading and combining the two parts of the answer correctly if I understand the following: The theoretical guarantees of the algorithm provide no clear benefit for sparse graphs over an offline algorithm that stores the graphs in memory. The point you make is that one may still use your algorithm for sparse graphs without worrying, though, as the experiments show good performance for the sparse instance.