当前位置：首页 > article >正文

论文学习_Efficient Algorithms for Personalized PageRank Computation: A Survey

article 2024/11/15 6:43:43

论文名称	发表时间	发表期刊	期刊等级	研究单位
Efficient Algorithms for Personalized PageRank Computation: A Survey	2024年	IEEE TKDE	CCF A	中国人民大学

1. 引言

Graph 是一个广泛应用的抽象数据类型，可以用来建模现实世界中的各种信息。Personalized PageRank（PPR）是 Google 著名的 PageRank 中心性的直接变体，是一种常用的图中节点邻近度度量方法。给定源节点 s 和目标节点 t，PPR 值 πs(t) 用来定量衡量目标节点 t 在源节点 s 视角下的重要性。另一方面，πs(t) 也反映了源节点 s 在目标节点 t 视角下的重要性，因此，它本质上衡量了 s 和 t 之间的相互显著性。节点 t 的 PageRank 中心性表示为 π(t)，它等于所有源节点 s 上 πs(t) 的平均值，可以看作是广义 PPR 的一种特殊形式。PPR 的引出

尽管 PageRank 和个性化 PageRank（PPR）的开创性论文最初主要探讨了如何利用它们客观、机械地对网页进行评级，但近年来，它们在网络之外的应用也得到了广泛扩展。事实上，由于其简单性和深远的影响，PageRank 在 2008 年被评为数据挖掘领域十大经典算法之一。以下是 PPR 应用的三个代表性实例：局部聚类、节点嵌入和图神经网络。更多的应用可以参考 Gleich 的调查。PPR 的应用

局部聚类：作为传统的图挖掘任务，局部图聚类旨在通过仅分析图的局部区域来识别指定节点周围连接紧密的簇。一个著名的算法是 Anderson 提出的 PageRank-Nibble，该算法利用本地推送方法计算个性化 PageRank（PPR），能够有效地发现局部集群，并且具有强大的理论保障。在 PageRank-Nibble 之后，出现了一系列基于 PPR 或其扩展来计算局部集群的最新研究成果，例如 MAPPR、TEA 等。
节点嵌入：节点嵌入方法旨在学习图中节点的低维表示，同时尽可能保留它们之间的相似性。这些方法通常需要首先计算节点的邻近度度量，其中许多方法选择使用 PPR 值，例如 HOPE、APP 以及 VERSE 等。
图神经网络：近年来，图神经网络（GNN）推动了图机器学习领域的爆炸式发展。作为节点邻近度的基本度量，个性化 PageRank（PPR）在设计各种 GNN，尤其是可扩展的 GNN 中，发挥了重要作用。例如，APPNP 和 PPRGo 将近似 PPR 应用于 GNN，从而提高了它们的效率和可扩展性；GBP 和 AGP 则扩展了 PPR 的概念，提出了有效近似图传播的新方法。

尽管 PPR 在许多领域有着丰富的应用，但在某些情况下，PageRank 和 PPR 的计算仍然是瓶颈，特别是当图变得越来越庞大时。早在 2002 年，某些图就已经包含了 27 亿个节点，PageRank 的计算因此被称为“世界上最大的矩阵计算”。此外，计算 PageRank 和 PPR 的复杂性也具有重要的理论意义。过去几十年，这些挑战激发了大量关于如何在大规模图上有效计算 PPR 的研究。PPR 现存问题

基于这些研究，已有多项关于 PPR 算法的调查，例如 Berkhin 在 2005 年的早期调查、Chung 在 2014 年的简要调查，以及 Park 等人于 2019 年的最新调查。然而，这些研究并未对计算 PPR 的基本技术进行详细总结，也没有从理论角度全面回顾近年来的 PPR 算法。与之相比，本文旨在填补这一空白，通过深入研究五种基础技术，并根据查询类型对众多算法进行系统分类。论文对基本技术进行了理论分析，指出了它们的优缺点，并总结了所调查算法的方法和贡献。此外，为了应对处理不断变化的图形、开发新的计算环境等新兴需求，论文还包括了针对这些特殊设置量身定制的最新 PPR 算法部分。论文主要关注 PPR 的邻近度度量，但论文也涵盖了许多用于 PageRank 计算的相关算法。主要研究内容

2. 基础知识

2.1 图基础

