論文：

論文題目：《Inductive Representation Learning on Large Graphs》

論文地址：https://arxiv.org/pdf/1706.02216.pdf

利用圖信息的推薦我們?cè)谥暗奈恼吕锩嬉步榻B了幾篇，SRGNN技肩，node2vec且轨，deepwalk等等，這些論文都是利用了圖結(jié)構(gòu)的鄰域關(guān)系來對(duì)node進(jìn)行建模學(xué)習(xí)虚婿。而今天我們要介紹的這篇論文是用鄰域聚合(aggregate)的方式來學(xué)習(xí)的旋奢，跟item2vec，node2vec不同的是然痊，i2v直接生成了node的embedding信息至朗，而在Graphsage中，embedding信息是動(dòng)態(tài)聚合生成的剧浸，下面一起來看看Graphage是怎么生成embedding的吧锹引。

假設(shè)讀這篇文章的你已經(jīng)知道了 deepwalk，node2vec等生成item embedding的方法唆香，那么接下來你將更容易的理解為什么GraphSAGE的方法較這些方法來得好嫌变。

一 、背景

本文是斯坦福大學(xué)發(fā)表在2017年nips的一篇文章躬它，不同于deepwalk等文章通過圖結(jié)構(gòu)信息腾啥，在訓(xùn)練之前需要所有節(jié)點(diǎn)的embedding信息，這種方法對(duì)于那些沒有見過的node節(jié)點(diǎn)是沒辦法處理的冯吓，概括的說倘待，這些方法都是transductive的。此文提出的方法叫GraphSAGE组贺，針對(duì)的問題是之前的網(wǎng)絡(luò)表示學(xué)習(xí)的transductive凸舵，從而提出了一個(gè)inductive的GraphSAGE算法。GraphSAGE同時(shí)利用節(jié)點(diǎn)特征信息和結(jié)構(gòu)信息得到Graph Embedding的映射失尖，相比之前的方法啊奄，之前都是保存了映射后的結(jié)果贿条，而GraphSAGE保存了生成embedding的映射，可擴(kuò)展性更強(qiáng)增热，對(duì)于節(jié)點(diǎn)分類和鏈接預(yù)測(cè)問題的表現(xiàn)也比較突出。

GraphSAGE是為了學(xué)習(xí)一種節(jié)點(diǎn)表示方法胧辽，即如何通過從一個(gè)頂點(diǎn)的局部鄰居采樣并聚合頂點(diǎn)特征峻仇，而不是為每個(gè)頂點(diǎn)訓(xùn)練單獨(dú)的embedding。這一點(diǎn)就注定了它跟其他方法不同的地方邑商，對(duì)于新的節(jié)點(diǎn)信息摄咆，transdutive結(jié)構(gòu)不能自然地泛化到未見過的頂點(diǎn)，而GraphSAGE算法可以動(dòng)態(tài)的聚合出新節(jié)點(diǎn)的embeddinng信息人断。

回顧一下GCN的問題：

在大型圖中吭从，節(jié)點(diǎn)的低維向量embedding被證明了作為各種各樣的預(yù)測(cè)和圖分析任務(wù)的特征輸入是非常有用的。頂點(diǎn)embedding最基本的基本思想是使用降維技術(shù)從高維信息中提煉一個(gè)頂點(diǎn)的鄰居信息恶迈，存到低維向量中涩金。這些頂點(diǎn)嵌入之后會(huì)作為后續(xù)的機(jī)器學(xué)習(xí)系統(tǒng)的輸入，解決像頂點(diǎn)分類暇仲、聚類步做、鏈接預(yù)測(cè)這樣的問題。

GCN雖然能提取圖中頂點(diǎn)的embedding奈附，但是存在一些問題：

GCN的基本思想： 把一個(gè)節(jié)點(diǎn)在圖中的高緯度鄰接信息降維到一個(gè)低維的向量表示全度。

GCN的優(yōu)點(diǎn)： 可以捕捉graph的全局信息，從而很好地表示node的特征斥滤。

GCN的缺點(diǎn)： Transductive learning的方式将鸵，需要把所有節(jié)點(diǎn)都參與訓(xùn)練才能得到node embedding，無法快速得到新node的embedding佑颇。

回想一下deepwalk這些文章顶掉，他們學(xué)習(xí)的是固定的圖結(jié)構(gòu)，當(dāng)有新的節(jié)點(diǎn)或者新的子圖加入到整個(gè)圖中漩符，需要讓新的graph或者subgraph去和已經(jīng)優(yōu)化好的node embedding去“對(duì)齊（align）”一喘。然而每個(gè)節(jié)點(diǎn)的表示都是受到其他節(jié)點(diǎn)的影響，因此添加一個(gè)節(jié)點(diǎn)嗜暴，意味著許許多多與之相關(guān)的節(jié)點(diǎn)的表示都應(yīng)該調(diào)整凸克。這會(huì)帶來極大的計(jì)算開銷，即使增加幾個(gè)節(jié)點(diǎn)闷沥，也要完全重新訓(xùn)練所有的節(jié)點(diǎn)萎战。

