图卷积网络 GCN（三）详解三代图卷积网络理论

前两篇介绍完图卷积网络的背景知识，现在正式引入 GCN！

卷积定义

在泛函分析中，卷积是通过两个函数 $f$ 和 $g$ 生成第三个函数的一种数学算子，表示函数 $f$ 与经过翻转和平移的 $g$ 的乘积函数所围成的曲边梯形的面积，公式如下所示：

$(f * g)(t) \stackrel{\text { def }}{=} \int_{\mathbb{R}^{n}} f(\tau) g(t-\tau) d \tau \quad\quad\quad (1)$

下面给出两幅图来直观理解上述公式，参考卷积解释：

以上是连续函数的卷积运算，对于离散卷积公式定义如下：

$(f * g)[n]=\sum_{m=-\infty}^{\infty} f[m] g[n-m]=\sum_{m=-\infty}^{\infty} f[n-m] g[m] \quad\quad\quad (2)$

卷积除了直接计算这种方法，还可以根据卷积定理来计算。

卷积定理：在适当条件下，两个信号的卷积的傅立叶变换等于它们傅立叶变换的点积。例如，一个域（如时域）的卷积等于另一个域（如频域）的点乘：

$\mathcal{F}\{f * g\}=\mathcal{F}\{f\} \cdot \mathcal{F}\{g\} \quad\quad\quad (3)$

如果以 $\mathcal{F}^{-1}$ 表示傅里叶逆变换，那么卷积计算可以重新表示为：

$f * g=\mathcal{F}^{-1}\{\mathcal{F}\{f\} \cdot \mathcal{F}\{g\}\} \quad\quad\quad (4)$

PS：利用卷积定理可以简化卷积的运算量。对于一个长度为 $n$ 的序列，按照卷积的定义来计算则需要做 $2n-1$ 组对位乘法，即时间复杂度为 $O(n^2)$ ；而利用傅立叶变换后，只需要计算一组对位乘法，而且离散傅立叶变换有快速的算法（快速傅立叶变换），所以总的计算复杂度为 $O(n\log n)$ 。

图卷积

谱图卷积的思想是：既然无法直接在空域对图进行卷积，那么将图信号映射到频域后再做卷积操作。

根据公式（4）与文章图卷积网络 GCN（二）图上的傅里叶变换和逆变换中图上的傅里叶变换公式，可得

$\begin{aligned} (f * h)_{G} &=\mathcal{F}^{-1}[\mathcal{F}\{f\} \cdot \mathcal{F}\{h\}] \\ &=\mathcal{F}^{-1}\left[\mathbf{U}^{T} f \cdot \hat{h}\right] \end{aligned} \quad\quad\quad (5)$

上式表示时域信号 $f$ 和 $h$ 的卷积等价于将信号转换到傅立叶域做点乘后再逆变换回来。其中，向量 $f$ 与向量 $\hat{h}$ 的元素点积，等价于将 $\hat{h}$ 组织成对角矩阵的形式进行矩阵乘法，可得：

$\begin{aligned} (f * h)_{G} &=\mathcal{F}^{-1}\left[\mathbf{U}^{T} f \cdot \hat{h}\right] \\ &=\mathcal{F}^{-1}\left[\operatorname{diag}\left[\hat{h}_{1}, \ldots, \hat{h}_{n}\right] \mathbf{U}^{T} f\right] \end{aligned}\quad\quad\quad (6)$

根据图上的逆变换计算公式，上式做成 $\mathbf{U}$ 可得：

$(f * h)_{G}=\mathbf{U} \operatorname{diag}\left[\hat{h}_{1}, \ldots, \hat{h}_{n}\right] \mathbf{U}^{T} f\quad\quad\quad (7)$

也可以写成写成矩阵形式为：

$(f*h)_G=\mathbf{U} ((\mathbf{U} ^Tf)(\mathbf{U} ^Th)) \quad\quad\quad (8)$

目前先不写成式 (8) 的形式，是因为在 GCN 中我们的卷积核是可训练并且参数共享的，所以在此我们可以直接令

$\operatorname{diag}\left[\hat{h}_{1}, \ldots, \hat{h}_{n}\right] =\operatorname{diag}\left[\theta_{1}, \ldots, \theta_{n}\right] = g_{\theta} \quad\quad\quad (9)$

这就是深度学习中的可学习参数。

第一代图卷积

论文来源：《Spectral Networks and Deep Locally Connected Networks on Graphs》

第一代图卷积的计算方法就直接根据式（7）（9）推出