考虑一个有向或无向图 $G=(V,E)$ ，其中 $\left | V \right |=n$ 是节点数， $\left | E \right |=n$ 是边数，并且假设节点集合 $V$ 中的节点按照某种顺序编号为 $v1,v2,\cdots ,vn$ ，下面列出一些 $G$ 的基本概念：

邻居节点与度：对于一个节点 $v \in V_v$ ，考虑用 $\mathcal{N}_{\text{in}}(v) = \{ u \mid (u, v) \in E \}$ 表示 $v$ 的入邻居集合，并用 $d_{\text{in}}(v) = |\mathcal{N}_{\text{in}}(v)|$ 表示 $v$ 的入度。类似地，用 $\mathcal{N}_{\text{out}}(v) = \{ u \mid (v, u) \in E \}$ 和 $d_{\text{out}}(v) = |\mathcal{N}_{\text{out}}(v)|$ 表示 $v$ 的出邻居集合与出度。对于无向图，用 $d(v)$ 表示节点 $v$ 的度。

图相关矩阵：图 $G$ 的邻接矩阵 $\mathbf{A}$ 是一个 $n \times n$ 的矩阵，其第 $(i, j)$ 个元素为 $1\{(v_i, v_j) \in E\}$ ，其中 $1\{\}$ 表示指示函数。图 $G$ 的度矩阵 $\mathbf{D}$ 是一个 $n \times n$ 的对角矩阵，其第 $i$ 个对角元素等于 $d_{\text{out}}(v_i)$ 。图 $G$ 的转移矩阵定义为 $\mathbf{P} = \mathbf{A}^\top \mathbf{D}^{-1}$ 。为了确保 $\mathbf{P}$ 定义良好，假设在论文中所有 $v \in V$ 满足 $d_{\text{out}}(v) > 0$ 。在这种情况下， $\mathbf{P}$ 是列随机矩阵，因此可以视为马尔可夫链的转移矩阵。

邻接矩阵 A：表示图中节点之间的连接关系。

度矩阵 D：表示每个节点的出度。

转移矩阵 P：表示从一个节点转移到其他节点的概率。

指示向量：对于一个节点 $v \in V$ ，我们定义 $e_v$ 为一个 $n$ 维列向量，其中第 $i$ 个元素等于 $1\{ v_i = v \}$ 。注意，在本综述中我们使用列向量而非行向量。此外，对于一个与节点集合 $V$ 关联的 $n$ 维向量 $x$ ，我们用 $x(v)$ 表示向量 $x$ 的第 $i$ 个元素，其中 $i$ 满足 $v_i = v$ 。

指示向量：将每个节点映射到一个独特的位置，便于数学运算和算法处理。

2.2 PPR 定义

PPR 代数定义：我们用 $\pi_s$ 表示相对于源节点 $s$ 的 PPR 向量，它为每个 $t \in V$ 分配一个接近度得分 $\pi_s(t)$ 。 $\pi_s$ 被定义为以下线性方程的唯一解：

$\pi_s = (1 - \alpha) \mathbf{P} \pi_s + \alpha \cdot e_s,$

其中 $\alpha \in (0, 1)$ 是一个预定义的参数，称为“传送概率”（又称“衰减因子”）。在这里，指示向量 $e_s$ 被称为定义 PPR 时的“偏好向量”。为了证明 $\pi_s$ 是定义良好的，需要注意矩阵 $\mathbf{I} - (1 - \alpha) \mathbf{P}$ 保证是非奇异的，因为它是严格列对角占优的。因此， $\pi_s$ 等于：

$\pi_s = \alpha \left( \mathbf{I} - (1 - \alpha) \mathbf{P} \right)^{-1} e_s,$

这证明了 $\pi_s$ 的存在性和唯一性。PPR 的更一般定义允许方程中的偏好向量为任意概率分布向量，而不仅限于指示向量。正如我们将在定理 1 中看到的，这些广义的 PPR 向量是我们定义中的 PPR 向量的线性组合。

基于随机游走的解释：在第一种可能的定义中，随机游走从源节点 $s$ 出发，并且在每一步中，它要么以概率 $\alpha$ 跳回到 $s$ （简称 w.p. 表示“以概率”），要么随机均匀地前往当前节点的一个出邻居。此类随机游走也被称为带重启的随机游走（Random Walk with Restart，RWR）。PPR 向量 $\pi_s$ 被定义为 RWR 在无限多步后在 $V$ 上的平稳分布。因此，PPR 值有时也被称为 RWR 值。

