谱图理论深度专题

1. 引言

谱图理论（Spectral Graph Theory）是连接代数与图论的桥梁，研究图的邻接矩阵或拉普拉斯矩阵的特征值与图结构性质之间的关系。¹ 在深度学习时代，这一理论为图神经网络（GNN）提供了坚实的数学基础，使得我们能够在谱域设计图卷积滤波器。

---

2. 图拉普拉斯算子

2.1 拉普拉斯矩阵的定义

给定无向图 $G=(V,E)$，其中 $|V|=n$，$|E|=m$，定义：

组合拉普拉斯矩阵：
$L=D-A$

其中：

• $A\in {\mathbb{R}}^{n\times n}$：邻接矩阵，$A_{ij}=1$ 当且仅当 $(i,j)\in E$
• $D\in {\mathbb{R}}^{n\times n}$：度矩阵，$D_{ii}=d_i={\sum }_j{A}_{ij}$

归一化拉普拉斯矩阵：

对称归一化：
$L_{\text{sym}}=D^{-1/2}L{D}^{-1/2}=I-D^{-1/2}A{D}^{-1/2}$

随机游走归一化：
$L_{\text{rw}}=D^{-1}L=I-D^{-1}A$

2.2 拉普拉斯矩阵的基本性质

性质2.1：$L$ 是半正定矩阵，所有特征值 ${\lambda }_i$ 满足 $0={\lambda }_1\le {\lambda }_2\le \cdots \le {\lambda }_n$。

性质2.2：$L$ 的特征向量 $u_1=(1,1,\dots ,1)/\sqrt{n}$ 对应特征值 $0$，当且仅当图是连通的。

性质2.3（二次型解释）：
$x^{\top }Lx=\frac{1}{2}{\sum }_{i,j\in E}(x_i-x_j{)}^2={\sum }_{(i,j)\in E}(x_i-x_j{)}^2$

这一性质表明 $L$ 是图上离散拉普拉斯算子的离散化。

2.3 特征值的谱定理

设 $L$ 的特征值分解为：
$L=U\Lambda U^{\top }={\sum }_{i=1}^n{\lambda }_i{u}_i{u}_i^{\top }$

其中：

