图 Laplacian 与谱聚类：从图结构到最优分割

Art. 14 算子全景预告了 Part 2 的三族算子矩阵——随机矩阵、图结构矩阵、相似度矩阵。前几篇文章探索了第一族（马尔可夫链、HMM、PageRank）和第三族（Kernel 矩阵）。现在我们转向第二族的核心：图 Laplacian。

假设你有一组用户的社交关系图，想把它分成几个紧密社区。或者你有一组像素，想按视觉相似度分割成前景和背景。直觉上，好的分割应该切断尽可能少的连接。问题是：怎么找到这样的”最优切割”？ 暴力搜索所有可能的分割在大图上不可行——$n$ 个节点有 $2^n$ 种二分方式。

答案藏在图 Laplacian 矩阵 $L = D - A_G$ 的特征值和特征向量里。$L$ 的第二小特征值对应的特征向量（Fiedler 向量）天然地把图分成两个群组，而且这个分割在特定意义下接近最优。谱聚类（spectral clustering）正是将这个数学洞察转化为实用算法：用 Laplacian 特征向量做降维，再用 k-means 完成聚类。

“谱”（spectrum）词源：在数学中，矩阵的谱指它的所有特征值的集合 $\{\lambda_1, \lambda_2, \ldots, \lambda_n\}$。这个术语借自物理学——白光通过棱镜分解成不同频率的光谱（spectrum），矩阵通过特征分解”分解”成不同特征值对应的成分。所以”谱聚类”就是”基于特征值/特征向量的聚类”，“谱方法”就是”利用特征值/特征向量性质的方法”。

图 Laplacian 的定义

基本设置

给定一个无向图 $G = (V, E)$，有 $n = |V|$ 个节点。我们需要三个矩阵：

邻接矩阵（adjacency matrix） $A_G \in \mathbb{R}^{n \times n}$（用 $A_G$ 而非 $A$，以避免与泛指矩阵混淆）：

$(A_G)_{ij} = \begin{cases} w_{ij} & \text{如果节点 } i \text{ 和 } j \text{ 相连} \\ 0 & \text{否则} \end{cases}$

对于无权图，$w_{ij} = 1$。对于带权图，$w_{ij} > 0$ 是边的权重。无向图的邻接矩阵是对称的：$(A_G)_{ij} = (A_G)_{ji}$。

度矩阵（degree matrix） $D \in \mathbb{R}^{n \times n}$：对角矩阵，$D_{ii} = d_i = \sum_{j=1}^n (A_G)_{ij}$ 是节点 $i$ 的度（degree），即与它相连的边的权重之和。

图 Laplacian（graph Laplacian） $L \in \mathbb{R}^{n \times n}$：

$\boxed{L = D - A_G}$

逐项理解：

• 对角元素 $L_{ii} = d_i$（节点 $i$ 的度）
• 非对角元素 $L_{ij} = -(A_G)_{ij}$（如果 $i, j$ 相连则为 $-w_{ij}$，否则为 $0$）
• 每行之和为零：$\sum_j L_{ij} = d_i - \sum_j (A_G)_{ij} = 0$

为什么叫”Laplacian”？

这个名字来自连续数学中的 Laplace 算子 $\Delta f = \nabla^2 f = \sum_i \frac{\partial^2 f}{\partial x_i^2}$。Laplace 算子衡量的是”函数值与邻域均值的偏差”——如果 $f$ 在某点的值高于邻域平均，$\Delta f < 0$；低于邻域平均，$\Delta f > 0$。

图 Laplacian $L$ 是这个思想的离散版本。对于定义在节点上的信号 $\mathbf{f} \in \mathbb{R}^n$（$f_i$ 是节点 $i$ 上的值）：

$(L\mathbf{f})_i = \sum_{j: (i,j) \in E} w_{ij}(f_i - f_j)$

