论文笔记：LCML 2020 Simple and Deep Graph Convolutional Networks

前言

图卷积网络(GCNs)是一种针对图结构数据的强大的深度学习方法。最近，GCNs和后续的变体在实际数据集中的各种应用领域显示了优越的性能。大多数目前的GCN模型是浅层结构的，由于过度平滑的问题。本文研究了深度图卷积网络的设计与分析问题，提出了GCNII，它是普通GCN模型的扩展，具有两种简单而有效的技术:初始残差和恒等映射。这两种技术有效地缓解了过度平滑的问题。实验表明，深层GCNII模型在各种半监督和全监督任务上的性能优于目前最先进的方法。

论文链接：https://arxiv.org/abs/2007.02133
github：https://github.com/chennnM/GCNII

1. 背景

首先是两种基础的图数据学习模型：GCN和GAT，前者是CNN在图数据结构上的变体，通过信号处理的理论推导得到适用于图的卷积操作的基本范式，后者是基于注意力机制聚合信息实现信息提取的一种有效方法。但是两种方法在只有两层神经网络时已经达到了性能最优。这种浅层的模型限制了从高阶邻居节点提取信息的能力，但是堆叠更多的层数并添加非线性**会导致模型能力的下降，这种现象被称为过平滑(over-smoothing)，表明随着层数的增加，GCN中节点的表示方式倾向于收敛到某个值，从而变得不可区分。

最近的工作致力于解决过平滑问题，JKNet使用Dense的思想进行稠密连接组合每个层的输出，以保持节点表示的位置。DropEdge提出，通过从输入图中随机删除一些边，可以减轻过度平滑的影响。实验表明，随着网络深度的增加，这两种方法可以降低性能下降的速度。然而，对于半监督的任务，最先进的结果仍然是通过浅层模型实现的，因此增加网络深度所带来的效益仍然存在疑问。

其他方法从另一个角度出发，出发点是结合深层传播与浅层神经网络。SGC 试图通过在单个神经网络层中应用图卷积矩阵的k次幂来捕获图中的高阶信息。PPNP和APPNP用个性化的PageRank矩阵替换图卷积矩阵的幂来解决过平滑问题。GDC进一步扩展了APPNP，将个性化PageRank推广为任意图扩散过程。但是，这些方法只是将每一层的相邻特征进行线性组合，失去了深度非线性架构强大的表达能力，仍然是浅模型。

总之，如何设计一个GCN模型来有效地防止过度平滑，并在真正深度的网络结构中实现最先进的结果，仍然是一个有待解决的问题。由于这一挑战，在设计新的图形神经网络时，网络深度究竟是一种资源还是一种负担甚至还不清楚。在本文中，通过证明普通的GCN可以通过两个简单而有效的修改扩展到一个深层模型，从而对这个开放问题给出了一个肯定的答案。特别地，提出了通过初始残差和身份映射(GCNII)的图卷积网络，这是一种解决过度平滑问题的深度GCN模型。在每一层，初始残差从输入层构建一个跳跃连接，而标识映射在权值矩阵中添加一个单位矩阵。实验研究表明，当增加GCNII的网络深度时，这两种简单得令人惊讶的技术可以防止过度平滑，并一致地提高其性能。特别是，深层GCNII模型在各种半监督和完全监督的任务上实现了最新的最先进的结果。

2. 参数设置

