路径： 本科数学/ 进阶数学/ 矩阵分析与谱图论/谱图论：拉普拉斯、图傅里叶与 GNN 前置
28

谱图论：拉普拉斯、图傅里叶与 GNN 前置

Spectral Graph Theory · 把"图"变成"矩阵"再变成"信号"

【章首引子】社交网络、分子结构、知识图谱，本质都是"点连着边"的图。怎么让神经网络直接吃图？答案是：把图翻译成一个矩阵——拉普拉斯矩阵——然后像处理信号一样处理它。谱图论就是这门"图的傅里叶分析"。GCN、GraphSAGE、ChebNet 这些图神经网络，全都能在这套谱语言里被说清楚。这一章是连接"组合图论"与"深度学习 GNN"的那座桥。

卡必背公式 / 记忆口诀
未归一化拉普拉斯：$L=D-A$
归一化：$L_{\mathrm{sym}}=D^{-1/2}LD^{-1/2}=I-D^{-1/2}AD^{-1/2}$
二次型：$x^\top L x = \sum_{(i,j)\in E}(x_i-x_j)^2$
随机游走平稳分布：$\pi_i\propto d_i$
口诀：图变矩阵看 L，谱就是 L 的特征值

① 是什么：图的矩阵化身

啥拉普拉斯矩阵与它的谱

① 邻接与度：无向图 $G=(V,E)$，邻接矩阵 $A\in\{0,1\}^{n\times n}$（对称），度矩阵 $D=\mathrm{diag}(d_1,\dots,d_n)$，$d_i$ 是节点 $i$ 的度数。

② 拉普拉斯矩阵：$L = D - A$。它是对称半正定矩阵，最小特征值 $\lambda_1=0$，对应全 1 向量 $\mathbf{1}$（因为 $L\mathbf{1}=0$）。其二次型有漂亮解释：$x^\top L x = \frac12\sum_{(i,j)\in E}(x_i-x_j)^2$——它衡量"信号 $x$ 在相邻节点上有多不平滑"。

③ 归一化拉普拉斯：为避免度数差异主导，定义 $L_{\mathrm{sym}}=D^{-1/2}L D^{-1/2}=I-D^{-1/2}A D^{-1/2}$，特征值落在 $[0,2]$。还有随机游走拉普拉斯 $L_{\mathrm{rw}}=D^{-1}L=I-D^{-1}A$，其特征值与 $L_{\mathrm{sym}}$ 相同。

④ 谱 = 特征值全体：把 $L$（或 $L_{\mathrm{sym}}$）做特征分解 $L=U\Lambda U^\top$，$\Lambda=\mathrm{diag}(\lambda_1,\dots,\lambda_n)$（$\lambda_1=0\le\lambda_2\le\cdots\le\lambda_n$）。这些特征值与特征向量承载了图的连通性、社区、平滑性等信息。

⑤ 图傅里叶变换：把特征向量 $u_k$ 当作"图上的频率基"，信号 $x\in\mathbb{R}^n$ 的图傅里叶变换是 $\hat{x}(k)=u_k^\top x$。"低频"对应平滑信号，"高频"对应在边上剧烈震荡的信号。

② 怎么想到的

思解题心法

1

要衡量"图上的不平滑" → 看 $x^\top L x$。它正好是相邻节点差的平方和，越小越平滑。

2

要判断连通 / 切图 → 看 $\lambda_2$（Fiedler 值）。$\lambda_2>0$ 当且仅当图连通；$\lambda_2$ 小说明图"很勉强才连起来"（瓶颈细）。

3

要找平稳分布 → 看随机游走。随机游走转移 $P=D^{-1}A$，平稳分布 $\pi\propto$ 度数。

4

要处理图信号 → 做图傅里叶。把信号投影到 $L$ 的特征向量上，就在"图频域"里滤波。

5

要搭 GNN → 看 $L$ 与归一化邻接。GCN/ChebNet 的每一层，本质是在图上做一次局部谱滤波。

证谱图论的核心定理与公式

