Introduction of Graph Convolutional Networks

图卷积网络(Graph Convolutional Networks)

THOMAS KIPF, 2016.9

mage-20180819235646

概览

​ 很多重要的真实数据都来源于图或者网络: 社交网络, 知识图谱, 蛋白质相互作用, 万维网等(简单列举一些)。然而,到目前为止,很少有人关注去将神经网络模型泛化到这样的数据结构中。

​ 在过去几年中,一些文章回顾了广义神经网络在任意网络上的尝试(Brunna et al, ICLR 2014; Henaff et al. 2015; Devenaud et al. NIPS 2015; Li et al., ICLR 2016; Defferrard et al., NIPS 2016; Kipf &Welling, ICLR 2017), 其中已经有些在某些领域(之前往往都被核方法,基于图的正则化技术等其他统治)取得比较不错的结果。

​ 这篇post中, 作者将会简单介绍一下相关领域最近的发展然后指出各个方法的优缺点。讨论主要集中在两篇论文:

另一篇post也讨论了这些模型的限制。我写这篇评论主要是针对Ferenc的意见(最后)。

大纲

  • 图的神经网络模型简介
  • 谱图卷积和图卷积
  • Demo: 简单的1阶图模型的图嵌入
  • GCN是Weisfeiler-Lehman算法的可微分推广

为什么图卷积这么强大

最近的文献

