基于图的半监督学习：最小割（Min-Cut）算法的原理与图划分过程
字数 4190 2025-12-07 16:46:58

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

题目描述

假设我们有一张无向加权图 \(G = (V, E)\)，其中节点集 \(V\) 包含少量已标记的节点（已知类别标签）和大量未标记的节点，边的权重表示节点之间的相似度。目标是根据图的拓扑结构和已标记信息，为所有未标记节点预测类别标签，使得同一类别内部的节点连接紧密，不同类别之间的连接尽可能弱。这可以形式化为一个图划分问题：在满足已标记节点约束的前提下，将图划分为若干个子集（每个子集对应一个类别），并最小化子集之间的边权重之和（即割的大小）。最小割算法即为求解该目标的一种经典方法。

解题过程

1. 问题形式化

  • 设节点集 \(V = \{v_1, v_2, \dots, v_n\}\)，其中前 \(l\) 个节点已标记，其余 \(u = n - l\) 个节点未标记。假设共有 \(C\) 个类别，用集合 \(\{1, 2, \dots, C\}\) 表示。
  • 定义权重矩阵 \(W \in \mathbb{R}^{n \times n}\)，其中 \(W_{ij} \geq 0\) 表示节点 \(v_i\) 与 \(v_j\) 之间的相似度（权重），若两节点无边则 \(W_{ij} = 0\)。通常 \(W\) 对称。
  • 设节点标签向量为 \(y \in \{1, 2, \dots, C\}^n\)，其中前 \(l\) 个元素已知，后 \(u\) 个元素待求。

最小割的目标是：将节点划分为 \(C\) 个互不相交的子集 \(V_1, V_2, \dots, V_C\)，满足已标记节点的类别约束（例如，已标记为类别 \(c\) 的节点必须属于 \(V_c\)），并最小化割函数（cut）：

\[\text{Cut}(V_1, \dots, V_C) = \frac{1}{2} \sum_{c=1}^C \sum_{i \in V_c, j \notin V_c} W_{ij}, \]

其中系数 \(1/2\) 是因为每条边在求和时被计算了两次。最小化该割函数意味着不同类别之间的相似度（即边权重）总和尽可能小，从而促使同一类别内部的节点连接更强。

2. 将多类问题转化为多个二分类问题

通常采用一对多策略：每次将一个类别与其他所有类别区分开。假设当前考虑类别 \(c\)，定义二分类标签向量 \(f \in \{-1, +1\}^n\)：

  • 若 \(y_i = c\)，则 \(f_i = +1\)；
  • 若 \(y_i \neq c\)，则 \(f_i = -1\)；
  • 未标记节点的 \(f_i\) 待求。

对于已标记节点，\(f_i\) 已知。于是，最小割的目标转化为：在满足已标记节点 \(f_i\) 值固定的前提下，最小化类别 \(c\) 与其补集之间的割：

\[\text{Cut}(c) = \sum_{i: f_i = +1, \; j: f_j = -1} W_{ij}. \]

可以证明，该割函数可写成二次形式：

\[\text{Cut}(c) = \frac{1}{4} \sum_{i,j} W_{ij} (f_i - f_j)^2 = \frac{1}{2} f^T L f, \]

其中 \(L = D - W\) 是图的拉普拉斯矩阵，\(D\) 为度矩阵（对角阵，\(D_{ii} = \sum_j W_{ij}\)）。这里利用了 \(f_i^2 = 1\) 和 \(L\) 的性质。

于是，对每个类别 \(c\)，我们求解如下约束优化问题：

\[\min_{f \in \{-1, +1\}^n} f^T L f \quad \text{s.t.} \quad f_i = \begin{cases} +1, & \text{若 } y_i = c \text{ 且 } i \text{ 已标记} \\ -1, & \text{若 } y_i \neq c \text{ 且 } i \text{ 已标记} \end{cases}. \]

3. 连续松弛与求解

由于上述问题是离散的（\(f_i = \pm 1\)），求解是 NP 难的。常用连续松弛：将 \(f\) 的取值范围放松到实数域，即 \(f \in \mathbb{R}^n\)，但保留已标记节点的约束值（\(+1\) 或 \(-1\)）。松弛后的问题为：

\[\min_{f \in \mathbb{R}^n} f^T L f \quad \text{s.t.} \quad f_i = \begin{cases} +1, & \text{若 } y_i = c \text{ 且 } i \text{ 已标记} \\ -1, & \text{若 } y_i \neq c \text{ 且 } i \text{ 已标记} \end{cases}. \]

