Details: Personalized PageRank

下面把 2.3 节拆成六个层次来讲透：conductance 的定义与直觉 → 为什么用 Personalized PageRank → PR 方程的随机游走推导 → 懒惰随机游走的矩阵形式 → 近似算法（push 方法）→ 扫描割与理论保证。

一、Conductance：为什么这样定义

1.1 定义

对无向加权图 $G=(V,E,R)$ ，子集 $S \subseteq V$ 的 conductance 为：

\Phi(S) = \frac{\sigma(S)}{\min[\mathrm{vol}(S),\, 2m - \mathrm{vol}(S)]}

其中：

\sigma(S) = \sum_{v_x \in S,\, v_y \notin S} R_{xy}

\mathrm{vol}(S) = \sum_{v_i \in S} \deg(v_i), \quad \deg(v_i) = \sum_j R_{ij}

2m = \sum_i \deg(v_i)

符号解释：

$R_{xy}$ ：功能相似图中边 $(v_x,v_y)$ 的权重，即 IsoRank 分数；
$\sigma(S)$ ：割权，即从 $S$ 连到 $S^c$ 的所有边权之和；
$\mathrm{vol}(S)$ ： $S$ 的体积，即 $S$ 内所有节点度数之和；
$2m - \mathrm{vol}(S) = \mathrm{vol}(S^c)$ ：补集体积；
分母取较小体积，保证 $\Phi(S)$ 关于 $S$ 和 $S^c$ 对称。

1.2 为什么分母用 $\min[\mathrm{vol}(S), \mathrm{vol}(S^c)]$

如果分母用 $|S|$ （节点数），会偏向小集合：一个很小的集合只要割边少，conductance 就低，但它可能没有生物学意义。
如果用 $\mathrm{vol}(S)$ ，会偏向大集合： $S=V$ 时割为 0，conductance 为 0，但这不是簇。
用 $\min[\mathrm{vol}(S), \mathrm{vol}(S^c)]$ 的直觉是：

如果 $S$ 很小，分母是 $\mathrm{vol}(S)$ ，要求割相对于 $S$ 自身的连接也不能太大；
如果 $S$ 很大，分母是 $\mathrm{vol}(S^c)$ ，等价于在衡量补集这个“小集合”的割；
因此 $\Phi(S)=\Phi(S^c)$ ，不会因取 $S$ 还是补集而改变。

1.3 直观：conductance 衡量“像不像簇”

内部边多、外部边少 → $\sigma(S)$ 小、 $\mathrm{vol}(S)$ 大 → $\Phi(S)$ 小 → 像簇；
内部边少、外部边多 → $\sigma(S)$ 大、 $\mathrm{vol}(S)$ 小 → $\Phi(S)$ 大 → 不像簇。

在功能相似图中，一个跨物种功能簇应该内部高权重、外部低权重，因此对应低 conductance 集。

1.4 与“最大加权 clique”的对比

严格 clique 要求 $S$ 内每对节点都有边，且边权高。PPI 数据有噪声、不完整，严格 clique 几乎不存在。
低 conductance 集只要求“内部连接相对紧密、外部连接相对稀疏”，允许缺失边和低权边，因此误差容忍。这就是作者从 clique 转向 conductance 的原因。

二、为什么用 Personalized PageRank

2.1 全局谱划分的问题

经典谱聚类需要对整张图做拉普拉斯特征分解，复杂度高，且给出的是全局划分，不能针对某个起点 $v$ 找“包含 $v$ 的簇”。
IsoRankN 需要：对每个蛋白 $v$ ，在它的星 $S_v$ 上找包含 $v$ 的高质量子集 $S_v^s$ 。这是局部图划分问题。

2.2 PageRank-Nibble 的核心思想

Anderson et al. (2006) 证明：

给定起点 $v$ ，可以通过计算 $v$ 的 Personalized PageRank 向量，再对其做扫描割，高效地找到一个包含 $v$ 的低 conductance 集，且该集合接近最优。

“Nibble”意为“小口咬”：只探索 $v$ 附近的一小部分图，而不是全图。复杂度与输出集合大小相关，而不是 $n$ 或 $m$ 。

2.3 Personalized PageRank 与普通 PageRank 的区别

普通 PageRank：

\pi = \alpha \pi W + (1-\alpha) \mathbf{1}/n

