[论文笔记]Simple and Deep Graph Convolutional Networks (GCNII) 原理

GCNII Note

参考：

Paper: Simple and Deep Graph Convolutional Networks (arxiv.org)

【论文阅读笔记】Simple and Deep Graph Convolutional Networks - 程序员大本营 (pianshen.com)

Paper

Motivation

• 目前大多数的GCN模型都是浅层的，如GCN，GAT模型都是在2层时取得最优效果，随着加深模型效果就会大幅度下降，经研究GCN随着模型层次加深会出现Over-Smoothing问题，Over-Smoothing既相邻的节点随着网络变深就会越来越相似，最后学习到的nodeembedding便无法区分。

• 不管是更多层数或者添加非线性变换，都会导致模型的准确性降低，这种现象就被称作过度平滑（oner-smoothing）。即随着层数的增加，GCN节点的表示趋向于收敛到一个特定值，并因此难以区分。至于为什么会这样，一种比较合理的解释是：这些模型都可以看作是一些滤波器，而这些滤波器所模拟的lazy随机游走会最终收敛到一个稳定的向量，因而导致了无法区分出不同的节点。并且，高度节点由于从邻居获得更多的信息，所以更容易出现过平滑问题。
  而模型过浅，我们就无法从高阶邻居中提取信息了。

• Quantitative Metric for Smoothness给Over-smoothness提出一个定量的指标$SVMG $ %3D%5Cfrac%20%7B1%7D%7B2%7D%5ClVert%20%5Cfrac%7Bx_i%7D%7B%5ClVert%20x_i%5CrVert%7D-%5Cfrac%7Bx_j%7D%7B%5ClVert%20x_j%5CrVert%7D%5CrVert%2C%5C%5C%0ASVM_i%3D%5Cfrac%7B1%7D%7Bn-1%7D%5Csum%7Bj%5Cin%20V%2C%20j%5Cneq%20i%7DD(xi%2Cx_j)%2C%5C%5C%0ASVM_G%3D%5Cfrac%7B1%7D%7Bn%7D%5Csum%7Bi%5Cin%20V%7DSVMi%0A#card=math&code=D%28x_i%2Cx_j%29%3D%5Cfrac%20%7B1%7D%7B2%7D%5ClVert%20%5Cfrac%7Bx_i%7D%7B%5ClVert%20x_i%5CrVert%7D-%5Cfrac%7Bx_j%7D%7B%5ClVert%20x_j%5CrVert%7D%5CrVert%2C%5C%5C%0ASVM_i%3D%5Cfrac%7B1%7D%7Bn-1%7D%5Csum%7Bj%5Cin%20V%2C%20j%5Cneq%20i%7DD%28xi%2Cx_j%29%2C%5C%5C%0ASVM_G%3D%5Cfrac%7B1%7D%7Bn%7D%5Csum%7Bi%5Cin%20V%7DSVM_i%0A)

衡量了图中任意两个节点之间的欧氏距离之和，越小表示图学习时Over-Smoothing越严重，当时，图中所有节点完全相同，也可以从图中看出随着层次的加深，的值越来越小。

• 对于过平滑的研讨方向：

  1. 第一类大方向是沿着ResNet中的剩余连接以及图的正则化等方法进行扩展和思考。

     • skip-connection。一般是把当前层的结果和上一层的结果进行连接/拼接，这样，既可以保留之前的运算结果，又可以加速模型在训练过程中的收敛速度。
     • JKNet。保存每一层的运算结果，最后统一对所有层的结果进行一个连接，可以减轻过平滑问题。
     • DropEdge。训练时随机丢弃途中的一些边，是一种图数据增强的方法。

  2. 第二类大方向是浅层模型中的深度传播方法。

     • SGC试图通过在单个神经网络层中应用图卷积矩阵的 k 次幂来捕获图中的高阶信息。

     • PPNP和APPNP用自定义的PageRank矩阵代替图卷积矩阵的幂来解决过平滑问题。

     • GDC进一步扩展了APPNP，将自定义PageRank推广到任意图扩散过程。
       结合 deep propagation 和浅层网络，但是这些网络只是将每一层的相邻特征进行线性组合，丢失了深度非线性结构强大的表示能力；也就是说他们还是浅层网络。

Method

• GCNII为了解决GCN在深层时出现的Over-Smoothing问题，提出了Initial Residual（初始残差）和Identit Mapping（恒等映射）两个简单技巧，成功解决了GCN深层时的Over-Smoothing问题。

Initial Residual（初始残差）

• 残差一直是解决Over-Smoothing的最常用的技巧之一，传统GCN加residual connection用公式表示为： %7D%3D%5Csigma(%5Ctilde%20PH%5E%7B(l)%7DW%5E%7B(l)%7D)%2BH%5E%7B(l)%7D%0A#card=math&code=H%5E%7B%28l%2B1%29%7D%3D%5Csigma%28%5Ctilde%20PH%5E%7B%28l%29%7DW%5E%7B%28l%29%7D%29%2BH%5E%7B%28l%29%7D%0A)

其中：

residual connection相当于每次聚合都从前一层获取信息，进行残差连接

在计算机视觉中，ResNet通过残差结构解决了类似的问题，从而使得能够训练更深层的网络：

