《The Emerging Field of Signal Processing on Graphs》论文理解

图G={V,E,W}G=\{V,E,W\}G={V,E,W}是由顶点VVV和边EEE组成，WWW表示权值邻接矩阵，(i,j)∈E(i,j) \in E(i,j)∈E表示由iii连接到jjj的边；图分为有向图和无向图，在无向图中，(i,j)=(j,i)(i,j)=(j,i)(i,j)=(j,i)，但是在有向图中并不满足这条性质。这里重点介绍无向图，因为之后介绍的性质之后无向图中才具备。
WijW_{ij}Wij​表示顶点i,ji,ji,j之间的边(i,j)(i,j)(i,j)的权值。如果Wij=0W_{ij}=0Wij​=0表示在顶点i,ji,ji,j之间没有边，即：(i,j)∉E(i,j) \notin E(i,j)∈/​E。WWW中的元素一般为实数，并且由与存在(i,j)=(j,i)(i,j)=(j,i)(i,j)=(j,i)的关系，可以得到：WWW是一个实对称矩阵。定义WWW最常用的方法就是使用阈值高斯核权值函数：
Wij={exp(−[dist(i,j)2]2θ2)dist(i,j)≤k0otherwise(1) W_{ij}=\begin{cases} exp(-\frac{[dist(i,j)^2]}{2\theta^2})&dist(i,j)\leq k \\ 0&otherwise \end{cases}\tag1 Wij​={exp(−2θ2[dist(i,j)2]​)0​dist(i,j)≤kotherwise​(1)

其中dist(i,j)dist(i,j)dist(i,j)可以是顶点i,ji,ji,j之间的物理距离，也可以是它们特征之间的距离。最简单的WWW就是通常介绍的邻接矩阵AAA，AAA矩阵只是WWW矩阵的一种特殊情况。AAA中每一个元素Aij∈{0,1}A_{ij}\in \{0,1\}Aij​∈{0,1}，即：
Amn={0(i,j)∈B1(i.j)∉B(2)A_{mn}= \begin{cases} 0 & (i,j) \in B\\ 1 & (i.j) \notin B \end{cases}\tag{2}Amn​={01​(i,j)∈B(i.j)∈/​B​(2)

无向图中，NiN_iNi​表示节点iii的邻域节点，它有多种定义的方法，一般情况下，某个顶点iii的邻域由路径来定义:
Ni={j∈V,path(i,j)≤k}(3)N_i=\{j\in V,path(i,j)\leq k\}\tag3Ni​={j∈V,path(i,j)≤k}(3)

定义了度矩阵DDD，DDD为对角矩阵并且满足：
Dmm=∑nWmn(4)D_{mm}=\sum_nW_{mn}\tag4Dmm​=n∑​Wmn​(4)

无向图的组合拉普拉斯矩阵定义为
L=D−W(5)L=D-W\tag5L=D−W(5)

归一化拉普拉斯矩阵为：
LN=D1/2(D−W)D1/2(6)L_N=D^{1/2}(D-W)D^{1/2}\tag6LN​=D1/2(D−W)D1/2(6)

用f∈RNf\in R^Nf∈RN表示一个离散信号，那么
(Lf)(i)=∑j∈NiWij[f(i)−f(j)](7)(Lf)(i)=\sum_{j\in N_i}{W_{ij}[f(i)-f(j)]}\tag7(Lf)(i)=j∈Ni​∑​Wij​[f(i)−f(j)](7)

从式（7）可以看出，离散域的拉普拉斯矩阵与连续域拉普拉斯算子相对应，计算了离散域所有自由度上进行微小变化后所获得的增益。

经典的连续域傅里叶变换为：
f^(w)=<f,e2πiwt>=∫Rf(t)e−2πiwtdt(8)\hat{f}(w)==\int_{R}{f(t)e^{-2\pi iwt}dt}\tag8f^​(w)==∫R​f(t)e−2πiwtdt(8)

然而在连续的拉普拉斯算子的特征函数为e2πiwte^{2\pi iwt}e2πiwt,即满足：
−Δ(e2πiwt)=−∂2∂t2e2πiwt=(2πw)2e2πiwt(9)-\Delta(e^{2\pi iwt})=-\frac{\partial^2}{\partial t^2}e^{2\pi iwt}=(2\pi w)^2e^{2\pi iwt}\tag9−Δ(e2πiwt)=−∂t2∂2​e2πiwt=(2πw)2e2πiwt(9)

离散傅里叶变换公式为：
f^(l)=<f,ul>=∑i=0N−1f(i)ul∗(i)=∑i=0N−1f(n)e−jl2πNi(10)\hat{f}(l)==\sum_{i=0}^{N-1}{f(i)u^{\ast}_l(i)}=\sum_{i=0}^{N-1}{f(n)e^{-jl\frac{2\pi}{N}i}} \tag{10}f^​(l)==i=0∑N−1​f(i)ul∗​(i)=i=0∑N−1​f(n)e−jlN2π​i(10)

其中ul∈CN,ul(i)=e−jl2πNi,0≤i≤N−1u_l \in C^N,u_l(i)=e^{-jl\frac{2\pi}{N}i},0\leq i\leq N-1ul​∈CN,ul​(i)=e−jlN2π​i,0≤i≤N−1

拉普拉斯矩阵LLL是实对称矩阵，可知它的特征值{λl}l=0,...,N−1\{\lambda_l\}_{l=0,...,N-1}{λl​}l=0,...,N−1​都为非负实数，对应的特征向量为{ul}l=0,...,N−1\{u_l\}_{l=0,...,N-1}{ul​}l=0,...,N−1​，满足：
Lul=λlul(11)Lu_l=\lambda_lu_l\tag{11}Lul​=λl​ul​(11)

通过离散域和连续域的类比可以得到图上的离散傅里叶变换：
f^(λl)=<f,ul>=∑i=0N−1f(i)ul∗(i)(12)\hat{f}(\lambda_l)==\sum_{i=0}^{N-1}{f(i)u^{\ast}_l(i)}\tag{12}f^​(λl​)==i=0∑N−1​f(i)ul∗​(i)(12)

同时，离散域的逆傅里叶变换为：
f(i)=∑i=0N−1f^(λl)ul(i)(13)f(i)=\sum_{i=0}^{N-1}{\hat{f}(\lambda_l)u_l(i)}\tag{13}f(i)=i=0∑N−1​f^​(λl​)ul​(i)(13)

在信号处理过程中，假设系统的传递函数为h^\hat{h}h^,则冲击响应为hhh。所以有输入信号finf_{in}fin​经过系统后的输出foutf_{out}fout​为：
fout=(fin∗h)(14)f_{out}=(f_{in}*h)\tag{14}fout​=(fin​∗h)(14)

变换到频域得到：
f^out=f^in⨀h^(15)\hat{f}_{out}=\hat{f}_{in}\bigodot\hat{h}\tag{15}f^​out​=f^​in​⨀h^(15)

将式（12）带入式（15）得到：
fout=U(UTh⨀UTfin)=h^(L)fin(16)f_{out}=U(U^{T}h\bigodot U^{T}f_{in})=\hat h(L)f_{in}\tag{16}fout​=U(UTh⨀UTfin​)=h^(L)fin​(16)

其中h^(L)=Uh^(Λ)UT=U[h^(λ0)0⋯00h^(λ1)⋯0⋮⋮⋱⋮00⋯h^(λN−1)]UT\hat h(L)=U\hat{h}(\Lambda)U^T=U \left[ \begin{matrix} \hat{h}(\lambda_{0}) &0 & \cdots & 0\\ 0 & \hat{h}(\lambda_{1}) & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \hat{h}(\lambda_{N-1}) \end{matrix} \right]U^Th^(L)=Uh^(Λ)UT=U⎣⎢⎢⎢⎡​h^(λ0​)0⋮0​0h^(λ1​)⋮0​⋯⋯⋱⋯​00⋮h^(λN−1​)​⎦⎥⎥⎥⎤​UT。
当频域滤波器是一个K(K≤N−1)K(K\leq N-1)K(K≤N−1)阶多项式时，
h^(λl)=∑k=0Kh(k)λlk(17)\hat{h}(\lambda_{l})=\sum_{k=0}^{K}{h(k)\lambda_{l}^k}\tag{17}h^(λl​)=k=0∑K​h(k)λlk​(17)

将式（17）带入式（16），得到：
fout(i)=∑l=0N−1ul(i)h^(λl)f^in(λl)=∑j=1Nfin(j)∑k=0Kh(k)∑l=0N−1λlkul∗(j)ul(i)(18) \begin{aligned} f_{out}(i)&= \sum_{l=0}^{N-1}{u_l(i)\hat{h}(\lambda_l)\hat{f}_{in}(\lambda_l)}\\ &= \sum_{j=1}^{N}{f_{in}(j)}\sum_{k=0}^{K}h(k)\sum_{l=0}^{N-1}{\lambda_l^ku_l^*(j)u_l(i)} \end{aligned}\tag{18} fout​(i)​=l=0∑N−1​ul​(i)h^(λl​)f^​in​(λl​)=j=1∑N​fin​(j)k=0∑K​h(k)l=0∑N−1​λlk​ul∗​(j)ul​(i)​(18)

由于L=λUUTL=\lambda UU^TL=λUUT,得到：
(Lk)ij=∑l=0N−1λlkul∗(j)ul(i)(19)(L^k)_{ij}=\sum_{l=0}^{N-1}{\lambda_l^ku_l^*(j)u_l(i)}\tag{19}(Lk)ij​=l=0∑N−1​λlk​ul∗​(j)ul​(i)(19)

将式（19）带入式（18），得到：
fout(i)=∑j=1Nfin(j)∑k=0Kh(k)(Lk)ij(20)f_{out}(i)=\sum_{j=1}^{N}{f_{in}(j)}\sum_{k=0}^{K}h(k)(L^k)_{ij}\tag{20}fout​(i)=j=1∑N​fin​(j)k=0∑K​h(k)(Lk)ij​(20)

对于整个信号而言：
fout=∑k=0Kh(k)Lkfin(21)f_{out}=\sum_{k=0}^Kh(k)L^kf_{in}\tag{21}fout​=k=0∑K​h(k)Lkfin​(21)

由LLL矩阵的性质可知：
在图中，当顶点i,ji,ji,j之间的最短路径大于kkk时，(Lk)ij=0(L^k)_{ij}=0(Lk)ij​=0,这意味着当滤波器是取kkk阶多项式时，顶点iii处的输出值，只与自身顶点的原来的值以及路径不大于kkk的顶点有关，即：
fout(i)=biifin(i)+∑j∈N(i,K)bijfin(j)(22)f_{out}(i)=b_{ii}f_{in}(i)+\sum_{j\in N(i,K)}{b_{ij}f_{in}(j)}\tag{22}fout​(i)=bii​fin​(i)+j∈N(i,K)∑​bij​fin​(j)(22)

其中bij=∑k=0Kh(k)(Lk)ijb_{ij}=\sum_{k=0}^K{h(k)(L^k)_{ij}}bij​=∑k=0K​h(k)(Lk)ij​。

对比卷积操作，从式（21）中可以看出：∑k=0Kh(k)Lk\sum_{k=0}^Kh(k)L^k∑k=0K​h(k)Lk就是我们所需要的卷积核，训练参数为[h(0),...,h(K)][h(0),...,h(K)][h(0),...,h(K)]。
当输入信号有多个通道的时候，得到卷积公式：
fm+1,j=∑i=1DmFm,i,jfm,i(23)f_{m+1,j}=\sum_{i=1}^{D_m}{F_{m,i,j}f_{m,i}}\tag{23}fm+1,j​=i=1∑Dm​​Fm,i,j​fm,i​(23)

其中，mmm表示第mmm层卷积层，NmN_mNm​表示顶点数目，DmD_mDm​表示特征维数，fm,i∈RNm×Dmf_{m,i}\in R^{N_m×D_m}fm,i​∈RNm​×Dm​表示输入信号fmf_{m}fm​的第iii个特征。Fm,i,j=∑k=0Khm,i,j(k)LkF_{m,i,j}=\sum_{k=0}^Kh_{m,i,j}(k)L^kFm,i,j​=∑k=0K​hm,i,j​(k)Lk表示第jjj个卷积核对第iii特征做卷积的卷积核。
卷积之后需要进行非线性激活和池化操作，得到：
fm+1,j=Pmh(∑i=1DmFm,i,jfm,i)(24)f_{m+1,j}=P_mh(\sum_{i=1}^{D_m}{F_{m,i,j}f_{m,i}})\tag{24}fm+1,j​=Pm​h(i=1∑Dm​​Fm,i,j​fm,i​)(24)

其中h(∗)h(*)h(∗)表示非线性激活函数，PkP_kPk​表示池化操作。式（24）表达了图在顶点域中的卷积过程。
相应顶点域的卷积公式可以由式（16）得到：
fm+1,j=U∑i=1Dm(UTh⨀UTfm,i)=U∑i=1Dmh^(Λ)UTfm,i=∑i=1Dmh^(L)fm,i(25)\begin{aligned} f_{m+1,j}&=U\sum_{i=1}^{D_m}(U^{T}h\bigodot U^{T}f_{m,i})\\ &=U\sum_{i=1}^{D_m}\hat h(\Lambda)U^Tf_{m,i}\\ &=\sum_{i=1}^{D_m}\hat h(L)f_{m,i} \end{aligned}\tag{25}fm+1,j​​=Ui=1∑Dm​​(UTh⨀UTfm,i​)=Ui=1∑Dm​​h^(Λ)UTfm,i​=i=1∑Dm​​h^(L)fm,i​​(25)
其中h^(Λ)\hat h(\Lambda)h^(Λ)是对角矩阵，同时是我们需要训练的卷积核，训练参数为[h^(λ0),...,h^(λN−1)][\hat{h}(\lambda_{0}),...,\hat{h}(\lambda_{N-1})][h^(λ0​),...,h^(λN−1​)]。

signal processing ON