NewBeeNLP原創出品??

公眾號專欄作者@上杉翔二?

悠閑會 · 信息檢索

圖神經網絡可以說是現在AI領域的超級寵兒。針對推薦系統的稀疏性問題，圖方法還真的很適合，主要原因有下：

• 推薦系統中存在很多的圖結構，如二部圖，序列圖，社交關系圖，知識語義圖等

• GNN比傳統的隨機游走等能有更好的表現

「PinSage」和「EGES」都是很好的落地實踐方法，也是這篇文章的重點。不過首先來看一下對于user-item二部圖的一般處理方法「GCMC」，通用的捕捉主要是需要處理四步，

構圖，包括如何采樣

鄰居聚合，包括多少信息應該被選擇

信息更新，如何整合中心節點的信息

最后的節點表示，然后再做下游的推薦預測任務。

PS！文末有我們新建立的『圖神經網絡』專題討論組，名額有限，趕緊加入一起精準交流吧！

GCMC

• 論文：Graph Convolutional Matrix Completion

• 地址：https://arxiv.org/pdf/1706.02263.pdf

發表在KDD2018，將user-item矩陣補全問題抽象成了二分圖的連接預測問題。每種連接預測的邊可以視為lable（如點擊，購買，收藏等等，1-5的評分也可以），然后用二部圖的方法來進行鏈接預測（即預測是否點擊或者預測評分是多少，就變成了分類預測問題）。

雖然也可以圖特征提取模型和鏈接預測模型，不過本文具體方式上如上圖，是使用圖自編碼器進行端到端建模。

Graph convolutional encoder

使用節點消息傳遞來更新模型參數，比如從item j 到 user i：

μ

其中c是正則化，W是控制變類型的權重，x是j的特征。從user到item當然也是同樣的方法，然后對每個節點都進行這樣的消息傳遞，最后就能得到每個節點的表示（如user的表示是用一個權重W對其所有相鄰節點的表示聚合得到）。

Bilinear decoder

重建鏈路，即把每個不同的評分等級（或者點擊，購買等）看作是一類

其中 ， 是用戶，商品的表示，Q是轉化矩陣，最后計算一個softma分數來預測“分類”就可以了。

GCMC使用消息傳遞+自編碼的思想，實際上在大圖應用中對每個節點做消息傳遞太過復雜。在實踐應用中還是使用隨機游走+其他，接下主要介紹PinSage，EGES。

PinSage

• 論文：Graph Convolutional Neural Networks for Web-Scale Recommender Systems

• 地址：https://arxiv.org/abs/1806.01973

• arxiv訪問不方便的同學后臺回復『0013』直接獲取論文

PinSage，一個能夠學習節點嵌入的隨機游走GCN，由Pinterest公司和Stanford完成的工作，首次將圖方法落地到了工業界。PinSage的理論背景是基于GraphSAGE^[1]，即歸納(inductive)式的學習，直接學習聚合函數而不是固定的節點，這也是其他的圖算法如GCN等等直推式(transductive)方法無法做到的，更能滿足實際中的圖節點是不斷變化的需求（節點和關系都會不斷的變化）。

目地

首先看看需求。Pinterest公司是世界上最大的圖片社交分享網站，業務采用瀑布流的形式向用戶展現圖片（抖音也很像這種模式），并且允許用戶創建和管理主題圖片集合。網站上的大量圖片稱為pins，而用戶喜歡的圖片集合（類似收藏夾），即稱為pins釘在畫板 的pinboards上。于是pins和boards就形成了如開頭圖片所示的二部圖形式。

挖掘這種二部圖的目的在哪里？分析用戶興趣，幫助用戶發現和匹配他們感興趣的圖片（商品）。雖然Pinterest的數據顯然都是一堆圖片，但是圖片節點本身的信息是無法通過CNN-based方法來解決的。如圖像識別，床欄和花園柵欄都是條狀的“欄”，被分為一類的概率很大，這并不能提供很多有用的信息，但是如果看看這兩個圖片在Graph中的位置就會發現區別很大，因為大門和花園柵欄通常會成為鄰居節點，但是床和大門卻很少相鄰。這也就是圖的優點，可以通過鄰居節點的信息，位置得到更豐富的嵌入特征。

