新零售智能引擎事業群出品
背景
圖可以用來描述事物之間的普遍關系，并把它們編碼在參數化的圖結構裡（如鄰接矩陣）。基于專家的構圖方法需要昂貴的人工資訊，很難快速部署到廣泛的生産生活中，也就推動了基于資料驅動的圖生成算法的研究。後者拟構造一張可以最好地描述輸入資料産生過程的圖，比如推薦場景中，資料可以是使用者的購物記錄，商品網絡圖表達物品之間的關系強度。由于基于資料驅動的算法嚴重依賴資料的條件獨立性假設，也即訓練場景和測試場景有同樣的資料分布，一旦獨立性假設遭到破壞，圖的表現性能就會大打折扣。然而獨立性假設在現實中是十分脆弱的，資料采樣的過程也一定存在時間和間的局限性。比如，線上購物的使用者中，通常女性比男性比例多，青年人比老年人比例多，那麼學出來的圖就會産生對年輕女性的偏好，對其他群體則不太友好。是以如何提升圖結構的泛化性能是非常有實踐意義的課題。
挑戰
雖然學習因果圖可以直接抓取事物之間的不變的因果關系、帶來穩定性，但是學因果圖的計算複雜度很大、很難拓展到大規模的網絡中，而且因果圖自身是有向無環圖，也不能描述場景中廣泛的有環結構。另一方面，圖結構中包含複雜的高階和非線性關系，直接在原始圖結構空間（如鄰接矩陣）修正偏差是很困難的，而且用于生成圖結構的輸入資料（如集合類型）是高維稀疏的。為了學習穩定的一般性圖結構，本文提出了一種從多異質環境中學習穩定圖結構的方法 SGL。
模型
為了針對更加普遍的場景，我們假設輸入資料類型是高維稀疏的集合資料類型。一條集合資料的産生可以了解為從空集開始，一步一步向集合中添加元素，直至集合達到飽和的過程。對第 m 個資料環境，每次添加時，給定目前集合 s，各個元素 IkIk 加入的機率是集合的條件生成機率 p(m)(Ik|s)p(m)(Ik|s)。顯然， pm I |s p I |s ( k ) m( k )和 圖結構 G(m)G(m) 包含的元素關系有關，可表示成：
由于各個異質環境存在采樣偏差，其相應的條件生成機率也是有偏的。假設環境的選擇是随機的，那麼平均各環境的機率空間就是對無偏環境的估計。
由于圖結構中充滿了高階和非線性的關系，直接在圖結構的參數空間（鄰接矩陣）去偏差是很難的，如果我們可以建立圖結構到條件生成機率的映射，通過在生成機率空間平衡偏差，就能間接修正圖結構的偏差。
1. 基于圖的稀疏集合資料生成
根據以上想法，我們的第一件事就是建立圖結構到條件生成機率的映射。已知多個有差異的有偏資料環境，我們首先可以利用基于聯合發生頻率的方法在各個環境中建構初始的圖，每個點表示集合中的元素。SGL 架構由 2 個子產品構成，第一個子產品是圖卷積神經網絡，可以把初始圖的結構特性嵌入到輸出的元素表征中。這樣，通過池化一個集合的所有元素表征，我們可以得到對應集合的特征向量。特征向量會經過第二個子產品，元素級的變分編碼器（E-VAE），重構真實資料的同時，學習集合的生成機率。具體地說，集合的特征向量經過編碼器會得到隐空間分布，并能從中采樣一個隐向量；隐向量分别和各個元素的表征聯合解碼，産生該元素被選入集合的強度；把所有元素的強度投影到機率空間，就能輸出集合的生成機率。假設輸入集合資料是飽和的，我們可以通過盡可能重構原始資料的方式，學習環境中的條件生成機率空間。也就是說，我們希望條件于真實樣本的輸出機率，采樣新元素加入後，集合保持不變，最大化真實樣本出現的機率。
考慮到集合資料的稀疏性，我們用 negative log likelihood 目标函數優化模型的學習。
同時，優化 E-VAE 裡隐層分布和預定義的正态分布的 KL 散度距離：
2. 學習穩定的圖結構
在各個環境中訓練一套參數共享的 GCN 和 E-VAE，我們可以得到給定相同輸入集合，各個環境不同的條件生成機率。此時，假設有一個無偏資料環境，并初始化其中的圖結構。我們能夠優化無偏環境的圖結構，使得從這張圖輸出的無偏環境中的生成機率是各個有偏環境的均值，進而得到穩定的圖結構。
考慮到各部分之間的互相作用，我們最終聯合優化 GCN、E-VAE 和穩定圖結構的鄰接矩陣。模型通過 SGD 的架構優化，是以對圖規模的适用性也比較友好。
實驗
為了驗證模型的有效性，我們分别在模拟資料和真實資料上進行了實驗。模拟實驗的部分，我們先利用有偏的随機遊走政策在兩個環境中産生了資料分布有差異的遊 走路徑。政策由p0（0 階關系，如使用者的先驗偏好）、p1（元素的一階關系）、p2（元 素的二階關系）控制兩個環境中的差異程度。p0 、 p1 、 p2 的值越大，說明分布差異 越大。然後在各個環境中的訓練資料基于聯合發生頻率建圖，可以得到内含關系不同的 2 張圖。
除了單一環境的頻率圖G1、G2，我們的基線模型還有GA = GG 12 + 2 和均勻比例 混合各環境資料構成的頻率圖GC。基于G1、G2 和訓練資料，我們可以學到穩定的圖結構GS。
為了測試不同圖結構的穩定性，我們設計了集合預測任務：首先把一個測試集合劃分成目标元素和剩餘已知元素，給定從圖結構學出來的元素表征和測試集已知元素，目标是從所有候選節點中選出目标元素，也即選出與集合中剩餘元素的距離最近的元素。進一步，我們把兩個環境的測試資料以 0:10、1:9、……、10:0 比例混合，可以得到 11 個測試組。統計基于不同圖結構學出來的元素表征，用元素表征之間的平均 COS 距離作為測度，在多個資料分布不同的測試組中的預測準确率。為了保證明驗的公平性，我們用同一個 GCN 學習不同圖中的元素表征。
從以下結果可以看出，單一環境中的圖随着另一個環境資料的增加，圖中關系的适用性越來越差；簡單對各環境的圖線性平均，沒有考慮到圖中的非線性關系；混合各環境資料構圖，會存在原始建圖方法的模型偏差，也不能解決 0 階關系，如使用者的先驗偏好的差異；穩定的圖結構可以以最小的預測标準差達到最好的預測準确率，因為它可以平衡不同測試環境中的高階、非線性的關系偏差。
真實實驗上，我們分别對使用者群體偏差和商品曝光偏差的場景做了測試。前者是指不同環境中使用者成分比例不同，後者是指不同環境中商品的主導成分的熱度不同。對于使用者群體偏差，我們直接把女性使用者和男性使用者劃分兩個環境；對于商品曝光偏差，我們先篩選出熱門商品，然後根據一個購物記錄中是否熱門商品占比超過一半，把所有記錄劃分到熱門主導環境和冷門主導環境。基線模型和預測任務同模拟實驗。
實驗中觀察到，不同環境的預測難度是不同的：女性的購物行為比男性的更容易預測，可能是由于女性更傾向于一次相關性強的商品；熱門商品較多的購物記錄也更容易預測，可能由于熱門商品之間的相關性更強。SGL 依然可以從不同環境中學習更泛化的資訊，達到最好的預測率。
總結：
為了從多異質環境中學習穩定的圖結構，我們提出了SGL學習架構。架構通過基于圖的稀疏資料生成，建立了圖結構到生成機率空間的映射，然後在生成機率空間平衡有偏資訊，進而能修正圖的結構偏差。實驗證明，我們提出的方法确實可以提升圖結構的穩定性，并在實際問題中起到有效作用。
參考文獻：
[1] Lada A Adamic and Eytan Adar. 2003. Friends and neighbors on the web. Social networks 25, 3 (2003), 211–230.
[2] Aleksandar Bojchevski, Oleksandr Shchur, Daniel Zügner, and Stephan Günnemann. 2018. Netgan: Generating graphs via random walks. arXiv preprint arXiv:1803.00816 (2018).
[3] Peter Bühlmann, Jonas Peters, Jan Ernest, et al. 2014. CAM: Causal additive models, high-dimensional order search and penalized regression. The Annals of Statistics 42, 6 (2014), 2526–2556.
[4] Abhishek Gupta, Coline Devin, YuXuan Liu, Pieter Abbeel, and Sergey Levine. 2017. Learning invariant feature spaces to transfer skills with reinforcement learning. arXiv preprint arXiv:1703.02949 (2017).
[5] Kilol Gupta, Mukund Yelahanka Raghuprasad, and Pankhuri Kumar. [n.d.]. A Hybrid Variational Autoencoder for Collaborative Filtering. ([n. d.]).
[6]Bo Jiang, Ziyan Zhang, Doudou Lin, Jin Tang, and Bin Luo. 2019. Semi-supervised learning with graph learning-convolutional networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 11313–11320.
[7] Diederik P Kingma and Max Welling. 2013. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114 (2013).
更多資料挖掘論文檢視：
《KDD論文精華解讀》