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

1. 问题背景

图神经网络（GNN）通常需要大量带标签的节点进行监督训练，但在实际应用中（如社交网络、生物网络），获取标签的成本高昂，大多数节点可能无标签。标签传播算法（Label Propagation, LP）是一种半监督学习技术，利用图中已标注节点的标签来预测未标注节点的标签，其核心思想是“相似节点可能具有相同标签”。

2. 算法核心思想

标签传播基于图的平滑性假设（Smoothness Assumption）：在图中相邻或相似的节点倾向于共享相同的标签。算法通过迭代方式将已标注节点的标签信息沿边传播到未标注节点，最终使得整个图的标签分布趋于稳定。

3. 数学建模

设图 \(G=(V, E)\)，其中 \(V\) 是节点集合，分为已标注节点集 \(V_L\) 和未标注节点集 \(V_U\)。每个节点 \(i\) 的标签用向量 \(Y_i\) 表示（例如，对于分类问题，\(Y_i\) 是 one-hot 向量）。算法步骤如下：

步骤1：初始化标签矩阵

• 已标注节点：固定其标签向量 \(Y_i\)（真实标签）。
• 未标注节点：初始标签可设为均匀分布或随机值，记为 \(Y_i^{(0)}\)。

步骤2：构建传播矩阵

定义转移矩阵 \(T\)，其中 \(T_{ij}\) 表示节点 \(j\) 到节点 \(i\) 的标签传播权重，通常基于图的邻接关系：

\[T_{ij} = \frac{A_{ij}}{\sum_{k} A_{ik}} \]

其中 \(A\) 是邻接矩阵（可带权），\(T\) 的每一行和为1，表示标签从邻居节点的加权聚合。

步骤3：迭代传播

每次迭代中，每个节点的标签更新为其邻居节点标签的加权平均，但已标注节点的标签保持不变：

\[Y_i^{(t+1)} = \begin{cases} Y_i & \text{(如果 } i \in V_L \text{)} \\ \sum_{j \in N(i)} T_{ij} Y_j^{(t)} & \text{(如果 } i \in V_U \text{)} \end{cases} \]

其中 \(N(i)\) 是节点 \(i\) 的邻居集合。

步骤4：收敛判断

重复步骤3直到标签变化小于阈值或达到最大迭代次数。未标注节点的最终标签取迭代稳定后的结果。

4. 为什么标签传播会收敛？

将标签矩阵按已标注和未标注分块为 \(Y = [Y_L; Y_U]\)，传播过程可写为线性方程组：

\[Y_U^{(t+1)} = T_{UL} Y_L + T_{UU} Y_U^{(t)} \]

其中 \(T_{UL}\) 和 \(T_{UU}\) 是转移矩阵的分块。该方程的解为：

\[Y_U = (I - T_{UU})^{-1} T_{UL} Y_L \]

当图是连通且非二部图时，\(T_{UU}\) 的谱半径小于1，迭代必收敛。

5. 实际应用中的改进

• 权重设计：邻接矩阵可结合节点相似度（如余弦相似度）加权，增强传播合理性。
• 标签约束：已标注节点的标签在迭代中始终固定，避免信息被稀释。
• 软标签与硬标签：分类问题中，软标签（概率分布）比硬标签（one-hot）更易传播。
• 与GNN结合：现代GNN常将标签传播作为预处理步骤（为未标注节点生成伪标签）或嵌入到模型中（如APPNP算法）。

6. 代码实现简例（Python伪代码）

import numpy as np

def label_propagation(adj_matrix, labels, labeled_indices, max_iters=100, tol=1e-6):
    n_nodes = adj_matrix.shape[0]
    # 初始化标签矩阵（软标签）
    Y = np.random.rand(n_nodes, n_classes)
    Y[labeled_indices] = labels[labeled_indices]  # 固定已标注标签
    
    # 构建转移矩阵 T
    degree = np.sum(adj_matrix, axis=1)
    T = adj_matrix / degree[:, None]
    
    for it in range(max_iters):
        Y_old = Y.copy()
        # 未标注节点更新：Y = T * Y
        Y = T @ Y
        Y[labeled_indices] = labels[labeled_indices]  # 重置已标注标签
        
        if np.linalg.norm(Y - Y_old) < tol:
            break
    return Y

7. 总结

标签传播算法通过图的局部结构传递标签信息，实现半监督学习。其优点是不需要训练参数、计算高效，尤其适用于标注数据稀缺的场景。但它依赖图的平滑性假设，在异质图（相邻节点标签差异大）上效果可能受限。与GNN结合时，可弥补GNN对标签依赖的不足，提升泛化能力。