基于图的半监督学习：图标签传播（Graph Label Propagation）的迭代更新与收敛性分析
字数 4397 2025-12-19 15:49:04

基于图的半监督学习：图标签传播（Graph Label Propagation）的迭代更新与收敛性分析

我将为您讲解一个经典的半监督学习算法，它利用图结构在标记数据极少的情况下，通过已标记节点向未标记节点传播标签信息，以完成分类任务。

1. 问题描述

在现实世界的机器学习任务中，获取大量有标签数据（Labeled Data）通常成本高昂，而获取无标签数据（Unlabeled Data）则相对容易。基于图的半监督学习 旨在利用数据点之间的关系（构图成图），使得少量有标签样本的“信息”能够沿着图的边传播到大量的无标签样本上，从而“带标签”地利用无标签数据，提升模型性能。

核心问题：给定一个数据集，其中只有少数数据点有标签，大部分点无标签。我们如何构建一个图来建模数据点之间的相似性关系，并设计一种高效的算法，使得已知的标签能通过图的结构传播到未知的节点上？

2. 图构建：构建相似性图

在标签传播之前，我们必须先将数据点及其关系表示为一个图 \(G = (V, E)\)。这是算法的基础。

  • 顶点（V）： 每个数据点（无论有标签还是无标签）构成图的一个节点。假设总共有 \(n\) 个数据点，则 \(V = \{v_1, v_2, ..., v_n\}\)。
  • 边（E）与权重（W）： 如果两个节点 \(v_i\) 和 \(v_j\) 是相似的，则在它们之间建立一条边 \(e_{ij}\)。边的强度用一个权重 \(w_{ij}\) 来表示，通常由相似度函数计算得出，值越大表示越相似。
    • 常见构图方法：
      1. ε-近邻图： 如果两点之间的欧氏距离小于阈值 ε，则连边。权重通常设为1（无权图）或与距离相关的函数。
      2. k-近邻图： 为每个点连接与其欧氏距离最近的k个点。这可能导致不对称，通常处理为若 \(v_i\) 是 \(v_j\) 的k近邻，或反之，则连边。
      3. 全连接图： 所有点两两相连。权重通常用高斯（RBF）核函数计算：
        \(w_{ij} = \exp\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)\)
        其中 \(x_i, x_j\) 是节点的特征向量，σ 是控制相似度衰减的带宽参数。这是最常用的方法之一，能够精细刻画所有点对的关系。

构建完成后，我们得到一个对称的权重矩阵 \(W \in \mathbb{R}^{n \times n}\)，其中 \(W_{ij} = w_{ij}\)。

3. 算法目标：定义标签矩阵与传播机制

假设我们有 \(l\) 个有标签样本，\(u\) 个无标签样本（\(n = l + u\)），总共 \(C\) 个类别。

  • 初始标签矩阵 \(Y \in \mathbb{R}^{n \times C}\)：

    • 对于有标签节点 \(i\) (\(1 \leq i \leq l\))，其对应的行向量 \(Y_i\) 是一个独热编码（One-Hot）向量。例如，如果节点i属于第3类，则 \(Y_i = [0, 0, 1, ..., 0]\)。
    • 对于无标签节点 \(i\) (\(l+1 \leq i \leq n\))，其对应的行向量 \(Y_i\) 初始化为全0向量，即 \([0, 0, ..., 0]\)。
    • 这个 \(Y\) 是我们已知的、固定的“真值种子”。

  • 待学习的软标签矩阵 \(F \in \mathbb{R}^{n \times C}\)：

    • 矩阵 \(F\) 的每一行 \(F_i\) 表示节点 \(i\) 属于各个类别的概率（或置信度、成员度）。
    • 我们的目标就是通过学习，为所有节点（尤其无标签节点）计算出这个 \(F\) 矩阵。最终，节点 \(i\) 的预测类别就是 \(\arg\max_j F_{ij}\)。

  • 传播的核心思想：
    直观上，一个节点的新标签，应该由其邻居节点的当前标签的加权平均来决定。相似度越高的邻居，其标签对该节点的影响应该越大。这很像社交网络中，一个人的观点会受到其朋友群体的影响。

4. 算法过程：迭代传播

