一. 概括

图神经网络已经成为深度学习领域最炽手可热的方向之一。GCN具体思想的核心是通过拉普拉斯矩阵可以对图信息进行特征分解的特点把该公式定义为图卷积操作，同时图卷积的出现也填补了神经网络获取拓扑图类型特征的空白。
图谱理论简单的概括就是借助于图的拉普拉斯矩阵的特征值和特征向量来研究图的性质

GCN(Graph convolution Network)是Convets在图结构上的自然推广。卷积神经网络是采用局部感知区域、共享权值和空间域上的降采样，相对于位移、缩放和扭曲，具有稳定不变的特性，能够很好的提取图像的空间特征。图结构不具备图片的平移不变性，传统的卷积方式不适用于图结构。图中每个节点的邻域节点数目不一致，无法用同样尺寸的卷积核进行提取.

而GCN的本质就是提取图的结构特征，关键在于如何定义局部接受域(receptive field)，主要有两种方式：

1. Spatial Approach 空域方法 --- 如何定义局部感受域或者是邻居和节点的顺序 比如给节点的边指定方向

2. Spectral Approach  频域方法（谱方法）--- 通过图的拉普拉斯矩阵的特征值和特征向量对图结构进行处理。

 

二 图卷积理论基础

什么是拉普拉斯矩阵？为什么GCN要用拉普拉斯矩阵？

拉普拉斯变换后的矩阵是正定对称矩阵，可以进行特征分解（谱分解）。

对于图G=(V,E), 其Laplacian 矩阵的定义为L=D−A 

• L为拉普拉斯矩阵Laplacian matrix
• D为对角度矩阵Degree matrix，对角线上的元素是顶点的度，即该元素链接的元素的个数
• A为邻接矩阵 Adjacency matrix ,即表示任意两个顶点之间的邻接关系，邻接则为1，不邻接则为0

看图示例，Laplacian 矩阵的计算方法。

物理意义：这个矩阵描述图的拉普拉斯矩阵与图的性质之间的关系。拉普拉斯矩阵与图的性质满足L=D−A 这种矩阵关系，其中图G=(V,E)的性质，体现在图的邻接矩阵A和图的度矩阵D上。

在理解了这个的基础上，还有其他的几种拉普拉斯矩阵，上面这种拉普拉斯矩阵只是其中的一种。

通过上面的公式的物理意义，我们知道了，图的性质可以表示在拉普拉斯矩阵之中，即图的性质可以通过拉普拉斯矩阵体现出来。这样，我们将图的分析，可以变为对拉普拉斯矩阵的分析。

首次将深度学习里卷积操作引入图数据里的方法GCN是Thomas Kpif于2017年在论文Semi-supervised classification with graph convolutional networks提出的,在他的博客里对模型解释非常清楚。

对称归一化拉普拉斯算子

为何要归一化？

采用加法规则时，对于度大的节点特征越来越大，而对于度小的节点却相反，这可能导致网络训练过程中梯度爆炸或者消失的问题。

为什么GCN要用拉普拉斯矩阵？

拉普拉斯矩阵矩阵有很多良好的性质

(1)拉普拉斯矩阵是对称矩阵，可以进行特征分解（谱分解），这就和GCN的spectral domain对应上了

(2)拉普拉斯矩阵只在中心顶点和一阶相连的顶点上（1-hop neighbor）有非0元素，其余之处均为0

(3)通过拉普拉斯算子与拉普拉斯矩阵进行类比

 

三. GCN介绍

假设有一批图数据，其中有N个节点（node），每个节点都有自己的特征，我们设这些节点的特征组成一个N×D维的矩阵X，然后各个节点之间的关系也会形成一个N×N维的矩阵A，也称为邻接矩阵（adjacency matrix）。

X和A便是我们模型的输入。

GCN也是一个神经网络层，且仅仅是一个全连接层。（下图是一个2层的GCN例子）

