4. 标签传播算法的数学推导
聊完了算法的基本思想和数据治理中的应用场景，今天咱们把底层的数学逻辑彻底拆一遍。
说实话，刚接触标签传播算法的时候，我也是先上手调包跑通。但后来踩过坑才明白，不搞清楚背后的数学结构，参数调优基本靠猜。
4.1 概率转移矩阵：算法的引擎
先问个问题：标签是怎么扩散出去的？
简单说，每个节点会“看”邻居的标签分布，然后按相似度权重重新算自己的标签概率。这就是概率转移矩阵的本质。
咱们用数学语言描述一下。
定义图结构为 G = (V, E)，节点数 n = |V|。
步骤一：构建邻接矩阵 W
W[i][j] = 边权重 (0 表示不连通)
W[i][i] = 0 (不允许自环)步骤二：归一化得到概率转移矩阵 P
每一行除以行和：
P[i][j] = W[i][j] / sum(W[i][k] for k in range(n))嗯，这里每个 i 都是有标签的节点。你要注意，P 是 行随机矩阵（row-stochastic），每一行加起来等于 1.0。
举个例子会更好理解。
| 节点 | A | B | C | 说明 |
|---|---|---|---|---|
| A | 0.0 | 0.6 | 0.4 | A连着B和C |
| B | 0.8 | 0.0 | 0.2 | B主要依靠A |
| C | 0.3 | 0.7 | 0.0 | C跟B更亲近 |
我个人习惯，做数据治理项目时会把 P 矩阵打印出来看一眼。有一次做客户画像补全，发现某列几乎全是 0.25…… 后来查出来是数据预处理阶段把相似度搞砸了。记住：P 矩阵要是太均匀，说明特征工程出了问题，标签根本转不动。
4.2 迭代公式与收敛性分析
概率转移矩阵搭建好了，那标签是怎么迭代的？
定义状态向量 F，它是一个 n×C 的矩阵。
- C 是标签类别数
- F[i][c] 表示节点 i 是标签 c 的概率
每次迭代就像这样：
F(t+1) = P · F(t)等等，这里有个致命的绕坑。
如果完全不约束已标注节点，算法会把有标签节点变成“新”的分布。你会看到标签在图上漂移，最后完全变味。
我曾经踩过的坑：做反欺诈标签传播时，没用 clamping 操作，少量人工标注的欺诈样本被邻居的“正常”样本冲淡了，模型把正样本全判成负类。复盘时花了整整两天，才发现 P 矩阵每轮迭代后没把已标注节点固定回来。
正确的做法：加 clamping 约束。
# 伪代码
def iteration(F, P, labeled_indices, Y_labeled):
F_new = P @ F
# 把已标注节点强行拉回真实标签
for idx, label in zip(labeled_indices, Y_labeled):
F_new[idx] = one_hot(label)
return F_new你想想看，为什么 P 的谱半径 ρ(P) = 1，迭代会收敛？
因为 P 是个随机矩阵，它的最大特征值永远是 1。特征值小于 1 的那些分量会指数衰减，最后只剩主导特征向量。加上 clamping，它其实像个交替投影：在约束空间和无约束空间之间来回投影，最终卡在不动点。
收敛速度取决于第二大特征值 λ₂。λ₂ 接近 1，收敛慢；λ₂ 接近 0，两三轮就稳定。这个特性在做图压缩或子采样时尤其重要——我一般要求 λ₂ ≤ 0.85 才上线。
4.3 与随机游走的关系
标签传播和随机游走，本质上是一个硬币的两面。
怎么理解？
假设我们放一个粒子在节点 i 上。它按 P 矩阵的分布随机跳到邻居。这个过程重复 t 步，粒子落在节点 j 的概率就是 P^t[i][j]。
标签传播在做什么？
它在计算：从已标注节点出发的粒子，最终落在未标注节点的概率分布。
如果你把每个标签类别看成一个“吸收态”，那标签传播就是解了一个吸收马尔可夫链的吸收概率问题。
数学上，把节点分成两类：
- labeled set L: 标签已知，充当吸收态
- unlabeled set U: 未知标签，需要预测
转移矩阵分块：
P = [ P_LL P_LU ]
[ P_UL P_UU ]最终的解：
F_U = (I - P_UU)^{-1} · P_UL · F_L这就是随机游走的核心公式。
说白了，标签传播就是无限步随机游走的闭式解迭代版。
实际项目中的应用心法：
- 图规模小（n < 10k）：直接用闭式解算，一步到位，稳定可靠。
- 图规模大（n > 100k）：用迭代法，因为矩阵求逆 O(n³) 扛不住。
- 再大（n > 1M）：考虑近似方法或图采样，否则内存会爆。我曾经用 50 万节点直接算 P_UU 逆，服务器直接 OOM 死机，这是真事。
来，我把这三个概念画张图，帮你理清它们的关系。
从图上你能看到，三块内容其实串联成一个完整链路：构建 P 矩阵 → 迭代/闭式计算 → 最终收敛到吸收概率。
我个人在做数据治理清洗的时候，经常在 P 矩阵构建这一步卡壳。建议你上手项目时，先把邻接矩阵归一化后的行统计打印出来看看——要是整行都是 0，那肯定是预处理漏了数据。
4.4 收敛条件与工程实践
理论上收敛不难证明，但工程上怎么判断“差不多收敛了”？
我是这样做的：
- 计算前后两轮 F 的 Frobenius 范数变化：||F(t+1) - F(t)||_F
- 如果连续 3 轮变化小于 1e-6，视为收敛
- 设置最大迭代轮数（比如 200），防止死循环
import numpy as np
def converged(F_new, F_old, tol=1e-6):
diff = np.linalg.norm(F_new - F_old, 'fro')
return diff < tol
def label_propagation(P, F_init, labeled_idx, Y, max_iter=200, tol=1e-6):
F = F_init.copy()
for i in range(max_iter):
F_old = F.copy()
F = P @ F
# Clamping
for idx, label in zip(labeled_idx, Y):
F[idx] = 0
F[idx, label] = 1.0
if converged(F, F_old, tol):
print(f"收敛于第 {i+1} 轮")
break
return F这个代码我用了很久，基本没出过问题。唯一一次例外，是图中有孤立节点，P 矩阵全零行，乘完 F 直接 NaN。记住：孤立节点事先要处理，或者给它一个均匀分布保底。
大实话：很多教材把收敛性抬得很高深的地位。但真正做数据治理时，迭代法本来就是逐轮推进，收敛是自然结果。真正要下功夫的，反而是 P 矩阵的构建质量——特征选不好，图不对，数学再漂亮也白搭。
简单总结三点：
- 概率转移矩阵：一切的根本，行归一化后必须检查分布质量
- 收敛分析：记住第二大特征值 λ₂ 和 clamping 的作用
- 随机游走视角：帮你理解标签传播的本质，以及何时该用闭式解
把这些数学底子打扎实了，后面讲工程优化、多标签传播、图压缩就顺理成章了。