Graph U-Nets [gPool gUnpool] 图分类 节点分类 图池化 ICML 2019

论文：Graph U-Nets

作者：Hongyang Gao , Shuiwang Ji
美国德克萨斯A&M大学计算机科学与工程系

来源：ICML 2019

论文链接：
Arxiv: https://arxiv.org/abs/1905.05178

github链接：https://github.com/HongyangGao/gunet

1 相关介绍

背景

此文研究了图数据的表示学习问题。卷积神经网络可以很自然地对图像进行操作，但在处理图数据方面存在很大的挑战。图像可以看作是是二维格上有节点的图，所以图的节点分类任务与如图像分割这样的像素级预测任务具有天然的对应关系。具体来说，这两项任务的目标都是对每个输入单元(对应图像上的一个像素或图上的一个节点)进行预测。在计算机视觉领域，像素级预测任务近年来取得了很大的进展。像U-Net这样的编码器-解码器架构是实现这些任务的最先进的方法，并且已经成功地应用于许多像素级的预测任务，但类似的方法在图数据上还很缺乏。因此，开发类似于U-Nets的图数据架构是非常有趣的。除了卷积之外，池化和上采样操作也是这些体系结构中的基本构件。然而，将这些操作扩展到图数据非常具有挑战性，因为与图像和文本之类的网格数据不同，图数据中的节点没有空间局部性和顺序信息，即节点的邻居数量不固定，并且没有顺序。所以池化和上采样（up-sampling）不能很自然地对图数据进行操作。

贡献

为了解决这些挑战，文中提出了新的graph pooling(gPool)和graph unpooling(gUnpool)层：

• gPool层根据节点在可训练投影向量上的标量投影值，适应地选择节点，即对重要节点的子集进行采样，形成较小的图，从而增大了感受野并有效编码了高级特征。
• gUnpool层是gPool层的逆操作。gUnpool层使用在相应gPool层中选择的节点的位置信息将图恢复到其原始结构。
• 基于gPool和gUnpool层，文中提出了一个作用在图上的编码器-解码器模型，称为graph U-Nets。graph U-Nets可以编码高维特征，然后解码生成网络embedding。
• 文中在节点分类和图分类任务上进行了实验，结果表明，graph U-Nets在transductive learning任务上比以前的GNNs取得了更好的性能。
• 为了避免采样图中可能存在的孤立节点问题，文中采用图2次幂来改进了图的连通性。

2 相关工作

图卷积

（1）Kipf的GCN

$$X_{\ell +1}=\sigma \left({\hat{D}}^{-\frac{1}{2}}\hat{A}{\hat{D}}^{-\frac{1}{2}}{X}_{\ell }{W}_{\ell }\right)\text{\hspace{1em}(1)}$$

• $W_{\ell }$是一个可训练的权重矩阵，它对特征向量进行线性变换。
• GCNs本质上是在没有学习可训练的filters的情况下对节点特征进行聚合和转换。、

参考：GCN - Semi-Supervised Classification with Graph Convolutional Networks 用图卷积进行半监督节点分类 ICLR 2017

（2）GraphSAGE
采样固定数量的相邻节点，以保持计算内存占用的一致性。
参考：GraphSAGE：Inductive Representation Learning on Large Graphs 论文详解 NIPS 2017

（3）GAT
利用注意力机制使相邻节点的权值不同。
参考：GAT - Graph Attention Network 图注意力网络 ICLR 2018

（4）RGCN
使用关系图卷积网络进行链接预测和实体分类任务。
参考：RGCN - Modeling Relational Data with Graph Convolutional Networks 使用图卷积网络对关系数据进行建模 ESWC 2018

卷积在图分类上的一些工作：

• DGCNN：An end-toend deep learning architecture for graph classification，AAAI 2018
• Deep convolutional networks on graph-structured data，2015:用于大规模图分类的谱网络
• Spectral networks and locally connected networks on graphs，ICLR 2014:用于大规模图分类的谱网络

图池化

• Convolutional neural networks on graphs with fast localized spectral filtering，Defferrard,NIPS 2016
  使用二叉树索引进行图粗化，在应用1-D池化操作之前固定节点索引。
