【論文解讀 ICLR 2020 | DropEdge】TOWARDS DEEP GRAPH CONVOLU-TIONAL NETWORKS ON NODE CLASSIFICATION

論文題目：DROPEDGE: TOWARDS DEEP GRAPH CONVOLU-TIONAL NETWORKS ON NODE CLASSIFICATION

論文來源：ICLR 2020

論文連結：https://openreview.net/forum?id=Hkx1qkrKPr

代碼連結：https://github.com/DropEdge/DropEdge

關鍵詞：GNN的加深，過拟合，過平滑，DropEdge

文章目錄

• 1 摘要
• 2 引言
• 3 DropEdge
• • 3.1 METHODOLOGY
  • • 3.1.1 阻止過拟合
    • 3.1.2 Layer-Wise DropEdge
  • 3.2 阻止過平滑
  • 3.3 讨論
• 4 實驗
• 5 總結
• 參考文獻

1 摘要

本文解決的是圖神經網絡無法加深的問題，提出DropEdge機制加深GNN，用于節點分類任務。

圖神經網絡無法加深主要有兩個原因：過拟合（over-fitting）和過平滑（over-smoothing）。

本文提出了DropEdge機制，在模型訓練時随機删減掉原始圖中的邊，來緩解這兩個問題。

此外，作者還從理論上證明了DropEdge既可以降低過平滑的收斂速度，又可以減少由過平滑引起的資訊損失。并且DropEdge可以用于許多GNN模型以增強其性能，例如JKNet、GCN、ResGCN、GraphSAGE。

實驗結果顯示DropEdge可以提升多個淺層和深層GCN模型的性能。

2 引言

GCNs的思想是：聚合節點鄰居的資訊及其自身的資訊，進行消息傳遞，以擷取到節點的高階特征，生成節點的表示。GCNs已經成為圖表示學習的重要方法，但是這些模型通常都是淺層的，限制了模型的表示能力。

最近，基于卷積神經網絡裡面的經驗，有一些對圖卷積網絡做深的模型修改嘗試。但是這些工作并沒有真正去分析為什麼圖卷積網絡很難做深以及去解釋模型修改在圖卷積網絡裡面是有效的。

本文的動機就是分析阻礙GCN加深的因素，并且提出方法來解決這些問題。導緻GCN無法加深主要有過拟合（over-fitting）和過平滑（over-smoothing）兩個原因。

（1）過拟合指的是使用複雜的模型去拟合少量資料時會造成泛化能力變差，是深度學習模型中常見的問題。

（2）過平滑是圖神經網絡中特有的問題，由于GCN的思想是聚合鄰居節點和節點自身的資訊來學習節點的表示，是以随着網絡層數的加深，節點的表示有趨同性，節點表示的可區分性會變差。也就是說随着層數的不斷加深，所有節點的表示最終會收斂到一個固定點，得到的節點表示就和輸入特征無關了，而且還會導緻梯度消失。

圖1中虛線部分是原始的 4 層和 8 層 GCN 在 Cora 資料集上的訓練曲線（這裡為了更好展示過拟合和過平滑，取消了 GCN 層中的 bias），可以看到，在 GCN-4 上，驗證集 (Validation Set) 的損失函數在訓練經過一定輪數後反向增長。這個增長是優于過拟合。而在 GCN-8 上，訓練集 (Training Set) 上的損失函數則根本沒有下降，這是因為過平滑的存在，導緻 GCN-8 上訓練失效。

本文提出的DropEdge方法可以緩解這兩個問題，主要思想是：在每次訓練時，随機删除掉原始圖中固定比例的邊。在GCN訓練過程中應用DropEdge有許多好處：

（1）DropEdge可以看成是資料增強技術。在訓練過程中對原始圖中的邊進行不同的随機删除，也就增強了輸入資料的随機性和多樣性，可以緩解過拟合的問題。

（2）DropEdge還可以看成是一個消息傳遞減速器（message passing reducer）。GCNs中，鄰接節點間的消息傳遞是通過連邊實作的，随機删除掉一些邊就可以讓節點連接配接更加稀疏，在一定程度上避免了GCN層數加深引起的過平滑問題。

作者還在理論上證明了DropEdge既可以降低過平滑的收斂速度，又可以減少由過平滑引起的資訊損失。

定義

