谱图论：从图拉普拉斯到图信号处理

传统 DSP 的频域分析范式

在传统离散信号处理中，Nyquist–Shannon 采样定理告诉我们：若信号带宽有限（band-limited），以不低于两倍带宽的频率采样即可完美恢复。这一结论依赖于一个关键结构——傅里叶基。给定均匀采样的离散信号序列 $\mathbf{x} = (x_0, x_1, \ldots, x_{N-1})$，其离散傅里叶变换（DFT）定义为：

其逆变换将信号展开为频率基 $e^{i 2\pi kn/N}$ 的线性组合。频域分析的强大之处在于：频率 $k$ 编码了信号的平滑/振荡程度——低频率分量对应全局平滑，高频率分量对应快速变化。卷积定理 $\widehat{x \ast h} = \hat{x} \cdot \hat{h}$ 使得滤波操作变成频域中的逐点乘法。

图数据为何需要新框架

然而现实中的大量数据并非定义在均匀网格上。考虑以下场景：

• 一个社交网络：节点 = 用户，边 = 关注关系，信号 = 用户的购买偏好评分
• 一个脑网络：节点 = 脑区，边 = 白质纤维连接，信号 = fMRI 时间序列
• 一个传感器网络：节点 = 传感器，边 = 空间邻近关系，信号 = 温度/湿度读数

这些数据的共同特征是：信号定义在图的顶点上，但图的结构是非规则、非均匀的。在这样的域上，经典的 DFT 没有定义，因为不存在等间隔的"时间轴"。

核心思路：用图拉普拉斯的特征基替代傅里叶基

谱图论提供了一种自然的推广思路。观察拉普拉斯算子在欧几里得空间中的作用：二阶导数算子 $\Delta = -\nabla^2$ 的特征函数正是傅里叶基 $e^{ikx}$，对应特征值 $\lambda_k = k^2$。这一定义完全可以迁移到图上——用图拉普拉斯矩阵 $L$ 替代连续拉普拉斯算子，其特征向量就扮演"图上的傅里叶基"角色：

低特征值（接近 0）的特征向量对应"全局平滑"的图信号模式——信号在相邻节点间变化平缓；高特征值的特征向量则对应高度振荡的"细节"模式。这与经典频域分析中低频/高频的对应完全一致，只是基底从正弦波变成了图的结构自适应基。

三种基本形式

设无向图 $G = (V, E, \mathbf{W})$ 有 $N$ 个顶点，顶点集 $V = \{1, 2, \ldots, N\}$，加权邻接矩阵 $\mathbf{W} \in \mathbb{R}^{N\times N}$ 满足 $W_{ij} = W_{ji} \geq 0$，且 $W_{ij} > 0$ 当且仅当 $(i,j) \in E$。度矩阵 $\mathbf{D}$ 为对角矩阵，$D_{ii} = d_i = \sum_{j=1}^N W_{ij}$。

三种矩阵之间存在明确关系：$\mathbf{L}_{\text{sym}} = \mathbf{D}^{1/2} \mathbf{L}_{\text{rw}} \mathbf{D}^{-1/2}$，它们的谱（特征值集合）紧密关联。

半正定性

对于任意向量 $\mathbf{x} \in \mathbb{R}^N$，组合拉普拉斯矩阵满足：

式（1）是理解拉普拉斯矩阵性质的钥匙：它度量了信号在图边上的总变化量（variation）。由于 $W_{ij} \geq 0$ 且 $(x_i - x_j)^2 \geq 0$，对所有 $\mathbf{x}$ 都有 $\mathbf{x}^\top \mathbf{L} \mathbf{x} \geq 0$，故 $\mathbf{L}$ 半正定。

特征值的代数意义

设 $\mathbf{L}$ 的特征值按升序排列为：

Fiedler 特征值（代数连通度）

第二小特征值 $\lambda_2$ 由 Fiedler 在 1973 年命名为 algebraic connectivity（代数连通度）。它提供了图的全局连通性的一种代数度量。直观上，$\lambda_2$ 越大，说明图的"连接越紧密"，越难以被分割成两部分。反之，$\lambda_2$ 接近 0 表明图存在一个窄"瓶颈"（bottleneck），去掉少量边即可将图分裂。$\lambda_2$ 的对应特征向量 $\mathbf{u}_2$ 称为 Fiedler 向量，是谱聚类的核心工具。

下面通过一个简单图例说明图拉普拉斯矩阵的结构与特征值含义：

