我们提出了一种局部算法，能够在高概率下计算满足 Andersen、Chung 与 Lang (ACL; Internet Math. 2007) 定义的 $\varepsilon$‑近似 PageRank 向量，跳转参数为 $\alpha$，其运行时间为 $\widetilde{O}\bigl(1 / (\sqrt{\alpha}\,\varepsilon)\bigr)$，显著快于原始局部推送方法的 $O\bigl(1/(\alpha\varepsilon)\bigr)$。
该方法同样适用于 $\ell_1$ 正则化的 PageRank 问题，运行时间提升至 $\widetilde{O}\bigl(1 / (\sqrt{\alpha}\,\rho)\bigr)$，其中 $\rho$ 为正则化系数，解答了 Fountoulakis 与 Yang (COLT 2022) 提出的未解问题。
更快的原语可以加速依赖局部推送的多类图算法。例如，将其直接嵌入 ACL 框架即可得到更快的基于 PageRank 的局部图聚类；我们还构造了若干归约，使得有效电阻估计等任务的算法亦可受益。
技术核心在于对 Wei 与 Yang（2026）提出的主动集方法的改进进行势函数分析。算法在当前活跃节点集合上反复调用 SDD 求解器并扩展集合。我们将相邻扩展块的势函数下降关联起来，证明扩展次数被上界为 $\widetilde{O}\bigl(1/\sqrt{\alpha}\bigr)$。
点评：该工作通过潜在函数技巧将局部推送的复杂度从 $1/(\alpha\varepsilon)$ 降至 $1/(\sqrt{\alpha}\varepsilon)$，为大规模图的局部计算提供了更实用的工具，并打开了在正则化 PageRank 上进一步优化的可能性。