One-sentence Summary

Researchers from Fudan University propose a deterministic local algorithm for regularized personalized PageRank achieving additive accuracy $\varepsilon_{\text{obj}}$εobj​ in $\bar{O}(1 / (\rho \sqrt{\alpha}))$Oˉ(1/(ρα​)) work via regularization continuation and accelerated corrections constrained by a degree-scaled box and mass cap, without SDD oracles or graph-wide preprocessing, and a randomized variant with expected work $\tilde{O}(V_* \min\{k_*, \alpha^{-1/2}\})$O~(V∗​min{k∗​,α−1/2}).

Key Contributions

• A deterministic local algorithm for regularized personalized PageRank achieves additive objective error ε_obj with work Ō(1/(ρ√α)), where α is the teleportation parameter and ρ the regularizer, and the accuracy enters only polylogarithmically; the method requires no graph-wide preprocessing or supplied solution support and includes a bounded-arithmetic implementation for rational inputs.
• A randomized local algorithm uses support-safe threshold batches and certified SDD solves to achieve expected work Õ(V_* min{k_, α^{-1/2}}), where k_ and V_* are the optimal support's cardinality and degree volume, matching the randomized scale of concurrent work without an SDD oracle.
• Both algorithms imply an accelerated degree-normalized PPR approximation through an explicit regularization-bias and objective-error conversion, and the deterministic method provides the principal distinction of deterministic local acceleration with only polylogarithmic overhead.

Introduction

Local personalized PageRank algorithms compute sparse relevance scores without accessing the whole graph, but accelerating them while preserving locality is challenging. Prior work either uses momentum-based updates that can activate vertices far outside the optimal support and incur high-degree scans, or solves a sequence of restricted problems whose cost multiplies with the number of support discoveries. The authors present two new algorithms for regularized personalized PageRank that overcome these obstacles. A deterministic continuation method achieves the accelerated work bound of Õ(1/(ρ√α)) with only polylogarithmic overhead and no need for a nearly-linear SDD oracle. A randomized threshold-batching method attains an expected work bound of Õ(min{1/ρ², 1/(ρ√α)}), adapting to the optimal support size while also providing a Las Vegas certification. Both results translate into a degree-normalized PPR approximation with the same accelerated complexity.

Method

The authors formulate the problem as a regularized PageRank (RPPR) objective on an unweighted, undirected graph. Given a seed distribution $\boldsymbol{s}$s (typically a point source $\boldsymbol{e}_\nu$eν​), a teleportation parameter $\alpha \in (0,1]$α∈(0,1], and a regularization strength $\rho>0$ρ>0, the RPPR problem minimizes

where $\boldsymbol{Q} = \frac{1+\alpha}{2}\boldsymbol{I} - \frac{1-\alpha}{2}\boldsymbol{D}^{-1/2}\boldsymbol{A}\boldsymbol{D}^{-1/2}$Q=21+α​I−21−α​D−1/2AD−1/2, $\boldsymbol{b} = \alpha \boldsymbol{D}^{-1/2}\boldsymbol{s}$b=αD−1/2s, and $\boldsymbol{A},\boldsymbol{D}$A,D are the adjacency and degree matrices. The unique minimizer $\boldsymbol{x}_\rho^*$xρ∗​ yields a sparse vector whose support volume is at most $1/\rho$1/ρ. The standard personalized PageRank (PPR) vector is $\boldsymbol{\pi} = \boldsymbol{D}^{1/2}\boldsymbol{x}_0^*$π=D1/2x0∗​, where $\boldsymbol{x}_0^* = \boldsymbol{Q}^{-1}\boldsymbol{b}$x0∗​=Q−1b is the unregularized solution. Accuracy is measured either in objective gap $F_\rho(\widehat{\boldsymbol{x}}) - F_\rho(\boldsymbol{x}_\rho^*) \le \varepsilon_{\mathrm{obj}}$Fρ​(x)−Fρ​(xρ∗​)≤εobj​ or in degree-normalized PPR error $\|\boldsymbol{D}^{-1/2}(\widehat{\boldsymbol{x}} - \boldsymbol{x}_0^*)\|_\infty \le \varepsilon_{\mathrm{ppr}}$∥D−1/2(x−x0∗​)∥∞​≤εppr​. The algorithms operate under a local access model: they start only with the seed label and can query degrees and adjacency lists of discovered vertices; total work counts all adjacency inspections, degree queries, arithmetic operations, and output words.

