鑽石舞台

現有的 GNN 默認節點 samples 的類別滿足 balance 的條件，但是在現實世界中可能存在 class imbalance 的情況。如果直接訓練 GNN model 可能存在依賴偏好導致模型性能欠佳，基於此本文提出了 GraphSMOTE ，GraphSMOTE 構造了一個嵌入空間來編碼節點之間的相似性，基於此生成 new samples。此外，同時訓練一個edge generator 來對關係信息進行建模提供給 new samples，該框架具備良好的可擴展性。

如果大家對大圖數據上高效可擴展的 GNN 和基於圖的隱私計算感興趣，歡迎關注我的 Github，之後會不斷更新相關的論文和代碼的學習筆記。

鏈接：https://github.com/XunKaiLi/Awesome-GNN-Research

現在世界中的 class imbalance 問題的一些例子：虛假賬戶檢測，社交網絡上的正常用戶和機器人賬號。同樣，網站頁面的主題分類，一些主題類別可能因為受眾度等原因缺乏標籤。

在機器學習領域，class imbalance 問題的解決辦法分類如下：

Data-level 方法希望類分布更加平衡，使用 over-sampling 或 down-sampling 方法來實現；algorithm-level 方法為不同的類引入不同的誤分類懲罰或先驗概率；hybrid-level 方法結合上述兩類方法的特點。然而由於圖結構的特殊性，上述方法直接應用於圖數據上的效果不佳，因為在訓練過程需要充分考慮節點之間的關係，class imbalance 不僅會影響其嵌入質量，而且會影響相鄰節點之間的特徵信息傳播過程。

原有的 class imbalance 問題的解決方法不能很好適用於圖數據的原因如下：

很難為合成的 new samples 生成關係信息。over-sampling 方法使用目標樣本與其最近鄰之間的插值來生成新的 training samples。然而插值可能破壞拓撲結構；合成的 new samples 質量可能較低，直接原因在於高維的節點屬性，直接對其進行插值不利於 GNN model 的訓練。synthetic minority oversampling techniques（SMOTE）是解決 class imbalance 最有效的方法。在圖數據集上應用 SMOTE 的難點如下：1. 原始特徵空間上的合成節點生成未充分考慮圖數據自帶的複雜信息；2. 新生成的節點無法與現有圖建立關係（edges），對於 GNN model 來說難以利用。基於上述問題，本文提出 GraphSMOTE。

在訓練過程中圖中只有部分節點 帶有標籤信息 ，總共有 類 ， 代表第 類的數量，基於此使用 imbalance ratio 來衡量 class imbalance。如果存在 class imbalance 問題則相應的係數較小。模型目標是希望在 class imbalance 的前提下學習得到一個分類器 能夠在 majority 和 minority classes 上都表現良 好:

其中 代表節點屬性的特徵矩陣。

GraphSMOTE 的主要思想是在基於 GNN 的 feature extractor 通過插值生成少數類 new samples，並利用 edge generator 補全關係信息，形成一個增廣的平衡圖。

GraphSMOTE 由四部分組成：

使用 Feature extractor 的出發點有二：低維嵌入空間中，samples 的空間分布更加接近；經過 GNN 編碼可以提取到一定的圖拓撲結構信息。並且遵循一個假設：當前節點與最近鄰節點的插值特徵以更高的概率表示為當前節點的標籤信息。在圖中，節點的相似性需要考慮節點屬性、節點標籤以及局部圖結構。本文基於 GNN 在 edge prediction 和 node classification 兩個下游任務上對其進行訓練。

考慮到 over-smoothing 和 over-fitting 問題，feature extractor 使用一層的 GraphSAGE 實現：

該模塊為少數類生成 new samples， SMOTE 的基本思想是將來自目標少數類的樣本與它們在嵌 入空間中最近的鄰域進行揷值，這些樣本應屬於同一類 (假沒條件)。設 為少數節點，標記 為 。第一步是找到與 相同類別的最近標記節點:

指來自同一類的 的最近鄰居，使用嵌入空間中的歐氏距離來衡量該指標。生成少數類 new samples:

對於每一個少數類，可以應用 SMOTE 來生成完整的節點。使用超參數、over-sampling 比例來控制為每一類生成的樣本量。通過這個生成過程，可以使類的大小分布更加均衡。

其中 代表捕捉節點對之間交互信息的參數矩陣， edge generator 的損失函數為:

其中 指的是 中的節點之間的預測連接（預測原本存在的連接關係來使 學習到如何捕獲 節點對的信息交互過程) 。基於此認為生成的 new samples 所預測的連接關係也是準確的。之後本文嘗試了兩種增廣圖數據的構建方法分別為 :

基於上述的增廣圖數據策略得到 ，其中帶有標籤節點集為 ，並且此時的 class imbalance 問題得到了改善，GNN Classifier 形式如下 (最後接一個線性層完成節點分 類）:

其中 代表第二個 GraphSAGE 模塊，該模塊使用交叉嫡損失函數:

預測結果:

全局目標函數為:

其中 分別代表 feature extractor， edge generator 和 node classifier 模塊的可訓練參 數。

baselines