标签传播算法（Label Propagation）通过迭代更新 \(F\) 来实现信息的传播。其更新规则非常简洁优雅。

步骤1：计算归一化（或正则化）的传播矩阵

为了使得每次更新后的标签分布仍然是合理的概率分布，我们需要对权重矩阵 \(W\) 进行归一化处理。最常用的是计算对称归一化的拉普拉斯矩阵相关的传播矩阵：

\[S = D^{-\frac{1}{2}} W D^{-\frac{1}{2}} \]

其中 \(D\) 是一个对角矩阵，称为度矩阵，其对角线元素 \(D_{ii} = \sum_{j=1}^{n} w_{ij}\)，即节点 i 所有边的权重之和。
矩阵 \(S\) 是对称的、双随机的（每行和每列的和均为1）。它的元素 \(S_{ij}\) 可以解释为从节点 j 到节点 i 的归一化“转移概率”或“影响力”。

步骤2：初始化软标签矩阵
将待学习的 \(F^{(0)}\) 初始化为初始标签矩阵 \(Y\)。

\[F^{(0)} = Y \]

注意，此时无标签节点的行仍然是0。

步骤3：迭代更新
在每次迭代 \(t\) 中，执行以下更新：

\[F^{(t+1)} = \alpha S F^{(t)} + (1-\alpha) Y \]

我们来拆解这个公式：

  1. \(\alpha S F^{(t)}\)：这是传播项。每个节点从所有邻居那里收集标签信息（\(S F^{(t)}\) 相当于一次平滑操作），并用一个传播系数 \(\alpha\) （通常 \(0 < \alpha < 1\)，如0.99）来控制传播的强度。这一步让无标签节点从邻居那里获得标签信息，也让有标签节点被邻居“微调”。
  2. \((1-\alpha) Y\)：这是锚定项或保真项。它像一个“拉力”，将有标签节点的预测 \(F\) 拉回其真实标签 \(Y\)。系数 \((1-\alpha)\) 控制了这种拉力的强度。这确保了在传播过程中，有标签节点的标签不会被完全“淹没”，算法最终会收敛到一个平衡点。

步骤4：判断收敛
重复步骤3，直到 \(F\) 的变化小于一个很小的阈值 \(\epsilon\)，即 \(\| F^{(t+1)} - F^{(t)} \| < \epsilon\)，或者达到预设的最大迭代次数。

步骤5：得到最终标签
算法收敛后，我们得到最终的软标签矩阵 \(F^{*}\)。

  • 对于每个节点 i，其预测类别为：\(y_i = \arg\max_j F^{*}_{ij}\)。

5. 收敛性分析：为什么算法能收敛？

这是一个非常关键的数学保证。让我们分析迭代公式：

\[F^{(t+1)} = \alpha S F^{(t)} + (1-\alpha) Y \]

这是一个线性迭代系统。我们可以将其视为不动点迭代。

假设算法收敛到 \(F^{*}\)，那么在极限情况下有：

\[F^{*} = \alpha S F^{*} + (1-\alpha) Y \]

整理后得到：

\[(I - \alpha S) F^{*} = (1-\alpha) Y \]

这是一个关于 \(F^{*}\) 的线性方程组。由于 \(0 < \alpha < 1\)，且 \(S\) 的最大特征值为1（行随机矩阵的性质），矩阵 \((I - \alpha S)\) 是严格对角占主的，因此是可逆的。这意味着该线性系统有唯一解：

\[F^{*} = (1-\alpha)(I - \alpha S)^{-1} Y \]

这个封闭解说明：

  1. 收敛性：迭代过程必定收敛到这个唯一的 \(F^{*}\)，与初始 \(F^{(0)}\) 无关（虽然我们初始化为 \(Y\)）。
  2. 解的直观解释：最终的解 \(F^{*}\) 是初始标签 \(Y\) 在图上经过无限次平滑（由矩阵 \((I - \alpha S)^{-1}\) 实现）后的结果。这就像一个扩散过程，标签信息从有标签节点出发，随着迭代次数趋于无穷，传播到图的每一个角落。

