转载
目录
大纲
1. 问题定义
2. 图上的快速卷积近似
谱图卷积
逐层线性模型
3. 半监督学习节点分类
传播公式解释
后话
参考文献
本文为GNN教程的第二篇文章 【GCN介绍】，取自Kipf et al. 2017，文章中提出的模型叫Graph Convolutional Network(GCN)，个人认为可以看作是图神经网络的“开山之作”，因为GCN利用了近似的技巧推导出了一个简单而高效的模型，使得图像处理中的卷积操作能够简单得被用到图结构数据处理中来，后面各种图神经网络层出不穷，或多或少都受到这篇文章的启发。
大纲
考虑图（例如引文网络）中节点（例如文档）的分类问题，假设该图中只有一小部分节点标签（label）是已知的，我们的分类任务是想通过这部分已知标签的节点和图的结构来推断另一部分未知标签的节点的标签。这类问题可以划分到基于图结构数据的半监督学习问题中。半监督学习（semi-supervised learning）是有监督学习的一个分支，主要研究的是如何利用少量的有标签数据学习大量无标签数据的标签。
为了对节点进行分类，首先我们可以利用节点自身的特征信息，除此之外，我们还可以利用图结构信息，因此一个典型的图半监督学习问题可以对两个损失函数一起优化：
显然，这样的学习策略基于图中的相邻节点标签可能相同的假设（因为损失函数要求相邻节点的特征向量尽量相似，如何他们的标签不相似的话，那么不能学习到一个从特征向量到标签的有效映射）。然而，这个假设可能会限制模型的能力，因为图的边在语义上不一定代表所连接节点相似。还有一种可能是图中有大量的噪声边。
因此，在这个工作中，作者不再显示的定义图结构信息的损失函数 , 而是使用神经网络模型直接对图结构进行编码，训练所有带标签的结点，来避免损失函数中的正则化项。
这篇文章的主要贡献是为图半监督分类任务设计了一个简单并且效果好的神经网络模型，且这个模型由谱图卷积(spectral graph convolution)的一阶近似推导而来，具有理论基础。
2. 图上的快速卷积近似这一节介绍如何从谱图卷积推导出GCN的逐层更新模型，涉及到一些谱图理论的知识，可以安全的跳过这一节，后面我们会为谱图卷积专门出一个专栏的文章，将详细讨论它们。
这一节主要介绍图卷积网络GCN逐层更新(propagation)的理论推导。多层图卷积网络(Graph Convolutional Network, GCN)的逐层传播公式：
现在假设我们限制，即谱图卷积近似为一个关于的线性函数。这种情况下，我们仍能通过堆叠多层来得到卷积的能力，但是这时候，我们不再受限于切比雪夫多项式参数的限制。我们期望这样的模型能够缓解当图中节点度分布差异较大时对局部结构过拟合问题，比如社交网络，引文网络，知识图谱等。另一方面，从计算的角度考虑，逐层线性模型使我们可以构建更深的模型。
这个形象的解释对理解GNN非常重要，希望大家能仔细想一下是不是懂了。
例子
实现时，由于GCN需要输入整个邻接矩阵和特征矩阵, 因此它是非常耗内存的，论文中作者做了优化，他们将作为稀疏矩阵输入，然后通过实现稀疏矩阵和稠密矩阵相乘的GPU算子来加速计算，然而，即使这样，整个矩阵仍然存在这要被塞进内存和显存中的问题，当图规模变大的时候，这种方法是不可取的，在下一篇GraphSAGE的博文中，我们将会介绍如何巧妙的克服这样的问题。
参考文献[1] Semi-Supervised Classification with Graph Convolutional Networks
[2]谱域理解以及GCN公式发展演变
核心
