PinSage:第一個基於GCN的工業級推薦系統
論文：Graph Convolutional Neural Networks for Web-Scale Recommender Systems
作者：Rex Ying??, Ruining He來源：KDD, 2018
0.概括
本文的理論基礎為上一篇文章：GraphSAGE: GCN落地必讀論文
斯坦福和Pinterest公司合作提出了第一個工業級別（數十億節點和數百億邊）基於GCN的推薦系統，並在離線評估和AB實驗選中取得了不錯的效果。
斯坦福圖這塊非常厲害，Node2Vec和GraphSage都是出自這裡，論文中GCN落地的技巧和創新非常值得借鑒。
1.問題設定
用戶在Pinterest中 自己感興趣的東西用圖釘(pin)釘在釘板(broad)，包擴10億pin ，10億board 以及180億邊（若pin在broad中，則它們之間存在一條邊）。
目標是利用pin-broard二分圖結構和屬性（如描述文本、圖片特徵），生成pin的高質量的embedding用於推薦任務，如相關pin推薦，或者作為機器學習系統的輸入特徵。
2. PinSage框架
本章節描述PinSage 框架和訓練細節，以及基於訓練好的模型使用MapReduce高效生成每個節點的embedding。
2.1 局部圖卷積
局部圖卷積是本文的核心，通過對節點鄰域子圖進行多個卷積操作，以此聚合鄰居特徵的方式生成節點embedding。
每個卷積模塊都學習如何聚合來自子圖的信息，並堆疊起來，可以獲得局部網路拓撲信息。並且卷積模塊的參數在所有節點之間共享，大大減少複雜度，不受輸入圖尺寸的影響。
2.2 模型框架
本章介紹圖卷積的前向傳播演算法：利用節點u的特徵和其周圍的圖結構，生產節點的embedding
2.2.1 卷積層
學習如何將u周圍鄰居信息聚合：
輸入：
- 節點u當前embedding
- 鄰居embedding
,
為u的鄰居集合
- 鄰居權重集合
- 對鄰居embedding進行聚合／pooling 的函數
：如簡單平均、加權求和、最大。
輸出：節點u新的embedding
演算法：
- 對每個鄰居embedding進行線性變換後非線性輸出，然後進行有權聚合／pooling。
- 拼接節點u自身embedding和鄰居聚合embedding,再進行線性變換後非線性輸出 （實踐中拼接操作比平均操作效果更好）。
- 歸一化，可以使訓練更穩定，以及在近似查找最近鄰的應用中更有效率。
2.2.2 鄰居採樣
問題：獲得節點所有鄰居（如二階內）執行卷積，也會生成巨大的子圖，計算複雜度大，需要採樣。
對節點u的鄰居採樣：從節點u開始隨機遊走，統計每個節點的訪問次數（L1正則化），取訪問次數top的節點作為u的鄰居 （引自《Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time》）
2.2.3 堆疊多個卷積層
每次進行卷積時，得到一個節點新的表示，可以通過將卷積層堆疊起來，以聚合節點K跳鄰居內的特徵。下面演算法是對於minibatch的節點集合M，如何通過堆疊卷積生成emebdding：
輸入：minibatch 節點集合M， 深度K（卷積層數）、查找鄰居函數N
輸出：M內每個節點embedding
演算法（以K=2為例子）：
1. 獲得M中每個節點二跳鄰居（基於隨機遊走抽樣），並保存成三個集合：
=自身節點
自身節點+一跳鄰居
自身節點+一跳鄰居+二跳鄰居
2.生成M中每個節點embedding：
- 初始化:設置二跳內任意節點的輸入層為自身特徵:
- 進行兩層卷積及疊加操作：
- 第一次卷積，生成
中節點embeddinng，作為第二層卷積的輸入。（這個操作等價為一次傳播：將二跳鄰居信息傳播到一跳鄰居上，以及將一跳鄰居原有信息傳播到自身節點。 不傳播到二跳鄰居原因是接下來不會用到二跳鄰居信息了）
- 第二次卷積：以第一層卷積的輸出作為輸入，生成
中節點embedding （這個操作等價繼續做一次傳播）
- 全連接：將卷積結果輸入到全連接層。
2.3 模型訓練
2.3.1 標籤定義
正例：若用戶在點擊item q後馬上點了item i，可以認為i是q的好的推薦候選，即 是正例。
負例：在數十億中item中，大概率與p不相似，故簡單的方法是隨機採樣生成負例（後面會進一步做優化）
2.3.2 損失函數
訓練損失使用max-margin ranking loss，基本想法是使最大化正例embedding之間相關性，與此同時要保證負例之間相關性通過某個預定義margin 小於正例子。
為item q對應的負例分佈，
為對應節點i的embedding，
為超參（margin）
2.3.3 基於大的minibatch的多個GPU訓練
- 前向傳播：將minibatch等分，數量等於GPU數。然後每個GPU取minibatch中的一塊，使用相同的參數執行FP操作。
- 反向傳播：將每個GPU中參數梯度聚合在一起，同步執行SGD。
- batch 大小從512 到4096
- 使用warmup計劃：在第一個epoch將學習率線性上升到最高，然後指數下降
2.3.4 生產者-消費者minibatch架構
問題：GPU前向傳播計算，需要在CPU中查詢全圖鄰接矩陣和節點特徵矩陣（數十億節點GPU存儲不下），十分低效。
提出生產者-消費者模式，交替使用GPU和CPU：在CPU中抽取下一輪GPU計算所涉及的節點及鄰居構成的子圖G（re-index）、所涉及的節點特徵、負採樣操作。
2.3.5 負採樣
a.簡單負樣本操作每個minibatch時，隨機抽取500個items作為minibatch中所有正樣本共享的負樣本。
b. "hard"負樣本
在實際場景中，對每個q 在20億item中選擇1000個相關的item，相當於模型需要在200個item中分辨出1個。但上面負樣本的設置，使模型僅需從500個中分辨出1個，但這500個樣本基於與q沒有相關性，這會導致所訓練到的模型可能無法區分與q略有相關的item，即負樣本代表性不夠。
即需要尋找到與q有些相關，但不是正例的「hard」負樣本，具體的方法是通過定製化PageRank得到與q相關的排名在2000-5000的items進行隨機採樣認為是「hard」負樣本（為什麼是2000-5000？）
2.4 基於MapReduce預測節點embedding
問題：如果採用訓練時的方法進行全局預測節點embedding，會有大量重複計算，比如下圖中對6個節點進行預測，綠色節點embedding雖然已經學習到了，但還是會重複計算。
在全局預測時重構成兩個MapReduce 任務
- 計算所有pins的embedding。
- 將pins和對應的broads匹配，並對採樣鄰居pin的embedding進行pooling得到broad的embedding。
得到全量節點embedding後，導入到資料庫中供下游應用查詢。
2.5 最近鄰查找
- 近似KNN：《Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions》）
- 基於 Weak AND 操作的兩級檢索：《Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions》
3.附技巧和創新
3.1 提升GCN可擴展性技巧
3.1.1 On-the-fly convolutions
問題：傳統卷積操作是特徵矩陣與全圖拉普拉斯矩陣相乘（ ），非常耗時。
在局部卷積基礎上，採樣目標節點的鄰居做進一步優化：在目標節點及採樣鄰居構建的子圖上進行卷積操作。
3.1.2 Producer-consumer minibatch construction
問題：GPU前向傳播計算，需要在CPU中查詢全圖鄰接矩陣和節點特徵矩陣（數十億節點GPU存儲不下），十分低效。
提出生產者-消費者模式，交替使用GPU和CPU：在上一輪GPU計算時，並行進行CPU計算，抽取下一輪GPU計算所需的子圖G『和子圖內節點特徵（re-index）。
3.1.3 Efficient MapReduce inference
問題：在採用訓練時的方法進行全局預測，會有大量重複計算，比如下圖中對6個節點進行預測，綠色節點embedding雖然已經學習到了，但還是會重複計算。
在全局預測時重構成兩個MapReduce 任務：
- 計算所有pins的embedding。
- 將pins和對應的broads匹配，並對採樣鄰居pin的embedding進行pooling得到broad的embedding。
3.2 訓練技術和演算法上創新
3.2.1 Constructing convolutions via random walks
問題：獲得節點所有鄰居（如二階內）執行卷積，也會生成巨大的子圖，計算複雜度大，需要採樣。
節點u的鄰居採樣：從節點u開始隨機遊走，統計每個節點的訪問次數（L1正則化），取訪問次數top的節點作為u的鄰居 （引自《Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time》）。
3.2.2 Importance pooling
基於隨機遊走得到的相似度權重對鄰居特徵「加權聚合」，提升46%效果。
3.2.3 Curriculum training
在演算法訓練階段逐步在模型中加入越來越難的負樣本，提升12%效果。
推薦閱讀：
