Iterative Methods via Locally Evolving Set Process

Summary

This paper considers the study of local algorithms for graph clustering which is an important problem in the field of graph data analysis. In particular this paper is considers the task of computing Personalized Page Rank (PPR) vectors for a given graph. In this problem the algorithm is given a graph in the form of its adjacency and degree matrices, the goal is to approximate the Personalized Page Rank vector for a given starting vertex and dampening factor $\alpha$ up to precision $\epsilon$ without accessing the entire graph. The classical algorithm of Andersen, Chung and Lang runs in time $O(1/\alpha \epsilon)$, which independent of the graph size. The central question posed by subsequent works is whether the dependence on $\alpha$ can be improved to $1/\sqrt{\alpha}$. The main contribution of the paper is to propose a new algorithmic framework based on the locally evolving set process. Under this framework they are able to implement existing algorithms such as Andersen et al.'s APPR algorithm as well as localized implementation of standard gradient descent. They are also able to develop localized versions of chebyshev and heavy ball methods that do achieve the $1/\sqrt{\alpha}$ dependence for some fixed constant value of $\epsilon$. Finally they show that on several large scale graphs, their new localized chebyshev and heavy ball methods do outperform APPR and related methods empirically.

Strengths

The main strengths of this paper are to develop a new algorithmic framework that can not only encompass existing algorithms but lead to the development of better ones that overcome previously known limitations for designing local graph clustering algorithms. They also back their theoretical analysis with the practical implementation of their method which is also shown to be superior to previous algorithms.

Weaknesses

One weakness is that the paper is only able to obtain a quadratic improvement in the dependence on the parameter $\alpha$, obtained by the local implementation of the Chebyshev and Heavy-ball method, only for a value of $\epsilon$ and not for all.

Questions

One question is that what is the core reason for not obtaining convergence result for accelerated methods for all $\epsilon>0$.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Authors have addressed limitations.

Summary

This paper uses the evolving set procedure to give a local PageRank algorithm whose dependence on \alpha (the reset probability) is \sqrt{\alpha}. It proposes accelerated local iterative methods with coefficients given by Chebyshev iteration. The convergence of this algorithm in both graph theoretic and general sparse linear systems settings are analyzed in detail. Discussions of the relations between this method and other local iterative algorithms are also given in detail. The method was implemented and tested on a range of graphs, mostly coming from social networks. This includes two large ones with edges in the billions. On moderate ranges of \alpha (reset probability), the experiments show significant speedups (factor of about 3) and convergences (factor of 10) on most graphs.

Strengths

Local algorithms are widely used in graph analytics. The question studied is natural, and has been proposed before. The method is theoretically well-founded, and has significant technical depth. The experiments are thorough and well documents, and clearly demonstrate the advantages of this method in multiple parameter regimes.

Weaknesses

The gains only kick in at a relatively large number of steps: it's not clear to me that these are the parameter regimes in which local algorithms actually get used. Ideally for the empirical works I'd also like to see comparisons of downstream tasks and effects on overall accuracies (e.g. F-1 score), but the paper itself has already covered a lot of ground.

Questions

Is the dependence on \epsilon optimal? Aka. have methods with \sqrt{\eps} (or even \log(1 / \eps)) dependences been ruled out?

Rating

9

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

yes, limitations have been addressed, and are entirely theoretical w.r.t. some graph parameter regimes.

Summary

This paper considers the approximate personalized page rank. Classical results for this problem have a runtime that is linear in $1/\alpha\epsilon$ where $\alpha$ is the damping factor and $\epsilon$ is the error parameter. The authors show that APPR is simply a local variant of Gauss-Seidel Successive Overrelaxation. Using this connection, the authors derive new run time bounds for APPR and also propose a new algorithm based on Gradient Descent. The execution time for both these are, in the worst-case, identical to the previous bounds. However, they are more sensitive to the state of execution of the algorithms (depend on the active nodes) and seem to mirror the actual performance of these algorithms. Also, under certain assumptions, they improve the worst-case execution time.

Strengths

The paper addresses an important problem, provides deeper insights into an existing algorithm, provides a new algorithm and also reanalyzes the algorithm in a more fine-grained way. All of this is done via connection to GSSOR which seems to be new. I find the result quite interesting. However, I am not very familiar with recent work on personalized page rank. For this reason, I recommend accepting but with a low confidence.

Weaknesses

NA

Questions

Can you explain how weak/strong are the assumptions that you make to achieve the improvement for the local Chebyshev method? I couldn't quite gauge the usefulness of this result.

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

NA

thank you

Thank you for the detailed comments / clarifications. It's good to know the \epsilon regime being considered here. However, my worry is that in such parameter regimes, non-local things with some dependencies on n might start winning. This is, of course, beyond the scope of this work, or even this discussion. So I'll keep my review/score unchanged.

Response to rebuttal

Thanks to the authors for answering the question. My score remains the same.

Thank all reviewers for their time and effort in the discussion and for helping us.

We sincerely thank all reviewers for their time and effort in the discussion and for helping us; we will keep improving our submission.