在迭代过程中，无标签节点（初始 \(F\) 为0）的标签值完全从邻居的传播中获得，而有标签节点的标签值则是邻居传播来的信息和其自身真实标签的加权平均。参数 \(\alpha\) 平衡了“相信图结构”和“相信原始标签”之间的信任程度。

6. 总结与扩展

核心贡献：图标签传播算法以一种直观、优雅且数学上有保障的方式，将半监督学习问题转化为图上的标签传播与平衡问题。其核心优势在于利用了数据的流形（几何）结构，而不仅仅是特征空间中的点坐标。

关键步骤回顾：

  1. 构图： 将数据点及其相似性表示为带权图（邻接矩阵 \(W\)）。
  2. 归一化： 计算归一化传播矩阵 \(S = D^{-1/2} W D^{-1/2}\)。
  3. 初始化： 构造初始标签矩阵 \(Y\) 和软标签矩阵 \(F\)。
  4. 迭代： 反复执行 \(F \leftarrow \alpha S F + (1-\alpha) Y\)，直到收敛。
  5. 解码： 取 \(F^{*}\) 中每一行最大值的索引作为节点的预测类别。

算法变体：

  • 高斯随机场与调和函数： 可以将此问题视为在图上求解调和函数，其中已知标签的点是边界条件。标签传播的解是这个调和函数的最小能量解。
  • 吸收随机游走： 想象一个粒子从某个无标签节点出发，在图上随机游走。它以概率 \(\alpha\) 跳到邻居节点，以概率 \((1-\alpha)\) 被“吸收”回某个有标签节点（其标签即为该节点的真实类别）。最终粒子被吸收时所在的有标签节点的类别，就可以作为无标签节点的预测类别。标签传播的解恰好是这种随机游走的稳态概率。

局限性：

  • 效果严重依赖于图构建的质量。相似性度量和参数（如高斯核的σ）需要仔细选择。
  • 假设同类样本在特征空间中是连通的，即“聚类假设”。如果不同类别的样本在图中紧密相连，传播会出错。

这个算法清晰地展示了如何将数据结构与迭代计算结合，为解决“标记数据稀缺”这一普遍性问题提供了一个强大的工具。