flowchart LR

subgraph Graph["图 G = (V, E)"]

A((1)) ---|"W₁₂"| B((2))

A((1)) ---|"W₁₃"| C((3))

B((2)) ---|"W₂₃"| C((3))

B((2)) ---|"W₂₄"| D((4))

C((3)) ---|"W₃₄"| D((4))

end

subgraph Matrices["拉普拉斯矩阵"]

L1["L = D - W\n\nD = diag(d₁, d₂, d₃, d₄)\nd₁ = W₁₂ + W₁₃\n..."]

L2["谱 λ₁=0 ≤ λ₂ ≤ λ₃ ≤ λ₄\n\nλ₂ = 代数连通度\nu₂ = Fiedler 向量"]

end

Graph --> Matrices

左侧展示了一个四节点加权图的拓扑结构。每个节点的度 $d_i$ 是其所有邻边权重之和。对角矩阵 $\mathbf{D}$ 记录各节点的度，而 $\mathbf{L} = \mathbf{D} - \mathbf{W}$ 的特征值按右图顺序排列：零特征值对应常数信号，高特征值对应振荡模式。

路径图与完全图的对比

考虑两个极端图例以建立直观：

• 路径图 $P_N$：$N$ 个顶点排成一条直线，仅相邻顶点相连（边权均为 1）。其拉普拉斯特征值为 $\lambda_k = 2 - 2\cos\frac{\pi(k-1)}{N}$，$k=1,\ldots,N$。注意 $\lambda_2 = 2 - 2\cos\frac{\pi}{N} \approx \frac{\pi^2}{N^2}$（当 $N$ 较大时），随 $N$ 增长趋近于 0——这反映了路径图两端之间存在大量"瓶颈"，整体连通脆弱。
• 完全图 $K_N$：所有顶点两两相连，边权均为 1。度矩阵 $D_{ii}=N-1$，拉普拉斯矩阵 $\mathbf{L} = (N-1)\mathbf{I} - \mathbf{J}$（$\mathbf{J}$ 为全 1 矩阵）。其非零特征值为 $N$，重数 $N-1$。故 $\lambda_2 = N$，非常大，说明完全图不可能被轻易切割。

Cheeger 不等式建立了图的最优切割难度（组合量）与图的代数连通度（代数量）之间的双向不等式关系。

符号准备与 Cheeger 常数

设图 $G = (V, E)$ 的顶点集合被划分为两个非空子集 $S$ 和 $T = V \setminus S$。定义切割（cut）为集合 $\delta(S) = \{ (i,j) \in E : i\in S, j\in T \}$，其容量（volume）之和为 $\text{vol}(S) = \sum_{i\in S} d_i$。

统一解释：代数连通度越大，图越难被"切开"

将两个不等式合并来看：

Cheeger 常数和代数连通度在常数因子（2 倍）范围内相互控制。具体含义：

• 若 $\lambda_2$ 大，则 $h(G) \geq \lambda_2$ 大，切割任何合理的子集都需要大量边，图连通紧密
• 若 $\lambda_2$ 小，则 $h(G) \leq 2\lambda_2$ 小，存在一个相对小的切割，图存在明显分隔

这一结果给谱方法（spectral methods）提供了理论保证：在不知道最优切割的情况下，仅凭 $\lambda_2$ 和 Fiedler 向量就可以得到一个"不算太差"的切割——切割质量至少在两倍最优范围内。谱聚类（spectral clustering）算法正是基于这一原理设计的。

graph TD

subgraph Good["λ₂ 大 → h(G) 大 → 图连通紧密"]

G1["高连通图"] --> E1["λ₂ = 5.2"]

E1 --> C1["任意切割都需大量边"]

C1 --> H1["h(G) ≈ 2λ₂"]

end

subgraph Bad["λ₂ 小 → h(G) 小 → 图存在明显分隔"]

G2["带瓶颈的图"] --> E2["λ₂ = 0.03"]

E2 --> C2["存在小切割"]

C2 --> H2["h(G) ≈ 2λ₂"]

end

style Good fill:#dcfce7

style Bad fill:#fee2e2

上图中展示了两种极端情况：左侧图连通紧密，其代数连通度大，切割任何子集都需要跨越较多边；右侧图存在明显的"瓶颈"区域，其代数连通度接近零，存在相对容易的切割。

拉普拉斯特征向量作为图上的"傅里叶基"