The core of the method consists of two complementary local algorithms, both producing a nonnegative vector $\widehat{\boldsymbol{x}}$x satisfying the RPPR objective tolerance and supported inside the optimal support. The deterministic algorithm uses a continuation strategy that halves the regularization parameter across stages. At each stage, a diffuse-source correction problem is solved on an explicit convex set $\mathcal{K}_r = \{\boldsymbol{u}: \boldsymbol{0} \le \boldsymbol{u} \le 4r\boldsymbol{\omega},\; \boldsymbol{\omega}^\top\boldsymbol{u} \le m_r\}$Kr​={u:0≤u≤4rω,ω⊤u≤mr​}, where $\boldsymbol{\omega} = \boldsymbol{D}^{1/2}\boldsymbol{1}$ω=D1/21 and $m_r$mr​ is the residual mass. An accelerated recurrence, parameterized by a curvature $\mu_c = \theta^2$μc​=θ2 with $\theta$θ chosen so that $\theta^2 \le \alpha$θ2≤α, iterates

where $\chi = 1-\theta$χ=1−θ, $\lambda_r = \alpha r$λr​=αr, and $\boldsymbol{h}$h is the current residual source. The projection onto $\mathcal{K}_r$Kr​ is computed exactly via a finite threshold search on a balanced tree of key densities, enabling sparse updates that touch only the kinetic support and its boundary. A key analytical contribution is a cumulative kinetic volume bound: the total degree volume of all projected iterates over a stage is $O(K/r)$O(K/r), where $K$K is the number of iterations. Combined with accelerated convergence ($K = O(\alpha^{-1/2}\log(1/\tau))$K=O(α−1/2log(1/τ))), the total work per stage is $\widetilde{O}(1/(r\sqrt{\alpha}))$O(1/(rα​)). Summing over the halving schedule gives the overall deterministic work $\widetilde{O}(1/(\rho\sqrt{\alpha}))$O(1/(ρα​)).

The randomized algorithm adopts a different philosophy: it builds the optimal support incrementally through safe active-set expansion. Starting from the seed, it repeatedly solves the restricted linear system $\boldsymbol{x}^{\mathcal{U}} = \boldsymbol{Q}_{\mathcal{U}\mathcal{U}}^{-1}(\boldsymbol{c}_\rho)_{\mathcal{U}}$xU=QUU−1​(cρ​)U​ on the current active set $\mathcal{U}$U (where $\boldsymbol{c}_\rho = \boldsymbol{b} - \alpha\rho\boldsymbol{\omega}$cρ​=b−αρω) and examines the boundary slacks. Any boundary vertex with a sufficiently negative slack is guaranteed to belong to the optimal support (Theorem 7) and is added in a batch. The slack condition is local: for $j \notin \mathcal{U}$j∈/U, $w_j^{\mathcal{U}}/\sqrt{d_j} = \alpha\rho - \frac{1-\alpha}{2d_j}\sum_{i\in\mathcal{N}(j)\cap\mathcal{U}} y_i$wjU​/dj​​=αρ−2dj​1−α​∑i∈N(j)∩U​yi​, requiring only adjacency scans of $\mathcal{U}$U. A local objective certificate (Lemma 9) uses the KKT subgradient to bound the objective gap from the active set and its boundary, without needing the whole graph.

