Representation Learning on Graphs with Jumping Knowledge Networks[ICML'18]

ICML18一篇解决GCN层数加深性能反而变差的论文

解决的问题

当图卷积网络GCN的层数超过两层时模型的表现会变差,这使得GCN只能作为浅层模型使用,且在对邻域节点的信息进行聚合时,即使同样是采用$k$层网络来聚合$k$跳邻居的信息,有着不同局部结构的顶点获得的信息也可能完全不同,以下图为例:

BpCLz8.jpg

图$(a)$中的顶点位于核心区域,因此采用$4$层网络把几乎整个图的信息都进行聚合了,而不是它的邻域,这会导致过度平滑,而图$(b)$中顶点位于图边缘的一个树状结构中,采取同样的$4$层网络只囊括了一小部分顶点的信息,只有在第$5$层囊括了核心顶点之后才有效地囊括了更多顶点的信息。

所以,对于处于核心区域的顶点,GCN中每多一层即每多一次卷积操作,节点的表达会更倾向全局,这导致核心区域的很多顶点的表示到最后没有区分性。对于这样的顶点应该减少GCN的层数来让顶点更倾向局部从而在表示上可以区分;而处于边缘的顶点,即使更新多次,聚合的信息也寥寥无几,对于这样的顶点应该增加GCN的层数,来学习到更充分的信息。因此,对于不同的顶点应该选取不同的层数,传统做法对于所有顶点都用一个值会带来偏差。

做法及创新

理论部分,论文主要讨论的问题是,在一个$k$层的GCN中,顶点$x$对顶点$y$的影响程度,即顶点$x$输入特征的改变,会对顶点$y$在最后一层得到的表示产生多大的变化,也可以说是顶点$y$对于顶点$x$有多敏感。假设输入的特征为$X\in \mathbb{R}^{n\times f}$,输出的预测标签为$Z\in \mathbb{R}^{n\times c}$,其中$n$为图中顶点数目,$c$为类别数目,$f$为特征数目,则这种影响程度可以表示为$I(x,y)=\sum_i\sum_j\frac{\partial Z_{yi}}{\partial X_{xj}}$。

更特别地,论文证明了这个影响程度与从顶点$x$开始的$k$步随机漫步的分布有关,如果对$k$取极限$k\rightarrow \infty$,则随机漫步的分布会收敛到$P_{lim}(\rightarrow y)$。详细论证过程可见原文。这说明,结果与随机漫步的的起始顶点$x$没有关系,通过这种方法来得到$x$的邻域信息是不适用的。

另一种说法是,一个$k$层的图卷积网络等同于一个$k$阶的多项式过滤器,其中的系数是预先确定的SDC。这么一个过滤器与随机漫步类似,最终会收敛到一个静态向量,从而导致过度平滑。

实践部分,论文提出JK-Net,通过Layer aggregation来让顶点最后的表示自适应地聚合不同层的信息,局部还是全部,让模型自己来学习:

BpEvLT.jpg

论文的重点在于最后的Layer aggregation层,可选的三种操作为:Concat、Max-pooing以及LSTM-attn。

  1. Concat

    将各层的表示直接拼接在一起,送入Linear层。对于小数据集及结构单一的图这种聚合方式会更好,因为它们不需要顶点在聚合邻域的顶点信息时具有什么自适应性。

  2. Max-pooling

    选取各层的表示中包含信息量最多的作为顶点的最终表示,在多层结构中,低层聚合更多局部信息,而高层会聚合更多全局信息,因此对于核心区域内的顶点可能会选取高层表示而边缘顶点选取低层表示。

  3. LSTM-attention

    对于各层的表示,attention机制通过计算一个系数$s_v^{(l)}$来表示各层表示的重要性,其中$\sum_ls_v^{(l)}=1$,顶点最终的表示就是各层表示的一个加权和:$\sum_ls_v^{(l)}·h_v^{(l)}$。

    $s_v^{(l)}$的计算:将$k$层网络各层的表示$h_v^{(1)},\dots,h_v^{(k)}$输入一个双向LSTM中,同时生成各层$l$的前向LSTM与反向LSTM的隐式特征,分别表示为$f_v^{(l)}、b_v^{(l)}$,拼接后将$|f_v^{(l)}||b_v^{(l)}|$送入一个Linear层,将Linear层的结果进行Softmax归一化操作就得到了系数$s_v^{l}$。

数据集

Citeseer、Cora、Reddit、PPI

在模式识别上对这篇论文进行了简短的一个分享,这里直接把讲稿和PPT放上来。

PPT

2EFaFI.png
2EFdYt.png
2EFDl8.png
2EFwfP.png
2EFNTA.png
2EFBSf.png
2EFr6S.png
2EFRkn.png
2EFcwj.png
2EFff0.png
2EFLkR.png
2EFoXF.png

讲稿

大家好,今天我要介绍的是ICML会议18年的一篇论文,通过跳跃知识网络进行图上的表示学习,论文的亮点在于引入ResNet的思想解决图神经网络层数无法加深的问题。图神经网络简称GNN,它受卷积神经网络CNN启发,主要应用于图这种非欧几里得结构数据。它根据”相邻的顶点具有相似性“这一假设,通过聚合邻域顶点的信息来进行图上顶点的表示学习。不同于图像这种排列整齐的欧几里得结构数据,在图上不同顶点的邻居顶点数目是不同的,这就为图上的问题带来了挑战。

给定一张由顶点和边组成的图作为输入,图神经网络通常分为如下两个步骤:邻域聚合和状态更新。邻域聚合对应式子的后半部分,而状态更新对应于式子的前半部分。在每一层的网络,首先对邻域内的顶点的表示进行聚合,再将得到的聚合结果和上一层得到的表示组合在一起,共同作为当前层顶点的表示。这里的聚合和组合有多种定义方式,因为时间原因不在这里进行介绍。虽然图神经网络的出现给图上问题的解决方法带来了新的思路,但它也面临着挑战。不同于CNN,GNN在层数加深时会出现性能下降的问题,典型的网络如图卷积网络GCN、图注意力网络GAT等都是在2~4层时取得最好的性能表现。本文的一个贡献就是从理论上分析了性能下降的原因。导致这个现象的一个主要原因是所谓的”过平滑“现象,即随着网络层数的加深,图中顶点经过网络学习得到的特征表示会趋向于相等的现象。这就会导致顶点间不再具有区分度,进而导致下游任务效果变差。例如图中的例子,从左到右表示层数的加深,可以看到,六层网络时不同的顶点几乎都混在了一起,比浅层网络时的效果要差很多。论文从随机游走的角度说明了原因,一个K层的GNN相当于从源顶点出发到目标顶点的一个K步的随机游走,当K趋向于无穷即层数不断加深时, 顶点的极限分布与初始的顶点表示无关,只与图的结构相关。也就是说,本来聚合邻域的信息是为了得到中心顶点的特征表示,当随着层数加深聚合的信息越多,反而得到的表示与中心顶点无关,这就导致每个顶点都会得到相等的特征表示。

因为ResNet等深层神经网络模型在计算机视觉领域的成功,本文受此启发引入ResNet中的残差模块,在GNN的框架中引入额外的连接。左边对应于论文提出的架构图,从架构图可以看到,不同于传统GNN每一层的表示只与上一层有关,现在每一层的表示都会额外地连接到最后一层,使得在最后一层得到最终的顶点表示时可以聚合不同层的信息,来避免前面说到的过平滑问题。聚合有三种方式:Concat、Max-pooling和LSTM-attention,每种方式有各自适合的场景,例如第三种方式通过双向LSTM来得到各层表示的重要程度,进而自适应地聚合各层的信息,得到更好的特征表示。因为时间关系不再展开介绍。实验部分,论文选取的baseline都是经典的GNN模型,包括图卷积网络GCN和图注意力网络GAT,可以看到在几个benchmark数据集上都取得了最好的结果,也使用了更深的网络层数。我今天的分享到此结束,谢谢大家。