设 $\mathbf{L}$ 的特征值互异（或按重数选取正交基），其特征向量矩阵 $\mathbf{U} = [\mathbf{u}_1, \mathbf{u}_2, \ldots, \mathbf{u}_N] \in \mathbb{R}^{N\times N}$ 满足 $\mathbf{U}^\top \mathbf{U} = \mathbf{I}_N$——即特征向量构成标准正交基。这与 DFT 矩阵的酉性完全对应。

图拉普拉斯 $\mathbf{L}$ 对应的连续拉普拉斯算子 $\Delta = -\nabla^2$ 的特征函数是复指数 $e^{ikx}$，而后者恰好是单位圆（周期边界）上图的拉普拉斯算子的特征函数。因此，图拉普拉斯特征向量的角色就是"结构自适应正交基"，其选择完全由图的结构决定，而非预先固定。

图傅里叶变换（Graph Fourier Transform, GFT）

频率的含义

与经典 DFT 类似，图拉普拉斯特征值的排序定义了频率层级：

• $\lambda_1 = 0$：$\mathbf{u}_1 = \mathbf{1}/\sqrt{N}$，对应的图傅里叶系数 $\hat{x}_1 = \mathbf{1}^\top \mathbf{x}/\sqrt{N}$ 恰好是信号均值（直流分量）
• $\lambda_2$ 低 → 低频 → 全局平滑（相邻节点值相近）
• $\lambda_k$ 高 → 高频 → 局部剧烈变化（相邻节点值差异大）

可以形式化地定义图信号的总变差（Total Variation, TV）：

式（6）揭示了 TV 与 GFT 系数之间的对角关系：每个频率分量对总变差的贡献由其对应特征值加权。因此，低通图滤波器（smoothing filter）抑制高频分量，即降低 $\TV(\mathbf{x})$。

一个具体例子：完全图上的 GFT

在完全图 $K_N$ 中，$\mathbf{L} = N\mathbf{I} - \mathbf{J}$。其特征值为 $\lambda_1 = 0$（对应 $\mathbf{u}_1 = \mathbf{1}/\sqrt{N}$），$\lambda_k = N$（$k=2,\ldots,N$，相互正交的特征向量张成与 $\mathbf{1}$ 正交的子空间）。此时 GFT 退化为：

完全图上的高频分量并不对应任何几何意义——图上任意两点都直接相连，没有"空间"可以振荡。但在真实稀疏图（如传感器网络、脑网络）中，高频特征向量对应图上节点的空间局部振荡模式，具有明确的物理/结构意义。

谱域滤波器设计的基本思想

在经典 DSP 中，线性时不变滤波器通过卷积实现，其频域表示为 $\hat{y}_k = \hat{h}_k \cdot \hat{x}_k$（逐点乘法）。图信号处理中，线性图滤波器定义为信号与图拉普拉斯特征基上的系数变换：

其中 $h(\lambda): [0, \lambda_{\max}] \to \mathbb{R}$ 称为滤波器的 频率响应，是定义在拉普拉斯谱上的函数。逆变换给出空域形式：

其中 $h(\mathbf{L}) = \mathbf{U} \operatorname{diag}(h(\lambda_k)) \mathbf{U}^\top$ 是拉普拉斯矩阵的多项式（更一般地，矩阵函数）。

滤波器类型

ChebNet 的多项式近似

Defferrard et al.（NeurIPS 2016）提出的 ChebNet 通过截断 Chebyshev 多项式近似克服了这一计算瓶颈。核心方法是将频率响应 $h(\lambda)$ 用 $K$ 阶 Chebyshev 多项式展开：

其中 $\tilde{\lambda} = \frac{2}{\lambda_{\max}}\lambda - 1 \in [-1,1]$ 是重新缩放的特征值（确保在 Chebyshev 多项式的定义域内），$T_k$ 为 Chebyshev 多项式，满足递归关系：

截断后：

关键优势：$T_k(\tilde{\mathbf{L}})$ 可以通过递推关系高效计算，每次矩阵-向量乘法只需 O(|E|)（稀疏矩阵乘法），总复杂度 O(K|E|)。参数 $\beta_k$ 通过学习得到，而非手动设计频率响应。

上图展示了三种基本图滤波器的频率响应曲线。蓝色曲线表示低通滤波器，保留低频分量（小的 $\lambda_k$）而抑制高频分量；红色曲线表示高通滤波器，提取局部剧烈变化；绿色曲线表示带通滤波器，仅保留某一频带内的信号成分。

