一句话总结

复旦大学的研究者提出一种用于正则化个性化PageRank的确定性局部算法，通过正则化延拓和受度缩放盒子与质量上限约束的加速校正，在 $\bar{O}(1 / (\rho \sqrt{\alpha}))$Oˉ(1/(ρα​)) 的工作量内达到加性精度 $\varepsilon_{\text{obj}}$εobj​，无需SDD预言机或图全局预处理；同时给出一个期望工作量为 $\tilde{O}(V_* \min\{k_*, \alpha^{-1/2}\})$O~(V∗​min{k∗​,α−1/2}) 的随机化变体。

核心贡献

• 一种用于正则化个性化PageRank的确定性局部算法，以 $\widetilde{O}(1/(\rho\sqrt{\alpha}))$O(1/(ρα​)) 的工作量达到加性目标误差 $\varepsilon_{\text{obj}}$εobj​，其中 $\alpha$α 为传送参数，$\rho$ρ 为正则化强度，精度仅以多对数形式出现；该方法无需图全局预处理或预先提供的解支撑集，并包含适用于有理输入的有限算术实现。
• 一种随机化局部算法，利用支撑集安全的阈值批次和认证的SDD求解，达到期望工作量 $\widetilde{O}(V_* \min\{k_*, \alpha^{-1/2}\})$O(V∗​min{k∗​,α−1/2})，其中 $k_*$k∗​ 和 $V_*$V∗​ 分别为最优支撑集的基数和度体积，在无需SDD预言机的情况下匹配了同期工作的随机化规模。
• 两种算法均通过显式的正则化偏差与目标误差转换，隐含地给出了一种加速的度归一化PPR近似，而确定性方法的主要区别在于仅以多对数开销实现确定性局部加速。

引言

局部个性化PageRank算法无需访问整个图即可计算稀疏相关性分数，但在保持局部性的同时加速它们具有挑战性。先前的工作要么使用基于动量的更新，可能激活远在最优支撑集之外的顶点并引发高度数扫描，要么求解一系列受限问题，其代价与支撑集发现次数相乘。作者提出了两种用于正则化个性化PageRank的新算法，克服了这些障碍。一种确定性延拓方法以 $\widetilde{O}(1/(\rho\sqrt{\alpha}))$O(1/(ρα​)) 的加速工作量界实现，仅有多对数开销，且无需近线性SDD预言机。一种随机化阈值批处理方法达到 $\widetilde{O}(\min\{1/\rho^2, 1/(\rho\sqrt{\alpha})\})$O(min{1/ρ2,1/(ρα​)}) 的期望工作量界，同时适应最优支撑集大小，并提供Las Vegas认证。两种结果均转化为具有相同加速复杂度的度归一化PPR近似。

方法

作者将问题形式化为无向无权图上的正则化PageRank（RPPR）目标。给定种子分布 $\boldsymbol{s}$s（通常为点源 $\boldsymbol{e}_\nu$eν​）、传送参数 $\alpha \in (0,1]$α∈(0,1] 和正则化强度 $\rho>0$ρ>0，RPPR问题最小化

其中 $\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，$\boldsymbol{A},\boldsymbol{D}$A,D 分别为邻接矩阵和度矩阵。唯一极小点 $\boldsymbol{x}_\rho^*$xρ∗​ 给出一个稀疏向量，其支撑集体积至多为 $1/\rho$1/ρ。标准个性化PageRank（PPR）向量为 $\boldsymbol{\pi} = \boldsymbol{D}^{1/2}\boldsymbol{x}_0^*$π=D1/2x0∗​，其中 $\boldsymbol{x}_0^* = \boldsymbol{Q}^{-1}\boldsymbol{b}$x0∗​=Q−1b 为无正则化解。精度按目标间隙 $F_\rho(\widehat{\boldsymbol{x}}) - F_\rho(\boldsymbol{x}_\rho^*) \le \varepsilon_{\mathrm{obj}}$Fρ​(x)−Fρ​(xρ∗​)≤εobj​ 或度归一化PPR误差 $\|\boldsymbol{D}^{-1/2}(\widehat{\boldsymbol{x}} - \boldsymbol{x}_0^*)\|_\infty \le \varepsilon_{\mathrm{ppr}}$∥D−1/2(x−x0∗​)∥∞​≤εppr​ 度量。算法在局部访问模型下运行：它们仅从种子标签开始，可查询已发现顶点的度数和邻接表；总工作量计入所有邻接检查、度数查询、算术运算和输出字。