传送项均匀分布到所有节点，得到全局重要性排序。

Personalized PageRank：

p = \alpha p W + (1-\alpha) \chi_v

传送项集中在起点 $v$ ，得到“相对于 $v$ 的局部重要性排序”。与 $v$ 连接紧密的节点获得较高质量。

三、PR 方程的随机游走推导

3.1 随机游走过程

从 $v$ 出发，每一步：

以概率 $\gamma$ 传送回 $v$ ；
以概率 $1-\gamma$ 做懒惰随机游走：以 1/2 概率不动，以 1/2 概率按边权比例跳到邻居。

设 $p(x)$ 为长期停留在节点 $x$ 的概率。则：

p(x) = \gamma \cdot \mathbf{1}[x=v] + (1-\gamma) \sum_{y} p(y) W_{yx}

其中 $W_{yx}$ 是从 $y$ 跳到 $x$ 的转移概率。

写成向量形式：

p = \gamma \chi_v + (1-\gamma) p W

这就是原文公式 (1) 的等价形式（原文用 $\gamma$ 表示传送概率，与常见 PageRank 的 $\alpha$ 对应）：

Pr(\gamma, v) = \gamma \chi_v + (1-\gamma) Pr(\gamma, v) W

注意符号： 原文中 $\gamma$ 是传送回 $v$ 的概率， $\gamma$ 越大，越局部；常见 PageRank 中 $\alpha$ 常表示继续游走的概率，这里不要混淆。

3.2 解的存在唯一性

整理方程：

p(I - (1-\gamma)W) = \gamma \chi_v

p = \gamma \chi_v (I - (1-\gamma)W)^{-1}

因为 $W$ 是随机矩阵，谱半径 $\le 1$ ，而 $0 < \gamma \le 1$ ，所以 $(1-\gamma)W$ 谱半径 $<1$ ，矩阵 $I - (1-\gamma)W$ 可逆，解唯一：

p = \gamma \sum_{t=0}^{\infty} (1-\gamma)^t \chi_v W^t

展开理解：

p = \gamma \chi_v + \gamma(1-\gamma)\chi_v W + \gamma(1-\gamma)^2 \chi_v W^2 + \cdots

第一项：传送一次就停在 $v$ 的概率；
第二项：传送后走一步到达某节点的概率；
第 $t$ 项：传送后走 $t$ 步的概率；
因子 $(1-\gamma)^t$ 使长游走指数衰减，因此 $p$ 集中在 $v$ 附近。

这就是“局部性”的数学来源： $\gamma$ 越大，衰减越快， $p$ 越集中在 $v$ 附近； $\gamma$ 越小，扩散越远。

3.3 与 IsoRank 全局方程的关系

原版 IsoRank 的方程：

R = \alpha A R + (1-\alpha)E

Personalized PageRank 方程：

p = (1-\gamma) p W + \gamma \chi_v

结构相同：都是“传播项 + 重启/先验项”。区别：

	IsoRank	Personalized PageRank
传播矩阵	$A$ （乘积图拓扑）	$W$ （功能相似图懒惰游走）
先验项	$E$ （序列同源性，全局）	$\chi_v$ （单点指示，局部）
解的含义	所有蛋白对的全局相似度	相对于起点 $v$ 的局部重要性

可以认为：IsoRank 是“以序列相似性为先验的全局 PageRank”；Personalized PageRank 是“以单点 $v$ 为先验的局部 PageRank”。

四、懒惰随机游走矩阵 $W$

4.1 定义

原文：

W = \frac{1}{2}(I + D^{-1}R)

符号解释：

$R$ ：功能相似图的加权邻接矩阵， $R_{ij} = w(v_i,v_j)$ ；
$D$ ：对角矩阵， $D_{ii} = \sum_j R_{ij}$ （按行归一化）或列和（无向图行和=列和）；
$D^{-1}R$ ：普通随机游走转移矩阵，从 $i$ 跳到 $j$ 的概率为 $R_{ij}/\deg(i)$ ；
$I$ ：单位矩阵；
$\frac{1}{2}(I + D^{-1}R)$ ：以 1/2 概率不动，以 1/2 概率按边权跳。

4.2 为什么要“懒惰”

普通随机游走可能具有周期性（例如二分图上奇偶步来回跳），导致极限分布不收敛。懒惰随机游走通过“以 1/2 概率不动”打破周期性，保证：