• Dynamic edge-conditioned filters in convolutional neural networks on graphs，CVPR 2017
  使用确定性图聚类算法确定池化模式。
• Hierarchical graph representation learning with differentiable pooling，NIPS 2018
  使用assignment矩阵，通过将节点分配到下一层的不同cluster来实现池化。

3 Graph U-Nets

下面介绍graph pooling(gPool)层和graph unpooling(gUnpool)层。基于这两个新层，提出了进行节点分类任务的graph U-Nets。

符号定义：

• 假设图$G$中有$N$个节点，每个节点包含$C$个特征。
• 节点的邻接矩阵为$A^{\ell }\in {\mathbb{R}}^{N\times N}$，特征矩阵为$X^{\ell }\in {\mathbb{R}}^{N\times C}$

3.1 Graph Pooling Layer：gPool

池化层在CNNs中对网格状数据起着重要的作用，可以减小feature map的大小，扩大感受域，从而产生更好的性能，泛化能力也增强。在图像等网格数据上，将特征图分割成不重叠的矩形，并对其使用非线性下采样函数，例如max，mean pooling。除了局部池化之外，还有全局池化，全局池化层(Self-adaptive hierarchical sentence model，IJCAI 2015)还对所有输入单元执行下采样操作，从而将每个feature map为一个数字。k-max池化层(A
convolutional neural network for modelling sentences， 2014)从每个特征图中选择k-max的单元。

但是，不能将这些池化操作直接应用到图数据上，特别是因为图中节点之间没有局部性信息。因此，分区操作不适用于图。全局池化操作将所有节点映射为一个节点，限制了网络的灵活性。k-max池化操作输出可能来自图中不同节点的k个最大单元，导致所选节点的连接性不一致。

文中使用图池化层(gPool)来对图数据进行向下采样。在图池化层中，自适应地选择节点的一个子集来形成一个新的但是更小的图。为此，使用了一个可训练的投影向量$\mathbf{p}$，将所有节点特征投影到1D，然后执行k-max池化来选择节点。因为这种选择是基于每个节点的一维footprint，所以新图中的连接在节点之间是一致的。给定一个具有特征向量$x_i$的节点$i$,$x_i$在$\mathbf{p}$上的标量投影为：

$$y_i={\mathbf{x}}_{\mathbf{i}}\mathbf{p}/\Vert \mathbf{p}\Vert$$

• $y_i$度量了将节点$i$投影到$\mathbf{p}$方向时，可以保留多少$i$的信息。
  为了在采样节点的过程中尽可能多地保留原始图中的信息，选择在$\mathbf{p}$上投影的标量最大的值的节点来形成一个新的图。

图池化传播规则为：

$$\begin{array}{rl}\mathbf{y}& =X^{\ell }{\mathbf{p}}^{\ell }/\Vert {\mathbf{p}}^{\ell }\Vert \\ \mathrm{i}\mathrm{d}\mathrm{x}& =\mathrm{rank}(\mathbf{y},k)\\ \tilde{\mathbf{y}}& =\mathrm{sigmoid}(\mathbf{y}(\mathrm{i}\mathrm{d}\mathrm{x}))\\ {\tilde{X}}^{\ell }& =X^{\ell }(\mathrm{i}\mathrm{d}\mathrm{x},:)\\ A^{\ell +1}& =A^{\ell }(\mathrm{i}\mathrm{d}\mathrm{x},\mathrm{i}\mathrm{d}\mathrm{x})\\ X^{\ell +1}& ={\tilde{X}}^{\ell }\odot \left(\tilde{\mathbf{y}}{1}_C^T\right)\end{array}\text{\hspace{1em}(2)}$$