​ 广义的神经网络模型(RNN或者CNN)用在任意结构的图上是一个挑战。最近很多文章介绍了特定问题的架构(比如 Duvenaud et al., NIPS 2015; Li et al., ICLR 2016; Jain et al., CVPR 2016),其他用到了谱图理论((Bruna et al., ICLR 2014; Henaff et al., 2015)来定义多次神经网络中用到的filter参数,类似于我们熟知和喜欢的经典CNN,

​ 更多最近的工作的重点是弥合启发式和慢速之间的差距,更具体点就是谱图方法和速度之间的差距。Defferrard等人在2016年使用自由参数的切比雪夫多项式在频谱中近似平滑滤波器 来学习神经网络模型。他们去的了令人信服的结果(MNIST数据集),与简单的2D-CNN模型很接近。

​ Kipf&Welling(ICLR 2017)采用了某种类似的方法,从谱图卷积框架开始,然后引入简化(后面会介绍),在多数情况下在一些基准数据集上都取得了加速,更高的准确度而且达到最先进的分类结果。

GCN-1: 定义

​ 最近,很多图卷积模型都有某种统一的框架。我将参考这些图卷积网络作为模型(卷积: 因为过滤器参数通常在图中会共享, 或者子集共享)。

​ 对于这些模型,目的是为了在图$G=(V,E)$中学习一个信号/特征的函数,他的输入如下:

  • 每个节点(i)的特征描述$x_i$, $N \times D$的特征矩阵X (N: 节点数目; D:输入特征数目)
  • 图结构的矩阵表示, 一般都用邻接矩阵A

然后会产生node-level的输出Z($N\times F$),其中F是每个输出节点的特征数目。图级别的输出可以用某种池化操作来引入(参考Devenaud et al. NIPS 2015)。

​ 每个神经网络层可以写成形式:$H^{(l+1)}=f(H^{(l)}, A)$,其中$H^{(0)}=X$, $H^{(L)}=Z$,L是网络层数。网络具体的不同体现在f。

GCN-II: 简单的例子

​ 举个栗子,首先我们考虑层之间的传播规则: $f(H^{(l)},A)=\sigma(AH^{(l)}W^{(l)})$, $W^{(l)}$是去权值矩阵,$\sigma$是非线性激活函数(比如Relu).尽管这个模型简单,但已足够强大。

​ 首先,让我们提出两个问题:第一个问题,乘以A以为这对于每个节点,都要将它周围节点的特征向量加起来,但是不包含节点本身(除非图中有自循环)。我们可以通过强制让他自循环来修正这个: 仅仅是与单位矩阵相加。第二个问题是A往往是非归一化的,因此乘以A会导致特征向量的范围会发生很大变化(可以通过A的本征值来理解)。归一化A(比如把列加到一起, $D^{-1}A$, D是节点对角度矩阵)。乘以$D^{-1}A$可以充分利用邻近节点的平均特征。实际上,当使用对称的归一化($D^{-\frac{1} {2}}AD^{-\frac{1} {2}}$)时,动力学变得更加有趣。结合这些小技巧,我们基本可以理解Kipf&Welling(ICLR 2017)提出的传播规则: $,f(H^{(l)}, A)=\sigma(\hat D^{-\frac {1} {2}}\hat A\hat D^{-\frac {1} {2}}H^{(l)}W^{(l)})$其中,$\hat A = A + I$, $I$是一个单位矩阵,而$\hat D$是$\hat A$的对角节点度矩阵。下面,我们将深入研究这个模型在Zachary’s karate club network 数据集上如何实现.

GCN-III: Karate clue 网络嵌入

mage-20180820071627

​ 这里,我们采用了一个初始化权值的3层GCN。现在,在训练权值之前,我们简单地插入邻接矩阵,此时$X=I$ (比如单位矩阵,因为这个时候没有任何节点特征到模型中)。3层卷积模型现在在前馈过程中执行3层传播,并有效地对每个节点的三阶邻域进行卷积操作(所有节点 最多三阶邻域)。

​ 值得注意的是,该模型生成了这些节点的嵌入,这些节点非常类似于社区图的结果(下图)。记住,我们是完全随机初始化参数权值,并且目前也没有执行任何训练。

mage-20180820072537

​ 这看起来似乎有点出人意料。最近有篇论文叫DeepWalk, KDD 2014就证明了可以从一个复杂的非监督训练过程学习得到一个非常简单的嵌入。那么使用我们简单的未训练的GCN模型就能或多或少得到这样一个嵌入呢?

​ 我们可以通过将GCN模型解释为图上众所周知的Weisfeiler-Lehman算法的通用微分版本来阐明一点。(1维)W-L算法流程如下:


对于所有节点$v_i \in G$:

  • 获取邻近节点 {$vj$} 的特征{$h{v_j}$}
  • 更新节点 $h_{v_j} \leftarrow hash (\sumj h{v_j})$, 其中hash($\cdot$)理想情况下是一个内射的哈希函数

然后重复k步知道收敛


​ 实际上,W-L算法为大多数图分配了一组独特的特征。这意味着每个节点分配了一个特征,用于描述他在图中的角色。有一些例外,比如高度规则的图像,入网格,链等。对于大多数不规则图形,这个特征可以用于检查同构图形(即两个图形是否相同,甚至节点的排列)。

​ 回顾图卷积层级传播规则(向量形式): $h^{(l+1)}_{v_i} = \sigma(\sumj \frac 1 {c{ij}}h_{v_j}^{(l)}W^{(l)})$, 其中j代表节点$vi$邻近的节点数,$c{ij}$是边($v_i, v_j$)的归一化常数,在GCN模型中,他从对称的邻接矩阵$D^{-\frac 1 2}AD^{-\frac 1 2}$得到。现在可以将我们这个传播规则看作是原始W-L算法中哈希函数的一个可微分和参数化($W^{(l)}$)辩题。如果选择合适的非线性以及初始化随机参数矩阵使其正交(比如使用Glorot & Bengio AISTATS 2010的初始化方案 xavier), 这个更新规则在时间中会变得比较稳定(这可能也要归功于$c_{ij}$规范化)。我们进行了深入的考察,最终得到了很有意义的平滑嵌入,我们可以将距离解释为局部图结构的[非]相似性。

GCN-IV: 半监督学习

​ 既然我们模型的所有都是可微分并参数化的,我们可以添加一些便签,来训练模型并观察如何嵌入的。这里可以使用在Kipf & Welling (ICLR 2017)提出的GCN半监督学习算法。我们简单的对每个类做便签(在视频中高亮的节点)然后开始训练。

Semi-supervised classification with GCNs: Latent space dynamics for 300 training iterations with a single label per class. Labeled nodes are highlighted

Semi-supervised classification with GCNs: Latent space dynamics for 300 training iterations with a single label per class. Labeled nodes are highlighted

​ 注意这个模型直接产生了2维的隐变量空间,这样才能实时的可视化。我们观察到3层GCN模型设法线性地分开了团簇,其中每个类只给一个标签。鉴于模型没有给任何特征描述,这是一个不错的结果。同事,我们提供了初始节点特征,这真是我们论文中做的,在许多图像数据集中达到了当前最优结果。

总结

​ 关于这个主题的研究才刚刚开始。过去几个月已经看到了一些令人激动的发展,但是目前为止我们可能只是触及了这类方向的表面。如何进一步了解神经网络解决特定类型问题还有待研究。例如,学习有向图或关系图,以及如何使用学习到的图嵌入进行下一步的其他任务等。这只是一个粗略的介绍,我希望将来会有更多有趣的应用和扩展。

人艰不拆,生活不易