直觉理解：$(L\mathbf{f})_i$ 是节点 $i$ 的值与其每个邻居的值的加权差之和。如果 $f_i$ 远大于邻居们的值，$(L\mathbf{f})_i$ 很大；如果 $f_i$ 接近邻居均值，$(L\mathbf{f})_i$ 接近零。这正是离散 Laplace 算子——衡量”一个节点与邻居的差异程度”。

下图用一个 5 节点图直观展示了图 Laplacian 的平滑效果：对信号 $\mathbf{f}$ 执行一步 $\mathbf{f}' = \mathbf{f} - \alpha L\mathbf{f}$，高值节点向下、低值节点向上，信号变得更”光滑”。

推导 $(L\mathbf{f})_i$ 的展开式： $(L\mathbf{f})_i = (D\mathbf{f})_i - (A_G\mathbf{f})_i = d_i f_i - \sum_j (A_G)_{ij} f_j = \sum_j (A_G)_{ij} f_i - \sum_j (A_G)_{ij} f_j = \sum_{j: (i,j) \in E} w_{ij}(f_i - f_j)$

图 Laplacian 的关键性质

性质 1：对称半正定

$L$ 是对称半正定（positive semi-definite, PSD）矩阵。

对称性：$L^T = (D - A_G)^T = D^T - A_G^T = D - A_G = L$（$D$ 是对角矩阵，$A_G$ 对于无向图是对称的）。

半正定性——用二次型证明（这是最具洞察力的证明方式）：

$\mathbf{f}^T L \mathbf{f} = \mathbf{f}^T (D - A_G) \mathbf{f} = \sum_i d_i f_i^2 - \sum_{i,j} (A_G)_{ij} f_i f_j$

利用 $d_i = \sum_j (A_G)_{ij}$，可以改写为：

$\mathbf{f}^T L \mathbf{f} = \sum_{i,j} (A_G)_{ij} f_i^2 - \sum_{i,j} (A_G)_{ij} f_i f_j = \sum_{i,j} (A_G)_{ij} f_i (f_i - f_j)$

注意对称性 $(A_G)_{ij} = (A_G)_{ji}$，交换 $i, j$ 得到 $\sum_{i,j} (A_G)_{ij} f_j(f_j - f_i)$。两式相加除以 2：

$\boxed{\mathbf{f}^T L \mathbf{f} = \frac{1}{2} \sum_{i,j} (A_G)_{ij} (f_i - f_j)^2}$

这是一个平方和，因此 $\mathbf{f}^T L \mathbf{f} \geq 0$ 对所有 $\mathbf{f}$ 成立——$L$ 半正定。（见 von Luxburg, 2007, Proposition 1）

这个二次型的直觉：$\mathbf{f}^T L \mathbf{f}$ 度量的是信号 $\mathbf{f}$ 在图上的”总变化量”。如果两个相连的节点 $i, j$ 的信号值差距很大（$|f_i - f_j|$ 大），这一项的贡献就大。一个”光滑”的信号（相连节点值相近）对应小的 $\mathbf{f}^T L \mathbf{f}$，一个”剧烈变化”的信号对应大的 $\mathbf{f}^T L \mathbf{f}$。

性质 2：最小特征值为 0

由于每行之和为零（$L\mathbf{1} = \mathbf{0}$，其中 $\mathbf{1}$ 是全 1 向量），全 1 向量 $\mathbf{1}$ 是 $L$ 的特征向量，对应特征值 $\lambda_1 = 0$：

$L\mathbf{1} = (D - A_G)\mathbf{1} = D\mathbf{1} - A_G\mathbf{1}$

$D\mathbf{1}$ 的第 $i$ 个分量是 $d_i$，$A_G\mathbf{1}$ 的第 $i$ 个分量是 $\sum_j (A_G)_{ij} = d_i$，所以 $L\mathbf{1} = \mathbf{0}$。

结合半正定性（所有特征值 $\geq 0$），$\lambda_1 = 0$ 就是最小特征值。将所有特征值从小到大排列：

$0 = \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$

性质 3：零特征值个数 = 连通分量数