或者，可以修改上述过程以定义一个 $\alpha$ -折扣随机游走（ $\alpha$ -discounted random walk），该游走从 $s$ 开始并在当前节点终止（而不是在每一步以概率 $\alpha$ 跳回到 $s$ ）。向量 $\pi_s$ 可以定义为此类 $\alpha$ -折扣随机游走最终终止的节点上的终止分布。

PR 代数定义：我们用 $\pi$ 表示 PageRank 向量，它为每个 $t \in V$ 分配一个中心性得分 $\pi(t)$ 。在代数上，PageRank 是广义 PPR 的一种特殊形式，其中偏好向量为 $\frac{1}{n} \cdot \mathbf{1}$ ，其中 $\mathbf{1}$ 是一个 $n$ 维向量，所有坐标的值均为 1：

$\pi = (1 - \alpha) \mathbf{P} \pi + \alpha \cdot \frac{1}{n} \mathbf{1}.$

正如我们将在定理 1 中看到的， $\pi$ 等于所有 $s \in V$ 的 $\pi_s$ 的平均值。PageRank 也可以通过 RWR 或 $\alpha$ -折扣随机游走来定义。为此，RWR 从任意节点出发，并在每一步以概率 $\alpha$ 跳回到 $V$ 中的一个均匀随机节点；而 $\alpha$ -折扣随机游走则从 $V$ 中的一个均匀随机源节点开始。PR是PPR的特殊形式

消除悬挂节点：如果节点 $v$ 的出度 $d_{\text{out}}(v) = 0$ ，则称该节点为悬挂节点。如前所述，PPR 和 PageRank 的正式定义要求图中没有悬挂节点。然而，实际中几乎不可能满足这一条件。在处理真实世界的图时，提出了多种处理悬挂节点的策略。

引入一个虚拟节点，该节点自循环并从每个悬挂节点到它添加一条边；
假设每个悬挂节点都有指向 VVV 中每个节点的出边；
为每个悬挂节点添加一个自循环。不同的方法可能会导致结果 PPR 值的微小差异，但总体排名保持不变。

2.3 PPR 查询

PPR查询定义： $n \times n$ 的 PPR 矩阵 $\Pi$ 包含了 $V$ 中所有节点之间的 PPR 值，作为有用的接近度得分。然而，计算和存储密集矩阵 $\Pi$ 需要 $\Omega(n^2)$ 的时间和空间，当 $n$ 达到例如 $10^7$ 时，这是不可行的。幸运的是，在许多情况下，并不需要计算整个 $\Pi$ ；我们只需要 $\Pi$ 的一行或一列，甚至仅仅一个元素。这促使我们定义了用于 PPR 计算的多种查询类型：

单源 PPR (SSPPR)：给定一个源节点 $s \in V$ ，需要 PPR 向量 $\pi_s$ 。
单目标 PPR (STPPR)：给定一个目标节点 $t \in V$ ，需要逆 PPR 向量 $\pi_t^{-1}$ 。
单对 PPR (SPPPR)：给定一个源节点 $s \in V$ 和一个目标节点 $t \in V$ ，需要 PPR 值 $\pi_s(t)$ 。
Top-k PPR：给定一个源节点 $s$ 和一个整数 $k$ ，需要 $\pi_s$ 中值最大的 $k$ 个节点。在某些情况下，还需要这些节点在 $\pi_s$ 中对应的值。

近似查询误差：正如我们将看到的，这些查询可以通过基于代数技术的算法精确解答。然而，计算精确答案通常会产生显著的成本，这对于高效的在线查询来说是不现实的。尤其是对于输出规模较小的 SPPPR 和 top-k PPR 查询，计算精确答案会造成不必要的浪费。在实际应用中，通常可以接受对这些查询进行近似解答，以换取更高的效率。此外，引入近似计算允许算法使用稀疏向量回答某些查询。对于两个 $n$ 维向量 $\hat{x}$ 和 $x$ ，或一个正实数 $x$ 及其估计值 $\hat{x}$ ，四种常用的误差度量定义如下：

ℓ1-误差： $\|\hat{x} - x\|_1 = \sum_{v \in V} |\hat{x}(v) - x(v)|$
ℓ2-误差： $\|\hat{x} - x\|_2 = \sqrt{\sum_{v \in V} \left( \hat{x}(v) - x(v) \right)^2}$
绝对误差： $\|\hat{x} - x\|_\infty = \max_{v \in V} |\hat{x}(v) - x(v)|$
相对误差： $\max_{v \in V: x(v) \geq \mu} \frac{|\hat{x}(v) - x(v)|}{x(v)}$

