机器学习中的谱图理论

1. 什么是谱图理论？

谱图理论通过表示图的矩阵的特征值与特征向量来研究图。我们不再逐个推敲顶点和边，而是把整张图编码成一个矩阵，并从该矩阵的谱（即其特征值的集合）中读出它的结构。它是一座桥梁，把离散的组合对象与连续而高度成熟的线性代数机器连接起来。

正是这座桥让机器学习如此重视它。现实数据绝大多数是关系型的：社交网络、分子、引文图、道路地图、图像的像素，以及词语的共现。然而大多数学习算法期望整齐的数值向量作为输入。谱方法通过把图转化为坐标来化解这一矛盾，这是一种可以聚类、嵌入并送入神经网络的几何。

这一领域在纯数学中根基深厚（Fiedler、Chung 等人的工作），但已成为一套实用工具。正如 Daniel Spielman 在他广为使用的耶鲁讲义中所言，谱揭示了"一张图连接得有多好、它是否有良好的簇，以及信息如何在其中扩散"。这三个问题正是无监督学习的核心。

2. 从图到矩阵：拉普拉斯矩阵

三个矩阵描述一张有 n 个顶点的图。邻接矩阵 A 在顶点 i 与 j 之间有边时，于 (i, j) 处取 1。度矩阵 D 是对角矩阵，存放每个顶点的度。主角是图的拉普拉斯矩阵：

L = D − A

拉普拉斯矩阵是对称且半正定的，每一行之和为零，并且其行为如同物理学中拉普拉斯算子的离散版本，它衡量图上的信号从一个节点到相邻节点变化了多少。这一直觉体现在其二次型 xᵀLx = Σ (xᵢ − xⱼ)² 中，对每条边求和：当相连顶点取值相近时它很小，取值相异时它很大。

实践中通常更倾向使用归一化拉普拉斯矩阵，它针对不均衡的度进行重新缩放。对称版本为 L_sym = I − D^(−1/2) A D^(−1/2)，随机游走版本为 L_rw = I − D^(−1) A。归一化可防止高度数的枢纽节点主导谱，而大多数机器学习方案，无论是谱聚类还是图神经网络，都建立在这些归一化形式之上。

3. 图的谱：作为结构的特征值

由于拉普拉斯矩阵是对称且半正定的，它的所有特征值都是实数且非负。我们将它们排序为 0 = λ₁ ≤ λ₂ ≤ … ≤ λₙ。这个有序列表就是图的谱，而它的信息量惊人。

• 最小的特征值始终是 0，其特征向量为常向量。
• 零特征值的个数等于连通分量的个数。只有一个 0 意味着图是连通的。
• 第二小的特征值 λ₂ 就是著名的代数连通度，或称 Fiedler 值（Miroslav Fiedler，1973）。它越接近零，图就越容易被分成两块。

从 λ₂ 到 λ₃ 的跃升称为谱间隙，间隙越大，越强烈地暗示图具有清晰的簇结构。对应 λ₂ 的特征向量，Fiedler 向量，为每个顶点赋予一个数，其符号告诉你它落在割的哪一侧。著名的 Cheeger 不等式使之严格化，用 λ₂ 界定图的最稀疏割。仅凭一个数，谱就回答了：这些数据是一团，还是若干团？

4. 谱聚类

谱聚类是机器学习中的旗舰应用，它直接源自上一节。配方很短：

1. 从数据构建相似度图，通常是 k 近邻图，或连接邻近点的高斯（RBF）核。
2. 构造归一化拉普拉斯矩阵，并计算其最小的 k 个特征向量。
3. 把这些特征向量按列堆叠，为每个点赋予新的 k 维坐标，即谱嵌入。
4. 在该嵌入空间中运行普通的 k-means。

既然已有 k-means，何必费此周折？因为 k-means 只能切出圆形、凸形的团块，而谱聚类能够还原任意形状的簇，经典的"两个交错的月牙"或同心圆环会让 k-means 彻底失效。从数学上看，它是归一化割问题的一个可处理的松弛，而该问题的精确形式是 NP 难的；特征向量给出最佳的连续近似。该方法因 Shi 与 Malik 用于图像分割的 Normalized Cuts（2000）以及 Ng、Jordan 与 Weiss（2002）而广为人知，而 Ulrike von Luxburg 2007 年的教程至今仍是权威的实用指南。