这是图 Laplacian 最深刻的结构性定理。

定理（von Luxburg, 2007, Proposition 2）：$\lambda_1 = 0$ 的重数（即特征值 0 出现的次数）等于图 $G$ 的连通分量数 $k$。

证明思路：

$k = 1$（图连通）的情况：需要证明 $\lambda_1 = 0$ 的特征空间是一维的，即 $L\mathbf{f} = \mathbf{0}$ 的解只有 $\mathbf{f} = c\mathbf{1}$（常数向量）。

如果 $L\mathbf{f} = \mathbf{0}$，则 $\mathbf{f}^T L\mathbf{f} = 0$。由二次型公式：

$\frac{1}{2}\sum_{i,j} (A_G)_{ij}(f_i - f_j)^2 = 0$

因为每一项 $(A_G)_{ij}(f_i - f_j)^2 \geq 0$，所以对所有边 $(i,j) \in E$ 必须有 $f_i = f_j$。如果图是连通的，任意两个节点之间存在路径，沿路径传递 $f_i = f_j$ 得到所有节点的值相等，即 $\mathbf{f} = c\mathbf{1}$。因此零特征空间是一维的，$\lambda_1 = 0$ 的重数为 1。

$k > 1$（图有多个连通分量）的情况：设图有 $k$ 个连通分量 $C_1, C_2, \ldots, C_k$。对每个连通分量 $C_\ell$ 定义指示向量 $\mathbf{1}_{C_\ell}$（在 $C_\ell$ 的节点上为 1，其余为 0）。由于不同分量之间没有边，$L\mathbf{1}_{C_\ell} = \mathbf{0}$——每个指示向量都是零特征值的特征向量。这 $k$ 个指示向量线性无关，所以零特征值的重数至少为 $k$。

反过来，每个连通分量内部的 Laplacian 是连通的（上面已证零特征空间一维），所以每个分量贡献恰好一个零特征值。因此零特征值的重数恰好为 $k$。$\blacksquare$

实践意义：如果你计算了一个图的 Laplacian 特征值，发现前 3 个特征值都是 0（$\lambda_1 = \lambda_2 = \lambda_3 = 0, \lambda_4 > 0$），那么这个图恰好有 3 个连通分量。特征值直接告诉你图的全局拓扑结构。

数值例子：6 节点图的 Laplacian 特征分解

为了让上述理论具体化，我们对一个小图做完整的 Laplacian 特征分解。

图的定义

考虑 6 个节点的无权无向图，边集：

$E = \{(0,1), (0,2), (1,2), (1,3), (3,4), (3,5), (4,5)\}$

这个图有两个”紧密群组”：$\{0, 1, 2\}$ 和 $\{3, 4, 5\}$，通过边 $(1,3)$ 连接。

邻接矩阵和度矩阵

$A_G = \begin{bmatrix} 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 \end{bmatrix}$

度：$d_0 = 2, \; d_1 = 3, \; d_2 = 2, \; d_3 = 3, \; d_4 = 2, \; d_5 = 2$。

$D = \text{diag}(2, 3, 2, 3, 2, 2)$

Laplacian 矩阵

$L = D - A_G = \begin{bmatrix} 2 & -1 & -1 & 0 & 0 & 0 \\ -1 & 3 & -1 & -1 & 0 & 0 \\ -1 & -1 & 2 & 0 & 0 & 0 \\ 0 & -1 & 0 & 3 & -1 & -1 \\ 0 & 0 & 0 & -1 & 2 & -1 \\ 0 & 0 & 0 & -1 & -1 & 2 \end{bmatrix}$

验证：每行之和 = $0$ ✓

特征值

对 $L$ 做特征分解（可用数值工具验证），特征值从小到大排列：

$\lambda_1 = 0, \quad \lambda_2 \approx 0.44, \quad \lambda_3 = \lambda_4 = \lambda_5 = 3, \quad \lambda_6 \approx 4.56$