為了能夠動(dòng)態(tài)的生成node節(jié)點(diǎn)的embedding信息，GraphSAGE直接學(xué)習(xí)來一種節(jié)點(diǎn)的表示方法舆逃，去學(xué)習(xí)一個(gè)節(jié)點(diǎn)的信息是怎么通過其鄰居節(jié)點(diǎn)的特征聚合而來的蚂维。 學(xué)習(xí)到了這樣的“聚合函數(shù)”戳粒，而我們本身就已知各個(gè)節(jié)點(diǎn)的特征和鄰居關(guān)系，我們就可以很方便地得到一個(gè)新節(jié)點(diǎn)的表示了虫啥。

GCN等transductive的方法蔚约，學(xué)到的是每個(gè)節(jié)點(diǎn)的一個(gè)唯一確定的embedding； 而GraphSAGE方法學(xué)到的node embedding涂籽，是根據(jù)node的鄰居關(guān)系的變化而變化的苹祟，也就是說，即使是舊的node评雌，如果建立了一些新的link树枫，那么其對(duì)應(yīng)的embedding也會(huì)變化，而且也很方便地學(xué)到景东。

二 砂轻、Proposed method: GraphSAGE

前面已經(jīng)說到了GraphSAGE學(xué)習(xí)的不是node的embedding，而是生成node embedding的映射斤吐，這個(gè)方法跟其他方法不同：

觀察上面三張圖搔涝，第一張圖表示的是k=2 hop的時(shí)候的領(lǐng)域關(guān)系圖。第二張圖表示的是通過對(duì)鄰居節(jié)點(diǎn)進(jìn)行聚合的方式來生成node embedding的過程和措，其中綠色的聚合表示的是第二跳鄰居的聚合体谒，藍(lán)色的聚合表示第一跳鄰居的聚合。第三張圖表示的是臼婆，測(cè)試或是推斷的時(shí)候抒痒，使用訓(xùn)練好的系統(tǒng)，通過學(xué)習(xí)到的聚合函數(shù)來對(duì)完全未見過的頂點(diǎn)生成embedding颁褂。

可以看到GraphSAGE的方法分為三個(gè)步驟：

1.對(duì)圖中每個(gè)頂點(diǎn)鄰居頂點(diǎn)進(jìn)行采樣故响，因?yàn)槊總€(gè)節(jié)點(diǎn)的度是不一致的，為了計(jì)算高效颁独， 為每個(gè)節(jié)點(diǎn)采樣固定數(shù)量的鄰居

2.根據(jù)聚合函數(shù)聚合鄰居頂點(diǎn)蘊(yùn)含的信息

3.得到圖中各頂點(diǎn)的向量表示供下游任務(wù)使用

2.1 Embedding generation

這一部分是本篇論文的重頭戲彩届，也是本文的核心部分。

首先誓酒，我們先明確一下算法1里面各個(gè)符號(hào)的定義樟蠕。

1. G=(V,E)表示一個(gè)圖

2.?K是網(wǎng)絡(luò)的層數(shù)，也代表著每個(gè)頂點(diǎn)能夠聚合的鄰接點(diǎn)的跳數(shù)靠柑，因?yàn)槊吭黾右粚诱纾梢跃酆细h(yuǎn)的一層鄰居的信息

3. ?,?v∈V表示節(jié)點(diǎn)v的特征向量，并且作為輸入

4.?{?,?u∈N(v)}表示在k?1層中節(jié)點(diǎn)v的鄰居節(jié)點(diǎn)u的embedding

5.??表示在第k層歼冰，節(jié)點(diǎn)v的所有鄰居節(jié)點(diǎn)的特征表示

6.??,?v∈V表示在第k層靡狞，節(jié)點(diǎn)v的特征表示

7.?N(v)定義為從集合{u ∈ v : ( u , V ) ∈ E}中的固定size的均勻取出，即GraphSAGE中每一層的節(jié)點(diǎn)鄰居都是是從上一層網(wǎng)絡(luò)采樣的隔嫡，并不是所有鄰居參與甸怕，并且采樣的后的鄰居的size是固定的

介紹完了這些節(jié)點(diǎn)的定義后甘穿，我們就可以來講解下算法一的工作流程了，這里我用簡(jiǎn)單的幾句話來講解一下吧梢杭，我相信看完算法一和符號(hào)定義的你已經(jīng)知道這個(gè)算法的流程來温兼。

