图信号

图信号的其中一种视觉化方法－－颜色标示

图信号（Graph Signal）的构造方法为在一张图的顶点上赋予值，故在讨论一个图信号时，必须先有一张图。

图信号与离散时间信号相对应，分别是图信号处理和数字信号处理的处理对象。

图信号的指标域为图的顶点集合。与离散时间信号不同，因为图的性质，指标不一定有前后的方向性，故一般而言不能将图信号的指标域比拟作时间。然而，为了与数字信号处理中的概念相呼应，有时还是会将其称作时域。

与离散时间信号的关系

所有有限维的离散时间信号皆可用图信号来表示，例如

• 一维的离散时间信号可看作一个图信号，其中使用的图为一条道路。
• 二维的离散时间信号可看作一个图信号，其中使用的图为一栅格。

更高维离散时间信号亦可用高维栅格来表示。

图信号处理

图信号处理（英语：Graph Signal Process, GSP），是与数字信号处理类似，但处理对象为图信号的一个信号处理的分支。

图信号处理的目的为测量及分析图信号，发展初期，数学家与工程师从图论傅里叶变换开始，仿照数字信号处理中现有的处理工具，试图做出对应的图信号处理版本。然而当时域从普通的整数改变成图，因诸多的不确定性，并无法将所有可使用的工具完整地推广至图信号处理版本（见下例）。

图信号处理的数学理论基础为谱图理论（英语：Spectral graph theory）。

图信号处理的域

图信号处理领域和数字信号处理领域相似，工程师在时域、频域、小波域中研究图信号，但这些域的形象与数字信号处理中使用到的皆有些微差别，例如：

• 时域：图信号的时域为一图的顶点集。在视觉化图信号时，最容易的方法是直接视觉化此图。但在要作图信号处理的数学运算时，会先将图的顶点编号，再依序排列信号值，故运算式中的图信号往往还是以向量的方式出现。
• 频域：图信号的频域与一般数字信号相同的是其指标域皆为频率；不同的是图信号的频域不一定由间隔相同的一连串频率值所构成，故无法直接对应到有限的整数集合。

时域与频域的对应关系由图论傅里叶变换定义，同一张图下，不同的图论傅里叶变换定义出的频域未必相同。

图采样与重建

图采样与重建（Graph Signal Sampling and Reconstruction）旨在从图结构数据中获取有限样本并重构原始图信号。传统的图信号采样（decimation）仅采集部分顶点的信号值，而本文提出的【局部测量】（local measurement）概念则为采样提供了一种广义化方法，允许在一个“无中心局部集”（centerless local set）中，通过线性组合多个顶点的信号来获取测量值，从而提高重构的鲁棒性与精确度。

局部测量

在图信号处理中，一个图信号定义为从顶点集 $V$ 映射到实数集的函数，即 $f:V\to \mathbb {R}$，表示在每个顶点上所观测到或定义的信号值。

设图 $G(V,E)$ 的顶点集 $V$ 被划分为互不重叠的子集 $\{N_{i}\}_{i\in I}$（即无中心局部集），每个局部集 $N_{i}$ 上定义一个局部权重函数 $\phi _{i}:V\to \mathbb {R}$，满足 $\phi _{i}(v)={\begin{cases}\geq 0,&{\text{若 }}v\in N_{i},\\[1mm]0,&{\text{若 }}v\notin N_{i},\end{cases}}\quad {\text{且}}\quad \sum _{v\in N_{i}}\phi _{i}(v)=1.$ 则图信号 $f:V\to \mathbb {R}$ 的局部测量定义为 $f_{\phi _{i}}=\langle f,\phi _{i}\rangle =\sum _{v\in N_{i}}f(v)\phi _{i}(v).$

可见，当仅选取单一顶点（即某顶点 $u$ 的权重取值 1，其余顶点权重均为 0）时，局部测量退化为传统采样；而一般情况下，局部测量则融合了局部集内多个顶点的信息。

迭代局部测量重构（ILMR）