验证：$\text{tr}(L) = 2 + 3 + 2 + 3 + 2 + 2 = 14$，$\sum \lambda_i = 0 + 0.44 + 9 + 4.56 = 14$ ✓。$\lambda_1 = 0$ 且 $\lambda_2 > 0$，说明图是连通的（1 个连通分量）✓。$\lambda_2 \approx 0.44$ 是 Fiedler 值（algebraic connectivity），数值较小，反映两个群组之间的连接较弱（只有一条桥接边）。$\lambda_3 = 3$ 的三重重数来源于图的对称结构——两个三角形通过一条桥接边相连，产生了简并特征空间。

Fiedler 向量

$\lambda_2 \approx 0.44$ 对应的特征向量（Fiedler 向量）大约为：

$\mathbf{v}_2 \approx (-0.46, -0.26, -0.46, 0.26, 0.46, 0.46)^T$

关键观察：$\mathbf{v}_2$ 的分量自然分成正负两组：

• 负分量：节点 $\{0, 1, 2\}$ —— 恰好是第一个群组
• 正分量：节点 $\{3, 4, 5\}$ —— 恰好是第二个群组

按 Fiedler 向量的符号切割图——这就是谱聚类的核心思想。

Fiedler 向量与图切割

Graph Cut 问题

给定图 $G = (V, E)$，将节点分成两组 $S$ 和 $\bar{S} = V \setminus S$。定义切割代价（cut）为：

$\text{cut}(S, \bar{S}) = \sum_{\substack{i \in S \\ j \in \bar{S}}} w_{ij}$

即被切断的边的权重之和。最小切割（min-cut）寻找使 $\text{cut}$ 最小的分割。

但 min-cut 有一个问题：它倾向于切出极小的群组（极端情况下，切出单个孤立节点就能得到很小的 cut）。为了得到”平衡”的分割，我们需要归一化。

RatioCut

RatioCut（Hagen & Kahng, 1992）用群组大小归一化：

$\text{RatioCut}(S, \bar{S}) = \frac{\text{cut}(S, \bar{S})}{|S|} + \frac{\text{cut}(S, \bar{S})}{|\bar{S}|}$

其中 $|S|$ 是群组的节点数。这个目标函数同时惩罚大的 cut 值和不平衡的分割。

RatioCut 与 Laplacian 的联系

关键定理：最小化 RatioCut 的松弛问题等价于 Laplacian 的 Fiedler 向量。

定义指示向量 $\mathbf{f} \in \mathbb{R}^n$：

$f_i = \begin{cases} \sqrt{|\bar{S}|/|S|} & \text{if } i \in S \\ -\sqrt{|S|/|\bar{S}|} & \text{if } i \in \bar{S} \end{cases}$

可以验证 $\mathbf{f}^T \mathbf{1} = 0$（正交于全 1 向量）且 $\|\mathbf{f}\|^2 = n$。

代入二次型：

$\mathbf{f}^T L \mathbf{f} = \frac{1}{2}\sum_{i,j} (A_G)_{ij}(f_i - f_j)^2$

对于每条跨群组的边 $(i \in S, j \in \bar{S})$，$(f_i - f_j)^2 = \left(\sqrt{|\bar{S}|/|S|} + \sqrt{|S|/|\bar{S}|}\right)^2 = \frac{n^2}{|S||\bar{S}|}$。每条群组内部的边贡献 $0$（$f_i = f_j$）。因此：

$\mathbf{f}^T L \mathbf{f} = \text{cut}(S, \bar{S}) \cdot \frac{n^2}{|S||\bar{S}|} = n \cdot \text{RatioCut}(S, \bar{S})$

所以：

$\text{RatioCut}(S, \bar{S}) = \frac{1}{n} \mathbf{f}^T L \mathbf{f}$

