Accelerated Evolving Set Processes for Local PageRank Computation
Authors: BinbinHuang
Luo Luo
Yanghua Xiao
Deqing Yang
Baojian Zhou
Venue: NeurIPS 2025 poster ()
Keywords: Personalized PageRank
Local methods
Sublinear methods
Primary area: general_machine_learning
TL;DR: we propose a new local acceleration framework based on inexact proximal operators (e.g., Catalyst acceleration).

Abstract: This work proposes a novel framework based on nested evolving set processes to accelerate Personalized PageRank (PPR) computation. At each stage of the process, we employ a localized inexact proximal point iteration to solve a simplified linear system. We show that the time complexity of such localized methods is upper bounded by $\min\{\tilde{\mathcal{O}}(R^2/\epsilon^2), \tilde{\mathcal{O}}(m)\}$ to obtain an $\epsilon$-approximation of the PPR vector, where $m$ denotes the number of edges in the graph and $R$ is a constant defined via nested evolving set processes. Furthermore, the algorithms induced by our framework require solving only $\tilde{\mathcal{O}}(1/\sqrt{\alpha})$ such linear systems, where $\alpha$ is the damping factor. When $1/\epsilon^2\ll m$, this implies the existence of an algorithm that computes an $\epsilon$-approximation of the PPR vector with an overall time complexity of $\tilde{\mathcal{O}}(R^2 / (\sqrt{\alpha}\epsilon^2))$, independent of the underlying graph size. Our result resolves an open conjecture from existing literature. Experimental results on real-world graphs validate the efficiency of our methods, demonstrating significant convergence in the early stages.

Accelerated Evolving Set Processes for Local PageRank Computation
Binbin Huang
Luo Luo 1,2
Yanghua Xiao Deqing Yang 1.3 Baojian Zhou 1,3-
School of Data Science, Fudan University, Shanghai Key Laboratory for Contemporary Applied Mathematics,
Shanghai Key Laboratory of Data Science, School of Computer Science, Fudan University bbhuang24@m. fudan. edu. en luoluo, shaluo,,haayh..yyaggeeiiii bj zhou@fudan. edu. cn
Abstract
This work proposes a novel framework based on nested evolving set processes accelerate Personalized PageRank (PPR) computation. At each stage of the pro- cess, we employ a localized inexact proximal point iteration to solve simplified linear system. We show that the time complexity of such localized methods is up- per bounded by min (e²), {m)) to obtain e-approximation of the PPR vector, where m denotes the number of edges in the graph and R a constant defined via nested evolving set processes. Furthermore, the algorithms induced by framework require solving only ((L/va) such linear systems, where is the damping factor. When 1/e² < m, this implies the existence of an algo- rithm that computes e-approximation of the PPR vector with overall time complexity of O(R? ((vae))) independent of the underlying graph size. Our sult resolves an open conjecture from existing literature [09. 52].. Experimental results real-world graphs validate the efficiency of our methods, demonstrating significant convergence in the early stages.
Introduction
We study efficient local methods for computing the PPR vector IR", defined by
I (1 aI + AD-
ae.,
(1)
where e, E I2 is the standard basis vector corresponding the source node E and (0, is the damping factor. Here, A E R"** and D E Raxn are the adjacency and degree matrices of an undirected graph &(V,E) with n [V] nodes and m | edges, respectively. The vector measures the importance of nodes in V from the perspective of the source node which is the steady-state distribution of a lazy random walk on G. Specifically, given a precision parameter e, our goal is to design local algorithms that compute an e-approximation म, i.e., one that satisfies | - т T)lo < e, while avoiding access to the entire graph.
Andersen et al. [4]] proposed the first local method, called the Approximate Personalized PageRank (APPR) algorithm, approximate π, achieving time complexity of ((1((ac)). To further charac- terize the locality of π, Fountoulakis et al. [2]] introduced a variational formulation of Eq. (I) and applied proximal gradient method to compute local estimates with a comparable time complexity to APPR. Both methods critically rely on the monotonically decreasing & -n-mr of the residual (or gradient) to ensure the time complexity remains locally bounded.
Note that Eq. (II can be reformulated as a strongly-convex minimization problem with condition number 1/a. It natural to ask whether accelerated local methods can be designed with time
"Corresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

complexity that depends on 1/v [19] However, the main challenge lies in the fact that accelerated methods [TT.. [9] typically involve momentum terms, which disrupt the key property, namely the monotonically decreasing f1-norm of the residual (or gradient), relied on by existing local algorithms [.) 20 As a result, standard accelerated methods may access up to n nodes per iteration, leading to known upper bounds of (mm/Va) for solving Eq. (... To preserve monotonicity, Martínez-Rund Rubio et al. [[9]] proposed subspace-pursie style algorithm that performs accelerated projected gradient descent (APGD) in each iteration; however, the number of APGD calls required can still be as large as O((S*)), where S is the support of the optimal solution. Recently, Zhou et al. [52]] introduced a localized Chebyshev method inspired by the evolving set process [[8], However, the proposed method is heuristic, and its convergence remains unknown, as the accelerated local bounds rely heavily on the assumption that the gradient norm decreases at each iteration.
This work develops a locally Accelerated Evolving Set Process (AESP) framework that provably runs ((1/Va) short evolving set processes instead of a single long one. Our AESP is based on inexact accelerated proximal point iterations to accelerate APPR. Each stage guarantees a monotonic decrease in the f--nrrm of the gradient by using local methods to solve a regularized PPR linear system with constant condition number. Hence, converges faster than APPR in the early stages,
Let (St) and Tt denote the average volume and the average f--nrrm of the gradient ratio of the active nodes processed at the t-th round. We show that each evolving set process has a time complexity of ((vol(S))/7.) and that AESP-induced algorithms have a total time complexity of Ō ((vol(5))/(Va7))) matching the accelerated bound conjectured by Zhou et al. [52]]. Additionally, we prove that vol(S.)/7, admits an upper bound of m /e²,, 2m,), where R is a constant defined via nested evolving set processes. As result, the algorithms induced by AESP achieve time complexity bound that reflects a trade-off between the dependence on the condition number 1 \/a and the per-round time complexity O /²) The AESP framework is also well-suited for solving the variational formulation of Eq. (M), as studied by Fountoulakis et al. [20]] with the potential to achieve an accelerated time complexity.
To summarize,
We propose an Accelerated Evolving Set Process (AESP) framework, which computes an approximation for PPR using ((1/va)) short evolving set process. Our framework is built upon the inexact proximal point algorithm, and naturally extends to solving the variational formulation of Eq. (I)) Furthermore, the algorithms induced by AESP are parameter-frre.
Our accelerated methods are guaranteed to converge without any additional assumptions. We establish theoretical guarantees for the induced algorithms with the time complexity of Ó ((vo((5))((V777) which matches the accelerated bound conjectured in the existing literature. This result improves upon existing (vvo((S)) (aT))) from standard local methods. Furthermore, show that vol(S.) /T, is bounded above by min(O(RR) /e²), 2m). which implies that the over- all time complexity ORR² /(Vac²) is independent of the underlying graph size when 1/e² < m.
Experimental results on large-scale graphs confirm the efficiency of our method. Unlike standard local methods, AESP-based methods demonstrate significant speed-up during the early stages. Our code is publicly available for review and will be open-sourced upon publication."
Preliminaries
Notations and definitions. Throughout this paper, we assume that the underlying simple graph G(V,E) is undirected and connected, with n = [V] nodes and m = [8] edges. The adjacency if there exists an edge (u,w) E E, and due =
matrix of G is denoted by A = (duv)) where due otherwise. The set of all neighbors of a node is denoted by (v). The degree matrix D is diagonal and has each entry D.w = d, = [.()) set of its nonzero indices: supp(æ) (x) := {u E in] Ze * 0}. The volume of node set S C V is defined as the sum of all node degrees in S, i.e., vol(S) = -vvss dy. Note vol(V) = 2m. For an integer T, we denote [T] == {1, ,,......Ty T}.
J. For æ E RR"," the support of æ, denoted by supp(æ), ), is the
For details on the importance of local PPR computation and related work. see Appendix

---