这些定义是直观的，除了相对误差：由于对于较小的值很难实现相同的相对误差，许多相关算法仅为大于阈值 $\mu$ 的值提供相对误差界。此外，注意这些误差度量不直接适用于 top-k PPR 查询；我们将单独讨论 top-k PPR 查询的近似保证。

3. 基础技术

3.1 Monte Carlo（Total）

蒙特卡洛方法（Monte Carlo method，MC）是一种经典的方法，用于计算基于样本的期望值估计。受到基于 $\alpha$ -折扣随机游走的 PPR 解释的启发，我们可以利用 MC 方法来近似 PPR 向量 $\pi_s$ 。尽管看似简单，MC 方法可以高概率地高效获得无偏且精确的 PPR 估计，且它有潜力突破确定性算法的理论下界。MC 方法的另一个潜在优势是其对并行化的天然适应性。

3.2 Power Iteration（Total）

幂迭代法（Power Iteration，PI）是一种用于计算整个 PPR 向量的基本迭代方法，最初在 Google 的开创性论文中提出。实际上，它是数值线性代数中用于求解线性方程的 Jacobi 方法的直接改编，其中 $\pi_s$ 被视为方程 $\pi_s = (1 - \alpha) \mathbf{P} \pi_s + \alpha e_s$ 的解。PI 使用以下迭代公式来计算 $\pi_s$ 的估计 $\hat{\pi}_s^{(0)}, \hat{\pi}_s^{(1)}, \ldots, \hat{\pi}_s^{(T)}$ ，其中 $T$ 是一个参数：

$\hat{\pi}_s^{(0)} = e_s, \quad \hat{\pi}_s^{(L+1)} = (1 - \alpha) \mathbf{P} \hat{\pi}_s^{(L)} + \alpha e_s, \quad \forall L \geq 0.$

这里， $\hat{\pi}_s^{(L)}$ 表示在经过 $L$ 步后从 $s$ 开始的 RWR 的概率分布。

3.3 Forward Push（SSPPR）

前向推送（Forward Push，FP）是一种局部推送方法，可以在不扫描整个图的情况下回答 SSPPR 查询。本质上，FP 可以视为一种迭代坐标求解器，也可以视为 Gauss-Seidel 方法的一种变体。对于我们的目的，FP 最好理解为 CPI 的局部版本，详细解释见，简要介绍如下。回顾一下，CPI 在每次迭代中同步地向所有节点进行推送操作。另一方面，FP 修改了这一过程，异步地执行推送。它一次仅对一个节点执行推送操作，并允许节点以一种不太结构化的顺序进行推送。直观上，具有较大保留值的节点应优先进行推送。

3.4 Reverse Power Iteration（STPPR）

反向幂迭代（RPI）是一种方法，用于通过累积迭代近似计算 STPPR 查询的反向 PPR 向量。RPI 使用矩阵 $\mathbf{P}^\top$ 和逐步累加迭代来估计 $\pi_t^{-1}$ 。由于 $\mathbf{P}^\top$ 不是列随机矩阵，RPI 采用绝对误差作为误差度量。为确保误差小于给定阈值 $\epsilon$ ，可以设定适当的迭代步数 $T$ 。最终，RPI 能够在 $\left(\frac{m}{\alpha} \log \frac{1}{\epsilon}\right)$ 的时间复杂度内完成查询，提供了一种高效的近似解法。

3.5 Backward Push（STPPR）

反向推送（BP）是一种用于回答 STPPR 查询的局部推送算法，它通过保留向量和残差向量之间的关系递归地执行推送操作。BP 的复杂度由节点的推送操作主导，可以通过选择参数 $r_{\max}^{(b)}$ 来控制误差界，从而在 $O \left( \frac{m / n}{\alpha \epsilon} \right)$ 的时间复杂度内完成查询。

总结而言，五种基本算法在误差界和复杂度上各有特点：PI 和 RPI 适合较高精度要求但需要全图扫描，MC 不扫描图但对小误差要求时复杂度较高。相比之下，FP 和 BP 作为本地推送方法，在误差控制和效率之间提供了折中选择，适合局部查询。FP 提供度归一化的误差保证，BP 则提供绝对误差保证，且在无向图或平均复杂度下表现更简洁。总体上，MC 和本地推送方法是设计子线性算法的关键工具。