To limit the number of batch expansions, the algorithm employs a threshold $\vartheta$ϑ: a vertex is admitted only if its exact residual exceeds $\vartheta$ϑ, while all remaining optimal support coordinates have residual at most $\vartheta$ϑ. A spectral depth analysis (Theorem 20) shows that after $J = O(\alpha^{-1/2}\log(1/\varepsilon_{\mathrm{obj}}))$J=O(α−1/2log(1/εobj​)) batches, the restricted solution on the discovered face achieves the desired objective accuracy. The analysis uses a block Cholesky decomposition of the optimal support and Chebyshev approximation to separate a rapidly decaying seed contribution from a threshold-induced error. Each face solve is performed by a randomized nearly-linear SDD solver on the supplied principal submatrix, with independent retries to control failure probability. The expected total work is $\widetilde{O}(V_* \min\{k_*, \alpha^{-1/2}\})$O(V∗​min{k∗​,α−1/2}), where $V_*$V∗​ and $k_*$k∗​ are the volume and size of the optimal support; this is bounded above by $\widetilde{O}(1/(\rho\sqrt{\alpha}))$O(1/(ρα​)) in the worst case. The algorithm can also return a subsolution satisfying $\boldsymbol{0} \le \widehat{\boldsymbol{x}} \le \boldsymbol{x}_\rho^*$0≤x≤xρ∗​ and $\boldsymbol{0} \le \boldsymbol{b} - \boldsymbol{Q}\widehat{\boldsymbol{x}} \le 2\alpha\rho\boldsymbol{\omega}$0≤b−Qx≤2αρω.

For the final PPR task, a two-stage completion is used. First, either algorithm computes an RPPR solution with $\rho = \varepsilon_{\mathrm{ppr}}/3$ρ=εppr​/3, yielding an approximate support $\mathcal{U}$U whose volume is at most $3/\varepsilon_{\mathrm{ppr}}$3/εppr​. Then the exact principal PPR system $\boldsymbol{Q}_{\mathcal{U}\mathcal{U}}\boldsymbol{u}_{\mathcal{U}} = \boldsymbol{b}_{\mathcal{U}}$QUU​uU​=bU​ is solved on that support to the required Euclidean accuracy. Because the support already captures the essential mass, the degree-normalized error between the resulting vector and the true PPR is bounded by $\varepsilon_{\mathrm{ppr}}$εppr​. The second stage can use deterministic preconditioned conjugate gradient or a randomized SDD solver, both running in time $\widetilde{O}(\mathrm{vol}(\mathcal{U})/\sqrt{\alpha})$O(vol(U)/α​), preserving the overall $\widetilde{O}(1/(\varepsilon_{\mathrm{ppr}}\sqrt{\alpha}))$O(1/(εppr​α​)) work bound. All steps are local, require no global preprocessing, and count every adjacency inspection and arithmetic operation explicitly.

Experiment

The paper develops deterministic and randomized local algorithms for regularized PageRank (RPPR) and personalized PageRank (PPR) that operate with only local graph access and no preprocessing. The deterministic method guarantees an objective gap within $\widetilde{\mathcal{O}}(1/(\rho\sqrt{\alpha}))$O(1/(ρα​)) work, while the randomized Las Vegas algorithm adapts to the support size and volume, achieving expected work $\widetilde{\mathcal{O}}(V_* \min\{k_*, \alpha^{-1/2}\})$O(V∗​min{k∗​,α−1/2}). Both approaches produce sparse outputs that satisfy semantic PPR accuracy and can generate ACL-compatible residual certificates or approximate support envelopes for subsequent linear-system solves, with all support admissions deterministically certified.

The comparison shows how local RPPR algorithms trade off work and output guarantees. Earlier methods scale with support size, volume, or internal nonzeros, while the new Algorithm 1 achieves a support-independent bound of Õ(1/(ρ√α)), and Algorithm 2 matches the best accelerated active set bound in expectation, backed by a deterministic continuation theorem. Algorithm 1 is the only method whose work bound Õ(1/(ρ√α)) does not depend on the optimal support size, volume, or internal nonzeros, in contrast to all prior algorithms. Algorithm 2 attains the same Õ(V_* min{k_*, α^{-1/2}}) guarantee as the accelerated active set, but as an expected bound rather than with high probability, and the paper's main distinction is a deterministic continuation proof.

The evaluation compares local RPPR algorithms in terms of their work and output guarantees. Algorithm 1 stands out as the only method whose work bound does not depend on optimal support size, volume, or internal nonzeros, achieving a support-independent guarantee. Algorithm 2 matches the best accelerated active set bound in expectation, with the key contribution being a deterministic continuation proof rather than a high-probability analysis.