Iterative Methods via Locally Evolving Set Process

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.

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.

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.

General Responses

We thank all reviewers for their time and effort in carefully reading our paper. We are very happy that you like our work. Some general concerns are worth discussing as follows:

Q1. Comments on the assumption of the local Chebyshev (LocCH) method.

A: Let us recall that our Theorem C.6 (Standard CH) provides a runtime bound for the standard Chebyshev method. The total number of operations is bounded by

where $m$ is the number of edges. Our key lemma, Lemma 4.1 (Line 246), captures the evolving process of the local Chebyshev method. By considering the geometric mean reduction on $\beta_t$ and using Lemma 4.1, LocCH has the following runtime bound:

where $\overline{\operatorname{vol}} ({\mathcal S } _T)$ is the averaged volume and $y_T$ is defined by $y _ {t+1}-2 y _t+y _{t-1} / ( (1+\beta _{t-1}) (1+\beta _t ) )=0$. Ideally, when $\epsilon \rightarrow 0$, it roughly indicates the local solver is getting closer to the global one. This leads to $y_T \rightarrow 1$, $\overline{\operatorname{vol}} ({\mathcal S } _T) \rightarrow m$, and $c \rightarrow 0$ where $c$ is the parameter defined via the geometric mean of $\beta_t$. However, verifying how strong or weak this assumption is can be difficult. The main reason is the convergence of the second-order difference equation itself is complicated and makes the analysis harder. We are investigating and exploring alternative directions now. A more reasonable approach might be to consider a typical example on a chain graph, where one can obtain a much simpler formulation for $y_t$. We will develop a refined analysis for specific graph types in future work.

Q2. Comments on the parameter regimes in which local algorithms get used.

A: The range of $\epsilon$ that is useful in real-world applications depends on the specific task. However, as far as we know, the speedup over standard solvers can be applied to a wide range of downstream tasks. Let's look at typical examples to see when $\epsilon$ is sufficient or useful in practice. For the local clustering algorithm, in Fountoulakis's paper (see Fountoulakis's work in [1]), they used $\epsilon = 10^{-5}$ where the number of nodes in graphs is in the range $[2\times 10^6, 3\times 10^6]$. This is around $\epsilon \approx 1/n$ (roughly corresponding to the largest speedup shown in Figure 4, where the dashed vertical lines are $\epsilon = 1/n$). For learning GNN models, PPRs are used to train the PPRGo model (see Bojchevski's work in [2]); the parameter $\epsilon$ used is $10^{-4}$ where the number of nodes in graphs is in the range $[1.87\times 10^4, 1.05 \times 10^7]$. This means $\epsilon \leq 1/n$ in all graphs. We found similar parameter settings in graph embedding and online graph node classification.

Overall, the effective range of $\epsilon$ is $\epsilon \leq 10^{-4} / n$, where the speedup is significant, as presented in Fig. 4. This should cover most interesting downstream tasks where PPR is a crucial tool.

Q3. Is the dependence on $\epsilon$ optimal?

A: Let us recall that the runtime bound is optimal for the standard Chebyshev method. Specifically, the first-order optimal methods (such as Chebyshev) for linear systems have the runtime bound $\mathcal{O}(m/\sqrt{\alpha} \cdot \log 1/\epsilon)$. This runtime bound is optimal for finding a solution of a sparse linear system defined on a chain graph (see Theorem 3.15 of Bubeck's work in [3] for more details).

We believe this is true in terms of the optimal local first-order methods for local solvers. However, it remains interesting to see whether the lower bound can be identified, where one may find that it matches the bound conjectured in Line 295 of our manuscript.

References

• [1] Fountoulakis, K., Roosta-Khorasani, F., Shun, J., Cheng, X., & Mahoney, M. W. (2019). Variational perspective on local graph clustering. Mathematical Programming, 174, 553-573.

• [2] Bojchevski, Aleksandar, Johannes Gasteiger, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik, and Stephan Günnemann. "Scaling graph neural networks with approximate pagerank." In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2464-2473. 2020.

• [3] Sébastien Bubeck, Convex Optimization: Algorithms and Complexity, https://arxiv.org/pdf/1405.4980.

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

This paper introduces a novel approach to efficiently compute approximate personalized PageRank (and more generally for sparse linear systems) based on a locally evolving set process. It further develops localized versions of chebyshev and heavy ball methods that achieve a $1/\sqrt{\alpha}$ dependence in the number of iterations necessary for approximating pagerank with dampening factor $\alpha$, in contrast with the $1/\alpha$ dependence for the classic algorithm by Andersen-Chung-Lang. This dependence is optimal, and the authors also present simulations that suggest an empirical advantage for small enough target accuracy.

The reviewers were positive about the paper, highlighting the novel technical contributions. There were some concerns about the empirical advantage being realized only for very small approximations, but I think this is an overall solid contribution.