Efficient and Local Parallel Random Walks
Authors: Michael Kapralov
Silvio Lattanzi
Navid Nouri
Jakab Tardos
Venue: NeurIPS 2021 Poster (2021)
Keywords: personalized pagerank
random walks
MPC
clustering

Abstract: Random walks are a fundamental primitive used in many machine learning algorithms with several applications in clustering and semi-supervised learning. Despite their relevance, the first efficient parallel algorithm to compute random walks has been introduced very recently (Łącki et al.). Unfortunately their method has a fundamental shortcoming: their algorithm is non-local in that it heavily relies on computing random walks out of all nodes in the input graph, even though in many practical applications one is interested in computing random walks only from a small subset of nodes in the graph. In this paper, we present a new algorithm that overcomes  this limitation by building random walks efficiently and locally at the same time. We show that our technique is both memory and round efficient, and in particular yields an efficient parallel local clustering algorithm. Finally, we complement our theoretical analysis with experimental results showing that our algorithm is significantly more scalable than previous approaches.

Efficient and Local Parallel Random Walks
Michael Kapralov
Silvio Lattanzi Google Research si wilvoo@gooogle.coo
EPFL
michael kwppalovveppl.ccmmmmo ch
Navid Nouri EPFL navid. navid.nouri@epfl.
Jakab Tardos EPFL waw.bbbarddseepl..om ch
Abstract
Random walks are fundamental primitive used in many machine learning algo- rithms with several applications clustering and semi-supervised learning. Despite their relevance, the first efficient parallel algorithm to compute random walks has been introduced very recently (f.ącki et al.) Unfortunately their method has a fundamental shortcoming: their algorithm is non-local in that it heavily relies on computing random walks out of all nodes in the input graph, even though in many practical applications one is interested in computing random walks only from a small subset of nodes in the graph. In this paper, we present a new algorithm that overcomes this limitation by building random walk efficiently and locally at the same time. We show that our technique is both memory and round efficient, and in particular yields efficient paralle! local clustering algorithm. Finally, we complement our theoretical analysis with experimental results showing that our algorithm is significantly more scalable than previous approaches.
Introduction
Random walks key components of many machine learning algorithms with applications in computing graph partitioning [ST04, G1L,-21, spectral embeddings [CPS15, CKK- or net- work inference [HMMT18),
well learning image segmentation [MS00], ranking nodes in graph [AC07] and many other applications. With the increasing availability and importance of large scale datasets it is important design efficient algorithms compute random walks in large networks.
Several algorithms for computing random walks in parallel and streaming models have been proposed in the literature. the streaming setting. Sarma, Gollapudi and Panigrahy [DSGP1 1] introduced multi- pass streaming algorithms for simulating random walks, and recently Jin [Jin19] gave algorithms for generating a single random walk from a prespecified vertex in one pass. The first efficient parallel algorithms for this problem have been introduced in the PRAM model [KNP92, HZ96].
more recent line of work, Bahmani, Chakrabarti, and Xin [BCX1] 1] designed parallel algorithm that constructs single random walk of length from every node in Ollog {) rounds in the massively parallel computation model (MPC), with the important caveat that these walks are not independent (an important property in many applications). This was followed by the work of Assadi, Sun and Weinstein [ASW19] 19],, which gave an MPC algorithm for generating random walks an undirected regular graph. Finally, Eşcki et al. [LMOS20] presented new algorithm compute random walks of length from every node in an arbitrary undirected graph. The algorithm of [LMOS20] still uses only Oloog f) parallel rounds, and walks computed are now independent.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

From a high level perspective, the main idea behind all the MPC algorithms presented in [BCX11, 1, ASW19, LMOS20] to compute random walks of length by stitching together random walks of length f/2 in single parallel round. The walks of length f/2 are computed by stitching together random walks of length f/4 and so on. It is possible to prove that such strategy leads to algorithms that run in O(log f) parallel rounds as shown in previous work (this is also optimal under the 1-vs-2 cycle conjecture, as shown in [LMOS20)). Note that this technique in order to succeed computes in round several random walks of length 2' for all the nodes in the network in parallel. This technique is very effective if we are interested in computing random walks from all the nodes in the graph, or, more precisely, when the number of walks computed out of a node is proportional to its stationary distribution. However, this approach leads to sigmificant inefficiencies when we interested in computing random walks only out of subset of nodes for a single node in the graph. This is even more important when we consider that in many applications as in clustering [GLMY11, GS12, WGD13] we are interested in running random walks only from a small subset of seed nodes. This leads to the natural question: Is it possible to compute efficiently and in parallel random walks only from a subset of nodes in graph?
In this paper we answer this question in the affirmative, and we show an application of such a result in local clustering. Before describing our results in detail, we discuss the precise model of parallelism that we use in this work.
The MPC model. We design algorithms in the massively parallel computation (MPC) model, which theoretical abstraction of real-world system, such as MapReduce [DG08], Hadoop [Whi Spark [ZCF+ 10] and Dryad [IB++07]. The MPC model [KSV10, GSZ11, BKS13] is the de-facto standard for analyzing algorithms for large-scale parallel computing.
Computation in MPC is divided into synchronous rounds over multiple machines. Each machine has memory S and at the beginning data is partitioned arbitrarily across machines. During each round, machines process data locally and then exchange data with the restriction that no machine receives more than S bits of data. The efficiency of an algorithm in this model measured by the number of rounds it takes for the algorithm to terminate, by the size of the memory of every machine and by the total memory used in the computation. In this paper we focus on designing algorithm in the most restrictive and realistic regime where S E O(n") for a small constant ò E (0, 1) these algorithms are called fully scalable.
Our contributions. Our first contribution is an efficient algorithm for computing multiple random walks from single node in graph efficiently.
Theorem 1. There exists a fully scalable MPC algorithm that, given a graph G = (V, F) with vertices and m edges, a root vertex r, and parameters B", l and can simulate B" independent random walks on G from r of length with an arbitrarily low error, in Ollog log, B²) rounds and Ö(mEer + B* Xe) total space.
Our algorithm also applies to the more general problem of generating independent random walks from subset of nodes in the graph:
Theorem 2. There exists fully scalable MPC algorithm that, given a graph G = (V, E) with vertices and m edges and a collection of non-negative integer budgets (b.))eV for vertices in G such that Evev bu B², parameters l and X, can simulate, for every u V, by independent random walks on G of length E from with an arbitrarily low error, in Ollo e log, B*) rounds and
Ö(mAe + XC) total space. The generated walks are independent across starting vertices u V.
The following remark clarifies the effect of parameter À on the number of machines.
Remark 1. The parameter X has nothing to do with the input of the algorithm, but a trade-off parameter between space and round complexity. It is useful to think of it as X = n' for some e (not necessarily a constant), in which case we get round complexity of Olog f log B" /(( (cloog n)) S Olog t/c) and a total memory of Omm" et + +B"n n²'n' f). We can set e to, for example, 1/ 1/log log n, to get nearly optimal total space and Ólog E) round complexity.
If we compare our results with previous works, our algorithm computes truly independent random walks as [F.MOS20] does. This is in contrast with the algorithm of [BCX11], which introduces dependent constructs not independent walks. Our algorithm has significantly better total memory than [LMOS20], which would result in memory Q(m B²) for generating 8* walks out of root
2