最小化 RatioCut 等价于在约束 $\mathbf{f}^T \mathbf{1} = 0$、$\|\mathbf{f}\| = \sqrt{n}$ 下最小化 $\mathbf{f}^T L \mathbf{f}$。如果放松 $\mathbf{f}$ 的离散约束（允许 $\mathbf{f}$ 取任意实数），这就是一个标准的 Rayleigh 商问题，最优解正是 $L$ 的第二小特征向量——Fiedler 向量。（见 von Luxburg, 2007, Section 5）

Fiedler 向量的含义

Fiedler 向量 $\mathbf{v}_2$（$\lambda_2$ 对应的特征向量）是满足 $\mathbf{v}^T \mathbf{1} = 0$（与全 1 向量正交）的条件下，使 $\mathbf{v}^T L \mathbf{v}$ 最小的单位向量。换言之，$\mathbf{v}_2$ 是图上变化最缓慢的非常数信号——它在图的紧密连接区域内部值接近，跨区域边界处值跳变。

因此，按 $\mathbf{v}_2$ 的符号（或在某个阈值处切分）将节点分成两组，得到的分割接近最优 RatioCut。

下图将数值例子中的 Fiedler 向量可视化：上方是 6 节点图的两个群组（蓝、橙）和桥接边（红色虚线），下方是 $\mathbf{v}_2$ 的分量——负值对应群组 A，正值对应群组 B。

Fiedler 值 $\lambda_2$ 本身也有重要意义：它衡量图的代数连通性（algebraic connectivity）。$\lambda_2$ 越大，图越难被二分（连接越紧密）；$\lambda_2$ 接近 0，说明图接近”断成两半”。

谱聚类算法

从二分到 $k$ 分

Fiedler 向量给出了最优二分割。但实际问题中我们常常需要将图分成 $k > 2$ 个群组。自然的推广是：使用 $L$ 的前 $k$ 个最小特征值对应的特征向量（而非仅第二个）。

下图概括了谱聚类从数据到聚类标签的完整五步流程。

标准谱聚类算法（Unnormalized）

给定相似度图 $G$（节点集 $V$，带权邻接矩阵 $A_G$）和目标聚类数 $k$：

1. 构造 Laplacian：计算 $L = D - A_G$
2. 特征分解：计算 $L$ 的前 $k$ 个最小特征向量 $\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_k$
3. 构造嵌入矩阵：令 $U \in \mathbb{R}^{n \times k}$，其中第 $i$ 行 $\mathbf{u}_i = (v_1(i), v_2(i), \ldots, v_k(i))$ 是节点 $i$ 在 $k$ 维”谱空间”中的坐标
4. K-means 聚类：对 $U$ 的行向量 $\mathbf{u}_1, \ldots, \mathbf{u}_n$ 做 $k$-means 聚类
5. 输出：节点 $i$ 的聚类标签 = $\mathbf{u}_i$ 的 k-means 标签

为什么有效？ 步骤 2-3 把每个节点从”图拓扑”映射到了 $k$ 维欧氏空间。在这个空间里，同一群组内的节点聚集在一起（因为它们在慢变的特征向量上取值接近），不同群组的节点分离。K-means 在欧氏空间中表现良好，所以能有效完成聚类。

归一化 Laplacian

实践中，归一化版本的谱聚类通常效果更好。有两种常见的归一化 Laplacian。

对称归一化 Laplacian $L_\text{sym}$：

$L_\text{sym} = D^{-1/2} L \, D^{-1/2} = I - D^{-1/2} A_G \, D^{-1/2}$

随机游走归一化 Laplacian $L_\text{rw}$：

$L_\text{rw} = D^{-1} L = I - D^{-1} A_G$

注意 $D^{-1}A_G$ 就是图上随机游走的转移矩阵——第 $i$ 行第 $j$ 列是从节点 $i$ 一步转移到节点 $j$ 的概率。所以 $L_\text{rw}$ 与随机游走直接相关。

Shi-Malik 算法（Normalized Cuts, 2000）最小化 NCut（用度之和而非节点数归一化）：

