论文标题：Semi-Supervised Classification with Graph Convolutional Networks

论文链接：https://arxiv.org/abs/1609.02907

论文来源：ICLR 2017

之前的文章：

①傅里叶级数与傅里叶变换

②图神经网络中的谱图理论基础

③第一代图卷积网络：图的频域网络与深度局部连接网络

④第二代图卷积网络：应用快速局部谱卷积的图卷积网络

一、概述

考虑分类图中节点这样一个问题，每个节点可以是一篇文章，那么图可以代表引用关系，并且只有一部分节点有标签。这样的问题就是一个基于图的半监督学习问题。解决这个问题的一种方法是为损失函数添加一个基于图的正则项，比如采用图的拉普拉斯矩阵正则项：

上式之所以能够采用这样的损失函数是基于这样的假设：在图中相邻的节点更倾向于拥有相同的标签。然而这个假设可能会限制模型的容量，因为图的边不一定需要编码节点相似度，但可能包含额外的信息。

本文主要内容包括三部分：

①网络的架构，也就是设计的卷积层是如何前向传播的，以及它如何从前两代GCN中获得启发并对其进行改进；

②如何利用设计的GCN解决前述半监督问题；

③通过实验来证明本文设计的模型是有效且高效的。

二、图上的快速近似卷积

在本文中所设计的GCN的卷积层结构如下：

1. 谱卷积核

2. 第三代谱卷积核

上面介绍了前两代谱卷积核，本节介绍如何由第二代谱卷积核进行改进从而得到本文所设计的第三代谱卷积核。对于第二代卷积核，首先我们设置，那么现在有：

上式和 ，也仍然可以通过堆叠多层来使得模型具备足够的容量和复杂度，而且本文认为这样设置还可以缓解社交网络、引文网络、知识图谱或者其他真实世界的这种大规模图的局部邻域的过拟合问题。另外，这样的设计也能够允许我们构建更深的深度网络。

接着，本文近似使用 ，本文认为在训练过程中神经网络可以适应这种假设，那么现在，卷积的过程就变成：

一共有两个参数 。连续应用这种卷积层也可以达到卷积图的 阶邻域的效果，这是由于每次卷积 阶邻域内的节点信息都会流向当前节点，这里的 代表连续的卷积操作数或者卷积的层数。

接下来进一步限制参数的数量以解决过拟合和最小化每层的操作(如矩阵乘法)的数量，具体的，限制 ，现在卷积的过程就变成：

现在的特征之间。在深度神经网络中重复应用上述过程会造成数值不稳定以及梯度爆炸或梯度消失，为了缓解这个问题，本文采用再标准化（renormalization）技巧：

三、半监督节点分类

正如之前所说的，对于半监督分类问题，由于我们将数据 和邻接矩阵 同时作为模型 的输入条件，因而我们可以放宽某些典型的基于图的半监督学习的假设。我们期待这种方法在邻接矩阵包含 种没有的信息时能够是powerful的，解释一下这一点就是说传统的基于图的半监督学习（正如开篇介绍的）要求图的邻接矩阵表征节点的相似度，而节点的相似度信息是利用 计算得到的，也就是说 本身就包含相似度信息，这就造成了重复和浪费，而使用本文的模型后，邻接矩阵就可以用来表征一些其他

信息（比如文章的引用关系或者知识图谱中的关系），相当于将邻接矩阵解放了出来。

对于模型的具体架构，使用一个两个卷积层的神经网络作为例子。在预处理阶段首先计算 ，然后模型架构可以表示为：

                                                       架构图

在实验中采用batch gradient descent对整个数据集进行迭代。对于稀疏矩阵 ，需要的内存复杂度为 。随机性通过dropout引入。对于mini-batch stochastic gradient descent的方法需要后续进行研究。

四、实验

实验数据集信息如下：

                                                数据集信息

实验结果如下：

                                                 实验结果

具体实验设置请参照原文。

多种架构对比：

                                           多种架构对比

训练时间与图边数的关系：

                                  训练时间与图边数的关系

五、模型的局限性

1. 内存的需求

采用batch gradient descent，内存需求与图边数成线性关系。而如果采用mini-batch，则需要考虑模型的层数，因为模型的层数代表了卷积的感受野，对于非常大且稠密连接的图，可能需要更进一步的近似。

2. 有向图和边的特征

本文提出的模型只适用于无向图模型。不过NELL数据集的结果表明，通过将原始有向图表示为无向二部图，并使用额外的节点表示原始图中的边，可以同时处理有向边和边的特征。

3. 有限的假设

前述模型的定义有两个假设：

①局部性假设，也就是 层对应 阶邻域的假设；

②自连接与相邻节点的边等同重要性，也就是

对于一些数据集，最好引入一个权衡参数：

这个权衡参数可以被学习。