模型

模型的輸入Graph是數十億對象的web-scale graph（30億個節點，180億），節點是圖片（需要注意的是，節點特征包括視覺特征和文本特征）。然后可以將圖分成Pin和Pinboard（實際上可以看作是pin的上下文信息），依照關系可以構建二部圖。

PinSage基于GraphSAGE，GraphSAGE^[2]博主以前已經整理過了，所以不做過多的展開。簡單來說它的核心思想就是學習聚合節點的鄰居特征生成當前節點的信息的「聚合函數」，有了聚合函數不管圖如何變化，都可以通過當前已知各個節點的特征和鄰居關系，得到節點的embedding特征。

GraphSage(Graph SAmple and aggreGatE)，很重要的兩步就是Sample采樣和Aggregate聚合，PinSage也是一樣。

首先是Convolve部分，這部分相當于GraphSage算法的聚合階段過程，偽代碼如下：

輸入是當下節點u的嵌入 ，然后得到它的鄰居節點 ，然后主要對應偽碼的1，2，3步：

聚合鄰居。可以看到，所有的鄰居節點特征 都經過一層dense層（由Q和q參數控制，再ReLU激活），再由聚合器或池化函數 （如mean等）將所有鄰居節點的信息聚合得到

更新當前節點的特征。將原特征 和 拼接后再經過一層dense層（W，w參數控制，再ReLU激活）

最后歸一化。直接對上一步得到的特征歸一化

所以其實Convolve和GraphSage的不同之處就在于聚合鄰居特征前多做了一步dense層抽象特征。

然后是minibatch對應著采樣鄰居部分，偽代碼如下：

采樣方法實際上就是在某個Minibatch內，以所有節點作為起始節點，然后做一個bfs去獲取一定數量的鄰居節點（步長固定為K的路徑），最后按照逐層方式進行多層的卷積。

• 2~7行是鄰居采樣階段。不沿用GraphSage的隨機采樣，而是使用訪問數作為重要性采樣。即每次從當前節點出發隨機走，雖然一開始是平均的，游走很多次之后，被走到的次數越多的節點，它相對于當前節點的重要性就越高，最終選取top-t的鄰居。

• 然后后面就是Convolve操作了逐層的生成節點嵌入特征。特別注意就是要經過dense之后才更新特征（偽碼15-16）。

訓練損失使用的是常規負采樣之后，再使用的max-margin ranking loss，即最大化正例之間的相似性，同時保證與負例之間相似性小于正例間的相似性：

訓練技巧

• 簡單負采樣會導致模型分辨的粒度過粗，沒針對性，特別是數據量如此大的情況下。所以增加了“hard”負樣本，即根據當前節點相關的PageRank排名，選排名在2000-5000之間的items為“hard”負樣本候選集，再進行隨機采樣，以增加訓練難度。

• Multi-GPU形式，minibatch取值為512-4096不等，大的batchsize可能會導致收斂困難。所以使用warmup：在第一個epoch中將學習率線性提升到最高，后面的epoch中再逐步指數下降。

• Minibatch里具有較多樣本，一個GPU無法計算。所以將這個Minibatch的圖切成很多個子圖，每個子圖在一個GPU上，來做GPU并行的求梯度，最后再將梯度匯集起來更新參數。

• 為了大規模計算設定的兩個MapReduce任務：

• • 執行聚合所有pins的嵌入特征。即把所有的pins映射到一個低緯度空間

  • 執行采樣鄰居特征得到board的嵌入特征，即直接通過采樣鄰接節點的特征來獲得。向量最終都會存在數據庫中供下游任務使用，實驗證明這種方法在不到24小時內可以為所有30億樣本生成Embedding。

PinSage的工程啟示

• 在鄰接點的獲取中，采用基于Random Walk的重要性采樣

• Hard負樣本抽取

• 基于鄰接點權重的重要性池化操作

• 利用圖片，文字信息構建初始特征向量

• 階段性存儲節點最新的Embedding，避免重復計算

PinSage和node2vec，DeepWalk的區別？

• node2vec，DeepWalk是無監督訓練，而PinSage是有監督訓練

• node2vec，DeepWalk不能用節點特征，PinSage可以

• node2vec，DeepWalk的參數和節點呈線性關系，很難用在超大型的圖上

如果只用完全hard的負采樣會怎么樣？

模型收斂速度減半，迭代次數加倍。所以其實PinSage使用的是一種curriculum的方式，即第一輪簡單負采樣，幫助模型快速收斂，然后再逐步加入hard的樣本，如第n輪使給負樣本集合中增加n-1個負樣本。直觀來講，PinSage有12億個樣本作為訓練正例，每個batch500個負例，每張圖又有6個hard負例。

負采樣之道

我之前也有一個疑問，就是為什么不使用「曝光未點擊」的樣本呢？

這里我也是弄混了兩個概念，所以就暫時整理在這篇文章里面吧。弄混的地方就是一般推薦系統的召回和排序的采樣是不一樣的！對于排序的效果提升才會比較講究“真負”樣本，所以一般就拿“曝光未點擊”的樣本，但這里反應的往往是用戶的直接反饋。但是召回不一樣，召回階段不僅僅是它的候選集大而已，與排序側需要挖掘用戶可能的喜好不同（其得到的list已經相當規整了，所以某種程度曝光未點擊策略只能算是個trick而已），召回需要將可能喜歡的盡可能得與其他海量不靠譜的樣本分隔開（這里的候選集會是千差萬別的），所以在召回側如果只拿用戶的反饋訓練，將會一葉障目導致更多不靠譜的都篩選不掉。

所以隨機采樣或許會是一個好選擇。但是這里又有兩個坑：一是盡量不要隨機選擇，因為推薦中充斥著二八定律和熱門商品等等，很容易被綁架，所以一般最好對熱門的降采樣，這就和word2vec很像了。二是隨機選擇的能力有限，無法學到細粒度的差異。

所以Hand Negative是很重要的。一方面和用戶匹配程度最高的是正樣本，另一方面完全差異很大的是負樣本，而hard negative需要找到難度適中的，沒那么相似的樣本，所以才有剛剛PinSage也使用的2000-5000的這個范圍，并且先簡單負采樣，再逐步加hard，且按照facebook EBR提到的，easy：hard維持在100：1是比較合理的。

EGES

• 論文：Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba

• 地址：https://arxiv.org/abs/1803.02349

• arxiv訪問不方便的同學后臺回復『0014』直接獲取論文

同樣的阿里其實也基于GraphSAGE做過相關工作（或許GraphSAGE在工業落地上是最有優勢的了），發自KDD 2018。為了解決在推薦系統中的老三樣困難：可擴展性，稀疏性和冷啟動。所以提出了：

• 可以根據用戶的歷史行為來構建商品圖（如上圖的a和b，根據用戶的一些點擊記錄，依照連續點擊應該存在關系，可以構造出如b一樣的item graph），并學習圖中所有商品的嵌入（如圖c的帶權隨機游走采樣，用deepwalk^[3]思想基于skip-gram訓練embedding）。這一步就是作者描述的Base Graph Embedding（BGE）。

• 為了減輕稀疏性和冷啟動問題，將邊信息合并到圖嵌入框架中。即增加商品的屬性，如品牌，價格等。然后就升級成了Graph Embedding with Side information (GES)，并且對不同的side Information加權得到Enhanced Graph Embedding with Side information (EGES)。

插一句這個歷史行為構圖其實就是session-based會話推薦了，這個下一篇文章會繼續詳細介紹。EGES模型圖如下：

看圖可知，就是把特征one-hot之后Embedding，再用注意力算一次權重H之后concat所以的特征，最后一層dense就得到了商品的特征。EGES只是把side Information帶權加入進來，即把每個item的特征變豐富了。之后還是用deepwalk^[4]思想采樣變“句子”，基于skip-gram訓練embedding，DeepWalk博主整理過了就不說了吧，最后也是一個負采樣訓練的常規操作。

SR-GNN

會話序列推薦的圖應用，發自AAAI 2019，先放鏈接：

• 論文：Session-based Recommendation with Graph Neural Networks

• 地址：https://arxiv.org/abs/1811.00855

• arxiv訪問不方便的同學后臺回復『0015』直接獲取論文
  