简单无向图的表示 G = ( V , E ) G = (V,E) G=(V,E) 包含 n n n 个节点， m m m 条边 ，加上节点自连接的图表示为 G ~ = ( V , E ~ ) \widetilde{G} = (V,\widetilde{E}) G =(V,E )，使用 { 1 , . . . n } \{1,...n\} {1,...n} 表示 G G G 和 G ~ \widetilde{G} G 的 I D s IDs IDs， d j d_j dj​， d j + 1 d_j+1 dj​+1 分别表示简单无向图和带自环图的节点的度， A A A 代表图的邻接矩阵， D D D 代表图的度矩阵(对角矩阵) A ~ = A + I \widetilde{A}=A+I A =A+I ， D ~ = D + I \widetilde{D}=D+I D =D+I 代表自环图的邻接矩阵和度矩阵。 X ∈ R n × d X \in \mathcal{R}^{n \times d} X∈Rn×d 代表节点特征信息矩阵 ，归一化的图拉普拉斯矩阵为 L = I n − D − 1 2 A D − 1 2 L=I_n-D^{-\frac{1}{2}}AD^{-\frac{1}{2}} L=In​−D−21​AD−21​ ，具有特征分解的对称正半正定矩阵是 U Λ U T UΛU^T UΛUT， Λ Λ Λ 是由归一化拉普拉斯矩阵特征值组成的度矩阵， U ∈ R n × n U \in \mathcal{R}^{n \times n} U∈Rn×n。 x x x 为信号变量，卷积核定义为 g γ ( L ) ∗ x = U g γ ( Λ ) U T x g_{\gamma}(L)*x = U_{g_{\gamma}}(Λ)U^Tx gγ​(L)∗x=Ugγ​​(Λ)UTx ，其中 γ ∈ R n \gamma \in \mathcal{R}^n γ∈Rn 对应一个光谱滤波系数向量。

3. 图卷积

3.1 传统图卷积(以切比雪夫多项式的一阶近似为卷积核)由Kipf于2017年提出

以切比雪夫不等式的一阶近似为卷积核进行化简。

可参考：https://blog.csdn.net/qq_44015059/article/details/105574250

与上式对应进行化简，其中图中(4)就对应该论文最后的形式

P ~ = D ~ − 1 2 A D ~ − 1 2 \widetilde{P}=\widetilde{D}^{-\frac{1}{2}}A\widetilde{D}^{-\frac{1}{2}} P =D −21​AD −21​

3.2 SGC(传统图卷积的简化形式，消除不必要的非线性**和参数矩阵，更新为线性关系)

结果表明，经过K层的叠加，GCN在 G ~ \widetilde{G} G 的图谱域中对应一个 K K K 阶的固定多项式滤波器。具体来说 L ~ = I n − D ~ − 1 2 A D ~ − 1 2 \widetilde{L}=I_n-\widetilde{D}^{-\frac{1}{2}}A\widetilde{D}^{-\frac{1}{2}} L =In​−D −21​AD −21​

其实就是 I n − L ~ = P ~ = D ~ − 1 2 A D ~ − 1 2 I_n-\widetilde{L}=\widetilde{P}=\widetilde{D}^{-\frac{1}{2}}A\widetilde{D}^{-\frac{1}{2}} In​−L =P =D −21​AD −21​

3.3 APPNP

利用个性化PageRank推导出一个 k k k 阶固定滤波器，设 f θ ( X ) f_\theta(X) fθ​(X) 表示两层全连通神经网络在特征矩阵 X X X 上的输出，定义PPNP模型为

由于个性化PageRank的特性，该过滤器保持了局部性，适合于分类任务。提出了APPNP

其中 H ( 0 ) = f θ ( X ) H^{(0)}=f_{\theta}(X) H(0)=fθ​(X)，PPNP和APPNP通过解耦特征转换和传播，可以在不增加神经网络层数的情况下聚合多跳邻居的信息。

3.4 JKNet

第一个深度GCN框架由这篇文章提出。在最后一层，JKNet结合了之前所有的表示 [ H ( 0 ) , . . . , H ( K ) ] [H^{(0)},...,H^{(K)}] [H(0),...,H(K)]。证明了

• 1)K层的普通GCN模型模拟自循环图 G ~ \widetilde{G} G
• 2)JKNet通过结合前一层的所有表示，缓解了过度平滑的问题。

3.5 DropEdge