• GCNII Initial Residual不是从前一层获取信息，而是从初始层进行残差连接，并且设置了获取的权重。这里初始层initial representation不是原始输入feature，而是由输入feature经过线性变换后得到，如下公式所示： %7D%3Df%7B%5Ctheta%7D(X)%2C%5C%5C%0AH%5E%7B(l%2B1)%7D%3D%5Csigma(((1-%5Calpha)%5Ctilde%7BP%7DH%5E%7B(l)%7D%2B%5Calpha%20H%5E%7B(0)%7D)(…))%5Ctag%7B1%7D%0A#card=math&code=H%5E%7B%280%29%7D%3Df%7B%5Ctheta%7D%28X%29%2C%5C%5C%0AH%5E%7B%28l%2B1%29%7D%3D%5Csigma%28%28%281-%5Calpha%29%5Ctilde%7BP%7DH%5E%7B%28l%29%7D%2B%5Calpha%20H%5E%7B%280%29%7D%29%28…%29%29%5Ctag%7B1%7D%0A)

但Initial Residual不是GCNII首次提出，而是ICLR 2019模型APPNP中提出。

• 不过在GCN中添加残差结构仅仅能够减缓过度平滑现象，而非从根本上解决这个问题。因此2层以上的GCN模型依然面临的过拟合的问题。

Identit Mapping（恒等映射）

• 仅仅使用残差只能缓解Over-Smoothing问题，因此GCNII借鉴了ResNet的思想有了Identity Mapping，Initial Residual的想法是在当前层representation和初始层representation之间进行权重选择，而Identity Mapping是在参数W和单位矩阵I之间设置权重选择，如下公式所示： %7D%3D%5Csigma((…)((1-%5Cbeta_l)I_n%2B%5Cbeta_l%20W%5E%7B(l)%7D))%5Ctag%7B2%7D%0A#card=math&code=H%5E%7B%28l%2B1%29%7D%3D%5Csigma%28%28…%29%28%281-%5Cbeta_l%29I_n%2B%5Cbeta_l%20W%5E%7B%28l%29%7D%29%29%5Ctag%7B2%7D%0A)

是为了确保权值矩阵的衰减随着我们堆叠更多层而自适应地增加。实践中设%5Capprox%20%5Cfrac%7B%5Clambda%7D%7Bl%7D#card=math&code=%5Cbeta_l%3D%5Clog%20%28%5Cfrac%20%7B%5Clambda%7D%7Bl%7D%2B1%29%5Capprox%20%5Cfrac%7B%5Clambda%7D%7Bl%7D)，其中是超参，随着层数的增加，比例系数逐渐减小，代表着层数越深越接近恒等变换。

恒等映射被证明在半监督学习当中很有用，可以从迭代收缩阈值算法中找到很好的理论动机。

• GCNII论文中也给出了为什么Identity Mapping可以起到缓解Deep GNN出现Over-Smoothing问题，总结来说：Identity Mapping可以起到加快模型的收敛速度，减少有效信息的损失。

  • 逐渐变小，Deep GCNII逐渐忽略权重矩阵%7D#card=math&code=W%5E%7B%28l%29%7D)，本质上模拟APPNP（式子(1)）
  • 已经观察到，特征矩阵不同维度之间的频繁交互(Klicpera等人，2019a)降低了模型在半监督任务中的性能。映射平滑%7D#card=math&code=%5Ctilde%7BP%7DH%5E%7B%28l%29%7D)的表示直接输出减少了这种相互作用。?
  • 对%7D#card=math&code=W%5E%7B%28l%29%7D)添加了小的正则化，避免了过拟合。在半监督任务中，恒等映射被证明是特别有用的（ResNet）。
  • (Oono & Suzuki, 2020) 理论证明了k层GCNs的节点特征将收敛到子空间并导致信息丢失，收敛速率依赖于，其中是矩阵%7D#card=math&code=W%5E%7B%28l%29%7D)的最大奇异值。I_n%2B%5Cbeta_l%20W%5E%7B(l)%7D)#card=math&code=%28%281-%5Cbeta_l%29I_n%2B%5Cbeta_l%20W%5E%7B%28l%29%7D%29)替代%7D#card=math&code=W%5E%7B%28l%29%7D)，使得强迫%7D#card=math&code=W%5E%7B%28l%29%7D)逐渐变小。I_n%2B%5Cbeta_l%20W%5E%7B(l)%7D)#card=math&code=%28%281-%5Cbeta_l%29I_n%2B%5Cbeta_l%20W%5E%7B%28l%29%7D%29)的奇异值将接近于1，也将接近于1，变大，信息丢失减少。

Experiment

实验数据

• 实验中Cora, Citeseer, Pubmed三个引文数据，是同质图数据，常用于Transductive Learning类任务,三种数据都由以下八个文件组成，存储格式类似：
  

  同质图：同质(Homogeneity)图指的是图中的节点类型和关系类型都仅有一种。

异质图：异质(heterogeneous)图指的是图中的节点类型或关系类型多于一种。

属性图：在异质图基础上增加了额外的属性信息。

实验结果

• 实验结果在Cora, citeseer, pubmed三个数据上都进行DeepGNN测试，测试结果可以看出随着网络层级的加深，模型不仅没有像传统GNN出现Over-Smoothing而效果下降，反而模型效果随着深度增加而不断提升，解决了传统DeepGNN存在的Over-Smoothing问题。
  

Conclusion

• 作者提出了未来方向：将GCNII与注意力（attention）机制相结合。