基于上述局部测量，提出了一种迭代型重构算法——迭代局部测量重构（Iterative Local Measurement Reconstruction, ILMR）。令 $PW_{\omega }(G)$ 表示图 $G$ 上带限于频率 $\omega$ 的子空间（即 Paley–Wiener 空间），并设 $P_{\omega }(\cdot )$ 为将信号投影到 $PW_{\omega }(G)$ 的投影算子。定义对于每个局部集 $N_{i}$ 的指示函数 $\delta _{N_{i}}(v)={\begin{cases}1,&v\in N_{i},\\[1mm]0,&v\notin N_{i}.\end{cases}}$ 则 ILMR 的初始化与迭代更新公式分别为 $f^{(0)}=P_{\omega }{\Bigl (}\sum _{i\in I}f_{\phi _{i}}\,\delta _{N_{i}}{\Bigr )},$ $f^{(k+1)}=f^{(k)}+P_{\omega }{\Bigl (}\sum _{i\in I}{\Bigl (}f_{\phi _{i}}-\langle f^{(k)},\phi _{i}\rangle {\Bigr )}\,\delta _{N_{i}}{\Bigr )}.$ 证明表明：若原始图信号 $f$ 属于 $PW_{\omega }(G)$ 且满足某些条件（例如 $\omega <1/C_{\max }^{2}$，其中 $C_{\max }$ 与局部集的结构有关），则 ILMR 能以指数速率收敛并准确重构 $f$；此外，在噪声存在的情况下，对局部权重的优化可使重构误差最小化。

优势与应用

该局部测量采样与重构方案对于具有聚类结构或局部关联性的应用（如感测网络、社交网络等）特别适用，因为在这类场景中，单一顶点的信号可能因噪声而不稳定，而局部测量能通过融合多点信息提高信号的鲁棒性。此外，ILMR 算法可通过局部化实现近似运算，适合分布式处理环境。

图信号滤波

图信号滤波（Graph Signal Filtering）指在图信号的频域上设计与应用滤波器，以调整或强化图信号中的某些频率成分。透过图傅里叶变换，图信号的频谱反映了信号在图结构中不同“频率”成分的能量分布。利用多项式逼近方法（例如切比雪夫多项式逼近），可设计出图滤波器，其通式通常定义为 $h(S)=\sum _{k=0}^{K}h_{k}S^{k},$ 其中 $S$ 为图的移位算子（例如图拉普拉斯矩阵或其正规化形式），而 $h_{k}$ 为滤波器系数。此方法可用于去除噪声、平滑信号或提取重要特征。此外，最新研究亦提出统一的代数滤波器设计框架，可将传统数字滤波技术推广至图结构数据。

相关理论工具

现阶段图信号处理的理论工具皆与数字信号处理有对应关系：

• 图位移（Graph-Shift）（对应一般信号的单位移动）
• 线性非移变系统（Linear-Shift-invariant-system）（对应线性时不变系统）
• 图论Z变换（对应Z变换）
• 图论傅里叶变换（对应离散傅里叶变换）
• 图论小波变换（对应小波变换）
• 流形采样定理（Sampling theorem on manifold）
• 图粗糙化（graph coarsening）

参见

• 图论
• 离散时间信号
• 数字信号处理
• Shuman, D. I.; Narang, S. K.; Frossard, P.; Ortega, A.; Vandergheynst, P. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Processing Magazine. 2013, 30 (3): 83–98 [2025-03-30]. doi:10.1109/MSP.2012.2235192. （原始内容存档于2024-07-10）. 

• Sandryhaila, A.; Moura, J. M. F. Discrete Signal Processing on Graphs. IEEE Transactions on Signal Processing. 2013, 61 (7): 1644–1656. doi:10.1109/TSP.2013.2240057. 

• Ortega, A.; Frossard, P.; Kovačević, J.; Moura, J. M. F.; Vandergheynst, P. Graph Signal Processing: Overview, Challenges, and Applications. Proceedings of the IEEE. 2018, 106 (5): 808–828. doi:10.1109/JPROC.2018.2813598.