Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.

main_review: 
The 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.

The 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].

Apart from typos and small grammatical errors, the paper is well written and presents the main ideas very clearly. 

In 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.

----
I suggest that the authors spend some time proofreading the paper and fixing spelling and small grammatical errors.

l.25: has -> have

l.34: an high -> a high

l.41: "a random walk" or "random walkS"

l.50: in details -> in detail

page 4: Two paragraphs are titled "Budgeting". Was this intended?

Page 3 and 4 have the same footnote.

wee -> we

----------------

Edit: I acknowledge reading the rebuttal from the authors.

limitations_and_societal_impact: There is no concern about negative social impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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).

The 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).
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. 

Comments:

1- Line 36, there is a typo: “of of ...“
2- 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. 
3- 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? 
4- In Remark 1 (Line 78), in the total memory once \Lambda is replaced with n^{eps} and next to it is not replaced. 
5- Lines 159 and 178, there are two paragraphs for Budgeting. 
6- 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? 
7- 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. 
8- What is \tau in Algorithm 2.
9- 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. 
10- 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. 
limitations_and_societal_impact: None
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
main_review: Weak points:

W1. 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. 

W2. Some proofs aren't as rigorous as others: 

(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) ?

(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? 

(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? 

W3. There are a few key experiments that are lacking:

(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. 

(2) Experiments for finding local sparse cuts and approximating Personalized PageRank should be provided. 


Minor comments: 

There are various mistakes and confusing descriptions in the present version. A list of minor comments is shown below. 

M1: In Remark 1, lambda should be replaced with n^eps in the total memory complexity. 
 

M2: In Theorem 3, the definition of \Phi(C) is omitted. 
 

M3: The definition of eps is omitted in Theorem 4. Furthermore, eps appears to be irrelevant for obtaining Theorem 4's complexity results. 

M4: 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. 

M5: can simulate -> we can simulate in Theorems 2 and 4. 

M6: Line 85, Page 2: dependen -> dependent. 
 
M7: Line 105, Page 3: then -> than 

M8: Line 123, Page 3: As mentioned before our main idea -> As mentioned before, our main idea… 

M9: Lines 135, Page 3, and 142, Page 4: assume that -> we assume that.

M10: 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 ….

M11: Line 159 and line 178, Page 4: There are two headings both named as "Budgeting".

M12: Line 180, Page 4: and to do we initialize -> and we initialize. 

M13: Line 182, Page 4: The key observation is that to do it we need to 

M14: Line 189, Page 4: thee -> the. 

M15: Line 270, Page 8: machines each of modest memory … -> machines. Each of them has modest memory …

M16: Line 473, Page 13: of the supplementary material: the formal definition of TVD error is omitted.
limitations_and_societal_impact: There is no evidence that this work will have a detrimental effect on society.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: I have three major comments that hopefully can be addressed.

0. 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. 

1. 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. 

2. 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.

Minor comments

3. 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. 

4. Typo in line 34. "From a" instead of  "From an".

5. Typo in line 45. "that" instead of "than".

6. Typo in line 244. "we" instead of "wee".

7. Lines 520-521 in the appendix. This sentence seems incomplete. 

[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.
limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

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)