图信号处理与图卷积神经网络

图信号与图拉普拉斯矩阵

【图的拉普拉斯矩阵】 \(L=D-A\)，其中\(L_{ij}=\begin{cases}d(v_i) & i=j \\ -1 & e_{ij}\in E\\ 0 & otherwise\end{cases}\)

正则化表示：\(L'=D^{-\frac{1}{2}}(D-A)D^{-\frac{1}{2}}=I-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}\)，其中\(L'_{ij}=\begin{cases}1 & i=j \\ -\frac{1}{\sqrt{d(v_i)d(v_j)}} & e_{ij}\in E\\ 0 & otherwise\end{cases}\)
对角化表示（L是实对称矩阵）：\(L=V\Lambda V^T=\begin{bmatrix}v_1&\cdots &v_N\end{bmatrix}\begin{bmatrix}\lambda_1 && \\ & \ddots&\\ &&\lambda_N\end{bmatrix}\begin{bmatrix}v_1^T \\ \vdots \\ v_N^T\end{bmatrix}\)
\(V\in R^{N\times N}\)为正交矩阵（\(VV^T=E\)）
\(V=\begin{bmatrix}v_1&\cdots&v_N\end{bmatrix}\)为\(L\)的N个特征向量
对特征值进行排序得到\(\lambda_1\leq \cdots \leq \lambda_N\)，对应的特征向量为\(v_1,\cdots,v_N\)
在图信号中，拉普拉斯算子被用来描述中心节点与邻居节点之间信号的差异：\(Lx=(D-A)x=[\cdots,\sum_{v_j\in N(v_i)}(x_i-x_j),\cdots]^T\)。由此可知，拉普拉斯矩阵是一个反映图信号局部平滑度的算子。

【图信号的总变差】 \(TV(x)=x^TLx=\sum_{e_{ij}\in E}(x_i-x_j)^2\)

总变差是一个标量，刻画了图信号整体的平滑度

【关于拉普拉斯矩阵的特征值】

由于二次型\(x^TLx\geq 0\)，因此拉普拉斯矩阵为半正定矩阵，其特征值均非负
可以证明，对于正则化的拉普拉斯矩阵，特征值不大于2

图傅里叶变换

【图傅里叶变换GFT】 \(\tilde{x}=V^Tx\)

\(\tilde{x}_k=\sum_{i=1}^{N}V_{ki}^Tx_i\)
特征向量为傅里叶基，傅里叶系数\(\tilde{x}_k\)本质上是图信号在傅里叶基上的投影，衡量了图信号与傅里叶基之间的相似度

【图傅里叶逆变换IGFT】 \(x=V\tilde{x}\)

\(x_k=\sum_{i=1}^{N}V_{ki}\tilde{x_i}\)
特征向量组成了\(N\)维特征空间中的一组完备的基向量，图信号可表示为基向量的线性加权，权重则为对应傅里叶基上的傅里叶系数

再次考察总变差，\(TV(x)=x^TLx=(V^Tx)^T\Lambda(V^Tx)=\tilde{x}^T\Lambda\tilde{x}= \sum_{k=1}^{N}\lambda_k\tilde{x}_k^2\)。由此可以看出图信号的总变差与图的特征值之间存在明显的关系。在图信号为单位向量的限定条件下，若\(x=v_k\)，则有\(TV(x)=\lambda_k\)。特别地，当图信号与特征向量\(v_1\)完全重合时，总变差取最小值。可以进一步证明，如果依此选择彼此正交的图信号\(x_k\)使得\(TV(x_k)\)取最小值，则这组彼此正交的图信号即为\(\{v_1,\cdots,v_N\}\)，即\(\lambda_k=\min_{x:||x||=1,x\bot x_1,\cdots,x_{k-1}} \ x^TLx\)。

通过以上信息可以发现，特征值的依次排列对图信号的平滑度做出了梯度刻画，因此特征值可以看作信号中的频率：特征值越低，则频率越低，对应傅里叶基变化越缓慢；特征值越高，则频率越高，对应傅里叶基变化越剧烈。傅里叶系数可以等价于图信号在对应频率分量上的幅值，反映了图信号在该频率分量上的强度。

【图信号能量】 \(E(x)=||x||_2^2=x^Tx=\tilde{x}^T\tilde{x}\)

【图信号的频谱】将图信号所有傅里叶系数合称为图信号的频谱

频域视角是一种全局视角，频谱上任意一个傅里叶系数都是对图信号低频或高频特征的定量描述
频谱中既包含了图信号本身值的大小，也考虑了图的结构信息

图滤波器

【图滤波器】假设图滤波器为\(H\in R^{N\times N}\)，\(H:R^N\rightarrow R^N\)，令输出图信号为\(y\)，则有\(y=Hx=\sum_{k=1}^N(h(\lambda_k)\tilde{x}_k)v_k\)

