背景

图卷积GCN的概念最早在ICLR2017中的一篇论文内提出，该论文名为《Semi-Supervised Classification with Graph Convolutional Networks》，作者是阿姆斯特丹大学的Thomas N. Kipf和Max Welling。

论文地址：https://arxiv.org/pdf/1609.02907.pdf

在过去，主要所使用的卷积方法都是CNN、RNN等经典模型，它们在许多领域中都有一个优异的表现。但是同样地，它们通常情况下只能处理结构较简单的序列或网格结构的数据。以CNN为例，它的本质是利用一个滤波器在矩阵上滑动，通过计算各个像素点的加权求和来得到特征图，实现一个特征的提取。而这一过程的可以实现的关键因素是不管滤波器移动到哪一个位置，它所覆盖的结构都是完全一样的。

但是在现实生活中，许多数据都是非结构化的，如社交网络，交通图，知识图谱等，它们各个顶点所相邻的顶点数目都可能不同，因此无法用同一个的卷积核对其进行处理。在这篇论文中，作者将卷积扩展到了图结构的数据中，提出了一个图卷积神经网络GCN。图卷积的核心思想是，图中每个节点受到它的邻居节点和更远处的节点影响而改变自己的状态，直到整个网络达到一个平衡状态，并且每个节点与其它节点的关系越近，受到的影响就越大。

图的定义

要对图结构进行处理，首先得将图结构数学化，我们可以用来代表一个图，其中V代表图的节点集，E为图的边集。表示图的邻接矩阵，它说明了图上各个节点的连通性以及各边的权重。是图的度矩阵，表示了图中每个节点的邻居数。同时，对于图中的每一个节点i，可以用，其中N表示节点数量，d表示节点特征数。最简单的拉普拉斯矩阵L可以定义为。

图卷积的分类

目前，图卷积的方式可以分为两类：一是基于频谱的图卷积，二是基于空间域的图卷积。

基于频谱的方法从图信号处理的角度引入滤波器来定义图卷积，它们通过傅里叶变换将结点映射到频域空间，通过在频域空间上做乘积来实现时域上的卷积，最后再将做完乘积的特征映射回时域空间。该方法是GCN的理论基础。

基于空间域的图卷积通过信息聚合的思想来实现卷积，它与传统的CNN更为类似。

基于频谱的图卷积

基于频谱的图卷积的思想来自于用于信号处理的傅里叶变换。关于具体的从傅里叶变换到图卷积，本文不作推导，详细的推导过程可以参考一些其它文献。

首先，对于图卷积中任何一层神经网络，可以用一个通用公式进行表示：

其中表示第l-1层的输入，即为第一层的输入，A为图的邻接矩阵。之后的各种图卷积都是对函数f进行修改和优化。

首先考虑最简单的一种形式，即节点特征与其所有邻居节点有关，因此将邻接矩阵A与特征H直接相乘，该公式的含义与传统卷积相似，将每个节点的邻居节点的特征进行相加，当通过多个隐藏层后，就获得了多层邻居的信息。

但是，该形式有明显的缺点，首先是邻接矩阵A中不包含自身的信息，因此该公式将会忽略节点自身的影响，其次是对于邻接矩阵A而言，没有进行正则化，因此邻居节点更多的节点所造成的影响力会明显大于邻居节点少的点。

针对第一个没有包含自身信息的问题，可以将邻接矩阵A用拉普拉斯矩阵L进行替代，这样节点自身也被涵括进来了。使用拉普拉斯矩阵的原因大致有以下几点：(1)拉普拉斯矩阵是一个对称矩阵，可以对其进行特征分解；(2)拉普拉斯矩阵除了一阶邻居有非零元素外，主对角线也为非零元素，涵括进了节点自身信息；(3)拉普拉斯矩阵可以和拉普拉斯算子进行对应。

针对第二个正则化问题，我们就需要对拉普拉斯矩阵再进行一次处理，即得到对称规范化拉普拉斯矩阵（Symmetric normalized Laplacian）。该矩阵表示为：

因此解决上述两个问题之后，图卷积的公式可以表示为：

基于空间域的图卷积

对于基于空间域的图卷积而言，它的思想与传统CNN更为相似。对于传统CNN而言，每个像素与附近的像素直接相连，如果用一个3×3窗口取块，每个节点的邻居节点就是其周围的八个像素，将滤波器作用于3×3块，则每个中心像素的值就是3×3块内像素的加权平均值。因此推广到一般图结构中，中心结点的表示也是根据其邻居结点的聚合结果进行表示的。

基于空间域的图卷积目前有多种模型存在，我们将对几个经典模型进行讲解：

1、Neural Network for Graphs (NN4G)：

NN4G模型是第一个基于空间域的GCN模型，它通过直接累加节点的邻域信息来实现图卷积，因此该模型每层网络表示为：

2、Diffusion Graph Convolution(DGC)：

扩散神经网络将图卷积看作一个扩散过程，它假设信息以一定的概率从一个节点转移到其相邻的一个节点，在几轮之后各节点的信息将达到一个平衡状态。该模型的定义可以表示为：

其中概率转移矩阵，对概率转移矩阵做幂运算意味着越远的节点所提供的信息越少。

3、Graph Attention Network (GAT)：

图注意网络GAT在ICLR 2018上被提出。它假设相邻节点对中心节点的贡献是不同的，也不像常规图卷积那样可以预先确定。它结合了注意力机制，在聚合节点邻居信息时确定每个邻居节点对中心节点的重要性，即不同节点的权重。该模型公式可以表示为：

其中表示节点v与它的邻居节点u之间的权重，可以通过以下公式计算得到:

图注意力网络GAT通过端到端的神经网络结构隐式地捕获节点的权重，以便影响更大的节点有更大的权重。

频谱图卷积和空间域图卷积对比

1、效率

基于频谱方法的计算量会随着图的大小急剧增加，因为模型需要同时计算特征向量。基于空间的图方法由于直接对图的邻居节点进行聚合，所以有潜力处理大图。

2、通用性

基于频谱的图卷积结构是固定的，增删节点或边线都会导致训练好的模型失效，因为图结构变化后，拉普拉斯矩阵，度矩阵和邻接矩阵等都会随之变化。

3、灵活性

基于频谱的方法不适用于有向图，因为有向图没有明确意义上的拉普拉斯矩阵。