它的层与层之间的传播方式是(网络的每一层结构)

其中，

（1）A波浪=A+I，I是单位矩阵；

（2）D波浪是A波浪的度矩阵（degree matrix）；

（3）H是每一层的特征，对于输入层的话，H0就是X；

（4）σ是非线性激活函数。

 

 

上图中的GCN输入一个图，通过若干层GCN每个node的特征从X变成了Z，但是，无论中间有多少层，node之间的连接关系，即A都是共享的。

就是说解决了上面说的不具备平移不变性问题。其思路是：借鉴CNN，将卷积分为三步：

（1）选定中心节点后，确定邻域：对每个节点选择固定个数的节点作为邻居；

（2）给邻域结点编号；

（3）参数共享：选择固定大小的窗口进行参数共享。

 

 

假设构造一个两层的GCN，激活函数分别采用ReLU和Softmax，则整体的正向传播的公式为：

例如，我们有一个多分类问题，有10个类，F 被设置为10。在第2层有了10个维度的向量后，我们将这些向量通过一个softmax函数进行预测。

最后，我们针对所有带标签的节点计算cross entropy损失函数:

就可以训练一个node classification的模型了。由于即使只有很少的node有标签也能训练，作者称他们的方法为半监督分类。当然也可以用这个方法去做graph classification、link prediction，只是把损失函数给变化一下即可。

所以利用GCN提取出的特征，我们可以实现节点分类（node classification）、图分类（graph classification）、边预测（link prediction），还可以得到图的嵌入表示（graph embedding）

 

四. GCN公式解释

作者给出了一个由简入繁的过程来解释：

我们的每一层GCN的输入都是邻接矩阵A和node的特征H，那么我们直接做一个内积，再乘一个参数矩阵W，然后激活一下，就相当于一个简单的神经网络层嘛，是不是也可以呢？

实验证明，即使就这么简单的神经网络层，就已经很强大了。这个简单模型应该大家都能理解吧，这就是正常的神经网络操作。

但是这个简单模型有几个局限性：

• 只使用A的话，由于A的对角线上都是0，所以在和特征矩阵H相乘的时候，只会计算一个node的所有邻居的特征的加权和，该node自己的特征却被忽略了。因此，我们可以做一个小小的改动，给A加上一个单位矩阵 I ，这样就让对角线元素变成1了。
• A是没有经过归一化的矩阵，这样与特征矩阵相乘会改变特征原本的分布，产生一些不可预测的问题。所以我们对A做一个标准化处理。首先让A的每一行加起来为1，我们可以乘以一个D的逆，D就是度矩阵。我们可以进一步把D的拆开与A相乘，得到一个对称且归一化的矩阵 

通过对上面两个局限的改进，我们便得到了最终的层特征传播公式：

公式中的与对称归一化拉普拉斯矩阵十分类似，而在谱图卷积的核心就是使用对称归一化拉普拉斯矩阵，这也是GCN的卷积叫法的来历。原论文中给出了完整的从谱卷积到GCN的一步步推导。

A(hat)其实它就是邻接矩阵A做的一个归一化。下面为了表达的方便，直接当做邻接矩阵来分析

 

A是n×n维，H是n×m维

A矩阵的第i行和H矩阵的第j列对应元素相乘在求和就得到Q矩阵的(i,j)个元素。 仔细看看图中高亮的那几个向量的内部：

GCN的这一步，跟GraphSAGE是一样的思想，都是把邻居的特征做一个聚合（aggregation）。

在GCN中，是直接把邻居的特征进行求和，而实际不是A跟H相乘，而是A帽子，A帽子是归一化的A，所以实际上我画的图中的邻居关系向量不应该是0,1构成的序列，而是归一化之后的结果，所以跟H的向量相乘之后，相当于是“求平均”。

 

 

 

 

五 从数学角度简单模拟GCN公司

从图G中，我们有一个邻接矩阵A和一个度矩阵D。同时我们也有特征矩阵X。

