今天給大家介紹的是清華大學的Zhen Yang等人在KDD 2020發表的文章“Understanding Negative Sampling in Graph Representation Learning”。作者在文章中分析負采樣的作用，從理論上證明在優化目标函數和減小方差時負采樣與正采樣同等重要，得到負采樣分布應與正采樣分布正相關且呈次線性相關的結論，并提出了一個統一的負采樣政策MCNS優化各種網絡表示學習算法 。
1
背景
近年來，圖表示學習逐漸成為資料挖掘研究的熱點。主流的圖表示學習算法包括傳統的網絡嵌入方法(如DeepWalk，LINE)和圖神經網絡(如GCN，GraphSAGE)。大量的網絡嵌入工作已經研究出正節點對采樣的良好标準。然而，很少有論文系統地分析或讨論圖表示學習中的負采樣。
在這篇文章中，作者證明了負采樣與正采樣一樣重要。同時考慮負采樣，可以确定優化目标并減少真實圖形資料中估計值的方差。文章提出負采樣分布應與正采樣分布正相關且呈次線性相關的理論，并基于此理論提出了一種有效且可擴充的負采樣政策，即馬爾可夫鍊蒙特卡洛負采樣（MCNS），該政策将理論應用于基于目前嵌入的近似正分布。為了降低時間複雜度，利用特殊的Metropolis-Hastings算法進行采樣。
2
方法
2.1負采樣原理
為了确定特定正分布的适當負分布，可能需要權衡目标的合理性(最佳嵌入在何種程度上适合下遊任務)和預期損失(訓練嵌入偏離最佳嵌入的程度)。一個簡單的解決方案是對負節點進行正采樣，并與其正采樣分布呈次線性相關。
2.2 自對比估計
雖然推導出正采樣與負采樣的關系，但實際正分布是未知的，并且通常會隐式定義其近似值。是以，作者提出了一種自對比估計(self-contrast approximation)方法，用基于目前編碼器的内積代替正分布，即
作者提出的MCNS通過改編的Metropolis-Hastings算法解決了采樣耗時問題。
2.3 Metropolis-Hastings算法
Metropolis-Hastings算法構造了一個相對于
周遊且靜止的馬爾可夫鍊
這意味着
2.4 馬爾可夫鍊負采樣
MCNS的主要想法是應用Metropolis-Hastings算法，對
中的每個節點v從自對比估計分布中采樣。為了解決Metropolis-Hastings具有相對較長的老化期的缺點，作者提出通過深度優先搜尋(DFS)周遊圖，并繼續從最後一個節點的馬爾可夫鍊生成負樣本(如圖1)。
圖1 MCNS的一個運作示例
DFS周遊中心節點，每個節點通過馬爾可夫鍊使用Metropolis-Hastings算法對三個負上下文節點進行采樣。
此外作者将二進制交叉熵損失替換為γ偏斜鉸鍊損失
其中(u，v)是正節點對,( x，v)是負節點對。γ是一個超參數。算法2總結了MCNS。
圖2 MCNS算法流程
3
實驗
實驗是在3個代表性任務、3個圖表示學習算法和5個資料集總共19個實驗設定下進行了評估，這些資料集涵蓋了廣泛的下遊圖形學習任務，包括連結預測，節點分類和個性化推薦。為了驗證MCNS對不同類型的圖表示學習算法的适應性，作者對DeepWalk，GCN，GraphSAGE三種算法進行了實驗。實驗設定基于度的負采樣，難例負采樣，基于GAN負采樣作為基準，這些相對全面的實驗結果證明了其魯棒性和優越性。
表1 任務和資料集的統計資料
3.1個性化推薦
表2 在三個資料集上使用各種編碼器的MCNS的推薦結果
結果表明，難例負采樣通常會超過基于度的政策，MRR的性能會提高5％到40％。基于GAN的負采樣政策的性能更高，這是因為不斷發展的生成器更準确地挖掘了難例負采樣。根據實驗理論，提出的MCNS在最佳基準上可實作2％到13％的顯著增益。
3.2連結預測
表3 Arxiv資料集上不同負采樣政策的連結預測結果
在Arxiv資料集上，MCNS的各種圖表示學習方法均優于所有基線。
3.3 節點分類
表4 BlogCatalog資料集上的多标簽分類的Micro F1分數
不管訓練集比率TR如何，MCNS都會穩定地勝過所有基線。Macro-F1的趨勢相似，由于空間限制而被省略。
3.4分析
圖3 度數和MCNS的比較
與度數的比較 圖3中每條紅線表示在此設定下MCNS的性能，藍色曲線表示不同β的度數的性能，基于度的政策的表現一直低于MCNS，這表明MCNS在基于度的政策的表達能力之外學習了更好的負分布。此外，最佳β在資料集之間會有所不同，并且似乎很難在實驗前确定，而MCNS自然會适應不同的資料集。
圖4 MCNS在阿裡巴巴上的性能
參數分析 為了定量測試MCNS的魯棒性，作者通過更改兩個最重要的超參數（嵌入尺寸和邊距γ）來可視化MCNS的MRR曲線。
圖5 運作時間比較
效率比較 為了比較不同的負采樣方法的效率，作者在圖5的推薦任務中報告了MCNS和帶有GraphSAGE編碼器的硬采樣或基于GAN的政策（PinSAGE，WARP，DNS，KBGAN）的運作時間。
4
總結
作者在文章中從理論上分析了負采樣在圖表示學習的作用，并得出結論：負采樣分布和正采樣分布同等重要，并且應與正采樣分布正相關且呈次線性相關。基于此理論，作者提出了MCNS，通過自對比估計逼近正采樣分布，并通過Metropolis-Hastings算法加速計算。大量的實驗表明，無論底層的圖表示學習方法如何，MCNS的性能均優于8種負采樣政策。