IEEE Signal Processing Magazine 2013, 原文链接：The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
Abstract 社交、能源、运输、传感器、神经网络、高维数据很多都很自然地依赖于带权图的顶点。新兴的图信号处理领域融合了代数、谱图理论与计算谐波分析来处理图上的信号。在这篇教程中，我们列出了这个领域的主要挑战，讨论了定义图谱域的不同方法，点明了融合图数据域中不规则的结构在处理图信号时的重要性。然后回顾了将基础的操作，如filtering, translation, modulation, dilation, downsampling等技术泛化到图上的方法，对已经提出的高效地从图中的高维数据提取信息的localized, multisacle transforms进行了总结。最后对一些问题以及未来的扩展做了一些讨论。
1. Introduction 图是很多数据的表示形式，在描述很多应用的几何结构时很有用，如社交、能源、运输、传感器、神经网络等。图中每条边的权重，经常表示为两个顶点之间的相似度。连接性和边权重要么由问题的物理性质指明，要么从数据中推断出来。举个例子，边权重可能与网络中两个顶点之间的距离成反比。这些图的数据可以看作是一个样本的有限集合，每个顶点一个样本。我们称这些样本为一个图信号。一个图信号的例子如图1所示。
在运输网络中，我们关心分析描述疾病传播的传染病数据，描述用户迁移的人口数据，或是描述货物仓库的后勤数据。现在，在大脑图像中，推断大脑皮层上独特的功能区结构上的连接性变为可能，这种连接可以表示为一个带权图，顶点代表了功能区。因此，noisy fMRI图像可以看作是带权图上的信号。带权图一般用来表示统计学习问题中数据点之间的相似性，如计算机视觉和文本分类问题。事实上，很多研究图数据分析的论文是从统计学习社区中发表出来的，因为基于图的方法在半监督学习问题中变得非常流行，这些问题的目标是用一些标记样本对未知的样本进行分类。在图像处理，对图像的像素构造非局部和半局部连接的图的这种，基于图的filtering methods突然流行了起来，这些方法不仅基于像素间的物理相似性，还有要处理的图像的nosiy versions。这些方法经常能更好地识别并考虑图像的边和材质。
这些应用中常见的数据处理任务有filtering, denoising, inpainting, compressing graph signals。如何在不规则的域中处理他们，比如在任意结构的图上面？对数据的存储，通信，分析最有效的从高维数据中提取信息的方法是什么，统计与可视化？传统的信号处理的操作或算法可以使用吗？在图上的信号处理领域还有一些这样的问题。
A. The Main Challenges of Signal Processing on Graphs
N N N N N N R N \mathbb{R}^N R N f ( t ) f(t) f ( t ) f ( t − 3 ) f(t-3) f ( t − 3 ) f ( ∘ − 3 ) f(\circ - 3) f ( ∘ − 3 ) 1 1 1 N N N f ( ∘ − 3 ) : = f ( m o d ( ∘ − 3 , N ) ) f(\circ - 3) := f(\mathrm{mod}(\circ - 3, N)) f ( ∘ − 3 ) := f ( mod ( ∘ − 3 , N ))
此外，处理数据域的不规则性，图结构在之前提到的应用中，可以表示很多顶点的特征。为了能很好地对数据的尺度进行缩放，对于图信号的处理技术应该使用局部操作，通过对每个顶点，计算顶点的邻居，或是和它很近的顶点的信息得到。
因此，图信号处理的主要挑战是：1. 有些任务中图没有直接给出，需要决定如何构建可以捕获数据几何结构的带权图；2. 将图结构整合到局部变换操作中；3. 同时利用这些年来信号处理在欧氏空间发展出的理论成果；4. 研究局部变换的高效实现，从高维的图结构数据或其他不规则数据域中提取信息。
为了解决这些问题，新兴的图信号处理领域将代数和谱图理论的概念与计算谐波分析融合了起来。这是在代数图理论和谱图理论中的扩展；但是，早于十年前的研究主要是聚焦于分析图，而不是分析图的信号。
2. The Graph Spectral Domains 谱图理论是聚焦于构建、分析、操作图的，不是图上的信号。在构建扩展图、图的可视化、谱聚类、着色问题、还有许多如化学、物理、计算科学领域的问题上都很有效。
图信号处理领域，谱图理论被用作一个定义频谱和图傅里叶变换的基的扩展的工具。这部分我们会回顾一些谱图理论基本的定义与符号，研究它如何使得从传统的傅里叶分析扩展出很多重要的数学理论到图论上。
A. Weighted Graphs and Graph Signals G = { V , E , W } \mathcal{G} = \lbrace \mathcal{V}, \mathcal{E}, \mathbf{W} \rbrace G = { V , E , W } e = ( i , j ) e = (i, j) e = ( i , j ) i i i j j j W i , j W_{i,j} W i , j w i , j = 0 w_{i,j} = 0 w i , j = 0 G \mathcal{G} G M M M M M M
当边的权重没有给出的时候，一种常用的方法是使用一个带阈值的高斯核权重函数：
W _ i , j = { exp ( − [ d i s t ( i , j ) ] 2 2 θ 2 ) if d i s t ( i , j ) ≤ κ 0 otherwise , (1) \tag{1}
W\_{i,j} = \begin{cases}
\exp{(-\frac{[dist(i,j)]^2}{2\theta^2})} \quad &\text{if } dist(i, j) \leq \kappa \\
0 \quad &\text{otherwise}
\end{cases},
W _ i , j = { exp ( − 2 θ 2 [ d i s t ( i , j ) ] 2 ) 0 if d i s t ( i , j ) ≤ κ otherwise , ( 1 ) 参数是θ \theta θ κ \kappa κ d i s t ( i , j ) dist(i, j) d i s t ( i , j ) i i i j j j k k k
一个定义在图的顶点上的信号或函数f : V → R f: \mathcal{V} \rightarrow \mathbb{R} f : V → R f ∈ R N \mathbf{f} \in \mathbb{R}^N f ∈ R N i i i V \mathcal{V} V i i i
B. The Non-Normalized Graph Laplacian
非归一化的拉普拉斯矩阵，也称为组合拉普拉斯矩阵(combinatorial graph Laplacian)，定义为L : = D − W \bf L := D - W L := D − W D \bf{D} D i i i i i i f ∈ R N \mathbf{f} \in \mathbb{R}^N f ∈ R N
( L f ) ( i ) = ∑ _ j ∈ N _ i W _ i , j [ f ( i ) − f ( j ) ] ,
(\mathbf{L}f)(i) = \sum\_{j \in \mathcal{N}\_i} W\_{i,j}[f(i) - f(j)],
( L f ) ( i ) = ∑ _ j ∈ N _ i W _ i , j [ f ( i ) − f ( j )] , 邻居N i \mathcal{N}_i N i i i i N ( i , k ) \mathcal{N}(i, k) N ( i , k ) k k k k k k i i i L L L { u l } l = 0 , 1 , … , N − 1 \lbrace \mathbf{u}_l \rbrace_{l=0,1,…,N-1} { u l } l = 0 , 1 , … , N − 1 { λ l } l = 0 , 1 , … , N − 1 \lbrace \lambda_l\rbrace_{l=0,1,…,N-1} { λ l } l = 0 , 1 , … , N − 1 L u l = λ l u l L \mathbf{u}_l = \lambda_l \mathbf{u}_l L u l = λ l u l l = 0 , 1 , … , N − 1 l = 0,1,…,N-1 l = 0 , 1 , … , N − 1 0 = λ 0 < λ 1 ≤ λ 2 … ≤ λ N − 1 : = λ max 0 = \lambda_0 < \lambda_1 \leq \lambda_2 … \leq \lambda_{N-1} := \lambda_{\text{max}} 0 = λ 0 < λ 1 ≤ λ 2 … ≤ λ N − 1 := λ max σ ( L ) = { λ 0 , λ 1 , … , λ N − 1 } \sigma(L) = \lbrace \lambda_0, \lambda_1, …, \lambda_{N-1}\rbrace σ ( L ) = { λ 0 , λ 1 , … , λ N − 1 }
C. A Graph Fourier Transform and Notion of Frequency
传统的傅里叶变换
f ^ ( ξ ) : = ⟨ f , e 2 π i ξ t ⟩ = ∫ _ R f ( t ) e − 2 π i ξ t d t
\hat{f}(\xi) := \langle f, e^{2\pi i \xi t} \rangle = \int\_\mathbb{R} f(t) e^{-2\pi i \xi t}dt
f ^ ( ξ ) := ⟨ f , e 2 πi ξ t ⟩ = ∫ _ R f ( t ) e − 2 πi ξ t d t 是函数f f f
− Δ ( e 2 π i ξ t ) = − ∂ 2 ∂ t 2 e 2 π i ξ t = ( 2 π ξ ) 2 e 2 π i ξ t . (2) \tag{2}
-\Delta(e^{2\pi i \xi t}) = -\frac{\partial^2}{\partial t^2} e^{2\pi i \xi t} = (2 \pi \xi)^2 e^{2\pi i \xi t}.
− Δ ( e 2 πi ξ t ) = − ∂ t 2 ∂ 2 e 2 πi ξ t = ( 2 π ξ ) 2 e 2 πi ξ t . ( 2 ) 类比这个，我们可以定义任何一个在图G \mathcal{G} G f ∈ R N \mathbf{f} \in \mathbb{R}^N f ∈ R N f ^ \hat{\mathbf{f}} f ^ f \mathbf{f} f
f ^ ( λ _ l ) : = ⟨ f , u _ l ⟩ = ∑ N _ i = 1 f ( i ) u ∗ _ l ( i ) . (3) \tag{3}
\hat{f}(\lambda\_l) := \langle \mathbf{f}, \mathbf{u}\_l \rangle = \sum^N\_{i = 1} f(i) u^*\_l (i).
f ^ ( λ _ l ) := ⟨ f , u _ l ⟩ = ∑ N _ i = 1 f ( i ) u ∗ _ l ( i ) . ( 3 ) 逆图傅里叶变换为：
f ( i ) = ∑ N − 1 _ l = 0 f ^ ( λ _ l ) u _ l ( i ) . (4) \tag{4}
f(i) = \sum^{N - 1}\_{l = 0} \hat{f}(\lambda\_l) u\_l(i).
f ( i ) = ∑ N − 1 _ l = 0 f ^ ( λ _ l ) u _ l ( i ) . ( 4 ) 传统的傅里叶分析中，式2中的特征值{ ( 2 π ξ ) 2 } ξ ∈ R \lbrace (2 \pi \xi )^2 \rbrace_{\xi \in \mathbb{R}} {( 2 π ξ ) 2 } ξ ∈ R ξ \xi ξ ξ \xi ξ u 0 \mathbf{u}_0 u 0 1 N \frac{1}{\sqrt{N}} N 1 λ l \lambda_l λ l ∣ Z G ( ⋅ ) ∣ \vert Z_\mathcal{G}(\cdot) \vert ∣ Z G ( ⋅ ) ∣ f \bf{f} f G \mathcal{G} G
Z _ G ( f ) : = { e = ( i , j ) ∈ ε : f ( i ) f ( j ) < 0 } ;
Z\_\mathcal{G}(\mathbf{f}) := \lbrace e = (i, j) \in \Large\varepsilon \normalsize : f(i)f(j) < 0 \rbrace;
Z _ G ( f ) := { e = ( i , j ) ∈ ε : f ( i ) f ( j ) < 0 } ; 也就是，连接一个正信号和一个负信号的边的集合。
D. Graph Signal Representations in Two Domains g \bf{g} g g ^ \hat{\bf{g}} g ^ 核(kernels) 。图4a和图4b中，一个这样的核，一个heat kernel，分别展示了在两个域中的效果。类比传统的模拟情况，图4中展示的一个平缓的信号图傅里叶系数衰减的很快。这样的信号是可压缩的(compressible) ，因为可以通过调整一些图傅里叶系数来趋近他们。
E. Discrete Calculus and Signal Smoothness with Respect to the Intrinsic Structure of the Graph
为了增加smoothness对应图的内在结构的问题，我们简单的提一些离散可微分操作。一个信号f \bf{f} f i i i e = ( i , j ) e = (i, j) e = ( i , j ) 边导数 (edge derivative)定义为：
∂ f ∂ e ∣ _ i : = W _ i , j [ f ( j ) − f ( i ) ] ,
\left. \frac{\partial \mathbf{f}}{\partial e} \right|\_i := \sqrt{W\_{i,j}}[f(j) - f(i)],
∂ e ∂ f _ i := W _ i , j [ f ( j ) − f ( i )] , 顶点i i i f \bf{f} f
∇ _ i f : = [ { ∂ f ∂ b ∣ _ i } _ e ∈ ε s.t. e = ( i , j ) for some j ∈ V ] .
\nabla\_i \mathbf{f} := [\lbrace \left. \frac{\partial f}{\partial b} \right|\_i \rbrace\_{e \in \varepsilon \ \text{s.t.} \ e=(i,j) \ \text{for some} \ j \in \mathcal{V}}].
∇_ i f := [{ ∂ b ∂ f _ i } _ e ∈ ε s.t. e = ( i , j ) for some j ∈ V ] . 顶点i i i local variation
∥ ∇ _ i f ∥ _ 2 : = [ ∑ _ e ∈ ε s.t. e = ( i , j ) for some j ∈ V ( ∂ f ∂ e ∣ _ i ) 2 ] 1 2 = [ ∑ _ j ∈ N _ i W _ i , j [ f ( j ) − f ( i ) ] 2 ] 1 2
\begin{aligned}
\Vert \nabla\_i \mathbf{f} \Vert\_2 : & = [\sum\_{e \in \varepsilon \ \text{s.t.} \ e =(i, j) \ \text{for some} \ j \in \mathcal{V}} (\left. \frac{\partial \mathbf{f}}{\partial e} \right|\_i)^2]^{\frac{1}{2}} \\
& = [\sum\_{j \in \mathcal{N}\_i} W\_{i, j} [f(j) - f(i)]^2]^{\frac{1}{2}}
\end{aligned}
∥∇_ i f ∥_2 : = [ ∑ _ e ∈ ε s.t. e = ( i , j ) for some j ∈ V ( ∂ e ∂ f _ i ) 2 ] 2 1 = [ ∑ _ j ∈ N _ i W _ i , j [ f ( j ) − f ( i ) ] 2 ] 2 1 可以度量顶点i i i f \bf{f} f i i i j j j f \bf{f} f
对于global smoothness，f \bf{f} f discrete p-Dirichlet form 定义为：
S _ p ( f ) : = 1 p ∑ _ i ∈ V ∥ ∇ _ i f ∥ p _ 2 = 1 p ∑ _ i ∈ V [ ∑ _ j ∈ N _ i W _ i , j [ f ( j ) − f ( i ) ] 2 ] p 2 . (5) \tag{5}
S\_p(\mathbf{f}) := \frac{1}{p} \sum\_{i \in V} \Vert \nabla\_i \mathbf{f} \Vert^p\_2 = \frac{1}{p} \sum\_{i \in V}\LARGE[ \normalsize \sum\_{j \in \mathcal{N}\_i} W\_{i,j} [f(j) - f(i)]^2 \LARGE]^{\normalsize \frac{p}{2}}.
S _ p ( f ) := p 1 ∑ _ i ∈ V ∥∇_ i f ∥ p _2 = p 1 ∑ _ i ∈ V [ ∑ _ j ∈ N _ i W _ i , j [ f ( j ) − f ( i ) ] 2 ] 2 p . ( 5 ) 当p = 1 p=1 p = 1 S 1 ( f ) S_1(\mathbf{f}) S 1 ( f ) total variation 。当p = 2 p = 2 p = 2
S _ 2 ( f ) = 1 2 ∑ _ i ∈ V ∑ _ j ∈ N _ i W _ i , j [ f ( j ) − f ( i ) ] 2 = ∑ _ ( i , j ) ∈ ε W _ i , j [ f ( j ) − f ( i ) ] 2 = f T L f . (6) \tag{6}
\begin{aligned}
S\_2(\mathbf{f}) &= \frac{1}{2}\sum\_{i \in V} \sum\_{j \in \mathcal{N}\_i} W\_{i,j} [f(j) - f(i)]^2 \\
&= \sum\_{(i,j) \in \varepsilon} W\_{i,j} [f(j) - f(i)]^2 = \mathbf{f^TLf}.
\end{aligned}
S _2 ( f ) = 2 1 ∑ _ i ∈ V ∑ _ j ∈ N _ i W _ i , j [ f ( j ) − f ( i ) ] 2 = ∑ _ ( i , j ) ∈ ε W _ i , j [ f ( j ) − f ( i ) ] 2 = f T Lf . ( 6 ) S 2 ( f ) S_2(\mathbf{f}) S 2 ( f ) ∥ f ∥ L \bf \Vert f \Vert_L ∥f ∥ L
∥ f ∥ _ L : = ∥ L 1 2 f ∥ _ 2 = f T L f = S _ 2 ( f ) .
\Vert \mathbf{f} \Vert\_\mathbf{L} := \Vert \mathbf{L}^{\frac{1}{2}} \mathbf{f} \Vert\_2 = \sqrt{\mathbf{f^TLf}} = \sqrt{S\_2(\mathbf{f})}.
∥ f ∥_ L := ∥ L 2 1 f ∥_2 = f T Lf = S _2 ( f ) . 注意式6，二次型S 2 ( f ) S_2(\mathbf{f}) S 2 ( f ) f \bf{f} f ∥ f ∥ L \Vert \mathbf{f} \Vert_L ∥ f ∥ L f \bf{f} f S 2 ( f ) S_2(\mathbf{f}) S 2 ( f )
回到拉普拉斯矩阵的特征值和特征向量上，Courant-Fischer Theorem指出，他们也可以通过Rayleigh quotient定义为：
λ _ 0 = min _ f ∈ R N , ∥ f ∥ _ 2 = 1 { f T L f } , (7) \tag{7}
\lambda\_0 = \min\_{ \mathbf{f} \in \mathbb{R}^N, \Vert \mathbf{f} \Vert\_2 = 1} \lbrace \mathbf{f^TLf} \rbrace,
λ _0 = min _ f ∈ R N , ∥ f ∥_2 = 1 { f T Lf } , ( 7 )
and λ _ l = min _ f ∈ R N , ∥ f ∥ _ 2 = 1 , f ⊥ s p a n { u _ 0 , . . . , u _ l − 1 } { f T L f } , l = 1 , 2 , . . . , N − 1. (8) \tag{8}
\text{and} \ \lambda\_l = \min\_{ \mathbf{f} \in \mathbb{R}^N, \Vert \mathbf{f} \Vert\_2 = 1, \mathbf{f} \perp span\lbrace \mathbf{u}\_0, ..., \mathbf{u}\_{l-1} \rbrace} \lbrace \mathbf{f^TLf} \rbrace, \ l = 1, 2, ..., N-1.
and λ _ l = min _ f ∈ R N , ∥ f ∥_2 = 1 , f ⊥ s p an { u _0 , ... , u _ l − 1 } { f T Lf } , l = 1 , 2 , ... , N − 1. ( 8 ) 其中，特征向量u l \mathbf{u}_l u l l l l u 0 \mathbf{u}_0 u 0
总结一下，图的连通性编码进了拉普拉斯矩阵，拉普拉斯矩阵通常用于定义图傅里叶变换（通过特征向量），平滑性的不同表示。Example 1展示了smoothness和一个图信号的谱内容是如何依赖于图的。
F. Other Graph Matrices
图拉普拉斯矩阵的基{ u l } l = 0 , 1 , … , N − 1 \lbrace \mathbf{u}_l \rbrace_{l = 0, 1, …, N - 1} { u l } l = 0 , 1 , … , N − 1 W i , j W_{i,j} W i , j 1 d i d j \frac{1}{\sqrt{d_i d_j}} d i d j 1 L ~ : = D − 1 2 L D − 1 2 \bf\tilde{L} := D^{-\frac{1}{2}} L D^{-\frac{1}{2}} L ~ := D − 2 1 L D − 2 1
( L ~ f ) ( i ) = 1 d _ i ∑ _ j ∈ N _ i W _ i , j [ f ( i ) d _ i − f ( j ) d _ j ] .
(\tilde{L}f)(i) = \frac{1}{\sqrt{d\_i}} \sum\_{j \in \mathcal{N}\_i} W\_{i,j} \LARGE[\normalsize \frac{f(i)}{\sqrt{d\_i}} - \frac{f(j)}{\sqrt{d\_j}} \LARGE].
( L ~ f ) ( i ) = d _ i 1 ∑ _ j ∈ N _ i W _ i , j [ d _ i f ( i ) − d _ j f ( j ) ] . 连通图G \mathcal{G} G { λ ~ l } l = 0 , 1 , … , N − 1 \lbrace \tilde{\lambda}_l \rbrace_{l=0,1,…,N-1} { λ ~ l } l = 0 , 1 , … , N − 1
0 = λ ~ _ 0 < λ ~ _ 1 ≤ . . . ≤ λ ~ _ max ≤ 2 ,
0 = \tilde{\lambda}\_0 < \tilde{\lambda}\_1 \leq ... \leq \tilde{\lambda}\_{\text{max}} \leq 2,
0 = λ ~ _0 < λ ~ _1 ≤ ... ≤ λ ~ _ max ≤ 2 , 当且仅当G \mathcal{G} G λ ~ max = 2 \tilde{\lambda}_{\text{max}} = 2 λ ~ max = 2 { u ~ l } l = 0 , 1 , … N − 1 \lbrace \mathbf{\tilde{u}}_l \rbrace_{l = 0,1,…N-1} { u ~ l } l = 0 , 1 , … N − 1 L ~ \tilde{L} L ~ u 0 \mathbf{u}_0 u 0 u ~ 0 \tilde{\mathbf{u}}_0 u ~ 0
归一化和非归一化的拉普拉斯矩阵都是generalized graph Laplacians 的例子，也称为discrete Schrödinger operators 。一个图G \mathcal{G} G i i i j j j ( i , j ) (i, j) ( i , j ) i ≠ j i \not = j i = j i i i j j j 0 0 0 i = j i = j i = j
第三个常用的矩阵，经常在图信号的降维技术中使用，是random walk matrix ，P : = D − 1 W \bf{P := D^{-1}W} P := D − 1 W P i , j P_{i,j} P i , j G \mathcal{G} G i i i j j j P t \mathbf{P}^t P t t t t L a : = I N − P \mathbf{L}_a := \mathbf{I}_N - \mathbf{P} L a := I N − P I N \mathbf{I}_N I N N × N N \times N N × N L a \mathbf{L}_a L a L ~ \tilde{\mathbf{L}} L ~ u ~ l \tilde{\mathbf{u}}_l u ~ l L ~ \tilde{L} L ~ λ ~ l \tilde{\lambda}_l λ ~ l D − 1 2 u ~ l \bf{D}^{-\frac{1}{2}} \tilde{\mathbf{u}}_l D − 2 1 u ~ l L a \mathbf{L}_a L a λ ~ l \tilde{\lambda}_l λ ~ l
正如下一节要讨论的，归一化和非归一化的拉普拉斯矩阵都能用于filtering。没有明确的规定要求什么时候必须使用归一化的，什么时候使用非归一化的拉普拉斯矩阵的特征向量，什么时候使用其他的基。归一化的拉普拉斯矩阵有很好的性质，它的谱总时在[ 0 , 2 ] [0, 2] [ 0 , 2 ]
3. Generalized Operators For Signals on Graphs 在这部分，我们会回顾不同的方式来泛化基本操作到图上，如filtering, translation, modulation, dilation, downsampling。这些泛化的操作是第四部分要讨论的localized, multiscale transforms的基础。
A. Filtering
第一个泛化的操作是filtering。我们从扩展频率滤波的概念到图上开始，然后讨论顶点域上的局部滤波。
1. Frequency Filtering: 在传统的信号处理中，频率滤波是将输入信号表示成一个复指数的线性组合，扩大或缩小一些复指数贡献的过程
f ^ _ o u t ( ξ ) = f ^ _ i n ( ξ ) h ^ ( ξ ) , (9) \tag{9}
\hat{f}\_{out}(\xi) = \hat{f}\_{in}(\xi) \hat{h}(\xi),
f ^ _ o u t ( ξ ) = f ^ _ in ( ξ ) h ^ ( ξ ) , ( 9 ) 其中，h ^ ( ⋅ ) \hat{h}(\cdot) h ^ ( ⋅ )
f _ o u t ( t ) = ∫ _ R f ^ _ i n ( ξ ) h ^ ( ξ ) e 2 π i ξ t d ξ (10) \tag{10}
f\_{out}(t) = \int\_\mathbb{R} \hat{f}\_{in}(\xi) \hat{h}(\xi)e^{2 \pi i \xi t} d\xi
f _ o u t ( t ) = ∫ _ R f ^ _ in ( ξ ) h ^ ( ξ ) e 2 πi ξ t d ξ ( 10 )
= ∫ _ R f _ i n ( τ ) h ( t − τ ) d τ = : ( f _ i n ∗ h ) ( t ) . (11) \tag{11}
=\intop\_\mathbb{R} f\_{in}(\tau) h(t-\tau)d\tau =: (f\_in * h)(t).
= ∫ _ R f _ in ( τ ) h ( t − τ ) d τ =: ( f _ in ∗ h ) ( t ) . ( 11 ) 一旦我们fix一个图谱表示，我们的图傅里叶变换的概念，我们可以直接将式9泛化到定义频率滤波上，或图谱滤波 (graph spectral filtering)上：
f ^ _ o u t ( λ _ l ) = f ^ _ i n ( λ _ l ) h ^ ( λ _ l ) , (12) \tag{12}
\hat{f}\_{out}(\lambda\_l) = \hat{f}\_{in}(\lambda\_l) \hat{h}(\lambda\_l),
f ^ _ o u t ( λ _ l ) = f ^ _ in ( λ _ l ) h ^ ( λ _ l ) , ( 12 ) 或者，等价的，取逆图傅里叶变换，
f _ o u t ( i ) = ∑ N − 1 _ l = 0 f ^ _ i n ( λ _ l ) h ^ ( λ _ l ) u _ l ( i ) . (13) \tag{13}
f\_{out}(i) = \sum^{N-1}\_{l=0} \hat{f}\_{in}(\lambda\_l) \hat{h}(\lambda\_l) u\_l(i).
f _ o u t ( i ) = ∑ N − 1 _ l = 0 f ^ _ in ( λ _ l ) h ^ ( λ _ l ) u _ l ( i ) . ( 13 ) 接用matrix functions[38]理论中的符号，我们可以将式12和式13写成f o u t = h ^ ( L ) f i n \mathbf{f}_{out} = \hat{h}(\mathbf{L})\mathbf{f}_{in} f o u t = h ^ ( L ) f in
h ^ ( L ) : = U [ h ^ ( λ _ 0 ) 0 ⋱ 0 h ^ ( λ _ N − 1 ) ] U T (14) \tag{14}
\hat{h}(\mathbf{L}) := \mathbf{U} \begin{bmatrix}
\hat{h}(\lambda\_0) & & 0 \\
& \ddots & \\
0 & &\hat{h}(\lambda\_{N-1})
\end{bmatrix}\mathbf{U^T}
h ^ ( L ) := U h ^ ( λ _0 ) 0 ⋱ 0 h ^ ( λ _ N − 1 ) U T ( 14 ) 基础的图谱滤波可以用来实现连续滤波技术的离散版，如高斯平滑，双边滤波，total variation filtering，anisotropic diffusion，non-local means filtering。特别地，这些滤波器中的很多成为了解决variational problems的方法，对ill-posed inverse problems进行正则化，这些问题如denoising，inpainting，super-resolution。举个例子，离散正则框架：
min _ f { ∥ f − y ∥ 2 _ 2 + γ S _ p ( f ) } , (15) \tag{15}
\min\_\mathbf{f}\lbrace \Vert \mathbf{f} - \mathbf{y} \Vert^2\_2 + \gamma S\_p(\mathbf{f}) \rbrace,
min _ f { ∥ f − y ∥ 2 _2 + γ S _ p ( f )} , ( 15 ) 其中，S p ( f ) S_p(\mathbf{f}) S p ( f ) p = 2 p = 2 p = 2
2. Filtering in the Vertex Domain: 在顶点域中filter一个信号，只要简单的将顶点i i i f o u t ( i ) f_{out}(i) f o u t ( i ) i i i K − h o p K-hop K − h o p
f _ o u t ( i ) = b _ i , i f _ i n ( i ) + ∑ _ j ∈ N ( i , K ) b _ i , j f _ i n ( j ) , (18) \tag{18}
f\_{out}(i) = b\_{i, i} f\_{in}(i) + \sum\_{j \in \mathcal{N}(i, K)} b\_{i,j} f\_{in}(j),
f _ o u t ( i ) = b _ i , i f _ in ( i ) + ∑ _ j ∈ N ( i , K ) b _ i , j f _ in ( j ) , ( 18 ) { b i , j } i , j ∈ V \lbrace b_{i,j} \rbrace_{i,j \in \mathcal{V}} { b i , j } i , j ∈ V
我们现在简单地将图谱域上的滤波关联到了顶点域的滤波上。当式12中的频率滤波是K K K h ^ ( λ l ) = ∑ k = 0 K a k λ l k \hat{h}(\lambda_l) = \sum^K_{k=0} a_k \lambda^k_l h ^ ( λ l ) = ∑ k = 0 K a k λ l k { a k } k = 0 , 1 , … K \lbrace a_k\rbrace_{k=0,1,…K} { a k } k = 0 , 1 , … K
f _ o u t ( i ) = ∑ N − 1 _ l = 0 f ^ _ i n ( λ _ l ) h ^ ( λ _ l ) u _ l ( i ) = ∑ N _ j = 1 f _ i n ( j ) ∑ K _ k = 0 a _ k ∑ N − 1 _ l = 0 λ k _ l u ∗ _ l ( j ) u _ l ( i ) = ∑ N _ j = 1 f _ i n ( j ) ∑ K _ k = 0 a _ k ( L k ) _ i , j . (19) \tag{19}
\begin{aligned}
f\_{out}(i) & = \sum^{N-1}\_{l=0} \hat{f}\_{in}(\lambda\_l) \hat{h}(\lambda\_l) u\_l(i) \\
& = \sum^N\_{j=1} f\_{in}(j) \sum^K\_{k=0} a\_k \sum^{N-1}\_{l=0} \lambda^k\_l u^*\_l(j) u\_l(i) \\
& = \sum^N\_{j=1} f\_{in}(j) \sum^K\_{k=0} a\_k(\mathbf{L}^k)\_{i,j}.
\end{aligned}
f _ o u t ( i ) = ∑ N − 1 _ l = 0 f ^ _ in ( λ _ l ) h ^ ( λ _ l ) u _ l ( i ) = ∑ N _ j = 1 f _ in ( j ) ∑ K _ k = 0 a _ k ∑ N − 1 _ l = 0 λ k _ l u ∗ _ l ( j ) u _ l ( i ) = ∑ N _ j = 1 f _ in ( j ) ∑ K _ k = 0 a _ k ( L k ) _ i , j . ( 19 ) 然而，在顶点i i i j j j d G ( i , j ) d_\mathcal{G}(i,j) d G ( i , j ) k k k ( L k ) i , j = 0 (\mathbf{L}^k)_{i,j} = 0 ( L k ) i , j = 0
b _ i , j : = ∑ K _ k = d _ G ( i , j ) a _ k ( L k ) _ i , j .
b\_{i,j} := \sum^K\_{k=d\_\mathcal{G}(i,j)} a\_k (\mathbf{L}^k)\_{i,j}.
b _ i , j := ∑ K _ k = d _ G ( i , j ) a _ k ( L k ) _ i , j . 所以当频率滤波是一个K K K i i i f o u t ( i ) f_{out}(i) f o u t ( i ) i i i K − h o p K-hop K − h o p
B. Convolution
我们不能直接将卷积的定义（11）泛化到图上，因为h ( t − τ ) h(t - \tau) h ( t − τ )
( f ∗ h ) ( i ) : = ∑ N − 1 _ l = 0 f ^ ( λ _ l ) h ^ ( λ _ l ) u _ l ( i ) , (20) \tag{20}
(f * h)(i) := \sum^{N-1}\_{l=0} \hat{f}(\lambda\_l) \hat{h}(\lambda\_l) u\_l(i),
( f ∗ h ) ( i ) := ∑ N − 1 _ l = 0 f ^ ( λ _ l ) h ^ ( λ _ l ) u _ l ( i ) , ( 20 ) 这个使得在顶点域上的卷积等价于在图谱域的乘法。
C. Translation