• 假设选择的$k$个索引为$i_1,i_2,\cdots ,i_k$，其中$i_m<i_m$且$1\le m<n\le k$。
• $k$表示选择的节点的数量
• $\mathbf{y}={\left[y_1,y_2,\cdots ,y_N\right]}^T$，使用$y_i$来度量每个节点在投影向量${\mathbf{p}}^{\ell }$上的投影值
• gate 向量$\tilde{\mathbf{y}}\in {\mathbb{R}}^k$
• $\mathrm{rank}(\mathbf{y},k)$表示节点的排序操作，返回$\mathbf{y}$中值最大的$k$个节点的索引。索引选择过程保留了原图中的位置顺序信息。
• 使用选择的索引idx，可以得到新图的邻接矩阵$A^{\ell +1}\in {\mathbb{R}}^{k\times k}$和特征矩阵${\tilde{X}}^{\ell +1}\in {\mathbb{R}}^{k\times C}$
• 特征矩阵${\tilde{X}}^{\ell +1}\in {\mathbb{R}}^{k\times C}$
• $1_C\in {\mathbb{R}}^C$是一个所有元素都是1，大小为$C$的特征向量
• 经过一个gPool层后，图中的节点数量从$N$变到了$k$

gate operation(sigmoid)使得投影向量$\mathbf{p}$可以通过反向传播进行训练。在没有gate operation的情况下，投影向量$\mathbf{p}$会产生离散的输出，这使得它无法通过反向传播进行训练。

• 图1是$k=2$的图卷积层（gPool）的示意图
• $\times$和$\odot$分别表示矩阵乘法和hardmard积
• 图中有4个节点，每个节点有5个特征
• 在特征投影阶段，$\mathbf{p}\in {\mathbb{R}}^5$是一个可训练的投影向量
• 通过矩阵乘法和$\text{sigmoid}(\cdot )$，得到了$\mathbf{y}$，它是估计每个节点到投影向量的投影值的分数
• $k=2$选择得分最高的两个节点，并在top-k Node Selection阶段记录它们的索引
• 在gate阶段，将$\tilde{X}$与选择的节点的分数向量$\mathbf{y}$求hardmard积，得到$X^{\ell +1}$
• 图pooling层输出$A^{\ell +1}$和$X^{\ell +1}$
• 与网格数据中的池化操作相比，gPool池化层在投影向量$\mathbf{p}$中使用了额外的训练参数。

3.2 Graph Unpooling Layer：gUnpool

上采样操作对于U-Net这样的编码器-解码器网络非常重要。网络的编码器通常采用池化操作来减小feature map的大小，增加感受野。而在解码器中，需要对feature map进行上采样以恢复其原始分辨率。对于像图像这样的网格数据，有几种上采样操作，如deconvolution层( Image-to-image translation with conditional adversarial networks，2015 CVPR；Stacked what-where auto-encoders 2015)和unpooling层(Fully convolutional networks for semantic segmentation，2015 CVPR)。但是，目前在图数据上还没有这种操作。

为了在图数据上使用上采样操作，文中提出了graph unpooling(gUnpool)层，它执行gPool层的相反操作，将图恢复到原始结构：记录在相应的gPool层中选择的节点的位置，并使用这些信息将节点放回图中的原始位置。

graph unpooling层的逐层传播规则为：

$$X^{\ell +1}=\text{ distribute }\left(0_{N\times C},X^{\ell },\text{ id }\mathrm{x}\right)\text{\hspace{1em}(3)}$$

• $\mathrm{i}\mathrm{d}\mathrm{x}\in {\mathbb{Z}}^{\ast k}$对应了再gPool层中选择的$k$个节点
• $X^{\ell }\in {\mathbb{R}}^{k\times C}$是当前图的特征矩阵
• $0_{N\times C}$是为新图初始空的特征矩阵
• $\text{ distribute }\left(0_{N\times C},X^{\ell },\text{ id }\mathrm{x}\right)$根据存储在idx中的索引将$X^{\ell }$中的行向量分配到特征矩阵$0_{N\times C}$
• 在$X^{\ell +1}$中，具有idx中的索引的行向量按照$$中的行向量进行更新，而其他行向量保持值为0

• 图2是graph unpooling (gUnpool)层的示意图
• gPool层对具有7个节点的图进行下采样，从而得到具有4个节点的粗化图和选择的节点的位置信息。
• gUnpool层利用位置信息对未选择的节点使用空特征向量恢复原始的图结构。

