一、CNN

传统的CNN（Convolutional Neural Network）利用一个共享参数的卷积核，通过计算中心像素点以及相邻像素点的加权和构成feature map实现空间特征提取，在图像分类、语义分割、机器翻译等领域都取得了很好地效果。但是CNN也存在一个弊端，就是只能处理Euclidean结构的数据，对于图结构数据无法保持平移不变性（图中每个顶点的相邻节点数据可能不同，无法使用一个固定尺寸的卷积核进行卷积运算）。

二、GCN的发展史

GCN（Graph Convolutional Network）通过将局部的图结构和节点特征结合，可以实现图结构数据的卷积操作。图卷积大致可分为两类：

• 空间卷积：找出中心节点的邻居节点，再基于中心节点的邻居节点进行传统卷积操作。
• 谱图卷积：基于图上的傅里叶变换，借助图的Laplacian矩阵的特征值和特征向量，定义图上的卷积。

这里我们主要关注谱图卷积。

2.1 基本原理

关于GCN的基本原理及公式推导，强烈下面几篇资料：

• 从CNN到GCN的联系与区别——GCN从入门到精（fang）通（qi）
• GCN (Graph Convolutional Network) 图卷积网络解析

主要内容：CNN，拉普拉斯矩阵，Graph上的傅里叶变换及卷积，Graph Convolution

2.2 第一代GCN

2.3 第二代GCN

2.4 第三代GCN

文章【Wavelets on graphs via spectral graph theory】提出利用切比雪夫多项式来进行近似，降低前向传播高复杂度的问题。

接着，文章【Semi-supervised Classification with Graph Convolutional Networks】在切比雪夫多项式近似的基础上进一步简化，提出一阶近似，通过叠加多层GCN来达到经典卷积层的功能。（该文中的GCN形式，其实是二阶Chebyshev多项式推导出的特例）


这里，图中的Feature matrix $X$对应公式中的 $H$.

上面公式中：

• A波浪=A+I，I是单位矩阵，相当于是无向图G的邻接矩阵加上自连接(就是每个顶点和自身加一条边)。
  如此一来消息聚合时不仅能聚合来自其他结点的消息，还能聚合结点自身的消息。
  

• D波浪是A波浪的度矩阵（degree matrix），公式为D波浪ii=∑j A波浪（无向图里,节点的度就是节点连接的边的个数。）

• H是每一层的特征，对于输入层的话，H就是X（初始就给定的）

• σ是像Softmax、ReLU这样的非线性激活函数

• W就是每一层模型的参数，也就是模型给节点特征乘上的权重，这是模型需要训练的参数，即权值矩阵

他们之间的运算，就是各矩阵相乘，部分内容就长这样：

(1) 对称归一化的拉普拉斯矩阵

其实我们需要重点关注的就是上面画红线的部分，也就是 对称归一化的拉普拉斯矩阵，拉普拉斯矩阵是对称矩阵，可以进行特征分解（谱分解）。

之所以邻接矩阵$A$要加上一个单位矩阵$I$，是因为我们希望 在进行信息传播的时候顶点自身的特征信息也得到保留。 而对邻居矩阵A波浪进行归一化操作 $D^{-1/2}A\ast D^{1/2}$有如下好处：

1. 为了信息传递的过程中保持特征矩阵$H$的原有分布，防止一些度数高的顶点和度数低的顶点在特征分布上产生较大的差异。归一化可以将数据变得具有可比性，同时又相对保持数据之间的关系。
2. 经过归一化处理后，模型即使不训练，完全用随机初始化的参数W，GCN提取出来的特征也十分优秀。

关于对称归一化的拉普拉斯矩阵的实现代码可以参考博客：GCN之邻接矩阵标准化

(2) GCN特征聚合方式

GCN的每一层通过 归一化的拉普拉斯矩阵 和 特征矩阵H(l) 相乘得到每个顶点邻居特征的汇总，然后再乘上一个 参数矩阵W(l) ，加上 激活函数σ 做一次非线性变换得到 聚合邻接顶点特征的矩阵H(l+1)。

同时，从上式也可以看出，GCN就是在节点特征聚合的过程中加入了针对每个节点度的归一化，使得邻居节点特征的聚合权重由邻居节点的度来决定。

三、GCN的结构

GCN是一个多层的图卷积神经网络，每一个卷积层仅处理一阶邻域信息，通过叠加若干卷积层可以实现多阶邻域的信息传递。

GCN的层数通常不需要太深，通常来说3-5层已经能够提取丰富的空间特征。每个卷积层处理一阶邻域信息，3-5层已经能够得到比较完善的邻域关系。实验表明，层数太深的GCN反而效果不佳。

这里给出一个两层GCN的表达式：

该模型实际是输入层+隐藏层（图卷积层，类似全连接层的作用）+SoftMax+输出层构成的，GCN模型可视化为：

[1] Kipf T N, Welling M. Semi-supervised classification with graph convolutional networks[J]. arXiv preprint arXiv:1609.02907, 2016.

总结来说，GCN就是在节点特征聚合平均法的基础上，加入了针对每个节点度的归一化，使得邻居节点特征的聚合权重由邻居节点本身的度来决定。

参考资料

• GCN-图卷积神经网络算法讲解（通俗版）
• 【GCN】论文笔记：SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS