2025-11-17T05:52:13.175509

Accelerated Evolving Set Processes for Local PageRank Computation

Huang, Luo, Xiao et al.
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/ε^2), \tilde{\mathcal{O}}(m)\}$ to obtain an $ε$-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α)$ such linear systems, where $α$ is the damping factor. When $1/ε^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}}\left(R^2 / (\sqrtαε^2)\right)$, 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.
academic

Accelerated Evolving Set Processes for Local PageRank Computation

基本信息

  • 论文ID: 2510.08010
  • 标题: Accelerated Evolving Set Processes for Local PageRank Computation
  • 作者: Binbin Huang, Baojian Zhou, Luo Luo, Deqing Yang, Yanghua Xiao (复旦大学)
  • 分类: cs.LG
  • 发表会议: 39th Conference on Neural Information Processing Systems (NeurIPS 2025)
  • 论文链接: https://arxiv.org/abs/2510.08010v2

摘要

本文提出了一个基于嵌套演化集合过程(nested evolving set processes)的新框架来加速个性化PageRank(PPR)计算。在每个阶段，采用局部化的非精确近似点迭代来解决简化的线性系统。研究表明，此类局部化方法的时间复杂度上界为min⁡{O~(R2/ε2),O~(m)}\min\{\tilde{\mathcal{O}}(R^2/ε^2), \tilde{\mathcal{O}}(m)\}以获得PPR向量的ε-近似，其中m表示图中边数，R是通过嵌套演化集合过程定义的常数。框架诱导的算法仅需求解O~(1/α)\tilde{\mathcal{O}}(1/\sqrt{α})个这样的线性系统，其中α是阻尼因子。当1/ε2≪m1/ε^2 \ll m时，这意味着存在一个算法能以O~(R2/(αε2))\tilde{\mathcal{O}}(R^2/(\sqrt{α}ε^2))的总时间复杂度计算PPR向量的ε-近似，且独立于底层图大小。

研究背景与动机

问题定义

个性化PageRank(PPR)向量π ∈ ℝⁿ定义为：

(I - (1-α)(I + AD⁻¹)/2)π = αeₛ

其中eₛ是对应源节点s的标准基向量，α ∈ (0,1)是阻尼因子，A和D分别是无向图G(V,E)的邻接矩阵和度矩阵。

研究动机

  1. 重要性：PPR是图分析的核心工具，广泛应用于局部聚类、扩散过程建模、图神经网络等领域
  2. 现有局限：
    • 标准方法如APPR时间复杂度为O(1/(αε))
    • 加速方法面临动量项破坏残差单调性的挑战
    • 现有加速方法可能访问整个图，导致O(m/√α)的时间复杂度
  3. 开放问题：是否存在时间复杂度依赖于1/√α而非1/α的局部加速方法

核心贡献

  1. AESP框架：提出了加速演化集合过程(AESP)框架，使用O~(1/α)\tilde{O}(1/\sqrt{α})个短演化集合过程而非单个长过程
  2. 理论保证：建立了O~(vol(St)/(αγt))\tilde{O}(\text{vol}(S_t)/(\sqrt{α}γ_t))的时间复杂度，匹配现有文献中的加速界限猜想
  3. 局部性保证：证明了vol(St)/γt\text{vol}(S_t)/γ_t的上界为min⁡{O(R2/ε2),2m}\min\{O(R^2/ε^2), 2m\}，当1/ε2≪m1/ε^2 \ll m时实现与图大小无关的复杂度
  4. 实验验证：在大规模真实图上验证了方法的有效性，展示了早期阶段的显著加速效果

方法详解

任务定义

给定精度参数ε，设计局部算法计算ε-近似π̂，满足∥D−1(π^−π)∥∞≤ε\|D^{-1}(π̂ - π)\|_∞ ≤ ε，同时避免访问整个图。

核心思想：嵌套演化集合过程

1. 问题重构

将线性系统重构为强凸优化问题：

min f(x) = (1/2)x⊤Qx - αx⊤D^(-1/2)b

其中Q = ((1+α)/2)I - ((1-α)/2)D^(-1/2)AD^(-1/2)，特征值λ(Q) ∈ α,1。

2. 嵌套ESP定义

在外循环迭代t，局部求解器M维护内循环迭代k上的活跃集合序列{S_t^(k)}_{k≥0}，更新仅限于活跃集合内的节点。

3. AESP更新规则

x^(t) = M(φ_t, y^(t-1), η, α, b, G)
y^(t) = x^(t) + β_t(x^(t) - x^(t-1))

其中β_t是动量权重，M是局部算子。

局部化非精确近似算子

LOCGD (Local Gradient Descent)

z_t^(k+1) = z_t^(k) - (2∇h_t(z_t^(k)) ∘ 1_{S_t^k})/(1 + α + 2η)

活跃节点集合：Stk={u:∣∇uht−1/2(zt(k))∣≥εt}S_t^k = \{u : |∇_u h_t^{-1/2}(z_t^{(k)})| ≥ ε_t\}

LOCAPPR (Local APPR)

对ui∈Stku_i ∈ S_t^k的坐标级更新：

z_t^(k_{i+1}) = z_t^(k_i) - (2∇h_t(z_t^{(k_i)}) ∘ 1_{u_i})/(1 + α + 2η)