首先，對(duì)于所有的頂點(diǎn)v武契，我們都賦予一個(gè)初始的特征表示妨托，這里的特征表示可以是節(jié)點(diǎn)的各種特征的組合信息。

然后對(duì)于每一層吝羞，聚合生成這一層的每一個(gè)v的embedding，聚合的方式如下：

最后内颗，我們通過k次聚合钧排，得到了所有v的embedding表示。

看著是挺簡(jiǎn)單的均澳，接下來我們講一下幾個(gè)細(xì)節(jié)恨溜。

2.2 鄰居節(jié)點(diǎn)的采樣

前文已經(jīng)說到了，對(duì)于節(jié)點(diǎn)v的鄰居節(jié)點(diǎn)找前，我們采用的是固定數(shù)量的采樣方式來聚合生成v的embedding表示的糟袁，設(shè)需要的鄰居數(shù)量，即采樣數(shù)量為S躺盛，若頂點(diǎn)鄰居數(shù)少于S,則采用有放回的抽樣方法项戴，直到采樣出S個(gè)頂點(diǎn)。若頂點(diǎn)鄰居數(shù)大于S槽惫，則采用無放回的抽樣周叮。(即采用有放回的重采樣/負(fù)采樣方法達(dá)到S)

文中在較大的數(shù)據(jù)集上實(shí)驗(yàn)。因此界斜，統(tǒng)一采樣一個(gè)固定大小的鄰域集仿耽，以保持每個(gè)batch的計(jì)算占用空間是固定的（即 graphSAGE并不是使用全部的相鄰節(jié)點(diǎn)，而是做了固定size的采樣）各薇。

這樣固定size的采樣项贺，每個(gè)節(jié)點(diǎn)和采樣后的鄰居的個(gè)數(shù)都相同，可以把每個(gè)節(jié)點(diǎn)和它們的鄰居拼成一個(gè)batch送到GPU中進(jìn)行批訓(xùn)練峭判。

2.3 聚合函數(shù)

這是第二章的核心部分开缎，主要是講解聚合函數(shù)是如何工作的。在圖中頂點(diǎn)的鄰居是無序的林螃，所以希望構(gòu)造出的聚合函數(shù)是對(duì)稱的（即也就是對(duì)它輸入的各種排列啥箭，函數(shù)的輸出結(jié)果不變），同時(shí)具有較高的表達(dá)能力治宣。?聚合函數(shù)的對(duì)稱性（symmetry property）確保了神經(jīng)網(wǎng)絡(luò)模型可以被訓(xùn)練且可以應(yīng)用于任意順序的頂點(diǎn)鄰居特征集合上急侥。

2.3.1 Mean aggregate

mean aggregator將目標(biāo)頂點(diǎn)和鄰居頂點(diǎn)的第k?1層向量拼接（不是concate）起來砌滞，然后對(duì)向量的每個(gè)維度進(jìn)行求均值的操作，將得到的結(jié)果做一次非線性變換產(chǎn)生目標(biāo)頂點(diǎn)的第k層表示向量坏怪。

這里表示的不是concate的意思贝润，而是將v在第k-1層的embedding表示和v在k-1成的所有鄰居節(jié)點(diǎn)的embedding進(jìn)行avg pooling的意思。

跟算法一4铝宵，5不同的地方在于打掘，mean aggrate操作沒有conncate操作，而是用上面這個(gè)式子直接替換了算法一中的4鹏秋，5這兩步尊蚁。

2.3.2 Lstm aggregate

文中也測(cè)試了一個(gè)基于LSTM的復(fù)雜的聚合器[Long short-term memory]。和均值聚合器相比侣夷，LSTM有更強(qiáng)的表達(dá)能力横朋。但是，LSTM不是symmetric的百拓，也就是說不具有排列不變性（permutation invariant）琴锭，因?yàn)樗鼈円砸粋€(gè)序列的方式處理輸入。因此衙传，需要先對(duì)鄰居節(jié)點(diǎn)隨機(jī)順序决帖，然后將鄰居序列的embedding作為L(zhǎng)STM的輸入。

2.3.3 Pooling（Max） aggregate

pooling聚合器蓖捶，它既是對(duì)稱的地回，又是可訓(xùn)練的。Pooling aggregator 先對(duì)目標(biāo)頂點(diǎn)的鄰居頂點(diǎn)的embedding向量進(jìn)行一次非線性變換俊鱼，之后進(jìn)行一次pooling操作(max pooling or mean pooling)落君，將得到結(jié)果與目標(biāo)頂點(diǎn)的表示向量拼接，最后再經(jīng)過一次非線性變換得到目標(biāo)頂點(diǎn)的第k層表示向量亭引。