4. PPR 算法

4.1 SINGLE-SOURCE PPR ALGORITHMS

4.1.1 SSPPR Algorithms Based on PI and Algebraic Techniques

此类 SSPPR 算法从 PPR 的代数定义开始，应用多种先进的线性代数或优化技术来有效计算误差较小的 PPR 向量。然而，它们的复杂性通常至少与图的大小成线性关系：

线性代数方法：多项研究利用线性代数技术，如 Arnoldi、GMRES、LU 分解、块消元法等，以优化计算效率。BEAR 和 BEPI 等方法通过矩阵预处理减少计算开销，并提高查询效率。
图分解和低秩逼近：B_LIN 和 NB_LIN 利用图分割和低秩逼近，RPPR 和 BRPPR 则在限制的子图上迭代扩展，来加速 SSPPR 计算。
动态规划和动态平衡：动态规划算法如 Jeh 和 Widom 提出的 SSPPR 算法，通过分解定理和 Count-Min Sketch 提升了空间和查询效率。FastPPV 实现了查询时的动态效率与准确性平衡。
改进的迭代方法：CHOPPER 利用 Chebyshev 多项式组合来加速幂迭代收敛，减少迭代次数。TPA 算法则通过将 PPR 分解为多个部分来分步近似计算，以减少时间复杂度。
优化加速技术：Chen 等提出的 FwdPushSOR 利用后继超松弛法和动量加速，在无向图上将 SSPPR 计算转化为凸优化问题，提升了算法的收敛速度。最新成果

4.1.2 SSPPR Algorithms Based on Local Push and MC（主要研究方向）

这些算法主要优化普通 FP 算法和/或将本地推送技术与 MC 相结合来回答 SSPPR 查询。通过应用局部推送和随机性，他们有可能实现次线性复杂性。

局部推送与随机性结合：许多算法改进了标准的前向推送 (FP) 方法，或将其与蒙特卡罗 (MC) 方法结合以实现次线性复杂度。例如，Berkhin 的 BCA 和 Chakrabarti 的 HUBRANK 通过预计算的枢纽节点向量加速计算，FORA 使用“FP + MC”框架减少 MC 样本需求，而 ResAcc 则通过累积残差以减少推送次数和随机游走次数。
指数收敛和异步推送：Chung 和 Zhao 提出了使用指数阈值减少推送次数的方法，Wu 等人的 PowerPush 结合了 FP 的局部推送和 PI 的全局方法，提升了效率和准确性。
基于路径和节点的优化：FastPPV 通过路径分区优先处理关键路径，允许查询时在效率和准确性之间动态平衡。
动态规划与优化框架：Wu 等的 SpeedPPR 用 PowerPush 替换 FORA 的 FP 阶段，大幅提升效率；Fountoulakis 等将 FP 重新表述为优化问题，通过正则化 PageRank 提出新的局部聚类方法。
MC 技术的优化：Liao 等的 FORAL 使用随机生成森林替代 MC 中的随机游走采样，适合小 $\alpha$ 值的情况；后续工作提出降低 MC 估计方差的技术，结合森林采样提高了 SSPPR 的实际性能。
灵敏度受限的 FP 方法：Epasto 等人提出在无向图中限制沿边推送的残差量，从而确保对边的低灵敏度并保持近似质量。

4.2 SINGLE-TARGET PPR ALGORITHMS

目前，对 STPPR 查询的研究相对较少，主要依赖于反向局部推送。由于 MC 无法直接用于 STPPR 计算，研究集中在优化反向推送的方法上：

BP 实现优化：Lofgren 和 Goel 使用斐波那契堆优化 BP 实现，复杂度达到 $O(m \log(1/\epsilon))$ ，与 RPI 相当。
随机化 BP：Wang 等提出 RBS，通过只对节点的随机子集进行推送来降低 BP 的计算成本。对于相对误差的 STPPR 查询，RBS 将 BP 的平均复杂度从 $m/n$ 降至 $\tilde{O}(1/\mu)$ ，并在节点级别达到参数化复杂度 $\tilde{O}(n \pi(t)/\mu)$ ，实现了最优复杂度。
RBS 进一步优化：RBS 通过线性时间的预处理将每个节点的入邻居按出度排序，从而在绝对误差情况下，以 $\tilde{O}\left( \sum_{v \in V} \pi_t^{-1}(v) \cdot d_{\text{out}}(v) / \epsilon \right)$ 的复杂度完成查询。
基于随机生成森林的 BACKL：Liao 等提出 BACKL，作为 FORAL 的 STPPR 版本。BACKL 采用“BP+MC”框架，MC 阶段通过采样随机生成森林实现，在小 $\alpha$ 值下尤其高效。