$\text{NCut}(S, \bar{S}) = \frac{\text{cut}(S, \bar{S})}{\text{vol}(S)} + \frac{\text{cut}(S, \bar{S})}{\text{vol}(\bar{S})}$

其中 $\text{vol}(S) = \sum_{i \in S} d_i$ 是群组的度之和。NCut 的松弛解是 $L_\text{rw}$ 的特征向量。

Ng-Jordan-Weiss（NJW）算法（2001）使用 $L_\text{sym}$ 的特征向量，并在步骤 3 之后对每个行向量归一化到单位长度（$\mathbf{u}_i \leftarrow \mathbf{u}_i / \|\mathbf{u}_i\|$），然后再做 k-means。

可视化：谱聚类三步流程

下面的交互组件展示了谱聚类在一个 8 节点图上的完整流程。点击三个步骤按钮，分别查看原始图、Fiedler 向量的分量、以及最终的聚类结果。

Step 1: 原始图Step 2: Laplacian 特征向量Step 3: 聚类结果

一个8节点无向图，两个紧密群组之间只有一条桥接边

读图要点：

• Step 1：8 个节点分成两个紧密群组，中间只有一条桥接边（红色虚线）
• Step 2：Fiedler 向量的分量自然分成正负两组——负值节点对应一个群组，正值节点对应另一个群组。注意分量的绝对值反映了节点在群组中的”核心程度”
• Step 3：按 Fiedler 向量的符号着色，完美恢复了两个群组

从相似度数据到图：构造相似度图

谱聚类通常不是从一个现成的图开始，而是从数据点出发。给定 $n$ 个数据点 $\mathbf{x}_1, \ldots, \mathbf{x}_n \in \mathbb{R}^d$，需要先构造一个相似度图，然后在图上做谱聚类。

三种常用构造方法

1. $\varepsilon$-邻域图：如果 $\|\mathbf{x}_i - \mathbf{x}_j\| < \varepsilon$，则连一条边。

2. $k$-近邻图（$k$-NN graph）：如果 $\mathbf{x}_j$ 是 $\mathbf{x}_i$ 的 $k$ 个最近邻之一（或反过来），则连一条边。为了得到无向图，通常取”互为近邻”（mutual k-NN）或”至少一方是近邻”。

3. 全连接图 + 高斯权重：所有节点对之间都有边，权重为高斯核：

$w_{ij} = \exp\!\left(-\frac{\|\mathbf{x}_i - \mathbf{x}_j\|^2}{2\sigma^2}\right)$

$\sigma$ 是带宽参数，控制”多远算相似”。这与 Art. 20 Kernel 矩阵中的 RBF kernel 完全一致——全连接图的邻接矩阵就是 kernel 矩阵。

与 Kernel 的联系：谱聚类的第一步（构造相似度图）本质上就是在构造 kernel 矩阵。这解释了为什么谱聚类能处理非线性可分的数据——kernel 将数据映射到高维特征空间，谱聚类在这个空间中找到线性可分的结构。

Nystrom 近似：大图加速

计算瓶颈

标准谱聚类的主要计算瓶颈是特征分解。对 $n \times n$ 的 Laplacian 矩阵做特征分解的时间复杂度是 $O(n^3)$，空间复杂度是 $O(n^2)$（存储矩阵本身）。当 $n$ 达到数万甚至数百万时（如社交网络、图像分割），这不可行。

Nystrom 方法

Nystrom 近似（Williams & Seeger, 2001）提供了一种优雅的解决方案：从 $n$ 个节点中随机采样 $m \ll n$ 个”锚点”（landmark points），只计算锚点之间和锚点与其余点之间的相似度，然后用矩阵补全来近似整个 kernel 矩阵。

设 $K \in \mathbb{R}^{n \times n}$ 是完整的 kernel 矩阵。将节点分为采样集 $S$（$m$ 个）和剩余集 $R$（$n - m$ 个），$K$ 可以分块为：

$K = \begin{bmatrix} K_{SS} & K_{SR} \\ K_{RS} & K_{RR} \end{bmatrix}$

