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

字数 3445 2025-12-21 09:31:44

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

1. 题目描述
在基于图的半监督学习（Graph-based Semi-Supervised Learning）中，我们通常将数据点表示为一个加权图，其中节点是数据样本（部分节点有标签，部分无标签），边表示样本之间的相似性。最小割（Min-Cut）算法是一种经典的图划分方法，其核心思想是通过移除最少数量的边（或最小化移除边的总权重），将图分割成互不连通的子图，使得每个子图主要包含同一类别的节点，从而实现节点标签的预测。本题目将详解最小割算法在半监督分类中的图构造、优化目标建模和求解过程。

2. 解题过程

步骤1：图的构造

给定数据集 \(X = \{x_1, \dots, x_l, x_{l+1}, \dots, x_n\}\)，其中前 \(l\) 个样本有标签 \(y_i \in \{1, \dots, C\}\)，其余 \(u = n-l\) 个样本无标签。
构造一个无向加权图 \(G = (V, E)\)，其中节点集 \(V\) 对应所有 \(n\) 个样本，边集 \(E\) 由相似性矩阵 \(W \in \mathbb{R}^{n \times n}\) 定义。
边的权重 \(w_{ij}\) 通常用高斯核函数计算：

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

当 \(\|x_i - x_j\|\) 较大时权重接近0，因此通常只保留每个节点的 \(k\) 最近邻的边（\(k\)-NN图）或 \(\epsilon\)-邻域内的边。

相似性矩阵 \(W\) 是对称的（\(w_{ij} = w_{ji}\)），且对角线元素 \(w_{ii} = 0\)。

步骤2：最小割的优化目标

对于二分类问题（\(C=2\)），假设标签为 \(\{+1, -1\}\)。最小割的目标是将节点集 \(V\) 划分成两个不相交的子集 \(A\) 和 \(B\)（\(A \cup B = V, A \cap B = \emptyset\)），使得切割（即连接 \(A\) 和 \(B\) 的边）的总权重最小。
割（Cut）的定义为：

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

对于有标签数据，我们要求划分结果与已知标签一致：若 \(y_i = +1\)，则 \(i \in A\)；若 \(y_i = -1\)，则 \(i \in B\)。无标签节点的归属由优化决定。
因此，最小割的优化问题为：

\[ \min_{A, B} \text{Cut}(A, B) \quad \text{s.t.} \quad \text{已知标签的节点归属固定} \]

步骤3：转化为等价的优化问题

引入指示向量 \(f = (f_1, \dots, f_n)^\top \in \{-1, +1\}^n\)，其中 \(f_i = +1\) 表示节点 \(i\) 属于 \(A\)，\(f_i = -1\) 表示属于 \(B\)。
则割函数可重写为：

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

因为当 \(f_i = f_j\) 时 \((f_i - f_j)^2 = 0\)，否则为4，且 \(w_{ij}\) 仅对连接 \(A, B\) 的边非零。

已知标签的节点 \(i\) 的 \(f_i\) 固定为 \(y_i\)。令 \(f = [f_l; f_u]\)，其中 \(f_l\) 是已知的标签向量，\(f_u\) 是无标签节点的待求指示变量。
最小割问题等价于：

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

步骤4：松弛与求解

上述问题是整数规划，直接求解是NP难的。常用方法是松弛约束：允许 \(f_i\) 取实数值，但固定有标签节点的值为 \(y_i\)，无标签节点的值通过优化连续变量得到。
定义图的度矩阵 \(D\) 为对角矩阵，其中 \(D_{ii} = \sum_j w_{ij}\)。图的非规范化拉普拉斯矩阵为 \(L = D - W\)。
可以证明：

\[ \frac{1}{2} \sum_{i,j} w_{ij} (f_i - f_j)^2 = f^\top L f \]

因此松弛后的问题为：

\[ \min_{f_u \in \mathbb{R}^{u}} f^\top L f \quad \text{s.t.} \quad f_i = y_i \ (i=1,\dots,l) \]

将 \(L\) 和 \(f\) 分块为有标签和无标签部分：

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

其中 \(f_l\) 已知。

目标函数展开为：

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

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

\[ \frac{\partial}{\partial f_u} (f^\top L f) = 2 L_{ul} f_l + 2 L_{uu} f_u = 0 \]

得到线性系统：

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

