图信号处理

图信号处理 (Graph Signal Processing)

图信号处理（Graph Signal Processing, GSP）是将经典信号处理理论拓展至非规则定义域——图结构数据——的学科分支。在经典信号处理中，信号定义在规则网格（如时间轴或图像像素阵）上；而图信号处理则将信号视为定义在图节点上的函数，利用图的拓扑结构（邻接关系与边权重）定义频域分析、滤波、采样与重构等操作。该领域于 2000 年代末由 Shuman、Narang、Ortega 和 Vandergheynst 等人系统奠基，此后在社交网络分析、传感器网络、机器学习及计算生物学中快速扩展。

基本定义

设有无向加权图 $G = (V, E, W)$，其中 $V$ 为 $N$ 个节点的集合，$E$ 为边集，$W$ 为权重矩阵，$w_{ij} \ge 0$ 表示节点 $i$ 与 $j$ 之间的连接强度。图信号定义为从节点集到实数的映射 $f: V \to \mathbb{R}$，可排列为向量 $\mathbf{f} \in \mathbb{R}^N$。每条边携带的权重反映了相邻节点信号值的相关性程度——这一关系由图位移算子（Graph Shift Operator）编码。

最常用的图位移算子是图拉普拉斯矩阵（Graph Laplacian）：

其中 $D$ 为对角度的矩阵，$D_{ii} = \sum_j w_{ij}$。归一化形式为 $\mathcal{L} = D^{-1/2} L D^{-1/2}$。拉普拉斯矩阵的二次型：

衡量了信号在边上的"总变差"——值越平滑的信号，该二次型越小。此二次型是图信号处理中"频率"概念的核心。

图傅里叶变换

经典傅里叶变换将时域信号分解为正弦基的线性组合；在图信号中，正弦基由拉普拉斯矩阵的特征向量替代。由于 $L$ 为实对称半正定矩阵，可正交对角化为 $L = U \Lambda U^\top$，其中特征值 $0 = \lambda_1 < \lambda_2 \le \dots \le \lambda_N$ 对应图频率，特征向量对应频率分量。

图信号 $\mathbf{f}$ 的图傅里叶变换（GFT）定义为 $\hat{f}(\lambda_k) = \langle \mathbf{f}, \mathbf{u}_k \rangle = \sum_i f_i \, u_k(i)$，逆变换为 $f_i = \sum_k \hat{f}(\lambda_k) \, u_k(i)$。低特征值对应的特征向量在图上变化缓慢，高特征值对应的变化剧烈——与经典傅里叶分析中低频/高频的对偶完全对应。

图滤波与频域操作

图滤波器是作用于图信号频域系数的算子。给定频率响应函数 $h: \mathbb{R} \to \mathbb{R}$，滤波输出为 $\mathbf{f}_{\mathrm{out}} = U \, h(\Lambda) \, U^\top \mathbf{f}_{\mathrm{in}}$。常用滤波器包括低通滤波器（保留平滑分量抑制噪声）、高通滤波器（提取突变区域）及带通滤波器（选择特定频率范围）。直接特征分解复杂度 $O(N^3)$，实际常用切比雪夫多项式近似降至 $O(|E|K)$。

图信号处理与图神经网络

图信号处理与图神经网络（Graph Neural Networks, GNN）之间存在深刻联系。经典的图卷积网络（GCN）本质上是在图频域中定义卷积运算，再利用切比雪夫多项式的一阶近似实现局部化：

其中 $\tilde{W} = W + I$，$\tilde{D}$ 为加自环后的度数矩阵。这一公式可视为图低通滤波与非线性激活的交替组合——事实上，重复应用图低通滤波是 GNN 实现节点表示平滑的核心机制。GSP 视角也为分析 GNN 中"过平滑"问题（层数过多时节点表示趋同）提供了理论框架：过平滑本质上对应信号被过度低通过滤，丢失了高频信息。

扩展方向

图信号处理已发展出若干重要分支，包括图信号采样与重构、多分辨率图分析、时变图信号处理及图结构学习。在应用层面，已成功用于脑功能连接分析、交通流预测、推荐系统及电网状态监测。随着非欧几里得数据分析需求不断增长，图信号处理正加速与几何深度学习、谱图理论及拓扑数据分析融合。