基于图的半监督学习：最小割（Min-Cut）算法的原理与图划分过程

题目描述

在许多机器学习任务中，获取大量有标签的数据（例如，图像类别、文本情感、蛋白质功能）成本高昂且耗时，而未标签的数据则相对容易获取。半监督学习的目标是同时利用少量有标签数据和大量无标签数据来训练模型，以提高学习性能。基于图的半监督学习是其中一类重要方法，它将所有数据点（有标签和无标签）视为图中的节点，节点之间的相似性（或关系）用边的权重表示，从而将学习问题转化为一个图上的优化问题。

最小割（Min-Cut）算法是这类方法的一个经典代表。其核心思想是：将已标记的样本作为“种子”，利用图的结构信息，通过最小化一个与图割相关的目标函数，将标签从有标签节点“传播”到无标签节点，从而对整个图进行划分（例如，二分类或多分类）。这个过程可以直观地理解为：在连接不同标签节点的边权重很“弱”的地方（即相似性很低），切割图，使得相同标签的节点尽量在同一子图内，不同标签的节点分属不同子图。

接下来，我将循序渐进地讲解最小割算法的原理、数学形式、求解过程及其直观含义。

第一步：问题定义与图构造

假设我们有 \(n\) 个数据点，其中前 \(l\) 个点有标签（假设为二分类，标签为 +1 或 -1），剩下的 \(u = n - l\) 个点无标签。我们的目标是为所有无标签点预测标签。

1. 构造图：
   • 每个数据点（无论有无标签）对应图中的一个节点。
   • 在任意两个节点 \(i\) 和 \(j\) 之间，我们定义边的权重 \(w_{ij}\)。权重通常反映了两个数据点之间的相似性。一种常见的高斯核函数定义为：

\[ w_{ij} = \exp\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right) \]

    其中 $ x_i $ 是数据点的特征向量，$ \sigma $ 是控制相似度衰减速度的带宽参数。当 $ i = j $ 时，我们通常令 $ w_{ii} = 0 $。如果相似度很低，也可以直接将权重设为 0，得到一个稀疏图。

2. 数学表达：
   • 用 \(n \times n\) 的对称矩阵 \(W\) 表示权重矩阵，其元素为 \(w_{ij}\)。
   • 用 \(n \times n\) 的对角矩阵 \(D\) 表示度矩阵，其对角线元素 \(d_{ii} = \sum_{j=1}^{n} w_{ij}\)，表示节点 \(i\) 与其他所有节点的总连接强度。

第二步：最小割问题的形式化

我们的目标是将图中的节点划分为两个集合：\(S\) (预测标签为 +1) 和 \(T\) (预测标签为 -1)。对于一个理想的划分：

• 有标签节点的约束必须满足：有标签的 +1 节点必须在 \(S\) 中，有标签的 -1 节点必须在 \(T\) 中。
• 划分应该尽可能“自然”：我们希望连接 \(S\) 和 \(T\) 两个集合的边的总权重尽可能小。因为这些边连接了我们认为“不同”的类，如果它们权重很大，意味着两个本应分开的类之间有很多强连接，这与我们的分类目标矛盾。

“连接两个集合的边的总权重”在图中称为 割 (Cut)。对于二分类，割的定义是：

\[\text{Cut}(S, T) = \sum_{i \in S, j \in T} w_{ij} \]

我们的目标就是在满足标签约束的前提下，找到使 \(\text{Cut}(S, T)\) 最小的划分 \((S, T)\)。这就是最小割问题。

第三步：引入指示变量与目标函数转换

为了用数学优化来描述这个问题，我们为每个节点 \(i\) 引入一个指示变量 \(f_i \in \{-1, +1\}\)，表示其预测标签。所有节点的预测标签构成向量 \(f = [f_1, f_2, ..., f_n]^T\)。

1. 标签约束：

   • 对于有标签节点 \(i\) (假设 \(1 \le i \le l\))，其真实标签 \(y_i \in \{-1, +1\}\) 是已知的。因此，我们必须有 \(f_i = y_i\)。

2. 割的表示：

   • 注意，当 \(f_i\) 和 \(f_j\) 符号不同时（即一个在 \(S\)，一个在 \(T\)），它们之间的边被计入割。观察发现：

\[ \frac{1}{4}(f_i - f_j)^2 = \begin{cases} 1, & \text{if } f_i \ne f_j \\ 0, & \text{if } f_i = f_j \end{cases} \]

*   因此，割可以用指示向量表示为：

\[ \text{Cut}(S, T) = \sum_{i=1}^n \sum_{j=1}^n w_{ij} \cdot \frac{1}{4}(f_i - f_j)^2 \]

3. 目标函数：
   • 最小割问题等价于求解以下优化问题：

\[ \min_{f \in \{-1, +1\}^n} \quad \frac{1}{4} \sum_{i=1}^n \sum_{j=1}^n w_{ij} (f_i - f_j)^2 \]

\[ \text{subject to} \quad f_i = y_i, \quad i = 1, ..., l \]

第四步：目标函数的化简与连续松弛

直接求解上述离散（\(f_i \in \{-1, +1\}\)）优化问题通常是 NP-Hard 的。一个关键的技巧是进行连续松弛：我们暂时放宽约束，允许 \(f_i\) 为任意实数，并在问题求解后，再通过符号函数（例如，\(\text{sign}(f_i)\)）将其映射回离散标签。松弛后的问题是凸的，更容易求解。

1. 化简目标函数：
   • 展开目标函数中的平方项：

