論文解讀《Measuring and Relieving the Over-smoothing Problem for Graph NeuralNetworks from the Topological View》
論文資訊
論文標題：Measuring and Relieving the Over-smoothing Problem for Graph NeuralNetworks from the Topological View
論文作者：Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, Xu Sun
論文來源：2020, AAAI
論文地址：download
論文程式碼：download
1 Introduction
過平滑的標準定義：當 GNN 疊加多層時，不同類的圖節點的表示將變得難以區分。
產生過平滑問題的原因：融合結構資訊所帶來雜訊，即類內的交互可以帶來有用的資訊，而類間的交互可能會導致類之間難以區分的表示。
2 Measuring Over-smoothing Problem from the Topological View
在本節中，將研究產生過平滑的原因。為此提出兩個指標 MAD 和 MADGap 去測量圖表示的平滑（smoothness）和過平滑（over-smoothness）。
2.1 MAD: Metric for Smoothness
Mean Average Distance (MAD) ，MAD 通過計算從節點到其他節點的平均距離的平均值來反映圖表示的平滑性。
首先，計算餘弦距離：
$D_{i j}=1-\frac{\boldsymbol{H}_{i,:} \cdot \boldsymbol{H}_{j,:}}{\left|\boldsymbol{H}_{i,:}\right| \cdot\left|\boldsymbol{H}_{j,:}\right|} \quad i, j \in[1,2, \cdots, n] $
其中：
-
- $\boldsymbol{H} \in \mathbb{R}^{n \times h}$ 代表圖表示矩陣；
- $\boldsymbol{D} \in \mathbb{R}^{n \times n}$ 代表著距離矩陣；
- $D_{i j}\in [0,2]$ ；
其次，將 $D$ 和掩模矩陣（mask matrix）做哈達瑪積：
$\boldsymbol{D}^{t g t}=\boldsymbol{D} \circ M^{t g t}\quad\quad\quad(2)$
其中，$\boldsymbol{M}^{\text {tgt }} \in \{0,1\}^{n \times n}$ ，$\boldsymbol{M}_{i j}^{t g t}=1$ 代表著需要計算節點 $i$ 和節點 $j$ 之間的餘弦距離。【可以從局部領域考慮平滑性，也可以從全局考慮平滑性】
然後，沿著 $\overline{\boldsymbol{D}}^{\text {tgt }} $ 中每一行的非零值的平均距離 $\boldsymbol{D}^{\text {tgt }}$：
$\overline{\boldsymbol{D}}_{i}^{t g t}=\frac{\sum_{j=0}^{n} \boldsymbol{D}_{i j}^{t g t}}{\sum_{j=0}^{n} \mathbb{1}\left(\boldsymbol{D}_{i j}^{t g t}\right)} \quad\quad\quad(3)$
其中，如果 $x>0$ ， $\mathbb{1}(x)=1$ ，否則為 $0$。
最後計算整個圖的 MAD：
$\operatorname{MAD}^{\mathrm{tgt}}=\frac{\sum_{i=0}^{n} \overline{\boldsymbol{D}}_{i}^{t g t}}{\sum_{i=0}^{n} \mathbb{1}\left(\overline{\boldsymbol{D}}_{i}^{t g t}\right)} \quad\quad\quad(4)$
通過考慮所有節點對來計算 MAD 值 $MAD^{Glogal}$，即 $ M^{tgt}$ 中的所有值都是 $1$，以度量學習圖表示的全局平滑性。在 Cora 數據集上的 MAD 如下所示：
結果顯示：多層 GNN 的 MAD 值接近於 $0$，說明所有的節點表示都變得難以區分。
2.2 Information-to-noise Ratio Largely Affects Over-smoothness
信噪比 （information-to-noise ratio）：
-
- 局部鄰居角度：在二階時，每個節點的資訊噪比是同一類節點在所有一階和二階鄰居中的比例；
- 全圖角度：整個圖的資訊噪比是兩步節點對在所有節點對中可以接觸的類內對的比例；
$\text{Figure 3}$ 將展示在 Core 數據集上的不同 $\text{order}$ 的全圖的信噪比：
觀察結果：發現在低階上有更多的類內節點對，反之亦然。當模型層數變大時，信噪比變小，高階鄰居之間的相互作用帶來了太多的雜訊，稀釋了有用的資訊，這是導致過度平滑問題的原因。
基於上述分析，提出 MADGap 去測量圖表示過平滑。從 $\text{Figure 3}$ 中我們注意到，兩個拓撲距離較小的節點（低階鄰居）更有可能屬於同一類別。因此，我們建議利用圖的拓撲結構來近似節點類別，並計算區分遠程節點和鄰居節點的 MAD 值的間隙來估計圖表示的過光滑性：
$\mathrm{MADGap}=\mathrm{MAD}^{\mathrm{rmt}}-\mathrm{MAD}^{\mathrm{neb}} \quad\quad\quad(5)$
其中，$MAD^{\text {rmt }}$ 為圖拓撲中遠程節點的 $MAD$ 值，$MAD^{\text {neb }}$ 為相鄰節點的 $MAD$ 值。本文基於 $orders \leq 3$ 的節點計算 $MAD^{\text {neb }}$，基於 $orders \geq 8$ 的節點計算 $MAD^{\text {rmt }}$。
根據假設，$\text{MADGap}$ 值越大($\ge 0$)，表示節點接收到的有用資訊要大於雜訊。此時，GNN 進行了合理程度的平滑處理，模型表現良好。相反，小的或負的 $\text{MADGap}$ 值意味著過度平滑和較差的性能。
為了驗證 $\text{MADGap }$ 的有效性，我們計算了 $\text{MADGap}$ 值，並計算了 $\text{MADGap}$ 與預測精度之間的皮爾遜係數。
在 Table 2 中報告了在 CORA、CiteSeer 和 PubMed 數據集上具有不同層的 GNN 的皮爾遜係數。
可以發現 MADGap 與模型性能之間存在顯著的高相關性，這表明 MADGap 是度量圖表示過平滑度的可靠度量。此外，MADGap 還可以作為一個觀察指標，在不看到標籤的情況下，基於圖的拓撲結構來估計模型的性能。
需要注意的是 $1$ 層 GNN 的 MADGap 和預測精度通常較小（ Figure 1），這是由於資訊不足造成的，而高層 GNN 的過平滑問題是由於接收過多的雜訊造成的。
在 Figure 4 中，我們展示了在同一模型中具有不同資訊-雜訊比的節點集的 MADGap 和預測精度。我們可以發現，即使使用相同的模型和傳播步長，資訊噪比率較高的節點通常具有較高的預測精度，過平滑度較小。
為了驗證我們的假設，我們通過去除類間邊和添加基於標籤的類內邊來優化圖的拓撲結構。在 CORA 數據集上的結果如 Figure 5 所示。
可以發現，隨著更多的類間邊被刪除，MADGap 值不斷上升添加了更多的類內邊，從而獲得更好的模型性能。因此，優化圖的拓撲結構有助於緩解過平滑問題，提高模型的性能。
綜上所述，我們發現圖的拓撲結構對圖表示的平滑性和模型的性能有很大的影響。然而，在自然連接和下游任務之間仍然存在不一致。現有的工作主要集中在設計新的 GNN 架構，而較少關注已建立的圖拓撲。因此，我們進一步研究通過優化圖拓撲來提高 GNN 的性能。
3 Relieving Over-smoothing Problem from the Topological View
受前面分析的啟發，我們提出了兩種方法來從拓撲的角度緩解過度平滑問題：
-
- MADReg：我們在訓練目標中添加了一個 MADGap-based 的正則化器；
- Adaptive Edge Optimization (AdaEdge)：通過迭代訓練 GNN 模型，並根據預測結果進行邊緣去除/添加操作，從而自適應地調整圖的拓撲結構；
3.1 MADReg: MADGap as Regularizer
我們在訓練目標中添加了 MADGap，使圖節點接收到更多有用的資訊和更少的干擾雜訊：
$\mathcal{L}=\sum-l \log p(\hat{l} \mid \boldsymbol{X}, \boldsymbol{A}, \Theta)-\lambda \mathrm{MADGap} \quad\quad\quad(6)$
其中，$\boldsymbol{X}$ 為輸入特徵矩陣，$\boldsymbol{A}$ 為鄰接矩陣，$\hat{l}$ 和 $l$ 分別為節點的預測標籤和真實標籤。$\Theta$ 是GNN的參數，$\lambda$ 是控制 MADReg 影響的正則化係數。我們在訓練集上計算 MADGap，以與交叉熵損失相一致。
3.2 AdaEdge: Adaptive Edge Optimization
如前一節中所討論的，在基於真實標籤優化拓撲之後(添加類內邊，並去除類間邊)，過平滑問題明顯緩解，模型性能大大提高。受此啟發，我們提出了一種名為 AdaEdge 的自訓練演算法，基於模型的預測結果來優化圖的拓撲結構，以自適應地調整圖的拓撲結構，使其對特定的任務目標更加合理。具體來說，我們首先在原始圖上訓練GNN，並根據模型的預測結果，通過刪除類間邊和添加類內邊來調整圖的拓撲結構。然後，我們從頭開始在更新後的圖上重新訓練GNN模型。我們將多次執行上述圖的拓撲優化操作。AdaEdge演算法的詳細介紹如下：
3.3 Relieving Over-smoothing in High-order Layers
為了驗證這兩種方法的有效性，我們在CORA/CiteSeer/PubMed數據集上對所有10個基準線GNN模型進行了對照實驗。我們計算了 4 層、過平滑問題嚴重的GNN模型的預測精度和 MADGap 值。結果如 $\text{Figure 6}$ 所示。由於空間限制，我們給出了 10 個模型中的 6 個結果。可以發現，在過平滑問題嚴重的高階層情況下，MADReg 和 AdaEdge 方法可以有效地緩解過平滑問題，提高所有三個數據集中大多數模型的模型性能。MADReg 和 AdaEdge 的有效性進一步驗證了我們的假設，並為緩解過平滑問題提供了一個普遍而有效的解決方案。
3.4 Improving Performance of GNNs
在 $\text{Table 3}$ 中，我們展示了在所有 7 個數據集上訓練的 GNN 模型和在 AdaEdge 方法上訓練的更新圖模型的受控實驗。我們在原始圖上訓練 GNN 時選擇最佳的超參數，並在更新的圖上進行訓練時修復所有這些超參數。
實驗結果表明，AdaEdge方法在大多數情況下都可以有效地提高模型的性能，這證明了圖拓撲結構的優化對提高模型的性能有很大的幫助。我們分析了 AdaEdge 方法幾乎沒有改進或沒有改進的情況，發現這是由於調整拓撲時的錯誤操作不當造成的。因此，當錯誤操作的比例太大時，會對模型訓練造成嚴重的干擾，導致很少或沒有改善。
在 $\text{Table 3}$ 中，展示了 MADReg 的結果。通常，基準線在少量的 GNN 層下達到了最好的性能，其中過平滑問題並不嚴重。在這種情況下，MADReg 很難通過擴大 MADGap 值來提高性能。然而，當過平滑問題變得更嚴重，而 GNN 層數變得更大時，MADReg 仍然能夠顯著地提高基準線的性能。最重要的是，AdaEdge 和MADReg 都能有效地提高 GNN 的性能，並且當過平滑問題不嚴重時，AdaEdge 可以更好地推廣。
4 Conclusion
在這項工作中，我們對gnn所面臨的過度平滑問題進行了系統和定量的研究。我們首先設計了兩個定量指標：光滑度的MAD和過平滑度的MADGap。從多個gnn和圖數據集的定量測量結果中，我們發現平滑是gnn的本質；過光滑性是由資訊和雜訊的過度混合造成的。此外，我們發現MADGap與模型性能之間存在顯著的高相關性。此外，我們還證明了資訊噪比與圖拓撲有關，並通過優化圖拓撲來使其更適合下游任務，從而緩解過平滑問題。接下來，我們提出了兩種方法來緩解gnn中的過平滑問題：MADReg方法和AdaEdge方法。大量的研究結果證明，這兩種方法可以有效地緩解過平滑問題，並在一般情況下提高模型的性能。
雖然我們已經證明了優化圖拓撲是提高gnn性能的有效方法，但我們提出的AdaEdge方法仍然存在錯誤的圖調整操作問題。如何減少這些操作是一個很有前途的研究方向。