• 圖為 G = ( V , E ) \mathcal{G}=(\mathbb{V}, \mathcal{E}) G=(V,E)
• 節點特征定義為 X = { x 1 , . . . , x N } ∈ R N × C \mathbf{X}={\{x_1, ..., x_N}\}\in \mathbb{R}^{N\times C} X={x1​,...,xN​}∈RN×C
• 鄰接矩陣定義為 A ∈ R N × N \mathbf{A}\in \mathbb{R}^{N\times N} A∈RN×N
• 節點度定義為 d = { d 1 , . . . , d N } \mathbf{d}={\{d_1, ..., d_N}\} d={d1​,...,dN​}， d i d_i di​為和節點 i i i相連的邊的權重和。 D \mathbf{D} D為度對角矩陣。

GCN

GCN的前向傳播定義為：

• H ( l + 1 ) = { h 1 ( l + 1 ) , . . . , h N ( l + 1 ) } \mathbf{H}^{(l+1)}={\{h^{(l+1)}_1, ..., h^{(l+1)}_N}\} H(l+1)={h1(l+1)​,...,hN(l+1)​}是第 l l l層的隐層向量
• A ^ = D ^ − 1 / 2 ( A + I ) D ^ − 1 / 2 \hat{\mathbf{A}}=\hat{\mathbf{D}}^{-1/2}(\mathbf{A}+\mathbf{I})\hat{\mathbf{D}}^{-1/2} A^=D^−1/2(A+I)D^−1/2
• D ^ \hat{\mathbf{D}} D^是 A + I \mathbf{A}+\mathbf{I} A+I對應的度矩陣
• W ( l ) ∈ R C l × C l − 1 \mathbf{W}^{(l)}\in \mathbb{R}^{C_l\times C_{l-1}} W(l)∈RCl​×Cl−1​是第 l l l層的卷積核矩陣， C l C_l Cl​是第 l l l層的隐藏層單元數

3 DropEdge

3.1 METHODOLOGY

每次訓練時，DropEdge機制會随機删除掉原始圖中固定比例的邊。（隻在訓練集上使用，在測試集和驗證集上不使用DropEdge機制）也就是說随機選取鄰接矩陣 A \mathbf{A} A中 V p Vp Vp個非零的元素，将其置零。其中， V V V是原始圖中的總邊數， p p p是删除率。删除後得到鄰接矩陣 A d r o p \mathbf{A}_{drop} Adrop​：

然後對 A d r o p \mathbf{A}_{drop} Adrop​進行re-normalization得到 A ^ d r o p \hat{\mathbf{A}}_{drop} A^drop​，替換式（1）中的 A ^ \hat{\mathbf{A}} A^。

3.1.1 阻止過拟合

DropEdge對圖中的連接配接帶來了擾動，它對輸入資料産生了不同的随機變形，可以看成是資料增強。

GCNs的核心思想是對每個節點的鄰居特征進行權重求和（權重和邊有關），實作對鄰居資訊的聚合。從這一角度出發，可以看出DropEdge在GNN訓練時使用的是随機的鄰居子集進行聚合，而沒有使用所有的鄰居。

DropEdge删邊率為 p p p，對鄰居聚合的期望是由 p p p改變的。在對權重進行歸一化後就不會再使用 p p p。是以，DropEdge沒有改變鄰居聚合的期望，是用于GNN訓練的無偏的資料增強方法，可以有效防止GNN訓練時的過拟合問題。類似于經典的圖像資料增強方法：rotation, cropping, flapping。

3.1.2 Layer-Wise DropEdge

上述的DropEdge是所有層共享同一個鄰接矩陣。我們也可以在每層上進行DropEdge，在第 l l l層得到鄰接矩陣 A ^ d r o p ( l ) \hat{\mathbf{A}}^{(l)}_{drop} A^drop(l)​。這樣的話可以為原始資料帶來更多的随機性。實驗中将layer-wise DropEdge和原始的DropEdge進行了對比。

DropEdge還有助于緩解深層GNN帶來的過平滑問題，接下來将進行介紹。但是後面的推導假設所有的圖卷積層共享相同的鄰接矩陣，對layer-wise DropEdge的探讨作為未來的研究工作。

3.2 阻止過平滑

過平滑指的是随着網絡的不斷加深，節點的表示最終會收斂到一個固定點。這種不必要的收斂使得深度GCNs的輸出隻和圖的拓撲結構有關，獨立于輸入的節點特性，這會損害GCNs的表示能力。

Oono和Suzuki [1]同時考慮了非線性（例如ReLu函數）和卷積核，他們将過平滑看成是收斂到一個子空間，而不是收斂到一個固定點。本文使用的是這些學者提出的子空間的概念。

相關定義

（1）子空間（subspace）