$y=\sigma\left(\mathbf{U} g_{\theta} \mathbf{U}^{T} x\right)=\sigma\left(\mathbf{U}\left[\begin{array}{ccc} \theta_{1} & & \\ & \theta_{2} & \\ & & \\ & & \theta_{N} \end{array}\right] \mathbf{U}^{T} x\right) \quad\quad\quad (10)$

虽然利用上式已经可以构造深度网络进行图卷积运算了，但该版本有不少缺点：

没有 local 信息。每次卷积都是所有顶点都参与运算，没有实现局部卷积和参数共享。
运算量大。每次卷积都要进行拉普拉斯矩阵分解和矩阵相乘，计算复杂度为 $O(N^3)$ 。
参数量大。每个卷积核参数量为 $O(N)$ 。

第二代图卷积

文章来源：
《Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering》

针对第一代图卷积中存在的问题，学者基于切比雪夫多项式提出第二代 GCN：ChbeyNet

首先回顾下图傅里叶计算公式：

$\mathcal{F}_{T}\left(\lambda_{k}\right)=\hat{g}_{k}=\sum_{i=1}^{N} g(i) u_{k}(i) \quad\quad\quad (11)$

可知函数和特征值密切相关，令 $g_{\theta}$ 为拉普拉斯矩阵 $L$ 的特征值函数 $g_{\theta}(\Lambda)$ ：

$y=\sigma\left(\mathbf{U} g_{\theta} \mathbf{U}^{T} x\right)=\sigma\left(\mathbf{U} g_{\theta}(\Lambda) \mathbf{U}^{T} x\right) \quad\quad\quad (12)$

以拉普拉斯矩阵的特征值作为卷积核同样存在缺陷：

不具备局部连接性；
时间复杂度为 $O(n)$ ;

为了克服上述缺陷引入 $K$ 阶多项式：

$g_{\theta}(\Lambda) \approx \sum_{k=0}^{K-1} \theta_{k} \Lambda^{k}\quad\quad\quad (13)$

其中，参数 $\theta_k\in R^K$ 是多项式系数，因此滤波器具有了 $K$ 阶局部性，复杂度也降低到 $O(K)$ 。

将式代入第一代图卷积式（10）中可得：

$y=\sigma\left(\mathbf{U} g_{\theta}(\Lambda) \mathbf{U}^{T} x\right)=\sigma\left(\mathbf{U} \sum_{k=0}^{K-1} \theta_{k} \Lambda^{k} \mathbf{U} x\right)=\sigma\left(\sum_{k=0}^{K-1} \theta_{k} L^{k} x\right)\quad\quad\quad (14)$

其中 $\sigma$ 是激活函数，公式（14）的计算时间复杂度为 $O(K×N^2)$ ，因为对于静态图而言 $L$ 是固定的， $L^k$ 可以提前计算得到。如果使用稀疏矩阵乘法（pytorch 里有封装），时间复杂度是 $O(K×|E|)$ 其中 $|E|$ 是稀疏矩阵中非零元的个数表示图中边的数量。此时计算图卷积就不需要再乘上特征向量矩阵 $\mathbf{U}$ ，而是直接使用拉普拉斯矩阵 $L$ 的 $k$ 次方，就避免了进行特征分解。

因为 $L^k$ 当 $K$ 很大的时候并不稀疏（ $|E|$ 接近 $N^2$ ），所以文中提出了利用切比雪夫多项式展开（任何 $k$ 次多项式都可以通过切比雪夫多项式展开）来近似 $L^k$ ，切比雪夫多项式递归式为：

$T_0(x)=1\\T_1(x)=x\\T_k(x)=2xT_{k-1}(x)-T_{k-2}(x) \quad\quad\quad (15)$

因此根据上式可知：

$g_{\theta}(\Lambda) \approx \sum_{k=0}^{K-1} \theta_{k} T_{k}(\widetilde{\Lambda})\quad\quad\quad (16)$

其中， $\tilde{\Lambda}=\frac{2}{\lambda_{\max }} \Lambda-I_{N}$ ; $\lambda_{\max }$ 是指拉普拉斯矩阵 $L$ 的最大特征值。

PS：因为切比雪夫多项式的输入要在 $[-1, 1]$ 之间，由于拉普拉斯矩阵的半正定性，所以所有的特征值都是大于等于 0 的，将其除以最大特征值可以将特征压缩到 $[0,1]$ 区间内，现在需要将其压缩到 $[-1, 1]$ ，所以我们有： $\tilde{\Lambda}=\frac{2}{\lambda_{\max }} \Lambda-I_{N}$ 。

