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

一尔邓、回顧GCN及其問題

GCN的基本思想： 把一個節(jié)點在圖中的高緯度鄰接信息降維到一個低維的向量表示晾剖。 GCN的優(yōu)點： 可以捕捉graph的全局信息，從而很好地表示node的特征梯嗽。 GCN的缺點： Transductive learning的方式齿尽，需要把所有節(jié)點都參與訓練才能得到node embedding，無法快速得到新node的embedding灯节。

得到新節(jié)點的表示的難處： 要想得到新節(jié)點的表示循头，需要讓新的graph或者subgraph去和已經(jīng)優(yōu)化好的node embedding去“對齊”。然而每個節(jié)點的表示都是受到其他節(jié)點的影響显晶，因此添加一個節(jié)點贷岸，意味著許許多多與之相關的節(jié)點的表示都應該調整。這會帶來極大的計算開銷磷雇，即使增加幾個節(jié)點偿警，也要完全重新訓練所有的節(jié)點，這可太費勁了唯笙。

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

既然新增的節(jié)點螟蒸，一定會改變原有節(jié)點的表示，那么我們干嘛一定要得到每個節(jié)點的一個固定的表示呢崩掘？我們何不直接學習一種節(jié)點的表示方法七嫌。這樣不管graph怎么改變，都可以很容易地得到新的表示苞慢。

二诵原、GraphSAGE是怎么做的

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

基本思想： 去學習一個節(jié)點的信息是怎么通過其鄰居節(jié)點的特征聚合而來的。 學習到了這樣的“聚合函數(shù)”辑畦，而我們本身就已知各個節(jié)點的特征和鄰居關系吗蚌，我們就可以很方便地得到一個新節(jié)點的表示了。

GCN等transductive的方法纯出，學到的是每個節(jié)點的一個唯一確定的embedding蚯妇； 而GraphSAGE方法學到的node embedding，是根據(jù)node的鄰居關系的變化而變化的暂筝，也就是說箩言，即使是舊的node，如果建立了一些新的link焕襟，那么其對應的embedding也會變化分扎，而且也很方便地學到。

1. Embedding generation

即GraphSAGE的前向傳播算法胧洒。

上面的算法的意思是：

假設我們要聚合K次畏吓，則需要有K個聚合函數(shù)（aggregator），可以認為是N層卫漫。 每一次聚合菲饼，都是把上一層得到的各個node的特征聚合一次，在假設該node自己在上一層的特征列赎，得到該層的特征宏悦。如此反復聚合K次，得到該node最后的特征包吝。 最下面一層的node特征就是輸入的node features饼煞。

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

我來畫一個圖說明：（雖然樸素诗越，但是明明白白）

這里需要注意的是砖瞧，每一層的node的表示都是由上一層生成的，跟本層的其他節(jié)點無關嚷狞。

2.GraphSAGE的參數(shù)學習

在上面的過程中块促，我們需要學習各個聚合函數(shù)的參數(shù)，因此需要設計一個損失函數(shù)床未。 損失函數(shù)是設計是根據(jù)目標任務來的竭翠，可以是無監(jiān)督的，也可以是有監(jiān)督的薇搁。

對于無監(jiān)督學習斋扰，我們設計的損失函數(shù)應該讓臨近的節(jié)點的擁有相似的表示，反之應該表示大不相同啃洋。所以損失函數(shù)是這樣的：

也沒什么好解釋的传货。
對于有監(jiān)督學習，可以直接使用cross-entropy裂允。

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

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

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

• GCN aggregator：
  這個跟mean aggregator十分類似绝编，但有細微的不同僻澎，公式如下：

  
  

  把這個公式，去替換前面給的Algorithm1中的第4,5行十饥。
  自己體會一下哪里不同窟勃。想不明白的留言。實際上逗堵，這個幾乎就是GCN中的聚合方式秉氧，想一想為啥。

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

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

這就是GraphSAGE的主要內容了蚤假，其實思路還是十分簡潔的栏饮，理解起來也比GCN容易多了。

鄰居的定義：

前面一直都沒討論一個點磷仰，那就是如何選擇一個節(jié)點的鄰居以及多遠的鄰居袍嬉。

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

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

隨著迭代民逼，可以聚合越來越遠距離的信息呢泵殴？

后來我想了想，發(fā)現(xiàn)確實是這樣的拼苍。雖然在聚合時僅僅聚合了一個節(jié)點鄰居的信息笑诅，但該節(jié)點的鄰居，也聚合了其鄰居的信息疮鲫，這樣吆你，在下一次聚合時，該節(jié)點就會接收到其鄰居的鄰居的信息俊犯，也就是聚合到了二階鄰居的信息了妇多。
還是拿出我的看家本領——用圖說話：

我的天，這個圖簡直畫的太好了吧燕侠。