---

node r. This comes at the cost of slightly higher number of rounds (log, B", a factor that in many applications can be considered constant).
The main idea is to preform multiple cycles of stitching algorithms, changing the initial distribution of the random walks adaptively. More precisely, in initial cycle we construct only few random walks, distributed according to the stationary distribution - this is known to be doable from previous work. Then, in each cycle we increase the number of walks that we build for node r by factor of and we construct the walks only by activating other nodes in the graph that contribute actively in the construction of the random walks for r. In this way we obtain an algorithm that significantly more work efficient in terms of total memory, compared with previous work.
Our second contribution is to present application of our algorithm to estimating Personalized PageRank and to local graph clustering. To the best of our knowledge, our algorithm is the first local clustering algorithm that uses number of parallel rounds that only have a logarithmic dependency on the length of the random walk used by the local clustering algorithm.
Theorem 3. For any X > 1, let a E (0, 1] be a constant and let C be a set satisfying that the con- a/ 10 and Vol(C) S 3 Vo) Then there is MPC algorithm for local clustering that uses Olog f. Eloo B*) = Ollog log n- logxxVoll and total memory Ö(mAe1 B² Xe) O(m) + )Vol(C)2), where B
ductance of C, (CC), is at most
rounds of communication
10 log'o" l :== 10 log
n'aa
a
and 17 IovoliCy and outputs cluster with conductance O(v lo
Finally we present an experimental analysis of our results where we show that our algorithm to compute random walk is significantly more efficient than previous work [EMOS20], and that our technique scale to very large graphs.
Additional related works. Efficient parallel random walks algorithm have also been presented in distributed computing [DSNPT13] and using multicores [SRFM16]. Although the algorithms in [DSNPTI3] require a number of rounds linear in the diameter of the graph. The results in [SRFM16] are closer in spirit to our work here but from an algorithmic perspective the chal- lenges in developing algorithms in multicore and MPC settings are quite different. In our setting, most of the difficulty
the fact that there is no shared memory and coordination between machines. As result, bounding communication between machines and number of rounds is the main focus of this line of research. From an experimental perspective an advantage of the MPC environment is that it can scale to larger instances, in contrast an advantage of the multicore approach is that it is usually faster practice for medium size instances. In our case study, where one is interested in computing several local clusters from multiple nodes(for example to detect sybil attack(look at [ACE* 14] and following work for applications) the MPC approach is often more suitable. This is due to the fact that the computation of multiple Personalized PageRank vectors at the same time often requires large amount of space.
Several parallel algorithm have also been presented for estimating PageRank or PersonalizedPageR. ank [DSGP11, 1, DSMPU15, BCX11], but those algorithms either have higher round complexity or introduce dependencies between the PersonalizedPageRann. vectors computed for different nodes. Finally there has been also some work in parallelize local clustering algorithm [CS15], although all previously known methods have complexity linear in the number of steps executed by the random walk/process used the algorithm(in fact, our method could potentially be used to speed-up this work as well).
Notation. We work on undirected unweighted graphs, which we usually denote by G (V,E). where V and E are the set of vertices and the set of edges, respectively. We also have n := V and m : E), unless otherwise stated. We define matrix D as the diagonal matrix of degrees, i.e.. Dr.; = d((x)) Also, we let A be the adjacency matrix, where Ar, 1 if and only if there is an edge joining vn and Uj. and A = 0, otherwise.
2 MPC random walks
In this section, we present our main result to compute B" random walks from a single root vertex r up to length of f, then we generalize it to multiple sources. As mentioned before, our main idea is to carefully stitch random walks adaptively to activate nodes locally. the rest of the section, we start by presenting our main theorem and giving brief overview of our algorithm. We then describe
3

---

our stitching algorithm, and analyze the number of random walks we must start from each node so that our algorithms work. Finally, we present the extension of our result to the setting with multiple sources.
Theorem 1, There exists a fully scalable MPC algorithm that, given a graph G = (V, F) with n vertices and m edges, a root vertex v, and parameters B l and X can simulate B independent random walks on G from r of length with an arbitrarity low error, in Oflog E flog, B*) rounds and Ommee + B² XE) total space.
2.1 Overview of our Algorithm
Here, we explain the frameworks of stitching and budgeting, which are the two key tools making up our algorithm. For simplicity and without loss of generality, we assume that each vertex v has its own machine that stores its neighborhood, its budgets, and its corresponding random walks.'
Remark 2. For ease of notation we assume that f= 2 for some integer j. One can see that this assumption is without loss of generality, because otherwise one can always round I to the smallest power of 2 greater than E, and solve the problem using the rounded E. This affects the complexity bounds by at most constant factor.
Stitching.
Here, we explain the framework of stitching, which a key tool for our algorithm. At each point in time the machine corresponding to u stores sets of random walks of certain lengths, each starting in Each edge of each walk is labeled by a number from 1 to f, denoting the position it will hold in the completed walk. Thus, walk of length could be labeled (k + 1...., k + s) for some k. Initially each vertex generates a pre-determined number of random edges (or walks of length one) with each label from 1 to f. Thus this point, we would find walks labeled 1, 2, 3, ..... on each machine. After the first round of stitching, these will be paired up into walks of length two, and so we will see walks labeled by (1, 2). (3, 4), (5, 6), on each machine. After the second round of stitching see walks of length 4, such as (1, 2, 3, 4), and so on. Finally, after the last round of stitching, each machine will contain some number of walks of length l (labeled from 1 to E), as desired.
will
At any given time let (v) denote the set of walks stored by whose first label is and B(v k) denotes their cardinality in the future, we will refer to the function B as the budget. After the initial round of edge generation, Ww( consists of B(v, k) individual edges adjacent to v. for each v and k.
The rounds of communication proceed as follows: in the first round of stitching, for each edge (or length one walk) e in (w),, for any odd k. sends a request for the continuation of the walk to 2, where z is the other endpoint of e. That is, v sends a request to for an element of W Each vertex sends out all such requests simultaneously in a single MPC round. Following this each vertex replies to each request by sending walk from the appropriate set. Crucially, each request must be answered with a different, independent walk. If the number of requests for W&+1& (z) exceeds [W++1 B22, + 1), the vertex 2 declares failure and the algorithm terminates. Otherwise, all such requests are satisfied simultancously in a single MPC round. Finally, each vertex e increases the length of each of its walks in (v) to two when k is odd, and deletes all remaining walks in (v(v) when l is even (see Figure 1). For a more formal definition see Algorithm 1.
Budgeting.
crucial aspect of stitching is that the budgets (vv k) need be carefully prescribed. If at any point in time a vertex receives more requests than it can serve, the entire algorithm fails. In the case where B(; follows the stationary distribution, this can be done (see for instance [LMOS20)), since the number of requests - at least in expectation will also follow the stationary distribution. In our setting however, when (-, 1) follows the indicator distribution of r, this is much more difficult. We should assign higher budgets to vertices nearer r; however, we have no knowledge of which vertices these are.
In other words, the main challenge in making stitching work with low space and few rounds is to set the vertex budgets (B(c, k)) accurately enough for stitching to succeed this is the main technical contribution of this paper.
In reality multiple vertices may share a machine, if they have low degree; or if a vertex has a high degree it may be accommodated by multiple machines in centt tree structure.

---

b
a
d
d
d
data from the previous (a) Before round
(b) Before round 2
(c) Before round
Figure 1: Illustration of stitching algorithm for walk (a, b, d, e). The red, green, blue and orange
walks in each figure correspond to walks in Wi (a), W2(b), Wa(c) and (a(d), respectively.
Our technique is to run multiple cycles of stitching sequentially. In the first eycle, we simply start from the stationary distribution. Then, with each cycle, we shift closer and closer to the desired distribution, in which the budget of r is much greater than the budgets of other vertices. We do this by augmenting (r; 1) by some parameter À each cycle. This forces us to augment other budgets as well: For example, for u in the neighborhood of r we expect to have a significantly increased budget Buu, 2). In order estimate the demand (and all other vertices) cycle.
Though initially only a few walks simulated by our algorithm start in (we call these rooted walks), we are still able to derive some information from them. For instance, we can count the number of walks starting in and reaching u as their second step. If и. rooted walks visited u as their second step the previous cycle, we expect this number to increase to À K in the following cycle. Hence, we can preemptively increase Buu, 2) to approximately À K.
the initial budget of each vertex Bo deg(u) version of the stationary distribution. This guarantees that the first round of stitching succeeds. Afterwards we set each budget (v., k) individually based on the information gathered from the previous cycle. We first count the number of rooted walks that ended up at v as their hthh step (Line 9). this number is sufficiently large be statistically significant (above some carefully chosen threshold 0 in our case, Line 10), then we estimate the budget B(v, k) to be approximately À x in the following deemed too small, means that rooted random walks
More precisely,
appropriately scaled
cycle (Line 11). On the other hand, rarely reach their ht step, and the budget B(v, k) remains what it was before.
Budgets using [LMOS20]
Budgets in iteration j +
Budgets
Budgets in iteration j
Initial budgets
Bo
Vertices
root
Figure 2: Illustration of the evolution of B(v, k) for all v E V for fixed & on line graph over the iterations of Algorithm and comparing to budgets if one uses [LMOS20]. Vertices are sorted by their order on the line and root is the middle vertex on the line.
5

---

Algorithm Stitching algorithm
1: procedure STITCH(G, B)
2: for V in parallel do
3:
for k E [e] do
4:
(w( < a set of (v,, k) independent uniformly random edges adjacent on
5:
for j = 1......... log,, do
b See Remark
6:
for E V in parallel do
7:
for k = (mod 2²) do
8:
for walk p E Ww( do send (v,, k) to 2, where t- end vertex of
9:
10:
for E V in parallel do
11:
for each message (c, k) do if 2
12:
then
13:
return Fail
14:
send (g, k; 2) to v, where the walk q randomly chosen walk in Wa W (v) W (x+22-1(2) < W (=)
15:
16:
for E V in parallel do for each message (g. k; =) do
17:
18:
p any walk of length 2 in W&(U) with end vertex Di p + is the concatenated walk
19:
(v) < Wa(v)>(P) u +
20:
for k = 20-1 (mod 2 do
21:
(x(E)= +
22:
return (1( for all E
Algorithm Main Algorithm (Budgeting)
1:
procedure MAIN(G, r, B*,)
2:
+- 10C log n, Bn + 3 logn, T t 1 20C log 6
Parameter settings
3: Ve V, Bo(v) +- Bo deg(u)
4:
Vu E V, vk E [ (v, +- Bo deg(o)- 33
5:
for = 1... [logx B" do
6:
W1 STITCU(G,B)
7:
W + W1(r)
8:
for E V, k E [ do
9:
K t (( E Wlwk = o}l
if K 2 0 then
11:
B(u,k) k) - (Bo(v) + X³ ( 338-33
12:
else
B(u,k) t (o(v)-aak)
14:
W1 < STITCH B)
W (i(r)
16:
return W
Remark 3. In the above pseudocode (Algorithm 2) scaling parameter slightly greater then one. We augment all budgets B(-, k) by factor 33-33 to insure that there are always slightly more walks with higher labels, and ensure that stitching succeeds with high probability.
Analysis. We now ready to present the main properties of our algorithm:
Lemma 1 (Correctness and complexity). Algorithm takes Olog logx B*) rounds of MPC communication, STITCH terminates without failures with high probability, and the total amount of memory used for walks is Evey Elm B(v, k) = O log + B* XE).
Proof. Let pk be distribution of random walks of length & starting from That is, the probability that such walk ends up in V after k steps is pk(x))

---

To bound the round complexity we note that each call of STITCH takes only Ollog E) rounds of communication, and is called [log, _=] + times; this dominates the round complexity. Further rounds of communication are needed to update the budgets. However this can be done in parallel for each vertex, and thus takes only one round per iteration of the outer for-loop (Line 5).
To prove that the algorithm fails with low probability, we must show the following crucial claim about the budgets BV, K). Recall that the ideal budget in the 7t iteration would be (B,, k) s (v) + X (v). We show that in reality, the budgets do not deviate too much from this.
Claim 1. After iteration i of the outer for-loop (Line 5) in Algorithm 2, with high probability B is set such that
Ve E V, & [C] B(U, R)) [( + X (*)) 7 (Bo(u) + + Pt (u)) 73th 3k-- -]
Proof. We first note how B(r; 1) the budget of walks starting at the root vertex evolves. For v = r and & = L, K is always equal to W - since r is the root vertex and greater than 8. Therefore, B(r, 1) is set in Line 11 of Algorithm 2 to (Bo(r) + X²). This is important, because it means that when setting other budgets in iteration i > 1, |W| is always (Bo(r) + 1 the number of walks rooted from in the previous round. The exception is the first iteration, when [W] is simply [Bo(r)]- In both cases we may say that [W| 2 X
There are two options we have to consider: If after the hth round of STITCH exceeded 6, in which case our empirical estimator x/ x/|W| for pk (v) is deemed reliable. We then use this estimater to set the budget for the next round (see Line 11). Alternately, if did not exceed 0, the imperical estimator deemed too unreliable; we then simply set (vv, k) proportionally to (D( (see Line 13).
Case I (k < 0) then intuitively, x: is too small provide accurate estimator of (v)). In this case we are forced to argue that the (predictable) term (v) dominates the (unknown) term (*)).. Since < 0, [[x) = p* (v) [W]= < 29. (The opposite happens with low probability? by Chernoff bounds, since 0 10C' log n.) Therefore.
Bv, k) = Bo(w) - 3k-3 S (Bo(v) + X -.(()(()))) 3K-2
and
-.(())(())) (1 Bo(u) + X Ph(())
N pk (v)
(Bo(v) + X B(r, k) = Bo(u)= -B(()
3k-3
So, we need to prove that 1 (1) 2 11 Now, by the above bound on [B(x) as well as the
fact that [W] 2 Xi-1, we have 20 2 (2) |W| > pk (b)) which results in A p*( - 2X0. Consequently,
(I Bo x..
2A0
2 1- Bo(v) + 2X0
--
Here we used Bo(v)= > Bu > 320 (V0/(20C))) log n)), which holds by definition of Bo(e) and our setting of parameters Bg and
Case (n 2 8), then intuitively k is robust enough to provide a reliable estimator for p* (v). More precisely, x/|W| E [B(+/[W]) -1 [[</|W]] [[]) with high probability - indeed r defined in terms of deliberately in exactly such way that this is guaranteed by Chernoff bounds. E(k/|W W1) = (*))), therefore
A'
x
E [X pb(()) -3k s - 23.-2],
W
and
B(c,k) (Bolu) + K -33k-
|W]
E [[Bo(v) + + p+())) 36- (Bo(v) + + .p(())(())))))))))))>))) . 36--2
Throouhoou the proof, we say 'low probability' to mean probability of n -0(C) where C can be set arbitrarily
high.
7

