图卷积网络 GCN （一）研究背景和空域图卷积

研究背景

首先，为什么需要研究图卷积网络GCN（Graph Convolution Network）呢？

目前算法研究处理的数据主要分为两种：

Euclidean 结构数据：主要有图片、语音、文本等数据结构，例如图像、视频中像素点是排列整齐的矩阵，可以被CNN(Convolution Neural Network)高效地处理。

因此，研究 GCN 的原因可以分为以下三点：

CNN 无法直接处理 Non-Euclidean 数据。学术表达是传统离散卷积无法在 Non-Euclidean 的结构数据上无法保持平移不变性；简而言之就是在图结构数据中每个顶点的邻居节点数据不同，无法使用相同大小的卷积核来进行卷积运算。
由于 CNN 无法直接处理 Non-Euclidean 结构数据，而卷积操作可以有效地提取数据的特征。因此，如何在图数据中利用卷积来提取空间特征来进行机器学习是一个亟待解决的问题，也是 GCN 研究的重点内容。
如果研究的问题本身不具备拓扑图结构，是否可以使用 GCN？广义上来说任何数据在其空间内都可以建立拓扑关联，例如谱聚类方法（谱聚类原理总结），因此拓扑图结构是一种广义的数据结构，GCN 可以应用在多个领域当中。

CNN 比 FC 有效且在在图像识别等任务中取得显著的成效，主要是因为 CNN 的以下特性：

对于 CNN 而言，其核心在于使用了基于卷积核的卷积操作来提取图像的特征，即计算区域内的中心节点和相邻节点进行加权求和。

CNN 在图像领域取得显著效果的原因是图片（RGB）是规则化的数据结构，可存储在三维矩阵中，无论卷积核平移到图片中的哪个位置都可以保证其运算结果的一致性，这就是局部平移不变性。如下图所示：

CNN 的卷积本质就是利用这种平移不变性来对扫描的区域进行卷积操作，从而实现图像特征的提取。

拓扑图结构是不规则的数据结构，所以其不存在平移不变形（每个顶点的周围邻居数不固定），如下图所示，无法使用固定大小的卷积核来进行卷积操作，使得传统的 CNN 方法无法直接应用于网络中。

CNN 一个核心的思想是卷积核参数共享（Parameter Sharing），卷积核在图像上的卷积操作如下：

此时模型的参数大小仅与卷积核大小有关，而如果不进行参数共享的话，参数的大小则与图像的像素矩阵保持一致，如下图所示：

CNN 另一核心思想是卷积核的局部连接性（Locally Connection），局部连接是指卷积操作仅在与卷积核大小对应的区域进行，卷积操作的输入和输出是局部连接的，全局连接则会导致模型参数量巨大，与 FC（Full Connection）网络类似：

PS：卷积核还有另一特性，每个卷积核都是` $O(1)$ 复杂度，与输入大小无关。这样可以提高模型的泛化能力。

CNN 的层次化表达是指神经网络通过多个卷积层对图片进行特征提取，包括池化（Pooling）操作。每一个卷积层在前一层的基础上进行处理操作，那么随着网络深度的增加，其提取到的特征越高级，趋于语义特征。比如说：第一层可能是一些线条，第二层可能会是一些纹理，第三层可能是一些抽象图案，如下图所示：

现在常用的图卷积可以被分成两类：

空域图卷积直接在原空间图上做卷积运算。频域图卷积是先把信号转换到傅立叶空间，然后做卷积运算后再转换到原始空间。

上述谈到 CNN 难以应用在图上的问题在于顶点的邻域无法确定，空域卷积是以最直观的方式选择特定数量的领域并在每个节点及其领域组成的矩阵中进行卷积运算。经典空域卷积文章推荐阅读：Learning Convolutional Neural Networks for Graphs

这篇文章针对图分类任务，过程如下图所示：

算法步骤如下：

根据中心性的方法选择 $w$ 个可以代表 graph 的顶点——即计算顶点与其它所有节点的距离和，和值越小说明该顶点的中心性越大。
为每个顶点找到 $K$ 个邻域顶点。先从一阶邻域中选择，如果顶点数大于 $K$ 那么删除中心性值小的顶点；如果顶点数小于 $K$ 那么接着从二阶邻域中选择或者补充 0 向量。
选出的 $K$ 个节点，每个节点和其它节点可以构成 $(K+1)\times F$ 的矩阵，所有的边也可以构成 $(K+1)\times (K+1)\times F$ 的张量，然后在这些张量中做卷积操作。