基于随机游走的标签传播算法（Label Propagation with Random Walk）的原理与迭代计算过程
题目描述
假设我们有一个包含少量标记节点和大量未标记节点的图（Graph）。我们的目标是利用图中节点之间的连接关系（即图的结构信息），将标记节点的标签信息“传播”到未标记节点，从而为所有未标记节点预测标签。基于随机游走的标签传播算法正是解决此类“图半监督学习”问题的一种经典方法。其核心思想是：一个节点的标签，可以由在其附近“随机游走”时最可能到达的标记节点的标签决定。本题目将详细讲解该算法的原理、数学建模、迭代求解过程及其收敛性。
解题过程循序渐进讲解
步骤1：问题定义与图表示
我们有一个无向图 \(G = (V, E)\)，其中 \(V\) 是节点集合，包含 \(n\) 个节点，\(E\) 是边集合，通常用邻接矩阵 \(W\) 表示，\(W_{ij} \geq 0\) 表示节点 \(i\) 和 \(j\) 之间的边权重（相似度）。节点集合分为两部分：
- 已标记节点集合 \(V_l = \{1, 2, ..., l\}\)，其标签向量已知，属于 \(C\) 个类别，可用一个 \(l \times C\) 的标签矩阵 \(Y_l\) 表示（如one-hot编码）。
- 未标记节点集合 \(V_u = \{l+1, l+2, ..., n\}\)，共 \(u = n - l\) 个节点，其标签未知，是我们要预测的目标。
目标：为每个未标记节点 \(i \in V_u\) 预测一个类别标签。
步骤2：算法核心思想——随机游走的解释
想象一个粒子在图上进行随机游走。从一个未标记节点出发，每一步都依据边权重（相似度）概率性地跳转到邻居节点。如果这个随机游走过程最终以较高的概率到达某个标记节点，那么该未标记节点的标签就很可能与该标记节点的标签相同。
更形式化地，定义从节点 \(i\) 出发的随机游走，首次到达某个标记节点时，该标记节点的标签即为节点 \(i\) 的预测标签。算法通过计算“吸收概率”来实现。
步骤3：数学建模——构建转移概率矩阵
首先，根据邻接矩阵 \(W\) 计算度矩阵 \(D\)：
\[D_{ii} = \sum_{j=1}^{n} W_{ij} \]
度矩阵 \(D\) 是对角矩阵，其对角线元素是每个节点的度（即所有边权重之和）。
然后，定义随机游走的转移概率矩阵 \(P\)：
\[P = D^{-1} W \]
即 \(P_{ij} = \frac{W_{ij}}{D_{ii}}\) 表示从节点 \(i\) 一步转移到节点 \(j\) 的概率。注意，\(P\) 的每一行和为1。
步骤4：定义标签分布矩阵与迭代公式
我们为每个节点 \(i\) 维护一个 \(C\) 维向量 \(F_i\)，表示节点 \(i\) 属于各个类别的“置信度”或概率分布。初始时：
- 对于已标记节点 \(i \in V_l\)，\(F_i\) 固定为其真实的one-hot标签向量（即 \(Y_{l_i}\)），在迭代过程中保持不变。
- 对于未标记节点 \(i \in V_u\)，初始 \(F_i\) 可以设为均匀分布或全零向量（实际上初始值影响不大，因为最终会收敛到由已标记节点决定的值）。
标签传播的核心迭代公式为：
\[F_i^{(t+1)} = \sum_{j=1}^{n} P_{ij} F_j^{(t)}, \quad \forall i \in V_u \]
而对于已标记节点 \(i \in V_l\)，始终保持 \(F_i = Y_{l_i}\) 不变。
直观理解：每个未标记节点在下一次迭代时的标签分布，是其所有邻居节点当前标签分布的加权平均，权重即为随机游走到该邻居的概率 \(P_{ij}\)。这相当于模拟了标签信息沿着边进行扩散的过程。
步骤5：将迭代过程写成矩阵形式
将节点顺序排列，使得前 \(l\) 个为已标记节点，后 \(u\) 个为未标记节点。将矩阵分块：
- 标签矩阵 \(F = \begin{bmatrix} F_l \\ F_u \end{bmatrix}\)，其中 \(F_l\) 是 \(l \times C\) 的已知固定矩阵（即 \(Y_l\)），\(F_u\) 是 \(u \times C\) 的待求解矩阵。
- 转移概率矩阵 \(P = \begin{bmatrix} P_{ll} & P_{lu} \\ P_{ul} & P_{uu} \end{bmatrix}\)。
根据迭代公式，对于未标记节点部分 \(F_u\) 的更新为：
\[F_u^{(t+1)} = P_{ul} F_l + P_{uu} F_u^{(t)} \]
注意，由于已标记节点的 \(F_l\) 固定不变，因此 \(P_{ul} F_l\) 是一个常数项。这实际上是一个线性迭代系统。
步骤6：求解收敛状态
当迭代收敛时，有 \(F_u^{(\infty)} = F_u^{(t+1)} = F_u^{(t)}\)。代入上式得到：
\[F_u = P_{ul} F_l + P_{uu} F_u \]
整理得：
\[(I - P_{uu}) F_u = P_{ul} F_l \]
这是一个线性方程组。由于 \(I - P_{uu}\) 是严格对角占优的（因为 \(P_{uu}\) 的每一行和小于1），因此可逆。最终解为：
\[F_u = (I - P_{uu})^{-1} P_{ul} F_l \]
从随机游走角度，\((I - P_{uu})^{-1} = \sum_{k=0}^{\infty} P_{uu}^k\)，这恰好计算了从任意未标记节点出发，在首次到达已标记节点之前，在未标记子图中游走的期望次数。而 \(P_{ul} F_l\) 则给出了从已标记节点吸收的标签信息。因此，解 \(F_u\) 可以解释为吸收概率。
步骤7：算法步骤总结
- 输入：图 \(G\) 的邻接矩阵 \(W\)（或相似度矩阵），已标记节点的标签矩阵 \(Y_l\)。
- 计算度矩阵 \(D\)（对角线元素为 \(D_{ii} = \sum_j W_{ij}\)）。
- 计算转移概率矩阵 \(P = D^{-1} W\)。
- 将矩阵分块为 \(P_{ul}\) 和 \(P_{uu}\)，对应于未标记节点到已标记节点、未标记节点之间的转移子矩阵。
- 直接求解线性系统：计算 \(F_u = (I - P_{uu})^{-1} P_{ul} Y_l\)。
（或采用迭代法：初始化 \(F_u^{(0)}\) 为任意值（如0），然后迭代 \(F_u^{(t+1)} = P_{ul} Y_l + P_{uu} F_u^{(t)}\) 直到收敛。） - 输出：对于每个未标记节点 \(i\)，其预测标签为 \(\arg\max_c F_{u, i, c}\)（即置信度最大的类别）。
步骤8：收敛性与算法理解
- 该迭代过程本质上是求解一个线性系统，其收敛速度取决于矩阵 \(P_{uu}\) 的谱半径（最大特征值）。由于 \(P_{uu}\) 是随机矩阵的子矩阵，其谱半径小于1，保证迭代收敛。
- 算法可以看作是在图上定义一个马尔可夫随机游走，并将已标记节点视为“吸收态”，未标记节点的标签分布就是其被各个吸收态吸收的概率。
- 与基于图的另一种经典算法“标签传播”（Label Propagation，通过相邻节点标签的平均来迭代）相比，随机游走版本有更直观的概率解释，并且其解是吸收概率，具有清晰的数学形式。
总结
基于随机游走的标签传播算法巧妙地将图结构、随机过程和半监督学习结合起来。通过定义图上的随机游走转移概率，并将已标记节点视为吸收态，最终通过求解一个线性系统（或等价迭代）得到未标记节点的标签分布。该方法计算高效，且对图的结构信息利用充分，是图上半监督学习的基础算法之一。