Efficient Streaming Algorithms for Graphlet Sampling
Authors: Yann Bourreau
Marco Bressan
T-H. Hubert Chan
Qipeng Kuang
Mauro Sozio
Venue: NeurIPS 2024 poster (2024)
Keywords: graphlet sampling
streaming
approximation algorithms
Primary area: other
TL;DR: We have developed an efficient algorithm that enables random and uniform sampling of graphlets from large input graphs in the semi-streaming setting with limited memory.

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.

Efficient Streaming Algorithms for Graphlet Sampling
Yann Bourreau'
Marco Bressan
Cispa Helmholtz Center for Information Security
Department of Computer Science
Saarland University
University of Milan Milan, Italy
Saarbrücken, Germany
yann. bourreau@cispa.de
marco. bressanounimi. iit
T-H. Hubert Chan
Qipeng Kuang
Department of Computer Science The University of Hong Kong Hong Kong, China hubert@cs. hku. hk
Department of Computer Science
The University of Hong Kong
Hong Kong, China kuanggipeng&cconeet hku. hk
Mauro Sozio
Institut Polytechnique de Paris, Télécom Paris
Palaiseau, France
cozio@telecom.paris..o
Abstract
Given graph G and a positive integer k. the Graphlet Sampling problem asks sample 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 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 Onkk log k + m), and draws one sample in expected time {P(A) log n, where IV(G)) and input graph fits into main memory and does not seem to be straightforward to adapt very large graphs. We consider Graphlet Sampling in the semi-streaming setting, where we have a memory of M 2(n log n) words, and can be only read through sequential passes over the edge list. We develop remi-streaming algorithm that preprocesses G in p O(log n) passes and samples O O(MK O(k) independent uniform l- E-graphlets in O passes. For constant k. both phases run in time (( + m) log n.). We also show that the tradcoff 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.
[EG) Such algorithm relies on the assumption that the
Introduction
Sampling and counting small subgraphs in large graphs is central problem in graph mining and machine learning. Let G = (V, F.) be simple graph (where = [V] and m [E and k: an integer. A k-graphlet of G is 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 graph [MSO] and can be transformed into the
Authors appear in alphabetical order.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

feature vector for graph classification and subgraph identification ITL 19). Graphlet information also contributes to neural network in several ways. 20] converted the graph to a matrix by sampling k-graphlets for sequence of vertices so that convolutional neural networks can be applied. 191 showed that using graphlet frequency as a node attribute improves the performance of 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 consequence, sampling k-graphlets uniformly at random from G has become key primitive in graph mining and machine learning. This problem is called Graphlet Sampling, and many algorithms have been proposed for it [ABH19] BIRAH1R
inffusion-convoluttin
BCK 17, BCK + 18 BL.P1
BLP21 CLWL16 HST6 MG20 PSS19 SHI5
14]
In this work we give efficient streaming algorithus 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 arbitrary order that is unknown to the algorithm. Each scan of the list is called pass. Second, the algorithm is only granted M = o[[G)) words of memory of (log n) bits each, where -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 that is not necessarily connected is straightforward: just sample a k-vertex set S C V and return G[S). The problem becomes nontrivial, though, when the subgraph must be connected (i.c., 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 decade, all known rejection sampling techniques had worst-case running time of ((n*), or sampled from a nonuniform distribution [BRRAHI2] WLR+ 14, SHI5 BLP19 BLP It was then shown that both issues can be avoided by using a simple wwo-phase algorithm, UGS (Uniform Graphlet Sampler) [Bre2 la Bre23). The key idea behind UGS is to sort G topologically by repeatedly deleting a vertex of maximum degree; this takes time Onk log k + m) where m |.]. Afterwards, one chooses a starting vertex e according to a certain distribution computed from the topological order, creates a k-graphlet g by exploring the graph surrounding e with vertices topologically no smaller than v in randomized way, and accepts g with a certain probability (otherwise, the process 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()) log n.
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 mixiiuum-degres 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 passes in total, which is unacceptable. In this work we show how to overcome these kind of obstacles. We obtain an algorithm that in Ö(log r)) passes computes an approximate topological order of G, and afterwards can sample ((M/k0(k) independent uniform random graphlets every O(k) passes, as long as the algorithm has M 2(kn) words of memory. We make several other nontrivial improvements that has practical impacts. For instance, while deciding if each vertex is contained in sized-k graphlet takes A passes in straightforward implementation. we show how to do that in only 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 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 Om 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 Q (") therefore, our algorithm is
2

---

nearly space-optimal. Finally, we conduct a series of experiments which verify the relation between several metries and the parameters of the algorithm.
1.1 Contributions
An efficient streaming algorithm for graphlet sampling, We present STREAM-UGS, a graphlet sampling algorithm with the following formal guarantees:
Theorem 1.1. In the semi-streaming model with k = o(log n) and M words of memory satisfying (n log n) S M o(m), STREAM- UUG satisfies the following The preprocessing phase makes Sanalittyyyane and has running time Oppm + n n2 lg k). The sampling phase makes 2k passes, returns O OMM oTk) independent uniform k-graphlets from G with high probability, and runs in time (n 2 log n + m.k n)).
p= O n) passes with high probability
It is useful to instantiate Theorem 1.1 with k- = O(1) For example, A = 3,4,5 is common in the literature. In this case STREAM- UGS makes Ollog ri) preprocessing passes; afterwards, every (1) passes it returns a batch of Ω2n log n) random uniform k- k-graphlets of G. Both preprocessing and sampling take time (( log n.). Note that the sampling phase can be repeated arbitrarily many times; every execution yields new batch of independent uniform k-graphlets.
Tradeoff Between Memory and Number of Passes. We remark that Theorem 1.1 is a special case of a more general tradeoff that we prove between the number of passes, the memory size, and the number of graphlets returned. For example, if M (2(kn) then STREAM- UGS still works, but the number of preprocessing passes becomes Ologg log log nt), or the number of graphlets sampled decreases by a factor O log" (n)). From a technical standpoint, STREAM-UGS relies several ingredients. The first one is (log ppss streaming algorithm for computing the said approximate topological order. The second a 1-pass routine for computing, simultaneously from each vertex, a truncated breadth-firt search to detect those vertices that do not lead to any graphlet. The third is scheme for running instances of the sampling phase parallel without duplicating the stream across all instances. All these results are detailed in Section 3
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 2 3, any p-pass streaming algorithm for Graphlet Sampling requires (1/p) bits of memory.
We also give 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
Experimental evaluation. We conduct 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 valuable tool in graph mining.
1.2 Related Work
Most streaming algorithms for counting or sampling k- k-graphlets are specifically developed for counting or sampling triangles. and do not give guarantees for [BYKS02] BBCG08 PTTWI3
ADNK JSPTS /
The only algorithms that count 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 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- k-graphlet sampling.
The only algorithm comparable to ours MOTIVO [BLP19] which based on the celebrated color-coding technique of Alon, Yuster and Zwick. MOTIVO has a preprocessing phase and
We need k = o(log n), otherwise the bounds become vacuous. This is not drawback of STREAM-UGS: all known algorithms pay a factor (O(k) in their guarantces.
In this work, "high probability" means probability 1 - n where 0 is arbitrarily large but fixed.
3

---

sampling phase, and they can be implemented in O(k) passes over G using memory M = ((c n) for some с 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 & [LP11]] while STREAM-UGE 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 uugrraph-coumtin algorithms [MB83 CN85 Bbe2 22], and for which efficient streaming algorithms exist [BKV12] SGJSS 13). However, while core order is obtained by repeatedly removing from G 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 he the reversal of the other. turns out that this resemblance 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 (())) unless the widely-accepted Exponential Time Hypothesis fails (CHKX06) Graphlet Sampling instead can be solved in FPT time, that is, time f(k) n 01), as Bre2 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 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
2 Preliminaries
Let G (V, F)) be simple graph. We assume V = (1, (1,...,n) n). For a total order < over V, G(v) to denote the subgraph of G induced by {u u 2 U). i.c. the subset of vertices containing and all vertices after v in <. Given u V we let A(u)G(()
{w m v {u, w] E E}} be the neighborhood of u in G(u), and ((v])(())) [[)))(()) be the degree of u in G(t). We denote by A the maximum degree of G. The following notion will be crucial:
Definition 2.1 (V-DD Order). Let 1 E (0, 1]. total order - over V is d-degree-dominating order (0-DD order) if. for all v E V with d(v G(v))
> 1 and all u 2 e, we have d( G(v))(u)) 2 8-d(u G()).
The topological order used by UGS [Bre23] is a 1-DD order. A Í-DD order is an approximation of 1-DD order. Using 9-DD order yields the same guarantees of UGS, only with an acceptance probability scaled by g (see Lemma C.I
Computational model. The algorithm has memory of M words of ((log bits each. We require M = [()) or M = O( 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 [5)M+05) To avoid trivialities we assume m = R(M): otherwise, in one pass one can store G and run the algorithm of [re23). For computation we assume the standard RAM model. We also assume that in time ((1) one can draw a random uniform integer in (1....,c) c) for any e = pnly(n), or a Bernoulli random variable (p) for p = 2(n When we run multiple instances of subroutine in parallel, the running time is understood be the total number of operations executed by all those instances.
Graphlet size. Our algorithms are designed primarily for k O()) but they yield nontrivial guarantees also for t = ()); for instance, for k = vlog n. Our full statements make the dependence on l 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 dn leaves and ò2-clique. 6, > dz. then the center of the star comes first in a 1-DD order, but in core order it sits after the

---

star's leaves and before the clique vertices. If 02 > 81, 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 d2 51 vertices of the clique.
3 A Streaming-Basee Graphlet Sampling Algorithm
This section describes semi-streaming algorithm, STREAM -TR. 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.
Pl Computing a 9-DD order < of G. The order defines implicitly the subgraphs G(v), see Section 2 as well certain distribution 5 over V that is needed by the sampling phase, see below.
P2 Computing the said probability distribution ş on V. Let ((v) be the set of all graphlets that are subgraphs of G(u) and contain v. This is called the bucket of v. The distribution p can be seen as a distribution over the buckets (vv). For every v E V, the probability p(v) is proportional to di( d(c]GG(v) (( if (vv # 0, 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 uniformly random k- k-graphlet of G. The expected number of trials to successfully return a graphler is 0 k0(k), However, with enough memory, one can carry out independent trials in parallel. The phase consists of three steps.
S1 Choosing a bucket (vv) according to the probability distribution 1.. One can show that, if g(v) * 0, then [9(v) equals d(u|G(v)))*+) up to factors 100()) Thus, we are choosing buckets with probability roughly proportional to the number of k-graphlets in them.
S2 Sampling random graphlet G]S) E (vv). To this end let Si {v). For i 1, 2,2..... 2....,k-1 k- 1, draw an edge uniformly at random from the cut between S; and G(v). and add the endpoint to S this gives S,+1- The final set S S₁ 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.
Technical Challenges. In the semi-streaming setting, we cannot store all the edges of G in the memory. Our contributions are how implement each of the above steps with restricted memory using a small number of passes on the edge list.
3.1 Computing a 9-DD order
We present algorithm, APPROX-DD (Algorithm O(1), computes V-DD order of G, where l+c' Our main result is:
1 that given a graph G and a parameter 0 <
Theorem 3.1. In the semi-streaming model, APPROX-DD can be implemented so that with proba- bility at least n -01), makes q = O e²
log
logn e
passes if M 12(n), and q = O logn
passes if M = Q log
In both cases the total running time is in O(g m))
The complete proof of Theorem 3.1 combines several technical lemmas and can be found in Ap- pendix A The rest of this section overviews APPROX-DD and sketches the proof. APPROX-DD maintains list T., 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 I+a' for some appropriate any order; is carefully computed by another procedure, called shaving, using random partitioning. Algorithm ] gives the pseudocode of APPROX-DD DD. It assumes that 8G(-), and all other degrees, are updated as soon as the graphs are modified: except for A, which explicitly recomputed when needed. In practice, updating the degrees amounts to running one pass over the edges of G. The algorithm has triply nested loop structure, and we use the subroutines PEEL and SHAVE for clearer illustration.
A
and places them in L in the right order. This "right order" is not simply
5

---

Algorithm Approximate DD Order. The lines marked with degrees and, thus, one streaming pass.
>> entail a recomputation of the
1: function APPROX-DD(G,
2: L f empty list
3: while V(G) + do
4: LG. < eEEL(G,
5: return L
6: function PEEL(G, L)
7:
Á f max d(v|G)
8:
at 5
9:
H {u V(G) ([G):d(v[G)) A
while + 0 do
11:
(G, I, H) < C H,
return L)
13:
function SHAVE(G, A,
14:
B 4 242r4e2 ( + [2(1 By1
Hi... ...... He be uniform random partition of let R4 t- {u H, d[c[G[H.) s 1481 for [4]
16:
17:
for i = 1.....,, do
18:
1+a append the vertices of S, to L in arbitrary order G G
S; + {uE R² d(ulG) 2 A
19:
20:
H H R, return LG, H)
Intuition for PEEL and SHAVE. Let be the subset of vertices with degree at least Ita in G (line 9h. As first attempt, we could remove all vertices H from G in single batch, which is appended to L in arbitrary order. This works if every vertex u has all of its neighbors come after itself in L, since in that case d(v] Z 1ta A Z ltt d(v)(())) for all u Z v. However, in general this does not happen.
To this end, we attempt to remove vertices in H from G phases through SHAVE. Specifically, we assign each vertex in H to one of { = [2 B)] batches H1,- .1,.... H; independently and uniformly at random. By Markov's inequality, each vertex has at most A
T+ neighbors within H; with good A
probability; then, in phase i, every such vertex in H; that has current degree at least Ita will be removed together in one batch from (and appended to 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 it removes only the vertices that have few neighbors in the same subset H,. To completely remove H, we need to iterate the procedure. This is what PEEL does at line I0 We shall see that there are two cases. When A is large enough, then one call to SHAVE in line will be sufficient to make H empty with high probability. When small, we may instead need Olog n) calls to SHAVE in order for H to become empty. This is, technically speaking, what makes the whole algorithm APPROX-DD -DD efficient. Formally, prove the following (in Appendix A
Lemma 3.2. Let (0, With probability at least 1 p. execution of PEEL (Algorithm) 7 calls SHAVE O log 2) times, and at most once if A > 12(1 + a) + 3) In

---

3.2 Finding the Non-Empty Buckets
Algorithm 2 gives the pseudocode of COMPUTEDISTRIB, which computes the distribution p and the normalization constant I needed by the sampling phase. As said above, the crux of COMPUTEDISTRIB checking if (()) * 0 for each v E V. To this end, suffices to perform BFS on all vertices in parallel, as to check whether the connected component of in G(v) has size at least A naive method would take & passes on the edge list, but with (2(km) words of memory, we can achieve this in 1 passes, Lemma 3.3 proves.
Algorithm 2 COMPUTEDISTRIB
1: function COMPUTEDISTRIBCH
2: for each E V do
3: compute d(v G(v)) and 1, = Lo())
4: set set by + L. -(oo]G(e))
5: set Z + Everbe by
6:
compute probability vector p. for each e E V. V.p(v) +
7: set I' + (I-1)
8:
return (p,1)
Lemma 3.3.
the steiinggeuming model with M (kkn), the routine COMPUTEDISTRIB (Algo-
rithm 2 can be implemented so to use 1 pusses and time O(m + n 122 log k).
3.3 Sampling Graphlets in Parallel
Algorithm 3 gives the pseudocode of SAMPLE, the sampling phase of STREAM-UGS. The sam- pling phase works after invoking APPROX-DD and COMPUTEDISTRIB in turn (see the subroutine PREPROCESS Algorithm 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,,²), then with memory of M words we can perform ((M/k²) independent sampling trials in parallel. Doing so efficiently, though, 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 OMM parallel instances of SAMPLE can be run in a batch so that Q/k((k) ((M))) independent uniform random k- k-graphlets of G are returned successfully with high probability. Moreover each batch can be implemented in two ways:
The first one takes le passes and (MM) time.
TThe second one takes 2k: passes and O(M2 k + kr log n) time.
Proof Intuition. Each instance of SAMPLE requires only O(k2) words of memory. Hence, with memory M, we can run Q = OMM/k)) parallel instances of SAMPLE. By Lemma C.1 each instance
independently returns uniform random k- A-graphlet with probability least à (1+e)*-I O(k) By standard concentration bounds, then, with high probability the number of uniform random k-graphlets returned overall is ((M ((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 cettmoptimal. To this end, we use well known results from communication complexity. In the multi-party randomized communication model (CKS03 BJKS04), there are 2 2 players seeking to compute a function : X; x X2 ... X4 + y while exchanging messages according to specified protocol TI. For each i E [1], the i-th player has an input x; E X. Given ..,...,22 Tz, the random variable [x))...., denotes the message transcript (containing all messages) obtained when all players follow II on
7

---

Algorithm 3 SAMPLE (Abstract Description)
1: function SAMPLE(<,) T)
x is used to define G(v).
2: Sample e from the distribution p.
3: S <- RRAND--GROW GROD-G,O(W;, x)
4: qs f PROB(U, S, -
5: With probability pla return S;
6: Otherwise, return "failure"
7:
function RAND-GROW(;, =)
8:
S1 - {u} for i = --.....,-11 do
9:
let Eg be the subset of edges in G(v) with exactly one endpoint in S., sample an edge {u, n'} uniformly at random from E,, where E S; and u' $ S.
11:
S1+1 + S, U {n'}
13:
return S
14: function PROB(U, S. <)
15:
for i = 1,... do
Qi f- an empty map from (i) to R with default value 91 (1((1)) t
17:
18:
for = 2....,ku do
19:
for each S E ($) and each w E S; do
20:
n, f number of neighbors of w in S,
21:
q - E>ss (d(z[G(u)) - d(z \ {wHl))
22:
(S,) + (S,) (S; {w})-
23:
return (S)
inputs FT, Le. where the randomness is over the coins of the players. II is a 5-error protocol for f if there deterministic function Tour such that, for all inputs 3 ..,
Pr (oow (
= f 21-8
(1)
The communication cost of II, denoted by [II], is the maximum length of II(II,..., over all Ti,,.. ,.,,,., Tt and over all random choices of all players. The d-error randomized communication complexity of ff is the cost of the best d-error protocol for f. In the one-way variant of such model, the ith player sends exactly one message to the + 1)th player, throughout the protocol (we let ++ = 1).
In the classical disjointness problem, the ith player has n-bit vector (. T.. ) (0, 1}" 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 such that 2; all E [4]. It is known that this problem has Q(n/t) communication complexity in the one-way multi- parti-pprtt 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 unique common element but are otherwise pairwise disjoint.
for
We show that any g-pass streaming algorithm requires memory M ((n/g) even for the problem of computing node with approximate maximum degree, that is, to compute node with rank in an approximate DD-order. We believe such result is well-known, however, we could not find reference for a general g-pass algorithm. For completeness, we provide the full proofs Appendix D Lemma 4.1. Given a graph G = E), a E (0, 1), any q-pass streaming algorithm computing node v such that (v) 2 a max (w( with probability at least 3. requires memory Ω [
Finally, we provide a lower bound on the memory requirement of any streaming algorithm for uniform l- k-graphlet sampling, & 2 3.
Lemma 4.2. Given a graph G = (V, k 2 3, any q-pass streaming algorithm for the uniform k-gruphlet sampling problem on G requires memory Q V

---

Dataset
File Size (MB)
#Vertices
#Edges
Dense
1,858
20,000
159,993,472
NY Times [un13
858
401,388
69,654,798
Twitter (WWW) Kun 13 (LPMIQ
20,437
41,652,230
1,202,513,047
Twitter (MPI) [un 13 CHBGIQ
25,590
52,579,682
1,614, 1614,106,11 188
Friendster [3
32,300
68,349,466
1,811,849,88
Table 1: Dataset statistics. Dense is generated synthetically by drawing each edge with probability 0.8, and other four datasets are from KONECT.
5
Experiments
We implemented our algorithms in Python 3.9 and conducted experiments on a Ubuntu server with CPU Intel Xeon Silver 4108 (1880GH2) and 28GB RAM. The implementation can be found in the online repository.
Datasets. We run experiments several real-world graphs from the KONECT website [Kun 13 and a synthetic random dense graph generated by drawing each edge with probability 0.8 (we name 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 repports all dataset statistics after such a preprocessing phase.
Streaming model. The stream of edges comes from 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 2 1 passes and O(M2* + km log 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 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 metries as 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.
Heuristic Approach for PEEL We develop heuristic approach called HERRO-DDD-HURRITTIE in Appendix [ to speed up the running time of Algorithm We evaluate SERROX-DD--EURRISTE on large real-world graphs show the scalability of our algorithms and then conduct comparison between APPROX-DD and APPROX- DDEOX---D-HEURSTTT on smaller graphs
APPROX-DD versus APPROX-DD -D-DDDDHEEE HED--ITEUISCC We conduct the comparison between APPROX-DD and APPROX-DD-HEURISTIE on NY Times, the real-world sparse graph and Dense, the synthetic dense graph. Figure shows the number of passes and memory usage function of c.
In Figure Ta and we can see that APPROX- DD- HEURISTIC delivers significantly better re- sults 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 e, while the number of passes for sampling increases. Concerning APPROX-DO BEEXX-DD-HEURREE HE---HEEUSSCC both the number of passes and memory usage are less sensitive to e since in APPROX- more important role.
the amount of available memory plays
As observed, APPROX DOPROX-DD-EER DE-RRISIIT outperforms APPROX-DD on real-world sparse graphs. Hence, we will focus our attention on APPROX -DE--DD--HUSSTCC in the following experiment.
Running on Large Graphs. Figure 2 shows several metrics function of and k over real-world large graphs. Figure [a 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 22c [ show the number of trials to obtain 100 graphlets as a function of e and k respectively. Observe that the success probability significantly higher than the worst-case bound provided by
httper//gtthub.com//////g htt.
http:://oonet..cc/eettvxzz

---

730
-8- ADS Tael
Peprectsingg
630
ACD Samolio
350-
2300
Momory (148)
330-
630
A70 Samphrr
230
220
220
Num
150-
270
Canu
RrTima A604
(a) NY Times
(b) Dense
(c) Memory Usage
Figure 1:
The number of passes versus e on NY Times (aa. on Dense (b). and the memory
versus on two datasets (Tc). fixing & 4. ADD stands for APPROX-DD and ADD-H stands for
APPROX-DD DD-HEURISTIC.
20-
Twilistenn
Twitnnetti Prurocesann
0.5
2.0
15
2.0
25
300
(a) #Pass VS
23018
Tusterriiie Teil-rtti)))
17500
Hrenstter
(449
12020
Num of frails
150000
Num of Thaal
1230
100000
0.5
3020
50000
7538
Fir
45
1.
15
200
255
20
65
2.0
(b) Memory Usage vs
(c) #Trials vs
(d) # #Trials vs k
Figure The number of passes versus trials needed for 100 samples versus Friendster, fixing i in
2ah the memory usage versus c (2b), the number of
2c
and versus & (2d) on Twitter(WWW), Twitter(MPI) and
2c 2b
in 2d
Lemma C.1 For example, the actual success probability in TwitterWWWW with 1.k = is 100/31231 31300 R 0.0032, which is significantly larger than 9.65 x 10-5 provided by Lemma C.1
Conclusion and Future Work
We develop efficient cemi-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 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 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.
Acknowledgement
T-H. Hubert Chan partially supported by the Hong Kong RGC grants 17201823 and 17203122.
10

---

References
[ABH19] Matteo Agostini, Marco Bressan, and Shahrzad Haddadan. Mixing time bounds for graphlet random walks. Information Processing Letters, 152:105851, 2019.
[ADNK14] Nesreen K. Ahmed, Nick Duffield, Jennifer Neville, and Ramana Kompella. Graph sample and hold: framework for big-graph analytics. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1446-1455, New York New York USA, August 2014. ACM.
[BBCG08] 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.
[BCK 17] 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.
[BCK*18] 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.
22] Suman K. Bera, Lior Gishboliner, Yevgeny Levanzov, C. Seshadhri, and Asaf Shapira. Counting subgraphs in degenerate graphs. J. ACM, 69(3):33:1-23:21, 2022.
[BJKS04] Ziv Bar- Yossef,,,f, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statis- ties approach to data stream and communication complexity. J. Comput. Syst. Sci., 68(4):702-732, 2004.
[BKV12] Bahman Bahmani, Ravi Kumar, and Sergei Vassilvitskii. Densest subgraph in streaming and MapReduce. Proceedings of the VLDB Endowment, 5(5):454 465, January 2012.
[BLP19] Marco Bressan, Stefano Leucci, and Alessandro Panconesi. Motivo: Fast motif counting via succinet color coding and adaptive sampling. Proc. VLDB Endow., 12(11):1651-166) July 2019.
[BLP21] 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.
[Bre21a] Marco Bressan. Efficient and near-optimal algorithms for sampling connected sub- graphs. In Proc. of ACM STOC, page 1132-1143, 2021.
[Bre21b] Marco Bressan. Faster algorithms for counting subgraphs in sparse graphs. Algorith- mica, 2021.
[Bre23] Marco Bressan. Efficient and near-optimal algorithms for sampling small connected subgraphs. ACM Trans. Algorithms, 19(3), jun 2023.
[BRRAHI2] 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.
[BYKS02] Ziv Bar- Yossef, Ravi Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application counting triangles in graphs. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '02, page 623-632 632,, USA, 2002. Society for Industrial and Applied Mathematics.
[CHBG10] Meeyoung Cha, Hamed Haddadi, Fabrício Benevenuto, and P. Krishna Gummadi. Measuring user influence twitter: The million follower fallacy. In ICWSM. The AAAI Press, 2010.

---

[CHKX06] 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.
[CKS03] Amit Chakrabarti, Subhash Khot, and Xiaodong Sun. Near-optimal lower bounds on the multi-party communication complexity of set disjointness. In 18th Anmual IEEE Conference on Computational Complexity (Complexity 2003), 7-10 July 2003, Aarhus, Denmark, pages 107-117, 2003.
[CLWL16] 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):553-664, November 2016.
[CN85] Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM J. Comput. 14(1):210-22 120000222,-22 1985.
[DSTU17] Lorenzo De Stefani, Erisa Teroll,, and Eli Upfal. Tiered sampling: An efficient method for approximate counting sparse motifs in massive graph streams. In 2017 IEEE International Conference on Big Data (Big Data), pages 776-786, Boston, MA, USA, December 2017. IEEE.
[FKM+05] 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-2166
December 2005.
[GCYR22] Avishek Ghosh, Jichan Chung, Dong Yin, and Kannan Ramchandran. An efficient framework for clustered federated learning. IEEE Trans. Inf. Theory, 68(12):807- 8091, 2022.
[HS16] Guyue Han and Harish Sethu. Waddling random walk: Fast and accurate mining of motif statisties in large graphs. In Proc. of IEEE ICDM, pages 181-190, 2016.
[SP115] Madhav Jha, C. Seshadhri, and Ali Pinar. A Space-Efficiees Streaming Algorithm for Estimating Transitivity and Triangle Counts Using the Birthday Paradox. ACM Transactions on Knowledge Discovery from Data, 9(3):1-21, April 2015.
[KLPM10] Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue B. Moon. What is twitter, a social network or news media? In WWW, pages 591 6000 ACM, 2010.
[KMSS12] Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, and He Sun. Counting Arbi- trary Subgraphs in Data Streams. In David Hutchison, Takeo Kanade, Josef Kittler, Jon M. Kleinberg. Friedemann Mattern, John C. Mitchell, Moni Naor, Oscar Nierstrasz, C. Pandu Rangan, Bernhard Steffen, Madhu Sudan, Demetri Terzopoulos, Doug Tygar, Moshe Y. Vardi, Gerhard Weikum, Artur Czumaj, Kurt Mchlhomn Andrew Pitts, and Roger Wattenhofer, editors, Automata, Languages, and Programming, volume 7392, pages 598-508889 098-609.650 Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. Series Title: Lecture Notes in Computer Science.
[Kun13] 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.
[JJ18] Yongsub Lim, Minsoo Jung, and U. Kang. Memory-Effin -ffficief 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.
[MB83] David W. Matula and Leland Beck. Smallest-last ordering and clustering and graph coloring algorithms. J. ACM, 30(3):417-427, July 1983.
[MG20] Ryuta Matsuno and Aristides Gionis. Improved mixing time for k-subgraph sampling. In Proc. of SIAM SDM, pages 568-576, 2020.
12

---

[MSOI 02] 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-8277 2002.
[PLG*20] Hao Peng. Jianxin Li, Qiran Gong, Yuanxin Ning, Senzhang Wang, and Lifang He. Motif-matching based subgraph-level attentional convolutional network for graph classification. Proc. of AAAI, 34(04))5387-5334 Apr. 2020.
[PSS19] Kirill Paramonov, Dmitry Shemetov, and James Sharpnack. Estimating graphlet statistics via lifting. In Proc. of ACM KDD, page 587-595, 2019.
[PTWW13] A. Pavan, Kanat Tangwongsan, Srikanta Tirthapura, and Kun-Lung Wu. Counting and sampling triangles from a graph stream. Proceedings the VLDB Endowment, (114):8870-1881 September 2013.
[SERU17] 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.
2017.
[SGJS* 13] Ahmet Erdem Saríyüce, Bugra Gedik, Gabriela Jacques-Silva, Silva, Kun-Lung Wu, and Umit V. Çatalyürek. Streaming algorithms for k-core decomposition. Proceedings of the VLDB Endowment, 6(6):433 444, April 2013.
[SH15] Tanay Kumar Saha and Mohammad AI Hasan. Finding network motifs using meme sampling. In Proc. of CompleNet, pages 13-24, 2015.
[SV Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficient graphlet kernels for large graph comparison. In Proc. of AISTATS, volume 5, pages 488 488-495, 16-18 Apr 2009.
[TL Kun Tu, Jian Li, Don Towsley, Dave Braines, and Liam D. Turner. Gl2vec: Learning feature representation using graphlets for directed networks. In Proc. of TEEE/ACM ASONAM, page 216-221, 2019.
[WLR+14] Pinghui Wang, John C. S. Lui, Bruno Ribeiro, Don Towsley, Junzhou Zhao, and Xiaohong Guan. Efficiently estimating motif statistics large networks. ACM TKDD, 9()):8:1-8227, 2014.
13

---

A Proofs for Section 3.1
Lemma A.I. APPROX-DD(G, computes a T+c DD ordering of G.
Proof. First, consider SHAVE. We claim juat, after the execution of line 18 every vertex in S; has at least A
1+a T+p and at most A neighbors in V(G) \ Ss Consider indeed any E S; just after line 18 is executed. Note that has by construction at least I+a neighbors in V(G), and since S; S R2 it has at most I+8 neighbors in S. The lower bound follows. For the upper bound just note that has degree most A in V(G) and, thus, in V(G) St
A
A
Note that the final list I. obtained through the subroutine SHAVE by repeatedly computing some S, S V()), appending S; to L,, and deleting S; from G and 19). On the one hand this implies that the returned list L is permutation (G) (i.e., (lines and
Now consider APPROX-DD(G..1
every vertex of V (G) appears exactly once in L). On the other hand consider any vertex E V (G), and be as in the subroutine PEEL when v was appended to By the arguments above and by the choice of a,
A
A
A
d(olG(u)) 2 I+a 1+3
(2)
1+E
where (iv) is the subgraph of G' induced by and all vertices appearing after e in L. Moreover note that is an upper bound on d()(G(u)) for every u E G(v). follows that d(u ((](G()) 1
d(u(G(v))
for all v and all u > v where is the ordering defined by L.
Lemma A.2. Each call to SHAVE requires + = O(e + 2) invocations of COMPUTEALLDEG..
Proof. Line 16 requires, for each E l, one call to COMPUTEALLDEG on G G.H.). For each one of the l iterations of the loop at line 17 call to COMPUTEALLDEG is needed after G is updated at line 20 Noting that = ( + 2) concludes the proof.
Lemma 3.2. Let p (0, 1). With probability at least 1- p. one execution PEEL (Algorithm) 7
calls SHAVE O( log 7)) times, and at most once if A 2 12(1 + a) + 3) P'
Proof. Consider generic iteration of the loop of line 10 Fix any v H, and write dh (v) as:
d(u) H.)
Σ
(²(u)
where (u) is the indicator variable of the event u Hç. Note that TE. [[)) = 1 and therefore
E(d(v|HH.) d(vlG)
A
A
2(1 + 3)
By Markov's inequality, then, Pr (d(olH.)
A
1
It follows that
143
H4
E
R
>
(5)
2
and therefore
H
E| U R >
(6)
2
By standard arguments this implies that, for all 0, with probability at least 1 p after O )) iterations of the the loop of line 10] the set H becomes empty and thus the loop terminates.
For the second claim, note that e 4(1 + 3) and d(o Z I+a imply
E E(d(v H.) 4(1 a: 8)
Now consider again 33. and note that the random variables
(X+(u) (X(())](
(8)
14

---

are independent by construction of H5. By standard concentration bounds then:
A
Pr d(u d(u
>
I (r(((u)H) H:) > 2 E(d(u)
(9)
(1 (1+3))
Eld(u)Hi)
I exp
(10)
3
A
S exp
(11)
12(1 + () + +
Thus for A 2 12(1 + (1 + 8) In 2 we have Pr (d(x)H+)>
>
(1+B) S 3. By union bound over
all v E this implies that, with probability at least 1 - for all E [4] we have R; = H,. If that is the case then H becomes empty when line 21 executed, proving the claim.
Lemma A.3. When the subroutine PREL is called graph G with maximum degree A, it removes vertices from so that, upon termination, has maximum degree smaller than A I+a" < 1, then PEEL terminates after one iteration of the loop of line 10 a0 returns =
Moreover if
Proof. Denote by G the value of G when the loop of line 10 ends. Suppose G" contains vertex
A. Since 2 G' then do( (v) 2 T and thus H by line and since the loop ends when H = 0, then at some iteration v E R2 for some i E [e]. Consider then that iteration and let G be the current graph: obviously G G². If v S; then by line 20 & G and thus v & G".
such that de (v) 2 T
A
instead v & S, then by line 18 do (v) I d < Ita
Both cases give contradiction.
For the second claim note that if A 1 then = In that case H; = R = S for all E [e] and the claim follows by construction of the algorithm.
Lemma A.4. Consider one execution of APPROX-DD (G,c) in Algorithm 7 For every p E (0,
with probability at least 1 the subroutine SI1AVE is called O log (og( ! log : log times.
log(1+e)
Proof. Let 24(1 + a1 +1++1++ 9) In $ and consider the number of calls to PEEL such that A 2 T. Since 24 = 1n n > 12 n for all n 2 2, by Lemma 3.2 each such call with probability at 2p
p²
least 1 L. invokes SHAVE at most once. Moreover, by Lemma A.3 the number of those calls is at most
log
log n
min
71 log(1 + +a)
min log(1 + e/2)
(12)
2 the overall number of By union bound over the at most n calls, thus, with probability at least calls to SHAVE performed while A > T at most log(1+r//2)
log
Now suppose A < T. By Lemma
A.3 PEEL is called O
log T
times before G and by
[og(1+)/2]
Lemma 3.2 each such call invokes SHAVE Ollg 3) times with probability at least 1 g. Again by the union bound, with probability
? the overall number of calls SHAVE for < T is
log ((+ 1 log ) log a
o ( log T
log _ = =0
(13)
log(1 +c)
log +))
where we used T = 0 0 log )
By one final union bound over the two cases A > T and
< T, with probability the expression in [3] bounds the total number of calls to SHAVE. Li
A.1 Proof of Theorem
The number of passes is dominated by the number of calls to the subroutine COMPUTEALL.DEE Indeed, since (1...., n.), we can keep a global array of O(n) words that for every v V stores the following information: whether is still in G, the index i of the subset H, or R, or S,
15

---

containing well as the degree of u in any of those subgraphs. After each pass, the whole array can be updated in linear time so be ready for the next iteration. It then easy to see that COMPUTEALL.DEG can be ran any graph G, H, etc. using one pass and linear time: scan the edge list, and for each edge belong to the target vertex set (which can be checked in time ((1) using the array). This also shows that the total running time per pass of APPROX-DD DD is in (m))
[u, v increase the degree counters of both u and v iff they both
It remains to bound the total number of calls to COMPUTEALLDEG. First, assume M = Q(n).
In this case we simply run APPROX-DE DD until it terminates when V (.. By Lemma A.4 using p (()) the total number of calls fo SHAVE is in
o (
(ls((et)))) ()) log log log(1 + +c)
((++
log
log log c
=0
(14)
As by Lemma A.2 each call SHAVE makes ((1/c) invocation of COMPUTEALLDEG, the bound follows.
Now assume M = (0gnoogn) n). Let again @(1), In this case we let APPROX-DD stop
as A < T, where
T 12(1 + a) + 3n n
O log
(15)
as defined in Lemma 3.2 At that point we use one additional pass to store G, and use the linear-time
bucketing algorithm of [Br233 By Lemma 3.2 w.h.p. every call of PEEL makes only one call to
SHAVE. Moreover, by Lemma A.3 APPROX-DD makes O(logi-e n1) O log
calls to PEEL.
Hence the total number of calls to SHAVE is in O log As by Lemma A.2 each call to SHAVE
makes (1)ee) invocation of COMPUTEALL.DEG, the bound follows.
A.2
Pseudocode of PREPROCESS
Algorithm 4 PREPROCESS
1: function PREPROCESS()
2: compute ordering < APPR.
> see Algorithm
3: (p,1") t COMPUTEDISTRIB(11
b Algorithm
4: return (-, 1)
B Proofs for Section 3.2
Lemma 3.3. In the semi- stri-snreuning model with M [i(k),, the routine COMPUTEDISTRIB (Algo- rithm can be implemented so as to use passes and time O(m + n 1.2 log
Proof. Computing Z, p7, and I clearly takes time (n)), hence we focus on computing d(v(G(v)) and 1, for all v E V. Consider the oriented graph G = (V, A) constructed from G as follows. For every E V say that is light if d()) < k and heavy otherwise. For every light vertex add the are (v, to A for every I E G(v) (let us call such arc a light arc). Moreover, if u is light and has heavy neighbors in G, then add to A the
(v, y) where y is largest heavy neighbor of u in - (let us call such are heavy arc). For every v assign weight w(v) = if o is light and w(v) = k if is heavy. Moreover, for every let G(v) be the subset of vertices reachable from in G(v) by following the arcs in G. Finally, define w(v)) Enec(e) w(u).
We claim that (w) 2 1e if and only if ((v) # 0. To see this, note that both conditions are equivalent to the following one: in G. starting from v and following forward ares to vertices in G(v), one can reach at least light vertices at least one heavy vertex. Thus we need only to construct G and, from each E V. run truncated BFS to check if (v)) k. Assuming G is represented by adjacency
16

---

lists, each BFS requires Ok2² log k) operations, since it stops before seeing k2 arcs. The total time for the BFS is thus h2 log
To construct G, we use a single pass to compute (()) 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 (u,z) from e to I E (v))G((v) where v is light, we add it to A as a light arc. If v is heavy, we update the heavy are of a if æ light. Once we detect any light vertex v having at least k - 1 light arcs, we mark u as a heavy vertex, update the heavy arc of the other endpoint of each of these light ares and remove them. This can clearly be implemented in time ((m).
C Proofs for Section 3.3
C.1 Proof of Theorem 3.4
Each instance of SAMPLE requires only O(A2) words of memory, Hence, with memory M, we can run Q = @ parallel instances of SAMPLE. By Lemma C.1 each instance independently
returns uniform random k-graphlet with probability least A k
(I+c)==T k- By standard
concentration bounds, then, with high probability the number of uniform random k-graphlets returned overall is (M))k0())
We prove the two bounds on the number of passes and running time by describing two implementations of S SAMPIE.. 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(v)G(v)) for all u E S. To this end each instance creates pairs (u, v), (v, u) for each fu, v} E (5) and appends them to a global list L, where |L| S O(Q = (MM). Then, we invoke CHECKEDGES L); afterwards, every instance finds each one of its edges in the sorted output list. The same is for SUBDEGREES. By Lemma C.2 and Lemma C.3 we can carry out all of this in one pass and total time O([[Z) + m) log [.).. Since [T.] < M (m), the time to compute G[S] and d(u(G(o)) for all E S over all Q instances is in O(m log n).
This loop iterates over all subsets of S, which are at most 24 and performs O(k2) operations for each of them. Summed over the Q = (M/k²) instances, this yields a time O M). Adding the bound above for computing G[S] and the degrees, we obtain a total running time of (M2 m mlg n) for all instances of PROB.
Each instance of PROB can then conclude its execution by running the loop of line 18
It remains discuss the implementations of RAND-GROW.
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 Every edge the stream is sent to each of Q instances. The instance selects only the edges that belong to F,, 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 0 (Qkk), and the time for making the k- passes is O(Qk²m)
(Mm))
Since we consider A = o(log n) and M- = ((nk), the time for PROB is O(M2* + m log n) = O(M)). Hence, the total running time execute the batch is O(M)).
Second implementation. For a given instance of RAND-GROW (v, <) consider a generic iteration of the loop at line As in the original implementation of (Bre23, we first sample node E S; with probability proportional to the number of edges it has in E,, and then sample one of its edges {u, u') } in E, uniformly at random. to sample u, first we compute d(u) ((t)) for every well as GJS]. By using again SUBDEGREES and CHECKEDGES, this requires one pass and time Om log n). Then, can sample with probability proportional to d(u]G(vv) d(u[G))]). This takes time (kk)), as computing d(u G[S)) for every u entails checking the edges of G[S]. Next, to draw an edge {u, y'} uniformly at random in E,, we draw a random uniform subset of edges e...... e, incident with u in E.. Since at most - 1 of them can be incident with S,, follows that at least of them is not and is therefore random uniform edge incident with in the cut of E,
S, as
To draw eI...., Pq we use SAMPLEEDGES (Algorithm form subset of i distinct integers ji...., from (.....,TT[G(()))) We then create triplets
First, we draw random uni-
17

---

(u, v, (r.1...... (u, v.j.). For each h = I.....i i we then create a global list Th consisting of the triplets (u, v, jn). Finally, we execute SAMPLEEDGES(T) for all h 1,..., ,
parallel. Let Fh. By Lemma C.4 and by the choices of j1, :1....:J4
be the dictionary returned by SAMPLEEEDESSSC each 6 FA [u, v)] random uniform edge between u and A (ul (()).. for h = 1....,,. More- over, and crucially, Lemma C.4 guarantees that c,...... e, are all distinct, since the instances of
SAMPLEEDGES receive the same pairs (x, y); only the indices j differ. Thus 6i...,, E4 is a random
uniform subset of edges incident with u in E, as desired. Again by Lemma C.4 as Σi [Th] is
again bounded by M ((m), the total time is in O(m log
Therefore we have 2 passes for each one of the k - iterations of RAND-GROW, plus one pass for PROB, for a total of 2k passes. The total running time is (M2 + km l)g.).
C.2 Obtaining Degrees and Edges, in Parallel
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 + e))-o(k),
Lemma C.1. After running PREPROCESS once, every invocation of SAMPLE returns a size-k set S with probability least (2+c)==1((K-I))) 175a- Moreover, if SAMPLE succeeds, then the graphlet returned drawn uniformly at random from the set of all k-graphlets of G.
Proof. We adapt the claims and proofs of Section 6 of [BBr233] as follows. Suppose the vertices of G is sorted according to -DD ordering x, and suppose the subset S forms a k-graphlet of G, where 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 S; C S such that |Sa].
d(vlG(v)) (S, \ (S) S i(1 c)d(uG(())
(16)
Given and <, suppose qs is the probability that RAND-GROWE >) returns S. Using the inequality in (16), one can verify that [Bre23] Lemma 25] can be generalized to yield
(a+e)do)a))
1
k-1
4-1
1)! 1)! ( (1+))d(o(G(u))
Ss S (k - 1).3
(17)
d(v
One can also check that PROB (v, S. <) computes precisely gs. Now consider the probability that S accepted in line of Algorithm Pare(S) p(n) The same arguments of [Bre23] show that
Pacc (S)
(18)
+ k 1)!)
Moreover, the probability that S is sampled and returned by SAMPLE is p(v) 4s (Scc(S) I, which is independent of S. This implies that given that SAMPLE successfully returns some subset S, drawn uniformly at random from the set of all k-graphlets of G.
Next, we give simple routine for checking efficiently a set of edges, in parallel. This routine, and other ones below, operate list of pairs of vertices (u, v). When speak of an order over those pairs, we mean the lexicographic order induced by the approximate DD order x: (u,v) < (ul, o') iff u', or u' and v'.
Lemma C.2. Let L = (ui, .i)...., (ut, ve) where E V for each (u,v) v) E L. Then, CHECKEDGES(L) makes one pass, runs in time (([L) + m) [L]), and returns the list all edges of G that are in L.
Proof. The sorting of takes O log T.I) time. For each of the m edges in the list searching in the sorted list takes O(log L[) time. Finally, removing unmarked edges takes O(LL)) time. D
18

---

Algorithm 5 CHECKEDGES
1: function CHECKEDGES(L= =
(u, 2))
2: Sort I. and remove duplicates.
3: for each orientation (u, v) of every edge in the stream do
4: Search (u,,) T. and, if present, mark it.
5: Delete all unmarked elements from L.
6: return
We give two routines, SUBDEGREES and SAMPLEEDGES, that respectively compute a set of degrees (v)) and sample a of uniform random edges from subgraphs G(e). The routines make use of sorted lists of tuples, where in each tuple the first two elements are vertices v. The segment Lu,, v) is the sublist formed by all elements whose first entries u, e, in this order, and L(u) the sublist formed by all sublists L(u, v). The maps returned by the algorithms are assumed to support lookup in time (log LI).
Algorithm SUBDEGREES
1: function SUBDEGREES(+, I= (1), (we, v2))
2: Sort I. by < and remove duplicates.
3: Initialize Cu < O for every (u, L.
4:
for each orientation (u, () of every edge in the stream do if (u, v) E L, (u, v) 3 (u, 8) then Let (u, v) be the largest such pair. Update Cu,v < Cu,v +1.
5:
6:
7:
8:
Init dictionary D: 122 [m]].
9:
for every segment L(u) and every (u,v) v) E L(u) do
10: Set D(u, v) < [(e,, (u, L(u) (u,w) (u,
11:
return dictionary
Lemma C.3. Let L (u1, vi..... (u,, vt) where SUBDEGREES(- <,, L) makes one pass, runs in time (([L) + m) log Ll), and returns a dictionary D such that D(u,v) d(u]G(v)) for all (u,v)= L.
V for each (u,v) E L. Then
Proof. The algorithm makes one pass by construction. For the running time, note that the loop of line requires time O( Zl) by scanning each L(u) in reverse order. It is easy to see that the rest of the algorithm requires time O((L)) + m) log [[]. Now consider any pair (u, u) E L. Every edge in the stream between and vertex in G(v) is considered as (u, w) by the loop of line It then contributes to precisely one counter Cu,w" for some v. Therefore (u, w) also contributes to D(u, v), by the loop of line 9 It follows that D(u, r) dd(u)G(v)).
Lemma C.4. T = {u1, U1, U1,j1)..... (ue, Ut (e)) be such that, for every U.J. E T. we have u, E V with 3 u, and j E (1....,
.......(e d( ((v))) Then, SAMPLEEDGES( (RO (2, makes one pass G, and runs in time (((T) + m) log (T)).
over the edges GG
Moreover, for every (u,v,) v) E T, the map F(u,v, returns the j-th edge incident to in G(v), where the ordering of u's incident edges depends only on (i) the pairs (u,, v.) appearing in T (i.e., the first two components of each triple in T) and (ii) the order of the edges in the stream.
Proof. The algorithm makes one pass by construction. For the running time, it can be checked that several steps involve sorting data structure of size O([T),, and hence, they take O([2) log (T')) time. For the loop at line 20 there are (mm) iterations, where each iteration involves search an indexed data structure of size O (T)) ). which takes Oloo (TI) time. Hence, the total time is O(([T) m) log (T)).
next prove correctness. For every (u, w) L, let E(u, G(u)) 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 T-z (u) {(u, 01 v1...... .., (u, vn)) be the sorted list of pairs (u, v.) in L such that e; 2 v, where V1.
19

---

Algorithm 7 SAMPLEEDGES
1: function SAMPLEEDGES(<, T = (u, oi......... (2,, or.
2: Compute the list I. of distinct pairs (u, 0) s.t. 3(u,v,1) T, and sort L by x
3:
for each (u, v) E T. do Compute the increasingly sorted list
4:
(u, u) = (j v, E TT.
5:
Use SUBDEGREES( ( L) to compute d(u|G(v)), v(u, u) E L.
6:
Init empty list L*.
7:
Init dictionary J' mapping each (u, v)
an empty list.
8:
Init dictionary D V x [n] - V [n]
9:
for every (u, v) E L and every j E J(u, v) do
10:
Find the largest (u, in Lu,, v) such that
d(ulG(e')) d(ulG(o))+ +J
11:
j' =(u -
d(u]G(v)) +j Append (u, v') I,"
12:
13:
Append j' to (u, (", j)
14:
(u, (u,"",
Sort L by < and remove duplicaes
16:
For each (u,v) E L", sort (u, v) in increasing order and remove duplicates
17:
Init dictionary D 1/2 [n] F(()
18:
for each (u, u) E T." do
19:
init counter Ca.e 0
20:
for each orientation (u, of every edge in the stream do
21:
if Au, v) I.* with (u, v) 3 (u, t) then
22:
Let (u, v) be the largest such pair
Ca,u + Ca, +1 +1
24:
the first element j of (u, u) is = Cu.u then Set D(,, v. <- {u, 0}
25:
26:
Delete j from the head of J (u,v)
Define dictionary F V22 [n] E(G) s.t. F(u,e,)) = D(D"uu,,))) return dictionary
27:
For each 1,.... h, let (u, G(v)) be the subset of Elu, G(c)) formed by all edges (u, w) where U z w < U/41 (for = just consider U; I w). Clearly, the sets Etuu, G(v)) form a partition of Flu, G(v)); in fact,
(M, G(v)) F(u, G(s)) \ Elu, G(ve41)
with again the exception E* (u, G(o)) Elu, G(vn))
The order on E(u, G(v) is given as follows. Start with the elements E' (u, G(u)) in the order they appear in the stream. Then, add the elements of E²(u, G(v)) in the order they appear in the stream, and so on until E (u, G(v)). Note that this order depends only on the pairs (u, v) E L, and on the order of the edges the stream.
Note that if j is uniform at random in {l.... d(u (())) and independent from both and the stream, then the j-th edge ej in that order is uniform at random in E(u, G(v)).
Now let us look at the set E (u, G(v)) that contains éj. By standard computations,
i max(i d(ulG(vv) d(ulG(o)) 1
Note that ij depends only on and the sizes of the sets (", G(v)), and not the order of the elements in the stream. The vertex U; is precisely the vertex v computed by the algorithm at line Moreover, the index j' computed at the same line is precisely:
j'= d(u G(v)) + d(u)G(()))
20

---

It follows that, if we map (u, to the j'-th edge of E G(v)) that appears in the stream, which ej. then the algorithm correct. This is precisely what the algorithm does in the loop of line 20 The counter Cur keeps track, for every ....., h as above, of the number of edges of E (u, G
seen so far; when Cus matches some j. it maps (u, v) to ej, as desired.
D Proofs for Section 4
Lemma 4.1. Given a graph G = (V, V, a (0, any 9-pass streaming algorithm computing a node v such that (c( 2 a max 6c(w) with probability at least z. requires memory $2
Proof. Let be a q-pass s-Space streaming algorithm for computing a vertex with degree being at least fraction of of the maximum degree. Without loss of generality, assume that A computes its degree as well (as one additional pass and Ollog n) memory suffices to compute the degree of a given node). We will use A to obtain multi-agent protocol for the disjointness problem.
Let = 1 + 1 be the number of agents one-way multi- 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 agents, we obtain data stream of a bipartite graph G (U, V, B) as follows.
V (UI,..., vn) corresponding to the n bits
For each agent i, we introduce a set of vertices and edges associated with i as follows. For every for every j E [n) s.t. Fi, = 1, there is a node Vi U as well as an edge (ui,, E.
The edges are arranged in the stream so that the edges associated with a same agent appear next each other in the stream while preceding the edges associated with agent In other words, (Ma,, Uy) precedes (M,,,%)) in the stream if i < e, 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. ((1,,, j E [m), (m1, U)) E F.). Then, she sends her memory snapshot (with size (s)) to the second player that continues the execution of A on the set of edges {(12,, U;) j E [n], (u2,; vt) E). The second player in sends her memory snapshot to the third player and so forth until reaching the 1-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 2. and "NO" otherwise.
Such 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 ( in the NO instance ). Hence, with probability least 3. in YES instance finds node with degree at least t while a NO instance such a node has degree 1.
Observe that the number of vertices in the bipartite graph is at least V while it holds that |U| + V = O + n) = =On).. Moreover, the communication cost [I]] of the protocol satisfies [|| = 0 s q) = 0 ((*) by our arguments, and [I] Ω (+) +((an) by the bounds above.
From this, we derive E
Lemma 4.2. Given graph G (V,E), k 3, any q-pass streaming algorithm for the uniform k-graphlet sampling problem on G requires memory Q [V]
Proof. We use the same construction of Lemma while letting ( = k - 1. In such case, "NO" instance for the disjointness problem corresponds to graph with maximum degree one (with each connected component consisting of either singleton or single edge), while a "YES" instance
21

---

corresponds to graph containing connected component being a star with t + = 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 result, any streaming algorithm succeeding in sampling uniformly a k-graphlet with probability á would also solve the disjointness problem.
E
The Heuristic APPROX-DD
In this section we introduce 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 extract 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(vlG). Let the sorted vertex list be U1.-.. Plv(C)) We use a streaming pass to compute ((,))G(v;)) for each vertex Us. where G(v)) represents the induced subgraph the prefix 01, " Us. We know that Σj= d(ey GG())) )) is the number of edges in G(us). Let i' be the largest i such that edges in G(v,) can be stored in memory, i.e., Σj d(uy) G((z)) < M. If = IV(G) or d(v:++1|G) S I4a we run the heuristic algorithm PEEL HEURISTIC instead, otherwise we still run PEEL.
In HEUR-IIU,S we first use a streaming pass to record all edges in G(e-)). Then we repeatedly select the vertex v in ((v-)) with the maximum d(vll)), append
the DD order, remove from
G(u--) and update d(v' d(v'lG) for all vertices o' E G(v-) that are connected to We continue this process until d(vlG) of every remaining vertex (wx-) are less than d(ve -|G)
1te
The idea is summarized in Algorithm 8
easy to see that whenever we append v to L, holds that d(v]G(v))= d(v|G) 2 d(ulG)- = d(u]G(v) for each E G(v-)), and d(v])(+t) > M(0.=41100 > die, for each V/ where j > i", therefore the final order we obtain indeed a I+e LDD order. Note that after an execution of PEER-HEURIS the degrees of all remaining vertices are no greater than d( +1 G) S 1+o This means that and Theorem 3.J still bounds the number of passes for APPROX-D -E----D-HHHSSSS PEEL-HEURISTIC only requires 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-DI in practice.
performss no worse than PEEL if the condition in line Dis satisfied,
However, since
22

---

Algorithm 8 Approximate DD order heuristically, The lines marked with a entail a streaming pass.
function DEPROX-DDD-HEURSSIICCE
2:
L + +mmpty list
3:
a 5
4:
while V(G) + 0 do
5:
compute d(v G) for all v E V(G)
6:
",."","v(0""" <- the sorted list of V(G) in descending order of d(v[G)
7:
compute d(u, ((.)) for each E [[V[]]]
8:
max(i) Eド d(u,
d G(r)) S M)
9:
ir = -VV()) 4( G) S T then
b ((v,-+1()) ifi VVG)) otherwise 0
10:
1tc
11:
(G, PEEL-HEURISTIC (vi,... , J.b, b.e, L)
12:
else
13:
(G.L) e,,
return
15:
function PEEL- HEURISTUUIT P,b. L)
16:
E(P) <- the edges whose both endpoints are in while P / do
17:
18:
<- arg max,ee(d(((G))
if d((v(G) < then
20:
break
append
22:
G G \ [u), P P\ fo} for each o' P such that (u,v) E(P) do
24:
d(v'lG) + d(v'lG)
25:
return LG
23

---

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 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.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: As stated in all theorems, our results are under semi-streaming setting requiring (n)) or Qnn log n) memory, which might be satisfied in extremis. Though 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 encouraged to create separate "I "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results 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 the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or 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, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Assumptions were stated in every theorems. All the theoretical bounds were provided with detailed proof, either in the main text or in appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Our algorithm is easy to implement in various programming languages. Our Python implementation is attached to the submission. We elaborated on each step of our algorithms and marked the steps requiring a streaming pass.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
25

---

(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome 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 instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We attached the code and instruction to submission. The datasets used can be download in in/tttp://konett. cc/networks/ or generated by the attached random graph generator.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://niis. cc/
cublic/guides http:/ggiiieeeoeeuuuiiieeee
SrodeSubmissiooPoll11
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7 //nips /nips.cccpublle... wwwpcppwlcgggp...eceeeeeeeeooeee wwatii//guies//eeee http//ooeeuamiiiiiooooooeeeeeeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permirted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Experiment settings and details were elaborated in Section
Guidelines:
The answer NA means that the paper does not include experiments.
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.
7. 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:
26

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi-
dence 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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 96% CI, if the hypothesis of Normality of errors 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 out of range (e.g. negative етror 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.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Resources were stated at the beginning of Section S
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 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 failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: htttt:://ppe/urrrra http://pp...pbblc//cccccccieaaae
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 reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
27

---

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 no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), fairness considerations (c.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 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 unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
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 high risk for misuse or dual-us 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [Yes]
We have cited the public online datasets that we used. No license has been found.
Justification:
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 dataset.
28

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [Yes]
Justification: We included the source code in the supplementary material and the Github link is provided in the experiment section.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This work does not involve crowdsourcing nor research with human subjects.
Guidelines:
29

---

The answer NA means that the paper does not involve crowdsoureing 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 expect authors adhere 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.
30


Reviews:
[{"review_id": "WIqNAPulww", "reviewer": "Reviewer_NpXf", "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.", "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. \n\nI agree with authors that DD order is not reverse of core order,", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Starting from UGS, Authors provide a framework to efficiently and uniformly sample k-graphlets. To achieve this, they defined DD order and propose an efficient semi-streaming algorithm that approximate the order. Then a distribution $p$ is computed based on the approxiamted DD order, and nodes are sampled from $p$. Finally a graphlet is randomly expanded from the initial node and accepted with probability. While the peel part of algorithm 1 is similar to the streaming algorithm for core order, it is interesting to see the shave operation can improve the approximation.\n\nAuthors prove the memory lower bound for the problem and thus shows their algorithm is near  optimal.\n\nAuthors conduct experiments on large graphs", "weaknesses": "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.\n\nEnlarge the font size of Figure legends.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the comments, which we would like to address as follows.\n\n[Response to Weaknesses]\n\nAn efficient UGS sampling algorithm in the standard RAM model is described in the third paragraph of the introduction, which mentions the high level ideas of how topological order is used in uniform sampling.  We will clarify in the next version that the topological order is used to define the starting vertex of the sampling and compute the relevant probability.\n\nWe will add a paragraph for the background of communication complexity lower bound in the related work.\n\n[Question: 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.]\n\nDefinition 2.1 says that in an ordering, if d(v|G(v)) > 1, then some condition has to be satisfied. However, if d(v|G(v)) = 1 or 0, this means all the vertices in the remaining G(v) have degree 1 or 0, whose connected component has size at most 2.  Since the sampling problem is non-trivial only when k >= 3, in this case the ordering of the remaining vertices in G(v) is not important.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FM2QmjRlPA", "reviewer": "Reviewer_T1eM", "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.\n\nUGS 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.\n\nThe 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.", "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": "/", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "In comparison to previous work, the sample distribution is guaranteed to be exactly uniform over all graphlets.\n\nOverall, the approach of carefully approximating the ordering is appealing and not completely trivial.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the comments, which we would like to address as follows.\n\n[Response to Weakness]\n\nOur approach can deal with both sparse and dense graphs. The same theoretical guarantees work for sparse graphs and a good performance on sparse graphs by our approach is shown in the experiments. It is possible that there might be specialized algorithms for sparse graphs but our approach aims to provide a general solution to the problem, i.e. to both sparse and dense graphs. \n\n[Response to Hypothetical Application Scenario.]\n\nThe input graph can be very dense, in some cases of interest. For example, we may need to study the similarity graph between a large number of pictures, say 1,000,000. Here, each vertex represents a picture, with each edge between two vertices indicating that the corresponding pictures are “similar”. Depending on the similarity measure at hand (e.g. cosine similarity larger than a given threshold), the resulting graph can be very dense (over 10^10 edges), in which case storing the whole input graph in memory would not be feasible. This motivates the development of a streaming algorithm, requiring a “small” amount of memory.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZnGIHyn83w", "reviewer": "Reviewer_5Ka2", "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.", "questions": "Comment on the above weaknesses. How would you convince a machine learning researcher to read your paper?", "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.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- A strong algorithmic contribution.\n- Solid and apparently sound theoretical analysis. In particular, lower bounds on the computational complexity that almost match the complexity of the proposed approach.\n- A very well-written paper.\n\nNote: The overall low score I give for the contribution is based on the question \"Are the results valuable to share with the broader NeurIPS community?\" Otherwise, the score is \"Excellent\".", "weaknesses": "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. \n\n- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the comments, which we would like to address as follows.\n\n[Weakness 1 and Limitation]\n\nIn the next version of our work, we will highlight the connection between machine learning and the graph mining problem in our paper as follows:\n - Graphlet sampling can be used to select representative subgraphs for training, validating and testing (e.g. in a neural network), which can speed up the training process and reduce computational requirements significantly. \n - Graphlet sampling can be used to extract meaningful features from large graphs. The frequency distribution of different graphlets can be used as a feature vector to represent the graph structure [MSOI+02], which can be approximately obtained by our approach.\n\nOther applications can be also found in the literature such as graph classification [TLT+19], graph kernels [SVP+09], and graph neural networks [PLG+20].\n\n[Weakness 2]\n\nThank you for the suggestion of using a sparsified graph. However, for a k-graphlet that has only k-1 edges in the induced subgraph, the sparsification process will likely make this graphlet disconnected.  Even though we do not immediately see how this idea will work, we think it is an interesting future research direction.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)