---

STITCH only reports failure if for some E V and k E [2,4] vertex v receives more requests for walks in (o) than [W+(v)|= = Bu,, k). Number of such request upper bounded by the number of edges ending in e generated by neighbors of v, say at level k 1. That is, the number of requests for Wx (v) in expectation at most
Σ wET(e)
Blw,k - 1)
E wer(v)
(Bo(w) + + pk- p())(()) -T 335-5
d(w)
d(w)
Σ d(w) Bo(w) + X pt((())))) -3h-5 (wE((v)
= (d(u) + X (P() 73k-5
(Bo(v)+ + p (v)) 73k-5
Since this is greater than 8, the actual number of requests is at most (Bu(v) + x (p()) 73h-4 Bu, k), with high probability by Chernoff. Therefore, STITCH indeed does not fail.
Finally, prove the memory bound. By setting of parameter 0, 7 -2 is at most constant. Also by the setting of parameters we have,
B(e, k) < (Bo(v) + AlloRA B*1+1,
.*]++.p((v)) (p)( 7 3k-2 ( - + +B (*))
and ΣvEr Ex=
0(1) Evev (Bo() B(v, B
Om logn B*
This gives us the proof of Theorem Now, one can easily extend this result the case when multiple sources for the starting vertex is considered. Theorem 2 is proven in Appendix A.
3 From random walks to local clustering
We now present two applications for our algorithm to compute random walks. In particular we show how to use it to compute PageRank vectors and how to compute local clustering. In interest of space, we only state here our main results and we defer all the technical definition and proofs to the Appendix.
Approximating PageRank using MPC random walks Interestingly. we can show that we can use algorithm a primitive compute PersonalizedPageeRan for node of for any input vector
Theorem (Approximating PersonalizedPageeRan using MPC random walks). For any starting single vertex vector (indicator vector), any a E (0, 1) and any there is a MPC algorithm that using (log E-log, B*) rounds of communication and the total amount of memory of O(m log n- B" Xe), outputs a vector q. such that q is n-additive approximation to (s), where B == 10a log n and E = 10
n
The proof is deferred to Appendix C.
Using approximate PersonalizedPageRRanl vectors to find sparse cuts Now can use the pre- vious result on PersonalizedPageRank to find sets with relatively sparse cuts. Roughly speaking, argue that for any set C' of conductance O(a). for many vertices approximate pr, (v) using our algorithms and perform a sweep cut over it, we can find a set of conductance O( log( (oo(())) This result stated in Theorem 3. The proof of this result is very similar the proofs of Section 5 of [ACL06], however since our approximation guarantees are slightly different, we need to modify some parts of the proof for completeness. The full proof is presented in Appendix Our main result of this subsection is stated below.
C, if calculate an
'e note that [BCXI1] also propose an algorithm compute Personalized vector but with the limitation that this could be computed only for single node and not for vector.

---

Empirical Evaluation
In this Section we present empirical evaluations of our algorithms for random walk generation, as well as clustering. As our datasets, we use several real-world graphs form the Stanford Network Analysis Project 14, LKF07, LLDM08, KY04, YL12]. The graphs undirected and come mostly (though not in all cases) from 'Networks with ground truth communities where the clustering application is most relevant. In order to demonstrate the scalability of main Algorithm graphs of varying sizes, as demonstrated in the table below.
Table 1: Summary of the various graphs used in our empirical evaluations.
NAME
VERTICES
EDGES
DESCRIPTION
CA-GRQC
5424
14,496
COLLABORATION NETWORK
AMAIL-ENRON
36,692
183,831
EMAIL COMMUNICATION NETWORK
COM-DBLP
317,080
1,049,866
COLLABORATION NETWORK
COM-YOUTURE
1,134,890
2,987,624
ONLINE SOCTAL NETWORK
COM-L.VEJJOURNAL
3,997,962
34,681,189
ONLINE SOCIAL NETWORK
COM-ORKUT
3,072,441
117,185,083
ONLINE SOCIAL NETWORK
The experiments were performed on Amazon's Elastic Map-Reduce system using the Apache Hadoop library. The clusters consisted of 30 machines, each of modest memory and computing power (Amazon's 's m4. large instance) so as to best adhere to the MPC setting. Each experiment described in this section was repeated times to minimize the variance in performance inherent distributed systems like this.
Practical considerations. In Section we worked with the guarantee that no walks "fail" in the stitching phase. This assumption can be fulfilled at nearly expense to the (asymptotic) guarantees in space and round complexity Theorem I, and make the proof much cleaner. In practice however, allowing some small fraction of the walks to fail allows for more relaxed setting of the parameters, and thus better performance.
Each experiment is performed with 15 roots, selected uniformly at random. The main parameters defining the algorithm are as follows: f- the length of target random walk (16 and 32 in various experiments), C - The number of cycles (iterations of the for-loop in Line 5 of Algorithm 2) performed. Bn the initial budget-per-degree of each vertex, À the approximate scaling of parameter defining the amount of excess budget
the budgets of the root vertices each cycle, used stitching. This is used somewhat differently here than in Algorithm 2. For more details see Appendix D.
4.1 Scalability
In this section we present the results of our experiments locally generating random walks simul- tancously from multiple root vertices. We use the graphs COM-DBLP, COM- COM-YOUTUBE, COM- LIVEJOURNAL. and COM-ORKUT, in order to observe how the runtime of Algorithm scales with the size of the input graph. In each of these graphs, 15 root vertices have been randomly chosen. We three experiments with various settings of the parameters, of which one is presented below. For additional experiments see Appendix D. By is set to be proportional to n/m that is inverse proportional to the average degree since the initial budget of each of each vertex is set to Bg times the degree of the vertex.
We report the execution time in the Amazon Elastic Map-Reduce cluster, as well as the number of rooted walks generated. Finally, under 'Walk failure rate", we report the percentage of rooted walks that failed in the last cycle of stitching. This is the crucial quantity; earlier cycles used only to calibrate the vertex budgets for the final cycle.*
For completeness, report the empirical standard deviation everywhere. Note, however, that due to the high resource requirement of these experiments, each one only repeated three times.

---

Table 2: Experiments with 16, == Bu 6n/m, X 32, T 1.4.
GRAPH
TIME
Bo
ROOTED WALKS GENERATED
WALK FAILURE RATE
COM-DBLP
23 = 7 MINUTES
1.812
96, 362 + 2597
14.6 = 0.6%
COM-YOUTUBY
31 = 6 MINUTES
2.279
53, 076 + 1185
10.8 4 0.5%
COM-LIVEJOURNAL
76 11 MINUTES
0.692
184, 246 + 756
7.9 - 0.1%
COM-ORKUT
13 MINUTES
0.157
200, 924 + 1472
3.4 0.0%
We observe that Algorithm& 2 successfully generates large number of rooted walks far more than the initial budgets of the root vertices. As predicted, execution time scales highly sublinearly with the size of the input (recall for example, that COM-ORKUT is more than a hundred times larger than COM-DBLP) The failure rate of walks decreases with the size of the graph in this dataset, with that of FOM-ORKUT reaching low 3.4% average; this may be due to the the higher average degree of our larger graphs, leading to the random walks spreading out more.
In Appendix D we report the results of two more experiments, including one with longer walks.
4.2 Comparison
In this section compare the previous work of [EMOS20] for generating random walks in the MPC model. This work heavily relies upon generating random walks from all vertices simultaneously. with the number of walks starting from given vertex being proportional d(v). In many applications. however, we are interested in computing random walks from small number of root vertices. The only way implement this using the methods of [LMOS20] enough to guarantee the desired number of walks from each vertex.
start with an initial budget large
We perform similar experiments those in the previous section albeit on much smaller graphs. Each graph has 15 root vertices chosen randomly, from which we wish to sample random walks. In Table set Bo to 1 and perform C 3 cycles of Algorithm 2 with X 10, effectively augmenting the budget of root vertices by a factor 100 by the last cycle. Correspondingly, we implement the algorithm of [t.MOS20] which call UNIFORM STITCHING by simply setting the initial budget 100 times higher, and performing only single cycle of stitching, ie.: By = 100, C =
Table Experiments with = 10, 1.3. The row labeled Algorithm 2' corresponds to Bu 1. C' = 3, while the row labeled 'Uniform Stitching' corresponds to Bo 100, C =
ALGORITHM
CA-GRQC
EMAIL-ENRON
COM-DBLP
ALGORITHM 2 UNIFORM STITCHING
15 1 1 MINUTES
19 + 1 MINUTES
18 1 1 MINUTES
7 O MINUTES
15 O MINUTES
66 MINUTES
We observe that the running time of our Algorithm barely differs across the three graphs, despite the nearly 100-factor difference between the sizes of CA-GRQC and COM-DBLP. At this small size, the execution time is dominated by setting up the 12 Map-Reduce rounds required to execute Algorithm with these parameters. As expected, the baseline far outperforms our algorithm the smallest graph; as the size of the input graph grows, however, running time deteriorates quickly. For larger setting of the parameters UNIFORMSTITCHHE memory requirement, as we can see Table in Appendix D.
can no longer complete on the cluster, due to the higher
Acknowledgments and Disclosure of Funding
This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (grant agreement No 759471).
10

---

References
[AC07] Alekh Agarwal and Soumen Chakrabarti. Learning random walks to rank nodes in graphs. In Proceedings of the 24th international conference on Machine learning. pages 9-16, 2007.
[ACE* 14] Lorenzo Alvisi, Allen Clement, Alessandro Epasto, Silvio Lattanzi, and Alessandro Panconesi. Communities, random walks, and social sybil defense. Internet Math., 10(3-4):30-4200, 2014.
[ACL06] R. Andersen, F. Chung, and K. Lang. Local graph partitioning using pagerank vectors. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS-06), pages 475-486, 2006.
[ASW19] Sepehr Assadi, Xiaorui Sun, and Omri Weinstein. Massively parallel algorithms for finding well-connectdd components in sparse graphs. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 461-470, 2019.
[BCXI1] Bahman Bahmani, Kaushik Chakrabarti, and Dong Xin. Fast personalized pagerank on mapreduce. In Proceedings of the 201 ACM SIGMOD International Conference on Management of data, pages 973 984, 2011.
[Ber07] Pavel Berkhin. Bookmark cooloing-coloring approach to personalized pagerank computing. Technical report, Internet Mathematics, 2007.
[BKS13] Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. In Proceedings of the 32nd ACM SIGMOD-SIGACT-SSIAA symposium on Principles of database systems, pages 273-284. ACM, 2013.
[BP98] Sergey Brin and Lawrence Page. The anatomy of a large-scale hypertextual web search engine. Comput. Networks, 30(1-7):107-117, 1998.
[CKK+18] 18] Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, and Yuval Peres. Testing graph clusterability: Algorithms and lower bounds. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 497-506 IEEE, 2018.
[CPS15] Artur Czumaj, Pan Peng, and Christian Sohler. Testing cluster structure of graphs. In Proceedings of the ferty-seventh annual ACM symposium on Theory of Computing. pages 723-732, 2015.
[CS15] Fan Chung and Olivia Simpson. Distributed algorithms for finding local clusters using heat kernel pagerank. In International Workshop on Algorithms and Models for the Web-Graph, pages 177-189. Springer, 2015.
[DG08] Jeffrey Dean and Sanjay Ghemawat. Mapreduce: simplified data processing on large clusters. Communications of the ACM, 51(1):107-113 2008
[DSGPII] Atish Das Sarma, Sreenivas Gollapudi, and Rina Panigrahy, Estimating pagerank on graph streams. Journal of the ACM (JACM), 58(3):1-19, 2011.
[DSMPU15] Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan, and Eli Upfal. Fast distributed pagerank computation. Theoretical Computer Science, 561:113 1211113-11,11 2015.
[DSNPTI3] Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, and Prasad Tetali. Dis- tributed random walks. Journal of the ACM (JACM), 60( 11)1131,, 2013.
[FR04] Dániel Fogaras and Balázs Ráez. Towards scaling fully personalized pagerank. Ste- fano Leonardi, editor, Algorithms and Models for the Web-Graph: Third International Workshop, WAW 2004, Rome, Italy, October 16, 2004, Proceeedings, volume 3243 of Lecture Notes in Computer Science, pages 105-117. Springer, 2004.

---

[GKL*21] Grzegorz Gluch, Michael Kapralov, Silvio Lattanzi, Aida Mousavifar, and Christian Sohler. Spectral clustering oracles sublinear time. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1598-1617. SIAM, 2021.
[GLMY11] Ullas Gargi, Wenjun Lu, Vahab Mirrokni, and Sangho Yoon. Large-scale community detection on youtube for topic discovery and exploration. Proceedings of the International AAAI Conference on Web and Social Media, volume 5, 2011.
[GS12] David Gleich and Seshadhri. Vertex neighhorhoods, low conductance cuts, and good seeds for local community methods. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 597-605, 2012.
[GSZ11] Michael Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and simulation in the mapreduce framework. In International Symposium on Algorithms and Computation, pages 374-383. Springer, 2011.
[Hav03] T.H. Haveliwala. Topic-sensitive pagerank: context-sensitive ranking algorithm for web search. IEEE Transactions on Knowledge and Data Engineering, 15(4):784-796 2003.
[HMMT18] Jeremy G Hoskins, Cameron Musco, Christopher Musco, and Charalampos Tsourakakis. Inferring networks from random walk-based node similarities. In Proceed- ings of the 32nd International Conference on Neural Information Processing Systems, pages 3708-3711 2018
[HZ96] Shay Halperin and Uri Zwick. An optimal randomised logarithmic time connectivity algorithm for the erew pram. Journal of Computer and System Sciences, 53(3):395-416, 1996.
[IB++07] Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. Dryad: distributed data-parallel programs from sequential building blocks. ACM SIGOPS operating systems review, volume 41, pages 59-72. ACM, 2007.
[Jin 19] Ce Jin. Simulating random walks on graphs in the streaming model. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego California, USA, pages 46:1-46:15, 2019.
[JW03] Glen Jeh and Jennifer Widom. Scaling personalized web search. In Proceedings of the 12th International Conference on World Wide Web, WWW '03, page 271-279, New York, NY, USA, 2003. Association for Computing Machinery.
[KNP92] David Karger, Noam Nisan, and Michal Parnas. Fast connected components algo- rithms for the erew pram. In Proceedings of the fourth annual ACM symposium Parallel algorithms and architectures, pages 373-381, 1992.
[KSV10] Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for mapreduce. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 938-948. SIAM, 2010.
[KY04] Bryan Klimt and Yiming Yang. Introducing the enron corpus. In CEAS, 2004.
[LK14] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http: / //t:://naappp. stanf ord. edu/data, data, June 2014.
[LKF07] Jure Leskovee, Jon M. Kleinberg, and Christos Faloutsos. Graph evolution: Densifica- tion and shrinking diameters. ACM Trans. Knowl. Discov. Data, 1(1):2, 2007.
[LLDM08] Jure Leskovec, Kevin J. Lang, Anirban Dasgupta, and Michael W. Mahoney, Com- munity structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. CoRR, 10./08100.155. 2008
12

---

[LMOS20] Jakub Lącki, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski. Walking randomly, massively, and efficiently. In Proceedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing, pages 364-377, 2020.
[MS00] Marina Meila and Jianbo Shi. Learning segmentation by random walks, Advances in neural information processing systems, 13:873-879) 2000.
[PBMW99] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical Report 1999-66, Stanford InfoLab, November 1999. Previous number = SIDL-WP-1999-0122
[SRFM16] Julian Shun, Farbod Moosta-Khorasani. Kimon Fountoulakis, and Michael W. Mahoney, Parallel local graph clustering. Proc. VLDB Endow. 912):1041-1052, 2016.
[ST04] Daniel Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 81-90, 2004.
[WGD13] Joyce Jiyoung Whang. David F Gleich, and Inderjit Dhillon. Overlapping community detection using seed set expansion. In Proceedings of the 22nd ACM international conference on information knowledge management, pages 2099-2108, 2013.
[Whi12] Tom White. Hadoop: The definitive guide. O'Reilly Media, Inc.", 2012.
[YL12] Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based on ground-truth. CoRR, abs/1205.6233 2012.
IZCF+ 10] Matei Zaharia, Mosharaf Chowdhury, Michael Franklin, Scott Shenker, and Ion Stoica. Spark: Cluster computing with working sets. HotCloud, 10(10-10):95 2010.
13


Reviews:
[{"review_id": "q6GhxoDhKv8", "reviewer": "Reviewer_vgtt", "summary": "The paper introduces an algorithm for computing multiple random walks in parallel. Performance is measured using the MPC model. The authors also show an interesting application to local graph clustering. The proposed algorithm improves upon memory requirements of SOTA methods at the cost a logarithmically many more iterations.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "I have three major comments that hopefully can be addressed.\n\n0. The authors seem to work on the distributed computer setting. However, for the application of local graph clustering, the target clusters are much smaller than the size of the graph. In fact, for large graphs, the target clusters have constant size and they do not grow with the number of nodes in the graph. This means that local graph clustering algorithms like ACL, take a fraction of a second to terminate and their memory footprint is also constant. For these reasons, I do not think that local graph clustering is the best application for the distributed setting. Even the datasets that you have chosen can fit in RAM of my personal computer. I think the authors should work on demonstrating an application where having multiple machines is necessary. \n\n1. The introduction of the paper is very technical. I could not understand what the authors are talking about until I read the proofs in the appendix. I actually believe that reading the proofs was much easier than trying to figure out what is going on from the main paper. I understand that it is important to mention all your contributions first, but the current text is dry. I had to reach page 4 to figure out what stitching is. \n\n2. For the application of local graph clustering, the authors have missed citing and discussing [1]. In this paper the authors work on shared-memory machines and they use the work-depth model. In [1] the authors follow a different approach for parallelization. In particular, the ACL method is a coordinate solver, thus instead of updating one coordinate at each iteration, the authors in [1] suggest to update as many coordinate as the number of threads, or if the the number of threads is larger than the eligible push nodes, then in [1] they update all eligible nodes. The authors of the submitted paper need to compare their approach with [1] both in theory and in practice.\n\nMinor comments\n\n3. Regarding the conductance guaranteed for your modification of ACL. I think you should simply state the minor points where the proof changes instead of re-writing the whole proof. \n\n4. Typo in line 34. \"From a\" instead of  \"From an\".\n\n5. Typo in line 45. \"that\" instead of \"than\".\n\n6. Typo in line 244. \"we\" instead of \"wee\".\n\n7. Lines 520-521 in the appendix. This sentence seems incomplete. \n\n[1] J. Shun, F. Roosta-Khorasani, K. Fountoulakis, M. W. Mahoney. Parallel Local Graph Clustering. Proceedings of the VLDB Endowment, Volume 9, Issue 12, August 2016 pp 1041–1052.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours."}, "extra_text": {}}, {"review_id": "m-gfbuFCI5B", "reviewer": "Reviewer_oy5A", "summary": "This paper studies the problem of implementing random walks in the Massively Parallel Computation (MPC) model using logarithmic number of rounds.  Very recently, [LMOS20] develop a MPC algorithm that using O(log \\ell) rounds, computes (independent) random walks of length up to \\ell from every node in an arbitrary undirected graph. Their main idea is based on stitching: In order to compute walks of length r, we can stick together two walks of length r/2 and we can do this stitching procedure recursively using O(log \\ell) rounds. One issue with this algorithm is that if we want to do a few walks starting from a few nodes, this algorithm still implements all walks for all nodes. In particular, for say B walks of length \\ell, the algorithm of [LMOS20] uses O(mB) total memory (for all machines).\n\nThe current paper claims to solve this issue by proposing a MPC algorithm that uses a total memory of O(mn^{eps}\\ell^4+Bn^{eps}\\ell) and computes B walks of a given vertex r. The number of communication rounds of this new algorithm is slightly more and is O(log(\\ell)/eps).", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The paper is written poorly. I spent 7-8 hours to read the paper, but I don’t understand the main algorithm. In particular, the budgeting section which is the novelty of this paper is not clear to me. The overview of Algorithm 2 is very unclear and the pseudocode of Algorithm 2 uses lots of notations that have not been properly defined and is very complicated to understand it. Overall, the claims in this paper are nice, but I cannot verify them using this writeup. \n\nComments:\n\n1- Line 36, there is a typo: “of of ...“\n2- The parameters and notations used in this paper are not clearly defined. For example, in Line 66, Theorem 1, for the first time m is used, but it doesn’t say what m is. In the standard graph theory notation n and m are the number of vertices and edges in. A graph, I am guessing this should be the case here, but it can be written explicitly. \n3- I don’t understand why we have an informal version of theorems in this paper. Theorem 1 is the same as Theorem 4. Why is one of them informal and the other formal. Why Theorem 2 is informal? \n4- In Remark 1 (Line 78), in the total memory once \\Lambda is replaced with n^{eps} and next to it is not replaced. \n5- Lines 159 and 178, there are two paragraphs for Budgeting. \n6- Line 146, the definitions W_k(v) and  B(v,k) are not clear. B(v,k) is defined in this line, but then in line 159, for the first time is written that B(v,k) is a budget. Why didn’t you define this in Line 146? \n7- Section 2.1 gives an overview of the algorithm, but this overview is not precise. In Line 150 they explain the stitching procedure, but they only explain the first round. \n8- What is \\tau in Algorithm 2.\n9- The stitching algorithm (Algorithm 2) is very complicated and long. You can split this procedure to subroutines where the machines requests for walks (v,k) and the the surboutines where the other machines respond. \n10- Algorithm 2 is very hard to read. What is line 7 in this algorithm? Using \\kappa in Line 9 and above it k are very confusing. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours"}, "extra_text": {}}, {"review_id": "Xq64ws0zP7B", "reviewer": "Reviewer_oXY3", "summary": "This submission gives an algorithm in the MPC model (Massively Parallel Computation) for computing independent random walks from a single vertex or a subset of vertices. A previous paper, [LMOS], on the topic gave an algorithm that allowed for generating random walks from all vertices simultaneously (more specifically, the starting points of generated walks were from the stationary distribution). Suppose that you want to generate many random walks from a single vertex. [LMOS] would require generating lots of random walks from all vertices and because of that would require a lot of total space available in the system, and therefore, it would require a lot of machines. The algorithm introduced in this submission can be significantly more space efficient in this type of setting.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "\nThe solution follows the usual idea of stitching shorter random walks in order to create longer random walks. In consecutive rounds, random walks of length 2^k are turned into random walks of length 2^{k+1}. An obstacle that any such method has to overcome is that some of the length 2^k random walks may not have extensions. [LMOS] overcame this obstacle by using the stationary distribution, so the rough number of extensions that are needed is known in advance at the cost of large total space requirement. To avoid this, the paper runs several attempts at creating random walks and adjust based on them the distribution from which short random walks are generated. Overall, this solution is not very difficult in hindsight but it is neat and its simplicity allows for implementing the algorithm.\n\nThe submission also explores applications of random walks to computing Personalized PageRank and clustering. Furthermore, it shows experiments in which it positively compares the performance to [LMOS].\n\nApart from typos and small grammatical errors, the paper is well written and presents the main ideas very clearly. \n\nIn my opinion, the paper addresses a well-motivated question with real world applications in a practical model of computation. It would be great to see this paper in NeurIPS.\n\n----\nI suggest that the authors spend some time proofreading the paper and fixing spelling and small grammatical errors.\n\nl.25: has -> have\n\nl.34: an high -> a high\n\nl.41: \"a random walk\" or \"random walkS\"\n\nl.50: in details -> in detail\n\npage 4: Two paragraphs are titled \"Budgeting\". Was this intended?\n\nPage 3 and 4 have the same footnote.\n\nwee -> we\n\n----------------\n\nEdit: I acknowledge reading the rebuttal from the authors.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no concern about negative social impact.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "Q6ucsuAxBN0", "reviewer": "Reviewer_a4aA", "summary": "This paper studies the problem of parallelizing single-source and subset random walk computations. The primary technical contribution is an algorithm with the number of parallel rounds that depends on the length of the random walk in a logarithmic way. In addition, two applications are discussed in the article: personalized PageRank estimation and local clustering.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Weak points:\n\nW1. The presentation of the paper needs significant improvement. First, there are numerous confusing statements, spelling problems, and typos, making it impossible for me to determine the paper's contributions. More comments can be found under \"Minor Comments.\"  Second, the work lacks the intuition needed to describe the algorithms and proofs, making it nearly impossible for non-experts to comprehend. For example, what is the purpose of k in the Stitching algorithm? What's the difference between odd and even k? More in-depth explanations are anticipated. Finally, some important sections and proofs have been left out. The concluding section, for example, is missing. The preliminaries have been moved to the appendix. The formal version of Theorem 1 is missing. Furthermore, the proof of Theorem 1 has been omitted. \n\nW2. Some proofs aren't as rigorous as others: \n\n(1) Does Remark 1 require the existence of B*<n in order to derive the round complexity: O(log{\\ell}log{B*}/(eps*logn))<O(log{\\ell}/eps) ?\n\n(2) The error analysis appears to be missing in the proof of Theorem 6. Why is it that B* random walks can guarantee a low TVD error? \n\n(3) Based on the stationary distribution of random walks, the Budgeting algorithm initializes B(v,k) as B_0\\*deg(v). The stationary distribution pr_alpha=alpha\\*s*(I-(1-alpha)*W)^{-1} is difficult to obtain for the Personalized PageRank. How should we initialize B(v,k) in the context of Personalized PageRank? \n\nW3. There are a few key experiments that are lacking:\n\n(1) The paper only compares the proposed technique to one baseline (LMOS20) in Section 4.2. On both the GRQC and ENRON datasets, however, LMOS20 beats the proposed technique. Furthermore, the results on LiveJournal and Orkut are omitted.  Thus, the empirical effect of the suggested method is difficult to justify. \n\n(2) Experiments for finding local sparse cuts and approximating Personalized PageRank should be provided. \n\n\nMinor comments: \n\nThere are various mistakes and confusing descriptions in the present version. A list of minor comments is shown below. \n\nM1: In Remark 1, lambda should be replaced with n^eps in the total memory complexity. \n \n\nM2: In Theorem 3, the definition of \\Phi(C) is omitted. \n \n\nM3: The definition of eps is omitted in Theorem 4. Furthermore, eps appears to be irrelevant for obtaining Theorem 4's complexity results. \n\nM4: The assumption \"each vertex v has its own machine that stores its neighborhood\" is stated twice in lines 136 and 142. One of them can be removed. \n\nM5: can simulate -> we can simulate in Theorems 2 and 4. \n\nM6: Line 85, Page 2: dependen -> dependent. \n \nM7: Line 105, Page 3: then -> than \n\nM8: Line 123, Page 3: As mentioned before our main idea -> As mentioned before, our main idea… \n\nM9: Lines 135, Page 3, and 142, Page 4: assume that -> we assume that.\n\nM10: Line 148, Page 4: After the initial round of edge generation W_k(v) consists of … -> After the initial round of edge generation, W_k(v) consists of ….\n\nM11: Line 159 and line 178, Page 4: There are two headings both named as \"Budgeting\".\n\nM12: Line 180, Page 4: and to do we initialize -> and we initialize. \n\nM13: Line 182, Page 4: The key observation is that to do it we need to \n\nM14: Line 189, Page 4: thee -> the. \n\nM15: Line 270, Page 8: machines each of modest memory … -> machines. Each of them has modest memory …\n\nM16: Line 473, Page 13: of the supplementary material: the formal definition of TVD error is omitted.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no evidence that this work will have a detrimental effect on society.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8h"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers uniformly liked the algorithmic contribution of the paper. However, there were serious concerns about the writing quality of the paper. The reviewers strongly encourage the authors to polish the paper.
Overall, the quality of the contributions were deemed to be of significant interest to warrant an accept.
Decision: Accept (Poster)