方法的核心由两个互补的局部算法组成，两者均产生一个非负向量 $\widehat{\boldsymbol{x}}$x，满足RPPR目标容差且支撑于最优支撑集内。确定性算法采用延拓策略，在各阶段将正则化参数减半。在每个阶段，在显式凸集 $\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​} 上求解一个扩散源校正问题，其中 $\boldsymbol{\omega} = \boldsymbol{D}^{1/2}\boldsymbol{1}$ω=D1/21，$m_r$mr​ 为残差质量。一个由曲率 $\mu_c = \theta^2$μc​=θ2 参数化的加速递推，其中 $\theta$θ 选择使得 $\theta^2 \le \alpha$θ2≤α，迭代

其中 $\chi = 1-\theta$χ=1−θ，$\lambda_r = \alpha r$λr​=αr，$\boldsymbol{h}$h 为当前残差源。到 $\mathcal{K}_r$Kr​ 的投影通过关键密度的平衡树上的有限阈值搜索精确计算，使得稀疏更新仅触及动态支撑集及其边界。一项关键的分析贡献是累积动态体积界：一个阶段内所有投影迭代的总度体积为 $O(K/r)$O(K/r)，其中 $K$K 为迭代次数。结合加速收敛（$K = O(\alpha^{-1/2}\log(1/\tau))$K=O(α−1/2log(1/τ))），每阶段总工作量为 $\widetilde{O}(1/(r\sqrt{\alpha}))$O(1/(rα​))。对减半调度求和得到总体确定性工作量 $\widetilde{O}(1/(\rho\sqrt{\alpha}))$O(1/(ρα​))。

随机化算法采用不同的思路：通过安全的活动集扩展逐步构建最优支撑集。从种子开始，反复在当前活动集 $\mathcal{U}$U 上求解受限线性系统 $\boldsymbol{x}^{\mathcal{U}} = \boldsymbol{Q}_{\mathcal{U}\mathcal{U}}^{-1}(\boldsymbol{c}_\rho)_{\mathcal{U}}$xU=QUU−1​(cρ​)U​（其中 $\boldsymbol{c}_\rho = \boldsymbol{b} - \alpha\rho\boldsymbol{\omega}$cρ​=b−αρω），并检查边界松弛。任何具有足够负松弛的边界顶点保证属于最优支撑集（定理7），并被批量添加。松弛条件是局部的：对于 $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​，仅需扫描 $\mathcal{U}$U 的邻接。一个局部目标证书（引理9）利用KKT次梯度，从活动集及其边界界定目标间隙，无需整个图。

为限制批次扩展次数，算法采用阈值 $\vartheta$ϑ：仅当其精确残差超过 $\vartheta$ϑ 时才接纳顶点，而所有剩余最优支撑集坐标的残差至多为 $\vartheta$ϑ。谱深度分析（定理20）表明，经过 $J = O(\alpha^{-1/2}\log(1/\varepsilon_{\mathrm{obj}}))$J=O(α−1/2log(1/εobj​)) 个批次后，在已发现面上的受限解达到所需的目标精度。该分析利用最优支撑集的分块Cholesky分解和切比雪夫逼近，将快速衰减的种子贡献与阈值引起的误差分开。每个面求解由随机化近线性SDD求解器在提供的主子矩阵上执行，并通过独立重试控制失败概率。期望总工作量为 $\widetilde{O}(V_* \min\{k_*, \alpha^{-1/2}\})$O(V∗​min{k∗​,α−1/2})，其中 $V_*$V∗​ 和 $k_*$k∗​ 为最优支撑集的体积和大小；在最坏情况下上界为 $\widetilde{O}(1/(\rho\sqrt{\alpha}))$O(1/(ρα​))。算法还可返回一个子解，满足 $\boldsymbol{0} \le \widehat{\boldsymbol{x}} \le \boldsymbol{x}_\rho^*$0≤x≤xρ∗​ 和 $\boldsymbol{0} \le \boldsymbol{b} - \boldsymbol{Q}\widehat{\boldsymbol{x}} \le 2\alpha\rho\boldsymbol{\omega}$0≤b−Qx≤2αρω。

对于最终的PPR任务，采用两阶段完成。首先，任一算法以 $\rho = \varepsilon_{\mathrm{ppr}}/3$ρ=εppr​/3 计算一个RPPR解，产生一个近似支撑集 $\mathcal{U}$U，其体积至多为 $3/\varepsilon_{\mathrm{ppr}}$3/εppr​。然后，在该支撑集上以所需的欧几里得精度求解精确的主PPR系统 $\boldsymbol{Q}_{\mathcal{U}\mathcal{U}}\boldsymbol{u}_{\mathcal{U}} = \boldsymbol{b}_{\mathcal{U}}$QUU​uU​=bU​。由于该支撑集已捕获基本质量，所得向量与真实PPR之间的度归一化误差被 $\varepsilon_{\mathrm{ppr}}$εppr​ 界定。第二阶段可使用确定性预处理共轭梯度或随机化SDD求解器，两者运行时间均为 $\widetilde{O}(\mathrm{vol}(\mathcal{U})/\sqrt{\alpha})$O(vol(U)/α​)，保持总体 $\widetilde{O}(1/(\varepsilon_{\mathrm{ppr}}\sqrt{\alpha}))$O(1/(εppr​α​)) 的工作量界。所有步骤都是局部的，无需全局预处理，并明确计入每次邻接检查和算术运算。

实验

本文开发了用于正则化PageRank（RPPR）和个性化PageRank（PPR）的确定性和随机化局部算法，仅需局部图访问且无需预处理。确定性方法在 $\widetilde{\mathcal{O}}(1/(\rho\sqrt{\alpha}))$O(1/(ρα​)) 工作量的保证下达到目标间隙，而随机化Las Vegas算法适应支撑集大小和体积，达到期望工作量 $\widetilde{\mathcal{O}}(V_* \min\{k_*, \alpha^{-1/2}\})$O(V∗​min{k∗​,α−1/2})。两种方法均产生满足语义PPR精度的稀疏输出，并可生成ACL兼容的残差证书或用于后续线性系统求解的近似支撑集包络，所有支撑集接纳均被确定性认证。

比较展示了局部RPPR算法如何在工作量与输出保证之间权衡。早期方法随支撑集大小、体积或内部非零元规模缩放，而新算法1达到了与支撑集无关的界 $\widetilde{O}(1/(\rho\sqrt{\alpha}))$O(1/(ρα​))，算法2在期望上匹配了最佳的加速活动集界，并以确定性延拓定理为支撑。算法1是唯一工作量界 $\widetilde{O}(1/(\rho\sqrt{\alpha}))$O(1/(ρα​)) 不依赖于最优支撑集大小、体积或内部非零元的方法，与所有先前算法形成对比。算法2达到了与加速活动集相同的 $\widetilde{O}(V_* \min\{k_*, \alpha^{-1/2}\})$O(V∗​min{k∗​,α−1/2}) 保证，但作为期望界而非高概率界，本文的主要区别在于确定性延拓证明。

该评估从工作量与输出保证的角度比较局部RPPR算法。算法1作为唯一工作量界不依赖于最优支撑集大小、体积或内部非零元的方法脱颖而出，实现了与支撑集无关的保证。算法2在期望上匹配了最佳的加速活动集界，其关键贡献在于确定性延拓证明而非高概率分析。