最近的一项工作表明，从 G ~ \widetilde{G} G 中随机移除一些边缘会减慢过度平滑的收敛速度。设 P ~ d r o p \widetilde{P}_{drop} P drop​表示随机去掉某条边的重整化图卷积矩阵，具有DropEdge的普通GCN定义为

4. GCNII Model

传统GCN模拟一个 K K K 阶的多项式滤波器来进行图卷积操作 ( ∑ l = 0 K θ l L ~ l ) x (\sum_{\mathcal{l}=0}^K\theta_l\widetilde{L}^l)x (∑l=0K​θl​L l)x，其中在图谱域 G ~ \widetilde{G} G 的参数 θ \theta θ 固定。固定的系数限制了多层GCN模型的表达能力，从而导致过度平滑。为了将GCN扩展到一个真正深入的模型，需要使GCN能够表达一个具有任意系数的K阶多项式滤波器。这可以通过两种简单的技术来实现：残差链接和身份映射。形式上将GCNII的第1层定义为

其中 α l \alpha_l αl​ 和 β l \beta_l βl​ 是两个超参数， P ~ = D ~ − 1 2 A D ~ − 1 2 \widetilde{P}=\widetilde{D}^{-\frac{1}{2}}A\widetilde{D}^{-\frac{1}{2}} P =D −21​AD −21​，与传统的GCN相比，有两点修正：

1. 在进行信息聚合 P ~ H ( l ) \widetilde{P}H^{(l)} P H(l) 的基础上增加了第一层 H ( 0 ) H^{(0)} H(0) 的残差链接
2. 在权重参数矩阵上增加了一个恒等式映射 I n I_n In​ 到 l l l 层权重矩阵 W ( l ) W^{(l)} W(l) 中。

4.1 Initial residual connection

对特征矩阵进行多次非线性操作会导致过拟合，从而导致性能下降

与其使用剩余连接来携带来自前一层的信息，不如构建一个到初始表示 H ( 0 ) H^{(0)} H(0)的连接。初始剩余连接确保每个节点的最终表示至少保留了来自输入层的部分信息，即使我们堆叠了许多层。在实践中，我们可以简单地设置 α l = 0.1 o r 0.2 \alpha_l=0.1 or 0.2 αl​=0.1or0.2，以便每个节点的最终表示至少包含输入特性的一部分。同时 H ( 0 ) H^{(0)} H(0) 不一定是特征矩阵X。如果特征维数 d d d 较大，我们可以在 X X X 上应用全连通神经网络，在正向传播前得到低维的初始表示 H ( 0 ) H(0) H(0)。也就是初始维度较大的时候可以先进行一个嵌入进行降维

4.2 Identity mapping

• 与ResNet的动机相似，身份映射确保深度GCNII模型至少实现与其浅层版本相同的性能。特别是，通过设置 β l \beta_l βl​ 足够小，足够深的GCNII忽略了权重矩阵 W ( l ) W^{(l)} W(l)，本质上模拟了APPNP。
• 特征矩阵的不同维数之间频繁的相互作用会降低模型在半监督任务中的性能。将平滑的表示 P ~ H ( l ) \widetilde{P}H^{(l)} P H(l)直接映射到输出可以减少这种交互。
• 在半监督任务中，恒等映射被证明是特别有用的。例如线性的ResNet可以表示为 H ( l + 1 ) = H ( l ) ( W ( l ) + I n ) H^{(l+1)}=H^{(l)}(W^{(l)}+I_n) H(l+1)=H(l)(W(l)+In​)
• 1)最优权矩阵 W ( l ) W^{(l)} W(l) 具有小范数； 2)唯一的临界点是全局极小值。第一个性质允许我们将强正则化 W ( l ) W^{(l)} W(l) 避免过度拟合，而后者在训练数据有限的半监督任务中是可取的。
• 理论上证明了 K K K 层GCNS的节点特征会收敛到一个子空间，从而导致信息丢失。特别地，收敛速度依赖于 s K s^K sK， s s s 是权重矩阵 W ( l ) , l = 0 , . . . , K − 1 W^{(l)},l=0,...,K-1 W(l),l=0,...,K−1 的最大奇异值。通过将 W ( l ) W^{(l)} W(l) 替换为 ( 1 − β l ) I n + β l W ( l ) (1-\beta_l)I_n+\beta_lW^{(l)} (1−βl​)In​+βl​W(l) 并对 W ( l ) W^{(l)} W(l) 施加正则化，强制 W ( l ) W^{(l)} W(l) 的范数变小。因此， ( 1 − β l ) I n + β l W ( l ) (1-\beta_l)I_n+\beta_lW^{(l)} (1−βl​)In​+βl​W(l) 的奇异值将接近1。因此，最大奇异值s也将接近1，这意味着 s K s^K sK 过大，信息损失得到缓解。