技术创新点

  1. 单调性保持：通过求解条件数为常数的正则化PPR线性系统，保证D^{1/2}-缩放梯度的ℓ₁范数单调递减
  2. 局部性控制：引入常数R来界定嵌套ESP过程中梯度比率的有界性
  3. 加速与局部性平衡：在条件数1/α的依赖性和每轮时间复杂度O(R²/ε²)之间实现权衡

实验设置

数据集

实验使用19个真实世界图，规模从小型到超大型：

  • 中等规模：com-dblp (317K节点, 1M边)
  • 大规模：ogb-mag240m (244M节点, 1.7B边), ogbn-papers100M (111M节点, 1.6B边)
  • 其他：com-friendster, wiki-en21等

评价指标

  • 误差度量：log⁡∥D−1(π^−π)∥∞\log \|D^{-1}(π̂-π)\|_∞
  • 效率度量：操作次数、运行时间
  • 加速比：相对于基线方法的性能提升

对比方法

  • APPR：标准近似个性化PageRank算法
  • APPR-opt：使用最优步长的APPR
  • LOCGD：局部梯度下降
  • ASPR：加速稀疏个性化PageRank
  • FISTA：快速迭代收缩阈值算法

实现细节

  • 阻尼因子：α = 0.01, 0.1
  • 精度阈值：ε = 10⁻⁶
  • 随机选择5个源节点进行测试
  • Python实现，使用numba加速

实验结果

主要结果

大规模图性能

在四个大规模图(ogb-mag240m, ogbn-papers100M, com-friendster, wiki-en21)上：

  • AESP-LOCAPPR表现最佳，得益于在线坐标更新
  • 早期加速：AESP方法在早期阶段实现比基线方法更快的收敛
  • 操作数减少：相比APPR减少2-10倍操作数

α依赖性分析

当α较小时，AESP显著加速标准局部方法：

  • α ∈ 10⁻³, 10⁻¹范围内测试
  • 加速比随α减小而增大，验证了√α依赖性
  • 运行时间和操作数均显著降低

初始化策略比较

三种初始化策略z_t^(0)的比较：

  1. 冷启动：z_t^(0) = 0
  2. 前一估计：z_t^(0) = x^(t-1)
  3. 动量初始化：z_t^(0) = y^(t-1) (推荐)

动量初始化策略表现最佳，需要最少的外循环迭代次数。

消融实验

常数R的分析

  • 在19个图上R保持为小常数(1.0-1.4)
  • R对图大小和条件数不敏感
  • 验证了理论分析中R有界假设的合理性

vol(S_t)/γ_t比率分析

实验验证了vol(St)/γt≤min⁡{Ct0/εt,2m}\text{vol}(S_t)/γ_t ≤ \min\{C_t^0/ε_t, 2m\}的理论界限。

相关工作

PPR计算方法

  • 迭代方法：共轭梯度法、Chebyshev方法，复杂度O(m/√α)
  • 局部方法：APPR (O(1/(αε))), 变分方法 (O(1/((α+μ²)ε)))
  • 加速尝试：FISTA、线性耦合等破坏单调性，无法保证局部性

演化集合过程

  • Morris和Peres提出的概念，用于分析混合时间
  • Zhou等人的局部化Chebyshev方法，但缺乏收敛保证

加速优化

  • Catalyst框架：非精确加速近似点方法
  • 本文将其适配到局部方法，保持单调性

结论与讨论

主要结论

  1. 理论突破：首次实现了PPR计算的可证明局部加速，时间复杂度从O(1/α)改进到O(1/√α)
  2. 实用性：当ε ≥ 1/√m时，算法复杂度与图大小无关
  3. 通用性：框架可扩展到变分形式和其他相关问题

局限性

  1. 常数R界限：无法用图大小或输入参数普遍界定R
  2. ε²依赖性：当ε < 1/√m时，局部界限退化为O(m/√α)
  3. 理论与实践差距：ε_t的保守估计可能导致次优界限

未来方向

  1. 改进界限：探索是否能达到猜想的O(1/(√αε))复杂度
  2. 消除R依赖：通过约束或自适应重启消除常数R
  3. 扩展应用：将技术应用到双向PPR、单源PPR估计等问题

深度评价

优点

  1. 理论贡献显著：解决了文献中的开放猜想，建立了严格的理论保证
  2. 方法创新性强：巧妙结合Catalyst框架与局部演化集合过程
  3. 实验充分：在19个不同规模图上验证，从小型到超大型图
  4. 写作清晰：数学推导严谨，算法描述详细

不足

  1. 实用性限制：当ε很小时优势不明显，R的界定问题影响实际应用
  2. 实现复杂度：嵌套结构和参数调节增加了实现难度
  3. 对比不够全面：缺少与最新加速方法的详细比较

影响力

  1. 学术价值：为图算法加速提供了新思路，理论意义重大
  2. 实用价值：在大规模图分析、推荐系统等领域有应用潜力
  3. 可复现性：代码公开，实验设置详细

适用场景

  1. 大规模图分析：特别是当精度要求不极高时(ε ≥ 1/√m)
  2. 实时推荐系统：需要快速计算局部重要性分数
  3. 图神经网络：作为预处理步骤计算节点重要性

参考文献

本文引用了52篇相关文献，涵盖了PPR计算、加速优化、局部算法等多个领域的重要工作，为研究提供了坚实的理论基础。

总体评价：这是一篇高质量的理论与实践并重的论文，在PPR计算加速这一重要问题上取得了显著进展。虽然存在一些理论局限，但其创新性和实用性使其成为该领域的重要贡献。