一、背景

擴展 GCN 很困難，因為很多在大資料環境中，很多基于這些 GCN 設計的假設都不成立了，比如，所有的基于 GCN 的推薦系統需要在訓練時使用圖的拉普拉斯矩陣，但是當頂點數很大的時候，這就不現實了，因為算不出來，

所以本文提出了一種在 Pinterest 上的大規模深度推薦引擎，開發了一種高效的圖卷積演算法 PinSage，融合了隨機游走和圖卷積，來生成頂點（物品）的表示，同時整合了頂點資訊和圖結構，

二、模型結構

本文方法的計算關鍵在于區域圖卷積的表示(notion)，我們使用多個卷積模塊來聚合一個頂點區域的鄰域特征資訊，來生成這個頂點的 embedding（比如一個物品），每個模塊學習如何從一個小的圖鄰域中聚合資訊，并且通過堆疊多個這樣的模塊，我們的方法可以獲得區域網路的拓撲結構資訊，更重要的是，這些區域卷積模塊的引數對所有的頂點來說是共享的，這使得我們的方法的引數的計算復雜度與輸入的圖的大小無關，

1. Forward propagation algorithm

考慮對頂點 u 生成 embedding z u z_u zu? 的任務，需要依賴頂點的輸入特征和這個頂點周圍的圖結構，
PinSage 演算法是一個區域卷積操作，我們可以通過這個區域卷積操作學到如何從 u 的鄰居聚合資訊，這個步驟為：

從本質上來說，我們通過一個全連接神經網路對 ? v ∈ N ( u ) ?v∈N(u) ?v∈N(u)
，也就是 u 的鄰居的表示 z v z_v zv? 進行了變換，之后在結果向量集合上用一個聚合/池化函式（例如：一個 element-wise mean 或是加權求和，表示為 γ）（Line 1），這個聚合步驟生成了一個 u 的鄰居N(u) 的表示 n u n_u nu?，之后我們將這個聚集鄰居向量 n u n_u nu?和 u 的當前表示向量進行拼接后，輸入到一個全連接神經網路做變換（Line 2），除此以外，第三行的 normalization 使訓練更穩定，而且對近似最近鄰搜索來說歸一化的 embeddings 更高效，演算法的輸出是集成了 u 自身和他的區域鄰域資訊的表示，

2. Importance-based neighborhoods

我們方法中的一個重要創新是如何定義的頂點鄰居 N ( u ) N ( u ) N(u)，也就是我們在演算法1中是如何選擇卷積的鄰居集合，盡管之前的 GCN 方法簡單地檢驗了 k-hop 鄰居，在 PinSage 中我們定義了基于重要性的鄰域，頂點 u 的鄰居定義為 T 個頂點，這 T 個頂點對 u 是最有影響力的，具體來說，我們模擬了從頂點 u 開始的隨機游走，并且計算了通過隨機游走對頂點的訪問次數的 L1 歸一化值，u 的鄰居因此定義為針對頂點 u 來說 T 個最高的歸一化的訪問數量的頂點，

這個基于重要性的鄰域定義的優點有兩點，第一點是選擇一個固定數量的鄰居頂點來聚集可以在訓練程序中控制記憶體開銷，第二，在演算法1中聚集鄰居的向量表示時可以考慮鄰居的重要性，特別地，我們在演算法1中實作的 γ 是一個加權求均值的操作，權重就是 L1 歸一化訪問次數，我們將這個新的方法稱為重要度池化(importance pooling)，

3. Stacking convolutions

每次使用演算法1的 CONVOLVE 操作都會得到一個頂點的新的表示，我們可以在每個頂點上堆疊卷積來獲得更多表示頂點 u 的區域鄰域結構的資訊，特別地，我們使用多層卷積，其中對第 k 層卷積的輸入依賴于 k?1 層的輸出，最初的表示（”layer 0”）等價于頂點的輸入特征，需要注意的是，演算法1中的模型引數 （ Q , q , W （Q , q , W （Q,q,W 和 w）在頂點間是共享的，但層與層之間不共享，

