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

原理"/>

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

GCNII Note

参考：

Paper: Simple and Deep Graph Convolutional Networks (arxiv)

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

Paper

Motivation

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

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

  而模型过浅，我们就无法从高阶邻居中提取信息了。

• Quantitative Metric for Smoothness给Over-smoothness提出一个定量的指标$SVM_G $
  D ( x i , x j ) = 1 2 ∥ x i ∥ x i ∥ − x j ∥ x j ∥ ∥ , S V M i = 1 n − 1 ∑ j ∈ V , j ≠ i D ( x i , x j ) , S V M G = 1 n ∑ i ∈ V S V M i D(x_i,x_j)=\frac {1}{2}\lVert \frac{x_i}{\lVert x_i\rVert}-\frac{x_j}{\lVert x_j\rVert}\rVert,\\ SVM_i=\frac{1}{n-1}\sum_{j\in V, j\neq i}D(x_i,x_j),\\ SVM_G=\frac{1}{n}\sum_{i\in V}SVM_i D(xi​,xj​)=21​∥∥xi​∥xi​​−∥xj​∥xj​​∥,SVMi​=n−11​j∈V,j​=i∑​D(xi​,xj​),SVMG​=n1​i∈V∑​SVMi​
  S V M G SVM_G SVMG​衡量了图中任意两个节点之间的欧氏距离之和， S V M G SVM_G SVMG​越小表示图学习时Over-Smoothing越严重，当 S V M G = 0 SVM_G=0 SVMG​=0时，图中所有节点完全相同，也可以从图中看出随着层次的加深， S V M G SVM_G SVMG​的值越来越小。

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

  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用公式表示为：
  H ( l + 1 ) = σ ( P ~ H ( l ) W ( l ) ) + H ( l ) H^{(l+1)}=\sigma(\tilde PH^{(l)}W^{(l)})+H^{(l)} H(l+1)=σ(P~H(l)W(l))+H(l)
  其中：

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

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

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

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iet7rxDd-1634455924694)(GCNII_Note/ea804be82a549035c71bf58f61a2036b.png)]

• GCNII Initial Residual不是从前一层获取信息，而是从初始层进行残差连接，并且设置了获取的权重。这里初始层initial representation不是原始输入feature，而是由输入feature经过线性变换后得到，如下公式所示：
  H ( 0 ) = f θ ( X ) , H ( l + 1 ) = σ ( ( ( 1 − α ) P ~ H ( l ) + α H ( 0 ) ) ( . . . ) ) (1) H^{(0)}=f_{\theta}(X),\\ H^{(l+1)}=\sigma(((1-\alpha)\tilde{P}H^{(l)}+\alpha H^{(0)})(...))\tag{1} H(0)=fθ​(X),H(l+1)=σ(((1−α)P~H(l)+αH(0))(...))(1)
  α = 0.1 或 0.2 \alpha=0.1或0.2 α=0.1或0.2

  但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之间设置权重选择，如下公式所示：
  H ( l + 1 ) = σ ( ( . . . ) ( ( 1 − β l ) I n + β l W ( l ) ) ) (2) H^{(l+1)}=\sigma((...)((1-\beta_l)I_n+\beta_l W^{(l)}))\tag{2} H(l+1)=σ((...)((1−βl​)In​+βl​W(l)))(2)
  β \beta β是为了确保权值矩阵的衰减随着我们堆叠更多层而自适应地增加。实践中设 β l = log ⁡ ( λ l + 1 ) ≈ λ l \beta_l=\log (\frac {\lambda}{l}+1)\approx \frac{\lambda}{l} βl​=log(lλ​+1)≈lλ​，其中 λ \lambda λ是超参，随着层数 l l l的增加，比例系数 β \beta β逐渐减小，代表着层数越深越接近恒等变换。

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

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

  • β \beta β逐渐变小，Deep GCNII逐渐忽略权重矩阵 W ( l ) W^{(l)} W(l)，本质上模拟APPNP（式子(1)）
  • 已经观察到，特征矩阵不同维度之间的频繁交互(Klicpera等人，2019a)降低了模型在半监督任务中的性能。映射平滑 P ~ H ( l ) \tilde{P}H^{(l)} P~H(l)的表示直接输出减少了这种相互作用。?
  • 对 W ( l ) W^{(l)} W(l)添加了小的正则化，避免了过拟合。在半监督任务中，恒等映射被证明是特别有用的（ResNet）。
  • (Oono & Suzuki, 2020) 理论证明了k层GCNs的节点特征将收敛到子空间并导致信息丢失，收敛速率依赖于 s K s^K sK，其中 s s s是矩阵 W ( l ) W^{(l)} W(l)的最大奇异值。 ( ( 1 − β l ) I n + β l W ( l ) ) ((1-\beta_l)I_n+\beta_l W^{(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_l W^{(l)}) ((1−βl​)In​+βl​W(l))的奇异值将接近于1， s s s也将接近于1， s K s^K sK变大，信息丢失减少。

Experiment

实验数据

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

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-h9TO4SeJ-1634455924696)(GCNII_Note/image-20211006113732817.png)]

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

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

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

实验结果

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

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pm1UT9kq-1634455924697)(GCNII_Note/image-20211006113825500.png)]

Conclusion

型效果随着深度增加而不断提升，解决了传统DeepGNN存在的Over-Smoothing问题。

[外链图片转存中…(img-pm1UT9kq-1634455924697)]

Conclusion

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