圖訊號

圖訊號的其中一種視覺化方法－－顏色標示

圖訊號（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.