Abstract

卷积神经网络（CNN）在各种领域取得了令人瞩目的成果。他们的成功得益于能够训练非常深的CNN模型的巨大推动力。
尽管取得了积极的成果，但CNN未能正确解决非欧几里德数据的问题。
为了克服这一挑战，利用图卷积网络（GCN）构建图来表示非欧几里德数据，并借用CNN的相关概念并应用它们来训练这些模型。
GCN显示出不错的结果，但由于梯度消失问题，它们仅限于非常浅的模型。因此，大多数最新型的GCN算法都不会超过3或4层。
作者提出了成功训练非常深层的GCN的新方法。他们借用CNN的概念，主要是residual / dense connections（残差、密集连接） 和 dilated convolutions（膨胀卷积、扩张卷积、空洞卷积） ，使它们能够适应GCN架构。

• residual / dense connections：解决由网络加深导致的梯度消失问题
• dilated convolutions：解决由于pooling而导致的空间信息丢失，把卷积核膨胀了，增大了感受野，但没有增加参数数量

一个空洞卷积的例子如下：

Standard Convolution with a 3 x 3 kernel (and padding)

Dilated Convolution with a 3 x 3 kernel and dilation rate 2

作者通过大量实验，展示了这些深层GCN框架的积极的效果。最后，使用这些新概念构建一个非常深的56层的GCN，并展示它如何在点云语义分割任务中显著地提升了性能（相当于最先进的3.7％mIoU|均交并比）。

1. Introduction

GCN网络在近几年发展迅猛。对GCN的研究主要在于两点：

• 应用：现实世界中非欧氏距离的数据激增，GCN的应用广泛
• 性能：GCN处理这些数据的局限性

GCN目前用于预测社交网络中的个体关系[37]、药物发现的模型蛋白[56，41]、提高推荐引擎的预测[25，52]、有效分割大规模点云[43]等领域。

CNN的成功的一个关键因素是能够设计和训练一个深层的网络模型。但是，现在还不清楚如何恰当地设计一个深层的GCN结构。目前，有一些研究工作研究了深度GCN的限制因素[20，44，55]。
堆叠多层图卷积会导致常见的梯度消失的问题。这意味着通过这些网络的反向传播会导致过度平滑（over-smoothing），最终导致顶点的特征收敛到相同的值[20]。由于这些限制，大多数最先进的GCN不超过4层[55]。

梯度消失在CNNs中并不是一个陌生的现象。它们也对此类网络的深度增长提出了限制。
ResNet[12]在追求非常深的CNN方面向前迈出了一大步，因为它引入了输入层和输出层之间的残差连接（ residual connection）。这些连接大大减轻了消失梯度问题。今天，ResNet可以达到152层及以上。
DenseNet[14]提供了一个扩展，这个网络引入了 across layers。更多的层可能意味着由于pooling而导致更多的空间信息丢失。这一问题也通过Dilated Convolutions(扩张/膨胀卷积)来解决[53]。
这些关键概念的引入对CNN的发展产生了实质性的影响，相信如果能很好地适应GCN，它们也会有类似的效果。

在论文中，作者提出了一个全面的方法的研究，允许训练非常深的GCN。并借用了成功训练深层CNN的相关概念，主要是residual connections, dense connections和dilated convolutions。
文中展示了如何将这些层合并到图框架中，并对这些层的添加对深度GCN的准确性和稳定性的影响进行了全面的分析。
为了展示这些层的适应性，作者将它们应用到现在流行的点云语义分割任务中。结果表明，添加residual connections, dense connections和dilated convolutions的组合，可以成功地训练高达56层的GCN（参见图1）。这个非常入的GCN将具有挑战性的S3DIS[1]点云数据集的最新技术提高了3.7%。

图1.针对7,14,28,56层GCN网络训练时的loss变化图。左图是不使用残差连接的，可以看出，层数越多，loss越难降低；右图是使用了残差连接的，可以看出，对于所有深度的层，loss达到持续平稳。

Contributions

• （1）采用residual connections, dense connections和dilated convolutions以适应GCN。
• （2）对点云数据进行了大量的实验，展示了这些新层对训练深GCN的稳定性和性能的影响。使用点云语义分割作为实验框架。
• （3）展示了这些新概念如何帮助构建一个56层的GCN（一个最大限度的最深的GCN架构），并在S3DIS数据集上实现接近4%的性能提升。

2. Related Work

在社交网络[37]中，图代表了基于共同利益/关系的个人之间的联系。这种连接是非欧氏距离和非规则的。GCN有助于更好地评估社交网络图节点之间的边缘优势，从而使个人之间的联系更加准确。
图也被用来模拟化学分子结构[56，41]。了解这些分子的生物活性对药物发现有重大影响。图的另一个流行用法是在推荐引擎[25，52]中，用户交互的精确建模可以改进的产品推荐。图也是语言处理中常用的表示方式[2，24]，用于表示单词、句子和较大文本单位之间的复杂关系。