核心定理：① 二次型：$x^\top L x = \frac12\sum_{(i,j)\in E}w_{ij}(x_i-x_j)^2$（无向图）。② 连通性：$\lambda_2(L)>0\iff$ 图连通；若图有 $c$ 个连通分量，则 $0$ 是 $c$ 重特征值。③ Cheeger 不等式：$\frac{h_G}{2}\le\lambda_2\le 2h_G$，其中 $h_G=\min_{S}\frac{|\partial S|}{\min(|S|,|V\setminus S|)}$ 是 Cheeger 常数（稀疏割的度量）。④ 随机游走：$P=D^{-1}A$，平稳 $\pi$ 满足 $\pi P=\pi$，且 $\pi_i=\frac{d_i}{2|E|}\propto d_i$。⑤ 谱聚类：用 $u_2$（Fiedler 向量）的符号做二分类最优割（近似）。⑥ GNN 关系：GCN 层 $H^{(l+1)}=\sigma(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}H^{(l)}W^{(l)})$，其中 $\tilde{A}=A+I$，$\tilde{D}$ 为其度；该归一化邻接等于 $I-\tilde{L}_{\mathrm{sym}}$ 的一阶近似。

推导思路（二次型与连通性）：① 展开 $x^\top L x = x^\top D x - x^\top A x = \sum_i d_i x_i^2 - \sum_{(i,j)}2x_i x_j = \frac12\sum_{(i,j)}(x_i-x_j)^2\ge0$，故 $L\succeq0$。② 若图连通，非零向量 $x\perp\mathbf{1}$ 时必有某条边两端异号，使平方和 $>0$，故 $\lambda_2>0$；若图有 $c$ 个分量，每个分量取常数的向量都使平方和为 0，故 0 是 $c$ 重特征值。

推导思路（Cheeger 与随机游走）：Cheeger 不等式左边来自"把 $u_2$ 阈值化得到割"的变分论证（$\lambda_2=\min_{x\perp\mathbf{1}}\frac{x^\top L x}{x^\top x}$），右边来自"在割边界上构造测试向量"；随机游走的平稳方程 $\pi P=\pi$ 即 $\pi D^{-1}A=\pi$，两边乘 $D$ 得 $\pi A = \pi D$，对分量即 $\sum_j \pi_j A_{ji}=\pi_i d_i$，取 $\pi_i\propto d_i$ 立得满足。

推导思路（GCN 与谱的关系）：谱图卷积在频域为 $g_\theta(L)=U g_\theta(\Lambda)U^\top$；令 $g_\theta(\Lambda)\approx(1-\lambda)$ 的线性近似并加自环 $\tilde{A}=A+I$，归一化后即 $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}=I-\tilde{L}_{\mathrm{sym}}$。ChebNet 进一步用切比雪夫多项式 $T_k(\tilde{L})$ 把滤波写成 $K$ 阶局部传播，避免显式特征分解。

直觉把握：$L$ 的特征值像"图的频率"——$\lambda$ 小意味着在这支特征向量上信号很平滑（低频/社区内部一致），$\lambda$ 大意味着在边上剧烈震荡（高频）。GNN 每传一层，就是让节点特征向邻居平均一点（低通滤波），传太多层所有节点趋于一致，这就是过平滑。

③ 完整解法：三个例题

例题1：3 个点的路径图 $1-2-3$ 的拉普拉斯（手算二次型）
【审题】$A=\begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix}$，$D=\mathrm{diag}(1,2,1)$。
思路：$L=D-A$ 直接算。
逐步解法：$L=\begin{pmatrix}1&-1&0\\-1&2&-1\\0&-1&1\end{pmatrix}$。验证二次型：取 $x=(x_1,x_2,x_3)^\top$，$x^\top L x=(x_1-x_2)^2+(x_2-x_3)^2=\frac12\sum_{\text{边}}(x_i-x_j)^2$，与定理一致。$\lambda_1=0$（$\mathbf{1}$ 为 eigenvector），图连通故 $\lambda_2>0$。
例题2：随机游走的平稳分布（度数即权重）
【审题】仍用上面的路径图 $1-2-3$，度数 $(1,2,1)$，边数 $|E|=2$。
思路：平稳分布 $\pi_i\propto d_i$。
逐步解法：$\pi\propto(1,2,1)$，归一化得 $\pi=(\frac14,\frac12,\frac14)$。验证：$\pi P = (\frac14,\frac12,\frac14)\begin{pmatrix}0&1&0\\\frac12&0&\frac12\\0&1&0\end{pmatrix}=(\frac14,\frac14+\frac14,\frac14)=(\frac14,\frac12,\frac14)=\pi$。直觉：中间节点度数高，随机游走更常停在它附近。
例题3：图傅里叶变换一个简单信号（投影到特征基）
【审题】路径图上信号 $x=(1,0,-1)^\top$。
思路：把 $x$ 投影到 $L$ 的特征向量上。
逐步解法：$L$ 的特征向量（归一化后）含 $u_2\propto(1,0,-1)^\top$（对应非零特征值）。于是 $\hat{x}(2)=u_2^\top x = \|u_2\|^{-1}\cdot(1\cdot1+0+(-1)\cdot(-1))=2/\|u_2\| >0$，能量集中在这一支"振荡"基上——说明信号在两端异号、在边上变化大，正是高频图信号。
谱图论核心公式 $L = D - A$  |  $L_{\mathrm{sym}} = I - D^{-1/2} A D^{-1/2}$  |  $x^\top L x = \frac12\sum_{(i,j)\in E}(x_i-x_j)^2$
连通性：$\lambda_2(L) > 0 \iff$ 连通  |  Cheeger：$\frac{h_G}{2}\le\lambda_2\le 2h_G$
随机游走平稳：$\pi_i\propto d_i$  |  图傅里叶：$\hat{x}(k)=u_k^\top x$
GCN 层：$H^{(l+1)}=\sigma(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}H^{(l)}W^{(l)})$，$\tilde{A}=A+I$

