論文資訊

論文標題：GraphSMOTE: Imbalanced Node Classification on Graphs with Graph Neural Networks
論文作者：Tianxiang Zhao, Xiang Zhang, Suhang Wang
論文來源：2021, WSDM
論文地址：download 
論文程式碼：download

1 Introduction

　　節點分類受限與不同類的節點數量不平衡，本文提出過取樣方法解決這個問題。

　　圖中類不平衡的例子：

　　圖中：每個藍色節點表示一個真實使用者，每個紅色節點表示一個假使用者，邊表示關係。任務是預測未標記的使用者（虛線圈）是真實的還是假的。這些類在本質上是不平衡的，因為假使用者通常還不到所有使用者的1%。半監督設定進一步放大了類不平衡問題，因為我們只給出了有限的標記資料，這使得標記的少數樣本的數量非常小。

　　在不平衡的節點分類中，多數類主導著損失函數，使得訓練後的 GNNs 對這些類過度分類，無法準確預測樣本。

　　目前解決類不平衡問題的方法可以分為：

• • data-level approaches（資料級方法）
  • algorithm-level approaches（演演算法級方法）
  • hybrid approaches（混合方法）

　　資料級方法尋求使類分佈更加平衡，使用過取樣（over-sampling）或降取樣（down-sampling）技術 [8,26]；演演算法級方法通常對不同的類[11,22,44]引入不同的錯誤分類懲罰或先驗概率；混合方法[9,23]將這兩者結合起來。

　　以前的演演算法並不容易適用於圖。

• • 首先，對產生的新樣本，很難生成邊關係。主流過取樣技術[26]利用目標範例與其最近鄰之間的插值來生成新的訓練範例。然而，插值不適合於邊，因為它們通常是離散的和稀疏的，插值可以破壞拓撲結構。　　
  • 第二，產生的新樣本可能質量較低。節點屬性是高維的，直接對其進行插值很容易生成域外的例子，對訓練分類器不利。　　

2 Related work:Class Imbalance Problem

2.1 data-level method

　　通過過取樣和下取樣的方法調整類結構。

　　過取樣的一般形式是直接複製現有樣本，帶來的問題是沒有引入額外資訊，容易導致過擬合問題。

　　SMOTE[8] 通過生成新樣本來解決這個問題，在少數類和最近鄰的樣本之間執行插值，在此基礎上的方法：

• • Borderline-SMOTE [15] 將過取樣限制在類邊界附近的樣本；
  • Safe-Level-SMOTE [7]使用多數類鄰居計算每個插值的安全方向，以使生成的新樣本更安全；
  • Cluster-based Over-sampling [17] 首先將樣本聚為不同的組，而不是單獨的過樣本，考慮到輸入空間中經常存在小區域；

　　下取樣丟棄多數類中的一些樣本，也可使類保持平衡，但代價是丟失一些資訊。為此，提出只刪除冗餘的樣本，如 [3,20]。

2.2 hybrid method

　　Cost sensitive learning [22,44] 通常構造一個成本矩陣，為不同的類分配不同的錯誤分類懲罰。效果類似於普通的的過取樣。[28] 提出了一種近似於 $F$ 測量的方法，它可以通過梯度傳播直接進行優化。

2.3 algorithm-level method

　　它結合了來自上述一個或兩個類別的多個演演算法。[23] 使用一組分類器，每個分類器都在多數類和少數類的一個子集上進行訓練。[9] 結合了 boosting 與SMOTE，[16] 結合了過取樣與成本敏感學習。[33] 引入了三種成本敏感的增強方法，它們迭代地更新每個類的影響以及 AdaBoost引數。

3 Problem definition

　　在本文中，我們使用 $\mathcal{G}=\{\mathcal{V}, \mathrm{A}, \mathrm{F}\}$ 來表示一個屬性網路，其中 $\mathcal{V}=\left\{v_{1}, \ldots, v_{n}\right\}$ 是一組 $n$ 節點。$\mathrm{A} \in \mathbb{R}^{n \times n}$ 為 $\mathcal{G}$ 的鄰接矩陣， $\mathrm{F} \in \mathbb{R}^{n \times d}$ 表示節點屬性矩陣，其中 $\mathrm{F}[j,:] \in \mathbb{R}^{1 \times d}$ 為節點 $j$ 的節點屬性，$