\[ \begin{aligned} \sum_{i,j} w_{ij} (f_i - f_j)^2 &= \sum_{i,j} w_{ij} f_i^2 + \sum_{i,j} w_{ij} f_j^2 - 2\sum_{i,j} w_{ij} f_i f_j \\ &= 2\sum_i d_{ii} f_i^2 - 2\sum_{i,j} w_{ij} f_i f_j \\ &= 2(f^T D f - f^T W f) \\ &= 2f^T (D - W) f \end{aligned} \]

*   这里 $ d_{ii} = \sum_j w_{ij} $ 是度矩阵 $ D $ 的对角元。矩阵 $ L = D - W $ 是图的**非归一化拉普拉斯矩阵** (Unnormalized Graph Laplacian)。
*   因此，目标函数（忽略常数因子）可以写为：

\[ \min_{f} \quad f^T L f \]

2. 松弛后的问题：
   • 将离散约束松弛为连续约束后，并加入有标签点的硬约束，我们得到以下优化问题：

\[ \min_{f \in \mathbb{R}^n} \quad f^T L f \]

\[ \text{subject to} \quad f_i = y_i, \quad i = 1, ..., l \]

第五步：求解松弛问题

我们通过拉格朗日乘子法来求解这个带等式约束的凸二次规划问题。但这里有一个更直接的求解视角。

1. 分块表示：
   • 将向量 \(f\) 按照“有标签”（前 \(l\) 个）和“无标签”（后 \(u\) 个）分块：

\[ f = \begin{bmatrix} f_l \\ f_u \end{bmatrix} \]

    其中 $ f_l \in \mathbb{R}^l $ 是已知的（等于真实标签向量 $ y_l $），$ f_u \in \mathbb{R}^u $ 是待求的。
*   将拉普拉斯矩阵 $ L $ 也做相应的分块：

\[ L = \begin{bmatrix} L_{ll} & L_{lu} \\ L_{ul} & L_{uu} \end{bmatrix} \]

    其中 $ L_{ul} = L_{lu}^T $。

2. 代入目标函数：
   • 将分块形式代入 \(f^T L f\)：

\[ f^T L f = [f_l^T, f_u^T] \begin{bmatrix} L_{ll} & L_{lu} \\ L_{ul} & L_{uu} \end{bmatrix} \begin{bmatrix} f_l \\ f_u \end{bmatrix} = f_l^T L_{ll} f_l + 2f_u^T L_{ul} f_l + f_u^T L_{uu} f_u \]

*   由于 $ f_l = y_l $ 是固定的常数向量，目标函数优化只与 $ f_u $ 有关。我们可以将前两项视为常数，因此优化问题等价于：

\[ \min_{f_u \in \mathbb{R}^u} \quad 2f_u^T (L_{ul} y_l) + f_u^T L_{uu} f_u \]

3. 求导求解：
   • 这是一个关于 \(f_u\) 的无约束凸二次优化问题。对 \(f_u\) 求导并令其为零：

\[ \frac{\partial}{\partial f_u} \left( 2f_u^T (L_{ul} y_l) + f_u^T L_{uu} f_u \right) = 2L_{ul} y_l + 2L_{uu} f_u = 0 \]

*   整理得到关键性的线性方程组：

\[ L_{uu} f_u = -L_{ul} y_l \]

*   由于 $ L $ 是半正定矩阵，其子矩阵 $ L_{uu} $ 是正定的（在连通图中），因此该线性方程组有唯一解。我们可以通过高效的线性系统求解器（如共轭梯度法）得到 $ f_u $。

第六步：得到最终预测标签

1. 求解：计算 \(f_u = L_{uu}^{-1} (-L_{ul} y_l)\)。
2. 离散化：对于无标签节点 \(i\) (\(i > l\))，得到连续的实数值 \(f_i\)。然后，通过符号函数进行离散化，得到最终的类别预测：

\[ \hat{y}_i = \text{sign}(f_i) = \begin{cases} +1, & \text{if } f_i > 0 \\ -1, & \text{if } f_i < 0 \end{cases} \]

（如果 $ f_i = 0 $，可以随机分配或根据领域知识处理。）

总结与直观理解

• 原理核心：最小割算法的目标是找到一个划分，使得跨越不同类别的“连接强度”（即边的权重总和）最小。这符合我们的直觉：相似（权重高）的点应该属于同一类。
• 松弛的作用：将离散的整数规划问题松弛为连续的二次规划问题，使其变得可高效求解。解出的连续值 \(f_i\) 可以视为节点属于 +1 类的“置信度”或“倾向性”。
• 解的物理解释：方程组 \(L_{uu} f_u = -L_{ul} y_l\) 可以看作是在无标签节点上施加了一个调和条件 (Harmonic Condition)。可以证明，在无标签节点上，解 \(f_u\) 满足：每个无标签节点的预测值 \(f_i\)，是其所有邻居节点预测值的加权平均。这意味着标签信息沿着图中权重高的边（相似性高的连接）平滑地传播出去。
• 与随机游走的关系：这个“加权平均”的性质与图上随机游走的平衡态有关。从任意一个无标签节点出发随机游走，第一次碰到一个有标签节点时，这个有标签节点的标签就是我们对起始节点的预测。最小割的解在概率意义上近似于这个随机游走过程的稳态。
• 扩展：以上是二分类的情况。对于多分类（C个类），可以为每个类别定义一组指示变量（或称为“类别成员函数”），然后为每个类别独立求解一个类似的最小割问题，或者求解一个与归一化割（Normalized Cut）相关的、同时考虑所有类别的更复杂的目标函数。

至此，您已经了解了基于图的最小割半监督学习算法的完整原理、严谨的数学推导以及其直观的“标签传播”和“图划分”含义。