4.3 SINGLE-PAIR PPR ALGORITHMS

FAST-PPR：首先运行 BP 构建目标节点的前沿集合，然后使用 MC 从源节点检测到达该集合的概率。

BiPPR：在不同的分析框架下改进了 FAST-PPR 的复杂度
Undirected-BiPPR：在无向图上运行
HubPPR：Wang 等提出的 HubPPR 是 BiPPR 的优化版本，使用两个预处理的反向和正向 oracle 加速 BP 和 MC 阶段。HubPPR 预处理了“枢纽”节点的反向推送和随机游走结果，以减少查询时的计算成本。

4.4 TOP-k PPR ALGORITHMS

4.4.1 Top-k PPR Algorithms Based on Algebraic Techniques

Fujiwara 等人和 Wu 等人提出了一系列用于精确计算 top-k 个性化 PageRank (PPR) 的算法，这些算法主要通过上下界估计和剪枝策略来优化计算过程：

K-dash：利用广度优先搜索树，结合稀疏矩阵计算、节点重排序和 LU 分解来加速计算过程。
SPPPR 应用：在中应用 SPPPR 算法进行 top-k 计算。
Castanet：专门为目标节点集合中的 top-k 排名设计，返回精确的排名结果。
F-Rank：专为精确 top-k PageRank 计算而设计。
FLoS_RWR：Wu 等人提出的算法，基于 FLoS_PHP 扩展，用于计算受惩罚的命中概率 (PHP)。通过局部搜索和 SPI 计算节点 PHP 值的上下界，逐步扩展子图并收紧上下界，从而确定 top-k 节点。
CHOPPER：基于 Chebyshev 多项式的加速 SPI 计算 PPR 向量。利用加速误差界剪枝掉不可能为 top-k 的节点，减少迭代次数。

4.4.2 Top-k PPR Algorithms Based on Local Push and MC

上述内容介绍了多种用于近似 top-k 个性化 PageRank (PPR) 查询的算法及其优化策略：

两阶段算法与确定性取整：Sarlós 等人将确定性取整应用于动态规划算法，构建了占用最优空间的数据库用于近似 top-k 查询。
Basic Push Algorithm：Gupta 等人提出的算法使用 FP 结合优先队列和预计算的枢纽向量，通过上下界计算 PPR 值，在保证结果有效后终止，返回节点数在指定范围内的结果。
HUBRANK：Chakrabarti 等人提出 HUBRANKP 和 HUBRANKD，用于高效 top-k PPR 查询，基于 BCA 和分解定理构建索引，HUBRANKP 相较 HUBRANKD 更具优势。
蒙特卡罗方法：Avrachenkov 等人使用 MC 估算 PPR 向量，通过中心极限定理实现高效近似 top-k 查询，允许少量错误结果。
已有算法的适配：多种 SSPPR 和 SPPPR 算法（如 BiPPR、HubPPR 和 FORA）可适配用于 top-k PPR 查询。例如，BiPPR 通过分层采样提升性能，HubPPR 通过迭代更新目标节点的上下界实现高精度，而 FORA 采用试错方式调整误差阈值，确定终止时机。
TopPPR：Wei 等提出的 TopPPR 结合 FP、BP 和 MC，通过自适应 BP 确定 top-k 节点，维护并扩展候选节点集

本次调查研究了有效的 PPR 计算，并详细阐述了五种基本技术：蒙特卡罗方法、功率迭代、前推、反向功率迭代和后推。然后，我们从算法的角度对最新的 PPR 算法进行了广泛的调查，总结了它们的基本原理和贡献。我们的分类基于查询类型，包括单源 PPR、单目标 PPR、单对 PPR 和 Top-k PPR 查询。此外，我们还回顾了几种针对特殊设置定制的算法，例如动态图和并行/分布式环境中的算法。我们还根据 PPR 算法的技术对它们进行了高层比较，并指出了未来的研究方向，旨在启发和指导 PPR 计算领域的后续进展。

查看全文

http://www.kler.cn/a/394050.html