令 M : = { E C ∣ C ∈ R M × C } \mathcal{M}:={\{EC|C\in \mathbb{R}^{M\times C}}\} M:={EC∣C∈RM×C}是空間 R M × C \mathbb{R}^{M\times C} RM×C中的 M M M維的子空間（ N N N是節點數， C C C是節點特征的次元）。其中 E ∈ R N × M E\in \mathbb{R}^{N\times M} E∈RN×M是正交矩陣， E T E = I M , M ≤ N E^TE=I_M, M\leq N ETE=IM​,M≤N。

（2） ϵ − s m o o t h i n g \epsilon-smoothing ϵ−smoothing

給定獨立于輸入特征的子空間 M \mathcal{M} M，若第 l l l層的隐層矩陣 H ( l ) \mathbf{H}^{(l)} H(l)中的所有向量的距離不超過 ϵ ( ϵ > 0 ) \epsilon(\epsilon>0) ϵ(ϵ>0)，則稱GCN中的節點特征發生了 ϵ − s m o o t h i n g \epsilon-smoothing ϵ−smoothing現象。

其中， d M ( ⋅ ) d_{\mathcal{M}}(\cdot) dM​(⋅)是計算輸入矩陣和子空間 M \mathcal{M} M間的距離。

（3）the ϵ − s m o o t h i n g \epsilon-smoothing ϵ−smoothing layer

給定子空間 M \mathcal{M} M和 ϵ \epsilon ϵ，我們将滿足式（3）的GCN層的最小值稱為the ϵ − s m o o t h i n g \epsilon-smoothing ϵ−smoothing layer。即， l ∗ ( M , ϵ ) : = m i n l { d M ( H ( l ) ) < ϵ } l^*(\mathcal{M}, \epsilon):=min_l{\{d_{\mathcal{M}}(\mathbf{H}^{(l)})<\epsilon}\} l∗(M,ϵ):=minl​{dM​(H(l))<ϵ}。（ l ∗ ( M , ϵ ) l^*(\mathcal{M}, \epsilon) l∗(M,ϵ)是層數）

基于the ϵ − s m o o t h i n g \epsilon-smoothing ϵ−smoothing layer進行分析是很難的，是以我們将 l ∗ l^* l∗的上界定義為了the relaxed ϵ − s m o o t h i n g \epsilon-smoothing ϵ−smoothing layer。

（4）the relaxed ϵ − s m o o t h i n g \epsilon-smoothing ϵ−smoothing layer

給定子空間 M \mathcal{M} M和 ϵ \epsilon ϵ，我們将 l ^ ( M , ϵ ) = ⌈ l o g ( ϵ / d M ( X ) ) l o g s λ ⌉ \hat{l}(\mathcal{M}, \epsilon)=\lceil \frac{log(\epsilon/d_{\mathcal{M}}(\mathbf{X}))}{log s\lambda} \rceil l^(M,ϵ)=⌈logsλlog(ϵ/dM​(X))​⌉稱為the relaxed ϵ − s m o o t h i n g \epsilon-smoothing ϵ−smoothing layer。其中， s s s是所有層卷積核奇異值的最小上界， λ \lambda λ是 A ^ \hat{\mathbf{A}} A^的第二大特征值。有 l ^ ≥ l ∗ \hat{l}\geq l^* l^≥l∗。

根據Oono & Suzuki 的結論，足夠深的GCN在一些條件下，對于任意小的 ϵ \epsilon ϵ值，都會有 ϵ − s m o o t h i n g \epsilon-smoothing ϵ−smoothing問題。他們隻是提出了深度GCN中勳在 ϵ − s m o o t h i n g \epsilon-smoothing ϵ−smoothing，但是沒有提出對應的解決方法。

作者從兩個角度解釋了DropEdge有助于緩解 ϵ − s m o o t h i n g \epsilon-smoothing ϵ−smoothing問題：

（1）通過減少節點間的連接配接，DropEdge可以降低過平滑的收斂速度，也就是說使用DropEdge可以讓the relaxed ϵ − s m o o t h i n g \epsilon-smoothing ϵ−smoothing layer的值增加（也就是層數增加）；

（2）原始空間和收斂子空間的次元之差（例如 N − M N-M N−M）衡量了資訊的損失量，這個差越大說明資訊損失越嚴重。DropEdge可以增加子空間的次元，也就具有減少資訊損失的能力。

總結如下：

