图卷积神经网络初探

你吃过牛角甜甜圈吗（cronuts）？

这一被时代杂志称为“2013年25个最佳发明之一”的神奇美食，带着甜甜圈的可爱外貌与牛角面包的酥软内里，从美国纽约席卷全球。直到今天，世界各地的甜品店依然热衷于开发各种口味的cronuts，引得饕餮们纷纷自掏腰包。

再看一眼圆圆胖胖的cronuts，各位擦擦口水回到正题，接下来，本文将介绍近年来引爆学术界的另一样“牛角甜甜圈”：

Graph Convolutional Network——图卷积神经网络，顾名思义，它是图与卷积神经网络（CNN）的结合体。

CNN在图像识别、NLP等领域拥有广泛的应用场景，技术日臻成熟，常用于分类、识别等任务。通过将数据映射到低维的欧式空间，可以有效地采用CNN进行运算。图像中的像素点具有明确的上下左右位置关系，语句中的文字具有清晰的序列结构，均可转换为低维的欧几里得结构化数据，输入到神经网络中进行特征提取和计算。

常规卷积操作与图数据结构

图作为一种通用的数据结构，可以用来刻画现实世界中的很多问题，例如社交场景的用户网络、电商场景的用户和商品网络、电信场景的通信网络、金融场景的交易网络和医疗场景的药物分子网络等等。相比文本、语音和图像领域等易处理成欧式空间的数据而言，非欧空间的图数据（如上右图），无序才是常态。虽然可以用邻接矩阵、度矩阵等来表示图的结构信息，或者节点的特征矩阵等来表示图的属性信息，但如何将二者结合以产生高效的低维空间映射，成为当前图结构数据与CNN之间难以逾越的鸿沟。反过来说，解决这个问题，就架起了图与CNN连通的桥梁。

作为CNN的灵魂人物，卷积层承担了特征提取的任务。想要建立GCN，必须要面对来自灵魂的拷问：图结构数据上的卷积是什么？怎么求？

本文无意列举许多关于卷积定义的数学公式，简而言之，卷积运算的实质是加权求和和参数共享。如下GCN流程图所示，从图结构数据到神经网络，卷积操作必不可少，但在图结构中无法运用常规的卷积操作形成Feature Map，需要“特殊设计”。

GCN流程图

来自论文：

、Defferrard M, Bresson X, Vandergheynst P. Convolutional neural networks on graphs with fast localized spectral filtering[C]//Advances in neural information processing systems. 2016: 3844-3852.

当前的图卷积操作方式分成两类：谱域（Spectral Domain）和空域（Spatial Domain/Vertex Domain）。

基于谱的方法利用图的Laplacian矩阵的特征向量和特征值，经过一系列的特征分解、近似和归一化（同样不想贴公式），最终形成特征在不同层之间的传播公式：

来自论文：Kipf T N, Welling M. Semi-supervised classification with graph convolutional networks[J]. arXiv preprint arXiv:1609.02907, 2016.

如上的公式将图的结构信息（ ）作为卷积核，与特征信息（H）矩阵做卷积操作，实现了图结构数据到欧式空间数据的转换。但这种基于谱的方法有一个缺陷：产生的模型不可移植。由于卷积核是整图的邻接矩阵和度矩阵转换产生，一旦图的结构发生变化，模型需要重新训练。

为了解决这个问题，一批基于Spatial Domain/Vertex Domain的GCN算法被研发出来，例如大名鼎鼎的GraphSage、首次应用于工业生产的PinSage，以及GAT、FastGCN等等。这些GCN们网络结构多样，采样方式繁多，但都有一个共同的特点：利用节点的邻域进行特征的卷积操作，换言之，特征加权求和。

公式为GraphSage中提出的通用特征提取框架，它不再以传统GCN中显式的作为卷积核，而是采用邻域采样方法+Aggregator模拟卷积操作。常用的邻域采样方法有随机选择、random walk、概率分布等，Aggregator则可以为Mean、Pooling、LSTM等。在这个框架下，通过变换采样方法和Aggregator，就可以得到一种新型的GCN，非常有利于开发新算法。最重要的是，它仅仅利用图的局部结构信息，可被图的不同区域、甚至是不同图共享。

由于基于Spatial Domain的GCN们，拥有计算代价小、可移植、泛化能力强等特点，在工业级生产过程中，具有广泛的应用前景。

以上，是笔者目前了解到的两种主要的图卷积操作方法，它们成功将图数据与CNN连接起来，造就了新的AI神器GCN。不知在你眼中，GCN这种“牛角甜甜圈”究竟是拥有牛角面包內馅的甜甜圈，还是长着甜甜圈外表的牛角面包呢？