④ 用途与 AI 落点（GNN 前置）

GNN 前置
AI 落点 1：谱聚类

用 $L$ 的 Fiedler 向量 $u_2$（或前若干特征向量）把节点嵌入低维空间再聚类，等价于在谱域做"最优割"的松弛。是社区检测、图像分割的经典方法。

GNN 前置
AI 落点 2：GCN 的归一化邻接

GCN 的核心矩阵 $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ 正是 $I-\tilde{L}_{\mathrm{sym}}$ 的一阶近似——每一层 GCN 等价于在图上做一次"带自环的低通滤波"，让邻居信息平滑汇聚。

GNN 前置
AI 落点 3：ChebNet 与局部化

ChebNet 用切比雪夫多项式 $T_k(\tilde{L})$ 近似图卷积核，只依赖 $K$ 跳邻居，避免对全图做特征分解，可扩展到超大图，是 GNN 高效化的关键。

稳定性
AI 落点 4：PageRank 与随机游走

PageRank = 带重启的随机游走在图上的平稳分布；节点重要性排序、推荐系统的随机游走召回，数学内核就是本章的平稳分布 $\pi\propto d_i$ 及其推广。

GNN 前置
AI 落点 5：过平滑的特征值解释

GNN 层数加深时，特征不断向低频（$L$ 的小特征值方向）收缩；当最大特征值对应方向被压没，所有节点特征趋同——过平滑可用 $L$ 的谱半径与滤波器的频率响应来解释与缓解。

⑤ 延展

展知识衔接地图

往本科走：组合图论的邻接矩阵、树、最短路（math-undergrad-logic.html）、高中图论（math-senior.html#graph）给出"点边"的直觉。

往算法走：随机游走的平稳分布衔接马尔可夫链与 MCMC（math-undergrad-stochastic.html）；图的谱衔接矩阵分析的条件数/低秩（本章上一章）；GNN 训练衔接最优化理论（math-adv-optimization.html）。

思维陷阱

用未归一化 $L$ 直接喂 GNN。度数差异巨大时，$D-A$ 会让高度数节点主导，必须归一化成 $L_{\mathrm{sym}}$ 或加自环 $\tilde{A}=A+I$。

以为 $\lambda_2>0$ 就"连通得很好"。$\lambda_2$ 很小（但 $>0$）说明图只是"勉强相连"（细瓶颈），一割就断；Cheeger 不等式正是量化这种脆弱性。

混淆 $L_{\mathrm{sym}}$ 与 $L_{\mathrm{rw}}$ 的特征向量。两者特征值相同，但特征向量不同；做谱聚类要用 $L_{\mathrm{sym}}$ 的特征向量，随机游走分析用 $L_{\mathrm{rw}}$。

练习

【基础】两节点图 $1-2$（一条边），写出它的 $L$ 与特征值，并验证 $\lambda_1=0$ 对应全 1 向量。

查看思路与解答$D=\mathrm{diag}(1,1)$，$A=\begin{pmatrix}0&1\\1&0\end{pmatrix}$，$L=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$。特征值 $0,2$；$\lambda_1=0$ 对应 $\mathbf{1}=(1,1)^\top$，确实 $L\mathbf{1}=0$。
【自评反馈】和答案对得上 → 继续下一题；对不上 → 回到「① 是什么」的二次型定义重算。