演算法2詳細描述了如何堆疊卷積操作，針對一個 minibatch 的頂點 M 生成 embeddings，首先計算每個頂點的鄰居，然后使用 K 個卷積迭代來生成目標頂點的 K 層表示，最后一層卷積層的輸出之后會輸入到一個全連接神經網路來生成最后的 embedding z u ， ? u ∈ M z_u ， ? u ∈ M zu?，?u∈M，

三、模型訓練

1. loss

使用 max-margin ranking loss 來訓練 PinSage，在這步，假設我們有了一組標記的物品對 L ， ( q , i ) ∈ L L ， ( q , i ) ∈ L L，(q,i)∈L認為是相關的，也就是當查詢 q 時，物品 i 是一個好的推薦候選項，訓練階段的目標是優化 PinSage 的引數，使得物品對 ( q , i ) ∈ L ( q , i ) ∈ L (q,i)∈L 的 embedding 在標記集合中盡可能的接近，

為了訓練模型的引數，我們使用了一個基于最大邊界的損失函式，基本的思想是我們希望最大化正例之間的內積，也就是說，查詢物品的 embedding 和對應的相關物品的 embedding 之間的內積，與此同時我們還想確保負例之間的內積，也就是查詢物品的 embedding 和那些不相關物品 embedding 之間的內積要小于通過提前定義好的邊界劃分出的正例的內積，對于單個頂點對 embeddings ( z q , z i ) : ( q , i ) ∈ L ( z_q , z_i ) : ( q , i ) ∈ L (zq?,zi?):(q,i)∈L 的損失函式是：

其中， P n ( q ) P_n ( q ) Pn?(q) 表示物品 q 的負樣本分布，Δ 表示 margin 超引數，

2. 負樣本采樣

負樣本采樣在我們的損失函式中作為 edge likelihood 的歸一化系數的近似值，為了提升 batch size 較大時的訓練效率，我們采樣了 500 個負樣本作為一組，每個 minibatch 的訓練樣本共同使用這一組，相比于對每個頂點在訓練時都進行負樣本采樣，這極大地減少了每次訓練時需要計算的 embeddings 的數量，從實驗上來看，我們發現這兩種方法在表現上沒什么特別大的差異，

在最簡單的情況中，我們從整個樣本集中使用均勻分布的抽樣方式，然而，確保正例( ( q , I ) ( q , I ) (q,I))的內積大于 q 和 500 個負樣本中每個樣本的內積是非常簡單的，而且這樣做不能提供給系統足夠學習的解析度，我們的推薦演算法應該能從 200 億個商品中找到對于物品 q 來說最相關的 1000 個物品，換句話說，我們的模型應該能從超過 2 千萬的物品中區分/辨別出 1 件物品，但是通過隨機采樣的 500 件物品，模型的解析度只是 1/500，因此，如果我們從 200 億物品中隨機抽取 500 個物品，這些物品中的任意一個于當前這件查詢的物品相關的幾率都很小，因此，模型通過訓練不能獲得好的引數，同時也不能對相關的物品進行區分的概率很大，為了解決上述問題，對于每個正訓練樣本（物品對 ( q , I ) ( q , I ) (q,I)），我們加入了”hard”負例，也就是那些與查詢物品 q 有某種關聯的物品，但是又不與物品 i 有關聯，我們稱這些樣本為”hard negative items”，通過在圖中根據他們對查詢物品 q 的個性化 PageRank 分數來生成，排名在 2000-5000 的物品會被隨機采樣為 hard negative items，hard negative examples 相比于隨機采樣的負樣本更相似于查詢物品，因此對模型來說挑戰是排名，迫使模型學會在一個好的粒度上分辨物品，

參考資料

Graph Convolutional Neural Networks for Web-Scale Recommender Systems