Nyquist-Shannon 采样定理的图上推广

经典 Nyquist-Shannon 定理的图版本需要回答以下问题：给定图上部分节点上的信号值，能否唯一恢复完整的图信号？答案取决于信号的频率支撑。

设图信号 $\mathbf{x}$ 的图傅里叶变换系数满足 $\hat{x}_k = 0$ 对所有 $\lambda_k > \lambda_c$ 成立，即 $\mathbf{x}$ 为 $\lambda_c$-bandlimited。设采样集 $M \subseteq V$，采样后的降采样信号记为 $\mathbf{x}_M$（仅保留 $M$ 上节点的值）。恢复问题：是否存在唯一 $\mathbf{x}$ 使 $\mathbf{x}_M$ 与观察值一致？

图采样定理的关键结果

Ganis et al.（2015）和 Chen et al.（2015）独立给出了图上的采样定理。对于无向连通图上的 band-limited 信号，以下条件等价：

1. 信号 $\mathbf{x}$ 是 $\lambda_c$-bandlimited
2. $\mathbf{x}$ 可以表示为拉普拉斯逆矩阵 $(\mathbf{L} + \epsilon\mathbf{I})^{-1}$ 与某向量的乘积（低秩表示）
3. 在足够稠密的采样集 $M$ 上，仅通过插值即可唯一恢复 $\mathbf{x}$

采样集 $M$ 的充分条件与其 图频率响应支撑 有关。Narang et al.（2013）证明：若采样集的 cardinality 满足 $|M| \geq K$（其中 $K$ 为 bandlimit），且采样矩阵满足一定的 RIP（Restricted Isometry Property）类条件，则存在唯一的完美恢复。

采样定理的图直觉

从 Cheeger 不等式的角度理解：图的代数连通度 $\lambda_2$ 越大，图的"全局耦合"越强，意味着低频信号在不同节点间的相关性越高，从而少量采样点即可蕴含足够的全局信息。反之，路径图这样 $\lambda_2$ 极小的图，节点间相关性弱，需要大量采样才能恢复信号。

与经典的对应关系

图神经网络的谱解释

图神经网络（GNN）近年来在图表示学习中取得了突破性进展，而谱图论为其提供了坚实的理论基础。

GCN（Kipf & Welling, ICLR 2017）的一层前向传播为：

其中 $\tilde{\mathbf{A}} = \mathbf{A} + \mathbf{I}$ 为加自环的邻接矩阵。该传播规则实际上是归一化拉普拉斯 $\mathbf{L}_{\text{sym}}$ 的一阶多项式近似（$K=1$ 的 ChebNet 截断）：

因此，GCN 的每一层就是一个在归一化拉普拉斯谱域上的低通图滤波器。层数增多相当于使用更宽的多项式滤波器逼近，从而能够聚合更广邻域的信息。这解释了 GCN 的"过度平滑"（oversmoothing）现象：堆叠过多层后，低通滤波器反复抑制高频分量，使所有节点嵌入收敛到相似的表示——这正是低通滤波器的固有行为。

传感器网络中的分布式信号处理

在无线传感器网络中，每个传感器仅能与邻居通信，要求分布式算法。Chebyshev 多项式近似的关键特性是 局域性：$T_k(\tilde{\mathbf{L}})\mathbf{x}$ 的第 $i$ 个分量仅依赖于节点 $i$ 的 $K$-跳邻域内的信号值。这意味着分布式实现中，每个节点只需与有限跳邻居交换信息即可完成滤波。

Shuman et al.（2018）在这一方向上做出了系统性贡献，将分布式图信号处理的计算、通信和存储开销量化为 O(K|E|)、O(K|E|) 和 O(N)，与图的规模线性相关。

脑网络分析

功能性磁共振成像（fMRI）数据本质上是大脑区域间的时间序列，每个区域对应图的节点，白质纤维连接定义了边。利用 GSP 工具，研究者可以：

• 对 fMRI 信号做图频域分析，识别功能性连通网络（低频主导）
• 将健康脑网络与病理脑网络（如阿尔茨海默症）对比，发现 $\lambda_2$ 等谱指标在两组间存在显著差异
• 在脑网络上进行 band-pass 滤波（0.01–0.1 Hz）提取低频血氧信号，这正是神经科学中默认模式网络（Default Mode Network）分析的数学实现