$W$ 的特征值在 $[-1,1]$ 内，且最大特征值为 1；
当 $\gamma>0$ 时， $(1-\gamma)W$ 谱半径 $<1$ ，PR 方程有唯一解；
收敛行为更稳定。

4.3 列和/行和归一化方向

原文说 “ $D$ is the diagonal of column sums of $R$ ”。对于无向图，行和等于列和，所以方向不影响结果。严格来说：

若 $p$ 是行向量， $W = \frac{1}{2}(I + D^{-1}R)$ 中 $D^{-1}R$ 是行随机矩阵， $pW$ 表示从 $p$ 分布走一步后的分布；
若用列向量，则写成 $W = \frac{1}{2}(I + R D^{-1})$ ， $Wp$ 同理。

论文采用行向量约定，所以 $pW$ 在右乘。

五、近似算法：push 方法

5.1 为什么不精确求解

精确求解 $p = \gamma \chi_v + (1-\gamma)pW$ 需要解线性系统，复杂度 $O(n^3)$ 或至少 $O(m)$ ，对于全图太大。
Anderson et al. (2006) 的贡献是：只需局部计算，就能得到 $p$ 的近似，且近似误差可控制。

5.2 push 算法的核心思想

维护两个向量：

$p$ ：当前对 PR 向量的估计（“已确定的质量”）；
$r$ ：残差（“尚未分配的质量”）。

初始：

p = 0, \quad r = \chi_v

即所有质量都在起点 $v$ 的残差中。

迭代 push 操作：

选一个残差 $r(u)$ 较大的节点 $u$ ；
把 $r(u)$ 的一部分“推送”到 $p(u)$ 和邻居的残差中：

p(u) \leftarrow p(u) + \gamma r(u)

r(u) \leftarrow \frac{1}{2}(1-\gamma) r(u)

r(w) \leftarrow r(w) + \frac{1}{2}(1-\gamma) \frac{R_{uw}}{\deg(u)} r(u), \quad \forall w \in N(u)

解释：

以概率 $\gamma$ ，这部分质量“传送回 $v$ ”并永久留在 $u$ 的估计中（严格说是留在当前节点，但传送项最终归到 $v$ ；实现上 $p(u)$ 累加 $\gamma r(u)$ ，而 $\chi_v$ 项单独处理）；
以概率 $1-\gamma$ 继续游走，其中 1/2 不动（留在 $u$ 的残差），1/2 按边权分给邻居；
当所有残差都小于阈值 $\epsilon$ 时停止。

5.3 复杂度与局部性

push 算法的复杂度与被 push 的节点数成正比，而不是全图节点数。由于 $(1-\gamma)^t$ 指数衰减，远离 $v$ 的节点残差很快低于阈值，不会被 push。
因此对于局部性强的 $\gamma$ ，算法只探索 $v$ 附近的一小部分图。这就是“Nibble”的高效来源。

5.4 近似误差保证

Anderson et al. (2006) 证明：当残差满足 $\|r\|_\infty \le \epsilon$ 时，得到的 $p$ 满足：

\|p - Pr(\gamma,v)\|_1 \le \frac{\epsilon}{\gamma}

即近似误差可控。误差越小，需要 push 的次数越多，但仍是局部的。

六、扫描割：从 PR 向量到低 conductance 集

6.1 排序

得到近似 PR 向量 $p$ 后，按 $p(v_i)$ 从大到小对节点排序。
原文用归一化质量：

\frac{p(v_i)}{\sum_k R_k}

这里原文写法可能有笔误；更常见的做法是按 $p(v_i)/\deg(v_i)$ 或直接按 $p(v_i)$ 排序。关键思想是：PR 质量高的节点更可能属于包含 $v$ 的簇。

6.2 候选集 $T_j^p$

原文：

T_j^p = \left\{ v_i \mid \frac{p(v_i)}{\sum_k R_k} \ge \frac{p(v_j)}{\sum_k R_k} \right\}

即取质量不低于第 $j$ 个节点质量的所有节点，也就是排序后的前 $j$ 个节点构成的前缀集合。
$j$ 从 1 到 $n$ ，得到一系列嵌套候选集：

T_1^p \subseteq T_2^p \subseteq \cdots \subseteq T_n^p = V

6.3 扫描割

