图1. 图卷积神经网络基本结构
卷积神经网络(Convolutional Neural Network, CNN)已经许多现实任务场景中取得了显著的成绩。他可以十分高效的提取出视觉信号中的特征信息，进而加以应用及处理。然而，并不是所有重要的现实数据都是以视觉信号或而二维或三维信息的方式呈现的，比如社交网络，知识图，蛋白质交互网络，万维网等数据会以网络或其他拓扑结构的方式呈现，传统的神经网络无法很好的为这一类型的数据提供很好的处理方法。
在图卷积网络(Graph Convolutional Network, GCN)提出之前，对于图或者网络类型数据的处理方式大多是基于核的方法、基于图论的正则化方法等。图卷积网络的提出为这一问题提供了另一种解决方案，并在许多基准图数据集上都取得了最佳结果。
目前，大多数图卷积网络的基本架构都是相似的（图1）。对于图G=(V, E), 需要两种输入数据来学习一个模型（函数）来提取其特征／信号。
- 特征矩阵X。对于每一个结点的自身特征建立的矩阵，这里的特征可以指结点本身或编码过后数据，维数为D。若有N个结点，特征矩阵X的大小为N*D。
- 图结构代表性描述矩阵。通常用邻接矩阵A来表示。
图卷积网络的输出是一个N*F的矩阵Z，这里F表示每个节点的输出特征维数。
和普通神经网络一样，图卷积网络的每一层可用如下非线性函数来表示：
H^{(l+1)}=f(H^{(l)},A)
l代表层数，H^(l)代表上一层的输出。图卷积网络最大不同体现在f函数如何设计和实现的。对于最简单的模型结构，可以考虑如下函数：
f(H^{(l)},A)=\sigma(AH^{(l)}W^{(l)}))
W^(l)是l层的参数矩阵。这里将邻接矩阵和特征矩阵进行加权运算，代表某节点和其所相连的所有结点的特征进行了加权运算，并通过非线性变换得到这一层的输出。
然而，此模型存在一些问题：
- 若结点没有和自身相连，上述模型没有考虑结点自身的特征关系。然而在提取特征时，这一信息很重要。
- 邻接矩阵A没有正则化，若两结点的度差距很大则会改变输出的尺度。
对于第一个问题，可以将A与一单位矩阵相加。
对于第二个问题，可以用度矩阵D（对角线为该结点的度）进行如下正则化操作：
D^{-\frac{1}{2}}AD^{-\frac{1}{2}}
综合以上两点，一个比较鲁棒的图卷积模型基本架构可以表示如下：
f(H^{(l)},A)=\sigma(\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}H^{(l)}W^{(l)}))
上式种\hat{A}为加了单位矩阵的邻接矩阵，\hat{D}为其度矩阵。
描述和图片来源：
- Thomas Kipf. (2016) URL: https://tkipf.github.io/graph-convolutional-networks/
发展历史
描述
在CNN兴起之后，人们的视线逐步转向利用神经网络结构处理更多类型的数据。
- 2014年，Bruna等人第一次发表ICLR文章“Spectral Networks and Locally Connected Networks on Graphs”开始关注利用神经网络处理任何结构图的问题，并在小数据集上取得了十分具有启发性的结果。
- 2015年，Henaff等人的NIPS论文“Deep Convolutional Networks on Graph-Structured Data”在更大的Imagenet数据集上进行试验验证了模型的有效性，并将其应用扩展到无监督领域。
- 2016年，Defferrard的NIPS论文“Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering”在引入切比雪夫多项式，提出Chebynet，并将计算复杂度降低到线性，得到了近似平滑的滤波器，并在MNIST数据集上取得了最好结果。
- 2017年，Kipf等人的ICLR文章“Semi-supervised Classification with Graph Convolutional Networks”对Chebynet进行了简化，并结合卷积神经网络提出了一种十分有效的图半监督学习方法。
- 2018年，朱军等人的ICML论文“Stochastic Training of Graph Convolutional Networks with Variance Reduction”，提出control variate based algorithms，使得图卷积网络的训练复杂度大大降低。
主要事件
| 年份 | 事件 | 相关论文/Reference |
| 2014 | 尝试使用神经网络解决图问题 | Bruna, J., Zaremba, W., Szlam, A., & LeCun, Y. (2013). Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203. |
| 2015 | 将图神经网络应用于大数据集和更多任务中 | Henaff, M., Bruna, J., & LeCun, Y. (2015). Deep convolutional networks on graph-structured data. arXiv preprint arXiv:1506.05163. |
| 2016 | 提出更高效的图卷积网络 | Defferrard, M., Bresson, X., & Vandergheynst, P. (2016). Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems (pp. 3844-3852). |
| 2017 | 提出基于图卷积神经网络的图半监督学习方法 | Kipf, T. N., & Welling, M. (2016). Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907. |
| 2018 | 大大降低图卷积网络的训练复杂度 | Chen, J., Zhu, J., & Song, L. (2018, July). Stochastic Training of Graph Convolutional Networks with Variance Reduction. In ICML (pp. 941-949). |
发展分析
瓶颈
虽然图卷积网络可以在图结构网络中提取出更有效的信息，但现阶段仍存在一些问题。比如递归、控制流、条件迭代等概念没发用图的形式表示，但在某些场景下这些信息却是实际存在的。此外，图结构数据集并不像图像、文字等数据集容易采集整理，这也限制了图神经网络的进一步发展。
未来发展方向
- 对于模型本身，图神经网络结构可能仍会发生十分本质的改变。比如，现阶段模型在训练过程中无法改变图的自身结构，然而某些应用场景中图内结点间的关联信息或许是随训练过程而改变的。此外，引入更多其他的信号也许会使模型更加高效。
- 在数据集方面，更好的利用现有数据集或采集更多的该类型数据或许会为图模型的发展增添动力。
Contributor: Yujia Chen