【圖神經(jīng)網(wǎng)絡(luò)】萬物皆可Graph | 當(dāng)推薦系統(tǒng)遇上圖神經(jīng)網(wǎng)絡(luò)

NewBeeNLP原創(chuàng)出品??

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

悠閑會 · 信息檢索

圖神經(jīng)網(wǎng)絡(luò)可以說是現(xiàn)在AI領(lǐng)域的超級寵兒。針對推薦系統(tǒng)的稀疏性問題，圖方法還真的很適合，主要原因有下：

• 推薦系統(tǒng)中存在很多的圖結(jié)構(gòu)，如二部圖，序列圖，社交關(guān)系圖，知識語義圖等
• GNN比傳統(tǒng)的隨機(jī)游走等能有更好的表現(xiàn)

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

1. 構(gòu)圖，包括如何采樣
2. 鄰居聚合，包括多少信息應(yīng)該被選擇
3. 信息更新，如何整合中心節(jié)點(diǎn)的信息
4. 最后的節(jié)點(diǎn)表示，然后再做下游的推薦預(yù)測任務(wù)。

PS！文末有我們新建立的『圖神經(jīng)網(wǎng)絡(luò)』專題討論組，名額有限，趕緊加入一起精準(zhǔn)交流吧！

GCMC

• 論文：Graph Convolutional Matrix Completion
• 地址：https://arxiv.org/pdf/1706.02263.pdf
  
  

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

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

Graph convolutional encoder

使用節(jié)點(diǎn)消息傳遞來更新模型參數(shù)，比如從item j 到 user i：

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

Bilinear decoder

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

其中 是用戶，商品的表示，Q是轉(zhuǎn)化矩陣，最后計算一個softma分?jǐn)?shù)來預(yù)測“分類”就可以了。

GCMC使用消息傳遞+自編碼的思想，實際上在大圖應(yīng)用中對每個節(jié)點(diǎn)做消息傳遞太過復(fù)雜。在實踐應(yīng)用中還是使用隨機(jī)游走+其他，接下主要介紹PinSage，EGES。

PinSage

• 論文：Graph Convolutional Neural Networks for Web-Scale Recommender Systems
• 地址：https://arxiv.org/abs/1806.01973
• arxiv訪問不方便的同學(xué)后臺回復(fù)『0013』直接獲取論文

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

目地

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

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

模型

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

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

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

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

輸入是當(dāng)下節(jié)點(diǎn)u的嵌入 ，然后得到它的鄰居節(jié)點(diǎn) ，然后主要對應(yīng)偽碼的1，2，3步：

1. 聚合鄰居?？梢钥吹剑械泥従庸?jié)點(diǎn)特征 都經(jīng)過一層dense層（由Q和q參數(shù)控制，再ReLU激活），再由聚合器或池化函數(shù) （如mean等）將所有鄰居節(jié)點(diǎn)的信息聚合得到
2. 更新當(dāng)前節(jié)點(diǎn)的特征。將原特征 和 拼接后再經(jīng)過一層dense層（W，w參數(shù)控制，再ReLU激活）
3. 最后歸一化。直接對上一步得到的特征歸一化

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

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

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

• 2~7行是鄰居采樣階段。不沿用GraphSage的隨機(jī)采樣，而是使用訪問數(shù)作為重要性采樣。即每次從當(dāng)前節(jié)點(diǎn)出發(fā)隨機(jī)走，雖然一開始是平均的，游走很多次之后，被走到的次數(shù)越多的節(jié)點(diǎn)，它相對于當(dāng)前節(jié)點(diǎn)的重要性就越高，最終選取top-t的鄰居。
• 然后后面就是Convolve操作了逐層的生成節(jié)點(diǎn)嵌入特征。特別注意就是要經(jīng)過dense之后才更新特征（偽碼15-16）。

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

訓(xùn)練技巧

• 簡單負(fù)采樣會導(dǎo)致模型分辨的粒度過粗，沒針對性，特別是數(shù)據(jù)量如此大的情況下。所以增加了“hard”負(fù)樣本，即根據(jù)當(dāng)前節(jié)點(diǎn)相關(guān)的PageRank排名，選排名在2000-5000之間的items為“hard”負(fù)樣本候選集，再進(jìn)行隨機(jī)采樣，以增加訓(xùn)練難度。

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

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

• 為了大規(guī)模計算設(shè)定的兩個MapReduce任務(wù)：

• 執(zhí)行聚合所有pins的嵌入特征。即把所有的pins映射到一個低緯度空間
• 執(zhí)行采樣鄰居特征得到board的嵌入特征，即直接通過采樣鄰接節(jié)點(diǎn)的特征來獲得。向量最終都會存在數(shù)據(jù)庫中供下游任務(wù)使用，實驗證明這種方法在不到24小時內(nèi)可以為所有30億樣本生成Embedding。

PinSage的工程啟示