我们将切比雪夫多项式引入到我们的卷积变换中：

$g_{\theta} * x \approx \sum_{k=0}^{K-1} \theta_{k} T_{k}(\widetilde{L}) x \quad\quad\quad (17)$

其中， $\tilde{L}=\frac{2}{\lambda_{\max }} L-I_{N}$ 。这个表达式为拉普拉斯多项式中的一个 $k$ 阶近似函数，依赖于节点的 $k$ 阶邻域（ $k$ 步可达），时间复杂度与边呈线形相关。

总结第二代图卷积优点如下：

运算量相比第一代的 $O(N^3)$ 可以降到 $O(K|E|)$ 。
引入 K-hop 感受野，可以捕捉局部特征。

第三代图卷积

文章来源：《Semi-supervised Classification with Graph Convolutional Networks》

第二代图卷积解决了拉普拉斯矩阵特征分解的问题，但是在计算图卷积操作时矩阵乘法时间复杂度为 $O(N^2)$ ，在此基础上优化 Kipf 等人提出了目前流行的 GCN。

GCN 通过式（17）进行多层卷积层进行叠加，而每层都会逐点进行非线性叠加。考虑到时间复杂度问题，令 $K=2$ ，也就是说得到了一个拉普拉斯算子的二阶近似函数。既可以对网络进行卷积操作计算量增加不大。通过叠加层数可以提升模型的非线性。

归一化的拉普拉斯矩阵的特征值区间为 $[0, 2]$ ，令 ${\lambda}_{max} \approx 2, K=2$ 可得：

$g_{\theta} * x \approx \theta_{0} x+\theta_{1}\left(L-I_{N}\right) x=\theta_{0} x-\theta_{1} D^{-\frac{1}{2}} A D^{-\frac{1}{2}} x\quad\quad\quad (18)$

其中， $\theta_0,\theta_1$ 是切比雪夫系数且仅存的两个参数！

在 GCN 的训练过程中需要规范化参数避免过拟合，令 $\theta=\theta_{0}^{\prime}=-\theta_{1}^{\prime}$ ，由式可得：

$g_{\theta} * x \approx \theta\left(I_{N}+D^{-\frac{1}{2}} A D^{-\frac{1}{2}}\right) x\quad\quad\quad (19)$

注意 $I_{N}+D^{-\frac{1}{2}} A D^{-\frac{1}{2}}$ 的特征值范围在 [0, 2] 之间，所以如果在很深的网络中会引起梯度爆炸的问题，需要再次进行一次归一化（Renormalization trick）：

$I_{N}+D^{-\frac{1}{2}} A D^{-\frac{1}{2}} \rightarrow \widetilde{D}^{-\frac{1}{2}} \widetilde{A} \widetilde{D}^{-\frac{1}{2}} , \widetilde{D}_{i i}=\sum_{j} \widetilde{A}_{i j} \widetilde{A}=A+I_{N}\quad\quad\quad (20)$

把上式从标量推广到矩阵，对于输入顶点的向量 $X \in R^{N \times C}$ ，其中 $N$ 为节点数， $C$ 为顶点的特征向量维度，可得：

$Z=\widetilde{D}^{-\frac{1}{2}} \widetilde{A} \widetilde{D}^{-\frac{1}{2}} X \Theta\quad\quad\quad (21)$

其中， $\Theta \in R^{C \times F}$ 是参数矩阵， $Z \in R^{N \times F}$ 是卷积后的顶点特征，时间复杂度为 $O(|E|FC)$ 。

根据上式一层卷积，多层图卷积计算公式公式为：

$H^{(l+1)}=\sigma\left(\widetilde{D}^{-\frac{1}{2}} \widetilde{A} \widetilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)}\right)\quad\quad\quad (22)$

其中， $\widetilde{A}=A+I_{N}$ ， $A$ 为邻接矩阵， $I_N$ 为单位矩阵，所以 $\widetilde{A}$ 为添加自连接的邻接矩阵； $\widetilde{D}_{i i}=\sum_{j} \widetilde{A}_{i j}$ ， $\widetilde{D}$ 为顶点的度数矩阵； $W^{(l)}$ 为神经网络第 $l$ 层的权重矩阵； $\sigma(\cdot)$ 是激活函数； $H^{(l)} \in R^{N \times D}$ 是第 $l$ 层的激活矩阵，并且 $H^{(0)}=X$ ， $X$ 是由顶点的特征向量组成矩阵。