眾所周知，2017年ICLR出產(chǎn)的GCN現(xiàn)在是多么地?zé)衢T，仿佛自己就是圖神經(jīng)網(wǎng)絡(luò)的名片。然而，在GCN的風(fēng)頭中，很多人忽略了GCN本身的巨大局限——Transductive Learning——沒法快速表示新節(jié)點(diǎn)，這限制了它在生產(chǎn)環(huán)境中應(yīng)用。同年NIPS來了一篇使用Inductive Learning的GraphSAGE，解決了這個(gè)問題。今天，讓我們來一起琢磨琢磨這個(gè)GraphSAGE是個(gè)什么玩意兒。

一、回顧GCN及其問題

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。

得到新節(jié)點(diǎn)的表示的難處： 要想得到新節(jié)點(diǎn)的表示，需要讓新的graph或者subgraph去和已經(jīng)優(yōu)化好的node embedding去“對(duì)齊”。然而每個(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)，這可太費(fèi)勁了。

因此我們需要換一種思路：

既然新增的節(jié)點(diǎn)，一定會(huì)改變原有節(jié)點(diǎn)的表示，那么我們干嘛一定要得到每個(gè)節(jié)點(diǎn)的一個(gè)固定的表示呢？我們何不直接學(xué)習(xí)一種節(jié)點(diǎn)的表示方法。這樣不管graph怎么改變，都可以很容易地得到新的表示。

二、GraphSAGE是怎么做的

針對(duì)這種問題，GraphSAGE模型提出了一種算法框架，可以很方便地得到新node的表示。

基本思想： 去學(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é)到。

1. Embedding generation

即GraphSAGE的前向傳播算法。

上面的算法的意思是：

假設(shè)我們要聚合K次，則需要有K個(gè)聚合函數(shù)（aggregator），可以認(rèn)為是N層。 每一次聚合，都是把上一層得到的各個(gè)node的特征聚合一次，在假設(shè)該node自己在上一層的特征，得到該層的特征。如此反復(fù)聚合K次，得到該node最后的特征。 最下面一層的node特征就是輸入的node features。

用作者的圖來表示就是這樣的：（雖然酷炫，但有點(diǎn)迷糊）

我來畫一個(gè)圖說明：（雖然樸素，但是明明白白）

這里需要注意的是，每一層的node的表示都是由上一層生成的，跟本層的其他節(jié)點(diǎn)無關(guān)。

2.GraphSAGE的參數(shù)學(xué)習(xí)

在上面的過程中，我們需要學(xué)習(xí)各個(gè)聚合函數(shù)的參數(shù)，因此需要設(shè)計(jì)一個(gè)損失函數(shù)。 損失函數(shù)是設(shè)計(jì)是根據(jù)目標(biāo)任務(wù)來的，可以是無監(jiān)督的，也可以是有監(jiān)督的。

對(duì)于無監(jiān)督學(xué)習(xí)，我們設(shè)計(jì)的損失函數(shù)應(yīng)該讓臨近的節(jié)點(diǎn)的擁有相似的表示，反之應(yīng)該表示大不相同。所以損失函數(shù)是這樣的：

也沒什么好解釋的。
對(duì)于有監(jiān)督學(xué)習(xí)，可以直接使用cross-entropy。

3. 聚合函數(shù)的選擇

這里作者提供了三種方式：

• Mean aggregator ：
  直接取鄰居節(jié)點(diǎn)的平均，公式過于直白故不展示。

• GCN aggregator：
  這個(gè)跟mean aggregator十分類似，但有細(xì)微的不同，公式如下：

  
  

  把這個(gè)公式，去替換前面給的Algorithm1中的第4,5行。
  自己體會(huì)一下哪里不同。想不明白的留言。實(shí)際上，這個(gè)幾乎就是GCN中的聚合方式，想一想為啥。

• LSTM aggregator： 使用LSTM來encode鄰居的特征。 這里忽略掉鄰居之間的順序，即隨機(jī)打亂，輸入到LSTM中。這里突然冒出來一個(gè)LSTM我也是蠻驚訝，作者的想法是LSTM的表示能力比較強(qiáng)。但是這里既然都沒有序列信息，那我不知道LSTM的優(yōu)勢在何處。

• Pooling aggregator： 把各個(gè)鄰居節(jié)點(diǎn)單獨(dú)經(jīng)過一個(gè)MLP得到一個(gè)向量，最后把所有鄰居的向量做一個(gè)element-wise的max-pooling或者什么其他的pooling。

這就是GraphSAGE的主要內(nèi)容了，其實(shí)思路還是十分簡潔的，理解起來也比GCN容易多了。

鄰居的定義：

前面一直都沒討論一個(gè)點(diǎn)，那就是如何選擇一個(gè)節(jié)點(diǎn)的鄰居以及多遠(yuǎn)的鄰居。

這里作者的做法是設(shè)置一個(gè)定值，每次選擇鄰居的時(shí)候就是從周圍的直接鄰居（一階鄰居）中均勻地采樣固定個(gè)數(shù)個(gè)鄰居。

那我就有一個(gè)疑問了？每次都只是從其一階鄰居聚合信息，為何作者說：

隨著迭代，可以聚合越來越遠(yuǎn)距離的信息呢？

后來我想了想，發(fā)現(xiàn)確實(shí)是這樣的。雖然在聚合時(shí)僅僅聚合了一個(gè)節(jié)點(diǎn)鄰居的信息，但該節(jié)點(diǎn)的鄰居，也聚合了其鄰居的信息，這樣，在下一次聚合時(shí)，該節(jié)點(diǎn)就會(huì)接收到其鄰居的鄰居的信息，也就是聚合到了二階鄰居的信息了。
還是拿出我的看家本領(lǐng)——用圖說話：