一个经典的演示是"双月牙"（two moons）数据集，两个相互交错的月牙形状。朴素的 k-means 会从正中间一刀切下去，结果失败，因为这两个月牙不是线性可分的。谱聚类在邻域图上工作，沿着每个月牙的弧线延展，能正确地还原出两个簇。同样的优势也出现在同心圆环上，以及任何簇彼此连通却并不紧凑的数据上。

5. 流形学习与拉普拉斯特征映射

切割图的那些特征向量同样可以把高维数据"压平"。这正是 拉普拉斯特征映射（Laplacian Eigenmaps）的思想，由 Mikhail Belkin 与 Partha Niyogi 于 2003 年提出。其前提，流形假设，认为现实中的高维数据（人脸、笔迹、基因表达）实际上位于嵌入该空间的、维度低得多的弯曲曲面之上。

拉普拉斯特征映射通过构建邻域图，再选取低维坐标 y 使 Σ wᵢⱼ ‖yᵢ − yⱼ‖² 最小，从而还原该曲面，让原空间中相近的点在嵌入中仍然相近。其解再一次是图拉普拉斯矩阵的最小的非平凡特征向量。与只能找到线性投影的 PCA 不同，这是真正非线性的降维，并与扩散映射以及 scikit-learn 中的谱嵌入密切相关。它是可视化以及分类前预处理的主力工具。

值得把这些方法与流行的可视化工具 t-SNE 和 UMAP 区分开来。后者同样基于图、在精神上也保持邻域关系，但它们优化的是一个概率目标，而不是直接求解拉普拉斯特征向量。当你想要一个快速、确定性、且具有清晰线性代数解释的嵌入时，拉普拉斯特征映射依然很有吸引力。

6. 谱图神经网络

谱图理论也是深度学习一整个分支的理论基础。关键思想是图傅里叶变换：把定义在顶点上的信号投影到拉普拉斯矩阵的特征向量上，所起的作用与经典傅里叶变换对时间序列的作用相同。特征值充当频率，而"过滤"图信号意味着重新加权其谱分量。

Bruna 等人于 2014 年以此方式定义了图上首个谱卷积。它能用，但完整的特征分解代价为 O(n³)，且滤波器不具局部性。两项改进让这一思想变得实用：

• ChebNet（Defferrard、Bresson 与 Vandergheynst，NeurIPS 2016）用拉普拉斯矩阵的切比雪夫多项式来逼近谱滤波器。这使滤波器严格局部化，运行时间与边数成线性，无需特征分解。
• 图卷积网络（Kipf 与 Welling，ICLR 2017）把 ChebNet 简化为一阶形式，给出如今无处不在的传播规则 H' = σ( D̃^(−1/2) Ã D̃^(−1/2) H W )，其中 à = A + I 加上自环。

这一层优雅的结构，归一化拉普拉斯矩阵的直系后裔，正是当今 GNN 在推荐系统、欺诈检测、交通预测以及药物与材料发现中应用的动力来源。

一个实用的注意事项：纯谱滤波器被绑定在单一固定的图上，因为图一旦改变，特征向量也随之改变。这正是该领域大量转向空间消息传递网络的原因，后者可以泛化到不同规模的图。即便如此，谱视角仍然是理解图卷积究竟对信号做了什么的最清晰的透镜。

7. 工具与何时使用谱方法

你很少需要亲手实现线性代数。成熟、可信的库覆盖了整条流水线：

• scikit-learn，用于聚类与流形学习的 SpectralClustering 与 SpectralEmbedding。
• NetworkX，用于分析的 laplacian_matrix、normalized_laplacian_matrix 与 fiedler_vector。
• SciPy，scipy.sparse.linalg.eigsh，可高效地只计算大型稀疏拉普拉斯矩阵的少数几个最小特征向量。
• PyTorch Geometric 与 DGL，生产级 GNN 层，包括 GCN 与 ChebNet。

几条实用经验：始终使用归一化的拉普拉斯矩阵；使用稀疏特征求解器，只索取所需的最小特征向量；并用特征间隙启发式来选择簇数，在排序后的谱中寻找最大的跃升。当数据天然是图、当簇非凸、或当你需要一个有原则的低维嵌入时，就该求助于谱方法。当簇明显是圆形且数据已向量化时，朴素的 k-means 可能更快且同样好用。谱图理论并不取代你的工具箱，它赋予它几何。

一览：如何选择方法