对图滤波器的定义式变换可得： \(\(y=Hx=\sum_{k=1}^N(h(\lambda_k)\tilde{x}_k)v_k=\begin{bmatrix}v_1 & \cdots & v_N\end{bmatrix}\begin{bmatrix}h(\lambda_1)\tilde{x}_1 \\ \vdots \\ h(\lambda_N)\tilde{x}_N \end{bmatrix}=V\begin{bmatrix}h(\lambda_1) & & \\ & \ddots & \\ & & h(\lambda_N)\end{bmatrix}V^Tx=(V\Lambda_h V^T)x\)\)

观察对角矩阵\(\Lambda\)与\(\Lambda_h\)，可以看出\(H\)仅改变了主对角线上的特征值（\(\Lambda\rightarrow\Lambda_h\)）。

【频率响应矩阵】 \(\Lambda_h=\begin{bmatrix}h(\lambda_1) & & \\ & \ddots & \\ & & h(\lambda_N)\end{bmatrix}\)

图滤波器通常具有的性质包括：

线性：\(H(x+y)=Hx+Hy\)
顺序无关：\(H_1(H_2x)=H_2(H_1x)\)
如果\(h(\lambda)\neq 0\)，则滤波操作可逆

【图位移算子】矩阵\(S\in R^{N\times N}\)，只在对角和边坐标取非零值，即\(S_{ij}\)当且仅当\(i\neq j\)且\(e_{ij}\not \in E\)

典型的图位移算子是邻接矩阵和拉普拉斯矩阵
\(Sx\)描述了一种作用在每个节点一阶子图上的变换操作

【图滤波器的多项式表示】对于平移不变的图滤波器，可以使用图位移算子的多项式进行表示：\(H=\sum_{k=0}^{N}h_kS^k\)

空域角度

定义\(x^{(k)}=S^kx=Sx^{(k-1)}\)，则\(y=\sum_{k=0}^{K}h_kx^{(k)}\)。由于\(S\)为图位移算子，因此\(x^{(k-1)}\)到\(x^{(k)}\)的变换只需要所有节点的一阶邻居参与计算，这种性质称为图滤波器的局部性。

从空域角度看，滤波操作具有的性质包括：

局部性：每个节点的输出信号值只需要考虑其K阶子图
可通过K步迭代式的矩阵向量乘法完成滤波操作

频域角度

当图位移算子为拉普拉斯矩阵时，图滤波器可表示为\(H=\sum_{k=0}^{N}h_kL^k=V(\sum_{k=0}^K h_k\Lambda^k)V^T=V\begin{bmatrix}\sum_{k=0}^{K}h_k\lambda_1^k && \\ & \ddots \\ && \sum_{k=0}^{K}h_k\lambda_N^k\end{bmatrix}V^T\)。当\(K\)足够大时，可以用上述方式逼近任意一个关于\(\lambda\)的函数。

频域下滤波操作可表示为\(y=Hx=V(\sum_{k=0}^K h_k\Lambda^k)V^Tx\)，变换过程主要由3步组成：

通过GFT将图信号变换到频域空间，得到\(V^Tx\)
通过\(\Lambda_h\)对频率分量的强度进行调节，得到\(\Lambda_h V^Tx\)
通过IGFT将调节后的信号进行反解，得到\(V\Lambda_hV^Tx\)

假设所有多项式系数\(h_k\)构成向量\(h\)，则\(H\)的频率响应矩阵为\(\Lambda_h=\sum_{k=0}^Kh_k\Lambda^k=diag(\Psi h)\)，其中\(\Psi=\begin{bmatrix} 1& \lambda_1& \cdots & \lambda_1^K \\ 1& \lambda_2& \cdots & \lambda_2^K \\ \vdots & \vdots & \ddots & \vdots \\ 1& \lambda_N& \cdots & \lambda_N^K\end{bmatrix}\)为范德蒙矩阵。我们可以通过上式反解得到多项式系数\(h=\Psi^{-1}diag^{-1}(\Lambda_h)\)，其中\(diag^{-1}\)将对角矩阵变换为列向量。

从频域角度看，图滤波操作具有如下性质：

在频域能够更加清晰地完成对图信号的特定滤波操作
图滤波器如何设计具有显式的公式推导
对矩阵进行特征分解是非常耗时的操作，时间复杂度为\(O(N^3)\)。相比空域视角的矩阵向量乘法而言有一定局限性。

图卷积神经网络

【图卷积运算】 \(x_1*x_2=IGFT(GFT(x_1)\odot GFT(x_2))\)，\(\odot\)为哈达玛积。

\[
\begin{aligned}
x_1*x_2
&=V((V^Tx_1)\odot (V^Tx_2))\\
&=V(\tilde{x}_1\odot (V^Tx_2))\\
&=V(diag(\tilde{x}_1)(V^Tx_2))\\
&=(V\cdot diag(\tilde{x}_1)V^T)x_2\\
&=H_{\tilde{x}_1}x_2
\end{aligned}
\]

