图拉普拉斯矩阵的次小特征值与 Cheeger 不等式割界

图拉普拉斯矩阵是谱图理论的核心工具，它将离散图的结构信息编码为代数特征。在众多结论中，关于“切割质量”的 Cheeger 不等式建立了组合优化与矩阵特征值之间的联系。这篇文章将手把手带你理解：为什么次小特征值能衡量图的连通性，以及如何用它界定切割的代价。

1. 建立图的代数表示

获取 一个无向图 $G = (V, E)$，其中 $V$ 是顶点集合，$E$ 是边集合。定义一个顶点 $v$ 的度数为与它相连的边的数量，记作 $d_v$。

构造 图拉普拉斯矩阵 $L$，其维度为 $|V| \times |V|$。矩阵元素由以下规则确定：

• 填充 对角线上第 $i$ 个元素为顶点 $v_i$ 的度数 $d_{v_i}$。
• 填充 非对角线上第 $i$ 行第 $j$ 列的元素，当顶点 $v_i$ 与 $v_j$ 相连时设为 $-1$，否则设为 $0$。

验证 一个关键性质：对于任意实值向量 $x = (x_1, x_2, \dots, x_{|V|})^T$，二次型满足：

$$ x^T L x = \sum_{(u, v) \in E} (x_u - x_v)^2 $$

理解 这个公式的直观意义：它衡量了相邻顶点之间“信号值”差异的平方和。若将 $x$ 视为给每个顶点赋予的数值，则该二次型在邻近顶点数值差异大时取值较大。

2. 识别特征值与特征向量

计算 图拉普拉斯矩阵 $L$ 的特征值，按升序排列：

$$ 0 = \lambda_1 \le \lambda_2 \le \dots \le \lambda_{|V|} $$

注意 第一个特征值恒为 $0$，其对应的特征向量为全 $1$ 向量（记作 $\mathbf{1}$）。因为 $L \cdot \mathbf{1} = 0$，这是每行元素之和为 $0$ 的直接结果。

定位 次小特征值即 $\lambda_2$，通常被称为代数连通度。这个名称暗示了它与图的连通性密切相关。

判定 一个基本结论：图 $G$ 是连通图当且仅当 $\lambda_2 > 0$。若图不连通，则 $\lambda_2 = 0$，且 $0$ 作为特征值的重数等于连通分量的数量。

3. 定义切割的代价

设定 将一个顶点集合 $S \subset V$ 从图中分离出来。定义 $S$ 的补集为 $\bar{S} = V \setminus S$。

计算 切割规模 $|\partial S|$，即一端在 $S$ 中、另一端在 $\bar{S}$ 中的边的总数。

定义 切割的归一化代价。为公平比较不同大小的 $S$，需将其体积信息纳入考量。定义 $S$ 的体积为内部所有顶点的度数之和：

$$ \text{vol}(S) = \sum_{v \in S} d_v $$

构造 Cheeger 常数（也称 isoperimetric 数），用于描述图中最“划算”的切割比例：

$$ h_G = \min_{S \subset V, \, 0 < \text{vol}(S) \le \frac12 \text{vol}(V)} \frac{|\partial S|}{\text{vol}(S)} $$

解读 Cheeger 常数越小，说明存在一个相对边界规模很小的大块区域，即图存在明显的“瓶颈”结构。

4. 建立特征值与切割界的关系

引入 Cheeger 不等式。这个不等式将谱信息（$\lambda_2$）与组合信息（$h_G$）建立了双向控制：

$$ 2 h_G \ge \lambda_2 \ge \frac{h_G^2}{2 \cdot d_{\max}} $$

其中 $d_{\max}$ 是图中最大的顶点度数。

拆解 不等式左侧 $2 h_G \ge \lambda_2$ 的含义：若存在一个小代价切割（$h_G$ 很小），那么 $\lambda_2$ 必然也很小。这提供了从图谱判断是否存在瓶颈的线索。

拆解 不等式右侧 $\lambda_2 \ge \frac{h_G^2}{2 d_{\max}}$ 的含义：若 $\lambda_2$ 较大，则图中不可能存在代价过小的切割。这是保证图“鲁棒连通”的定量依据。

获取 上述不等式给出了 $\lambda_2$ 对 $h_G$ 的近似逼近：$\lambda_2$ 与 $h_G$ 在同一个量级内（至多相差一个与最大度数相关的因子）。

5. 通过特征向量执行切割

计算 求解矩阵 $L$ 的特征向量，找到 $\lambda_2$ 对应的特征向量 $f_2$。这个过程称为谱分解。

排序 将 $f_2$ 中的各分量按数值大小从低到高排列。每个分量对应原图中的一个顶点。

选择 寻找一个阈值 $t$，将顶点划分为两组：分量值小于等于 $t$ 的顶点归入 $S$，其余顶点归入 $\bar{S}$。阈值 $t$ 通常选择为中位数，以保证两侧体积大致平衡。

评估 计算该划分对应的实际切割代价 $|\partial S| / \text{vol}(S)$，并与 Cheeger 常数 $h_G$ 的下界进行比较。

理解 这种切割方法被称为谱聚类。它的理论保证来自 Cheeger 不等式：只要 $\lambda_2$ 足够小，按照 $f_2$ 符号（或其排序后的某个切点）进行划分，得到的切割代价不会偏离最优值太远。

6. 处理无向图以外的扩展情形

检查 当边带有权重时，调整 拉普拉斯矩阵的定义：将 $L$ 中对应对角线元素改为该顶点所有连接边的权值之和，非对角线元素改为边的权值的相反数。更新 度数的定义 $d_v$ 为连接边的权值总和。

验证 此时 Cheeger 不等式依然成立，只需将其中关于体积与边界的定义按权重版本重新解释。这使谱方法可用于加权网络分析。

观察 对大规模稀疏图，直接计算 全部特征分解代价过高（时间复杂度 $O(n^3)$）。此时改用 迭代法（如 Lanczos 算法）求解 最小几个特征值及其特征向量。大多数编程库（如 scipy.sparse.linalg.eigsh）已经内置了这类算法，只需传入 稀疏矩阵与所需特征值个数即可。

执行 上述步骤后，你已掌握运用谱理论分析图切割的完整流程：从构造拉普拉斯矩阵出发，计算次小特征值与对应特征向量，依据谱划分切割顶点集，并利用 Cheeger 不等式对切割代价做出定量估计。