深度图卷积网络系列文章（二）---DropEdge:Toward Deep Graph Convolutional Networks on Node Classification
深度图卷积网络系列文章（二）---DropEdge:Toward Deep Graph Convolutional Networks on Node Classification
DropEdge:关于节点分类的深度图卷积网络
今天分享的一篇文章是DropEdge:Toward Deep Graph Convolutional Networks on Node Classification，ICLR2020。
文章地址：https://iclr.cc/virtual_2020/poster_Hkx1qkrKPr.html
本文提出了一种随机边删除技术，通过随机去掉一定比率的边，DropEdge增加了输入数据的多样性，以防止过拟合，并减少了图形卷积中的消息传递，以缓解过平滑。
目前大部分图卷积网络都是浅层网络，即使使用残差连接，模型的分类效果也会随着深度的增加而变差。图卷积无法做到过深的原因是过拟合和过平滑，过拟合削弱了小数据集的泛化能力，随着网络深度的增加，过平滑会使输出表示与输入特征分离，阻碍了模型的训练。
虚线部分是原始的 4 层和 8 层 GCN 在 Cora 数据集上的训练曲线（这里为了更好展示过拟合和过平滑，取消了 GCN 层中的 bias），可以看到，在 GCN-4 上，验证集的损失函数在训练经过一定轮数后反向增长。这个增长是优于过拟合的。而在 GCN-8 上，训练集的损失函数则根本没有下降，这是因为过平滑的存在，导致 GCN-8 上训练失效。
过拟合
拟合训练数据的效果很好，但是对测试数据的推广很差，例如GCN-4。
过平滑
GCN的思想是聚合邻居节点和节点自身的特征信息来学习节点的表示，所以随着网络的加深，节点的表示具有趋同性，节点之间的区别会变小。最终，所有节点将会收敛到一个固定点，这样节点的表示便与输入特征无关，并且也会导致梯度消失，如GCN-8。
DropEdge
随机边删除技术，在每个epoch随机地从输入图中删除一定数量（固定比例）的边，就像一个数据增强器，同时也是一个消息传递减少器。DropEdge可以与其它骨干模型（GCN/ResGCN/GraphSAGE/JKNet）一起配置，虽然整体的精度还是随着层数的增加而降低，但是相对来说每一层的精度都提高了，那么网络的深度相对来说就会提高。
形式上，随机地选取邻接矩阵
A
A
A的
V
p
V_p
Vp个非零元素，将其置0。其中
V
V
V是边的总数，
p
p
p是删除率，删除之后得到的邻接矩阵为
A
d
r
o
p
A_{drop}
Adrop，那么有
A
d
r
o
p
=
A
−
A
′
A_{drop}=A-A'
Adrop=A−A′。其中
A
′
A'
A′是一个由原始边
ϵ
\epsilon
ϵ中大小为
V
p
V_p
Vp的随机子集展开的稀疏矩阵。我们也对
A
d
r
o
p
A_{drop}
Adrop进行了归一化，得到了
A
^
d
r
o
p
{\hat{A}}_{drop}
A^drop。取代
H
l
+
1
=
σ
(
A
^
H
l
W
l
)
H^{l+1}=\sigma ( \hat{A}H^{l}W^{l})
Hl+1=σ(A^HlWl)中的
A
^
\hat{A}
A^，则公式变为
H
l
+
1
=
σ
(
A
^
d
r
o
p
H
l
W
l
)
H^{l+1}=\sigma ({\hat{A}}_{drop}H^{l}W^{l})
Hl+1=σ(A^dropHlWl)，其中的
A
^
d
r
o
p
{\hat{A}}_{drop}
A^drop用于传播和训练，当验证和测试时，DropEdge不再使用。
数据增强器
在训练过程中对原始图中的边进行不同的随机删除，也就增强了输入数据的随机性和多样性，可以缓解过拟合的问题。
消息传递减少器
相邻节点之间的消息传递是通过边实现的，随机删除一些边可以让节点的连接更加稀疏，在一定程度上缓解了过平滑问题。
Layer-wise DropEdge
上面的DropEdge公式是所有层共享一个邻接矩阵。实际上，我们可以对每个单独的层执行dropedge。不同的层可以有不同的邻接矩阵。这种分层的版本带来了更多的随机性和原始数据的变形。实验中将layer-wise DropEdge和原始的DropEdge进行了对比。
DropEdge vs Dropout
Dropout是对特征向量中的某些维度随机置零，可以缓解过拟合，但是不能缓解过平滑，因为它没有改变邻接矩阵。DropEdge可以看成Dropout向图数据的推广，将删除特征维度变换成删除边，有助于缓解过拟合和过平滑问题。实际上两者是互补关系，实验中对两者进行了比较。
实验结果
表1总结了所有数据集的结果。由于空间限制，我们只报告了2/8/32层模型的性能。
另外，没有DropEdge的32层IncepGCN导致了内存不足(OOM)问题，而有DropEdge的模型却幸存了下来，这显示了DropEdge通过使邻接矩阵稀疏来节省内存消耗的优势。
在图2a中，我们通过DropEdge在不同层数的每个数据集上计算了所有主干的平均提升值。例如，在Citeseer上，DropEdge为更深层的架构提供了进一步的改进;对于2层的模型，它获得了平均0.9%的改进，而对于64层的模型，它获得了显著的13.5%的改进。
此外，Cora上所有四层模型的验证损失如图2b所示。应用DropEdge后，训练期曲线明显下降，这也解释了DropEdge有减轻过拟合的作用。
DropEdge与SOTAs的准确度(%)比较。括号中的数字为有DropEdge模型的网络深度。
图3a表示随着层数的增加，GCN中的过度平滑现象变得更加严重，这与我们的推测是一致的。与没有DropEdge（
p
=
0
p = 0
p=0）的模型相比，具有DropEdge（
p
=
0.8
p = 0.8
p=0.8）的模型显示的距离更长，收敛速度较慢，这暗示了DropEdge对缓解过度平滑的重要性。
图3b显示了150次训练后的结果。对于不带DropEdge的GCN，第5层和第6层的输出之间的差异等于0，这表示隐藏特征已收敛到某个固定点。相反，带有DropEdge的GCN的效果令人惊叹，因为当层数增加时，dislance不会一直为0。它可能已经成功地学习了有意义的节点表示，也可以通过图3c中的训练损失来验证。
我们对GCN-4进行了消融研究，验证损失如图4a所示。Dropout和DropEdge都能够促进GCN的训练，而DropEdge的改善更为显著。如果同时采用，则损失进一步降低，说明Dropedge与Dropout的兼容性。
从图4b中可以看出，LW DropEdge比原始版本的训练损失更低，而两个模型之间的验证值是可以比较的，这说明LW DropEdge比原始版本的DropEdge更有利于训练。然而。我们宁愿使用DropEdge而不是LW变体，这样不仅避免了过度拟合的风险，而且降低了计算复杂度，因为LW DropEdge需要对每一层进行采样，花费更多的时间。