图的谱图论与图信号处理

1. 基本概念
   图信号处理将传统信号处理理论推广到图结构上。一个图信号定义为从顶点集到实数的映射，即每个顶点被赋予一个实数值。图结构由邻接矩阵或拉普拉斯矩阵描述，其中拉普拉斯矩阵L = D - A（D为度矩阵，A为邻接矩阵）是核心工具。图的谱即拉普拉斯矩阵的特征值集合，对应图的频率分量。

2. 图傅里叶变换
   通过拉普拉斯矩阵特征分解L = UΛUᵀ，定义图傅里叶变换：信号f的变换为f̂ = Uᵀf。特征向量构成正交基，特征值反映频率高低——小特征值对应低频（平滑信号），大特征值对应高频（剧烈震荡信号）。逆变换通过f = Uf̂实现。

3. 图滤波器设计
   在图频域定义滤波器：对频谱进行缩放f̂_filtered = h(Λ)f̂，其中h(·)为滤波函数。空域实现为矩阵多项式运算。常见滤波器包括：

• 低通滤波器：保留低频成分
• 热核滤波器：h(λ) = e^{-tλ}
• 小波滤波器：多尺度分析

4. 图信号采样与重建
   基于谱聚类的采样策略选择代表性顶点，利用截断傅里叶基实现欠定系统求解。关键定理表明，当采样集满足一定条件时，可通过正则化最小二乘精确重建带限图信号。重建误差与图相干性密切相关。

5. 应用与扩展

• 节点分类：基于标签传播的半监督学习
• 图卷积网络：将滤波器参数化为神经网络
• 时序图信号处理：结合时间维度的动态图分析
• 非欧域处理：将方法推广至流形与异质图

该理论将傅里叶分析、小波变换等经典工具扩展到非规则域，为网络数据分析提供了数学基础。