对每个前缀 $T_j^p$ ，计算 conductance $\Phi(T_j^p)$ ，取最小者：

S_v^s = \min_j \Phi(T_j^p)

这就是“sweep cut”：沿着 PR 排序扫描所有前缀，找 conductance 最小的截断。

6.4 理论保证

Anderson et al. (2006) 的核心定理（简化表述）：

设 $S^*$ 是包含 $v$ 的最优低 conductance 集，则扫描割得到的 $S_v^s$ 满足
$\Phi(S_v^s) \le O\left(\sqrt{\Phi(S^*)}\right)$
或类似的近似保证，具体形式取决于 $\gamma$ 和近似误差。

直观：PR 向量把“与 $v$ 紧密相连”的节点排在前面，最优低 conductance 集会在某个前缀处出现，扫描割不会错过太多。
这意味着不需要精确求解全局最优割，局部 PR + 扫描就能得到近似最优的簇。

6.5 为什么扫描割适合噪声数据

不要求严格 clique，只要求割相对小；
PR 质量是连续分数，允许边权变化；
取最小 conductance 前缀，自动确定簇的大小，不需要预设簇数；
对缺失边和低权边有容忍性。

七、2.3 节完整数学流程总结

对每个蛋白 $v$ ：

在功能相似图的星 S_v 上，初始化 p=0, r=χ_v
用 push 方法近似求解 Personalized PageRank：
   p = γχ_v + (1-γ)pW,  W = 1/2(I + D^{-1}R)
   直到所有残差 ≤ ε
按 p(v_i) 从大到小排序节点
扫描所有前缀 T_j^p，计算 conductance Φ(T_j^p)
取 S_v^s = argmin_j Φ(T_j^p)

输出 $S_v^s$ 就是包含 $v$ 的低 conductance 跨物种功能簇。

八、关键公式速查

概念	公式
Conductance	$\Phi(S) = \frac{\sigma(S)}{\min[\mathrm{vol}(S), 2m-\mathrm{vol}(S)]}$
割权	$\sigma(S) = \sum_{v_x \in S, v_y \notin S} R_{xy}$
体积	$\mathrm{vol}(S) = \sum_{v_i \in S} \deg(v_i)$
Personalized PageRank	$Pr(\gamma,v) = \gamma \chi_v + (1-\gamma) Pr(\gamma,v) W$
懒惰随机游走矩阵	$W = \frac{1}{2}(I + D^{-1}R)$
级数解	$p = \gamma \sum_{t=0}^{\infty} (1-\gamma)^t \chi_v W^t$
候选前缀集	$T_j^p = \{v_i \mid p(v_i) \ge p(v_j)\}$ （按质量排序后的前 $j$ 个）
扫描割	$S_v^s = \min_j \Phi(T_j^p)$
近似误差	$\\|p - Pr(\gamma,v)\\|_1 \le \epsilon/\gamma$

九、用一句话讲透 2.3

2.3 节用 Personalized PageRank 把“找包含 $v$ 的低 conductance 簇”转化为“从 $v$ 出发的局部随机游走稳态分布 + 按质量排序扫描割”； $\gamma$ 控制局部性，懒惰随机游走保证收敛，push 近似保证高效，扫描割保证近似最优；整套机制不要求严格 clique，因此能容忍 PPI 网络的噪声和不完整性。

如果你愿意，下一步我可以继续把 star spread 与 star merging 的完整伪代码整理出来，或者画一张从 IsoRank 分数到最终簇分配的端到端流程图。

一、Conductance：为什么这样定义

1.1 定义​

1.2 为什么分母用 min⁡[vol(S),vol(Sc)]\min[\mathrm{vol}(S), \mathrm{vol}(S^c)]min[vol(S),vol(Sc)]​

1.3 直观：conductance 衡量“像不像簇”​

1.4 与“最大加权 clique”的对比​

二、为什么用 Personalized PageRank

2.1 全局谱划分的问题​

2.2 PageRank-Nibble 的核心思想​

2.3 Personalized PageRank 与普通 PageRank 的区别​

三、PR 方程的随机游走推导

3.1 随机游走过程​

3.2 解的存在唯一性​

3.3 与 IsoRank 全局方程的关系​

四、懒惰随机游走矩阵 WWW

4.1 定义​

4.2 为什么要“懒惰”​

4.3 列和/行和归一化方向​