• $\Lambda =\text{diag}({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n)$
• $U=[u_1,u_2,\dots ,u_n]$ 是正交特征向量矩阵

---

3. 图上的傅里叶变换

3.1 图傅里叶变换定义

借鉴经典傅里叶变换的思想，定义图傅里叶变换（Graph Fourier Transform）：

正向变换：
$\hat{x}({\lambda }_i)=⟨x,u_i⟩=u_i^{\top }x$

逆向变换：
$x(v)={\sum }_{i=1}^n\hat{x}({\lambda }_i)u_i(v)$

其中 $x\in {\mathbb{R}}^n$ 是定义在图节点上的信号，$u_i(v)$ 是特征向量 $u_i$ 在节点 $v$ 处的分量。

3.2 图频率解释

拉普拉斯矩阵的特征值 ${\lambda }_i$ 可以解释为图上的频率：

特征值	频率解释	特性
${\lambda }_1=0$	最低频率	全局常数信号（$u_1$ 是均匀向量）
${\lambda }_2$	次低频率	与图的宏观结构相关
${\lambda }_k$	中等频率	局部结构特征
${\lambda }_n$	最高频率	剧烈变化的信号（如噪声）

低频信号：变化平缓，在相邻节点间差异小
高频信号：变化剧烈，相邻节点间差异大

3.3 图信号的正则性

使用拉普拉斯二次型定义图信号的总变差（Total Variation）：

$\text{TV}(x)=x^{\top }Lx={\sum }_{(i,j)\in E}(x_i-x_j{)}^2$

• $\text{TV}(x)=0$ 当且仅当 $x$ 是常数信号
• $\text{TV}(x)$ 越小，信号越”平滑”（低频）
• $\text{TV}(x)$ 越大，信号越”粗糙”（高频）

---

4. 谱图卷积

4.1 卷积定理

在图上定义卷积操作。经典信号处理中的卷积定理指出：

$\text{Conv}(x,y)\stackrel{\mathcal{F}}{\leftrightarrow }\hat{x}\cdot \hat{y}$

其中 $\mathcal{F}$ 表示傅里叶变换。

将此定理推广到图上，设 $g_{\theta }$ 是谱域的滤波器（频率响应函数），则图卷积定义为：

$(g_{\theta }\ast x)(v)={\sum }_{i=1}^n\hat{x}({\lambda }_i)g_{\theta }({\lambda }_i)u_i(v)=U(G_{\theta }\circ \hat{x})$

其中 $G_{\theta }=\text{diag}(g_{\theta }({\lambda }_1),\dots ,g_{\theta }({\lambda }_n))$。

4.2 谱域滤波器设计

多项式滤波器：为避免直接计算特征分解，滤波器可参数化为 $K$ 阶多项式：

$g_{\theta }(\lambda )={\sum }_{k=0}^{K-1}{\theta }_k{\lambda }^k$

这使得图卷积变为：

$g_{\theta }\ast x={\sum }_{k=0}^{K-1}{\theta }_k{L}^{k}x$

多项式滤波器的性质：

性质	说明
$K$-局部化	输出仅依赖于 $K$ 跳内的节点
计算效率	避免特征分解，仅需矩阵乘法
表达能力	可表示 $K-1$ 次多项式的任意函数

---

5. 谱聚类与图划分

5.1 谱嵌入

谱聚类的核心思想是利用拉普拉斯矩阵的特征向量进行降维：

1. 计算 $L$ 的前 $k$ 个最小特征值对应的特征向量
2. 将节点映射到 ${\mathbb{R}}^k$ 空间：$v_i\mapsto (u_2(i),u_3(i),\dots ,u_{k+1}(i))$
3. 在低维空间使用 $k$-means 进行聚类

5.2 Cheeger不等式

Cheeger不等式建立了特征值 ${\lambda }_2$ 与图划分质量之间的联系：

$\frac{{\lambda }_2}{2}\le h(G)\le \sqrt{2{\lambda }_2}$

其中 $h(G)$ 是图的 Cheeger 常数（最小割与体积比）。

意义：${\lambda }_2$ 越小，图越容易被分割成两部分；${\lambda }_2$ 越大，图的结构越紧密。

5.3 谱聚类算法

import numpy as np
from sklearn.cluster import KMeans
 
def spectral_clustering(A, k):
    """
    谱聚类算法
    
    参数:
        A: 邻接矩阵 (n x n)
        k: 聚类数
    返回:
        labels: 节点聚类标签 (n,)
    """
    n = A.shape[0]
    D = np.diag(A.sum(axis=1))
    L = D - A
    
    # 归一化拉普拉斯
    D_inv_half = np.diag(1.0 / np.sqrt(A.sum(axis=1)))
    L_sym = D_inv_half @ L @ D_inv_half
    
    # 特征分解（取前k个最小特征值）
    eigenvalues, eigenvectors = np.linalg.eigh(L_sym)
    U = eigenvectors[:, :k]
    
    # 行归一化
    U_norm = U / (np.linalg.norm(U, axis=1, keepdims=True) + 1e-8)
    
    # k-means聚类
    kmeans = KMeans(n_clusters=k, random_state=42)
    labels = kmeans.fit_predict(U_norm)
    
    return labels

---

6. 特征值与图结构

6.1 特征值与图的连通性

连通分量数：$L$ 的零特征值的重数等于图的连通分量数。

** bipartite 性**：图是二部的当且仅当 $L$ 的最大特征值 ${\lambda }_n=2d_{\max }$（对于正则图）。

6.2 谱间隙与混合时间

谱间隙（Spectral Gap）：$\gamma ={\lambda }_2$（对于连通图）

谱间隙与随机游走的混合时间（Mixing Time）直接相关：

$t_{\text{mix}}\approx \frac{1}{\gamma }\log n$

• 谱间隙越大，随机游走混合越快
• 谱间隙越小，图结构越”细长”，信息传播越慢

6.3 有效电阻

节点 $i$ 和 $j$ 之间的有效电阻与拉普拉斯矩阵伪逆有关：

$R_{ij}^{\text{eff}}=(L^{+}{)}_{ii}+(L^{+}{)}_{jj}-2(L^{+}{)}_{ij}$

有效电阻在分析信息瓶颈和 over-squashing 时起重要作用。²

---

7. 图信号处理框架

7.1 滤波器算子

设 $g_{\theta }$ 是谱域定义的滤波器，则对应的图滤波器算子为：

$T_g[x]=g(L)x=U{G}_{\theta }{U}^{\top }x$

频率响应：$g_{\theta }$ 决定了不同频率成分被放大或衰减的程度。

7.2 局部化算子

通过多项式近似，可以构造局部化的图滤波器：

$g(L)={\sum }_{k=0}^{K-1}{c}_k{L}^k$

这类算子的空间支撑（Spatial Support）为 $K$ 跳邻域，即：

$\text{supp}(g(L)\cdot {\delta }_i)\subseteq \{j:d(i,j)\le K\}$

7.3 插值与重构

给定部分节点上的信号值，恢复完整信号的问题可以在谱域解决：

${\hat{x}}_{\text{known}}=U_{\text{known}}^{\top }x$

其中 $U_{\text{known}}$ 是对应已知节点的特征向量子矩阵。

---

8. 与深度学习的联系

8.1 ChebNet架构

ChebNet³ 利用 Chebyshev 多项式近似实现高效的谱域卷积：

$g_{\theta }(L)x\approx {\sum }_{k=0}^{K-1}{\theta }_k{T}_k(\tilde{L})x$

其中 $\tilde{L}=2L/{\lambda }_{\max }-I$ 是归一化拉普拉斯。

8.2 GCN的谱域解释

GCN⁴ 的一阶近似可以解释为谱域滤波：

$\tilde{A}=D^{-1/2}A{D}^{-1/2},H^{(l+1)}=\sigma (\tilde{A}{H}^{(l)}{W}^{(l)})$

这对应于谱域的低通滤波器，倾向于保留平滑信号。

8.3 图Transformer的谱域分析

最近的图Transformer架构⁵通过注意力机制学习数据驱动的谱滤波器：

$H^{(l+1)}=\text{Attention}(Q,K,V)=\text{softmax}\left(\frac{Q{K}^{\top }}{\sqrt{d}}\right)V$

---

9. 小结

谱图理论为图神经网络提供了强大的分析工具和理论基础：

概念	作用
拉普拉斯矩阵	图结构的线性表示
特征值/特征向量	定义图的频率基
图傅里叶变换	实现谱域信号处理
多项式滤波器	高效的局部化卷积

理解谱图理论对于设计新的GNN架构、分析现有模型的理论性质、以及解决over-squashing等实际问题都至关重要。

---

参考文献

Footnotes

1. Chung, F. R. K. (1997). Spectral Graph Theory. American Mathematical Society. ↩

2. Di Giovanni, A., et al. (2023). “How does over-squashing affect the power of GNNs?” NeurIPS 2023. ↩

3. Defferrard, M., Bresson, X., & Vandergheynst, P. (2016). “Convolutional Neural Networks on Graphs with Chebyshev Approximation.” NeurIPS 2016. ↩

4. Kipf, T. N., & Welling, M. (2017). “Semi-Supervised Classification with Graph Convolutional Networks.” ICLR 2017. ↩

5. Dwivedi, V. P., et al. (2023). “Graphormer: A Graph Transformer for Molecular Property Prediction.” ICLR 2022. ↩