图卷积网络(GCN)原理解析

Graph Convolutional Networks涉及到两个很重要的概念：graph和Convolution。传统的卷积方式在欧式数据空间中大展神威，但是在非欧式数据空间中却哑火，很重要的一个原因就是传统的卷积方式在非欧式的数据空间上无法保持“平移不变性”。为了能够将卷积推广到Graph等非欧式数据结构的拓扑图上，GCN横空出世。在深入理解GCN： 的来龙去脉之前，我觉着我们有必要提前对以下概念有点印象：

论文链接 Semi-supervised Classification with Graph Convolutional Networks

1.拉普拉斯矩阵及其变体

给定一个节点数为 的简单图 ， 是 的度矩阵， 是 的邻接矩阵，则 的拉普拉斯矩阵可以表示为 . 中的各个元素表示如下：

1.传统的傅里叶变换

当变换对象为离散变量时，求积分相当于求内积，即

这里的 就是传说中似乎有点神秘的拉普拉斯算子的特征函数（拉普拉斯算子是欧式空间中的二阶微分算子，卸了妆之后的样子是 ）。

为何这样说呢？是因为从广义的特征方程定义看 , 本身是一种变换， 是特征向量或者特征函数， 是特征值。我们对基函数 求二阶导， . 可以看出 是变换 的特征函数。

在Graph中，拉普拉斯矩阵 可以谱分解(特征分解)，其特征向量组成的矩阵是 ，根据特征方程的定义我们可以得到 。通过对比我们可以发现 相当于 , 相当于 。因此在Graph上的傅里叶变换可以写作 .

从傅里叶变换的基本思想来看，对 进行傅里叶变换的本质就是将 转换为一组正交基下的坐标表示，进行线性变换，而坐标就是傅里叶变换的结果，下图中的 就是 在第一个基上的投影分量的大小。

我们通过矩阵乘法将Graph上的傅里叶变换推广到矩阵形式：

是Graph上第 个节点的特征向量，可得Graph上的傅里叶变换形式：

。

此处的 是Graph的拉普拉斯矩阵的特征向量组成的特征矩阵的转置，在拉普拉斯矩阵的优良性质中我们知道拉普拉斯矩阵的特征向量组成的矩阵为正交阵，即满足 ，所以Graph的逆傅里叶变换形式为 ，矩阵形式如下：

到此为止我们已经通过类比从传统的傅里叶变换推广到了Graph上的傅里叶变换。接下来我们就要借助傅里叶变换这个桥梁使得Convolution与Graph把酒言欢了。

在前言中我们了解了大名鼎鼎的卷积定理：函数卷积的傅里叶变换是其傅里叶变换的乘积，即对于 ,两者的卷积是其傅里叶变换的逆变换：

我们把上一节中得到的Graph上的傅里叶变换公式代入得到：

是Hamada积，表示逐点相乘。

我们一般将 看作输入的Graph的节点特征，将 视为可训练且参数***享的卷积核来提取拓扑图的空间特征。为了进一步看清楚卷积核 ，我们将上式改写为：

也许有人对于上式的变换心存疑虑，证明其实很简单，有意者请看这位答主的解答 GCN中的等式证明 - 知乎

至此，我们已经推导出来GCN的雏形。

1. 第一代GCN

卷积操作的核心是由可训练且参数***享的卷积核，所以第一代GCN是直接把上式中的 中的对角线元素 替换为参数 。先初始化赋值，然后通过反向传播误差来调整参数 。

所以第一代GCN就变成了酱个样子：

是Graph中每个节点特征的表示向量， 是每个节点经过GCN卷积之后的输出。Graph中的每个节点都要经过卷积核卷积来提取其相应的拓扑空间，然后经过激活函数 传播到下一层。

第一代GCN的缺点也是显而易见的，主要有以下几点，

2. 第二代GCN

面对第一代GCN参数过多的缺点，第二代GCN进行了针对性的改进。由于Graph上的傅里叶变换是关于特征值的函数 ， 也可写作 ，用k阶多项式对卷积核进行改进:

将其代入到 可以得到：

所以第二代GCN是介个样子：

可以看出二代GCN的最终化简结果不需要进行矩阵分解，直接对拉普拉斯矩阵进行变换。参数是 ，k一般情况下远小于Graph中的节点的数量 ，所以和第一代GCN相比，第二代GCN的参数量明显少于第一代GCN，减低了模型的复杂度。对于参数 ，先对其进行初始化，然后根据误差反向传播来更新参数。但是仍旧需要计算 ，时间复杂度为 .

另外我们知道对于一个矩阵的k次方，我们可以得到与中心节点k-hop相连的节点，即 中的元素是否为0表示Graph中的一个结点经过k跳之后是否能够到达另外一个结点，这里的k其实表示的就是卷积核感受野的大小，通过将每个中心节点k-hop内的邻居节点聚合来更新中心节点的特征表示，而参数 就是第k-hop邻居的权重。

未完待续。

1.在谱域图卷积中，我们对图的拉普拉斯矩阵进行特征分解。通过在傅里叶空间中进行特征分解有助于我们我们理解潜在的子图结构。ChebyNet, GCN是使用谱域卷积的典型深度学习架构。

2.空域卷积作用在节点的邻域上，我们通过节点的k-hop邻居来聚合得到节点的特征表示。空域卷积相比谱域卷积更加简单和高效。GraphSAGE和GAT 是空域卷积的典型代表。

参考文献

1. /

3. /yyl424525/article/details/100058264