论文阅读总结（SEMI-SUPERVIED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS）

Semi-Supervised Classification with Graph Convolutional Networks（基于图卷积神经网络的半监督分类）

这篇文章是阿姆斯特丹大学的教授Max Welling和博士Thomas N.Kipf于2017年在深度学习顶会ICLR上发表的，至写此篇博客时，在谷歌学术上显示论文被引用数已经到达2136次。
作为一个新手，拜读大牛的论文后想要写一写自己的总结（只有我被通篇文章看不懂的数学虐得不行吗?（哭…）），本人菜鸟，有什么理解不正确的地方请大佬们指正。

论文：Semi-Supervised Classification with Graph Convolutional Networks

摘要部分：
作者提出了一种基于图（图论意义上的图）的可扩展的半监督学习方法。通过谱图卷积的局部一阶近似来确定卷积网络结构选择，并在引文网络，知识谱图等许多数据集中体现了较明显的优势。
tips：
（1）半监督分类
半监督学习(Semi-Supervised Learning）是监督学习与无监督学习相结合的一种学习方法。半监督学习使用大量的未标记数据，以及同时使用标记数据，来进行相关工作。在无类标签的样例的帮助下训练有类标签的样本。
（2）为什么要引入图结构模型
本来印象中的深度学习都是广泛地用CNN，RNN这类模型，但是CV，NLP处理的问题都是可以由矩阵结构表示的数据，但是对于非矩阵结构的Graph（如现实生活中常见的社交网络，引文网络等），CNN则束手无策了，其平移不变性不再适用，为了在Graph结构上提取特征进行学习并引入可优化卷积参数，作者在本文提出了GCN模型。

本篇博客的结构：
一. INTRODUCTION
二.Graph上的快速近似卷积思路
三. 半监督方式的节点聚类
四.模型局限及作者展望
五.总结

(以下Graph均指图论意义上的图)

一. INTRODUCTION
对于Graph中的节点半监督学习分类问题，前人在处理该问题时借助基于图的正则化形式将标签信息与图结构数据平滑的结合，在代价函数中加入Graph-based的拉普拉斯正则项

f(*)是神经网络的可微分梯度函数，λ是某权值系数，A是邻接矩阵，▲=D-A是未正则化的图上拉普拉斯算子（拉普拉斯矩阵），D是其度矩阵，A是其邻接矩阵。但是上述存在一个限制性的假设：相连节点存在相似的特征标签。 这些假设可能会影响到模型的性能。

拉普拉斯算子简述：
机器学习–拉普拉斯算子（Laplace Operator）学习整理

二. Graph上的快速近似卷积思路
作者提出频谱图上的一阶近似卷积。

其中：
（1）A~（带自环的邻接矩阵）=A+IN（A为邻接阶矩阵，IN为自环）；
（2）σ(*)为**函数；
（3）H(l)为第l层的**矩阵；H(0)=X；
（4）W(l)为可训练权重

作者的方法是在频谱图卷积下进行改进的：
在谱域下进行傅里叶变换及卷积。
通俗理解，图谱是将信号 / 音频 / 图像 / 图分解成简单元素 (微波、图) 的组合。
输入x与经过傅里叶域参数化的filter：gθ=diag（θ）进行相乘：

U是归一化Graph拉普拉斯算子L的特征向量的矩阵，Λ是它的特征值对角矩阵，UTx是x的图形傅里叶变换。
但是这种方式运算量很大O（n^2)，然后又有大牛提出用切比雪夫多项式的k阶截断展开式来逼近：

其中：Λ~=2Λ/λmax​−IN，λmax​是L的最大特征值​，θ’是切比雪夫系数的向量。
经过切比雪夫多项式的递归定义代入式子后，式子变为：

这个表达式变成了K的范围内。gθ约等于拉普拉斯算子中的一个K阶多项式，运算便只和卷积位置的节点的K steps范围内的点有关了，计算复杂度大大降低，变成了O(|ε|)。

上述部分都是前人的研究结果。

作者基于上述部分提出层级线性模型，分层卷积操作限制为K=1，然后主要的改进为设置λmax​≈2，这样对于中心节点进行一次卷积时，仅利用中心节点最近的节点，对上一层的卷积可扩展至下一层。
然后模型就变成：

然后，由于限制参数数量可以进一步解决过拟合问题并将各层的运算量最小化，作者进一步将θ’0和-θ’1都等价于θ，式子化简为：

计算的特征值都处于[0,2]之间，但是，当在深度神经网络模型中使用该运算时，不断地进行网络层叠加操作，反复使用该运算方法可能会导致数值不稳定性以及爆炸或消失梯度问题。这样，作者又适用了一个技巧性的归一化操作：

将该定义使用到具有C个输入通道（每个节点的C维特征向量）的X和F个filter，得到特征映射式子：

Z是卷积操作后得到的输出矩阵，卷积操作时间复杂度为

三. 半监督方式的节点聚类
作者弃用了传统的假设：Graph中相邻节点具有相似的特征标签。整体的模型是用于半监督学习的多层GCN网络。

（1）预处理及模型
作者首先计算了：

这使得模型式子更加简洁：

（2）交叉熵损失

其中YL是有标签的节点的集合。

（3）训练：
Tensorflow GPU环境：
作者使用每次训练迭代的完整数据集执行批量梯度下降，这是可行的选择，只要数据集适合内存即可。使用了A的稀疏矩阵表示，内存需求为O（| E |），即边数，为线性需求。同时，作者还借鉴了resnet中的经典dropout方法（随机舍弃网络中的神经元）引入到自己的模型中。

（4）数据集：
三个引文网络，一个知识谱图。

（5）模型参数：
两层的GCN网络，dropout率，L2正则化因子等
对不同的数据集参数有些差别：

（6）实验结果：

总体上，本文的模型均优于前人（仅两层GCN！)，同时注意到NELL数据集的accuracy远低于其他。

每个epoch的训练时间：
可以看出时间性能优良，但是当10M时CPU训练已经内存超限。

四.模型局限及作者展望
模型还存在的局限：
（1）存储空间的需求
如上述epoch的10M时的边数据CPU已经无法训练，作者的实现是基于全批次梯度下降，内存需求随着数据集大小线性增长。若要使用小批量的随机梯度下降的话，需要考虑GCN的层数，及节点的K邻域必须存储进去。
（2）不能处理有向图特征
本文GCN模型只适用于无向图。同时作者提出对于NELL数据集的一个有趣的现象，对于知识谱图，可以将有向图转化为无向二分图进行操作。
（3）前提假设同样存在局限
作者假设子环和边连的邻接结点的重要性同等，同时，作者认为对于某些数据集中引入一个权衡参数可能较有利。

五.总结
作者在本篇论文中介绍了一种基于graph结构的频谱卷积，采用一阶近似卷积（WL-1算法的一阶近似改进）的方式提出GCN模型，同时从结果可以看出仅两层的GCN就已经比深度训练的模型在Graph上有着更优的accuracy了。

最后，推荐几篇好博客：
首先，肯定是作者自己的博客啦，作者在自己的博客中也清楚的介绍了模型的思路，同时，通过空手道俱乐部的例子，能更直观的感受到GCN的强大。
https://tkipf.github.io/graph-convolutional-networks/

然后是学习的时候看到的几篇写得很好的博客：
（1）https://blog.****.net/yuzhijiedingzhe/article/details/78895464
（2）https://blog.****.net/u013263329/article/details/77587078
（3）https://blog.****.net/qq_41727666/article/details/84640549

博客有什么错误欢迎各位大佬指正！