由于 \(L_{uu}\) 是正定矩阵（对于连通图），可解出：

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

步骤5：决策与多类别扩展

得到实值 \(f_u\) 后，通过符号函数决定无标签节点的类别：

\[ \hat{y}_i = \text{sign}(f_i) \quad (i = l+1, \dots, n) \]

对于多类问题（\(C > 2\)），常用一对多策略：对每个类别 \(c\)，将有标签节点中属于类别 \(c\) 的标记为 \(+1\)，其他有标签节点标记为 \(-1\)，无标签节点初始为0，求解上述松弛问题得到实值 \(f_u^{(c)}\)，然后对每个无标签节点选择 \(\arg\max_c f_i^{(c)}\) 作为预测类别。

步骤6：与随机游走的联系

最小割的解可以解释为随机游走的平衡状态。考虑随机游走转移矩阵 \(P = D^{-1}W\)，则 \(f_u\) 的解恰好满足：无标签节点上的值是其在随机游走中首次到达有标签节点时，该节点标签的期望值。这提供了另一种直观理解。

3. 关键点总结

最小割将半监督分类转化为图划分问题，目标是最小化类间连接的总权重。
通过松弛整数约束，将离散优化转化为求解线性系统，计算高效。
解可视为图上的调和函数，满足边界条件（有标签节点）且在内部（无标签节点）平滑。
该方法假设“相似节点应有相同标签”，是图半监督学习的基本假设之一。

