1 介紹
阿里巴巴團隊發表於KDD 2018，paper為Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba。阿里的推薦系統是按照matching + ranking的兩步策略，本文解決的是matching階段的問題，即商品召回階段的問題。
paper中說到Taobao的推薦系統主要面臨了3個主要問題：
可擴充套件性：十億使用者，二十億商品的量級；稀疏性：有些使用者和商品之間的互動資訊特別少，導致無法精確的訓練推薦模型；冷啟動：新商品的冷啟動問題，taobao上每小時會上線百萬級的新商品，而使用者與新商品之間沒有互動資訊，因此無法很好建模使用者對商品偏好。paper主要解決的是matching階段中對應上面的3類問題。在這之前，taobao的推薦系統在召回階段主要是使用協同過濾的方法，計算不同商品之間的相似性，來生成商品候選集合。這篇文章中主要是用Graph技術來學習商品的embedding向量，但是考慮到前人工作中Graph embedding的缺點，paper作者引入了輔助資訊來學習商品向量表達，再計算商品之間的相似性。作者在構建商品Graph的時候，使用了啟發式的方法，從數十億的使用者歷史行為中構建商品Graph。paper中先後實驗的方案為：
Base Graph Embedding (BGE)；Graph Embedding with Side information (GES)；Enhanced Graph Embedding with Side information (EGES)。最後作者也介紹了在taobao的大規模的使用者和商品量級的規模下，他們也構建了graph embedding系統XTensorflow來支援演算法的上線。
2 框架這篇文章的思路也是受到最原始的Graph Embedding方法的啟發，例如DeepWalk方法，DeepWalk方法就是先通過在graph中隨機遊走來生成節點的序列，然後應用Skip-gram演算法來學習graph中節點的Embeddding表示。沿著這個思路，paper中也是按照兩步來介紹的，1）基於使用者歷史行為構建圖結構，2）學習圖中item的embedding表示。
2.1 基於使用者歷史行為的 Item Graph的構建在淘寶中，使用者的歷史行為都是具有時間序列特點的，例如圖2（a）所示，而協同過濾演算法中只考慮到商品之間的共現性，而沒有將商品的序列關係納入考慮，而在我們的item graph構建過程中，會考慮商品的序列資訊，但是由於計算量和儲存空間的成本高、以及使用者的興趣具有隨著時間而漂移的特點，因此我們在使用使用者歷史行為資訊時，基於以前的經驗，只使用一個小時時間視窗內的歷史行為item用於構建item graph，paper中也提到，對於這種一個小時的時間視窗稱之為session。
當我們得到基於session的使用者歷史行為時，在一個session中，我們可以得到item之間的順序關係，例如在圖2（a）中的順序關係已經反映在了圖2（b）中了，而在圖2（b）中，節點之間的連線權重被賦值為兩個item共現的次數。但是在構建item graph時，對於下面的三類髒資料和不正常行為會過濾掉：
點選後停留時間太短，例如不超過1秒的；三個月內購買超過1000個商品或者點選次數大於3500次的，這種過於活躍的使用者，有可能是刷單等異常行為；由於商家會給同一個標誌碼的商品不斷地做一些細節上的更新，但是有可能一段時期後，同一個標誌碼的商品已經變得完全不一樣了，對於這種情況，我們會直接去除。2.2 Base版的Graph Embedding基於圖2（b）中的權重有向item graph，paper中使用DeepWalk的隨機遊走方法生成節點序列，並在序列上執行Skip-gram演算法來學習節點的Embedding表示，按照節點間的權重關係將隨機遊走的節點轉移概率定義為：
我們使用Skip-gram演算法學習Embedding向量，該演算法是最大化序列中兩個節點的共現概率，因此我們可以關聯到下面的負數似然概率的優化問題：
其中，w表示序列中上下文節點的視窗大小，如果假設節點之間是相互獨立的，即獨立性假設的情況下，可以得到下面的公式：
我們通過借鑑Word2vec中的負取樣演算法，那麼方程（3）可以轉化為下面的式子：
其中，
表示v_i的負樣本，而 σ 表示sigmoid函式
理論上來說，
越大越好，當然這也會帶來更大的計算量上的負擔。
2.3 加入輔助資訊的Graph Embedding雖然在基本的graph embedding方法中，通過使用者的行為序列，可以學習到協同過濾方法無法學習到的高階相似性（因為加入了點選商品的序列資訊），但是對於需要冷啟動的商品，由於其缺乏使用者和該商品之間的互動，因此仍舊無法較好的學習其embedding表示。因此這部分使用了item的輔助資訊來學習item Embedding，用於解決item的冷啟動問題。
paper中舉了一些例子來說明當對item加入category、shop、price等輔助資訊時的作用，例如來自於優衣庫（shop相同）的兩件外套（category相同），那麼他們的embedding表示應該比較相似。基於類似的假設，paper中提出了GES的方法，如圖3所示。
在GES中，使用W表示item及其輔助資訊的embedding矩陣，W_v^0 表示item v的embedding，W_v^s表示item v的第s個輔助資訊的embedding，如果一共有n個輔助資訊的話，那麼對item v來說，將會有 n+1 個向量
其中d表示embedding向量的維度，在paper中，作者提到了經驗上的結論為，把item和其輔助資訊的embedding的維度設定成相同時的效果更好。
在圖3中可以看到，paper中的處理方式比較common，新增一個隱層，對這n+1個embedding向量做avg pooling的聚合操作，其中，H_v就表示item v的聚合embedding表示了。這樣的處理方式貌似可以較好的解決item的冷啟動問題了。
2.4 加入輔助資訊的增強型Graph Embedding上面GES演算法中，雖然使用了輔助資訊學習到了更好的item的embedding表示，而且一定成都上緩解了item的冷啟動問題，但是依然存在一些明顯的問題，就是item v的所有的輔助資訊對於最終的embedding表示的貢獻不一定是完全相同的，但是在GES方法中是按照完全一樣來計算的。對於item v，
表示權重矩陣， A_{ij} 表示第i個item的第j個輔助資訊，而A的第一列數值 A_{*0} 表示item 自身的權重。也就是說，a_v^s 表示item v的第s個輔助資訊的權重，而 a_v^0 表示item v本身的權重值，而該層組合了不同的輔助資訊的加權平均網路定義如下：
paper中使用指數計算得到權重，即 e^{a_v^j} 代替 a_v^j 以確保每個輔助資訊的權重貢獻值大於0。
在訓練樣本中，對於節點v和其上下文節點u，使用
來表示u的embedding表示，使用y來表示其label，那麼EGES的loss函式為
上式對 Z_u 求導（其實就是交叉上損失函式的求一階導數）得到
如果公式（9）再進一步對輔助資訊的權重求導的話，得到
而如果公式（9）再進一步對輔助資訊的embedding表示求導的話，得到
下面是EGES的虛擬碼，Alg1給出了EGES的整個框架，Alg2給出了權重Skip-gram演算法的計算流程，Alg2的核心其實就在於根據正、負樣本更新引數輔助資訊權重 a_v^s 和輔助資訊embedding表示 W_v^s 。
3 實驗3.1 離線評估實驗中使用了比較common的連結預測任務，使用的資料集為Amazon和Taobao的資料集，他們對應的節點數量、邊數量、輔助資訊數量、稀疏度如表1所示，兩個資料集的稀疏性都非常高。其中Amazon資料集的item graph主要根據共現性來構造，而taobao資料集主要基於前面講到的session-based的歷史行為來構造的。
paper中主要實驗的方法為BGE, LINE, GES, EGES，其中LINE方法是在graph embedding中捕獲一階和二階近似。
實驗結果如表2所示，結果顯示，GES和EGES方法在Amazon和Taobao資料集的效果均優於BGE、LINE(1st)、LINE(2nd)方法的效果。值得注意的地方為：
GES和EGES方法在 Taobao資料集相比於Amazon資料集上的效果提升更加明顯，這可能是由於Taobao資料集的輔助資訊更加豐富和有效；EGES方法相比於GES方法，可以使得Amazon資料集的效果提升更加明顯，但是對於Taobao資料集的效果提升卻不那麼明顯，這可能是因為GES的效果已經非常好了，所以EGES的提升也沒那麼顯著。3.2 線上A/B測因為paper中學習到的item 的向量表示最終用於推薦系統中的item召回階段，因此最終評估item embedding的方式也是推薦系統中常見的點選率評估方法，如果在召回階段通過使用graph embedding代替傳統的CF方法的召回物料品質更高的話，那麼對於最終線上的ctr一定會有提升的效果的。
3.3 Case Study
視覺化：paper中使用了tensorflow中自帶的視覺化工具進行embedding的視覺化，從圖7（a）中可以看到不同種類的鞋子分佈在不同的簇中，而具有相似輔助資訊的鞋子會更加相似；而圖7（b）中進一步分析了乒乓球、羽毛球、足球這三種不同運動的鞋子，並在圖中展示了乒乓球、羽毛球這兩種鞋子更加相近，而足球鞋子會距離更遠一些，這也更加符合中國人的特點，因為乒乓球、羽毛球更偏向於室內運動（相似性更高），而足球更偏向於室外運動。
冷啟動item：對於沒有user和item之間互動資訊的冷啟動item來說，可以使用其輔助資訊向量的average pooling值來表示該冷啟動item，這在之前傳統的CF方法中無法實現。
EGES中的權重：圖6可視化了不同item的不同型別的輔助資訊的權重，從圖中可以看到：
不同的item的輔助資訊的權重大小是不同的；所有的item中，Item自身embedding表示的權重是最大的；除了Item自身embedding表示的權重外，Shop的embedding表示的權重是最大的，這是因為對於Taobao的使用者來說，使用者會為了方便性和低價的好處，更傾向於在同一店鋪中購買商品。4 系統部署和操作在介紹Taobo的graph embedding學習系統之前，我們先了解下整個taobao的推薦系統，其分為線上系統和離線系統。 線上系統包括Taobao個性化平臺（TPP）和排序服務平臺（RSP），其線上系統的整個工作流為：
使用者開啟app後，TPP會獲取使用者最新的資料特徵以及從離線系統中獲取item候選集，然後將item候選集喂入到RSP中，排序模型會對使用深度神經網路對候選集的item進行打分和排序，並將排序結果返回給TPP，然後TPP再將排序結果展示到使用者app上。使用者在使用過程中的行為資訊會被收集下來並儲存成日誌資料，之後會再繼續服務於離線系統。而對於離線系統中的graph embedding的工作流如下，這裡只簡單說下，具體可以參考下paper原文：
獲取到使用者行為的日誌資料，取最近3個月的資料構建item graph。但是在此之前需要對使用者資料進行反爬蟲處理（以及其他去除髒資料的資料處理方法），然後才基於使用者行為取生成sessin-based的序列。然後就是實現item graph方法，再基於基於ODPS平臺的分散式訓練來進行學習；在XTF平臺上，整個的日誌獲取、反爬處理、item graph構建、隨機遊走生成session序列、item to item的相似性計算和對映生成這些過程只需要在6個小時內就可以計算完成。5 總結和未來展望總結：針對稀疏性、item冷啟動、大規模（十億使用者和二十億商品）這三個問題，作者分別提出了解決方案。對於稀疏性、item冷啟動問題，paper提出了將item的輔助資訊融入到item graph中來學習的graph embedding，而對於大規模的資料量問題，則詳細介紹了訓練graph embedding所依託的阿里的各種計算平臺的優勢。
展望：paper中也提出了未來將要繼續探索的一些領域，一是將在graph embedding中加入attention機制，以更靈活地學習到輔助資訊的權重；二是將item下的使用者評論中的文字資訊資料加入到item graph中去學習graph embedding。