图神经网络中的标签传播算法（Label Propagation）原理与应用

今天我们来详细讲解图神经网络中的一个基础但非常重要的算法——标签传播算法。这个算法常用于半监督学习任务，特别是在图结构数据中只有少量节点有标签的情况下。我们将从核心思想、数学原理到具体实现逐步展开。

1. 问题场景与核心思想

场景设定

假设我们有一个社交网络图（或论文引用网络），其中：

• 图包含 N 个节点（用户/论文）
• 只有少数节点（如 5%）带有标签（如用户兴趣分类、论文研究领域）
• 大部分节点（95%）没有标签
  我们的目标：预测所有未标记节点的标签。

核心直觉

“物以类聚，人以群分”。在图数据中，相连的节点（邻居）往往具有相似的属性或标签。标签传播就是让已标记节点的标签信息沿着图的边“传播”到未标记节点。

2. 算法形式化描述

2.1 图表示

• 设图 G = (V, E)，其中 V 是节点集（|V| = n），E 是边集。
• 构建对称的邻接矩阵 W ∈ ℝ^{n×n}，其中 W_ij = 1 如果节点 i 和 j 之间有边（或为边的权重），否则为 0。
• 度矩阵 D：对角矩阵，D_ii = Σ_j W_ij（节点 i 的度）。

2.2 标签表示

• 设共有 C 个类别。
• 定义标签矩阵 Y ∈ ℝ^{n×C}：
  • 对于已标记节点 i：Y_i 是 one-hot 向量（如 [0,1,0] 表示属于第 2 类）。
  • 对于未标记节点 i：Y_i = [0,0,...,0]（全零向量）。
• 算法最终输出软标签矩阵 F ∈ ℝ^{n×C}，其中 F_ic 表示节点 i 属于类别 c 的概率。

3. 算法的数学推导（两种视角）

3.1 能量最小化视角（更直观）

定义能量函数（平滑度约束）：
E(F) = ½ Σ_{i,j=1}^n W_ij ||F_i - F_j||²
其中 F_i 是节点 i 的标签向量（行向量）。

直观理解：如果两个节点 i 和 j 之间的边权重 W_ij 很大（强连接），那么我们希望它们的标签向量 F_i 和 F_j 尽可能相似，否则会导致能量 E(F) 增大。算法目标就是找到使 E(F) 最小的 F。

约束条件：已标记节点的标签在传播过程中应保持不变（或变化很小）。即对于已标记节点 i，F_i 应接近初始的 Y_i。

因此，优化问题为：
min_F E(F) + μ Σ_{i∈L} ||F_i - Y_i||²
其中 L 是已标记节点集合，μ 是控制拟合强度的超参数。

3.2 迭代传播视角（具体算法）

更常用的形式是迭代更新公式。对未标记节点 i，其标签更新为邻居节点标签的加权平均：
F_i^{(t+1)} = (Σ_{j∈N(i)} W_ij F_j^{(t)}) / D_ii
其中 N(i) 是节点 i 的邻居集合，t 是迭代次数。

对已标记节点，通常有两种处理方式：

1. 钳制（Clamping）：每个迭代步后，将已标记节点的 F_i 重置为初始 Y_i。
2. 软约束：更新公式中包含原始标签信息。

4. 算法步骤详解

步骤 1：初始化

1. 构建亲和矩阵 W（常使用 RBF 核：W_ij = exp(-||x_i - x_j||² / 2σ²) 如果节点有特征 x，或简单用 0/1）。
2. 计算度矩阵 D（对角矩阵，D_ii = Σ_j W_ij）。
3. 计算归一化的传播矩阵 P = D^{-1}W。
   • 注意：P_ij = W_ij / D_ii，表示从节点 i 到 j 的转移概率。
4. 初始化标签矩阵 F^{(0)}：
   • 已标记节点：F_i = Y_i（one-hot）
   • 未标记节点：F_i = 0 向量

步骤 2：迭代传播

对 t = 0, 1, 2, ... 直到收敛：

1. 执行传播：F^{(t+1)} = P F^{(t)}
   • 这相当于每个节点将当前标签分配给邻居（按边权重比例）。