设置 β l \beta_l βl​ 的原则是确保权重矩阵的衰减随着层数的增加而自适应地增加。在实践中，我们设置 β ℓ = log ⁡ ( λ ℓ + 1 ) ≈ λ ℓ \beta_{\ell}=\log \left(\frac{\lambda}{\ell}+1\right) \approx \frac{\lambda}{\ell} βℓ​=log(ℓλ​+1)≈ℓλ​，其中λ是一个超参数。

4.3 Connection to iterative shrinkage-thresholding

最近，已经有了以优化为灵感的网络结构设计工作。其思想是，前馈神经网络可以被视为最小化某些函数的迭代优化算法，并且假设更好的优化算法可能会导致更好的网络结构。因此，数值优化算法中的理论可能会启发设计出更好、更易解释的网络结构。

与压缩感知类似，我们认为 x x x 是我们试图恢复的信号， B B B 是测量矩阵， y y y 是我们观察到的信号。
在实验中， y y y 是节点的原始特征， x x x 是嵌入网络尝试学习的节点。与标准回归模型不同，设计矩阵 B B B 是未知参数，将通过反向传播学习。因此，这与稀疏编码问题的相同，稀疏编码问题已被用于设计和分析CNN。迭代收缩阈值算法是解决上述优化问题的有效算法，其中第 ( t + 1 ) (t+1) (t+1) 次迭代的更新为：

这里 μ t \mu_t μt​ 是步长， P β ( ⋅ ) ( β > 0 ) P_{β}(·)(β>0) Pβ​(⋅)(β>0))是入门级软阈值函数：

现在，如果我们用 W W W 重新参数化 − B T B -B^TB −BTB ，上述更新公式将变得非常类似于我们的方法中使用的公式。更具体地说， X t + 1 = P µ t λ ( ( I + µ t W ) X t + µ t B T y ) X^{t+1}=P_{µtλ}((I+µ_tW)X_t+µ_tB^Ty) Xt+1=Pµtλ​((I+µt​W)Xt​+µt​BTy) 其中， µ t B T y µ_tB^Ty µt​BTy 对应于初始残差，而 ( I + µ t W ) (I+µ_tW) (I+µt​W) 对应于模型(5)中的恒等映射。软阈值算子作为非线性**函数，类似于RELU的**效果。

Spectral Analysis 略，感兴趣可以去看一看原文

5. 实验

除了上面提到过的GCNII形式，在实验的时候又提出了上述的一种变种，定义如下

6. 结论

本文提出了GCNII，这是一个简单而深入的GCN模型，可以通过初始剩余连接和标识映射防止过度平滑。理论分析表明，GCNII可以表示任意系数的K阶多项式滤波器。对于具有多层的普通GCN，度数较高(边的交互关系更丰富)的节点更有可能遭遇过度平滑。实验表明，深层GCNII模型在各种半监督和全监督任务上取得了最新的结果。未来工作的有趣方向包括将GCNII与注意机制结合起来，以及用ReLU操作分析GCNII的行为。