图卷积神经网络初探

1. 什么是图卷积神经网络

卷积神经网络（CNN）是深度学习中使用最频繁的神经网络之一，但它存在一个缺陷，就是它只能处理欧几里得空间内的图结构而不能处理更一般的图结构。针对这一缺陷，人们提出了能处理更一般图结构的卷积神经网络，称为图卷积神经网络（GCN）。当存在一个图结构，图有$N$个顶点，$M$条边组成，此时一般的卷积神经网络无法在此发挥作用，需要用到图卷积神经网络。

2. 基于频域的图卷积神经网络

基于频域的图卷积神经网络一般有以下的迭代形式：

$$H_l= \sigma(\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}H_{l-1}W_l)$$

其中$H_l$表示第$l$层的输出；$\hat{D}$表示$\hat{A}$的度数矩阵；$\hat{A}$表示图的邻接矩阵加上单位矩阵，即$\hat{A}=A+I$；$W_l$是需要学习的参数；$\sigma$是非线性激活函数。这个式子是怎么推导出来的呢？首先有必要知道傅里叶变换与拉普拉斯算子的一些关系以及拉普拉斯算子和拉普拉斯矩阵的关系。我们知道在求函数在空间域的卷积时，可以先将两个函数从空间域变换到频域：

$$F(w)=\int f(t)e^{-jwt}dt$$

在频域上求积，然后作反变换：

$$f(t)=\int F(w)e^{jwt}dw$$

反变换的结果就是两个函数在空间域上的卷积。然后我们还知道拉普拉斯算子$\Delta$作用到一个函数时有：

$$\Delta f=\sum_{i}\frac{\partial^2 f}{\partial x_i^2}$$

我们可以发现，当拉普拉斯算子作用于频率域的基时，有下式：

$$\Delta e^{jwt}=\frac{\partial^2}{\partial t^2}e^{jwt}=-w^2e^{jwt}=\lambda e^{jwt}$$

这可以看作频率域的基函数是拉普拉斯算子的特征函数。现在我们看图的拉普拉斯矩阵，我们知道图的拉普拉斯矩阵$L$由下面式子表示：

$$L=D-A$$

其中$A$是图的邻接矩阵，$D$是$A$的度数矩阵。我们可以认为这是拉普拉斯算子在图结构上的形式，我们可以认为拉普拉斯算子在不同的对象有不同的表现，比如在函数域就是求函数的二阶导，在图上就是图的拉普拉斯矩阵，这是因为图的梯度与散度和函数的梯度与散度表现形式不同以及拉普拉斯算子本质是求梯度的散度决定的。在函数域上，我们有：

$$\Delta f=\Delta\int_w F(w)e^{jwt}dt=\int_wF(w)\Delta e^{jwt}dt=\int_w\lambda_wF(w)e^{jwt}dt$$

所以在图$G$上，我们也有：

$$\Delta x=L*x=\sum_i \lambda_i\hat{x}_iu_i$$

其中$u_i$是拉普拉斯矩阵$L$的特征向量，$\lambda_i$是特征值，$\hat{x}_i$是向量$x$在$u_i$上的分量。在函数域中，我们使用$e^{jwt}$作为基底，将函数转换到频率域。在图中，我们也可以使用特征向量集合$u_i$作为基底，将向量转换到该基底的域中。已知向量$x$，求其转换到$u_i$基底的线性组合，公式为：

$$\hat{x}=\sum_iu_i^*x_i=U^Tx$$

其中$u^*$表示向量$u$的共轭，我们默认特征向量都是实数。从$\hat{x}$反变换$x$的公式为：

$$x=\sum_iu_i\hat{x}_i=U\hat{x}$$

所以如果现在有矩阵$X$表示图的特征，$H$是卷积核，则$X$与$H$的卷积可以用下式表示：

$$H*X=U(U^TH\odot U^TX)$$

$\odot$是求哈达玛积，然后人们又对上式进行一系列的化简，比如将哈达玛积转换成矩阵乘法，近似求解$U$等等，最终得到了下面的形式：

$$H*X= \hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}XW$$

其中$W$与卷积核$H$相关，所以可以通过学习与更新$W$来间接更新卷积核$H$。加上激活函数，用$H_l$表示第$l$层的特征，则可以得到图卷积网络的式子：

$$H_l= \sigma(\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}H_{l-1}W_l)$$

在图卷积网络中，每一层可以使用同一个卷积核，即每一层的参数$W_l$是相同的，也可以使用不同的卷积核，即每一层的参数$W_l$是不同的。