這篇文章和上一篇很像，只是不是用DeepWalk，而是GNN的。首先，會話推薦是指，對于一個用戶的點擊序列（即session），預測下一個要點擊的物品。即輸入所有的物品V={v1,v2,...,vm} ，在給定某個session為s=[v1,v2,...,vn]的用戶點擊序列，預測下一個要點擊的物品vn+1。

現有基于會話的推薦，方法主要集中于循環神經網絡和馬爾可夫鏈，但是存在以下缺陷：

• 當一個session中用戶的行為數量十分有限時，RNN很難產生好的用戶特征

• 馬爾可夫鏈非常依賴數據獨立性的假設

• 同時，物品之間的轉移模式在會話推薦中是十分重要，但RNN和馬爾可夫過程只對相鄰的兩個物品的單向轉移關系進行建模，而忽略了會話中其他的物品（即上下文）。

所以不如直接將會話序列建模為圖結構數據，并使用圖神經網絡捕獲復雜的項目物品item間轉換，每一個會話利用注意力機制將整體偏好與當前偏好結合進行表示。同時這種方式也就不依賴用戶的表示了，完全只基于會話內部的潛在向量獲得Embedding，然后預測下一個點擊。

Graph Neural Networks

對于構圖的表示，可以看模型圖的最左邊紅色部分，對于一連串的點擊序列，就直接利用點擊關系構圖就ok。然后抽取這個會話圖中的每個物品的Embedding向量，利用物品的Embedding向量再進行預測。

抽取序列中物品特征的GNN部分使用 Gated GNN，其計算公式為：

H和b是權重矩陣和偏置，v是點擊物品序列。 是由兩個鄰接矩陣，即入度和出度A(in)和A(out)矩陣拼接而成的(n, 2n)的矩陣，而 可以理解成矩陣的第i行(1, 2n)。如下圖所示：

代表的就是紅色的那一行，這樣做的目的是使模型能結合出度入度以學習到更復雜的圖上下文關系。至此GNN的部分實際上就結束了.....后面的四個公式就是普通的RNN了，即利用某點在圖中的特征表示再RNN。

def?get_slice(self,?i):inputs,?mask,?targets?=?self.inputs[i],?self.mask[i],?self.targets[i]items,?n_node,?A,?alias_inputs?=?[],?[],?[],?[]for?u_input?in?inputs:n_node.append(len(np.unique(u_input)))max_n_node?=?np.max(n_node)#最大的session的item數目for?u_input?in?inputs:node?=?np.unique(u_input)#unique的itemitems.append(node.tolist()?+?(max_n_node?-?len(node))?*?[0])#不夠的補0u_A?=?np.zeros((max_n_node,?max_n_node))#user的鄰接矩陣for?i?in?np.arange(len(u_input)?-?1):if?u_input[i?+?1]?==?0:?#為0說明這個session已經結束了breaku?=?np.where(node?==?u_input[i])[0][0]v?=?np.where(node?==?u_input[i?+?1])[0][0]u_A[u][v]?=?1\#最終想要的鄰接矩陣A是入度和出度A(in)和A(out)矩陣拼接而成的(n,?2n)的矩陣u_sum_in?=?np.sum(u_A,?0)?#按0維度sum，即入度總數u_sum_in[np.where(u_sum_in?==?0)]?=?1?#防止沒有某節點沒有入度而除了0u_A_in?=?np.divide(u_A,?u_sum_in)?#平均一下u_sum_out?=?np.sum(u_A,?1)?#同理按1sum，算一下出度u_sum_out[np.where(u_sum_out?==?0)]?=?1u_A_out?=?np.divide(u_A.transpose(),?u_sum_out)?#需要轉置一下u_A?=?np.concatenate([u_A_in,?u_A_out]).transpose()?#最后拼接兩者A.append(u_A)alias_inputs.append([np.where(node?==?i)[0][0]?for?i?in?u_input])return?alias_inputs,?A,?items,?mask,?targets

拿到A之后再做GNN，按上面圖中的公式就可以了。

