新零售智能引擎事業群出品
近年來，圖表示學習得到了廣泛的研究。盡管它有可能為各種網絡生成連續的向量表示，但是将高品質的向量表示推向大型節點集的有效性和效率性方面仍具有挑戰。大多數的圖表示學習可以統一納入SampledNCE架構，該架構包括一個用于生成節點嵌入的可訓練編碼器，一個正采樣器和一個負采樣器（如下圖所示）。現有技術通常集中于對正節點進行采樣，而負采樣政策則沒有得到足夠的探索。
是以，我們從目标函數和方差兩個角度系統地分析了負采樣的作用，從理論上證明了負采樣與正采樣在确定優化目标和減小估計方差方面同等重要。首先，我們從如下的圖表示學習的目标函數出發，讨論更普遍的圖表示學習形式
其中p_d 是估計的資料分布，p_n 是負采樣分布， u ⃗、 v ⃗是節點的向量表示，σ(⋅) 是sigmoid函數。我們可以得出最優情況下向量内積應具有最優值：
上式表明正采樣分布和負采樣分布對目标函數的優化具有相同程度的影響。
此外，我們還從方差的角度分析了負采樣的作用，分别從正采樣分布中采樣T個正樣本對，從負采樣分布中采樣kT個負樣本對，用于最小化經驗誤差。最終，根據我們證明的定理——一個随機變量√T(θT−θ∗)T(θT−θ∗) 将逐漸收斂到一個具有零均值向量和協方差矩陣的分布，得到均方誤差：
從上式可知，均方誤差不僅與正采樣分布p_d有關，也與負采樣分布p_n也有關。此外，還明确了負采樣分布與正采樣分布之間的關系，這也是我們負采樣政策遵守的準則。據此，我們提出負采樣分布應該與正采樣分布呈現正但次線性相關，即p_n (u│v)∝p_d (u│v)^α,0<α<1。
在理論的指導下，我們提出了一種有效且可擴充的負采樣政策，即馬爾可夫鍊蒙特卡羅負采樣（MCNS），用自對比近似估計正采樣分布，用Metropolis-Hastings加速負采樣過程。
具體來說，我們使用目前編碼器的内積估計正采樣分布，即這種估計形式類似于RotatE[1]中的技術，并且非常耗時。每次采樣都需要O(n)的時間複雜度，難以在大規模圖上實作。我們的MCNS借助Metropolis-Hastings算法解決這一問題。
下圖是我們提出的MCNS架構，采用DFS周遊得到最後一個節點的馬爾可夫鍊，使用Metropolis-Hastings加速負采樣過程，并将采樣得到的負樣本和正樣本輸入到編碼器中，獲得節點的向量表示。為了訓練模型的參數，我們将二進制交叉熵損失函數替換為hinge loss，其基本思想是最大化正樣本對的内積，同時，確定負樣本對的内積比正樣本對的内積要小一定的門檻值。Hinge loss的形式如下：
其中(u,v)是正樣本對，(x,v) 是負樣本對，γ是門檻值，是一個超參數。
在MCNS中，我們對每個節點使用Metropolis-Hastings算法以加速負采樣過程，其中提出的分布q(y|x)也影響着收斂速度。我們的q(y|x)是按照1:1的比例混合均勻采樣和最近鄰的k個節點的采樣。MCNS進行負采樣的過程如下：
為了證明我們提出的MCNS的有效性，我們在3個常用的圖表示學習任務上，使用典型的3個圖表示學習算法，在5個資料集上進行了實驗。這些資料集涵蓋了19個實驗設定，涵蓋了從資訊檢索[2]，推薦[3,4]和知識圖譜嵌入[5,6]中收集到的8個負采樣政策。在個性化推薦任務上，如下表所示，無論采用network embedding 或GNN作為編碼器，MCNS始終優于其他8個負采樣政策，比最佳的baseline實作2%-13%的顯著提高。此外，我們還在個性化推薦任務上，對比了不同負采樣政策的效率。如下圖所示，相對于其他啟發式的負采樣政策，我們提出的MCNS具有更優的效率。
我們在Arxiv資料集上評估了不同負采樣政策在鍊路預測任務上的性能，實驗結果表明MCNS實作了不同程度性能的提高。此外，我們還在BlogCatalog資料集上評估節點分類任務，結果表明無論采用network embedding 或GNN作為編碼器，MCNS均穩定地勝過所有的baselines。
最後，我們還做了一些額外的實驗以便進一步了解我們所提出的MCNS。在之前的理論部分，我們從目标函數和方差的角度分析的負采樣政策的準則。但是，可能會産生以下疑問：（1）采樣更多的負樣本是否總是有幫助的？（2）為什麼我們的結論與“對附近節點進行正采樣而對遠處節點進行負采樣”的直覺相沖突？
為了進一步加深對負采樣的了解，我們設計了兩個擴充實驗，以驗證我們的理論。如下圖左圖所示，如果我們采樣更多的負樣本，一開始性能會随着負樣本數量的增加而提高，随後則會降低。根據均方誤差計算公式，一開始，采樣更多的負樣本會降低方差，進而提高性能。但是，當性能達到最佳狀态後，繼續增加負樣本則會使性能下降，原因在于增加了額外的偏差。右圖表明了對更遠處的節點進行負采樣會導緻災難性的後果。我們設計了一種名為inverseDNS的政策，在候選的負樣本中選擇得分最低而不是得分最高的樣本作為負樣本，也就是選擇更遠處的節點作為負樣本。實驗結果表明MRR和Hits@30随着M的增加而下降，是以驗證了我們的理論。
參考文獻:
[1]Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. 2019. Rotate: Knowl- edge graph embedding by relational rotation in complex space. arXiv preprint arXiv:1902.10197 (2019).
[2] Jun Wang, Lantao Yu, Weinan Zhang, Yu Gong, Yinghui Xu, Benyou Wang, Peng Zhang, and Dell Zhang. 2017. Irgan: A minimax game for unifying generative and discriminative information retrieval models. In SIGIR’17. ACM, 515–524.
[3] Yifan Hu, Yehuda Koren, and Chris Volinsky. 2008. Collaborative filtering for implicit feedback datasets. In ICDM’08. Ieee, 263–272.
[4] Weinan Zhang, Tianqi Chen, Jun Wang, and Yong Yu. 2013. Optimizing Top-N Collaborative Filtering via Dynamic Negative Item Sampling. In SIGIR’13. ACM, 785–788.
[5] Liwei Cai and William Yang Wang. 2018. KBGAN: Adversarial Learning for Knowledge Graph Embeddings. In NAACL-HLT‘18. 1470–1480.
[6] Yongqi Zhang, Quanming Yao, Yingxia Shao, and Lei Chen. 2019. NSCaching:Simple and Efficient Negative Sampling for Knowledge Graph Embedding. (2019), 614–625.
更多資料挖掘内容檢視：
《KDD論文精華解讀》