基于图的半监督学习：图标签传播（Graph Label Propagation）的迭代更新与收敛性分析 我将为您讲解一个经典的半监督学习算法，它利用图结构在标记数据极少的情况下，通过已标记节点向未标记节点传播标签信息，以完成分类任务。 1. 问题描述 在现实世界的机器学习任务中，获取大量有标签数据（Labeled Data）通常成本高昂，而获取无标签数据（Unlabeled Data）则相对容易。 基于图的半监督学习 旨在利用数据点之间的关系（构图成图），使得少量有标签样本的“信息”能够沿着图的边传播到大量的无标签样本上，从而“带标签”地利用无标签数据，提升模型性能。 核心问题 ：给定一个数据集，其中只有少数数据点有标签，大部分点无标签。我们如何构建一个图来建模数据点之间的相似性关系，并设计一种高效的算法，使得已知的标签能通过图的结构传播到未知的节点上？ 2. 图构建：构建相似性图 在标签传播之前，我们必须先将数据点及其关系表示为一个图 \( G = (V, E) \)。这是算法的基础。 顶点（V） ： 每个数据点（无论有标签还是无标签）构成图的一个节点。假设总共有 \( n \) 个数据点，则 \( V = \{v_ 1, v_ 2, ..., v_ n\} \)。 边（E）与权重（W） ： 如果两个节点 \( v_ i \) 和 \( v_ j \) 是相似的，则在它们之间建立一条边 \( e_ {ij} \)。边的强度用一个 权重 \( w_ {ij} \) 来表示，通常由相似度函数计算得出，值越大表示越相似。 常见构图方法 ： ε-近邻图 ： 如果两点之间的欧氏距离小于阈值 ε，则连边。权重通常设为1（无权图）或与距离相关的函数。 k-近邻图 ： 为每个点连接与其欧氏距离最近的k个点。这可能导致不对称，通常处理为若 \( v_ i \) 是 \( v_ j \) 的k近邻，或反之，则连边。 全连接图 ： 所有点两两相连。权重通常用高斯（RBF）核函数计算： \( w_ {ij} = \exp\left(-\frac{\|x_ i - x_ j\|^2}{2\sigma^2}\right) \) 其中 \( x_ i, x_ j \) 是节点的特征向量，σ 是控制相似度衰减的带宽参数。这是最常用的方法之一，能够精细刻画所有点对的关系。 构建完成后，我们得到一个 对称的权重矩阵 \( W \in \mathbb{R}^{n \times n} \)，其中 \( W_ {ij} = w_ {ij} \)。 3. 算法目标：定义标签矩阵与传播机制 假设我们有 \( l \) 个有标签样本，\( u \) 个无标签样本（\( n = l + u \)），总共 \( C \) 个类别。 初始标签矩阵 \( Y \in \mathbb{R}^{n \times C} \)： 对于有标签节点 \( i \) (\( 1 \leq i \leq l \))，其对应的行向量 \( Y_ i \) 是一个 独热编码 （One-Hot）向量。例如，如果节点i属于第3类，则 \( Y_ i = [ 0, 0, 1, ..., 0 ] \)。 对于无标签节点 \( i \) (\( l+1 \leq i \leq n \))，其对应的行向量 \( Y_ i \) 初始化为全0向量，即 \( [ 0, 0, ..., 0 ] \)。 这个 \( Y \) 是我们已知的、固定的“真值种子”。 待学习的软标签矩阵 \( F \in \mathbb{R}^{n \times C} \)： 矩阵 \( F \) 的每一行 \( F_ i \) 表示节点 \( i \) 属于各个类别的 概率 （或置信度、成员度）。 我们的目标就是通过学习，为所有节点（尤其无标签节点）计算出这个 \( F \) 矩阵。最终，节点 \( i \) 的预测类别就是 \( \arg\max_ j F_ {ij} \)。 传播的核心思想 ： 直观上，一个节点的新标签，应该由其邻居节点的当前标签的加权平均来决定。 相似度越高的邻居，其标签对该节点的影响应该越大 。这很像社交网络中，一个人的观点会受到其朋友群体的影响。 4. 算法过程：迭代传播 标签传播算法（Label Propagation）通过迭代更新 \( F \) 来实现信息的传播。其更新规则非常简洁优雅。 步骤1：计算归一化（或正则化）的传播矩阵 为了使得每次更新后的标签分布仍然是合理的概率分布，我们需要对权重矩阵 \( W \) 进行归一化处理。最常用的是计算 对称归一化的拉普拉斯矩阵 相关的传播矩阵： \[ S = D^{-\frac{1}{2}} W D^{-\frac{1}{2}} \] 其中 \( D \) 是一个对角矩阵，称为 度矩阵 ，其对角线元素 \( D_ {ii} = \sum_ {j=1}^{n} w_ {ij} \)，即节点 i 所有边的权重之和。 矩阵 \( S \) 是 对称的、双随机的 （每行和每列的和均为1）。它的元素 \( S_ {ij} \) 可以解释为从节点 j 到节点 i 的归一化“转移概率”或“影响力”。 步骤2：初始化软标签矩阵 将待学习的 \( F^{(0)} \) 初始化为初始标签矩阵 \( Y \)。 \[ F^{(0)} = Y \] 注意，此时无标签节点的行仍然是0。 步骤3：迭代更新 在每次迭代 \( t \) 中，执行以下更新： \[ F^{(t+1)} = \alpha S F^{(t)} + (1-\alpha) Y \] 我们来拆解这个公式： \( \alpha S F^{(t)} \)：这是 传播项 。每个节点从所有邻居那里收集标签信息（\( S F^{(t)} \) 相当于一次平滑操作），并用一个 传播系数 \( \alpha \) （通常 \( 0 < \alpha < 1 \)，如0.99）来控制传播的强度。这一步让无标签节点从邻居那里获得标签信息，也让有标签节点被邻居“微调”。 \( (1-\alpha) Y \)：这是 锚定项 或 保真项 。它像一个“拉力”，将有标签节点的预测 \( F \) 拉回其真实标签 \( Y \)。系数 \( (1-\alpha) \) 控制了这种拉力的强度。这确保了在传播过程中，有标签节点的标签不会被完全“淹没”，算法最终会收敛到一个平衡点。 步骤4：判断收敛 重复步骤3，直到 \( F \) 的变化小于一个很小的阈值 \( \epsilon \)，即 \( \| F^{(t+1)} - F^{(t)} \| < \epsilon \)，或者达到预设的最大迭代次数。 步骤5：得到最终标签 算法收敛后，我们得到最终的软标签矩阵 \( F^{* } \)。 对于每个节点 i，其预测类别为：\( y_ i = \arg\max_ j F^{* }_ {ij} \)。 5. 收敛性分析：为什么算法能收敛？ 这是一个非常关键的数学保证。让我们分析迭代公式： \[ F^{(t+1)} = \alpha S F^{(t)} + (1-\alpha) Y \] 这是一个 线性迭代系统 。我们可以将其视为不动点迭代。 假设算法收敛到 \( F^{ } \)，那么在极限情况下有： \[ F^{ } = \alpha S F^{ } + (1-\alpha) Y \] 整理后得到： \[ (I - \alpha S) F^{ } = (1-\alpha) Y \] 这是一个关于 \( F^{ } \) 的线性方程组。由于 \( 0 < \alpha < 1 \)，且 \( S \) 的最大特征值为1（行随机矩阵的性质），矩阵 \( (I - \alpha S) \) 是严格对角占主的，因此是 可逆的 。这意味着该线性系统有 唯一解 ： \[ F^{ } = (1-\alpha)(I - \alpha S)^{-1} Y \] 这个封闭解说明： 收敛性 ：迭代过程必定收敛到这个唯一的 \( F^{* } \)，与初始 \( F^{(0)} \) 无关（虽然我们初始化为 \( Y \)）。 解的直观解释 ：最终的解 \( F^{* } \) 是初始标签 \( Y \) 在图上经过无限次平滑（由矩阵 \( (I - \alpha S)^{-1} \) 实现）后的结果。这就像一个扩散过程，标签信息从有标签节点出发，随着迭代次数趋于无穷，传播到图的每一个角落。 在迭代过程中，无标签节点（初始 \( F \) 为0）的标签值完全从邻居的传播中获得，而有标签节点的标签值则是邻居传播来的信息和其自身真实标签的加权平均。参数 \( \alpha \) 平衡了“相信图结构”和“相信原始标签”之间的信任程度。 6. 总结与扩展 核心贡献 ：图标签传播算法以一种直观、优雅且数学上有保障的方式，将半监督学习问题转化为图上的标签传播与平衡问题。其核心优势在于 利用了数据的流形（几何）结构 ，而不仅仅是特征空间中的点坐标。 关键步骤回顾 ： 构图 ： 将数据点及其相似性表示为带权图（邻接矩阵 \( W \)）。 归一化 ： 计算归一化传播矩阵 \( S = D^{-1/2} W D^{-1/2} \)。 初始化 ： 构造初始标签矩阵 \( Y \) 和软标签矩阵 \( F \)。 迭代 ： 反复执行 \( F \leftarrow \alpha S F + (1-\alpha) Y \)，直到收敛。 解码 ： 取 \( F^{* } \) 中每一行最大值的索引作为节点的预测类别。 算法变体 ： 高斯随机场与调和函数 ： 可以将此问题视为在图上求解调和函数，其中已知标签的点是边界条件。标签传播的解是这个调和函数的最小能量解。 吸收随机游走 ： 想象一个粒子从某个无标签节点出发，在图上随机游走。它以概率 \( \alpha \) 跳到邻居节点，以概率 \( (1-\alpha) \) 被“吸收”回某个有标签节点（其标签即为该节点的真实类别）。最终粒子被吸收时所在的有标签节点的类别，就可以作为无标签节点的预测类别。标签传播的解恰好是这种随机游走的稳态概率。 局限性 ： 效果严重依赖于 图构建的质量 。相似性度量和参数（如高斯核的σ）需要仔细选择。 假设 同类样本在特征空间中是连通的 ，即“聚类假设”。如果不同类别的样本在图中紧密相连，传播会出错。 这个算法清晰地展示了如何将数据结构与迭代计算结合，为解决“标记数据稀缺”这一普遍性问题提供了一个强大的工具。