GCN在计算机视觉中也有许多应用，在场景图生成（scene graph generation）中，对象之间的语义关系是通过图来建模的。其中，图用于检测和分割图像中的对象，并预测对象pairs之间的语义关系[45、49、21]。场景图也有助于相反过程，在相反过程中，根据场景的图形表示来重构图像[18]。图也被用来模拟人的关节，以便在视频中识别动作[48，17]。

GCN是点云处理的完美候选。考虑到点云数据的非结构化性质，它提出了一个具有代表性的挑战。通过用多个二维视图（36、10、3、23）表示三维数据，或通过像素化（5、30、33、38），可以尝试从三维数据创建结构。最近的工作重点是直接处理无序点云表示[28、31、9、15、50]。Wang等人最近提出的EdgeConv方法[43]将GCN应用于点云。特别地，他们提出了一种用于点云语义分割的动态边缘卷积算法（dynamic edge convolution algorithm）。该算法利用点特征之间的距离，动态计算每个图层的邻接节点。这项工作展示了GCN对于点云相关应用程序的潜力，并在点云分割任务中击败了最先进的技术。与大多数其他工作不同，EdgeConv不依赖RNNs或复杂的点聚合方法。

目前的GCN算法（包括EdgeConv）仅限于浅层。最近的很多工作试图训练更深层次的GCN。
例如

• Kipf等人训练用于节点分类的半监督GCN模型[19]。作者展示了当使用超过3层时性能如何降低。
• Pham等人[27]针对关系学习中的集体分类提出了Column Network（CLN）。作者展示了10层达到峰值性能；但是，对于更深的图，性能会下降。
• Rahimi等人[32]在社交媒体图中开发了一个用于用户地理定位的公路GCN(Highway GCN)，作者在各层之间添加了“Highway”门，以促进梯度流。 即使有了这些门，在达到6层深度后，性能也会下降。
• Xu等人[47]开发了一个用于表示学习的跳跃知识网络(Jump Knowledge Network)。他们提出了一种基于图结构的节点邻域选择策略。与其他作品一样，他们的网络仅限于少量的层（6）。
• 为此，Li等人[20]研究了GCN的深度限制。他们表明，深度GCN会导致过度平滑，从而导致每个连接内顶点的特征收敛到相同的值。
• 其他工作[44，55]也显示了叠加多个GCN层的局限性，这导致了反向传播的高度复杂性和常见的消失梯度问题。

在CNN的早期，也出现了许多目前面临的GCN难题（如梯度消失、有限的感受野等）。这篇文章目的是要弥补了这一不足，这些缺点中的大多数可以通过借鉴CNN的几个技巧来弥补。随着ResNet的推出，Deep CNN在性能上获得了巨大的提升[12]。通过增加层的输入和输出之间的residual connections（残差连接），ResNet减轻了梯度消失的问题。DenseNet[14]将这一想法进一步发展，并增加了connections across
layers（跨层连接）。 Dilated Convolutions[53]是一种较新的方法，它通过增加接感受野而不损失分辨率，从而显著提高了性能，特别是在图像到图像的翻译任务（如语义分割[53]）中。作者展示了如何从这些由CNN引入的概念中获益，主要是 residual/dense connections和dilated convolutions，以训练非常深的GCN。他们通过扩展Wang等人[43]的工作来支持自己的工作，即达到一个更深入的GCN，从而显著提高其性能。文中对点云语义分割任务的大量实验验证了这些思想可用于任何通用图中。

3. Methodology

Graph Convolution Networks

受CNN启发，GCN打算通过聚集顶点邻域的特征来提取高级特征。GCNs通过将每个顶点$v$v与特征向量$h_v \in \mathbb{R}^D$hv​∈RD关联来表示顶点，其中$D$D是特征维数。因此，图G作为一个整体，可以通过连接所有顶点的特征来表示，即$H_G=[h_{v_1},h_{v_2},...,h_{v_n}]^T \in \mathbb{R}^{N×D}$HG​=[hv1​​,hv2​​,...,hvn​​]T∈RN×D，其中$N$N是集合$V$V的基数，可以将第$l$l层的一般图卷积运算$\mathcal{F}$F表示为聚集和更新操作，

$G_{l+1}=\mathcal{F}(G_l,W_l)=Update(Aggregate(G_l,W_l^{agg}),W_l^{update}) \qquad(1)$Gl+1​=F(Gl​,Wl​)=Update(Aggregate(Gl​,Wlagg​),Wlupdate​)(1)

• $G_l=(V_l,\varepsilon_l)$Gl​=(Vl​,εl​)和$G_{l+1}=(V_{l+1},\varepsilon_{l+1})$Gl+1​=(Vl+1​,εl+1​)分别是第$l$l层的输入和输出
• $W_l^{agg}$Wlagg​和$W_l^{update}$Wlupdate​分别是可训练的聚合和更新函数的权重，它们是GCNs的关键部分

