? ? ? ?本文作者來自斯坦福,都是大牛呀赏表。這是一篇難得的GCN大型網(wǎng)絡(luò)應(yīng)用類的文章检诗。再提一句,斯坦福在網(wǎng)絡(luò)計(jì)算瓢剿,社交網(wǎng)絡(luò)逢慌,graph embedding領(lǐng)域很厲害,有自己的主頁间狂,公開了很多數(shù)據(jù)集合攻泼。不過很遺憾,這篇文章既沒有公開數(shù)據(jù)前标,也沒有公開代碼坠韩。猜想可能是由于和Pinterest公司合作,涉及商業(yè)數(shù)據(jù)以及數(shù)據(jù)量高達(dá)十幾T的原因炼列。說實(shí)話只搁,這篇文章的實(shí)驗(yàn)部分沒有看懂,涉及到MapReduce并行計(jì)算多GPU單機(jī)訓(xùn)練俭尖,本人沒有接觸過這些技術(shù)氢惋,所以這部分自覺略過了,不過稽犁,也給自己提了個(gè)醒焰望,圖挖掘領(lǐng)域,工業(yè)界免不了的大圖已亥,分布式是逃不了的熊赖,未來要找時(shí)間學(xué)習(xí)這部分知識(shí)。如果有讀者對(duì)這篇文章的實(shí)驗(yàn)部分有一些理解和見地虑椎,歡迎聯(lián)系完善本文震鹉。
? ? ? ?言歸正傳俱笛,這篇文章的應(yīng)用背景是推薦系統(tǒng),用戶提交需求传趾,例如如何做一道菜迎膜,系統(tǒng)反饋推薦的菜單結(jié)果類似這樣的場(chǎng)景。構(gòu)建用戶-商品二分圖浆兰,千億用戶磕仅,十億商品,借鑒GCN簸呈,提出PinSage算法榕订。文章說的是pin and board,我就把它權(quán)且理解成商品和用戶了蝶棋。模型訓(xùn)練時(shí)在3億節(jié)點(diǎn)卸亮,18億邊的網(wǎng)絡(luò)上進(jìn)行的,這個(gè)網(wǎng)絡(luò)還是挺稠密的玩裙。本文將主要介紹該論文的模型算法部分兼贸。
? ? ? ?論文中模型設(shè)計(jì)的目的是為了得到節(jié)點(diǎn)的embedding表示,優(yōu)化目標(biāo)是正例內(nèi)積最大化和負(fù)例內(nèi)積小于給定閾值吃溅。這里說明一下溶诞,正例指的是查詢項(xiàng)(query item)和推薦相關(guān)項(xiàng)(related item)embedding之間的距離;負(fù)例則指的是正例指的是查詢項(xiàng)(query item)和推薦不相關(guān)項(xiàng)(unrelated item)embedding之間的距離决侈。因此螺垢,關(guān)鍵是如何求得embedding。
? ? ? ?常見的graph embedding的方法赖歌,有node2vec,embedding等枉圃。這兩種都是無監(jiān)督方法,且僅根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)庐冯,不考慮節(jié)點(diǎn)特征孽亲,因此,也正是這兩種方式的普適性就導(dǎo)致對(duì)于特定的分類預(yù)測(cè)問題展父,效果表現(xiàn)并不好返劲。還有就是最近很火的GCN,作為一種端到端的半監(jiān)督學(xué)習(xí)方式栖茉,GCN在分類問題中篮绿,不僅考慮了節(jié)點(diǎn)特征,并且將特征和網(wǎng)絡(luò)結(jié)構(gòu)整合吕漂,通過將每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)信息作用到自身亲配,相當(dāng)于一個(gè)消息傳播的過程,同時(shí)也存在著難以調(diào)參、很難收斂的問題弃榨,而且傳統(tǒng)的GCN在全圖上做操作菩收,對(duì)于大圖而言梨睁,有很大的計(jì)算限制鲸睛。門控圖序列神經(jīng)網(wǎng)絡(luò)也具有計(jì)算限制,一般在節(jié)點(diǎn)數(shù)小于1萬的網(wǎng)絡(luò)中起作用坡贺,圖遞歸神經(jīng)網(wǎng)絡(luò)筆者目前不是很了解官辈,學(xué)習(xí)后會(huì)另寫一篇分享。因此遍坟,本文提出了局部圖卷積模型拳亿。
? ? ? ?如圖所示,下半部分的結(jié)構(gòu)分別是以A,B,C,D,E,F為根節(jié)點(diǎn)的分支愿伴,每個(gè)分支包含各根節(jié)點(diǎn)的兩度鄰居節(jié)點(diǎn)肺魁。我們可以卡出 ,對(duì)于不同的節(jié)點(diǎn)隔节,其鄰居節(jié)點(diǎn)個(gè)數(shù)不同鹅经,這就遇到在上一篇文章我們提到的問題,節(jié)點(diǎn)的鄰居節(jié)點(diǎn)個(gè)數(shù)不同以及鄰居節(jié)點(diǎn)的無序性怎诫。這篇文章是這樣解決的:
- 鄰居數(shù)目不一致:通過將每個(gè)鄰居節(jié)點(diǎn)的特征在對(duì)應(yīng)維度上求平均或者做最大池化瘾晃,最終帶節(jié)點(diǎn)的特征表示還是原來的n維;
- 鄰居無序問題轉(zhuǎn)化為鄰居節(jié)點(diǎn)重要性問題:我們可以看到在根節(jié)點(diǎn)的子樹中幻妓,有些節(jié)點(diǎn)多次出現(xiàn)蹦误,因此根據(jù)當(dāng)前節(jié)點(diǎn)(根節(jié)點(diǎn))的子節(jié)點(diǎn)訪問次數(shù)來確定鄰居節(jié)點(diǎn)的重要程度。
? ? ? ?論文提出的PinSage算法的核心是局部卷積操作(如下圖)肉津。
算法
該算法中要解決的問題是:
? ? ? ?該網(wǎng)絡(luò)是考慮鄰居節(jié)點(diǎn)重要性强胰,所以有一個(gè)鄰居權(quán)重向量在算法一第一行,
是通過卷積過程中對(duì)鄰居節(jié)點(diǎn)訪問次數(shù)來決定的(上文第2點(diǎn))妹沙。通過一個(gè)全連接網(wǎng)絡(luò)以及Relu激活函數(shù)提取鄰居特征偶洋,然后通過
函數(shù)將鄰居特征與權(quán)值矩陣
作用得到
,作者說
具體是通過聚合池化起作用初烘,但是沒有詳述涡真。這一步可以理解成對(duì)u節(jié)點(diǎn)的鄰居節(jié)點(diǎn)進(jìn)行采樣,通過全連接操作按照鄰居重要性得到一個(gè)聚合的鄰居向量表示
肾筐;算法第二行將該向量和節(jié)點(diǎn)當(dāng)前表示
拼接哆料,通過另一個(gè)全連接層得到
;第三行做了一個(gè)規(guī)范化操作吗铐,因?yàn)殡S著不斷將鄰居節(jié)點(diǎn)信息聚合到自身節(jié)點(diǎn)上东亦,注意在這個(gè)迭代過程中,每個(gè)自身節(jié)點(diǎn)也是其他節(jié)點(diǎn)的鄰居節(jié)點(diǎn),因此為了保證訓(xùn)練過程中節(jié)點(diǎn)向量中每一維量級(jí)的穩(wěn)定典阵,加入了基于
范式的規(guī)范化的操作奋渔。
? ? ? ?最后總結(jié)一下,這篇論文的主要工作是提出一種隨機(jī)游走加局部圖卷積的用于生成節(jié)點(diǎn)embedding表示的模型壮啊。
作者原創(chuàng)嫉鲸,歡迎交流,如需轉(zhuǎn)載請(qǐng)先聯(lián)系作者歹啼。