这是一个带等式约束的凸二次优化问题，可解析求解。

将节点排序，使前 \(l\) 个为已标记节点，后 \(u\) 个为未标记节点。将 \(f\) 和 \(L\) 分块：

\[f = \begin{bmatrix} f_l \\ f_u \end{bmatrix}, \quad L = \begin{bmatrix} L_{ll} & L_{lu} \\ L_{ul} & L_{uu} \end{bmatrix}. \]

其中 \(f_l \in \mathbb{R}^l\) 已知（为 \(+1\) 或 \(-1\)），\(f_u \in \mathbb{R}^u\) 未知。目标函数展开：

\[f^T L f = [f_l^T \quad 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 + 2 f_u^T L_{ul} f_l + f_u^T L_{uu} f_u. \]

对 \(f_u\) 求导并令导数为零：

\[\frac{\partial}{\partial f_u} (f^T L f) = 2 L_{ul} f_l + 2 L_{uu} f_u = 0 \quad \Rightarrow \quad L_{uu} f_u = - L_{ul} f_l. \]

由于 \(L_{uu}\) 是正定矩阵（在连通图中），可求解线性方程组得到 \(f_u\)：

\[f_u = - L_{uu}^{-1} L_{ul} f_l. \]

解出 \(f_u\) 后，每个元素是一个实数，其符号表示类别归属：若 \(f_i > 0\)，则将节点 \(i\) 划为类别 \(c\)；若 \(f_i < 0\)，则不属于类别 \(c\)。

4. 多类别预测

对每个类别 \(c = 1, 2, \dots, C\)，重复步骤 2-3，得到 \(C\) 个实值向量 \(f^{(c)}\)（每个向量对应一个“类别 vs 其余”的划分）。对于未标记节点 \(i\)，比较它在所有 \(C\) 个向量中的值 \(f_i^{(c)}\)，将节点 \(i\) 分配给值最大的类别：

\[\hat{y}_i = \arg\max_{c} f_i^{(c)}. \]

因为 \(f_i^{(c)}\) 表示节点 \(i\) 与类别 \(c\) 的“关联强度”，最大值对应的类别即为最可能的类别。

5. 算法总结

输入：图权重矩阵 \(W\)，已标记节点的标签 \(y_1, \dots, y_l\)（共 \(C\) 类）。
输出：所有节点的预测标签 \(\hat{y}\)。

  1. 计算度矩阵 \(D\)（对角阵，\(D_{ii} = \sum_j W_{ij}\)）和拉普拉斯矩阵 \(L = D - W\)。
  2. 对每个类别 \(c = 1, 2, \dots, C\)：
    • 构建二分类标签向量 \(f_l \in \{-1, +1\}^l\)：若已标记节点 \(i\) 属于类别 \(c\)，则 \(f_{l,i} = +1\)；否则为 \(-1\)。
    • 将 \(L\) 分块为 \(L = \begin{bmatrix} L_{ll} & L_{lu} \\ L_{ul} & L_{uu} \end{bmatrix}\)，其中下标 \(l\) 对应已标记节点，\(u\) 对应未标记节点。
    • 解线性方程组 \(L_{uu} f_u^{(c)} = - L_{ul} f_l\)，得到 \(f_u^{(c)}\)。
    • 令 \(f^{(c)} = [f_l; f_u^{(c)}]\)。
  3. 对每个未标记节点 \(i\)，计算 \(\hat{y}_i = \arg\max_c f_i^{(c)}\)。

关键点说明

  • 为什么用拉普拉斯矩阵：\(f^T L f = \frac{1}{2} \sum_{i,j} W_{ij} (f_i - f_j)^2\) 直观衡量了不同类别之间边的差异。当 \(f_i\) 和 \(f_j\) 异号时，该项贡献较大，最小化它相当于减少跨类别的边权重和。
  • 连续松弛的合理性：松弛后的问题在实数域是凸的，有唯一解。尽管放松了离散约束，但解通常呈现“同类节点值相近、不同类节点值符号相反”的特性，符号可直接用于分类。
  • 与标签传播的关系：最小割的解等价于在图上用调和函数（harmonic function）做插值，其满足“未标记节点的值是相邻节点值的加权平均”，这与标签传播算法的核心思想一致。

这种方法在图半监督学习中非常经典，它通过最小化割来寻找平滑的类别划分，适用于社交网络、图像分割等场景。

基于图的半监督学习：最小割（Min-Cut）算法的原理与图划分过程 题目描述 假设我们有一张无向加权图 \(G = (V, E)\)，其中节点集 \(V\) 包含少量已标记的节点（已知类别标签）和大量未标记的节点，边的权重表示节点之间的相似度。目标是根据图的拓扑结构和已标记信息，为所有未标记节点预测类别标签，使得 同一类别内部的节点连接紧密，不同类别之间的连接尽可能弱 。这可以形式化为一个 图划分 问题：在满足已标记节点约束的前提下，将图划分为若干个子集（每个子集对应一个类别），并最小化 子集之间的边权重之和 （即割的大小）。最小割算法即为求解该目标的一种经典方法。 解题过程 1. 问题形式化 设节点集 \(V = \{v_ 1, v_ 2, \dots, v_ n\}\)，其中前 \(l\) 个节点已标记，其余 \(u = n - l\) 个节点未标记。假设共有 \(C\) 个类别，用集合 \(\{1, 2, \dots, C\}\) 表示。 定义权重矩阵 \(W \in \mathbb{R}^{n \times n}\)，其中 \(W_ {ij} \geq 0\) 表示节点 \(v_ i\) 与 \(v_ j\) 之间的相似度（权重），若两节点无边则 \(W_ {ij} = 0\)。通常 \(W\) 对称。 设节点标签向量为 \(y \in \{1, 2, \dots, C\}^n\)，其中前 \(l\) 个元素已知，后 \(u\) 个元素待求。 最小割的目标是：将节点划分为 \(C\) 个互不相交的子集 \(V_ 1, V_ 2, \dots, V_ C\)，满足已标记节点的类别约束（例如，已标记为类别 \(c\) 的节点必须属于 \(V_ c\)），并最小化 割函数 （cut）： \[ \text{Cut}(V_ 1, \dots, V_ C) = \frac{1}{2} \sum_ {c=1}^C \sum_ {i \in V_ c, j \notin V_ c} W_ {ij}, \] 其中系数 \(1/2\) 是因为每条边在求和时被计算了两次。最小化该割函数意味着 不同类别之间的相似度（即边权重）总和尽可能小 ，从而促使同一类别内部的节点连接更强。 2. 将多类问题转化为多个二分类问题 通常采用 一对多 策略：每次将一个类别与其他所有类别区分开。假设当前考虑类别 \(c\)，定义二分类标签向量 \(f \in \{-1, +1\}^n\)： 若 \(y_ i = c\)，则 \(f_ i = +1\)； 若 \(y_ i \neq c\)，则 \(f_ i = -1\)； 未标记节点的 \(f_ i\) 待求。 对于已标记节点，\(f_ i\) 已知。于是，最小割的目标转化为：在满足已标记节点 \(f_ i\) 值固定的前提下，最小化 类别 \(c\) 与其补集之间的割 ： \[ \text{Cut}(c) = \sum_ {i: f_ i = +1, \; j: f_ j = -1} W_ {ij}. \] 可以证明，该割函数可写成二次形式： \[ \text{Cut}(c) = \frac{1}{4} \sum_ {i,j} W_ {ij} (f_ i - f_ j)^2 = \frac{1}{2} f^T L f, \] 其中 \(L = D - W\) 是图的 拉普拉斯矩阵 ，\(D\) 为度矩阵（对角阵，\(D_ {ii} = \sum_ j W_ {ij}\)）。这里利用了 \(f_ i^2 = 1\) 和 \(L\) 的性质。 于是，对每个类别 \(c\)，我们求解如下 约束优化问题 ： \[ \min_ {f \in \{-1, +1\}^n} f^T L f \quad \text{s.t.} \quad f_ i = \begin{cases} +1, & \text{若 } y_ i = c \text{ 且 } i \text{ 已标记} \\ -1, & \text{若 } y_ i \neq c \text{ 且 } i \text{ 已标记} \end{cases}. \] 3. 连续松弛与求解 由于上述问题是离散的（\(f_ i = \pm 1\)），求解是 NP 难的。常用 连续松弛 ：将 \(f\) 的取值范围放松到实数域，即 \(f \in \mathbb{R}^n\)，但保留已标记节点的约束值（\(+1\) 或 \(-1\)）。松弛后的问题为： \[ \min_ {f \in \mathbb{R}^n} f^T L f \quad \text{s.t.} \quad f_ i = \begin{cases} +1, & \text{若 } y_ i = c \text{ 且 } i \text{ 已标记} \\ -1, & \text{若 } y_ i \neq c \text{ 且 } i \text{ 已标记} \end{cases}. \] 这是一个 带等式约束的凸二次优化问题 ，可解析求解。 将节点排序，使前 \(l\) 个为已标记节点，后 \(u\) 个为未标记节点。将 \(f\) 和 \(L\) 分块： \[ f = \begin{bmatrix} f_ l \\ f_ u \end{bmatrix}, \quad L = \begin{bmatrix} L_ {ll} & L_ {lu} \\ L_ {ul} & L_ {uu} \end{bmatrix}. \] 其中 \(f_ l \in \mathbb{R}^l\) 已知（为 \(+1\) 或 \(-1\)），\(f_ u \in \mathbb{R}^u\) 未知。目标函数展开： \[ f^T L f = [ f_ l^T \quad 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 + 2 f_ u^T L_ {ul} f_ l + f_ u^T L_ {uu} f_ u. \] 对 \(f_ u\) 求导并令导数为零： \[ \frac{\partial}{\partial f_ u} (f^T L f) = 2 L_ {ul} f_ l + 2 L_ {uu} f_ u = 0 \quad \Rightarrow \quad L_ {uu} f_ u = - L_ {ul} f_ l. \] 由于 \(L_ {uu}\) 是正定矩阵（在连通图中），可求解线性方程组得到 \(f_ u\)： \[ f_ u = - L_ {uu}^{-1} L_ {ul} f_ l. \] 解出 \(f_ u\) 后，每个元素是一个实数，其 符号 表示类别归属：若 \(f_ i > 0\)，则将节点 \(i\) 划为类别 \(c\)；若 \(f_ i < 0\)，则不属于类别 \(c\)。 4. 多类别预测 对每个类别 \(c = 1, 2, \dots, C\)，重复步骤 2-3，得到 \(C\) 个实值向量 \(f^{(c)}\)（每个向量对应一个“类别 vs 其余”的划分）。对于未标记节点 \(i\)，比较它在所有 \(C\) 个向量中的值 \(f_ i^{(c)}\)，将节点 \(i\) 分配给 值最大的类别 ： \[ \hat{y} i = \arg\max {c} f_ i^{(c)}. \] 因为 \(f_ i^{(c)}\) 表示节点 \(i\) 与类别 \(c\) 的“关联强度”，最大值对应的类别即为最可能的类别。 5. 算法总结 输入：图权重矩阵 \(W\)，已标记节点的标签 \(y_ 1, \dots, y_ l\)（共 \(C\) 类）。 输出：所有节点的预测标签 \(\hat{y}\)。 计算度矩阵 \(D\)（对角阵，\(D_ {ii} = \sum_ j W_ {ij}\)）和拉普拉斯矩阵 \(L = D - W\)。 对每个类别 \(c = 1, 2, \dots, C\)： 构建二分类标签向量 \(f_ l \in \{-1, +1\}^l\)：若已标记节点 \(i\) 属于类别 \(c\)，则 \(f_ {l,i} = +1\)；否则为 \(-1\)。 将 \(L\) 分块为 \(L = \begin{bmatrix} L_ {ll} & L_ {lu} \\ L_ {ul} & L_ {uu} \end{bmatrix}\)，其中下标 \(l\) 对应已标记节点，\(u\) 对应未标记节点。 解线性方程组 \(L_ {uu} f_ u^{(c)} = - L_ {ul} f_ l\)，得到 \(f_ u^{(c)}\)。 令 \(f^{(c)} = [ f_ l; f_ u^{(c)} ]\)。 对每个未标记节点 \(i\)，计算 \(\hat{y}_ i = \arg\max_ c f_ i^{(c)}\)。 关键点说明 为什么用拉普拉斯矩阵 ：\(f^T L f = \frac{1}{2} \sum_ {i,j} W_ {ij} (f_ i - f_ j)^2\) 直观衡量了 不同类别之间边的差异 。当 \(f_ i\) 和 \(f_ j\) 异号时，该项贡献较大，最小化它相当于减少跨类别的边权重和。 连续松弛的合理性 ：松弛后的问题在实数域是凸的，有唯一解。尽管放松了离散约束，但解通常呈现“同类节点值相近、不同类节点值符号相反”的特性，符号可直接用于分类。 与标签传播的关系 ：最小割的解等价于在图上用调和函数（harmonic function）做插值，其满足“未标记节点的值是相邻节点值的加权平均”，这与标签传播算法的核心思想一致。 这种方法在图半监督学习中非常经典，它通过最小化割来寻找平滑的类别划分，适用于社交网络、图像分割等场景。