【进阶】证明：无向图 $G$ 连通当且仅当 $\lambda_2(L)>0$；若有 $c$ 个连通分量，说明 0 是几重特征值。

查看思路与解答见 deep-dive：连通时任意 $x\perp\mathbf{1}$ 都有边两端异号使 $x^\top Lx>0$，故 $\lambda_2>0$；反之若不连通，每个分量取常数构成线性无关的零空间向量，故 0 是 $c$ 重特征值。
【自评反馈】和答案对得上 → 继续下一题；对不上 → 回到 deep-dive「连通性」推导段。

【挑战】把 GCN 层 $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ 写成 $I-\tilde{L}_{\mathrm{sym}}$ 的形式，并解释为什么"层数越深、节点特征越平滑"——用 $L$ 的特征值说明过平滑。

查看思路与解答由 $\tilde{L}_{\mathrm{sym}}=I-\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ 立得该层矩阵 $=I-\tilde{L}_{\mathrm{sym}}$。对特征向量 $u_k$（特征值 $\tilde{\lambda}_k\in[0,2]$），每层把它乘上 $(1-\tilde{\lambda}_k)$；$\tilde{\lambda}_k$ 越小（越低频）保留越多，$\tilde{\lambda}_k$ 越大衰减越快。多层后只剩下对应 $\tilde{\lambda}_k\approx0$ 的平滑方向，所有节点特征趋同 → 过平滑。
变式追问：举一反三
  1. 跨尺度：若图是两个互不相连的团（$c=2$），它的拉普拉斯有几个 0 特征值？此时"谱聚类"用 $u_2$ 还能正确分开这两团吗？该用哪些特征向量？
  2. 改条件：把无向图换成有向图，$L=D-A$ 不再对称，二次型 $x^\top L x=\frac12\sum_{(i,j)}(x_i-x_j)^2$ 还成立吗？有向情形该用什么矩阵（提示：拉普拉斯的随机游走版）？
  3. 反向应用：过平滑说"层数加深特征趋同"。若故意在 GNN 里加入"高频通道"（保留大 $\lambda_k$ 方向），能缓解过平滑吗？这和可学习的图滤波器 $g_\theta(\Lambda)$ 有什么关系？
费曼学习法：讲给别人听
合上书，给一个完全不懂的人讲清楚「谱图论：拉普拉斯、图傅里叶与 GNN 前置」——说不清楚的地方就是你没真懂的。
  1. 用自己的话讲：把图写成拉普拉斯矩阵 $L=D-A$；它的特征值（谱）描述图的连通性与平滑性；图傅里叶把节点信号投影到 $L$ 的特征向量上；GCN 每层就是图上的一次低通滤波，对应 $I-\tilde{L}_{\mathrm{sym}}$。
  2. 举个反例（什么条件下不成立）：图不连通时 $\lambda_2=0$、谱聚类 $u_2$ 失效；直接用未归一化 $L$ 时高度数节点会主导；有向图下 $L$ 不再对称、二次型形式改变。
  3. 哪里还说不清：为什么 Cheeger 不等式只给"近似"而非精确割？GCN 的归一化邻接与真正的谱滤波之间，误差到底来自哪一步近似？
记
小结卡

① 拉普拉斯 $L=D-A$，二次型 $x^\top L x=\frac12\sum_{\text{边}}(x_i-x_j)^2$；$\lambda_1=0$ 对应 $\mathbf{1}$，$\lambda_2>0\iff$ 连通。

② 归一化 $L_{\mathrm{sym}}=I-D^{-1/2}AD^{-1/2}$；随机游走平稳 $\pi\propto d_i$；Cheeger 不等式 $\frac{h_G}{2}\le\lambda_2\le 2h_G$。

③ 图傅里叶 $\hat{x}(k)=u_k^\top x$；GCN 层 $=I-\tilde{L}_{\mathrm{sym}}$ 的一阶低通近似，层数过深导致过平滑。

可视化：谱嵌入——用 $L$ 的第 2、3 特征向量把图投影到平面
左：6 节点图（两个社区 + 一条桥）。右：$L$ 的特征值谱。节点的平面坐标取 $(u_2,u_3)$，可见两个社区自动分开——这正是谱聚类"看得见"的数学根据。
社区 A 节点 社区 B 节点 边 最小非零特征值 $\lambda_2$
← 上一节 研究生数学总览