深度学习新星 | 图卷积神经网络（GCN）有多强大？

Original THOMAS KIPF 集智俱乐部 2018-12-21

带有一阶滤波器的多层图卷积神经网络

编译：集智翻译组
来源：THOMAS KIPF

综述

真实世界中，许多重要的数据集都是以图或者网络的形式存在的，比如社交网络，知识图谱，蛋白质相互作用网，世界贸易网等等。然而，迄今为止，却很少有人关注并且尝试将神经网络一般化后应用在这样的数据集上。

在过去几年里，有一些论文重新回顾了这个问题，尝试将神经网络一般化并应用在任意图结构数据中。

Bruna et al., ICLR 2014; Henaff et al., 2015; Duvenaud et al., NIPS 2015; Li et al., ICLR 2016; Defferrard et al., NIPS 2016; Kipf & Welling, ICLR 2017

其中一些工作在某些领域已经达到了非常好的效果，而这些领域之前主要是由核方法，图正则化等方法来解决的。

在这篇文章中，我将会对这个领域最近的发展做一个综述，并且指出多种方法模型的优缺点。本篇文章主要根据以下两篇论文进行讨论。

Kipf & Welling (ICLR 2017), Semi-Supervised Classification with Graph Convolutional Networks (disclaimer: I'm the first author)
Defferrard et al. (NIPS 2016), Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

另外有兴趣的还可以去Ferenc Huszar写的《How powerful are Graph Convolutions?》这篇文章进行讨论，文章里写了图卷积模型的限制。我对这篇文章也写了一个简短的评论。

文章地址：http://www.inference.vc/how-powerful-are-graph-convolutions-review-of-kipf-welling-2016-2/

内容梗概

图神经网络模型的简单介绍
谱图卷积和图卷积神经网络（GCN）
Demo：使用简单的一阶GCN模型进行图嵌入
GCN是WL算法的可微分一般化形式

如果你已经足够熟悉GCN模型，你可以直接跳到“空手道俱乐部网络的嵌入”这部分。

图卷积神经网络有多强大？

最近文献

一般化CNN、RNN这样的神经网络并且将它们应用在图结构数据上是一个很有挑战性的工作。最近有一些论文提出了针对特定问题的专用架构（比如，Duvenaud等, NIPS 2015; Li et等, ICLR 2016; Jain等, CVPR 2016），还有一些论文运用基于谱图理论的图卷积来定义参数化的滤波器（filter）（Bruna等, ICLR 2014; Henaff等, 2015），并将它们应用在我们熟知的经典多层CNN网络中。

另外最近更多的工作重点是结合速度快的启发式算法和速度慢但更合理的谱方法。Defferrard等人（NIPS 2016）使用带有自由参数的Chebyshev多项式在谱域中近似得到平滑的滤波器，其中参数可以通过一个类似神经网络的模型学习。他们在常用的数据集（MNIST）得到了令人信服的结果，和简单的2维CNN模型的结果非常接近。

在这篇（Kipf & Welling等，ICLR 2017）文章中，我们使用了一个相似的方法并且也是从谱图卷积的框架出发，并引入了一种简化方式（稍后介绍）既能明显加快训练时间又能得到更高的预测精度，在一些基准的图数据集上，达到了最好的效果。

GCN第一部分：定义

目前，大多数图神经网络模型都有一个通用的架构。我将它们称为图卷积神经网络（GCNs），这些模型是可卷积的，因为滤波器参数在图中所有位置或者一个局部位置上（ Duvenaud et al., NIPS 2015）都可以共享。

对于这些模型，它们的目标是要学习图G=（V，E）上的信号或特征的一个映射。它们的输入包括：

每一个节点i的特征描述xi，可以写成一个N*D的特征矩阵（N表示节点数，D表示输入的特征数）
矩阵形式的图结构的特征描述，通常是以邻接矩阵的形式（或者其他的形式）

模型会产生一个节点级别的输出Z（一个N*F的特征矩阵，其中F表示每一个节点的输出特征数）。图级别的输出可以通过引入一些池化操作来建模（Duvenaud等, NIPS 2015）。

每一个神经网络层可以写成这样一个非线性函数：

这里，（Z也可以作为图级别的输出），L是层数，这个模型主要在于f（）怎样选择以及参数化。

GCN第二部分：简单例子

作为示例，考虑下边这样一个简单的单层前向传播的形式：

这里，W是l层神经网络的参数矩阵，( ) 是非线性激活函数比如ReLU。这个模型尽管简单但是却非常有效（我们马上就会介绍）。

但是首先，让我们来看一下这个简单模型的两个限制：首先，和A相乘意味着对于每个节点，我们都整合了它的邻居节点的特征向量，但是却不包括这个节点本身（万一图中有自环存在）。我们可以通过在图中强行加入自环来解决这个问题，也就是给矩阵A加上一个单位阵。

第二个限制是A通常是非归一化的，因此和A相乘会完全改变特征向量的尺度（可以通过看A的特征值来理解）。归一化使A的各行和为1，比如，这里D是节点度的对角矩阵，这样就解决了这个问题。那么与相乘也就是对邻居节点的特征取平均。实际上，当我们使用对称归一化时，比如（这将不再仅仅是相邻节点的平均值），动力学会更加的有趣。

结合这两种技巧，我们基本上得到了[Kipf & Welling (ICLR 2017)]文章中的传播规则：

这里，是单位阵，是矩阵的节点度对角矩阵。

GCN第三部分：空手道俱乐部网络的嵌入

空手道俱乐部图，颜色表示通过基于模块化的聚类获得的社团

现在让我们来看一下，上边简单的GCN模型是怎样在一些知名的数据集上表现得如何，比如Zachary的空手道俱乐部网络数据（见上图）。

我们使用一个三层GCN，随机初始化权重。在训练权重之前，我们将图的邻接矩阵和X=I（即单位阵，因为我们没有任何的节点特征）输入模型。这个3层的GCN在前向过程中做了三次传播并且有效的对每个节点的3阶邻居进行了卷积（所有的节点可达3阶）。值得注意的是，这个模型生成的这些节点的嵌入和图的社区结构非常类似（见下图）。还记得我们完全随机初始化的权重并且现在还没有进行任何的训练更新。

使用GCN（随机初始化权重）做空手道俱乐部网络中的节点嵌入

这似乎有点令人惊讶，最近一篇论文提出的DeepWalk模型 (Perozzi et al., KDD 2014)通过复杂的非监督的训练过程也可以学习到一个相似的嵌入。使用这个简单的未经训练的GCN模型几乎“免费”的获得了这样的嵌入，这怎么可能呢？

我们可以通过将GCN模型解释为网络图上的著名的Weisfeiler-Lehman（WL）算法的广义可微分版本来理解。1维的WL算法是这样的：

对图上的所有节点：
得到邻居节点的特征
根据更新节点特征，这里hush（）是一个一个单射散列函数
迭代k次直到收敛

实际上，WL算法为大多数图分配一个独特的特征。也就是说每一个节点都被分配到一个可以唯一描述它在图中的角色的特征。例外是像网格（grid）、链（chain）等高度规则的图。对于大多数不规则的图，这个特征分配可以用来检验图同构（比如两个图是否相同，取决于节点的排列）。

回到我们图卷积层传播规则上（现在从向量角度来看）：这里j是邻居节点的索引，是边的正则化常量，来源于GCN模型中用到的对称正则化邻接矩阵。我们现在看到，这种传播规则可以解释为原始WL算法中使用的哈希函数的可微分和参数化（即）变体。如果我们现在选择一个合适的正交的非线性并且初始化随机的权重矩阵（比如，使用（Glorot & Bengio, AISTATS 2010）的初始化方式），在实践中这个更新规则最后会稳定下来（归功于的正则化）。

经过观察，我们得到了非常有意义的平滑的嵌入，然后我们可以将嵌入后的距离解释为局部图结构的（不）相似性！

GCN第四部分：非监督学习

由于我们模型中所有的内容都是可微分的和参数化的，所以我们可以添加标签，训练模型并观察嵌入效果。我们可以使用Kipf & Welling (ICLR 2017)文章中介绍的GCN的半监督学习算法。我们只需为每个节点标注类别或者社团（下面视频中突出显示的节点），然后开始进行多次迭代的训练。

https://v.qq.com/txp/iframe/player.html?vid=r134196jepw&width=500&height=375&auto=0

用GCN进行半监督分类：300次训练迭代中隐空间的动态变化，每个类别有一个标签，带标签标的节点突出显示。

我们注意到，这个模型直接产生了一个二维的可以直接可视化的隐空间。我们观察到这个3层的的GCN模型尝试线性区分社团，每类社团给出一个标签。考虑到该模型并没有输入节点的特征描述，所以这个结果可以说是非常卓越的。同样的，初始化的节点特征是可以提供的，在(Kipf & Welling, ICLR 2017)这篇文章的实验中我们确实是提供了的，因此在图数据的分类上达到了最好的效果。

结论

对这个问题的研究才刚刚开始，过去几个月已经看到了令人兴奋的发展，但是目前为止我们可能只是抓住了这个模型的表面。图神经网络如何进一步解决一些特定类型的问题仍然有待观察，比如有向和关系图的学习，如何利用学到的网络嵌入等等。这里的论文清单绝对不是最全面的，我预计在不久的将来会有更多有趣的应用和扩展。如果你有一些令人兴奋的想法或问题需要分享，请在下面的评论中告诉我们！

补充说明

这篇博客文章并不是对图神经网络领域的详尽回顾，因为为了使这篇文章更具可读性并且具有一个连贯的故事线，我忽略了一些近期和较早的论文。但是如果你想深入研究这个主题，并且全面了解目前为止已经研究过的内容和正在研究的内容，那么我在这里提到的论文是一个很好的开端。

参考文献

后台回复“GCN”领取文献大礼包

Bruna et al., ICLR 2014, http://arxiv.org/abs/1312.6203
Henaff et al., 2015, http://arxiv.org/abs/1506.05163
Duvenaud et al., NIPS 2015, http://papers.nips.cc/paper/5954-convolutional-networks-on-graphs-for-learning-molecular-fingerprints
Li et al., ICLR 2016, https://arxiv.org/abs/1511.05493
Defferrard et al., NIPS 2016, https://arxiv.org/abs/1606.09375
Kipf & Welling, ICLR 2017, http://arxiv.org/abs/1609.02907
How powerful are Graph Convolutions?http://www.inference.vc/how-powerful-are-graph-convolutions-review-of-kipf-welling-2016-2/
Jain et al., CVPR 2016, https://arxiv.org/abs/1511.05298
Brandes et al., 2008, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.68.6623
Perozzi et al., KDD 2014, https://arxiv.org/abs/1403.6652
Glorot & Bengio, AISTATS 2010,
http://jmlr.org/proceedings/papers/v9/glorot10a/glorot10a.pdf
本文 GCN 项目仓库：https://github.com/tkipf/gcn