3.3 Graph U-Nets Architecture 图U-Nets架构

U-Net这样的编译码器网络在像素级预测任务上有很好的性能，因为它们可以在保持局部空间信息的同时对高层特征进行编码和解码。文中在gPool和gUnpool层的基础上提出了用于节点分类任务的。

在graph U-Nets (g-U-Nets)架构中，首先应用一个图的embedding层将节点转换成低维表示，因为一些数据集的原始输入，如Cora通常有非常高维的特征向量。在图embedding层之后，通过堆叠几个编码块来构建编码器，每个编码块包含一个gPool层和一个GCN层。gPool层通过减少图的大小来编码高维特征，而GCN层负责从每个节点的一阶邻居聚合信息。在解码器部分，堆叠了与编码器部分数量相同的解码块。每个解码器块由一个gUnpool层和一个GCN层组成。gUnpool层将图恢复到更高分辨率的结构，而GCN层则聚合来自邻居的信息。在编码器和解码器层对应的块之间存在 skip-connections，这些连接将空间信息传输给解码器以获得更好的性能。skip-connections可以是feature map addition或concatenation。最后，使用一个GCN层和softmax函数进行最后的预测。

• 图3是g-U-Nets的一个示意图
• 输入图中的每个节点都有两个特征
• 使用GCN层将输入特征向量转换为低维表示，然后堆叠两个编码器块，每个块包含一个gPool层和一个GCN层。对于同一级别的块，编码器块使用skip connection来融合来自编码器块的低级空间特征。
• 在解码器部分，也有两个解码器块。每个块由gUnpool层和GCN层组成。
• 最后一层节点的输出特征向量是网络embedding，可用于节点分类、链路预测等多种任务。

3.4 Graph Connectivity Augmentation via Graph Power 通过图幂操作增加图的连接性

在gPool层中，对一些重要节点进行采样，以形成一个新的用于高级特征编码的图。由于在删除gPool中的节点删除了相关的边，因此图中的节点可能会变得相互隔离，这可能会影响后续层中的信息传播。当使用GCN层用于聚合来自邻居节点的信息的时，信息可能存在丢失。因此，需要增加池化了的图中节点之间的连接性。

为了解决上述问题，使用第$k$个图的幂${\mathbb{G}}^k$来增加图的连通性。该操作在距离最多$k$跳的节点之间建立链接(Subsampling for graph power spectrum estimation, 2016)。文中使用$k=2$，因为在每个gPool层之前有一个GCN层来聚合一阶邻居节点的信息。将公式（2）中的第5个公式替换为：

$$A^2=A^{\ell }{A}^{\ell },A^{\ell +1}=A^2(\text{ idx },\text{ idx })\text{\hspace{1em}(4)}$$

• $A^2\in {\mathbb{R}}^{N\times N}$代表图的2次幂

接下来，就可以对连通性较好的增广图进行图采样。

3.5 Improved GCN Layer 改进GCN层

在公式（1）中，使用的是添加了自循环的“renormalization”邻接矩阵$\hat{A}=A+I$
$$X_{\ell +1}=\sigma \left({\hat{D}}^{-\frac{1}{2}}\hat{A}{\hat{D}}^{-\frac{1}{2}}{X}_{\ell }{W}_{\ell }\right)\text{\hspace{1em}(1)}$$
考虑到节点自身的特征向量应该有更高的权重，因此将邻接矩阵改为$\hat{A}=A+2I$。

4 实验

研究内容

• 进行ablation研究，以检验gPool层、gUnpool层和图连接性增强对性能改进的贡献。
• 研究网络深度与节点分类性能的关系。
• 我们研究gPool层中涉及的额外参数是否会增加过拟合的风险。

任务

• transductive learning的节点分类任务（训练时，会使用到没有标记的数据集的图结构信息）
• inductive learning的图分类任务（训练时，只涉及有标记的数据集，不使用测试数据的图结构）

数据集

transductive learning的节点分类任务的数据集

inductive learning的图分类任务的数据集

实验设置

transductive learning的节点分类任务