基于图的半监督学习方法：最小割（Min-Cut）算法的原理与图划分过程 1. 题目描述在基于图的半监督学习（Graph-based Semi-Supervised Learning）中，我们通常将数据点表示为一个加权图，其中节点是数据样本（部分节点有标签，部分无标签），边表示样本之间的相似性。最小割（Min-Cut）算法是一种经典的图划分方法，其核心思想是通过移除最少数量的边（或最小化移除边的总权重），将图分割成互不连通的子图，使得每个子图主要包含同一类别的节点，从而实现节点标签的预测。本题目将详解最小割算法在半监督分类中的图构造、优化目标建模和求解过程。 2. 解题过程步骤1：图的构造给定数据集 \( X = \{x_ 1, \dots, x_ l, x_ {l+1}, \dots, x_ n\} \)，其中前 \( l \) 个样本有标签 \( y_ i \in \{1, \dots, C\} \)，其余 \( u = n-l \) 个样本无标签。构造一个无向加权图 \( G = (V, E) \)，其中节点集 \( V \) 对应所有 \( n \) 个样本，边集 \( E \) 由相似性矩阵 \( W \in \mathbb{R}^{n \times n} \) 定义。边的权重 \( w_ {ij} \) 通常用高斯核函数计算： \[ w_ {ij} = \exp\left(-\frac{\|x_ i - x_ j\|^2}{2\sigma^2}\right) \quad (i \neq j) \] 当 \( \|x_ i - x_ j\| \) 较大时权重接近0，因此通常只保留每个节点的 \( k \) 最近邻的边（\( k \)-NN图）或 \( \epsilon \)-邻域内的边。相似性矩阵 \( W \) 是对称的（\( w_ {ij} = w_ {ji} \)），且对角线元素 \( w_ {ii} = 0 \)。步骤2：最小割的优化目标对于二分类问题（\( C=2 \)），假设标签为 \( \{+1, -1\} \)。最小割的目标是将节点集 \( V \) 划分成两个不相交的子集 \( A \) 和 \( B \)（\( A \cup B = V, A \cap B = \emptyset \)），使得切割（即连接 \( A \) 和 \( B \) 的边）的总权重最小。割（Cut）的定义为： \[ \text{Cut}(A, B) = \sum_ {i \in A, j \in B} w_ {ij} \] 对于有标签数据，我们要求划分结果与已知标签一致：若 \( y_ i = +1 \)，则 \( i \in A \)；若 \( y_ i = -1 \)，则 \( i \in B \)。无标签节点的归属由优化决定。因此，最小割的优化问题为： \[ \min_ {A, B} \text{Cut}(A, B) \quad \text{s.t.} \quad \text{已知标签的节点归属固定} \] 步骤3：转化为等价的优化问题引入指示向量 \( f = (f_ 1, \dots, f_ n)^\top \in \{-1, +1\}^n \)，其中 \( f_ i = +1 \) 表示节点 \( i \) 属于 \( A \)，\( f_ i = -1 \) 表示属于 \( B \)。则割函数可重写为： \[ \text{Cut}(A, B) = \frac{1}{4} \sum_ {i,j} w_ {ij} (f_ i - f_ j)^2 \] 因为当 \( f_ i = f_ j \) 时 \( (f_ i - f_ j)^2 = 0 \)，否则为4，且 \( w_ {ij} \) 仅对连接 \( A, B \) 的边非零。已知标签的节点 \( i \) 的 \( f_ i \) 固定为 \( y_ i \)。令 \( f = [ f_ l; f_ u] \)，其中 \( f_ l \) 是已知的标签向量，\( f_ u \) 是无标签节点的待求指示变量。最小割问题等价于： \[ \min_ {f_ u \in \{-1, +1\}^{u}} \frac{1}{4} \sum_ {i,j} w_ {ij} (f_ i - f_ j)^2 \] 步骤4：松弛与求解上述问题是整数规划，直接求解是NP难的。常用方法是松弛约束：允许 \( f_ i \) 取实数值，但固定有标签节点的值为 \( y_ i \)，无标签节点的值通过优化连续变量得到。定义图的度矩阵 \( D \) 为对角矩阵，其中 \( D_ {ii} = \sum_ j w_ {ij} \)。图的非规范化拉普拉斯矩阵为 \( L = D - W \)。可以证明： \[ \frac{1}{2} \sum_ {i,j} w_ {ij} (f_ i - f_ j)^2 = f^\top L f \] 因此松弛后的问题为： \[ \min_ {f_ u \in \mathbb{R}^{u}} f^\top L f \quad \text{s.t.} \quad f_ i = y_ i \ (i=1,\dots,l) \] 将 \( L \) 和 \( f \) 分块为有标签和无标签部分： \[ L = \begin{bmatrix} L_ {ll} & L_ {lu} \\ L_ {ul} & L_ {uu} \end{bmatrix}, \quad f = \begin{bmatrix} f_ l \\ f_ u \end{bmatrix} \] 其中 \( f_ l \) 已知。目标函数展开为： \[ f^\top L f = [ f_ l^\top \ f_ u^\top] \begin{bmatrix} L_ {ll} & L_ {lu} \\ L_ {ul} & L_ {uu} \end{bmatrix} \begin{bmatrix} f_ l \\ f_ u \end{bmatrix} = f_ l^\top L_ {ll} f_ l + 2 f_ u^\top L_ {ul} f_ l + f_ u^\top L_ {uu} f_ u \] 对 \( f_ u \) 求导并令导数为零： \[ \frac{\partial}{\partial f_ u} (f^\top L f) = 2 L_ {ul} f_ l + 2 L_ {uu} f_ u = 0 \] 得到线性系统： \[ L_ {uu} f_ u = - L_ {ul} f_ l \] 由于 \( L_ {uu} \) 是正定矩阵（对于连通图），可解出： \[ f_ u = - L_ {uu}^{-1} L_ {ul} f_ l \] 步骤5：决策与多类别扩展得到实值 \( f_ u \) 后，通过符号函数决定无标签节点的类别： \[ \hat{y}_ i = \text{sign}(f_ i) \quad (i = l+1, \dots, n) \] 对于多类问题（\( C > 2 \)），常用一对多策略：对每个类别 \( c \)，将有标签节点中属于类别 \( c \) 的标记为 \( +1 \)，其他有标签节点标记为 \( -1 \)，无标签节点初始为0，求解上述松弛问题得到实值 \( f_ u^{(c)} \)，然后对每个无标签节点选择 \( \arg\max_ c f_ i^{(c)} \) 作为预测类别。步骤6：与随机游走的联系最小割的解可以解释为随机游走的平衡状态。考虑随机游走转移矩阵 \( P = D^{-1}W \)，则 \( f_ u \) 的解恰好满足：无标签节点上的值是其在随机游走中首次到达有标签节点时，该节点标签的期望值。这提供了另一种直观理解。 3. 关键点总结最小割将半监督分类转化为图划分问题，目标是最小化类间连接的总权重。通过松弛整数约束，将离散优化转化为求解线性系统，计算高效。解可视为图上的调和函数，满足边界条件（有标签节点）且在内部（无标签节点）平滑。该方法假设“相似节点应有相同标签”，是图半监督学习的基本假设之一。