Kipf, T., & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. ArXiv, abs/1609.02907.

摘要：我们提出了一种在图结构数据上进行半监督学习的可扩展方法，这种方法是基于直接在图上操作的卷积神经网络的高效变体。我们通过谱图卷积的局部一阶近似来激励我们卷积架构的选择。我们的模型在图边数量上线性扩展，并学习隐藏层表示，对局部图结构和节点的特征进行编码。在对引文网络和知识图数据集的大量实验中，我们证明我们的方法以显著的优势优于相关方法。

1 介绍

考虑节点分类问题，如citation network，只有少部分节点的标签已知，这类问题可称为基于图的半监督学习。
在损失函数中使用图拉普拉斯正则项：

• 表示有标签的那部分的有监督损失
• 是神经网络的可导函数
• 是权重因子
• 是节点特征向量的矩阵
• 是个节点、边、邻接矩阵、度矩阵的无向图
• 上式假设图中相连的节点极有可能共享相同的标签，但是这可能会限制模型的性能

本文直接使用神经网络模型对图结构编码，对所有有标签的节点训练，从而避免了损失函数中明确的基于图的正则化。基于图的邻接矩阵的允许模型从有监督损失中分布梯度信息，从而能够在有与无标签的情况下学习节点表示。
两个方面的贡献：

• 我们为直接在图上操作的神经网络模型引入了一个简单且表现良好的层间传播规则，并展示了如何从谱图卷积的一阶近似来激励它；

• 我们展示了这种基于图的神经网络模型形式能够快速和可扩展地对图中节点进行半监督分类。在一些数据集上的实验表明，我们的模型与最先进的半监督学习方法相比，在分类的准确性和效率上都有很好的表现。

  2 Fast Approximate Convolutions on Graphs

  多层Graph Convolutional Network(GCN)的层间传播规则为：

• 无向图的邻接矩阵加上self-connections

• 是单位阵
• 和是具体层可训练的权重矩阵
• 是激活函数，如
• 是第层激活值矩阵，
  

  2.1 Spectral Graph Convolutions

  Fourier变换：
  其中，是标准化的图Laplacian的特征向量矩阵。
  可以将理解成的特征值的函数，即为。
  计算上式中的复杂度为，复杂度太高。另外，在大图中第一步骤就要计算的分解太昂贵了。为了解决这一问题，建议使用Chebyshev多项式来近似估计：
  ，其中，表示的最大特征值，是Chebyshev系数向量。
  Chebyshev多项式：
  ，由此得出，复杂度为。
  

  2.2 Layer-Wise Linear Model

  基于图卷积的神经网络模型可以基于堆叠多层卷积，每层紧跟着一个逐点非线性函数。现在假设限制逐层卷积操作，即关于的线性函数，因此这是一个基于图Laplacian spectrum的线性函数。