定理 1：定義原始圖為 G \mathcal{G} G，經過DropEdge删邊後的圖為 G ′ \mathcal{G}^{'} G′。給定一個小值 ϵ \epsilon ϵ，假定 G \mathcal{G} G和 G ′ \mathcal{G}^{'} G′關于子空間 M \mathcal{M} M和 M ′ \mathcal{M}^{'} M′會遇到 ϵ − s m o o t h i n g \epsilon-smoothing ϵ−smoothing問題。然後，下面不等式的任意一個在删除足夠多的邊後仍然成立。

定理1的證明基于Oono & Suzuki[1]的推導和随機遊走理論中的mixing time，具體見論文附錄。定理1表明DropEdge要麼降低了過拟合的收斂速度，要麼緩解了過平滑帶來的資訊損失。是以，DropEdge使得我們可以有效地訓練深層的GCNs。

3.3 讨論

比較DropEdge和其他相關概念的不同，包括Dropout、DropNode和Graph Sparsification。

（1）DropEdge vs. Dropout

Dropout是對特征向量中的某些次元随機置零，可以緩解過拟合，但是不能緩解過平滑，因為它沒有改變鄰接矩陣。

DropEdge可以看成Dropout向圖資料的推廣，将删除特征次元變換成删除邊，有助于緩解過拟合和過平滑問題。

實際上兩者是互補關系，實驗中對兩者進行了比較。

（2）DropEdge vs. DropNode

作者将基于節點采樣的方法稱為DropNode（GraphSAGE, FastGCN, AS-GCN中均有使用）。DropNode的思想是采樣子圖用于mini-batch訓練，和删除的節點相連的邊也被删除了，是以它可以看成是删除邊的特殊形式。

然而，DropNode中删除的邊是面向節點（node-oriented）的且無向的。DropEdge是面向邊（edge-oriented）的，它可以在訓練時保留所有節點的特征，更具靈活性。

而且，現有的DropNode的方法通常是低效的，GraphSAGE的layer size是指數級增長的，AS-GCN每層都需要進行采樣。DropEdge在加深層數時不會增加layer size，也不需要遞歸地采樣，DropEdge對所有邊的采樣是并行的。

（3）DropEdge vs. Graph-Sparsification

圖稀疏性的目标是去除掉不必要的邊，以對圖進行壓縮，同時盡可能地保留原始輸入圖中的資訊。

DropEdge在每次訓練時會随機删除輸入圖中的一些邊，而圖稀疏性的方法需要複雜的優化過程來決定删除掉哪些邊。

4 實驗

1、資料集

（1）對papers的研究領域進行分類：Cora、Citeseer、Pubmed（transductive）

（2）預測社交網絡中的文章屬于哪個社群：Reddit（inductive）

2、對比方法

GCN; ResGCN; JKNet; INcepGCN; GraphSAGE

3、實驗結果

（1）在多個GCN方法中使用DropEdge，看性能是否有提升

（2）和SOTAs對比

（3）緩解過平滑

計算目前層輸出和上一層輸出的歐氏距離，來衡量過平滑的程度。距離越小說明過平滑現象越嚴重。

圖3 a可以看出，随着層數的加深，過平滑現象越來越嚴重。但是使用DropEdge（ p = 0.8 p=0.8 p=0.8）時過平滑的收斂速度明顯減緩了。

圖3 b顯示，在訓練之後，沒有使用DropEdge的GCN第5層和第6層輸出的差别為0，而使用了DropEdge的GCN随着層數的加深，不同層之間的差别并沒有減為0。

（4）和Dropout的相容性

在4層的GCN上進行消融實驗。驗證集上的損失如圖4 a所示，結果表明若同時使用Dropout和DropEdge有助于GCN的訓練。

（5）Layer-Wise的DropEdge

如圖4 b所示，layer-wise的DropEdge比原始的DropEdge在訓練時的損失更小，兩者在驗證集上表現差不多。這表明layer-wise的DropEdge有助于訓練的進行。但是為了避免過拟合的風險，以及減小計算複雜度，作者傾向于使用原始的DropEdge而不是layer-wise的DropEdge。

5 總結

本文的工作非常有意義，在解決圖卷積網絡不能加深的問題上邁出了重要的一步。DropEdge和Dropout有異曲同工之妙，思路簡單，但是非常有效。

本文提出DropEdge機制，有助于圖卷積網絡的加深，以用于節點分類任務。具體操作是在每次訓練時随機删除圖中固定比例的一些邊。DropEdge增加了輸入資料的多樣性，進而緩解了過拟合問題；還減少了圖卷積時資訊的傳遞，進而緩解了過平滑問題。

在多個資料集上進行實驗，證明了在已有的GCN模型上使用DropEdge，可以提升原有模型的性能。

參考文獻

[1] Kenta Oono and Taiji Suzuki. On asymptotic behaviors of graph cnns from dynamical systems perspective. arXiv preprint arXiv:1905.10947, 2019.