在大多数GCN框架中，聚合函数用于从顶点的邻域中编译信息；更新函数对聚合信息执行非线性转换，以计算顶点的新表示。这两种函数有不同的变体。例如，聚合函数可以是mean
aggregator[19]、max-pooling aggregator[29、11、43]、attention aggregator[40]或LSTM aggregator[26]。更新函数可以是多层感知器[11，7]，门控网络[22]等。更具体地说，通过对所有$v_{l+1} \in V_{l+1}$vl+1​∈Vl+1​的相邻顶点特征进行聚合，计算出各层的顶点表示，如下所示：

$h_{v_{l+1}} = \phi (h_{v_l}, \rho({h_{u_l}|u_l∈ \mathcal{N}(v_l)},h_{v_l},W_\rho ), W_\phi) \qquad(2)$hvl+1​​=ϕ(hvl​​,ρ(hul​​∣ul​∈N(vl​),hvl​​,Wρ​),Wϕ​)(2)

• $\rho$ρ是一个顶点特征的聚合函数
• $\phi$ϕ是一个顶点特征的更新函数
• $h_{v_l}$hvl​​和$h_{v_{l+1}}$hvl+1​​分别是第$l$l层和$l+1$l+1层的顶点特征
• $\mathcal{N}(v_l)$N(vl​)是第$l$l层的顶点$v$v的邻居节点的集合
• $h_{u_l}$hul​​是由$W_\rho$Wρ​参数化的邻居顶点的特征。
• $W_\phi$Wϕ​包含了这些函数的可训练的参数

本文使用一个简单的max-pooling顶点特征聚集器，在没有可学习参数的情况下，来聚集中心顶点与其所有相邻顶点之间的特征差异。使用的更新器是一个有batch normalization[16]的多层感知器（MLP）和一个ReLU作为**函数。文中还对不同的GCN变体进行了分析。（详见文章附录A。）

Dynamic Edges

如前所述，大多数GCN只在每次迭代时更新顶点特征。最近的工作[35，43，39]表明，与具有固定图结构的GCN相比，动态图卷积可以更好地学习图的表示。例如，ECC（Edge-Conditioned Convolution，边缘条件卷积）[35]使用动态边缘条件滤波器（dynamic edge-conditional filters）学习特定边的权重矩阵。EdgeConv[43]在每个EdgeConv层之后，找到特征空间中最近的邻居来重建图形。为了学习点云的生成，Graph-Convolution GAN（生成对抗网络）[39]还应用k-NN图来构造每一层顶点的邻域。作者发现动态变化的GCN邻居有助于缓解过度平滑的问题，并产生一个有效的更大的感受野。在本文的框架中，他们提出通过在每一层的特征空间中通过一个Dilated k-NN来重新计算顶点之间的边，以进一步增加receptive field。

3.1. Residual Learning for GCNs

设计深度GCN架构[44，55]是图学习空间中的一个开放问题。最近的工作[20，44，55]表明GCN不能很好地扩展到深层结构，因为叠加多个图卷积层会导致反向传播的高度复杂性。因此，大多数最先进的GCN模型的深度不超过3层[55]。受ResNet[12]、DenseNet[14]和Dilated Convolutions[53]巨大成功的启发，作者将这些想法转移到GCN，以释放它们的全部潜能。这使得更深层次的GCN能够很好地聚合并获得优异的性能。

在最初的图形学习框架中，底层映射$\mathcal{H}$H（以图形为输入并输出一个新的图形表示（参见等式（1））是需要学习的。作者提出了一个图的残差学习框架，通过拟合另一个残差映射$\mathcal{F}$F来学习所需的底层映射$\mathcal{H}$H。在$G_l$Gl​通过残差映射$\mathcal{F}$F变换了后，进行逐点加法得到$G_{l+1}$Gl+1​

$G_{l+1}=\mathcal{H}(G_{l},W_l)=\mathcal{F}(G_l,W_l)+G_l \qquad(3)$Gl+1​=H(Gl​,Wl​)=F(Gl​,Wl​)+Gl​(3)
残差映射$\mathcal{F}$F把一个图作为输入并为下一层输出一个残差图的表示$G_{l+1}^{res}$Gl+1res​。$W_l$Wl​是第$l$l层的一组可学习参数。在实验中，作者将这个残差模型称为ResGCN。
$G_{l+1}^{res}=\mathcal{F}(G_l,W_l):=G_{l+1}-G_l \qquad(4)$Gl+1res​=F(Gl​,Wl​):=Gl+1​−Gl​(4)

3.2. Dense Connections in GCNs

DenseNet[14]提出了一种更有效的方法，通过密集的连接来改进信息流并重用层之间的特征。DenseNet的启发下，文中采用了类似的思想到GCNs中，以利用来自不同GCN层的信息流。特别地，定义