ICLR 2017 | GCN：基于图卷积网络的半监督分类

题目：Semi-Supervised Classification with Graph Convolutional Networks

会议：International Conference on Learning Representations, 2017

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

阅读前建议先读一下前面几篇关于GNN的入门文章：

• 图神经网络（GNN）的基本原理
• 图解GNN | A Gentle Introduction to GNN
• TNNLS | GNN综述：A Comprehensive Survey on Graph Neural Networks

在TNNLS | GNN综述：A Comprehensive Survey on Graph Neural Networks一文中对GCN进行了大概的讲解，讲解如下（这部分不感兴趣可以跳过）：

RecGNN使用相同的图循环层(Grec)来更新节点的表示，而ConvGNN使用不同的图卷积层(Gconv)来更新节点表示。

ConvGNN分为两种：基于频域的和基于空间域的。其中基于频域的方法通过从图信号处理的角度引入过滤器（卷积核的集合）来定义图卷积，其中图卷积运算被解释为从图信号中去除噪声。基于空间域的ConvGNN继承了RecGNN的思想，通过消息传递来定义图卷积运算。

A. 基于频域的ConvGNN

基于频域的ConvGNN：假设图是无向的。无向图的归一化图拉普拉斯矩阵定义为：

其中

是一个对角阵，对角上的元素表示对应节点的度。归一化图拉普拉斯矩阵具有实对称半正定的性质，因此可以被分解为：

其中

是特征值排序的特征向量矩阵，

是特征值对角矩阵，线代基础知识了。归一化图拉普拉斯矩阵的特征向量形成正交空间，即

。

对图进行处理时，

表示为所有节点的特征向量，

为第

个节点的特征向量。

的图傅里叶变换为：

，逆图傅里叶变换为：

，其中

表示傅里叶变换的结果信号。

由以上定义可知，图傅里叶变换将输入图信号投影到标准化空间，其中空间基由标准化图拉普拉斯算子的特征向量形成。原始输入信号可以被表示为：

（逆图傅里叶变换）。

有了以上定义后，输入信号与过滤器

间的卷积运算被定义为：

如果将过滤器表示为：

，则图卷积可以简化为：

基于频域的ConvGNN都遵循以上定义，只是过滤器可能有所不同。

Spectral CNN假设过滤器

是一组可学习的参数，Spectral CNN的图卷积层定义为：

其中

是层索引，

是输入图信号，

，

为输入通道数，

为输出通道数。

其他的一些基于频域的ConvGNN，如ChebNet、CayleyNet和AGCN等，这里就不再详细介绍了。

B. 基于空间域的ConvGNN

基于空间域的ConvGNN：基于节点的空间关系来定义图卷积。

Image可以被视为Graph的特殊形式，每个像素代表一个节点，每个像素直接连接到其附近的像素：

对于3x3窗口，每个节点的邻域就是其周围8个像素点。类似地，基于空间域的图卷积将中心节点的表示与相邻节点的表示进行卷积，得到中心节点的更新表示。

图的神经网络（NN4G）是基于空间域的ConvGNN的第一个工作，它通过直接汇总节点的邻域信息来执行图卷积，NN4G导出的下一层的节点状态公式为：

是激活函数，

初始化为零向量。上式的矩阵形式为：

扩散CNN (DCNN)认为图的卷积是一个扩散过程。它假设信息以一定的转移概率从一个节点转移到它的一个相邻节点，使信息分布在几轮后达到均衡。DCNN将扩散图卷积定义为：

其中

是激活函数，概率转移矩阵

。由于扩散的平稳分布是概率转移矩阵幂级数的总和，因此DGC可以定义如下：

这里

。需要注意的是，这里使用了概率转移矩阵的幂，这意味着远处的邻居对中心节点更新的贡献很少。

PGC-DGCNN基于最短路径增加了远处邻居的贡献。PGC-DGCNN定义了最短路径邻接矩阵

：如果节点

到结节点

的最短路径长度为

，则

，否则为0。PGC-DGCNN中的图卷积运算定义如下：

式中

，

，

表示向量的连接。

其他的一些变种不再详细了解了。

本篇文章提出的GCN是基于空间域的ConvGNN。

1. 引言

考虑在图中对节点进行分类：图中只有少数节点被标记，我们的任务是预测未标记节点的标签，这种问题就是图的半监督分类。

解决上述问题比较经典的方法：

其中

表示标记数据上的误差，

可以是神经网络，

是节点特征向量矩阵，

是未归一化的图拉普拉斯矩阵，

为度矩阵，

为邻接矩阵，

为节点的编码表示。

上式中加上正则化项后，如果两个节点邻接（

），那么我们会认为它们可能共享同一标签。这种假设会限制模型的表达能力，因为图中的边不一定需要编码节点相似性，也可能是其它信息。

2. GCN

传统的图卷积：

可以发现，节点的状态向量在通过每一层图卷积进行传播时，都乘上了邻接矩阵

，也就是说节点在更新自己状态向量的同时考虑了邻接节点的信息，但并没有考虑到自身的信息，这是因为

的对角线为0（除非节点存在自环）。

本文提出的图卷积传播规则：

其中

，即邻接矩阵在原有基础上加上一个单位矩阵，也即每一个节点都增加一条指向自己的边；

为加上自环后的度矩阵；

为层权重矩阵；

为激活函数，比如ReLU；

，也就是节点特征矩阵；经过多层卷积后，我们得到了最终的

，

即GCN学到的节点的状态向量表示。

可以发现，本文在传统图卷积的基础上做了两点创新：

1.

。每个节点强行加上自环，这样节点的状态向量在向前传播过程中就能考虑到自身的特征信息。

2. 对加上自环后的邻接矩阵

进行了归一化：

。归一化后的邻接矩阵每一行的和都为1。

3. 半监督节点分类

有了上述图卷积的传播规则后，半监督节点分类就变得很简单了。比如说我们要分为两类，那么只需要在GCN后加上一个输出为2的全连接层，然后再经过一个Softmax即可。得到输出后再算出交叉熵损失，然后反向传播更新每一层GCN的参数

。

比如考虑只有一个隐藏层的简单模型：

其中

，即加上自环然后进行归一化后得到的邻接矩阵；

为从输入到隐藏层的权重矩阵；

为隐藏层到输出层的权重矩阵。

简单来说，我们有：

然后我们有交叉熵损失：

其中

为有label的节点索引集。

然后损失函数对神经网络参数

和

求导，梯度下降更新参数，更新后再进行新一轮的传播。

等训练了一定轮数后，我们就可以利用得到的模型对未标记的节点标签的类别进行预测了。

4. 实验

数据集

实验设置：测试集大小为1000个节点，网络采用第三节中提出的双层GCN模型：

Baseline：标签传播(LP)、半监督嵌入(SemiEmb)、流形正则化(ManiReg)以及DeepWalk。

实验结果

可以发现，GCN的效果是最好的！