那么我们怎样才能从邻居节点处得到每一个节点的特征值呢？解决方法就在于A和X的相乘。

看看邻接矩阵的第一行，我们看到节点A与节点E之间有连接，得到的矩阵第一行就是与A相连接的E节点的特征向量（如下图）。同理，得到的矩阵的第二行是D和E的特征向量之和，通过这个方法，我们可以得到所有邻居节点的向量之和。

计算 "和向量矩阵 "AX的第一行。

这里还有一些需要改进的地方。

1. 我们忽略了节点本身的特征。例如，计算得到的矩阵的第一行也应该包含节点A的特征。
2. 我们不需要使用sum()函数，而是需要取平均值，甚至更好的邻居节点特征向量的加权平均值。那我们为什么不使用sum()函数呢？原因是在使用sum()函数时，度大的节点很可能会生成的大的v向量，而度低的节点往往会得到小的聚集向量，这可能会在以后造成梯度爆炸或梯度消失（例如，使用sigmoid时）此外，神经网络似乎对输入数据的规模很敏感。因此，我们需要对这些向量进行归一化，以摆脱可能出现的问题。

此时的计算还存在上局限（1）忽略了节点本身的特征。按理得到的矩阵第一行应该包含结点A和E的信息，所以做出改进：

通过给每个节点增加一个自循环，我们得到新的邻接矩阵

对于问题(2): 对于矩阵缩放，我们通常将矩阵乘以对角线矩阵。在当前的情况下，我们要取聚合特征的平均值，或者从数学角度上说，要根据节点度数对聚合向量矩阵X进行缩放。直觉告诉我们这里用来缩放的对角矩阵是和度矩阵D有关的东西.  现在的问题变成了我们要如何对和向量进行缩放/归一化？换句话说：

我们如何将邻居的信息传递给特定节点？我们从我们的老朋友average开始。在这种情况下，D的逆矩阵（即，）就会用起作用。基本上，D的逆矩阵中的每个元素都是对角矩阵D中相应项的倒数。

例如，节点A的度数为2，所以我们将节点A的聚合向量乘以1/2，而节点E的度数为5，我们应该将E的聚合向量乘以1/5，以此类推。

因此，通过D取反和X的乘法，我们可以取所有邻居节点的特征向量（包括自身节点）的平均值。

 

到目前为止一切都很好。但是你可能会问加权平均()怎么样？直觉上，如果我们对高低度的节点区别对待，应该会更好。

但我们只是按行缩放，但忽略了对应的列（虚线框）。

为列增加一个新的缩放器

新的缩放方法给我们提供了 "加权 "的平均值。我们在这里做的是给低度的节点加更多的权重，以减少高度节点的影响。这个加权平均的想法是，我们假设低度节点会对邻居节点产生更大的影响，而高度节点则会产生较低的影响，因为它们的影响力分散在太多的邻居节点上。

因为进行了两次归一化处理，左乘和右乘了D波浪的-1/2逆。

 

假设存在一个图

该矩阵不再是对角阵了，为了保持它是对角阵, 

这样既得到了近似的归一化也保持了矩阵对称性。（左乘是行变换，右乘是列变换。）
 

 

最后总结：

 

六. GCN的优缺点：

优点：

1.理论完善；

2.可以捕捉graph的全局信息；

缺点：

1.直推式(transducive)：无法直接泛化到新加入（未见过）的节点，为新节点产生embedding需要额外的操作；

2.输出的是节点唯一确定的embedding；

3.很难应用在超大图上：无论是拉普拉斯计算还是图卷积过程，因为GCN其需要对 整张图进行计算，所以计算量会随着节点数的增加而递增;

4.基础GCN是基于无向图的;

从图上的信息传递角度考虑，一次图卷积计算，就是一次全图计算，所以很容易想到，GCN难以应用到工业界；

 

代码参考：https://github.com/tkipf/pygcn