We say that differentiable function : R" + R is p-sttrongly convex if there exists a constant j such that Va, y R" g(y) 2 g(æ) + (Vg(z). y + u y12/2. where Vg(az) the gradient of at a. We say 9 R" - IR is L-smooth if there exists L > such that Va, E R", g(y) S g(x)) + (Vg(m), y m) T. v12/2. The u-th entry of Vg(æ)) is denoted as Vug(.). When is convex and given a smoothing parameter 7), the proximal mapping of at y is given by
{g(x) + ||e yy1 where > 0.
prox 9/1 (y) = arg min
(2)
=ER"
With slight abuse of notation, we define the D1/2- gradient of g at æ as (g)
D and the D D-1/2-scaled gradient Vg-1/2(00) D gg1//
2.1 Problem reformulations and properties
We solve the linear system in Eq. (lI by reformulating it as the following optimization problem
min {[
1 x TQ oar D'DD" 1/22 2
(PI)
where Q A 1+a I 1-a D D-2 1/2, with the eigenvalues satisfying X(Q) E [a,, 1], and b is sparse vector. The function f both j-strongly convex and L-smooth, with μ and 1. The optimal solution of (PII) denoted by zj := =QQ* D D-1/2b. When b es, it implies
D'" We define the set of e-approximation solutions to PII as
P(e, b, 9) & {x: | x se).
Based on the above reformulation. we aim to design faster local methods that find a P. To ensure 2 is sparse, prior works [20 37] considered the following variational reformulation
min =ER
(xx)) & f(x) 2a
(P2)
Let a.. A arg min (ax be the optimal solution of (P2). When e, the first-order optimal condition implies that x. E Pee,, ar e..g). 9). The next two lemmas present properties PPR vectors and the optimal solutions of our reformulated problems,
Lemma 2.1 (Properties of π). Define the PPR matrix II, = a (0 ( - L-n AD-1)- Let the estimate-residual pair (p, r) for Eq. (II) satisfy r = Eg -II," p. Then,
The PPR vector is given by π IL which is a probability distribution, i.e., Vi E V. 0 and || 1. For e > 0, the stop condition D 'r10o0 < e ensures | |D-
(p T T) < E.
The matrix aQ- fi-norm of II satisfies ||Ta]]] ||D-1II,
2 is similar to the matrix II, ie., 1/ D-11/22 II,-- Furthermore, the
"II, D D1lco =
Lemma 2.2 (Properties of a and wt)) Denote the gradient of I at as Vs(x)) = 1xD-DD1122 and optimal solution x² = aQ-1111111 D 1/2b satisfying ग = D2/2 Define = 1/2 Then,
The stop condition
D 1/2 [m) < ae implies D- T) <e
The objective f is u-strongly convex and L-smooth with two constants a and L = 1. When e, then s P(e, ax, e,, and the solution is sparse, i.e., [supp(=;)) < 1/2.
2.2 Inexact accelerated proximal point framework
The inexact accelerated proximal point iteration is a well-known technique improve the conver- gence rate of ill-conditioned convex optimization problems. It approximately solves sequence of well-conditioned subproblems using linearly convergent first-order methods, thereby reducing the overall computational cost (see Chapter 5 in [I6].. Catalyst [62]] is representative example of
Prooff' of lemmas and theorems are postponed to the Appendix A

---

such methods. It employs base algorithm to approximate the proximal operator, corresponding to solving an auxiliary strongly convex optimization problem. Specifically, starting with initial points (0) ( for 2 Catalyst finds an approximate at z // (t)))) for solving (PI), and (e() = prox (v ((((())) for solving (P2), where the prox operator is defined in Eq. (2). Given
smoothing parameter 77 and an accuracy yp > O, x+(1) is guaranteed in the set of p-approximations of the proximal operator proxf/v //xx///((((t1 (x))-) denoted by H(pp) & {i E R" h(()) h- S {}} with h(z) = fz) + 1 - = =12 and h" is the minimum of h. Then, x(() attains (pp) precision by updating ( x1() + (,(((() (t) xx(-1) where { are momentum weights. However, directly
applying this method still results in the standard accelerated time complexity of (m/ (m//a)). The next section shows how to significantly reduce this bound to a local one using the AESP framework.
3 Accelerated Evolving Set Processes
This section presents our main results. We first introduce the nested ESP and propose two local inexact proximal operators. We then establish the accelerated convergence rate of AESP. Finally, we discuss potential improvements to this rate and its connections to related problems.
3.1 Nested evolving set process
Our method generates estimates (2(4) At each outer-loop iteration f, local solver M maintains a sequence of active sets (s((a) k=2 over the inner-loop iterations k. Updates are restricted to nodes within the active set, which is used to refine the approximation (k) in the inner loop. The next set s!t g(++1)
Oura
# of Operations
determined solely by s(k) We refer to this procedure as the nested evolving set process, defined follows.
Iterations (4)
Definition 3.1 (Nested evolving set process (ESP)). Given the configuration - (a, G), and local method M, the nested evolving set process outer-loop iteration L gener-
Figure 1:
The comparison of vol-
umes of ESP for APPR and Ours.
ates a sequence of {S!tt (s(t+1 (k+1)) 1k20 according to the dynamic system (S!++1) .zz ((+1)) =
T (s) _ 2(*)), where 5! C V is efficiently maintained using queue data structure, avoid- ing accessing the entire graph. We say the process converges when S.K.) for some K₁. After T' outer-loop iterations, the generated sequences of active sets and estimation pairs are
(0)
(S(Ki) 0, z (K1) ()), t=
(
(1) 27
(S (s(Kr) 0, x ((KT) xT))), T.
At each outer-loop t, we denote the time complexity of the local solver M by T:M, which dominates the total cost. The total time complexity T of the nested ESP framework then dominated by
1 K2
T M=M Ke- V.), where vol(S.)
(Sl
(4)
k=
with (S,) representing the average volume of the local process at time t. Fig. illustrates how the number of operations evolves during the updates in APPR [[]] and in our method under this process.
With this nested ESP, accelerated methods can be seamlessly incorporated to improve the efficiency of local PPR computation. Specifically, given the problem configuration 0 = (a, b)), at each outer-iteration we propose the following localized Catalyst-style updates
AESP
x (1) MM(i y (1-1), 1,,,,),,,, a, b,9),
(t)) = ( + (x( x (t-1))
(5)
where the momentum weight B, (o (I ar- ()/ + or)). and a is updated in (0, 1) by solving the equation of (1 ax) af 1 + aña, with an initial ogg (see the Scheme 2.2.9 in [8

---

Fort 2 1, the local operator obtains (1)) E (1(())) defined as
(1) E Hel(Pt) & {z E R" h₂(2) - hi S pr),
(CI)
where by is the minimal value of hrs which is the proximal operator objective at t-th iteration
he(2) - f(z) + "112= - 11-
(6)
Thus, the minimizer x; - arg ung (z) is given by कं = prox, (1(-11) =
(Q
-()--B((-1) with b(t-1) aD bD21//2 (t((t=1), To characterize the time complexity of the AESP framework, it is convenient to define the following constant
(2)))) (= e [TI)
|V
R := -==max
The following lemma is key to controlling the time complexity of the local algorithm M.
Lemma 3.2. Let he be defined in Eq. (G), and suppose that the initial point zi of t-th process satisfies 1 1/2 12, for a stopping condition V/,,, (z(
(1)(2()) * O. If there exists a local algorithm M such that [[ (zt (2(R))))
1/2
)l <
) < of M with
n)pt
2
C - max
where yr: > 00
(8)
m
(0) )12
(Kt) is guaranteed in the ball, i.e., zi (k))) E He((p) as defined in (CII..
the final solution 21
Lemma provides a way to find (x) E HHl(p)) under the condition that M satisfies the monotonic-
/Vn,/(22) )ll The next subsection introduces two operators that satisfy this monotonicity property while maintaining local time complexity.
ity property, | (= )I1 s
3.2 Localized inexact proximal operators
This subsection introduces two localized inexact proximal operators with optimized step sizes, in- cluding local gradient descent (LocGDD and an optimized version of APPR (LoCAPPR), for com- puting z[
(k.) E ().))) Given (0) RR, the first local operator is iteratively defined as
22h (8)
1st
LocGD (k+1)
for A: 2 0,
(9)
+ a + 2n
where means element-wise multiplication. For each u E St. then w-th entry of 1st is otherwise it is 0. The active node set St is determined by the following activation condition St {u : V Vuh, 1/2 (k) 2 ct). The stopping criterion for LocGD when S.K 6. which (z)
is Vh, 1/2 (2) < as stated in Lemma B.21 To analyze the convergence and time complexity of LocGD, characterize the sequences (vol(S}))=2o, and { //h//(22 (z((*) ] generated by & LOCGD. To quantify the ratio of progress, we define the average -nomm of the gradient ratio as
K
1h 1/2 (k)
s000 11
(R)
7t
(10)
Vh
Ih
When Sht V. convergence straightforward observe, yielding 7, and vol(S)) 2m. The quantity vol(S.)/7, meaningful measure of time complexity as vol(S.)/T, S 2m. The following theorem establishes the local convergence rate and time complexity of LocGD.
Theorem 3.3 (Convergence of LocGD). Let h4 be defined in Eq. (G)) LocGD (Algorithm B) used to minimize he(z)) and returns (K.) = LOcGD(pe ((-1)),1, or, b, E He(s))) Recall the
1/2 (k)) 1 1// (1)). For k 2 0, the scaled gradient satisfies D2/2-scaled gradient Vh
(z)
[ 1/2
(2, (2 (k+1) ||; S (1 - T-t (k) |
1/2 (z( (1) [|.
"See implementation details of LocGD (Algorithm B) and LoCAPPR (Algorithm E in Appendix
5

---

Algorithm AESP(s, o, a, M,
Algorithm 2 AESP-PPR o, 8, M,
y(0)
0
0.9 11
1: y =
2: T's computed in Eq. (122
2: T 1 /L log
3: fort 1.2...... do
3: for t = = 1........ T do
4:
(Pr
4: (t: = 4
5:
(x(() = MM
- (111)111111111)"1)) 13, a,
5:
LOCGD
6:
// M in LocAPPR LocGD
6:
x00 = M( (()11) 20, a. b,
7:
if {f(v: :ervd S (. 0 then
7:
if f car S v.f(x(()) = 0 then
8: break
8:
break
9: (0 x1
vutg-vf Vi
(x(() x (1(11))
9: y (1) + Al-avv va (m 11!-1)
Vatntva
VI-a+va
10: Return = x11)
10: Return क D (1)
where T = 2(++)) and (k) is the ratio defined in Eq. (II)) Assume 6, and stop condition are 24
It
defined in Eq. (8) of Lemma then the run time T.ocGGD as defined in Eq. (,), is bounded by
vol(S))
Ch
Cº - -C
T LOGGD S min
log
The
Che
Ki
TC
where C%
(8) Il1 denote constants. Furthermore, vol(S:))7, S min (Ch,/e, 2m).
Since the Hessian of h, is + nI and its eigenvalues X(Q ((Q+n)) E In+ a. 17 + 1]. the condition number of the shifted linear system is (17 (m + a),, which is smaller than 1/a. Hence, the time complexity per round improves from ((1((ac;) to ((1((Te)) In our later analysis, we show that for a < 0.5 and 1 2a, then r = 2/3, meaning that each local process is independent of 1/a.
Following the same analysis LocGD, we introduce an optimized version of APPR with online updates. For u, E S {ui, 42.., ) the optimized APPR updates are
2z (k:)) 1 (14)
(k4+1) (k.) LOCAPPR 2t 2t
(11)
1 + a + 2n
where k; k (i-))SS) for = 1, S. The convergence analysis of LOCAPPR follows similar approach to that of LocGD stated in Theorem A. of the Appendix Al
3.3 Time complexity analysis and AESP-PPR
This subsection presents the overall time complexity of the AESP framework. First, we analyze the number of outer-loop iterations required to achieve f(x((") - f(x7) μe² /2, which guarantees
|I-11/((xe)) x oloo S We derive the iteration complexity of AESP in the following lemma.
Lemma 3.4 (Outer-loop iteration complexity of AESP). If each iteration of AESP, presented in Algorithm MI finds (t)) =((k) using M, satisfying (())) hū S Pt = (L p)]lbl p)²/18, then the total number of iterations T required to ensure & = AESP(E, a, b, b. G.M) e P, 9) as defined in Eq. (E)) for solving (PI). satisfies the bound
P
T T log
1ue(va- - p)2 where p = 0.9 and q 1 ++
(12)
Furthermore, bi has lower bound 2 pE2 p) all te [T].
In a practical implementation, our AESP framework an adaptation of the Catalyst acceleration method applied to local methods, as presented in Algorithm II Specifically, Line 7 serves as an early
stopping condition since represents the worst-case number of iterations required. This stopping condition follows directly from Lemma D i.c., {u eayd, S (z 0, which implies
||V - (z(")))
Line 9 updates the sequence {3:)211 using 3, Vata-ya
VatatVi as
Og = VQ. The computational cost of verifying this condition is dominated by T.M. To minimize T.

---

the goal is to choose a suitable to maximize 1/(T(p n)). When < 0.5, we find that setting r7 (L -24), though not necessarily optimal, is sufficient for our purposes. Based on this analysis, we now present the total time complexity for solving (PI) using AESP in the following theorem.
Theorem 3.5 (Time complexity of AESP). Lei the simple graph G(V,E) be connected and undi- rected, and let f(x) be defined in (PI). Assume the precision >> satisfies {i 1b, 2 <d,} * and damping factor a < 1/2. Applying & = ( a, b, 17. G.M with = L - 2 and M
be either LOCGD or LOCAPPR, then AESP presented in Algorithm W1 finds solution E such that
[| 1/2
la I c with the dominated time complexity TT bounded by
(Si) Ch
Ch.
-
(ol(
Che <t
T min
log
hs. C.K."
with
S min
{
2m
The
TEE
Tt
where T, Et. Ch, and Chty are defined in Theorem Furthermore, q 11(LL p)) and the number of outer iterations satisfies
10
[400(L + + - 1
T S log
9 9
p
Roughly speaking,
Theorem 5.3 indicates that AESP solves Eq. (PII) in a time complexity of
T=ō (vol(s.)) VaT,
- Vaer = (aerr) )
Vace) (v
where the last equality follows from éT O(2)). This result is particularly meaningful when 2 1/ As argued in [[T), in many real-world applications, it is typical that 1/c < n. We now finalize our algorithm and present AESP-PPR for solving Eq. (II in the following theorem.
Theorem 3.6 (Time complexity of AESP-PPR). Let the simple graph G(VE)) be connected and undirected, assuming a 1/2. The PPR vector of V is defined Eq. (II, and the precision E (0, l/d.). Suppose ft = AESP-PPR(E,,, s, be returned by Algorithm D When M is either LocGD (Algorithm B) or LocAPPR (Algorithm B), then te satisfies D ( TT)1 S and AESP-PPR has dominated time complexity bounded by
T S min {
max; Ch
}}-
R /2
Va }
1--minn
(13)
Vaet
Vax
where T arg max vol (S.)/Te and R is defined in Eq. (0I)
The time complexity derived in Eq. (L3) is significant when e 2 1/ymm. Compared ASPR [E7].
which requires| supp(æ*)) iterations of APGD, our approach only needs O(1) /a) local evolving
set processes. contrast to LocCH [522], which imposes a strong assumption on the scaa-cdl gradient reduction, our method provides a provable stopping criterion and only requires mild
assumption on the bounded level set of the D1/2 gradient during AESP-PPR updates.
Initialization of z; (0) We consider three possible initialization strategies for 2, 1) A cold start with (0) = 0; 2) Using the previous estimate z (0) (t-1)); and 3) Momentum based initialization. i.c..
(0) (t-1)) Among these, we find that the momentum based strategy yields the best overall performance. This choice is well-motivated, since V/i//(3y = ((ab - II 2y which corre- sponds to the negative residual of Eq. (II) when treating D p1/2y(t-11 as an estimate. Notably, (t-2) + π as + co, justifying this initialization. Fig. D empirically supports this analysis, showing that requires the fewest lote iterations.
of Operations
Running Times (+)
Figure Convergence of log || AESP-LOCCPPPE with three different initializations for (0) as function of total operations and running times on the com-dbip graph.
π Iloo for
7

---

The assumption on the constant R. limitation of our theoretical analy- sis is that the constant R is not uni- versally bounded across all configu- rations 0 = (a, b, g). In particu- lar, we are unable to express It solely in terms of graph size or input pa- rameters. Nevertheless, empirical re- sults (see Fig. E) consistently show that R remains a small constant and largely insensitive to the graph size and the condition number, suggesting that this limitation has minimal prac- tical impact. To further upper bound R. two possible strategies sidered: The first is to add a simplex constraint == {x ||D|/2 =
10
22
be con-
Figure 3: /h//e,, vol(S.)/Ti and R of AESP-LOCAPPR
on 19 graphs (in ascending order of n) when _0 = (tt
1, R$} to (PII) since
((11) remains bounded, the quantity [/ 1/2
(2. (0) ]|1 can also be
kept bounded. The projection onto A can be solved in O[ s(sup(())))) log n) time [IS]] The second
strategy is to adopt an adaptive restart scheme [T6, gI]] which can ensure that |/ (z( )ll S
(0)
|| (221)(()()))
[z(")]]
throughout the iterations. This may lead R S during adaptive updates.
3.4 Discussions and related problems
Adaptive strategy for estimating e,. Since yrr (E2)) our conservative estimation of e, suggests that L/er ((1/²). Hence, the time complexity in Eq. (T3) remains unsatisfactory when e /m, 1/m]. Naturally, one may ask whether the final bound in our time complexity analysis is optimal. We observed that the bound in Lemma B- provides pessimistic estimation of the objective error. A more careful error estimate can potentially refine this analysis. Specifically, let x; (Ki) be the output of either LocGD or LOCAPPR. Then, by Corollary A.7 we have
(0) II?
K,-1
he (e(2(K)) hmx)))
II k=0
(1 17-27% 13)
(14)
(k) can be computed in vol (a() time per iteration, one can propose an adaptive adjustment for as follows: We progressively try different precision levels
Inspired by Eq. (LE)), and observing that 72
from cl = ((1 a / = /(1 a)y::/?...... to ef = v(1 a)pp/m, and at each time, verify whether Vh, (2) I /2 a a)p, is satisfied. This may potentially reduce the runtime, thereby lowering the time complexity per process.
AESP for the variational form of PPR. Our AESP framework naturally extends to solving where each outer iteration solves the following inexact proximal operator: (:(() as prox*/71 (1 (-")). We can employ ISTA or greedy coordinate descent to design local operators within the AESP frame- work. However, whether these standard methods can be effectively localized remains unclear. A previous study by Fountoulakis al. [20] suggested that the monotonicity of the D D1/2-scales gra- dient of ISTA depends on the non-tegatyy of the initial 2 which it may not be true during the updates. It remains an open question whether one can achieve a time complexity of Ö (eQa()(())) without imposing strict -egaativvt constraints.
Application to other related problems. Our results or framework can also be applied to other related problems. For example, in the thesis of Lofgren [35] (Section 3.3, Corollary 1), the author proposed bidirectional PPR algorithm for undirected graphs with a relative error guarantee. If our techniques can be incorporated, then their expected runtime could potentially improve from
O (Vm/(ar)) (aE))
improves
① (Vm/ (Vmm(Voe)) (Vac)).
Additionally, our approach could benefit other problems of single-source PPR estimation, as high- lighted in a recent survey by Yang et al. [50], which shows that many PPR-related computation methods have time complexity proportional to 1/a.
8

---

ogb-mag240m
ogbn-papers100M
com-frieedstee
wiki-en21
APSP- DeA
AESP-LacID
-12
APMR
LecGD
-32
-11
-14
0.
035
3.0
1.5
2.0
00
0.5
# of Operations
X10
of Operations
<10F
of Operations X10
Operations
<10
Figure 4: Performance of estimation error reduction, log D D x Il as a function of op- erations T, on the graph ogb-mag240m, ogbn-papers (00M, com-friendster and wiki-en21 with 0.01 and 10-6 where the graph can scale up to 244M and 1.728B.
4 Experiments
We conduct experiments on computing PPR for a single source node. We evaluate local methods on real-world graphs to address the following two questions: 1) Does AESP accelerate standard local methods? 2) How do our proposed approaches compare in efficiency with existing local acceleration methods? Additional experimental results are provided in the Appendix I Our code is publicly available /uttp:://githue https///gthhbb.oo//kk/////
AESP achieves early-stage acceleration and overall efficiency. We begin by conducting experi- ments on four scage-ccal real-world graphs, with the number of nodes ranging from 6 million to 240 million. We implement two AESP-PPR variants: AESP-LoCGD (where M LocGD) and AESP-LOCAPPE (where M LOCAPPRR. For comparison, we consider three baselines: 1) APPR []]. 2) APPR-opt (APPR with the optimal step size 2/(1 + a)), and 3) LOcGD (with the optimal step size 2/(1 + ot). Fig. gl presents our experimental results on four real-world graphs. Among all methods, AESP-LOCAPPR is the most efficient due to its online per-coordinate updates. Interest- ingly, by solving shifted linear systems, AESP-based methods achieve much faster convergence in the early stages than the baselines.
AESP accelerates standard local methods when a is small. We further validate whether AESP ef- fectively accelerates standard lo- cal methods such as LocGD and APPR. We fix the precision at 10 and vary from 10-3 to 10-1 selecting 50 source nodes for each at random. Com- pared to non-accelerated methods, both AESP-LoCGD and AESP- LocAPPR significantly reduce the
Running Time (s)
# of Operations (2 volls, 1)
APPR AESP-LocAPPR LocGD AESP-LocGD
Specdup
5.0
2.5
01003
10.0
01:15
0.00
11.05
0.10
11:13
0.42
11.04
02.00
0.06
0.101
Figure 5: Speedup of AESP-based methods over standard lo- cal solvers (LoCAPPR, LocGD) as a function of a, on the com-dbip graph with = 0.1/n and a E 110-3,10-1 number of operations and running times required, particularly when is small.
5 Conclusions and Discussions
In this paper, we propose the Accelerated Evolving Set Process (AESP) framework, which lever- ages an accelcrated incxact proximal operator approach to improve the efficiency of Personalized PageRank (PPR) computation. Our methods provably run in O aa) iterations, each performing a short evolving set process. We establish a time complexity of Ö (vvol (oo((S))((Va))))) and under a mild assumption on the bounded ratio of E en-noen-sealed gradients, we show that (vvo(S).)/r) is upper-bounded by min (R(R/22), m). This result demonstrates that our approach is sublinear in time when c > 1 /mm significantly improving over standard methods. Our algorithms not only advance local PPR computation but also offer purproe- framework that may benefit wide range of problems, including positive definite linear systems and related tasks in graph analysis.
Despite these advantages, when < 1/Vm, the local bounds degrade to Ö(m/ /or. A limitation of our theoretical analysis is that the constant R is not universally bounded across all configurations

---

0 = (a, G). A key open question remains whether the 1/c² dependence in our complexity bound can be further reduced to match the conjectured ((c((v)c) from existing literature [[9]] and whether the dependence on the constant It can be entirely eliminated.
Acknowledgments and Disclosure of Funding
The authors would like to thank the anonymous reviewers for their helpful comments. Luo is sup- ported by the Major Key Project of Pengcheng Laboratory (No. PCL2024A06), National Natural Science Foundation of China (No. 12571557), National Natural Science Foundation of China (No. 62206058), and Shanghai Basic Research Program (23JC1401000). The work of Baojian Zhou is sponsored by the National Natural Science Foundation China (No. KRH2305047). The work of Deqing Yang is supported by the Chinese NSF Major Research Plan 1N..9227012),, General Pro- gram (No.62522199) The computations in this research were performed using the CFFF platform of Fudan University.
References
[1] Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. Journal of Machine Learning Research, 18(221):1-51, 2018.
[2] Zeyuan Allen-Zhu and Lorenzo Orecchia. Linear coupling: An ultimate unification of gradient and mirror descent. arXiv preprint arXiv: 1407. 1537, 2014.
[3] Noga Alon, Ronitt Rubinfeld, Shai Vardi, and Ning Xie. Space-efficient local computation algorithms. In Proceedings of the twenty-third annual ACM-STAM symposium Discrete Algorithms (SODA), pages 1132-1139. SIAM, 2012.
[4] Reid Andersen, Fan Chung, and Kevin Lang. Local graph partitioning using PageRank vectors. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006.
[5] Reid Andersen, Fan Chung, and Kevin Lang. Using pagerank to locally partition graph. Internet Mathematics, 4(1):35 64, 2007.
[6] Anton Anikin, Alexander Gasnikov, Alexander Gornov, Dmitry Kamzolov, Yury Maximov, and Yurii Nesterov. Efficient numerical methods to solve sparse linear equations with applica- tion PageRank. Optimization Methods and Software, pages 1-29, 2020.
[7] Jiahe Bai, Baojian Zhou, Deqing Yang, and Yanghua Xiao. Faster local solvers for graph dif- fusion equations. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024.
[8] Amir Beck and Marc Teboulle. A fast iterative shrinkage-ttheshoolding algorithm for linear inverse problems. SIAM J. Imaging Sci., 2:183-202, 2009.
[9] Pavel Berkhin. Bookmark-coloring algorithm for personalized pagerank computing. Internet Mathematics, 3(1):41-62, 2006.
[10] Aleksandar Bojchevski, Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberezki, Michal Lukasik, and Stephan Günnemann. Scaling graph neural net- works with approximate pagerank. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining (KDD), 2020.
[11] Marco Bressan, Enoch Peserico, and Luca Pretto. Sublinear algorithms for local graph- centrality estimation. SIAM Journal on Computing, 52(4):968-0088, 2023.
[12] Sergey Brin and Lawrence Page. The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems, 30(1-7): 1998.
[13] Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and T in Machine Learning, 803-4):33-335,,200
10

---

[14] Li Chen, Richard Peng, and Di Wang. 2-norm flow diffusion in wear-linear time. In 202/ IEEE 62nd Anmual Symposium on Foundations of Computer Science (FOCS), pages 540-549. IEEE, 2022.
[15] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized PageRank graph neural network. In International Conference on Learning Representations, 2021.
[16] Alexandre d' Aspremont, Damien Scieur, Adrien Taylor, et al. Acceleration methods. Founda- lions and Trends@ in Optimization, 5(1-2):1-245, 2021.
[17] Etienne De Klerk, François Glineur, and Adrien В Taylor. On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions. Oprimization Letters, 11:1 185-1199, 2017.
[18] John Duchi, Shai Shalev-Shwartz, Yoram Singer, and Tushar Chandra. Efficient projections onto the 1-ball for learning in high dimensions. Proceedings of the 25th international conference on Machine learning, pages 279,279, 2008
[19] Kimon Fountoulakis and Shenghao Yang. Open problem: Running time complexity of accel- erated eerruularree PageRank. In Conference on Learning Theory (COLTT, 2022.
[20] Kimon Fountoulakis, Farbod Roosta-Khorasani, Julian Shun, Xiang Cheng, and Michael W Mahoney. Variational perspective on local graph clustering. Mathematical Programming (MP), 174(1):553-573, 2019.
[21] Kimon Fountoulakis, Di Wang, and Shenghao Yang. p-norm flow diffusion for local graph clustering. In /CML, 2020.
[22] Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. In Advances in neural information processing systems (NeurIPS), 2019.
[23] David F Gleich. PageRank beyond the web. siam REVIEW, 57())3221-36, 2015.
[24] Gene H Golub and Charles F Van Loan. Matrix computations (4th Edition). JHU press, 2013.
[25] Taher H Haveliwala. Topic-sensitive pagerank. In Proceedings of the 11th international con- ference on World Wide Web, pages 517-526, 2002.
[26] Rajesh Jayaram, Jakub cki, Slobodan Mitrovi, Krzysztof Onak, and Piotr Sankowski. Dynamic pagerank: Algorithms and lower bounds. arXiv preprint 24X::2404.16267, 2024.
[27] Glen Jeh and Jennifer Widom. Scaling personalized web search. In Proceedings of the 12th international conference on World Wide Weh, pages 271-279, 2003.
[28] Michael Kapralov, Silvio Lattanzi, Navid Nouri, and Jakab Tardos. Efficient and local parallel random walks. Advances in Neural Information Processing Systems, 34:21375-21387, 2021.
[29] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnneaann. Predict then propagate: Graph neural networks meet personalized Pagerank. In International Conference on Learning Representations (ICLR), 2019.
[30] Kyle Kloster and David F Gleich. A nearly-sublineat method for approximating column of the matrix exponential for matrices from large, sparse networks. In Algorithms and Models for the Web Graph: 10th International Workshop. WAW 2013, Cambridge, MA, USA, December 14-15, 2013, Proceedings 10, pages 68-79. Springer, 2013.
[31] Ioannis Koutis, Gary L Miller, and Richard Peng. A nearly-m log time solver for sdd linear systems. In 2071 IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 590-598. IEEE, 2011.
[32] Dennis Leventhal and Adrian S Lewis. Randomized methods for linear constraints: conver- gence rates and conditioning. Mathematics of Operations Research, 35(3):641-66 -654, 2010.
11

---

[33] Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. A universal catalyst for first-order opti- mization, Advances in neural information processing systems, 28, 2015.
[34] Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. Catalyst acceleration for first-order convex optimization: from theory to practice. Journal of Machine Learning Research (JMLR), 18 (212):1-54, 2018.
[35] Peter Lofgren. Efficient algorithms for personalized pagerank. Stanford University, 2015.
[36] Peter Macgregor and He Sun. Local algorithms for finding densely connected clusters, In International Conference on Machine Learning. pages 7268-7278. PMLR, 2021.
[37] David Martínez-Ruuee Rubio, Elias Wirth, and Sebastian Pokutta. Accelerated and sparse algorithms for approximate personalized PageRank and beyond. In Proceedings of Thirty Sixth Confer- ence on Learning Theory (COLT), volume 195 of Proceedings of Machine Learning Research, pages 2276. PMLR, 2023.
[38] Ben Morris and Yuval Peres. Evolving sets and mixing. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing (STOC), page 279286, New York, NY, USA, 2003. Association for Computing Machinery.
[39] Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
[40] Julie Nutini, Mark Schmidt, Issam Laradji, Michael Friedlander, and Hoyt Koepke. Coordinate descent converges faster with the gauss-southwell rule than random selection. In ICMI, pages 1632-1641, PMIR, 2015.
[41] Brendan Odonoghue and Emmanuel Candes. Adaptive restart for accelerated gradient schemes. Foundations of computational mathematics, 15:715-732, 2015.
[42] Ronitt Rubinfeld and Asaf Shapira. Sublinear time algorithms. SIAM Journal on Discrete Mathematics, 1564):156- 2011.
[43] Yousef Saad. Iterative methods for sparse linear linear systems. SIAM, 2003.
[44] Daniel A Spielman and Shang-Hua Teng. A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM Journal on Computing. 42(1): 1-26, 2013.
[45] Daniel A Spielman and Shang- Hua Teng. Nearly linear time algorithms for preconditioning and solving symmetrie, diagonally dominant linear systems. SIAM Journal on Matrix Analysis and Applications, 35(3):835-888 885, 2014.
[46] Paul Tseng and Sangwoon Yun. A coordinate gradient descent method for nonsmooth separa- ble minimization. Mathematical Programming, 117:387-425, 2009.
[47] Stephen Tu, Shivaram Venkataraman, Ashia Wilson, Alex Gittens, Michael Jordan, and Benjamin Recht. Breaking locality accelerates block gauss-seidel. In ICML, pages 3482-3491. PMLR, 2017.
[48] André Uschmajew and Bart Vandereycken. A note on the optimal convergence rate of descent methods with fixed step sizes for smooth strongly convex funetions. Journal of Optimization Theory and Applications, 194(1):364-373 2022.
[49] Hanzhi Wang, Zhewei Wei, Ji-Rong Wen, and Mingji Yang. Revisiting local computation of PageRank: Simple and optimal. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 911 912-92 2024.
[50] Mingji Yang, Hanzhi Wang, Zhewei Wei, Sibo Wang, and Ji-Rong Wen. Efficient algorithms for personalized PageRank computation: A survey, IEEE Transactions on Knowledge and Data Engineering, 2024.
[51] David M Young. Iterative solution of large linear systems. Elsevier, 2014.
[52] Baojian Zhou, Yifan Sun, Reza Babanezhad Harikandeh, Xingzhi Guo, Deqing Yang, and Yanghua Xiao. Iterative methods via locally evolving set process. The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024.
12

---

A Missing Proofs
In this section, we first summarize all notations in Table M for clarity, followed by the presentation of all missing proofs.
Table 1: Notations
Description
8(V,8) a
undirected and connected simple graph with n = [V] nodes and m = |E| edges.
The damping factor a which lies in the interval (0, 1).
A
The adjacency matrix of g.
D
The diagonal degree matrix of G.
II,
The PPR matrix defined as II, = a L+a
1-a AD-1)
2
Q
The symmetric matrix Q 1 I 1-e
D AD 1/2
The shifted matrix of Q. ie.. Q Q nI.
supp(a*)
The set of nonzero indices of æ E Re, i.e., supp(a)) = {v: x. # 0}. The volume of S C V is the sum of all degrees in S, that is, vol(S) Eves dy.
vol(S)
St s(k+1)
The set of active nodes at outer-loop iteration and inner-loop iteration k:
K,
The maximum number of iterations the inner loop at outer-loop iteration t.
vol(S.)
The average volume of I-th local process: vol(S.) - Tे. Ex- vol(S)"))
(R)
Active ratio at outer-iteration and inner-loop iteration & defined in Eq. (IT))
Te
Average active ratio of I-th local process defined in Eq. (II)).
ex
The standard basis vector e, where the s-th element and other elements are The PPR vector π IT.
The e-approximate PPR vector s.t. |D- T))6 Sc A sparse vector in Eq. (PI).
b
b(9)
(+)) aD 11/2b (*).
r
Residual of c-approximate PPV satisfying C, I1, pp.
(z)
D 1/2 scaled gradient of f at æ, (z) = -
112
D 1/2 scaled gradient of f æ, vf-1/2(x) D 1 f())
Quadratic function defined in Eq. (PI).
he
Proximal operator objective f-th iteration defined in Eq. (8)
L
Two constants with || y < f'v) - f(x) (V (x)) x) < 1
y113
Smoothing parameter for Eq. (2).
pl(p 7))
g
P
P 0.9.7
PP
Inner-loop stop criteria (.) - h S yt-
Inner-loop stop criteria of D 1-111/21000 1D-1//Vh(22)11 I 4.-
proxg/n(3)
The proximal point of y, i.e., prox g/n arg min {g(x)) + 311 y113)
Cj
C₁ D (z, []1
T.M
Time complexity of M, which is characterized by TM K, vol(S)).
Total time complexity.
A.1 Proofs of Lemmas 2. and 2.2
Lemma 2 (Properties of πT. Define the PPR matrix II, = ( - 1-a AD-1) AD-1)- Let the estimate-residude pair (p, r) for Eq. (Il) satisfy r = e, - II-1 Then,
The PPR vector is given by π Is which is a probability distribution, i.e., E V, m; >
and ||T||] 1. For e 0, the stop condition ||-'rll ensures DDD-1(p πτ) l
13

---

The matrix aQ is similar to the matrix HI ie., aDI/2Q" DD'2Q-1D'' --ror of II satisfies || 11
1/2 II. Furthermore, the
Proof. The PPR vector is probability distribution and is given by = e, which follows directly from the definition Eq. (I.) To verify the stopping condition, note that the residual satisfies Irr = π that is,
DT p). D D''
To meet the stop condition
(p- -T) S E, we note
| |D- pop-np +2) D
II D
D rloo
D- 1D'I11, D1,o |DD*rllo
= =rl S,
where the second inequality is due to D note that
11, x
To verify the second item,
I 1D-'II,
D1,
= a 2
1
a D
2
(1100
|1+0
1-
A ))
a
= III = 1.
2
Lemma 2 (Properties 2ÿ and x.). Denote the gradient of f at a as Vf(x) = Qx- QD 1/2b
and optimal solution 2; aQ D -1/2b satisfying DD x7 Define p 1//2z. Then,
The stop condition
D 1/2 f(x)ll < ar implies D D- (p- T) l) <e
The objective u-strrongyy convex and L-smooth with two constants μ a and L When غ = c, then F E P(c, a. C..9) 9) and the solution is sparse, i.e., supp(2 - 1/2.
Proof. For item 1, note 2 aQ D D-1/2b D D D 1/2e, D 1/2 Hence,
= 11,22 With Vf(x) Qx oD -1/2b, we have
| (p π co
D 1D2 (a x))|
D VD-))((
D D (())
D II DD 1/2)/(>))l>>>
D II 1D11/2
a
D 1/2 V <.
a
For item 2, the Hessian of f is H, Q and the eigenvalues of X(AD-1) satisfy X(AD-1)
(-1,1), so ((Q) E 1). When = c, then xx E P(c, o, G,.9), which follows from the result of Fountoulakis et al. [20]]
The following lemma provides useful results that will be useful in our later proofs.
Lemma A.1 (Gradient Descent for (μ, L)-oonvex IT 48 Let f be p-strongly convex and L- smooth. Consider the gradient descent update
2
x (t+1) (1)
(((((!))
11 L
Then, the following properties hold

---

Bounds on initial function error. [1 - x0112 S f(x!0)) - f(x²)==+=))))))))<))) - 1 |z x21
Gradient norm bounds on initial gradient.
1 VI(00 - (axl1)) - - V)((x(1)) V5(x")) 11
1
21.
2/1
Per-iteration reduction in function enror, f(x!t+1)) f- 1 1+71))
(f(x(1)) - fr)
Per-iteration reduction in estimation error, ||x - x011 112 S
1-
||x(1)
x2 -000--
L+#
A.2
The proof of Lemma 4
(0) Lemma 32 Let be defined in Eq. (6), and suppose that the initial point zi of 1-th process satisfies Vhe(zi) (0) # O. If there exists a local algorithum M such that V
1/2 (z) (x(k)))] <
|/V1122 1/2 (0)
(2) (z) )12, then for a stopping condition [|V,, 1/2 (=!
Ol < t M M with
+ mipt
2(1 + a) 11
- max
where yr > 0,
m
(K+) is guaranteed in the ball, i.e., zt (Kt) E Hel(P) defined in
the final solution 2t
Proof. The proximal objective he defined in Eq. (8) at t-th iteration can be expanded as
1 =z he(2)= =
1 a 21
1-a D D-1/2 1/2 z-zT (DD 1/2b + my
(t (-11))++
" 11 (t-111112
2² =
2
2
(15)
Let Q I+a+22
I
1-a D
1/2 AD 1/2 and (t-1) =aD 11/bb + ny my
then
= -
Q 1 2n
a
1/2 A/ 1/2 (((-1) aD 1/2b my (t-1),
2
2
(16)
We know the optimal solution x;
Q-106(1- Note that the objective error can be rewritten
h,(2) hr(x;))
1 T
TQ==
Q= - Tb(-11) -
t Qx; -x; b((
2
1
Q== = (t-1
ii T
Qai oi Qui
=
2
1
1
Q== z T (t-1)
#
+
2
2
Q==
1
Qx;
T
Q + 2 zi Qx;
2 x
zi
2
(z
x1) TQ(= zi).
Since 2
(Ki)
Q (V (Ki)), we show hz(2 (K()) h can be rewritten in terms of
(ki)) Vho(zi
(x(2(K)) he(zz)
2 (z)
(Ki)
x;)) x;)T (((((()))) =x()
2 (he (K)) Q QQQ (he(z((
Vhilzi (Ki)
T (Q (2
2
V2 (Ki)) T -
1/2
1 (1 (Ki))
2(1 + a
1+9
15

---

D 1/2 (2, (Ki)) (2(
II
D 1/22 1//2///
(2 (2( (k)))
2(n+
1+7
where the fourth equality is due to the identity D 0-1/211 inequality, we have
D1/2
(1 + aqQ
By Hölder's
145
hz(2 (())) 11(1;))
1
D D-1/2 (1))))
11/2 V/ (ki)))
-
2(n + a)
1+9
1
| 1D-1/2<h: (K+))
||ا00 11 (k:)))12
$ 2(n + a)
1D-1/2Vh, (K.) )| 11
|D (0) ) S Pr:
2(1+ +
where the last inequality gives the second part of q. On the other hand, we know
hz(zt (1)) - h)((a))) - 2(1 + a)
1/2 (/ (K)))) " (k)) (ko) |l1
D 1/1 (h. (1))))))) |1 |DD 1/2 Vhe (k:))]1 1/1
2(1 a)
volssupp(Vh((*) (K.()) 1-12 (2)
$ 2(1 + aa)
m
D 1/22
(k:) )133 S sm
which gives the first part of e,.
Remark A.2. Choosing a starting point z straightforward. For example, if z[" 0. then
(h((2,)) (0)) = (t-1)), Consequently, the following stopping condition is sufficient:
(H))) S = max
{
/ [n n)p.
+ 1o7+a)pp
|D1/2b(-D
m
A.3
Proofs of Theorems 3x and A
At each iteration & of the AESP framework in Algorithm we solve the inexact proximal opera- (f) ze p (t-1), as defined in (2), where f is given in (PI).. The following theorem establishes the convergence properties of LocGD.
Theorem 33 (Convergence of LocGD). Let h4 be defined in Eq. (B). LocGD (Algorithm B) is used minimize h4 (z) and returns 2;
(K.) LOcGD(pp ((1-1), ,7, ar, b, He(sp)). Recall the (z( (10)) For k 2 0, the scaled gradient satisfies Vh 1/2 (z ( < (1-TY: (K)
Di/2-scaled gradient Vh.
1/2 (=( (2))))
where T = 2))+t) 14
and Ti is the ratio defined in Eq. (III) Assume and stop condition are defined in Eq. ( of Lemma then the run time T.L.GDD as defined Eq. (H), is bounded by
vol(S.) CO
Ch
T LOOGD <
min
log
ThE
C
T6t
where CH,, |1 (2 1| denote constants. Furthermore, vol(S:)/7, S min (CR, /ct, 2m
Proof. Recall that hy (z) is defined in Eq. (L)) Minimizing (z(2) is equivalent to solving the linear system Q= = (t--)), as defined in Eq. (16). Using the iteration local gradient descent in Eq. (E), and noting that (x) is (u -tssnnly convex and (L + 17) smoothh the optimal step size is given
16

---

by 2/( L + 2n), as established in Lemma The updated gradient at iteration (t + 1) is then computed as follows.
Vhi(zt (k+1))
Qz( (k+1) (1-1)
= 2t
(K)
2
Vhe
(1))
o (1)(1)) b((-1)
1 a a 22
-h1((2( (k)
2
(2) (2( s
1 21
For simplicity, recall that we denote the normalized gradient Vh. (z{ we continue to have
(1))) then
1/2 (2) |/| = vn! (1 V 1
1-a a
AD-1
V/1 1/2
(2(1) (z)(a)
1 1+a+2 21)
|4 - (2()))
s(e) [oll1 +
1 1-a a
AD 1 (2) 5/00
1 + 21
$ |Vn1/222 (x) 111 | 1/2 (2
(k)
1
5
11 +
1 + a + 2n
1-a a
|4 (2, (+) a 1ا
|V (1) |11 1+ a + 2ny
2a + 2m
(k) (2
1/2
1
(17)
Therefore, associated with the gradient reduction ratio defined Eq. (IIO), we obtain
| 1/2 (z) (z(x+t)))1
||| S (1-
2(a + 7) I a + 2nj 7t
(k)
For any K 2 1, the above per-iteration reduction gives us
|DD (K) 11 < II k=
K-1
(1
(1 :) (1))
2 2( + 7)
1/2 1/2
Vhe (z)
1 2n)
Specifically, let K, be the total number of iterations of LocGD called from Local-Catalyst at I-th 1 iteration using the precision e.. Denote that 5: Ki K, the following
we can obtain upper bound of =k=0 i
(k)
1/// (k)
Ih D1/22//((z Ib
K.-1
2(a + 11)
K,
1+a 21 't 2(a + 11 (k)
log
< log 1 1+a++ 27 ?
(b)
k=0
The above inequality implies K, < complexity as
1+ log 2(a+
(1' (2) (1 (K0)))
Therefore, we have the time
K
(1 a + (S))
|DI/ (2
(ol( = K₁ - vol(S,) <
log
2(a + T)
D /// (ke) 111
On the other hand, from inequality of inequality (17)), we know that
1 + + 2n - - sk)(s
2a + 2n
<
2a + 2n
||
1/2
(z)
(k)
ادب ||: 1/2 (z (++1) )|1
1 + 21
1/2 (zt (1)
|
The total runtime can also be bounded as
TLOcGD
K
vo!ls 5
1 + 2m
KL-1
Σ
/2 (+))
2( + +1)
1 1 a + 20
(I 1/2 (2(0)) (0))
/h 122 (())))))))
2(a + n)):
17

---

Combining the two bounds above, we establish the first part of the theorem. To verify that the ratio (0) 1/2 (2)
serves a lower bound for Vh/' Et teydun da.. This further leads to
(()) /ll//e,, note that for any u, E we have Vhe(zz (8)
)u, >
(s(t)
| Vdu, Vn. 1e(2( = 7x (hr (1
ct voll = ct
duy
Since |D//2 (he (0) )|1 2 D 1
Vhe
111 ... |D (Ki))
|| this leads to
1 K1-1
K
K
vol(s )
1
D /1/2/ (1) -
Σ
(k)
D 1 (he (z)
Et
Kt
K
K
km0 0
vS.)
11//
(0)) ||
7t
E2
On the other hand, S.) <
2m. To see this, by Eq. (II). note for each iteration k.
spelli
(b)
7t
(8) )l1
(kk) For E St we have /aale" which means
/2////2(2/
1/2 (zt
(2))) 2 eddy and for E V) we have / (=(x))] 2 edd
V Vnn (2 (x))
V (2((2(((1())
2 6
du
dp
| /2 (z (K)
1 112
|V 1/22/212 (z(
(8)) siisiilll
2a
vol(S (K)
vol(V) vol(s,
Given a, b, c, and S. we have o
ate Then, b4d
(A))
sf 111
|7 1/2 (=(
(k) 1 s(s 111 + V/, 1/2 (z,
kk)
vol(V' vol(S ))) + vol
|V
(8) Ib |V, //2 (=(")( (=())))
vol(V)
2m
vol(S.)
< 2m.
7,
Hence, we prove two upper bounds of vol(S.)
The following theorem establishes the convergence and time complexity of LOCAPPR. We first define a similar active node ratio for LocAPPR as the following
(s())
(Ka)) 1
(kc)
7e
(18)
Kr
1/2 (z)
(kx)))1
where k; = k + (i 1) (k) for i = 1,2,...,,1$?? (s
Theorem A.3 (The convergence and time complexity of LocAPPR). Let he be defined in Eq. (.) The LocAPPR algorithum, implemented as in Algorithm A is used to minimize hu(z). Recall the
Di/2-scaled scaled gradient Vh, 1/2 (z(x)) D1/2 (*)) For k 2 0, the scaled gradient satisfies the
following reduction property:
(s(
V ( 5 1
Σ
(Ki)
18

---

where the constant : 2(++)))
(kc) is the active node ratio defined in Eg. (I8). Assume the 1+ and 7t
precision e, and stop condition is defined in (9) of Lemma 3.D. then the returned satisfies
(Ki) LOCAPPR (ft. 11, y (1-1) a, b, 9) E Helsee)-
2t
The time complexity T, LCCPPRR as defined Eq. (ER), is bounded by
TLOCAPPR <
mmn
vol(St) log
he. hbs
-h - -Ch
he
TEL
1/11//22 following upper bound
where Ch
(1) -1Vhi// (z)
Il1 denote constants at iteration Furthermore, vol(S,)/7, has the
vol(S.)
Che
S min
2m
Yt
4
Proof. Recall that u, E S. fu...... U.s. and K2 + (i- 1)/15/ for i 1,2....
... 1/5
The LOCSOR algorithm Algorithm updates as follows: zi 1 Hu.// (11 + + 27). Then, the gradient is updated as
(k+11)
=(hi) 2V 2 (ke2)
2 (z) (k:))
(he(2 (((1)) Q=((.-1) b(t-1)
= Q
(k:)
1wst b(1-1)
z
1 a + 2m
2Q 2Q (Rs)) 1 (ma)
= -Vh((z(
1 a + 21
Then, for all i 1,2,....
| following similar steps as in the proof of Theorem S we have V h 1/2 ( ||
vh 1/2 (z) (=(( (1
1
AD-1
7hy
1/2
(z)
(k))
1 fu.)
+ a + 21
1|/ (zt (1:i))
Vhe
1/2 (2. (k:))
1 11 +
1 1-a
AD V 1/2 (=(())) (h)) a {
1 a 2n
|V (ba)
1u
1-a a
V (=((1t) 14,
1+a+ a 2m
|h (2) (k)) |[1
2a 27
(z,
(k())
o (m:) 1l1.
(19)
+ 21
Recall the definition of gradient reduction ratio for active nodes is in IN Summing over the above equations over u, we have
(14 (()n))) vnk 1/22 (=
S 11 (2( (k:)))]
2x + 21
|/ 1/2 (2(11)) (0s) 11
1 21
-1- 2(a + 1777 (ks)
|V/1 (2(
(k:) (
1 2m
For any & 2 1, the above per-iteration reduction gives us
[s((k)
Ki
(1- 2(a + 7)) (kx) 1 + 2n
|| 1/2 (2 (Ki) |1
II
II
11 (2( Il1.
k=0
1=1
Denote that 7r = K.
k. (1
(ki)
we can obtain an upper bound of K, as the following
log
Vh 1/2 (Ki)
(2,
Ki - (s(
Σ
log (1
2(a + 17)
(ke)
5
Kr K- 1s
2(a + n) (K)
V
1/2 (0)
(z)
|||
1 + + 21
1 a 21j
Om=
1=1
k=
19

---

The above inequality implies K, v complexity as
1n log 2(++1)
IV 11 14 1
Therefore, we have the time 111
K
(1+ a + 2n) (o)
| 1 (z) (0) 111
vol(s - K₁ vol(S)) S
log
2((x + 7)7
|/ (2) (21
1/2
(k.))
To check the ratio is a upper bound of [V/ )11 note that Vha(z( (k)) Jas > Ex v duy for U, E S(A).
(S
|
4 vol(s((t) =
d
du V Va, ho(z)))) = -|
//2//26 (x,
1=1
Since | ||1 2 |
(Ki) 2 ... |in 1/2 (=( ( || this leads to
K (
K
K
vo)(s!+))
(kx) | 1/2 (2, ||| -
(k)) V
1/2 (2. ||,
K₁
K
K
k=
where the above implies that argument as in Theorem B.3. Moreover, from the inequality in (IZ), we obtain that
vo)(S.)
I /
The other upper bound follows a similar
T.
|
2a + 2n
4 vol(S(()) 5
2xx + 21j
Σ
| 1/2 (H)) (mm))ll
1 + a + 2n
21j
Vh.
|11 (2
(1()
|4 (z( (1
(2)
The total runtime can also be bounded as
K.
K -1
TLOCAPPR
vol(S
(1))
1 211
(1V/) (=( (1) >|1 - 11 (=( )1
2( + 7762
K=U
k=0
1+ a+a+22 21j
(z. (0) ||| - |/
1/2 (z. (K.) |||
2(a + r))c2
Combining the two bounds above, we prove the theorem.
A.4 Proof of Lemma T-
Before we prove Lemma 5 we introduce the following two lemmas from Lin et al. [34]] are pre-
sented for completeness. Lemma A. characterizes the error accumulation of {see J2o in Catalyst. For completeness, we include the full proof following the argument of Lin et al. [34]].
Lemma A.4 (Inequality of non-negative sequences). Consider a increasing sequence {Si)e20 and two non-negative sequences (arhe20 and (ur) he20 such that for all t, uf I S. + Etm a,u, Then,
S + a,u; S
VSS
a2
Lemma A.5 (Convergence of Catalyst, Theorem 3 in Lin et al. [3).). Consider the sequences (x(())) and (y 1:20 produced by Algorithm for solving (II), assuming that ae()) H (Ft) defined in (CI) for all I 2 1, Then,
Va- (1)- ao) (f (z)10) ft) + 70 || 1000 +3 2
-(=1))-f* Ar-1
Pj
A;-1
(20)
where 0g /4. 70 (1++1))00 (a0 - 9) and A, ITi=1 (1 - -ay) with Ao and q = p/(ut))
20

---

Proof. Let us define the function h₂(2)) = fxx) + |1 1 We show there exists an approximate sufficient descent condition for h4. Since the solution of the proximal operator defined in (c) is ((y(t-1) the unique minimizer of h, i... ()y = prox,, /n (yt/://y(ttt)) (1)t- The strong convexity of he yields: for any t 2 1, for all x E R and any 0₂ 0.
HH | (1)
hx()))
h
2
h + pl (1 (1))
1|20 2z(1)
7 7+ p
(1 1/0.) ||x0() p(y 12
2 hx(( =pt + 11 + p (1 0₂) ||2 10='='')3 101 + カ (1 - 1 /0)) ||x! - ppyy (1y"
2
2
where @ uses the (11 + -ttong convexity of hr For @ note for all x. y, E R. and 0 > 0.
| y 2 (1 - 0) - 212 (100 ||
11=
To see this, || y112 || z y112 x = =12 + || -yll +2( 2, v)
2(x z, 2- y) Iv0(x 2) + (z y) / 0||2 -----
-=11 =112 || 1==-y1/// 01/2/0
z - 01|x =11 ||= - y112/0.
The uses h4 (z) - hg S pt. Moreover, when 6₂ 2 1, the last term is positive and we have
he(x) 2 (z)) (1) - 5p +
17 + 1 (1 0e) || x0
2
If instead 0, < 1. the coefficient 02 -1 2 0 and we have
7 1 (1/0, - 1) (zx - ((("1-1))1 2 - -(1/0, - 1) (1)((x(0)) - -hi) 2 - -1100, gr
2
In this case, we have
he(x) h4 (z(()
+
11 + 1 (1 -0:) |2 - (1)
θ,
2
As result, we have for all values of 02= > 0,
h hx( (z)
1)
(1 1 0.) ||r x (0)
&tt
2
min {1, 0,}
After expanding the expression of ht, we then obtain the approximate descent condition. f(x
())(t))) + 2 || -
1 11
1 + # (1 0.) - x " < f(x)
~/ 1| 12 min (1,0,)
(21)
2
2
Let us introduce sequence (St).20 that will act as Lyapunov function, with
S. = -1=0)) at) (J(xl1)) - l*) a The
|0-
2
where x² is a minimizer of f, (x((t) 1020 is a sequence defined by 2(()) = (0) and
v (1) = x (t)
az-1 ( (z)
x ((-1)) for t 21
04-1
and (Te)e2o is an auxiliary quantity defined by Ti 9 The way we introduce these variables allows us to write the following relationship,
y (
(t) + (1 Te) (t), for all t 1 0,
which follows from simple calculation. Then by setting 21)) = -1=11x" + (1 - at-1) (111-) the following relations hold for all 2 1 by u-strongly convexity of ʃ.
(()( S aa-1f 1 + (1 a1-1) f(x((-1))- pma (1 04 1)
x (1-1) 112
2
20) - (()) = -0= - (1))
21

---

and also the following one (by expanding out 2(1) = 11-10" + (1 - aa- -(-1)=((1-1)
||x(0) - y 1) 1/= = 11(a--1 Tx-1)(x² - 11) + T 1--1=== - r((-1))]1 )|
= aa- - -T-1/ - -x(l11) + T-1 fx" - -(((_
a-1l
1 1 - Te-1/at-1)l1 x 2(1-1) [/ + az
T--1 | - v((t_1) 1
a1-1
- (at-1 T--1) ||00 x: 1| + 1- ||="
1(
where we used the convexity of the norm and the fact that Ti S ac. Using the previous relations in Eq. (2I) with x= =110= 1 + (1 ar-1) 1t, gives for all t 2 1,
f(x!()) + "
2 (0) 1| + " 1 14
(1 - Be) 1 11=00110 - -000
2
S 30-1ff" + (1 - a ((x11-11)-
0+ 1 (1 - a,-1) ||00 - 11-1)
2
na--1 (at-1 - TC-1)
xx* x
|1 11a411
T1-1
||00"
((1-1))
gtt
2
2
min {1,0,}
Remark that for all 1. 1 1, 04- 7-- 0
g(1
$ (1 02-1), and the
7 quadratic terms xx - (t-1)) cancel each other. Then, after noticing that for all / 2 1,
1-g 9
1-4
af q(z
(1 + 14) (1 0z) al_1
7raa 1
( by the updates of az),
1
which gives f(xx(1) f
2 0
|| - -0001== = I-ar We are left, for all t 2 1, with
I-aa
1 St S S
+
gt
|Tx! ((-)
1) 2 (1) + niy Or |
(22)
I-
a
min {1, 0z}
2
2
Using the fact that 1.0 S 1 +
1. we immediately derive from equation (22)) that
St S S + Pe + ft - " -1>000y00
- y (2)+ + (n + p)a P2
1|x= -
-000
1 1- 04
A 2
2
We obtain the following by minimizing the right-hand side of the above w.r.t Oz.
S
S S.1 + ip + 22pp(H + 1)a--1llzz
((1)
a-a at
and after unrolling the recursion,
Se
fj
21 + +n)aa=1 10- - x101
S So +
+
A,
1-
A
j=1
j=1
We may define Uj = Vln + m)
||
x - --(ا //2///AA1111 and aj = 2 2/Fj/ v AJ-1. Note
S (1/(A - az)) where (11(1- f(x(())-))
- f + T+E
2 a (+) (11 Therefore,
we have of S S.
A."
a < So +
9j Σ aju for all 1 1.
-1
j=1
This allows us to apply Lemma A4
(Let S = So + Σラ أ then we have uf S S +
Ej azu S (v S + Σラ= 03)² meanwhile St + E/= aرu; 2 St/A, ), which yields
2
St < So + Σイ
9j
Su + 3
A
Aj-1
Ay-1
1=ر
which provides us the desired result given that f(x(())
- f
<
S and that n (0) = (0)
I-a;
22

---

We now simplify the above theorem for our quadratic problem (PT).. In particular, we prove a variant of Proposition 5 from Lin et al. [B4]], replacing f(x=())- - f(x") with its upper bound /
Corollary A.6. Let (x(1)) J220 and {y h220 be generated by Algorithm I assuming that x(() E H. for all t 2 where local methods find zi. (K1) such that
(L + ( [6] p)
ho(=)k))) 10--ii lig S Pr:
18
Let the objective f be defined in (PI) and assume x 0. where "io pu(1 4 and A,
(1 -V) with Ao = 1 and q = / 11) and og v then the final solution (1) is guaranteed
)(al())) - 8 S 2(L + n1) |611
(V9 - p)² (1 p)+
(23)
Proof. We first show the following inequality
DD- (2 =2))l00 S
V
2(1 49)--1
(V1- vū)
-v]
L + p
|1b1] +3 j=1
1
2
A
(24)
By the definition of f in (PII), we know 2ÿ - =QQ DDD1222 Since (0) 0 and ʃ is L-smooth, implies
f(a!0))- f(ant) _ I== -;
L,
I, _ "1aQ D 1/-11/21113
I _ DD II. bl - 2 lbll
L
where the second equality due the identity II, - 1/2 and the last inequality is from the fact that ||ol| I = and |22 I || When og - V मोシ then 70
(n7 + p)ao(aa 9) u(1 vσ). then it indicates
L L+
V (1 - an) (s (zo(1)) (*) + ||0 x x0001
1 (1 (1-va)
v
[|x:(0) -x"") 112
L+ P
Vq)
|
Since A,-1 = (1- -v))-1,,
[o]]=-,,one one can simplify Eq. (20) of Lemma A.5 as the following
--)- (vl-- v0) (
((x(0))- ((())) S (1-
vo)
L 1
||b| + 3
2
Aş-1
Let f2 = + (1]lB1|1( - -p)p/18, then
9j
9:p, Va)=-I
Lota b 17((1-)) p)d
v Lu 1611
p)
3
Aj-1
Follow the same steps as shown in Proposition 5 of Lin et al.
[54]] the right-hand side of Eq. (244) is
v (1- v
[
| +
Σ
9j
V (1 v
L
|
1
Σ
1 p
A--1
1=1
J=1
$ (V(-v0) v2) (
(I.t 1))
51+1
1 1-p p
|bbl1
where Ç (=
2
--1 1'
1 1 - Vq
This leads to
2
f(x(0)) -f" s (1- --- (1l- v ( (I+
2 )
11)
c++1
||b||
5 -
23

---

L 11
S (1- VØ)
||61
5 1
L+ 1r
2
1661
((1 3
2
(
2
I. 11
v1 p
||B11
(1- p)'
2
vI p- v1 V0
2
L |1611
1
(1 p)(t1
2
vI p v1 - vo)
T. + 1M
4
(1 -))+1 = 2(T + 1))lbbll
|
(1 p)
2
(Vq- p)3
(vq p)2
where the last inequality uses the fact that convex, then
VT-p- -1- v 2
Ja Since I is p-strongly
D (x) - +, S (|x(0) - 13312 S V P
(f(z(0)- - f(xz)),
which leads us have the upper bound in Eq. (24)). Then, we have the following inequality
2 (L + p) [b)]
|D (=10 -
(1 - p) 4
VAVVQ - p)
The above theorem implies that if he (z) h S 4p := (L (L++)|0(((00)) then the function value
18
error satisfies ((x(0)) - f = 2
(v (1 - p) (1pr(1-p)
(ンリ-pp= Based on Corollary A.G. we
establish the total iteration complexity for AESP as presented in the following lemma.
Lemma tR (Outer-loop iteration complexity of AESP). If each iteration of AESP, presented in
Algorithm M finds xt := zi 2(K1) using M, satisfying be(zz(k)) - -h; S 4t == (L + 1)]|b|[(11
p) /18, then the total number of iterations T required ensure & AESP(C, a, b, n, M)
a(e,aa, b. as defined in Eq. (B). solving (PID, satisfies the bound
T T log
P where = 0.9 and q = + n)
(v p)2
Furthermore, ypx has lower bound Pt 2 (V p) /) all t [T].
Proof. As f is p-strongly convex, then 1/2 $110-1/2(00)) - xx") x13 S サ (1 - x011 113 S f(x(10) -8¹
It is enough to find a minimal integer T such that (() f _ That is, f() f S
2(L+))||b p)T+1 S ni² /2.
We have
P)
2(L + p1( 1)1b211b1
ut2
(V9- - -p}²
2
(1-p) < μe² (e29 - p)2
1
4(L + 1) 1
T < - log
4(T. + pb]|bb17
p
p p)
The minimal T satisfies the above inequality means (1 p)T has the following lower bound
He² (v/ - pp)
(1-p)²= > 4(L + 4)] b11?"
Applying Corollary A we know that (=(2 - h S lp: = tts (L + +D][b|I((11 - p)", then pr
is guaranteed lower bounded as
(<( - -p)
72 : 4(L + b1 p)² yee p))²
8r >
72
24

---

A.5 Proof of Theorem 35
Theorem 3.5 (Time complexity of AESP). Let the simple graph G(V,E) be connected and undi-
rected, and let f(x) be defined in (PI). Assume the precision > 0 satisfies {i bb: 2 cd.} & 9 and damping factor < 1/2. Applying & (ESP(e, a, b, 17. G. with r, = L 2n and M be either LOCGD or LOCAPPR, then AESP presented in Algorithm 11, finds solution & such that [D 11-1/2(#
loe S 6 with the dominated time complexity TT bounded by
vol(St) The
Ch.
-Chi
vol(S.)
Che 6t
T S
min
log
with
S min
2m
Ciks"
TéE
where T, Et. C2 and City are defined in Theorem of outer iterations satisfies
3.3
Furthermore, q = 1/(L p)) and the number
10
400(L + 1 -
T S
log
9 9/9
pe-q
Va
Proof. By the definition of total time complexity TT in Eq. (9),, we have T E TLOOGD or T Et T T.CCAPPRR Hence, the overall time complexity directly follows from Theorem B and
Theorem A. The upper bound on the total iteration complexity T is from Lemma 3.4 When a = 1J < 0.5, we have q = va ax), leading to an iteration complexity of T = Õ(1 Va). L
A.6 Proof of Theorem 3.6
The following theorem establishes the time complexity of AESP-PPR (Algorithm D2).
Theorem 3R (Time complexity AESP-PPR). Let the simple graph G(V, E) be connected and
undirected, assuming a 1/2. The PPR vector of V is defined in Eq. (I), and the precision e E (0, /.).. Suppose N =
a, s. MM) be returned by Algorithm A When M is
either LocGD (Algorithm G) or LocAPPR (Algorithm W. then it satisfies D (
1))l S
and AESP-PPR has dominated time complexity bounded by
T min {o vol(S (aaxe
maxi hy
}}=
(
{
m
R² R2/22
}
(25)
VOTTmaa
VacT
Va
Va
where maxx arg I vol( T/ and R is defined in Eq. (W).
Proof. We first analyze the total iteration complexity T required in Algorithm D. For the PPR problem defined in (I)) when a < 0.5, b = e., / a, L = 1, = - 2a, 9 oa/(1 a), and = 0.9, /7. we seek to determine / such that (1 p))+1 S <a²22/(400) - a²)). Since 0 the total iteration complexity simplifies to
[4(L+ + bIl
(400(1 - a²) a²c
10 a
400 - a²) a²c²
< log 0
< log
9 V
log
a
For [T], ppt
4: 1b11(11 p) and we know that bb1
< p)c+1
ue² then sp:
((4-0)²
Leb 18
b bb]l[111111 p)r - (vq- - 2)2 (772(1 - p)). As = maxly (ata)p
2(1+a) AA (A("(((")
from
Lemma 6.2, then for / E [7]. we have
2(1 + a)pp
2(1 + a)pr || (2(") (=
6 2
|4 1/2 (2, (1)
(7 + a)(v7 ue2
a²2²
36(1 - [6[1-p][VA/ ((= 1 3600 0.9 (2 (z(0))
where the first equality follows from Lemma 3.4 which states that Pr > ne² ( 19 p)?
72
By the bounded level set assumption for the scaled gradient, we have |
(22 (0)
1/2
(z,
25

---

R| / (1 R]]V)//(0)) = R 111 aR where assume that 21 0. This
leads to
max Ch
3600(1 - 0.9 Vh
(2) (0)
111
max Ch
Q²E² 3600(1 - 0 R2 a²
ET
R²
a²e²
2
Note that max ==
arg max (E[T] (S:) and that
(.
S min
Crmax cTmax
2m.. By combining
3,
the two bounds above, we complete the proof of the theorem.
A.7 Proof of Corollary
Corollary A.7. Let x (Ks) be the output of either LocGD or LoCAPPR, as defined in Algorithmm
and Algorithm @ respectively. Define the objective error as e, (z) (Ki)) = hz(z! - he(xt). Then, the following bound holds
cz(21 (Ke)
Kg II k=0
2
Vh, 1/2 (0) I|p (2,
5
1
a)
3
Proof. Recall Q =
22 2
1-a 1D-11 1/2 A/ 17-11/ 1/2, and the target linear system to solve is Q =
2
(t-11), Note that
1uts =
+ a
1
Tta 1
I
1-
T+a 1+
AD
-1
1 1+ 17
2
2
7+
[+ a 1aaa+0 +2
-1
AD
1+1 /
2(1 +1)
2(1 + 1))
[ |1+a+ 2m
I - AD
-1
(n) a)
Hence, D D-1/21I II
D1/2 1+1
(17 + a) a)Q
Recall x;- = Q Q- (b(-1) 1)_ Let (2, f) be estimate and
residual pair, then a. Q (+).. Since he is L + n--trongly smooth, then for < 2يي || 2ill Let 2 (Ke) be the estimate returned by
any z E R", it implies hz(z)= - he(z)t
APPR or LOCGD, then we have
(x(2)(ke)) - he(xz) <
+ L (k.)
||
2
1 +
11 ---h (k)) )
2
(n+ + L)
D 1/2
I1
11/2 (Ke) (k))
2(1 + x)
(n+ + L)
< 2(n + a)²
1D1/2
(k)))
where the last inequality is from the fact that for any 0, D- 1 < From previous analysis we know that \// (Ko)))
< II Ke-l (1 2(atn)
I+o+2n 2t (1)
D (1/ Il1 We
have a final upper-bound
hr(2z( hr(xx < (n+L) L)
K1-1
II
1 + + 2n 1110)
2(a +1)
(K) 110)
1/2 (2 (2((2()))) >1
10)
2(n + a)
k=0
We derive the bound under the condition that 17 1 2a.
26

---

B Related Work
Personalized PageRank. Personalized PageRank (PPR), initially introduced as variant of Googles PageRank [[2], was further studied in [25, 2Zll. A key property of PPR is that its important entries concentrated near the source node, allowing for effective retrieval of relevant information even at a lower precision e. These important entries follow the power-law distribution [[Z] 23]] Computing <-approximate PPR vectors is fundamental for analyzing large-scale graph-structured data, with applications in local clustering [4] 5S 16,, A4], modeling diffusion processes [[, 14., 21]], and training
node embeddings graph neural networks [TTL I.S 22, 29]. Further discussions on PPR-related
problems can be found in
26 2X R9, 50J.
There exist well-established iterative methods for computing PPR. particularly those based on solv- ing linear systems [224, 9.3. S.IJJ. Among these, the Conjugate Gradient Method (CGM) and the Cheby- shev method [|G]] are commonly employed for solving the symmetrized form of Eq. (... These approaches typically achieve a time complexity of Om/ va), where m is the number of edges. Further improvements have been made through symmetric diagonally dominant solvers [31 BS] and Anikin et al. [6] proposed algorithm for the PageRank problem with runtime complexity dependent on [V.. However, we focus on local methods that avoid accessing the entire graph.
Local algorithms and accelerations. Unlike standard solvers, local solvers [3, AL 9, 50, 42] exploit that the big entries of π are concentrated in a small part of the graph. Specifically, Andersen et al.
[I]] proposed the Approximate Personalized PageRank (APPR) algorithm, achieving time com- plexity of (11 (1)(e))) To further characterize the locality of ग, Fountoulakis et al. [20] introduced variational formulation of (I) and applied a proximal gradient method to compute local estimates with time complexity of Ó(I/((a + j=))))), where μ > 0 is local conductance constant associated with G. Both methods critically depend on the monotonic reduction of the residual or gradient to ensure convergence. The equivalence between APPR and other methods such Gauss-Seidel and coordinate descent has been considered [32]
26 97
but does not focus on local analysis.
The question of whether an algorithm with time complexity Ó(1/ (Vae)) can be achieved using methods such as FISTA [8], linear coupling [2], or other methods [II. [E] was raised in Fountoulakis and Yang [[9]]. However, the difficulty is that algorithms such as FISTA violate the monotonicity property where the volume accessed of per-iteration cannot be bounded properly. The work of Zhou al. [|52] proposes a locally evolving set process for localizing standard iterative methods for solving large-scale linear systems. However, their accelerated convergence rate framework strongly assumes that the residual has a geometric reduction rate, which could not be true in real-world settings. The work of Martinez-Rubio et al. [37]] employs nested APGD method, achieving time complexity of Ö(SS* vol(S \/v |S*| vol(S*)) where [S* supp(=;))) (with ot being the optimal solution of Eq. (P2)) and vol (S*) denoting the number of edges in the induced subgraph from St The factor |S*| appears in the bound due to the worst-case number of calls required for applying APGD. In contrast, our proposed framework introduces a novel local strategy that provably runs in 1/va outer-loop iterations. Furthermore, incorporate the Catalyst framework [3S, [a]], which ensures that each iteration maintains locality, allowing the overall time complexity to be locally bounded.
C Implementation Details and More Experimental Results
Algorithm and Algorithm present LocGD and LocAPPR respectively. They iteratively update the active node set in a queue data structure Q, ensuring a localized and efficient computation of the PPR estimate.
C.1 Datasets and Preprocessing
In our main experiments, we evaluate the proposed method on medium-scall graph com-dblp and four large-scale graphs ogb-mag240m. ogbn-papers 100M, con-friendster, and wiki-en21. To further investigate the effectiveness and acceleration performance of our approach on different sizes of graphs, we conducted additional experiments on more graphs. we treat all 19 graphs as undirected with unit weights. We remove self-loops and keep the largest connected component when the graph is disconnected. Table 0 presents the key statistics of these datasets, including the number of nodes
27

---

Algorithm 3 LocGD g ,7, a, 9)
Algorithm 4 LOCAPPR (1-1) 37 a, b,
1: Initialize:
((-11)
1: Initialize: 2 y
2: if [
(0) (2) 11 then
(2,
(())
then
3: Return
3: Return z
(utn) 2
(utn)e 2(+ta)e
4: 4 max
(=
6 max
m
(= ()
5: Q < : S (z)]
5: Q+ fu: G.dd I V <[Vn)((=)]
6: =
while Q + do
7: while Q + 0 do
7: + =.dequeueO
8: S(K) =1
if if|Val((z) < <Gvdd then
9: while @ + 0 do
continue 10: + (u)l((z)
< Q. doqueue()
11:
((k) append ((u, (z))
11: Zu + iu - I+a++2
Zu + Zu 14a+21 2n Vah((z)
12:
for E NN() do
13:
(h,(z), +-
13:
Voh((z)
Voh((z) + 14o+2n
14:
for (u, V V.h+(z)) S. do
8 Vduyd,
15:
for v E (()) do (u)
14:
if [ 2 av and v o
16:
(,h((z)
Voh((2)
then Qenqueue(())
1-a [.h((z)
I+a+2n vd.d.
15:
17:
[V), 2 ex do and $ Q
16:
if [z)+(2)] 2 av and u 2
then
then
Q. enqueue(v)
17:
C.nnqueee(u)
19:
k: + h ++1
18:
Return x(1)
20:
Return (1) + 2.
(n) and edges (m)) The largest graph in extended experiments contains up to 200 million nodes and billion edges, as shown in Table
C.2 Problem Settings and Baseline Methods
For solving Equation (PI) and
19 graphs, randomly select 5 source nodes from each graph. The damping factor a and convergence threshold were fixed at a = 0.1 and c = 1 x 10-6 throughout all experiments unless otherwise specified. To compare with AESP-LOCAPPR and AESP-LOCGD, we primarily consider LOCGD, APPR, LOCCH, FISTA, and ASPR methods as baselines. All methods implemented in Python with numba acceleration tools. Both ASPR and FISTA use a precision of = 0.1 and the parameter é c/(1 é) as suggested in [2I].
C.3 Additional experimental results
Comparison of baseline methods. Fig. compares the convergence behaviors of AESP- LocAPPR and ASPR for the com-dblp graph, with parameters 0.01 and c 0.1/n. As evi- denced by the early-stage iterations the subplots, AESP-LOCAPPR achieves significantly faster convergence compared to ASPR. Although ASPR guarantees monotonic decrease in the -nom of gradients, this property comes the expense of requiring increasingly iterative points, which consequently reduces computational efficiency.
Fig. demonstrates the superior convergence behavior of AESP-LOCAPPR, AESP-LocGD com- pared to bascline methods (LocCH, and FISTA) on the com-dblp graph, with parameters = 0.01 and e 0.1/n. AESP-LOCAPPR and AESP-LOcGD has rapid error reduction within the first 1 x 10 operations.
Fig. & presents results the estimation error reduction for 4 datasets: wiki-talk, ogbn-arxiv, com- youtube, and com-dblp. The acceleration effect of the AESP method is particularly evident in the initial stages.
Full results of 19 graphs. Fig. E demonstrates the performance comparison of our proposed algo- rithm against bascline methods (APPR, APPR Opt, and LocGD) across 19 graphs of varying scales,
28

---

Table 2: Dataset Statistics
Notations
Dataset Name
m
772
91
as-skitter
1694616
11094209
G2
cit-patent
3764117
16511740
93
com-dblp
317080
1049866
94
com-friendster
65608366
1806067135
9s
com-lj
3997962
34681 189
Go
com-orkut
3072441
117185083
97
com-youtube
1134890
2987624
Gs
ogb-mag240m
244160499
1728364232
Gy
ogbl-ppa
576039
21231776
910
ogbn-arxiv
169343
1157799
ogbn-mag
1939743
21091072
912
ogbn-pane sasbn--pppes1000
111059433
1615685450
91a
oghn-products
2385902
61806303
914
oghn-proteins
132534
39561252
915
soc-lji
4843953
42845684
916
soc-pokec
1632803
22301 92301964
917
st-stackoverfllow
2584164
28183518
918
wiki-en21
6216199
160823797
G19
wiki-talk
2388953
4656682
com-dblp (a 0.01, 0.1/n)
com-dblp (a 0.01, - 0.1/n)
-6
AESP LocAPPR
AESP-LocAPPR
-8
ASPR
-8
AESP-LocGD
k
LocCH
-10
100
10
t
FISTA
-12
log
-14
16
0
log
-14
-16
-16
0.0
0.5
L0
1.5
2.0
Operations
X10
# Operations
x10
Figure 6: Comparison of of AESP-LOCAPPR
Figure 7: Comparison of log D -- llo over the operations on the com-dblp graph with a 0.01 and 0.1 0.1/n, /n, illustrating the perfor- mance of AESP-LOCAPPR, AESP-LOCGD, LOCCH, and FISTA.
versus ASPR, log || '( - π loo over the op- erations the com-dbip graph with 0.01 and ε = 0.1/n (Insets Show Early-stage Itera- tion Details)
while Table G and ! present the corresponding operation counts and running times across different graphs. The results clearly show that AESP-based methods (AESP-LOCAPPE and AESP-LocGD) achieve significantly faster error reduction during initial iterations, highlighting their superior con- vergence properties, while maintaining robust performance across all graph scales from small to extremely large graphs, which substantiates the algorithmic robustness.
Table H reveals that our algorithm exhibits suboptimal performance on certain graphs, which can be attributed to the computational overhead introduced by the iterative parameter initialization process (particularly for it and e, inner-loops). While this initialization overhead marginally increases runtime in some cases, it crucially enables the superior convergence rates. What's 's more, this trade-
29

---

Table Operations Needed for five local solvers on 19 graphs datasets.
Graph
APPR
APPR Opt
LocGD
AESP-LoeGD
AESP-LocAPPR
as-skitter
3.06e+06
1.39c+06
1.94c+06
1.26e+06
1.00e+06
cit-patent
3.86e+06
1.81e+06
2.62e+06
1 1,45++06
1.27e+06
com-dblp
6.07e+06
3.18e+06
4.66e+06
I 1.63++06
1 1.43++06
com-friendster
8.35e+05
3.20e+05
3.87e+05
6.65e+05
6.57e+05
com-lj
1.73e+06
7.14e+05
9.69e+05
8.18e+05
7.70e+05
com-orkut
1.32e+06
5.72e+05
7.06e+05
8.29e+05
8. 8.19++05
com-youtube
2.27e+06
1.33e+06
1.60e+06
1.27e+06
1.09e+06
ogb-mag240m
1.92c+06
8.46c+05
9.86c+05
7.54c+05
7.01c+05
ogbl-ppa
8.19e+05
4.36e+05
4.53e+05
7.45e+05
7.33e+05
ogbn-arxiv
1.20c+07
5,47c+06
8.99c+06
2.59c+06
2.25c+06
ogbn-mag
9.23e+05
3.89c+05
4,45e+05
6.65e+05
6.33e+05
ogbn-papers
100M 100M
1.18++06
5.05c+05
5,86c+05
8.38c+05
7.98c+05
ogbn-products
2.00++06
9.73e+05
1.30e+06
9.1 le+05
8.89e+05
oghn-proteins
7.55e+05
7.73e+05
7.60e+05
9.20e+05
9.20e+05
soc-Ijl
2.45e+06
1.09c+06
1.53e+06
1.03e+06
9.51e+05
soc-pokec
1.58e+06
7.13e+05
7.98e+05
9.38e+05
8.95e+05
sx-stackoverflow
9.08e+05
3.47e+05
4.39e+05
5.18e+05
4.88e+05
wiki-en21
7.19e+05
2.18e+05
2.27e+05
5,47e+05
5.36e+05
wiki-talk
1.39c+06
7.76c+05
9.83c+05
6.79c+05
5.42c+05
vnlo-tale
ogtn -310
A27B
Opensloea
Operntaam
X100
Opankaae
'310"
Gpanelicns
Figure 8: Performance comparison of five local solvers across four graphs: wiki-tulk, ogbn-arxiv, com-youtube, and com-dblp (with parameters a = 0.01 and 0.1/n).
off between initialization overhead and convergence acceleration becomes increasingly favorable as the graph size grows.
Initialization of 2, Fig. A presents comprehensive comparison of different initialization strate- gies for the inner-loop optimization in AESP-LocAPPR, where we identify 2 = -t--)) as the rec- ommended choice based on empirical evidence. This supplementary investigation further evaluates the performance of AESP-LOCAPPR and AESP-LOCGID under varying initialization approaches (t versus momentum-free (t-1) versus zero-initialization) with fixed parameters and = 0.1/n. Fig. [[] demonstrating that the proposed ((t-1) initialization yields significantly superior convergence characteristics compared to both the (t-s)-baaed and cold-start alternatives. While all three initialization strategies (y (t-11) and zero-initialization) exhibit comparable performance during the initial iterations, the y (t-1) based approach establishes substantial superior- ity in later optimization stages.
0.01
30

---

Table 4: Running times
Graph
APPR
APPR Opt
LocGD
AESP-LocGD
AESP-LocAPPR
as-skitter
6.90e-01
3.18e-01
4.24e-01
5.62e+00
5.63e+00
cit-patent
5.05e-01
2.50e-01
9.97e-02
6.08e-02
1.87e-01
com-dblp
6.38e-01
3.28e-01
7.74e-02
2.32e-02
1.41e-01
com-friendster
1.60e+01
7.32e+00
9.93e+00
3.14e+02
3.15e+02
com-lj
1.18c-01
4.93e-02
2.70c-02
3.38e-02
6,87e-02
com-orkut
3.22e-02
1.47e-02
1.11e-02
1.74e-02
2.77e-02
com-youtube
2.90c-01
1.72e-01
3.55e-02
2.60e-02
1.33e-01
ogb-mag240m
6.17e-01
1.75e-01
3.56e-01
2. 2818-101
2.40c-01
ogbl-ppa
2.00e-02
8.77c-03
5.30c-03
7.81c-03
1.78e-02
ogbn-arxiv
1.10++00
5.04e-01
1.35e-01
3.08e-02
1.98e-01
oghn-mag
4.46e-02
2.29e-02
1.09e-02
1.46e-02
4.47e-02
ogbn-papers 100M
1.30e-01
6.09e-02
5.19e-02
1.81e-01
2.17e-01
oghn-products
7.91e-02
3.69e-02
2.85e-02
2,48e-02
3.98e-02
egbn-proteins
3.84e-03
3.71e-03
2.45e-03
2.50e-03
4.55e-03
soc-Ij1
1.73e-01
7.59e-02
4.09e-02
4.48e-02
9.75e-02
soc-pokec
9.18e-02
4.07e-02
2.04e-02
2.31e-02
5.93e-02
sx-stackoverflow
1.37e+00
5.44e-01
7.01e-01
2.90e+00
4.39e+00
wiki-en21
2.71e-02
8.66e-03
6.85e-03
2.40e-02
3.82e-02
wiki-talk
2.40e-01
1.53e-01
3.08c-02
2.15e-02
1.06c-01
-18
-00
edtigg
+80
-33
-50
-30
105
Ogens
Figure 9: Comparison of five local solvers over graphs
31

---

AESP LOCGD (a 0.01, = 0.1/n)
AESP -OCAAPP (a 0.01, 0.1/n] 10
10
-04
(0)
TT)
100
-0.8
(0)
x (113)
1)
0,8
(t-1)
-1.0
-10
D
-1.2
-12
log
-1.4
0.0
0.5
1.0
1.5
2.0
2.5
0.00
0.25
0.50
0.77
1.00
1.25
1.50
Operations
x 100
Operations
X 100
Figure 10: Comparison of AESP-LocAPPR and AESP-LOcGD with three initializations on the graph com-dblp (with parameters 0.01 and 0.1/n).
32

---

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: The main claims made in the abstract and introduction accurately reflect our contributions and scope. We propose novel framework based nested evolving set pro- cesses and employ inexact proximal point iterations to accelerate Personalized PageRank (PPR) computation.
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.
It is fine to include aspirational goals as motivation as long as it 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:
We discussed several limitations of our proposed work in the last section.
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 are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated 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 a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairnsss.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in 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 prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
33

---

Answer: [Yes]
Justification: The paper thoroughly presents theoretical results, including the full set of assumptions necessary for each theorem and lemma. Each proof is detailed and follows logically from the stated assumptions, ensuring correctness.
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 theo- rems.
The proof's 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 short proof sketch to provide intuition.
Inversely, any informal proof provided in the of the paper should be comple- mented by formal proof's 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 the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide comprehensive details on the experimental setup, including de- scriptions of the datasets used, parameter settings, and the specific algorithms applied. We also provided our code for review and will make it public upon publication.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture the contribution it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
fully might suffice,
specific model and empirical evaluation,
While NeurIPS does not require releasing code, the conference does require sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to 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
34

---

reproducible, they some way (e.g., to registered users), but it should be possible for other researchers have some path 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 provide open access to the data and code, along with instructions in the supplemental material.
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.
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so an acceptable answer. Papers cannot rejected simply 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: for more details.
/ //nips. wttppsscccppllcc////ecccccccccct wwwpp/pwwc/gw.pe////eeeeee//ee/e
The authors should provide instructions 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. If only subset of experiments 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 permitted.
6. Experimental setting/details
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?
Question:
Answer: [Yes]
Justification: We follow the existing experimental setup and provide detailed information the training and testing settings used for AESP-LocAPPR and AESP-LocGD.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper 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 other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The paper reports error bars and other relevant information about the statisti- cal significance of the experiments. We use 50 randomly sampled nodes and plot the mean of the results.
Guidelines:
The answer NA means that the paper does not include experiments.
35

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
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).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is 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 error rates).
If eπror 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 on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
The experiments were conducted using Python 3.10 with CuPy and Numba libraries on a server with 96 cores, 503GiB of memory, and four NVIDIA RTX A6000 GPUs with 28GB each.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs 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 or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
The research adheres to all aspects of the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure 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 societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: There broader socictal impacts, as it focuses technical contributions.
36

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate point that 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 out that a generic algorithm for optimizing neural networks could enable people 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 or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.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 MI..
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [Yes]
Justification:
The paper does not involve data models with a high risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access 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 is 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
Question: 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?
Answer: [Yes]
Justification:
The paper does not involve licenses for existing assets.
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 or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
37

---

For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the pack- age should be provided. For popular datasets, ssperswithcods com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's ' creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [Yes]
Justification:
The paper does not involve new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moddl 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 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 pa- per include the full text instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [Yes]
Justification:
The paper does not involve crowdsourcing and research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to NeurIPS Code Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
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 on the requirements of your country or institution) were obtained?
Answer: [Yes]
Justification: The paper does not involve institutional review board (IRB) approvals equivalent for research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
38

---

Depending on the country in which research is conducted, IRB approval (or equiva- lent) 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 we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [Yes]
Justification: The paper does not describe the usage of LLMs as an important, original, or non-standard component of the methods in this research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
39


Reviews:
[{"review_id": "1LmGbrS1wx", "reviewer": "Reviewer_P4e6", "summary": "This paper proposes the Accelerated Evolving Set Process (AESP) framework that leverages the accelerated inexact proximal operator to improve the computation efficiency of personalized PageRank. Particularly, the proposed algorithm improves the time complexity of existing methods for $\\epsilon$-approximate personalized PageRank computation from $O(vol(\\mathcal{S}_t)/(\\alpha \\gamma_t))$ to $O(vol(\\mathcal{S}_t)/(\\sqrt{\\alpha} \\gamma_t))$.", "questions": "1. How do the proposed methods compare to the sampling-based PPR estimation algorithms (e.g., FORA [KDD'2017]) in empirical efficiency?\n2. What is the intuition underlying the proposed methods for the lower time complexity?", "limitations": "yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "S1. The paper is theoretically grounded and technically grounded.\n\nS2. The idea of utilizing the accelerated inexact proximal operator is novel.\n\nS3. The methods are guaranteed to converge without any additional assumptions, and the time complexity achieves a provable improvement over existing works.\n\nW1. The assumption on constant $R$ may not hold.\n\nW2. The empirical studies that compare the proposed methods against the algorithms for personalized PageRank estimation on more datasets are needed. e.g., FORA [KDD'17], TopPPR [SIGMOD'19].", "was_revised": true, "final_justification": "Thank you for the responses. I would maintain my rating given the theoretical contributions in this paper.", "rebuttal": "**W1.** The concern of the assumption on a constant $R$  may not hold.\n\n**A1.** We appreciate the reviewer's insightful observation regarding the assumption of a constant $R$. As we discussed in line 248, we have provided explanations concerning this assumption. Overall, our experimental results demonstrate that: 1). $R$ does not exhibit any significant trend with respect to variations in graph size; 2). The increase of $R$ with decreasing $\\alpha$ shows a relatively gradual trend. Based on our comprehensive experiments, we found that $R$ generally maintains a magnitude on the order of $\\log(1/\\alpha)$. These observations support the constant $R$ is a relatively small constant parameter in our analysis. \n    \n**Q1.** How do the proposed methods compare to the sampling-based PPR estimation algorithms (e.g., FORA [KDD'2017]) in empirical efficiency?\n\n**A1.** Thank you for your question. We appreciate the opportunity to clarify the comparison with FORA [KDD'2017].  1) **Implementation Differences**: FORA is implemented in C++, while our method is implemented in Python with Numba acceleration. This difference in implementation languages and frameworks makes direct runtime comparisons less equitable.  2) **Algorithmic Frameworks**: FORA combines an approximate PPR (APPR, i.e., Forward Push) step with Monte Carlo random walks to refine the estimation. In contrast, our method (AESP) focuses on computing the full PPR vector for a given source node, rather than pairwise node-to-node probabilities. Thus, the two methods address distinct problem formulations, making operational comparisons less meaningful.  3) **Potential Synergy**: Empirically, our method demonstrates strong early-stage acceleration, which could potentially improve the Forward Push phase in FORA. This represents a promising direction for future work.  \n\n**Q2.** What is the intuition underlying the proposed methods for the lower time complexity?\n\n**A2.** We sincerely thank the reviewer for raising this important question about the intuition behind our method's improved time complexity. Our proposed framework is based on the following fact: at each time, we use a faster algorithm for solving a simpler version of the original problem, which has a constant condition number. Combine these solutions together to obtain the approximation of the original problem. These techniques are in the same vein as those in [1]. In optimization, this is the Catalyist framework.\n\n[1] Peng, Richard, and Daniel A. Spielman. \"An efficient parallel solver for SDD linear systems.\" Proceedings of the forty-sixth annual ACM Symposium on Theory of Computing (STOC). 2014."}, {"review_id": "R49qmk6yrO", "reviewer": "Reviewer_GvHx", "summary": "The paper studies the time complexity of Personalized PageRank (PPR) computation. It introduces a nested evolving set process to improve the time complexity to $\\tilde{O}(\\min(R^2/\\epsilon^2, m))$, where $R$ is a constant defined by the process and $\\epsilon$ is the normalized additive error parameter. In particular, the time dependence on the damping factor $\\alpha$ is improved to $1/\\sqrt{\\alpha}$. Theoretical analysis and experimental results are provided to demonstrate the effectiveness of the proposed methods.", "questions": "I’ve described my questions in the “Weaknesses” section above. Please refer to that for details.", "limitations": "Yes, there is not much concern about the potential negative societal impact of this paper.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nS1. The problem of efficiently estimating Personalized PageRank (PPR) on large graphs has been widely studied and has numerous applications. Improving the time dependence on $1/\\alpha$ is of particular interest in recent work, so the paper is well motivated.\n\nS2. The paper is generally well written and easy to follow (though some issues should be addressed, as outlined below). The theoretical analysis appears sound. Experimental results and source code are also provided, which strengthens the paper’s contributions.\n\nS3. The paper demonstrates that the time dependence on $1/\\alpha$ can be improved using nested evolving sets. While the improvement is partial, the underlying idea and algorithmic structure could offer new insights to the community.\n\n\nWeaknesses:\n\nW1. The complexity results presented in the paper are not very interesting to me. The proposed algorithm has quadratic dependence on $1/\\epsilon$, where $\\epsilon$ is the degree-normalized additive error. In contrast, the basic Forward Push algorithm (FOCS 2006) has a time complexity of $O(1/(\\epsilon \\alpha))$ (please correct me during the rebuttal if there is any misunderstanding). In other words, while the paper improves the dependence on $\\alpha$ from $1/\\alpha$ to $1/\\sqrt{\\alpha}$, it introduces a worse dependence on $\\epsilon$. This trade-off weakens the overall contribution.\n\nW2. Although the writing is generally clear, some aspects of the presentation need refinement: First, it would be better to clearly define the problem (i.e., the approximation error requirement) at the beginning of the paper. Presenting the complexity bound before defining the problem makes the bound hard to interpret. Second, the use of the term ”$\\epsilon$-approximation” is potentially confusing. In most literature, this refers to relative error, while in the paper, $\\epsilon$ denotes degree-normalized additive error. Clarifying this distinction earlier would help avoid confusion.", "was_revised": true, "final_justification": "After reading the paper and the authors' rebuttal, I decided to keep my original score.", "rebuttal": "**W1.** Concern about the tradeoff between the sparsity (related with $\\epsilon$) and the condition number (related with $\\alpha$)\n\n **A1.** We appreciate the reviewer’s insightful comment regarding the tradeoff between $\\epsilon$ and the condition number $\\alpha$. As discussed in Martínez-Rubio's work (see [1]), the final bound indeed represents a tradeoff between the dependence on the condition number, i.e., $1/\\alpha$, and the sparsity, i.e., $1/\\epsilon$. Specifically, while the condition number dependence scales as $1/\\sqrt{\\alpha}$, the sparsity dependence increases to $1/\\epsilon^2$, which aligns with the conjecture and discussion in their work. Exploring whether a tighter dependence on $\\epsilon$ can be achieved remains an interesting direction for future research, and we plan to investigate this further in our subsequent work.  \n    \n[1] Martínez-Rubio, David, Elias Wirth, and Sebastian Pokutta. \"Accelerated and sparse algorithms for approximate personalized PageRank and beyond.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.\n\n**W2.** The concern of the presentation in our abstract and introduction.\n\n**A2.** We appreciate the reviewer's valuable suggestions for improving the clarity of our presentation. We acknowledge these points (e.g., approximation error definition, $\\epsilon$-approximation, etc.) and will revise the paper to more intuitively and clearly present our results before introducing the problem formulation."}, {"review_id": "T24HDHCSUE", "reviewer": "Reviewer_Ev2P", "summary": "This paper introduces the Accelerated Evolving Set Process (AESP), a novel framework designed to accelerate the Approximate Personalized PageRank (APPR) algorithm. The core of AESP lies in its formulation based on inexact accelerated proximal point iterations. The authors provide a rigorous theoretical analysis, establishing sufficient conditions for convergence and detailing the method's time complexity. A key theoretical finding is that AESP achieves faster convergence rates than traditional APPR in the early stages. Extensive experiments on large-scale graphs, with node counts ranging from 6 million to 240 million, empirically validate this theoretical advantage, demonstrating that AESP-based methods significantly outperform baseline approaches in terms of early-stage convergence speed.", "questions": "Thank you for your work on this interesting problem. The paper is promising, particularly due to its strong theoretical contributions. However, I have a few key concerns regarding the clarity of the presentation and the experimental evaluation that prevent me from giving a higher score at this stage. My questions and suggestions below are intended to clarify these points. My evaluation score will be raised if you can address them convincingly in your rebuttal.\n1.\tOn the clarity of proposed AESP Framework: \nMy primary concern is with the presentation of the AESP framework in Section 2.2. I found the exposition overly complex and the notation difficult to follow, which obscures the core intuition behind the method. To address this, I strongly encourage the authors to Consider adding a simple, illustrative figure or a running example that walks the reader through one or two iterations of the algorithm. This would significantly improve comprehensibility. My score would increase substantially if the authors can provide a clearer, more accessible explanation of their framework in the rebuttal.\n2.\tOn the Robustness of the experimental evaluation:\nThe experimental section provides evidence for AESP's fast early-stage convergence. However, the choice of baseline methods seems somewhat outdated, which limits the persuasiveness of the results. To claim superiority, a comparison against the current state-of-the-art is essential. Could the authors please justify their choice of the current baselines? Are there specific reasons (e.g., implementation availability, direct comparability) why these were chosen over more recent methods from top conferences from the last 3-5 years?\n3.\tOn the characterization of early-stage convergence:\nThe paper's key empirical results emphasize that AESP's primary advantage is its faster early-stage convergence. This raises a question about the method's performance envelope. Could the authors elaborate on the behavior of AESP in the later stages of convergence? Specifically, does the performance advantage over baselines diminish or disappear as the approximation error tolerance becomes very small? Is there a crossover point after which traditional methods might become more efficient?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nSignificant Theoretical Contributions: The paper provides a rigorous theoretical foundation for the proposed method. A key strength is the inclusion of not only a detailed time complexity analysis but also formal convergence guarantees. Generality and Extensibility: The authors demonstrate the versatility of the AESP framework by analyzing its application to several variational forms of the PPR problem. This analysis effectively shows how the proposed framework can be extended beyond the standard PPR setting, broadening its potential impact. Practical and Meaningful Problem: The work addresses the important and practical challenge of accelerating a general formulation of the Personalized PageRank problem. Developing faster algorithms for this fundamental task is a meaningful contribution to the field of large-scale graph analysis.\n\nWeaknesses:\nClarity and Presentation: The presentation of the proposed framework is overly complex, which significantly hinders readability and makes the core ideas difficult to follow. Choice of Baselines in Experiments: The persuasiveness of the experimental results is somewhat limited by the choice of baseline methods. The selected baselines (e.g., APPR, APPR-opt) could be considered dated. A more robust evaluation against more recent PPR approximation algorithms would be necessary to convincingly demonstrate the superiority of the proposed AESP framework.", "was_revised": true, "final_justification": "I am fine with the response. I keep the decision and suggest to accept this work.", "rebuttal": "**Q1.** **The concern about the clarity of proposed AESP Framework**  \n\n**A1.** We appreciate this constructive suggestion and will add an illustrative figure to enhance the clarity of the AESP framework. The figure will demonstrate: (1) a simple graph with several nodes including the source node; (2) the first inner loop's local method (locGD or APPR) iterations, where the initial active set $\\mathcal{S}_1^{(0)}$ contains only the source node, with subsequent iterations showing $\\mathcal{S}_1^{(t)}$ first expanding then contracting; (3) the second inner loop recomputing the initial active set $\\mathcal{S}_2^{(0)}$ based on the previous solution, where the shrinking tolerance $\\epsilon_k$ leads to progressively larger active sets. Hope this will effectively demonstrate the dynamic evolution of active sets throughout the iterative process.\n\n**Q2.** **On the Robustness of the experimental evaluation**\n    \n**A2.** We appreciate the reviewer's valuable feedback regarding baseline selection. Our choice of baseline methods was motivated by several key considerations: (1) Since AESP's inner loop employs either locGD or APPR, we directly compared against these fundamental methods to demonstrate the acceleration benefits; (2) We have indeed included comparisons with recent methods ASPR[1] (2023), LocCH[2] (2024) and maintained FISTA[3] (2009) as it remains a relevant benchmark, with these results presented in Appendix C.3 (Figures 6-7) due to space constraints; (3) The results clearly show AESP's superior early-stage convergence with rapid error reduction;\n\n[1] Martínez-Rubio, David, Elias Wirth, and Sebastian Pokutta. \"Accelerated and sparse algorithms for approximate personalized PageRank and beyond.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.\n\n[2] Zhou, Baojian, et al. \"Iterative methods via locally evolving set process.\" Advances in Neural Information Processing Systems 37 (2024): 141528-141586.\n\n[3] Beck, Amir, and Marc Teboulle. \"A fast iterative shrinkage-thresholding algorithm for linear inverse problems.\" SIAM journal on imaging sciences 2.1 (2009): 183-202.\n\n**Q3.** **On the characterization of early-stage convergence**\n\n**A3.** We sincerely appreciate this insightful question regarding AESP's convergence behavior. Our analysis reveals that while AESP demonstrates significant early-stage convergence advantages, its time complexity does increase during updates as $\\epsilon_t$ decreases. We conducted new experiments on the **ogbn-arxiv** dataset ($\\alpha=0.1$, a random source node, different $\\epsilon$ values range from $10^{-6}$ to $10^{-10}$). We found that, when AESP maintains a constant condition number for subproblems, its convergence rate in later stages becomes less pronounced compared to non-accelerated methods like APPR-Opt. This occurs because the subproblem precision $\\epsilon_t$ eventually becomes smaller than the original problem's precision requirement. However, we emphasize that our outer loop incorporates an early-stopping mechanism (Algorithm 1, Line 7), which ensures comparable total operations between methods. Thus, while AESP's advantage becomes less pronounced at extremely small $\\epsilon$ (the locality is not significant, so all local methods do not have any advantages) values, it maintains overall operational efficiency comparable to baseline methods throughout the convergence process. Whether one can optimize/accelerate the convergence of the later stage is an interesting problem to explore."}, {"review_id": "rOeTJhBhtq", "reviewer": "Reviewer_qYeh", "summary": "The paper proposes a novel framework called AESP (Accelerated Evolving Set Process) to approximate the Personalized PageRank (PPR) vectors in a faster way using local computations. AESP has a complexity of O(min{ R^2/(sqrt(α)ϵ^2) , m/sqrt(α) }), where R is a constant depending on the evolving set process and m, α, ϵ are the number of edges, the damping factor, the precision, respectively. Interestingly, when 1/ϵ^2 ≪ m the algorithm computes an ϵ-approximation of the PPR vector with an time  complexity independent of the underlying graph size. The authors show that AESP can accelerate any existing local solver, e.g. APPR, by (1) reformulating the PPR computation as a convex quadratic problem, (2) applying proximal point acceleration with an evolving set process to avoid accessing the whole graph and to solve easier subproblems, (3) using the local solver for each subproblem, (4) using momentum [39] to update the estimate with less iterations (from 1/α to 1/sqrt(α)).", "questions": "If one compares with O(1/(αϵ)) from APPR where are the wins and losses? How does the ϵ^2 in the proposed method here affect performance compared to APPR and other methods with just  ϵ involved?\n\nHow does the R in the complexity scale with dumping factor? \n\nHow does the method perform against other methods from the literature e.g. Ref.[37] ?", "limitations": "The limitations of the current algorithmic proposal have not been sufficiently discussed, although to be fair there are some interesting ablation studies. Furthermore, some cases in large graphs where the method underperforms compared to baselines have been identified, but I was not convinced from the explanations.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Pros: The paper answers an open conjecture [19, 52] about achievable time complexity for the PPR computation. The problem is well introduced and the presentation is rigorous. Theoretical analysis with mathematical proofs are provided. The evaluation on real-world large graphs has been conducted, with a comparison with baseline algorithms (APPR and LocGD from [52]). Experiments include ablations (different initialization methods, different α values) and are consistent with the theory. They show acceleration in error reduction during initial operations and overall speedup.\n\nCons: The constant R depends not only on graph parameters, and R is not explicitly bounded. The authors claim that given the empirical results, it still seems to be small and show in Fig.3 a value of at most 1.4. However these values are shown for alpha = 0.1 and 0.01. Even for these two values of damping factor, there is an increase in R for lower alpha. This means that since R(a) then this should be also incorporated in the claimed complexity. How does R grow with smaller alpha? \nMore generally, a study of the algorithm over the range of the damping factor is missing. For example, the authors assume that α < 0.5, but is the algorithm also robust to high α values?\n\nAnother issue that troubles me is that the complexity has a denominator in ϵ^2 instead of ϵ. Certainly there is a benefit to go from 1/α to 1/(sqrt(α) but there is penalty in having the squared precision in the denominator. This is not discussed sufficiently.\n\nFurthermore, the comparison against APPR, LocGD and FISTA give interesting results, however, there are other state-of-the-art methods for approximating PageRank, e.g. it is missing comparison against Ref.[37] although extensively discussed in the Related Works section.", "was_revised": true, "final_justification": "The authors have made a good effort in answering my main concerns, especially the scaling of R with respect to a, and the effect of epsilon^2. I will keep my score, for the following reasons.\n\n1. Given the dependence of R on alpha<0.01 this should somehow be visible in the complexity expression. Strictly speaking R is not a global constant but a function of alpha, and this behavior is not sufficient to be shown empirically on a couple of datasets.\n\n2. Aiming to improve the complexity over the alpha parameter, another aspect of the algorithm gets worse. Specifically, O(1/sqrt(alpha)) comes at the cost of a looser dependence on sparsity O(1/epsilon^2). The paper does not answer the question, can we get better without worsening another aspect or have we reached the limits?\n\nI have appreciated the contribution of the paper, but I believe these two aspects should have been discussed and analyzed with more rigor, this is why I keep the Borderline accept score 4.", "rebuttal": "**Q1.** If one compares with $O(1/(\\alpha\\epsilon))$ from APPR where are the wins and losses? How does the $\\epsilon^2$ in the proposed method here affect performance compared to APPR and other methods with just $\\epsilon$ involved?\n\n**A1.** Thank you for raising this important question regarding the trade-offs in our theoretical guarantees.  \n\n1) **Practical Impact of $\\epsilon$**: In PPR approximation, the precision parameter $\\epsilon$ is typically not set too small, as an excessively tight tolerance would cause local push-based methods (e.g., APPR) to degenerate into global algorithms due to an overgrown active set. Thus, in practice, optimizing the dependence on $\\alpha$ is often more critical than the $\\epsilon$-dependence.  \n\n2) **Trade-off Between $\\alpha$ and $\\epsilon$**: As discussed in Martínez-Rubio et al. [1], our bound reflects a fundamental trade-off: while we improve the condition number dependence to $O(1/\\sqrt{\\alpha})$, this comes at the cost of a looser $O(1/\\epsilon^2)$ dependence on sparsity. This aligns with existing conjectures about such trade-offs in iterative methods. Whether a tighter $\\epsilon$-dependence (e.g., $O(1/\\epsilon)$) can be achieved without sacrificing the gains in $\\alpha$ remains an open question, and we intend to explore this direction in future work.     \n\n [1] Martínez-Rubio, David, Elias Wirth, and Sebastian Pokutta. \"Accelerated and sparse algorithms for approximate personalized PageRank and beyond.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.\n\n**Q2.** How does the $R$ in the complexity scale with dumping factor $\\alpha$? \n\n**A2.**  We sincerely appreciate the reviewer's insightful comments regarding the scaling behavior of $R$ with respect to the damping factor $\\alpha$. To address these concerns, we have conducted additional experiments (see table below) examining $R$ across both small $\\alpha$ values and values approaching 0.5, using the com-dblp graph (with $\\epsilon=1e-8$; results are similar for other graphs). Our findings demonstrate that: (1) for $0.01 \\leq \\alpha < 0.5$, **$R$ remains consistently at 1**, indicating our algorithm's robustness for larger $\\alpha$ values; (2) **when $\\alpha < 0.01$, $R$ exhibits a gradual increase with decreasing $\\alpha$, but crucially this growth follows a logarithmic scaling of $\\log(1/\\alpha)$** - substantially milder than the $1/\\alpha$ dependence. These empirical results validate the reasonableness of our treatment of $R$ in the complexity analysis while providing a more comprehensive characterization of its behavior across the full range of $\\alpha$ values.  \n\n**Q3.** How does the method perform against other methods from the literature e.g. Ref.[37] ?\n\n**A3.** Thank you for this important question regarding comparative performance. Regarding the comparison with Ref.[37]'s **ASPR** algorithm, we have included experimental comparisons in **Appendix C.3 (Figure 6)** due to space constraints in the main text. It should be noted that while ASPR maintains the desirable property of guaranteed monotonic decrease in the gradient's $\\ell_1$-norm, this advantage comes at the cost of requiring progressively more iterative points, which ultimately leads to reduced computational efficiency compared to our proposed method. The detailed comparative results demonstrate this trade-off between theoretical guarantees and practical performance.\n\n| Method       | α      | 1/α      | log(1/α) | R    |\n|-------------|--------|----------|----------|------|\n| AESP-LocAPPR | 1e-5   | 1.00e+5  | 11.51    | 2.83 |\n| AESP-LocAPPR | 5e-5   | 2.00e+4  | 9.90     | 2.52 |\n| AESP-LocAPPR | 1e-4   | 1.00e+4  | 9.21     | 2.43 |\n| AESP-LocAPPR | 5e-4   | 2.00e+3  | 7.60     | 1.99 |\n| AESP-LocAPPR | 1e-3   | 1.00e+3  | 6.91     | 1.59 |\n| AESP-LocAPPR | 2e-3   | 5.00e+2  | 6.21     | 1.34 |\n| AESP-LocAPPR | 5e-3   | 2.00e+2  | 5.30     | 1.17 |\n| AESP-LocAPPR | 7e-3   | 1.43e+2  | 4.96     | 1.00 |\n| AESP-LocAPPR | 2e-2   | 5.00e+1  | 3.91     | 1.00 |\n| AESP-LocAPPR | 4e-2   | 2.50e+1  | 3.22     | 1.00 |\n| AESP-LocAPPR | 5e-2   | 2.00e+1  | 3.00     | 1.00 |\n| AESP-LocAPPR | 6e-2   | 1.67e+1  | 2.81     | 1.00 |\n| AESP-LocAPPR | 8e-2   | 1.25e+1  | 2.53     | 1.00 |\n| AESP-LocAPPR | 1e-1   | 1.00e+1  | 2.30     | 1.00 |\n| AESP-LocAPPR | 2e-1   | 5.00e+0  | 1.61     | 1.00 |\n| AESP-LocAPPR | 3e-1   | 3.33e+0  | 1.20     | 1.00 |\n| AESP-LocAPPR | 4e-1   | 2.50e+0  | 0.92     | 1.00 |\n| AESP-LocAPPR | 4.5e-1 | 2.22e+0  | 0.80     | 1.00 |\n| AESP-LocAPPR | 4.9e-1 | 2.04e+0  | 0.71     | 1.00 |\n| AESP-LocGD   | 1e-5   | 1.00e+5  | 11.51    | 2.93 |\n| AESP-LocGD   | 5e-5   | 2.00e+4  | 9.90     | 2.57 |\n| AESP-LocGD   | 1e-4   | 1.00e+4  | 9.21     | 2.45 |\n| AESP-LocGD   | 5e-4   | 2.00e+3  | 7.60     | 1.88 |\n| AESP-LocGD   | 1e-3   | 1.00e+3  | 6.91     | 1.60 |\n| AESP-LocGD   | 2e-3   | 5.00e+2  | 6.21     | 1.38 |\n| AESP-LocGD   | 5e-3   | 2.00e+2  | 5.30     | 1.16 |\n| AESP-LocGD   | 7e-3   | 1.43e+2  | 4.96     | 1.00 |\n| AESP-LocGD   | 2e-2   | 5.00e+1  | 3.91     | 1.00 |\n| AESP-LocGD   | 4e-2   | 2.50e+1  | 3.22     | 1.00 |\n| AESP-LocGD   | 5e-2   | 2.00e+1  | 3.00     | 1.00 |\n| AESP-LocGD   | 6e-2   | 1.67e+1  | 2.81     | 1.00 |\n| AESP-LocGD   | 8e-2   | 1.25e+1  | 2.53     | 1.00 |\n| AESP-LocGD   | 1e-1   | 1.00e+1  | 2.30     | 1.00 |\n| AESP-LocGD   | 2e-1   | 5.00e+0  | 1.61     | 1.00 |\n| AESP-LocGD   | 3e-1   | 3.33e+0  | 1.20     | 1.00 |\n| AESP-LocGD   | 4e-1   | 2.50e+0  | 0.92     | 1.00 |\n| AESP-LocGD   | 4.5e-1 | 2.22e+0  | 0.80     | 1.00 |\n| AESP-LocGD   | 4.9e-1 | 2.04e+0  | 0.71     | 1.00 |"}]

Author rebuttal:

Meta-review: The authors describe for computing personalized PageRank where the restart is supported on one node.  The AESP algorithm is based on an accelerated inexact proximal operator with impressive empirical performance (in terms of number of operations; the experiments do not appear to discuss wall clock time) and scaling in the damping parameter of $O(R^2 \alpha^{-1/2} \epsilon^{-2})$ as opposed to the usual $O(\alpha^{-1} \epsilon^{-1})$ time required for competing methods.

The reviewers were all at least somewhat positive, but almost all pointed to two common concerns:

- The "constant" $R$ is not very well characterized.  The authors show that empirically it remains bounded and modest for the examples given, but there is not any real characterization in terms of graph properties.
- The improved scaling in the damping factor $\alpha$ comes at the cost of worse scaling with the sparsity tolerance $\epsilon$.

The authors acknowledge that these need further study.  Discussion was otherwise fairly terse, though three of the reviewers also suggested looking at other baselines in the comparison.

The personal PageRank problem is an interesting and useful one, and the proposed method appears to have interesting theoretical and empirical advantages, even with the limitations noted by the reviewers (who were all at least borderline positive).
Decision: Accept (poster)