由上述推导可知，两组图信号的图卷积运算总能转化为对应形式的图滤波运算，因此图卷积可以等价于图滤波。

先前讨论的图信号都以一维列向量形式表示，但是图信号可以拓展到多通道的矩阵形式\(X\in R^{N\times d}\)，即图信号矩阵，\(d\)为图信号的总通道数。相应地，图滤波操作表示为\(Y=HX\)，其中第\(j\)个通道的输出\(Y_{:,j}\)对应于输入\(X_{:,j}\)。

对频率响应矩阵进行参数化

图滤波算子的核心在于频率响应矩阵。定义如下网络层：

\[
X'=\sigma(V\begin{bmatrix}\theta_1 & & \\ & \ddots & \\ & & \theta_N\end{bmatrix}V^TX)=\sigma(V diag(\theta) V^T)=\sigma(\Theta X)
\]

在上式中，\(\{\theta_1,\cdots,\theta_N\}\)为需要学习的参数，\(\Theta\)为参数对应的图滤波器。从空域看，网络层引入了自适应的图位移算子，通过学习的手段指导算子的学习；从频域看，网络层在\(X\)与\(X'\)之间训练了一个可自适应的图滤波器，对应的频率响应函数可通过监督学习实现。

该方案存在的问题是引入的学习参数过多，需要学习的参数量与图中节点数一致，这样极易发生过拟合问题。另外，在真实图数据中，数据的有效信息通常蕴含在低频段中，因此图滤波器设置N个维度的自由度且对每个频率都进行学习是没必要的。

对多项式系数进行参数化

为了拟合任意的频率响应函数，可以将拉普拉斯矩阵的多项式形式转化为一种可学习的形式：\(X'=\sigma(V(\sum_{k=0}^{K}\theta_k\Lambda^k)V^TX)=\sigma(V diag(\Psi\theta)V^TX)\)，其中\(\{\theta_1,\cdots,\theta_K\}\)为多项式系数向量，也是网络层需要学习的参数。参数量\(K\)可自由控制，\(K\)的大小可以衡量输入与输出之间滤波关系的复杂程度，一般\(K\ll N\)以减小过拟合的风险。

该方案存在的问题主要在于依赖矩阵的特征分解而为计算带来较高复杂度。

设计固定的图滤波器

在多项式系数参数化方案的基础上，设定\(K=1\)，因此\(X'=\sigma(\theta_0X+\theta_1LX)\)，再设\(\theta_0=\theta_1=\theta\)，则有\(X'=\sigma(\theta(E+L)X)=\sigma(\theta\tilde{L}X)\)。对上式进行归一化处理，此时\(\theta\)可取1，最后可以得到一个固定的图滤波器\(\tilde{L}\)。

为了加强学习是的数值稳定性，对\(\tilde{L}\)也进行了类似拉普拉斯矩阵的归一化处理：

\[
\begin{aligned}
\tilde{L}_{sym}&=\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}\\
\tilde{A}&=A+I\\
\tilde{D}_{ii}&=\sum_{j}\tilde{A}_{ij}
\end{aligned}
\]

同时，为了加强网络的拟合能力，添加一个参数化的权重矩阵\(W\)对输入的图信号矩阵进行仿射变换，得到\(X'=\sigma(\tilde{L}_{sym}XW)\)。

【图卷积层（GCN Layer）】 \(X'=\sigma(\tilde{L}_{sym}XW)=\sigma(\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}XW)\)

\(\tilde{A}=A+I\)
\(\tilde{D}_{ii}=\sum_{j}\tilde{A}_{ij}\)

图卷积层是对频率响应函数拟合形式上的极大简化，最后图滤波器退化为\(\tilde{L}_{sym}\)。图卷积层的计算过程相当于对节点的一阶邻居进行了聚合，但是通过堆叠多层GCN可以达到高阶多项式对频率响应函数的拟合效果。在工程上，\(\tilde{L}_{sym}\)可以用稀疏矩阵表示，能够降低图卷积层的计算复杂度。相比频域中矩阵特征分解的\(O(N^3)\)复杂度，图卷积层的复杂度可降低为\(O(|E|d)\)。

对于固定的图滤波器的合理性可以进行如下说明：

\(\tilde{L}_{sym}\)本身具有的滤波特性是符合真实数据的性质的，能够对数据实现高效的滤波操作
虽然GCN层是对频率响应函数的线性近似推导而来，但是通过堆叠GCN层可以达到高阶多项式形式的频率响应函数的滤波能力

一般来说，对于只能从频域出发进行矩阵特征分解从而执行图卷积计算的模型，称之为频域图卷积模型；对于图卷积计算不需要进行矩阵特征分解，能在空域执行矩阵乘法计算的模型，称之为空域图卷积模型。虽然空域图卷积模型在工程上具有优越性，但是频域视角对于图卷积模型的设计仍然是十分重要的。