一個(gè)element-wise max pooling操作應(yīng)用在鄰居集合上來聚合信息：

聚合完v的第k-1層的鄰居節(jié)點(diǎn)后绎速，還要將這部分的向量跟v在第k-1層的embedding表示concate后送到非線性變換函數(shù)后得到最終的embedding表示。

介紹完這三個(gè)聚合函數(shù)后焙蚓，聰明的你已經(jīng)想到了一個(gè)可以水論文的方式了纹冤，你想到的是：v的鄰居節(jié)點(diǎn)對(duì)于聚合函數(shù)的作用是不同的，每一個(gè)鄰居都應(yīng)該對(duì)應(yīng)一個(gè)weight购公，沒錯(cuò)萌京，就是往這里面加attention，可惜宏浩，這篇文章是2017年的文章知残，而attention也確實(shí)在后面的改進(jìn)中被廣泛的加入。

2.4 目標(biāo)函數(shù)

其中u比庄，v是可以通過隨機(jī)游走方式確定的兩個(gè)鄰居求妹，也就是說u可以通過游走達(dá)到v乏盐，這個(gè)相當(dāng)于是pos樣本，在看看另一邊制恍，其中Q是負(fù)采樣的樣本數(shù)量父能，Pn(v)是負(fù)采樣的概率分布，vn是負(fù)樣本净神，E是期望何吝。與DeepWalk不同的是，這里的頂點(diǎn)表示向量是通過聚合頂點(diǎn)的鄰接點(diǎn)特征產(chǎn)生的鹃唯，而不是簡(jiǎn)單的進(jìn)行一個(gè)embedding lookup操作得到爱榕。

從直觀上來看這個(gè)函數(shù)，很容易就能理解：讓鄰居節(jié)點(diǎn)更相近坡慌，讓非鄰居節(jié)點(diǎn)更相遠(yuǎn)黔酥，這么訓(xùn)練后，可以用內(nèi)積表示節(jié)點(diǎn)之間的相似度八匠。

負(fù)采樣參考word2vec，按平滑degree進(jìn)行趴酣，對(duì)每個(gè)節(jié)點(diǎn)采樣20個(gè)梨树。

三、實(shí)驗(yàn)

實(shí)驗(yàn)結(jié)果1：分類準(zhǔn)確率（micro-averaged F1 scores）

如圖一所示：

1. 三個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明岖寞，一般是LSTM或pooling效果比較好抡四，有監(jiān)督都比無監(jiān)督好

2.?盡管LSTM是為有序數(shù)據(jù)而不是無序集設(shè)計(jì)的，但是基于LSTM的聚合器顯示了強(qiáng)大的性能

實(shí)驗(yàn)結(jié)果2：運(yùn)行時(shí)間和參數(shù)敏感性

如圖2所示:

1.計(jì)算時(shí)間：GraphSAGE中LSTM訓(xùn)練速度最慢仗谆，但相比DeepWalk指巡，GraphSAGE在預(yù)測(cè)時(shí)間減少100-500倍（因?yàn)閷?duì)于未知節(jié)點(diǎn)，DeepWalk要重新進(jìn)行隨機(jī)游走以及通過SGD學(xué)習(xí)embedding）

2.鄰居采樣數(shù)量：圖B中鄰居采樣數(shù)量遞增隶垮，F(xiàn)1也增大藻雪，但計(jì)算時(shí)間也變大。 為了平衡F1和計(jì)算時(shí)間狸吞，將S1設(shè)為25

3.聚合K跳內(nèi)信息：在GraphSAGE勉耀， K=2 相比K=1 有10-15%的提升；但將K設(shè)置超過2蹋偏，效果上只有0-5%的提升便斥，但是計(jì)算時(shí)間卻變大了10-100倍

實(shí)驗(yàn)結(jié)果3：不同聚合器之間的比較

1.LSTM和pool的效果較好

2.為了更定量地了解這些趨勢(shì)，實(shí)驗(yàn)中將設(shè)置六種不同的實(shí)驗(yàn)威始，即(3個(gè)數(shù)據(jù)集)×(非監(jiān)督vs.監(jiān)督))

3.GraphSAGE-LSTM比GraphSAGE-pool慢得多(≈2×)枢纠，這可能使基于pooling的聚合器在總體上略占優(yōu)勢(shì)

4.LSTM方法和pooling方法之間沒有顯著差異

5.文中使用非參數(shù)Wilcoxon Signed-Rank檢驗(yàn)來量化實(shí)驗(yàn)中不同聚合器之間的差異，在適用的情況下報(bào)告T-statistic和p-value黎棠。