Nystrom 近似用 $K_{SS}$ 和 $K_{SR}$ 来近似 $K_{RR}$：

$\tilde{K}_{RR} = K_{RS} K_{SS}^{-1} K_{SR}$

近似的完整矩阵为：

$\tilde{K} = \begin{bmatrix} K_{SS} & K_{SR} \\ K_{RS} & K_{RS} K_{SS}^{-1} K_{SR} \end{bmatrix}$

时间复杂度从 $O(n^3)$ 降到 $O(m^2 n)$，当 $m \ll n$ 时大幅加速。

注意：Nystrom 近似的质量取决于采样点的代表性。均匀随机采样通常表现不错，但对于分布不均匀的数据，k-means++ 初始化或分层采样可能更好。

与其他方法的联系

谱聚类 vs. K-means

K-means 假设聚类是凸的球形区域（因为它用欧氏距离）。谱聚类没有这个限制——它通过 Laplacian 特征向量做非线性映射，能处理任意形状的聚类。经典的”两个同心圆”数据，k-means 完全失败，而谱聚类轻松成功。

谱聚类 vs. PCA

PCA（Art. 6）是对协方差矩阵 $C = \frac{1}{n-1}\tilde{X}^T\tilde{X}$ 的特征分解。谱聚类是对图 Laplacian $L = D - A_G$ 的特征分解。两者都是”用特征向量做降维”，但作用的矩阵不同：

	PCA	谱聚类
目标矩阵	协方差矩阵 $C$	图 Laplacian $L$
取的特征值	最大的 $k$ 个	最小的 $k$ 个
编码的信息	方差最大的方向	变化最缓慢的图信号
处理的结构	线性	非线性（通过图/kernel）

注意特征值的方向正好相反：PCA 取最大特征值（最大方差方向），谱聚类取最小特征值（最平滑的信号方向）。

图 Laplacian 与随机游走

$L_\text{rw} = I - D^{-1}A_G$ 中的 $P = D^{-1}A_G$ 就是图上随机游走的转移矩阵（Art. 19 随机游走）。$L_\text{rw}$ 的特征向量与 $P$ 的特征向量相同（如果 $P\mathbf{v} = \mu\mathbf{v}$，则 $L_\text{rw}\mathbf{v} = (1-\mu)\mathbf{v}$）。这意味着谱聚类和图上的随机游走本质上在看同一个结构——随机游走者倾向于被”困”在紧密连接的社区内，难以跨越稀疏的边界。

总结与展望

本文建立了图 Laplacian 的完整理论框架，从定义到谱聚类算法：

• 图 Laplacian $L = D - A_G$：离散 Laplace 算子的矩阵形式，衡量节点值与邻居的偏差
• 核心二次型 $\mathbf{f}^T L \mathbf{f} = \frac{1}{2}\sum_{i,j}(A_G)_{ij}(f_i - f_j)^2$：度量信号在图上的总变化，保证 $L$ 半正定
• 零特征值个数 = 连通分量数：特征值直接编码图的全局拓扑
• Fiedler 向量（$\lambda_2$ 对应特征向量）：最优二分割的松弛解，按符号切割即得近似最优 RatioCut
• 谱聚类算法：Laplacian 前 $k$ 个特征向量 + k-means，能处理任意形状的聚类
• Nystrom 近似：采样 $m \ll n$ 个锚点，将 $O(n^3)$ 降到 $O(m^2 n)$

图 Laplacian 的谱理论不仅是聚类的工具，更是理解图上信号处理的基础。下一篇，我们将看到 Laplacian 如何驱动图上的信号扩散——每一次 Laplacian 平滑都让节点的值向邻居”靠拢”。图卷积网络（GCN）的每一层本质上就是一次归一化 Laplacian 平滑加上可学习的变换——消息传递（message passing）就是矩阵乘法。从谱聚类到 GNN，同一个 Laplacian 矩阵贯穿始终。