• 在鄰接點(diǎn)的獲取中，采用基于Random Walk的重要性采樣
• Hard負(fù)樣本抽取
• 基于鄰接點(diǎn)權(quán)重的重要性池化操作
• 利用圖片，文字信息構(gòu)建初始特征向量
• 階段性存儲節(jié)點(diǎn)最新的Embedding，避免重復(fù)計算

PinSage和node2vec，DeepWalk的區(qū)別？

• node2vec，DeepWalk是無監(jiān)督訓(xùn)練，而PinSage是有監(jiān)督訓(xùn)練
• node2vec，DeepWalk不能用節(jié)點(diǎn)特征，PinSage可以
• node2vec，DeepWalk的參數(shù)和節(jié)點(diǎn)呈線性關(guān)系，很難用在超大型的圖上

如果只用完全hard的負(fù)采樣會怎么樣？

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

負(fù)采樣之道

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

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

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

所以Hand Negative是很重要的。一方面和用戶匹配程度最高的是正樣本，另一方面完全差異很大的是負(fù)樣本，而hard negative需要找到難度適中的，沒那么相似的樣本，所以才有剛剛PinSage也使用的2000-5000的這個范圍，并且先簡單負(fù)采樣，再逐步加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訪問不方便的同學(xué)后臺回復(fù)『0014』直接獲取論文

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

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

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

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

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

SR-GNN

會話序列推薦的圖應(yīng)用，發(fā)自AAAI 2019，先放鏈接：

• 論文：Session-based Recommendation with Graph Neural Networks
• 地址：https://arxiv.org/abs/1811.00855
• arxiv訪問不方便的同學(xué)后臺回復(fù)『0015』直接獲取論文
  

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

現(xiàn)有基于會話的推薦，方法主要集中于循環(huán)神經(jīng)網(wǎng)絡(luò)和馬爾可夫鏈，但是存在以下缺陷：

• 當(dāng)一個session中用戶的行為數(shù)量十分有限時，RNN很難產(chǎn)生好的用戶特征
• 馬爾可夫鏈非常依賴數(shù)據(jù)獨(dú)立性的假設(shè)
• 同時，物品之間的轉(zhuǎn)移模式在會話推薦中是十分重要，但RNN和馬爾可夫過程只對相鄰的兩個物品的單向轉(zhuǎn)移關(guān)系進(jìn)行建模，而忽略了會話中其他的物品（即上下文）。

所以不如直接將會話序列建模為圖結(jié)構(gòu)數(shù)據(jù)，并使用圖神經(jīng)網(wǎng)絡(luò)捕獲復(fù)雜的項目物品item間轉(zhuǎn)換，每一個會話利用注意力機(jī)制將整體偏好與當(dāng)前偏好結(jié)合進(jìn)行表示。同時這種方式也就不依賴用戶的表示了，完全只基于會話內(nèi)部的潛在向量獲得Embedding，然后預(yù)測下一個點(diǎn)擊。

Graph Neural Networks

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

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

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

代表的就是紅色的那一行，這樣做的目的是使模型能結(jié)合出度入度以學(xué)習(xí)到更復(fù)雜的圖上下文關(guān)系。至此GNN的部分實際上就結(jié)束了.....后面的四個公式就是普通的RNN了，即利用某點(diǎn)在圖中的特征表示再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數(shù)目
????for?u_input?in?inputs:
??????node?=?np.unique(u_input)#unique的item
??????items.append(node.tolist()?+?(max_n_node?-?len(node))?*?[0])#不夠的補(bǔ)0
??????u_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已經(jīng)結(jié)束了
??????????break
????????u?=?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，即入度總數(shù)
??????u_sum_in[np.where(u_sum_in?==?0)]?=?1?#防止沒有某節(jié)點(diǎn)沒有入度而除了0
??????u_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)]?=?1
??????u_A_out?=?np.divide(u_A.transpose(),?u_sum_out)?#需要轉(zhuǎn)置一下
??????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_iah
????input_out?=?torch.matmul(A[:,?:,?A.shape[1]:?2?*?A.shape[1]],?self.linear_edge_out(hidden))?+?self.b_oah
????inputs?=?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)
????\#三個gate
????resetgate?=?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的特征向量后（模型圖中的彩色條），應(yīng)用一個注意力機(jī)制。有一點(diǎn)不同的是作者認(rèn)為在當(dāng)前的會話序列中，最后一個物品是非常重要的，所以單獨(dú)將它作為 ，然后計算其他的物品與最后一個物品之間的相關(guān)性，再加權(quán)就得到了 以考慮到全局信息：

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

最后使用 和每個物品的embedding進(jìn)行內(nèi)積計算，再softmax得到最終每個物品的點(diǎn)擊率，最后交叉熵得到損失函數(shù)：

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

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

總結(jié)

當(dāng)然只要有關(guān)系的地方就能構(gòu)圖，就能抽圖特征，特別是最近Graph這么火....萬物皆可Graph。比如有人的地方就能有社交關(guān)系等等，深入挖掘?qū)傩缘鹊?，最近也有很多論文是針對屬性中的異?gòu)信息^[5]進(jìn)行挖掘，下一篇博文再整理。

參考資料