2. 钳制已标记节点：对所有已标记节点 i，设置 F_i^{(t+1)} = Y_i
3. 检查收敛：如果 ||F^{(t+1)} - F^{(t)}|| < ε，停止。

步骤 3：输出结果

• 对未标记节点 i，取 F_i 中最大值的索引作为预测类别：y_i = argmax_c F_ic

5. 数学性质与收敛性分析

5.1 矩阵形式

将节点分为已标记（L）和未标记（U）两组。将矩阵分块：
P = [P_LL, P_LU; P_UL, P_UU]
F = [F_L; F_U]
Y = [Y_L; 0]

迭代公式可写为：
F_U^{(t+1)} = P_UU F_U^{(t)} + P_UL Y_L
F_L 始终被钳制为 Y_L。

5.2 收敛性证明

可以证明，上述迭代过程收敛到闭式解：
F_U^* = (I - P_UU)^{-1} P_UL Y_L
因为 P_UU 的谱半径 < 1（随机矩阵性质），所以 (I - P_UU) 可逆。

理解：这相当于在未标记节点子图上求解线性方程组，最终标签是已标记节点标签的“平滑”扩散结果。

6. 实际应用与变体

6.1 在GNN中的角色

标签传播常作为：

1. GNN的预处理：为未标记节点生成伪标签，用于训练GNN。
2. GNN的正则化：在GNN损失中加入标签平滑项，强制相邻节点有相似预测。
3. 简单的baseline方法：快速获得半监督分类结果。

6.2 变体算法

1. 个性化PageRank传播：F = (1-α)(I - αP)^{-1} Y，其中 α 是重启概率。
2. 吸收随机游走：将已标记节点视为“吸收态”，未标记节点的标签是随机游走到达各个吸收态的概率。
3. 流形正则化：在深度模型中添加基于图的正则化项。

6.3 超参数选择

• 相似度度量：如何构建 W？常用高斯核、余弦相似度等。
• 图构建：对于非图数据，需要先构建 k-NN 图。
• 收敛阈值 ε：通常 1e-6 到 1e-4。
• 最大迭代次数：防止不收敛时无限循环。

7. 代码实现示意（Python）

import numpy as np

def label_propagation(W, labels, labeled_idx, max_iter=1000, tol=1e-6):
    """
    W: n x n 亲和矩阵（对称）
    labels: n x C 的标签矩阵，未标记行为0
    labeled_idx: 已标记节点的索引列表
    """
    n = W.shape[0]
    D = np.diag(W.sum(axis=1))
    P = np.linalg.inv(D) @ W  # 传播矩阵
    
    F = labels.copy()
    unlabeled_idx = [i for i in range(n) if i not in labeled_idx]
    
    for t in range(max_iter):
        F_old = F.copy()
        
        # 传播步骤
        F = P @ F
        
        # 钳制已标记节点
        F[labeled_idx] = labels[labeled_idx]
        
        # 检查收敛
        if np.linalg.norm(F - F_old) < tol:
            print(f"收敛于迭代 {t}")
            break
    
    # 预测未标记节点
    predictions = np.zeros(n, dtype=int)
    predictions[unlabeled_idx] = np.argmax(F[unlabeled_idx], axis=1)
    
    return predictions, F

8. 优点与局限性

优点：

1. 简单高效：只需矩阵运算，无训练过程。
2. 理论基础强：有清晰的能量最小化解释。
3. 适用于任何图：不依赖节点特征，仅需图结构。

局限性：

1. 仅利用结构信息：忽略节点特征（除非在构建W时考虑）。
2. 同质假设：假设相连节点标签相同，但在异质图中可能不成立。
3. 标签不平衡敏感：如果某类标签很少，可能被淹没。

9. 总结

标签传播算法的核心是基于图结构的平滑性假设，通过迭代让标签信息在图上扩散。它虽然简单，但为理解更复杂的GNN提供了重要基础。在GNN中，消息传递机制可以看作是对标签传播的泛化，其中节点的特征也参与计算，而不仅仅是标签。

掌握标签传播有助于你理解：

1. 图上半监督学习的基本范式
2. 基于能量的图正则化思想
3. GNN中邻居聚合的直观动机

在实际应用中，标签传播常作为快速基线或与其他方法结合，在图数据标注成本高的情况下特别有用。