圖中（為了圖的簡潔者祖，這里假設只隨機聚合兩個鄰居）可以看出，層與層之間绢彤，確實都是一階鄰居的信息在聚合七问。在圖中的“1層”，節(jié)點v聚合了“0層”的兩個鄰居的信息茫舶，v的鄰居u也是聚合了“0層”的兩個鄰居的信息械巡。到了“2層”，可以看到節(jié)點v通過“1層”的節(jié)點u，擴展到了“0層”的二階鄰居節(jié)點讥耗。因此有勾，在聚合時，聚合K次葛账，就可以擴展到K階鄰居柠衅。

在GraphSAGE的實踐中，作者發(fā)現(xiàn)籍琳，K不必取很大的值，當K=2時贷祈，效果就灰常好了趋急，也就是只用擴展到2階鄰居即可。至于鄰居的個數(shù)势誊，文中提到S1×S2<=500呜达，即兩次擴展的鄰居數(shù)之際小于500，大約每次只需要擴展20來個鄰居即可粟耻。這也是合情合理查近，例如在現(xiàn)實生活中，對你影響最大就是親朋好友挤忙，這些屬于一階鄰居霜威，然后可能你偶爾從他們口中聽說一些他們的同事、朋友的一些故事册烈，這些會對你產(chǎn)生一定的影響戈泼，這些人就屬于二階鄰居。但是到了三階赏僧，可能基本對你不會產(chǎn)生什么影響了大猛，例如你聽你同學說他同學聽說她同學的什么事跡，是不是很繞口淀零，繞口就對了挽绩，因為你基本不會聽到這樣的故事，你所接觸到的驾中、聽到的唉堪、看到的，基本都在“二階”的范圍之內哀卫。

三巨坊、效果：

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

思考 & GCN的反芻：

在看完GraphSAGE之后趾撵，我又回頭把GCN思考了一遍。從直觀上去看，我一開始覺得GraphSAGE和GCN截然不同占调，后來發(fā)現(xiàn)只是論文作者的介紹的角度不同暂题，實際上兩者的本質上沒有很大差別【可海或者說薪者，懂了GraphSAGE的原理之后，再去看GCN剿涮，會發(fā)GCN沒那么難以理解了言津。

來人啊，GCN公式搬上來：

額取试，悬槽，，這個是丑版本的公式瞬浓，還是上美版本的吧：

這個公式的內部弊琴，畫成矩陣相乘的形式是這樣的：

其中，A是n×n維位迂，H是n×m維访雪，W則是m×u維。n就是節(jié)點個數(shù)掂林，m則是節(jié)點特征的維度臣缀，u就是神經(jīng)網(wǎng)絡層的單元數(shù)。

我們先看看A乘以H是個啥意思：

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

所以赖阻，都是一個詞——Aggregate！Aggregate就完事兒了踱蠢。

這也是為什么GraphSAGE的作者說火欧，他們的mean-aggregator跟GCN十分類似棋电。在GCN中，是直接把鄰居的特征進行求和苇侵，而實際不是A跟H相乘赶盔，而是A帽子，A帽子是歸一化的A榆浓，所以實際上我畫的圖中的鄰居關系向量不應該是0,1構成的序列于未，而是歸一化之后的結果，所以跟H的向量相乘之后陡鹃，相當于是“求平均”烘浦。GraphSAGE進一步拓展了“聚合”的方法，提出了LSTM萍鲸、Pooling等聚合方式谎倔，不是簡單地求平均，而是更加復雜的組合方式猿推，所以有一些效果的提升也是在情理之內的。

至于說為什么GCN是transductive捌肴，為啥要把所有節(jié)點放在一起訓練蹬叭？
我感覺不一定要把所有節(jié)點放在一起訓練，一個個節(jié)點放進去訓練也是可以的状知。無非是你如果想得到所有節(jié)點的embedding秽五，那么GCN可以讓你一口氣把整個graph丟進去，直接得到embedding饥悴，還可以直接進行節(jié)點分類坦喘、邊的預測等任務。

其實西设，通過GraphSAGE得到的節(jié)點的embedding瓣铣，在增加了新的節(jié)點之后，舊的節(jié)點也需要更新贷揽，這個是無法避免的棠笑，因為，新增加點意味著環(huán)境變了禽绪，那之前的節(jié)點的表示自然也應該有所調整蓖救。只不過，對于老節(jié)點印屁，可能新增一個節(jié)點對其影響微乎其微循捺，所以可以暫且使用原來的embedding，但如果新增了很多雄人，極大地改變的原有的graph結構从橘，那么就只能全部更新一次了。從這個角度去想的話，似乎GraphSAGE也不是什么“神仙”方法洋满，只不過生成新節(jié)點embedding的過程晶乔，實施起來相比于GCN更加靈活方便了。