关于图卷积神经网络的博文翻译

图1. 一阶滤波器架构搭建的图卷积神经网

我们知道,真实世界的许多重要数据集会以图或网络的形式展现:社交网络、知识图谱、蛋白质交互网络、万维网等等(更多例子不再罗列)。然而,到本文写作前,很少有人关注神经网络模型在这类结构上的推广。近年来,许多论文重新审视了神经网络在此类图结构上加以推广的问题(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 (博主一作)

Defferrard et al. (NIPS 2016), Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

另外,有兴趣也可以去读下Ferenc Huszar的《How powerful are Graph Convolutions?》,此文列举了图卷积神经网络的一些局限性,我也与Ferenc Huszar君进行了若干互动,此处为我的评论。概要:

  • 神经网络在图结构上推广的简单介绍
  • 谱图卷积以及图卷积神经网络(GCN)
  • 演示:简单的一阶图卷积神经网络构建的图嵌入模型
  • GCN在Weisfeiler-Lehman 算法上的可微分泛化推广

如果你熟悉了,可以直接跳到这部分内容
图卷积神经网络的威力

将已有的神经模型(如RNN或CNN)推广到任意结构的图上是一个具有挑战性的问题。最近的一些论文介绍了此类应用的专门架构(例如Duvenaud et al., NIPS 2015; Li et al., ICLR 2016; Jain et al., CVPR 2016),另一些论文利用谱图理论在我们喜闻乐见的经典的CNN架构上做图卷积来定义用于多层神经网络模型的参数化滤波器(Bruna et al., ICLR 2014; Henaff et al., 2015)。最近的工作重点立足于弥合快速启发法和慢速方法之间的差距,但更通用性的做法是在频域上做文章。Defferrard et al. (NIPS 2016)使用Chebyshev多项式自由参数构建的近似平滑滤波器组成在频域上进行神经网络的学习。他们在规则空间的数据集里(如MNIST)上取得了令人信服的结果,效果并不比二维的卷积神经网络(CNN)差。在博主和博主导师发表的论文里,我们采取了类似的方法,也是用了谱图卷积的框架,但引入了更简化的方法,之后将进行讨论。在许多情况下,进行简化可以缩短训练时间,提高预测精度,从而在一些基准的图数据集上达到最先进(state-of-the-art,STA)的分类效果。


第一部分:基本概念

目前,大多数基于图结构的神经网络模型具有一定的通用性。可以把这些模型称为图卷积神经网络(GCNS);卷积意味着滤波器参数通常在图中的所有位置上是共享的(参考下 Duvenaud et al., NIPS 2015的论述)。这些模型的目标函数致力于在图上学习信号/特征,例如:G=(V,E)其作为输入:每个节点的特征描述xi;用N×D特征矩阵X概括(N:节点数,D:输入特征数)以矩阵形式对图结构建模;通常以邻接矩阵A(或其它一些函数)的形式表示。它产生一个节点级输出Z(N×F特征矩阵,其中F是每个节点的输出特征数)。图级别的输出可以通过引入某种形式的池化操作来建模( Duvenaud et al., NIPS 2015)。每一层神经网络可以写成一个非线性函数:

其中:

L为神经网络的层数,Z为图节点输出。模型的关键在于f(. .)该怎么选择和进行参数化。


第二部分:图卷积

一个深入浅出的例子让我们来看下这个简单形式的层级传播的例子:

为第l层神经网络的权重矩阵,

类似ReLu那样的非线性激活函数。尽管简单,但却足够强大,稍后我们略微点评一二。不过,首先,让我们解决这个简单模型的两个局限性:用A乘法意味着,对于每个节点,我们需要加上所有相邻节点的所有特征向量,然后去掉节点本身(除非图中有自循环)。我们可以通过在图中强制执行自循环来“修正”这个问题:我将恒等矩阵添加到A中。第二个主要限制是,A通常不是归一化的,因此与A的乘法将完全改变特征向量的尺度(我们可以通过查看A的特征值来理解这一点)。可以通过对A做归一化,使得所有行和为1,

其中D是对角线节点度矩阵,从而消除了这个问题。做这样的乘法可以提取相邻节点特征的平均值。在实践中,这里面的动态变化十分有趣,比如,我们可以使用对称归一化:

而不再仅仅是相邻节点的平均值。结合这两个技巧,我们基本上得出了在Kipf & Welling (ICLR 2017)中引入的传播规则。

其中:

我们有单位阵:

则是下面的矩阵:

之对角矩阵。在下一节中,我们将更深入地了解这种模型是如何在一个简单的示例图上运行的:Zachary的空手道俱乐部网络。
第三部分:空手道俱乐部网络的嵌入

图2. 空手道俱乐部的图模型,不同颜色表示聚类得到的不同社团

让我们来看看我们的简单GCN模型(见前一节或 Kipf & Welling,ICLR 2017)是如何在著名的图表数据集Zachary的空手道俱乐部网络(见上图)上工作的。我们取一个随机初始化权重的三层GCN。现在,甚至在训练权重之前,我们只需插入图的邻接矩阵,X=I(即单位阵,因为我们没有任何节点特征)进入模型。三层GCN现在在正向传递过程中执行三个传播步骤,并有效地卷积周边每个节点的三阶邻域(所有节点最多到三阶)。值得注意的是,模型生成了这些节点的嵌入,这些节点与图中的社区结构非常相似(参见下图)。我们已经完全随机初始化了权重,并并且是在没有训练更新的情况下完成的!

图3. 基于初始化权重的图模型嵌入所表示的空手道俱乐部建模

是不是看上去很令人惊讶,Perozzi et al., KDD 2014论文里提出了一种思想叫深度游走(DeepWalk),它可以通过复杂的无监督学习方法来学习到这些嵌入表示,为什么不在用少量资源甚至不需要花费计算资源的情况下,就去掌握这样的特征表示呢,GCN,或许是您的选择。我们可以通过将GCN模型解释为著名的Weisfeiler-Lehman图算法(WL算法)的一个广义的、可微的版本来阐明这一点。(一维)Weisfeiler-Lehman算法的工作原理如下:对所有节点vi属于G:

  • 得到邻居节点 {vj}的特征{hvj} 
  • 用哈希函数更新节点 hvi←hash(∑jhvj), 其中哈希函数hash(⋅) 是理想的单射哈希函数。

重复K步直到收敛。实际中,WL算法会为每个独特的特征集合分配对应的图节点。这就意味着每个被分配对应特征的节点都可以被用图表示出来。像网格(grid)、链(chain)等高度规则的图会是个特例。对大多数不规则的图,特征分配可以用来检验图是否是同构的(两个图是否相同,取决于节点的排列)。回到向量形式的图卷积神经网络的层级传播规律:

其中 j 表示vi的邻居节点。cij 是边 (vi,vj) 的归一化常数,它由GCN模型的对称归一化邻接矩阵D^(-0.5)AD^(-0.5)变化而来。传播规律可以表达成原始WL算法的哈希函数的可微分和参数化形式W(I)。如果我们选择选择进行非线性拟合,并对正交化的随机权重矩阵做初始化(参考 Glorot & Bengio, AISTATS 2010),在实际应用中,传播参数的更新将会是稳定的(当然,做归一化得到cij 也是功不可没的)。现在,我们得到非常有意义的平滑嵌入,我们也可以将嵌入后节点之间良好的距离解释为局部结构的(非)相似性。
第四部分:半监督学习

由于我们的模型中的所有计算推到都是可微分的和参数化的,所以我们可以添加一些标签,对模型进行训练,并观察嵌入的变化。我们可以使用在Kipf & Welling(ICLR2017)中引入的GCN半监督学习算法。简单地将每个类/社区的一个节点(在下面的视频中突出显示的节点)进行标记,并启动对多轮训练。(用GCN进行半监督分类,每个类的标签经过300多个对隐空间内部动态变化的训练迭代步骤的进行学习,标记的节点被高亮,视频地址:https://tkipf.github.io/graph-convolutional-networks/images/video.mp4)。这个模型可以直接生成二维可视化的隐空间。

我们可以看到,一个3层的图卷积神经网模型就可以尝试线性地划分出社团。给每个类打上不同的标签。考虑到没有太多节点特征描述作为输入,这样的结果非常棒。与此同时,初始化节点特征是可以获得的,这个可以参考(Kipf & Welling, ICLR 2017)的实验,它证明了用图模型的方法可以在相关数据集上达到STA的效果。
结论:对于此项议题的研究方兴未艾。最近几个月的变化可谓是日新月异,然而,这只是摸到了模型的表皮,图神经网络如何进一步解决一些特定类型的问题仍然有待观察,比如有向和关系图的学习,如何利用学到的网络嵌入等等,都还刚刚起步,需要解决。我所罗列的东西并不完备,希望未来会有更多精彩的应用和扩展。欢迎大家有好想法的一起来分享下。

与Ferenc Huszar 商榷:

Ferenc Huszar在他的文章《 How powerful are Graph Convolutions?》提了些质疑,它举了常规化图的特定例子。它认为古典的CNN是专门为特定领域,比如图像处理设计的,图卷积模型的引入会带来烦琐的操作。目前来说,适用于任意结构图的GCN模型在应用于通用的图(如网格、链、全连通图等)时通常有一些缺点。Defferrard et al., NIPS 2016采用局部化谱操作,引入旋转对称滤波器,但在网格(grid)上,除了依然有边界效应外,却不能模仿经典CNN的效果。与此同时,WL算法也无法在普通的图上收敛。这告诉我们的是,当我们试图评估特定图形神经网络模型的有效性时,我们应该超越常规网格,因为在为任意图设计此类模型时,我们必须进行特定的权衡(但让人们了解这些权衡是很重要的),除非我们可以在找到一个普遍强大的模型(不太可能)。

1. 谱图卷积表示在图的傅立叶空间中,进行信号与滤波器的相乘。图傅立叶变换定义为图信号X(即每个节点的特征向量)和特征向量矩阵U的拉普拉斯图 L做乘法。利用对称归一化的图邻接矩阵可以很容易地计算出(归一化的)拉普拉斯图:

2. 使用频谱方法的代价是:必须在傅里叶空间中定义滤波器,并且图傅里叶变换对于计算机来说是昂贵的(它要求节点特征与图Laplacian的特征向量矩阵相乘,该特征向量矩阵是具有N个节点,整个操作费时O(N^2);计算最初的位置中的特征向量矩阵甚至更昂贵)。

3. 我简化了讨论: Douglas(2011)讲述了WL算法的数学扩展。

4. Weisfeiler-Lehman算法的节点特征是整数,会被上颜色。

5. 在这个例子中,我们没有退火学习率,所以一旦模型收敛到一个好的解决方案,事情就会变得非常“不稳定”。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

您正在使用您的 WordPress.com 账号评论。 注销 /  更改 )

Google photo

您正在使用您的 Google 账号评论。 注销 /  更改 )

Twitter picture

您正在使用您的 Twitter 账号评论。 注销 /  更改 )

Facebook photo

您正在使用您的 Facebook 账号评论。 注销 /  更改 )

Connecting to %s