提出新方法加速个性化网页排名计算，显著提升效率。
Accelerated Evolving Set Processes for Local PageRank Computation
- 用局部近似点迭代求解简化线性系统，分阶段优化计算。
- 理论证明时间复杂度可低至 $\tilde{\mathcal{O}}(R^2 / (\sqrtαε^2))$，与图大小无关。
- 适用于大规模图上快速计算个性化排名，尤其适合早期收敛场景。
本文提出一种基于嵌套演化集过程的新框架，用于加速个性化PageRank（PPR）的计算。在每一步中，采用局部不精确的近似点迭代求解简化线性系统。我们证明该局部方法的时间复杂度上界为 $\min\{\tilde{\mathcal{O}}(R^2/ε^2), \tilde{\mathcal{O}}(m)\}$，其中 $m$ 为图中边数，$R$ 是由嵌套演化集过程定义的常数。此外，本框架诱导的算法仅需求解 $\tilde{\mathcal{O}}(1/\sqrtα)$ 个此类线性系统，其中 $α$ 为阻尼因子。当 $1/ε^2 \ll m$ 时，存在一种算法可在 $\tilde{\mathcal{O}}(R^2 / (\sqrtαε^2))$ 的总时间复杂度内获得 $ε$-近似 PPR 向量，且与底层图规模无关。该结果解决了现有文献中的一个开放猜想。真实图数据上的实验验证了方法的高效性，表明其在早期阶段即实现显著收敛。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。