我的天，這個(gè)圖簡直畫的太好了吧。

圖中（為了圖的簡潔，這里假設(shè)只隨機(jī)聚合兩個(gè)鄰居）可以看出，層與層之間，確實(shí)都是一階鄰居的信息在聚合。在圖中的“1層”，節(jié)點(diǎn)v聚合了“0層”的兩個(gè)鄰居的信息，v的鄰居u也是聚合了“0層”的兩個(gè)鄰居的信息。到了“2層”，可以看到節(jié)點(diǎn)v通過“1層”的節(jié)點(diǎn)u，擴(kuò)展到了“0層”的二階鄰居節(jié)點(diǎn)。因此，在聚合時(shí)，聚合K次，就可以擴(kuò)展到K階鄰居。

在GraphSAGE的實(shí)踐中，作者發(fā)現(xiàn)，K不必取很大的值，當(dāng)K=2時(shí)，效果就灰常好了，也就是只用擴(kuò)展到2階鄰居即可。至于鄰居的個(gè)數(shù)，文中提到S1×S2<=500，即兩次擴(kuò)展的鄰居數(shù)之際小于500，大約每次只需要擴(kuò)展20來個(gè)鄰居即可。這也是合情合理，例如在現(xiàn)實(shí)生活中，對(duì)你影響最大就是親朋好友，這些屬于一階鄰居，然后可能你偶爾從他們口中聽說一些他們的同事、朋友的一些故事，這些會(huì)對(duì)你產(chǎn)生一定的影響，這些人就屬于二階鄰居。但是到了三階，可能基本對(duì)你不會(huì)產(chǎn)生什么影響了，例如你聽你同學(xué)說他同學(xué)聽說她同學(xué)的什么事跡，是不是很繞口，繞口就對(duì)了，因?yàn)槟慊静粫?huì)聽到這樣的故事，你所接觸到的、聽到的、看到的，基本都在“二階”的范圍之內(nèi)。

三、效果：

這個(gè)部分是最沒意思的，畢竟誰發(fā)paper不是說自己的模型最牛逼？

思考 & GCN的反芻：

在看完GraphSAGE之后，我又回頭把GCN思考了一遍。從直觀上去看，我一開始覺得GraphSAGE和GCN截然不同，后來發(fā)現(xiàn)只是論文作者的介紹的角度不同，實(shí)際上兩者的本質(zhì)上沒有很大差別?；蛘哒f，懂了GraphSAGE的原理之后，再去看GCN，會(huì)發(fā)GCN沒那么難以理解了。

來人啊，GCN公式搬上來：

額，，，這個(gè)是丑版本的公式，還是上美版本的吧：

這個(gè)公式的內(nèi)部，畫成矩陣相乘的形式是這樣的：

其中，A是n×n維，H是n×m維，W則是m×u維。n就是節(jié)點(diǎn)個(gè)數(shù)，m則是節(jié)點(diǎn)特征的維度，u就是神經(jīng)網(wǎng)絡(luò)層的單元數(shù)。

我們先看看A乘以H是個(gè)啥意思：

A帽子矩陣的第i行和H矩陣的第j列對(duì)應(yīng)元素相乘在求和就得到Q矩陣的(i,j)個(gè)元素。
這都是最基本的線性代數(shù)了，但我們不妨再仔細(xì)看看我圖中高亮的那幾個(gè)向量的內(nèi)部：

所以，都是一個(gè)詞——Aggregate！Aggregate就完事兒了。

這也是為什么GraphSAGE的作者說，他們的mean-aggregator跟GCN十分類似。在GCN中，是直接把鄰居的特征進(jìn)行求和，而實(shí)際不是A跟H相乘，而是A帽子，A帽子是歸一化的A，所以實(shí)際上我畫的圖中的鄰居關(guān)系向量不應(yīng)該是0,1構(gòu)成的序列，而是歸一化之后的結(jié)果，所以跟H的向量相乘之后，相當(dāng)于是“求平均”。GraphSAGE進(jìn)一步拓展了“聚合”的方法，提出了LSTM、Pooling等聚合方式，不是簡單地求平均，而是更加復(fù)雜的組合方式，所以有一些效果的提升也是在情理之內(nèi)的。

至于說為什么GCN是transductive，為啥要把所有節(jié)點(diǎn)放在一起訓(xùn)練？
我感覺不一定要把所有節(jié)點(diǎn)放在一起訓(xùn)練，一個(gè)個(gè)節(jié)點(diǎn)放進(jìn)去訓(xùn)練也是可以的。無非是你如果想得到所有節(jié)點(diǎn)的embedding，那么GCN可以讓你一口氣把整個(gè)graph丟進(jìn)去，直接得到embedding，還可以直接進(jìn)行節(jié)點(diǎn)分類、邊的預(yù)測等任務(wù)。

其實(shí)，通過GraphSAGE得到的節(jié)點(diǎn)的embedding，在增加了新的節(jié)點(diǎn)之后，舊的節(jié)點(diǎn)也需要更新，這個(gè)是無法避免的，因?yàn)?，新增加點(diǎn)意味著環(huán)境變了，那之前的節(jié)點(diǎn)的表示自然也應(yīng)該有所調(diào)整。只不過，對(duì)于老節(jié)點(diǎn)，可能新增一個(gè)節(jié)點(diǎn)對(duì)其影響微乎其微，所以可以暫且使用原來的embedding，但如果新增了很多，極大地改變的原有的graph結(jié)構(gòu)，那么就只能全部更新一次了。從這個(gè)角度去想的話，似乎GraphSAGE也不是什么“神仙”方法，只不過生成新節(jié)點(diǎn)embedding的過程，實(shí)施起來相比于GCN更加靈活方便了。