• 由于三个数据集中的节点都与高维特征相关联，采用了一个GCN层来将它们简化为低维表示。
• 在编码器部分，堆叠了四个块，每个块由一个gPool层和一个GCN层组成。在四个gPool层中分别采样2000、1000、500、200个节点。
• 相应地，解码器部分也包含四个块。每个解码块由一个gUnpool层和一个GCN层组成。
• 使用addition运算跳过编码器和解码器部分块之间的连接。
• 最后，应用GCN层进行最终预测。
• 对于模型中的所有层，在每个GCN层之后使用identity激活函数（LGCN，2018）。
• 为了避免过拟合，使用权重为$\lambda =0.001$的$L_2$正则化。
• 邻接矩阵和特征矩阵的dorpout分别为0.8和0.08

inductive learning的图分类任务

• 和DGCNN中相同的实验设置
• 由于图的大小在图的分类任务中有所不同，在四个gPool层中采样节点的比例分别为90%、70%、60%和50%
• 特征矩阵的dropout保持率为0.3

性能研究

transductive learning的节点分类任务性能研究

• g-U-Nets模型由GCN、gPool和gUnpool层组成，不涉及更高级的图卷积层，如GAT。
• 与GCN相比，g-U-Nets在所有三个数据集上的性能都有显著提高，分别提高了2.9%、2.9%和0.6%。
• g-U-Nets和GCN之间的唯一区别是g-U-Nets使用了包含gPool和gUnpool层的编码器-解码器体系结构。这些结果证明了g-U-Nets在网络embedding中的有效性。

inductive learning的图分类任务性能研究

• 从结果可以看出，gPool方法在D&D和PROTEINS数据集上的性能优于DiffPool，分别提高了1.79%和1.43%。
• DiffPool-DET在COLLAB上的结果明显高于其他所有方法和其他两个DiffPool模型。
• 在三个数据集上，g-U-Nets都是最优的
• DiffPool中的训练利用链路预测的辅助任务来稳定模型性能，这体现了DiffPool模型的不稳定性。
• 在g-U-Nets的实验中，只使用图标签进行训练，而不需要任何辅助任务来稳定训练。

gPool层和gUnpool层的ablation研究

• GCN论文认为，当网络越深，GCN的性能越差，但也有人认为，表3中GCN的性能提高是由于使用了更深层次的网络架构。
• 研究gPool和gUnpool层对g-U-Nets性能的贡献。通过从g-U-Nets中删除所有gPool和gUnpool层来进行实验，从而导致只有GCN层的网络具有 skip connections。

• 结果表明，在Cora、citeeser和Pubmed数据集上，g-U-Nets的性能分别比没有gPool和gUnpool层的g-U-Nets好2.3%、1.6%和0.5%。
• 这些结果证明了gPool和gUnpool层对性能改进的贡献。

图连接性增强研究

• 在上述实验中，使用图连通性增强的gPool层，并且使用的是2次图幂。
• 对节点分类任务进行了实验，以研究基于g-U-Nets的图连通性增强的效果。
• 从gPool层删除了图连接增强，同时保持其他设置不变，以保证比较的公平性。

• 结果表明，缺乏图连通性增强会导致三个数据集的性能一致性地下降。
• 说明使用图的二次幂增强图的连通性有助于采样的图中节点间的信息传递。

Graph U-Nets深度研究

在g-U-Nets中，编码器和解码器部分的块数是一个重要的超参数，因此通过实验研究了网络深度与节点分类精度之间的关系。

• 从结果可以看出，网络越深，性能越高，直到深度达到4。
• 过拟合问题常发生在较深的网络中，当深度超过此值时，会抑制网络性能。
• 在图像分割中，通常使用深度为3或4的U-Net模型，这与实验中的选择是一致的。
• 表明了即使在非常浅的网络中，gPool和gUnpool层在接受野扩大和高级特征编码方面的能力。

Graph Pooling层的参数研究

• 结果表明，U-Net模型中的gPool层只增加了0.12%的额外参数，但性能可以提高2.3%。
• 因此，额外参数的增加是微不足道的，不会增加过拟合的风险。