def?GNNCell(self,?A,?hidden):\#因為A是入度和出度兩個矩陣拼接得到的，所以要分0:A.shape[1]和A.shape[1]:?2?*?A.shape[1]分別做linear變換input_in?=?torch.matmul(A[:,?:,?:A.shape[1]],?self.linear_edge_in(hidden))?+?self.b_iahinput_out?=?torch.matmul(A[:,?:,?A.shape[1]:?2?*?A.shape[1]],?self.linear_edge_out(hidden))?+?self.b_oahinputs?=?torch.cat([input_in,?input_out],?2)#然后再拼接gi?=?F.linear(inputs,?self.w_ih,?self.b_ih)#輸入門gh?=?F.linear(hidden,?self.w_hh,?self.b_hh)#記憶門i_r,?i_i,?i_n?=?gi.chunk(3,?2)#沿2維度分3塊，因為線性變換這三門是一起做的h_r,?h_i,?h_n?=?gh.chunk(3,?2)\#三個gateresetgate?=?torch.sigmoid(i_r?+?h_r)inputgate?=?torch.sigmoid(i_i?+?h_i)newgate?=?torch.tanh(i_n?+?resetgate?*?h_n)hy?=?newgate?+?inputgate?*?(hidden?-?newgate)return?hy

Attention策略

得到item的特征向量后（模型圖中的彩色條），應用一個注意力機制。有一點不同的是作者認為在當前的會話序列中，最后一個物品是非常重要的，所以單獨將它作為 ，然后計算其他的物品與最后一個物品之間的相關性，再加權就得到了 以考慮到全局信息：

接著將得到的 和 連接，輸入到一個線性層

最后使用 和每個物品的embedding進行內積計算，再softmax得到最終每個物品的點擊率，最后交叉熵得到損失函數：

def?compute_scores(self,?hidden,?mask):\#計算全局和局部，ht是最后一個item，作者認為它代表短期十分重要ht?=?hidden[torch.arange(mask.shape[0]).long(),?torch.sum(mask,?1)?-?1]??#?batch_size?x?latent_sizeq1?=?self.linear_one(ht).view(ht.shape[0],?1,?ht.shape[1])??#?batch_size?x?1?x?latent_sizeq2?=?self.linear_two(hidden)??#?batch_size?x?seq_length?x?latent_sizealpha?=?self.linear_three(torch.sigmoid(q1?+?q2))?#計算全局注意力權重\#?不算被mask的部分的sum來代表全局的特征aa?=?torch.sum(alpha?*?hidden?*?mask.view(mask.shape[0],?-1,?1).float(),?1)if?not?self.nonhybrid:?#globe+locala?=?self.linear_transform(torch.cat([a,?ht],?1))#將局部和全局s1和sg拼接b?=?self.embedding.weight[1:]??#?n_nodes?x?latent_sizescores?=?torch.matmul(a,?b.transpose(1,?0))?#再做一次特征變換return?scores

完整的代碼中文逐行筆記：https://github.com/nakaizura/Source-Code-Notebook/tree/master/SR-GNN

總結

當然只要有關系的地方就能構圖，就能抽圖特征，特別是最近Graph這么火....萬物皆可Graph。比如有人的地方就能有社交關系等等，深入挖掘屬性等等，最近也有很多論文是針對屬性中的異構信息^[5]進行挖掘，下一篇博文再整理。

參考資料

[1]

GraphSAGE: https://blog.csdn.net/qq_39388410/article/details/103903631

[2]

GraphSAGE: https://blog.csdn.net/qq_39388410/article/details/103903631

[3]

deepwalk: https://blog.csdn.net/qq_39388410/article/details/103859078

[4]

deepwalk: https://blog.csdn.net/qq_39388410/article/details/103859078

[5]

異構信息: https://blog.csdn.net/qq_39388410/article/details/104344930

往期精彩回顧適合初學者入門人工智能的路線及資料下載機器學習及深度學習筆記等資料打印機器學習在線手冊深度學習筆記專輯《統計學習方法》的代碼復現專輯 AI基礎下載機器學習的數學基礎專輯 本站知識星球“黃博的機器學習圈子”（92416895） 本站qq群704220115。 加入微信群請掃碼：

總結

以上是生活随笔為你收集整理的【图神经网络】万物皆可Graph | 当推荐系统遇上图神经网络的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。