【論文翻譯】GraphSAGE：Inductive Representation Learning on Large Graphs（NIPS）

學習心得

• GCN不能泛化到訓練過程中沒有出現的節點（即屬于
• 本文先介紹GraphSAGE向前傳播過程（生成節點embedding），不同的聚合函數設定，然後介紹無監督學習和有監督學習的損失函數和參數學習——參數學習：通過前向傳播得到節點 u 的embedding，然後梯度下降（實作使用Adam優化器） 進行反向傳播優化參數
• GCN每次疊代AW 是會用到A整個圖鄰接矩陣；graphsage可以說對GCN做了進一步精簡，每次疊代隻抽樣取直接相連的鄰居；而且GraphSAGE可以通過mini-batch的形式訓練，定義合适的領域範圍，可以大大減小領接矩陣的次元。

圖源自百度飛槳

注：因無法一次性全圖送入計算資源，需要借鑒深度學習中的MiniBatch

PS：其中的SAGE即是Sample（采樣）和Aggregate（聚合）兩個單詞裡面抽取的英文字母組合（這兩個步驟也是該

用v在k-1跳的表示和v的鄰居在k跳的表示聚合得到v在k跳的表示，是以每一跳都包含了v的上一跳資訊和這一跳的鄰居資訊。v在1跳的表示是input（v自己），而通過遞歸得到的最後一跳（K跳）的表示是output z(v)。z(v)融合了從1跳到K跳所有v的表示資訊，是以可以更準确地描述v在整張圖裡的地位，進而更好地聚類v。

每次隻計算一跳鄰居特征，然後通過遞歸得獲得k跳内的鄰居資訊，極大減少計算複雜度

文章目錄

• ​​學習心得​​
• ​​零、Abstract​​
• ​​一、Introduction​​

• ​​論文的工作：​​

• ​​二、Related work​​

• ​​2.1 Factorization-based embedding approaches（節點embedding）​​
• ​​2.2 Supervised learning over graphs​​
• ​​2.3 Graph convolutional networks​​

• ​​三、Proposed method:GraphSAGE​​

• ​​3.1 Embedding generation algorithm​​

• ​​（1）Relation to the Weisfeiler-Lehman Isomorphism Test​​
• ​​（2）Neighborhood definition​​

• ​​3.2 Learning the parameters of GraphSAGE​​

• ​​（1）基于圖的無監督損失​​
• ​​（2）基于圖的有監督損失​​
• ​​（3）參數學習​​
• ​​（4）新節點embedding的生成​​

• ​​3.3 Aggregator Architectures​​

• ​​（1）均值聚合Mean aggregator​​
• ​​（2）LSTM聚合​​
• ​​（3）池化聚合Pooling aggregator​​

• ​​四、Experiments​​

• ​​4.1 Inductive learning on evolving graphs:Gitation and Reddit data​​

• ​​實驗背景​​

• ​​（1）實驗目的​​
• ​​（2）資料集和任務​​
• ​​（3）baselines​​
• ​​（4）實驗參數設定​​

• ​​資料集介紹​​

• ​​（1）資料集Citation data​​
• ​​（2）資料集Reddit data​​
• ​​（3）Generalizing across graphs: Protein-protein interactions​​

• ​​實驗結果​​

• ​​4.2 Runtime and parameter sensitivity​​
• ​​4.3 Summary comparison between the different aggregator architectures​​

• ​​五、Theoretical analysis​​
• ​​六、Conclusion​​
• ​​七、附錄​​
• ​​Reference​​

論文題目：Inductive Representation Learning on Large Graphs

題目中文：在大規模圖上的歸納表示學習

作者：Hamilton, William L. and Ying, Rex and Leskovec, Jure（NIPS 2017）

論文連結：​​​https://arxiv.org/abs/1706.02216​​​ 一作代碼：​​https://github.com/williamleif/GraphSAGE​​ 官方連結：​​http://snap.stanford.edu/graphsage/​​

零、Abstract

從内容推薦到蛋白質功能識别，大型圖中節點的低維嵌入在各種預測任務中被證明是非常有用的。然而，現有的大多數方法都要求在訓練嵌入時，需要圖中的所有節點都存在。以往的方法都是 式的，而作者提出的 （直推式） 式的 算法利用節點特征資訊(如文本屬性)有效地為未知的資料生成節點嵌入。本文的方法并非訓練每個節點的單獨嵌入，而是學習一個函數，該函數通過從節點的局部鄰域采樣和聚合特征來生成嵌入。該算法在三個 （歸納式） 式節點分類 上超過 ：能夠根據引文和 資料對演化資訊圖中未知的節點進行分類，實驗表明使用一個 （ ）多圖資料集，算法可以泛化到完全未見過的圖上。

一、Introduction

在大規模圖中，節點的低維向量embedding被證明了作為各種預測和圖分析任務的特征輸入是極為有用的。頂點embedding的基本思想是使用降維将節點圖鄰域的高維資訊提取成密集的向量嵌入。這些節點嵌入可以提供給下遊機器學習系統，并幫助完成節點分類、聚類和連結預測等任務[11, 28, 35]。

然而以往的工作一般是從單一的固定圖中抽取頂點嵌入，現實中的應用需要能夠快速地從不可見的節點或者全新的（子）圖中生成 ，這種生成式能力對高吞吐量的機器學習系統很重要，特别是當資料處于一個不斷演化的圖中，不斷加入新節點的情況下（如Reddit上的文章、Youtube上的使用者和視訊）。

生成節點嵌入的歸納算法也有助于在具有相同特征形式的圖之間進行泛化：比如我們可以在模型生物的蛋白質互相作用圖上訓練一個embedding生成器，然後利用這個生成器友善地為收集的新生物資料生成節點嵌入。

歸納式頂點嵌入問題比直推式難很多，因為要推廣到未知節點需要将新觀察的子圖與算法已經優化過的節點嵌入“對齊”（aligning）。歸納式學習架構必須學會識别一個節點鄰域的結構屬性，它揭示了圖中節點的局部角色和全局位置。

大部分現有的生成頂點嵌入的方法都是直推式的。這些方法中的大多數使用基于矩陣分解的目标直接優化每個節點的嵌入，而不會自然地推廣到看不見的資料，因為它們是對單個固定圖中的節點進行預測。這些方法可以修改為歸納式的（比如DeepWalk就可以），但是這些修改在計算上很昂貴，在做出新的預測之前需要額外的梯度下降。到目前為止，GCN僅被應用在固定圖直推式的任務上。本文将GCN擴充成歸納式無監督學習，并提出一種GCN的推廣算法（使用可訓練的聚合函數，而不是簡單的卷積）。

論文的工作：

• 提出歸納式節點embedding算法GraphSAGE，該方法與基于矩陣分解的嵌入方法不同，作者利用節點特征(例如文本屬性、節點概要資訊、節點度)來學習一個可推廣到未見節點的嵌入函數。通過在學習算法中引入節點特征，我們同時學習了每個節點的鄰域拓撲結構以及節點特征在鄰域中的分布情況。
• 雖然本文關注特征豐富的圖(例如，帶有文本屬性的引文資料，帶有功能/分子标記的生物資料)，但GraphSAGE也可以利用所有圖中存在的結構特征(例如，節點度)。是以該算法也能應用在沒有節點特征的圖上。

• 如上圖的figure1所示，GraphSAGE不是為每個節點訓練一個不同的嵌入向量，而是訓練一組聚合器函數，學習從節點的局部鄰域聚合的特征資訊。給定義一個節點，每一個聚合函數從一個不同跳數或搜尋深度上聚合資訊。在測試或者推理的時候，我們使用訓練好的系統通過應用學習聚合函數，生成整個不可見節點的嵌入。順着之前生成節點嵌入的思路，作者設計了一個無監督的損失函數，允許GraphSAGE能做任務無關的監督式訓練。同時也展示了GraphSAGE可以以一種完全監督學習的方式訓練。
• 作者在三個頂點分類的基準任務上評估了GraphSAGE模型，測試GraphSAGE在生成不可見節點的嵌入的能力。使用了兩個動态文檔圖（一個是文獻引用資料和一個是Reddit文章資料，一個是預測論文分類，一個是預測文章分類），并且還有一個多圖廣義化實驗（蛋白質之間的互動作用，是預測蛋白質功能的任務）。使用這些基準任務，我們展示了我們的方法有能力生成不可見節點的表示，并且效果遠超baseline模型。

二、Related work

GraphSAGE算法在概念上與以前的節點embedding方法、一般的圖形學習監督方法以及最近将卷積神經網絡應用于圖形結構化資料的進展有關。

2.1 Factorization-based embedding approaches（節點embedding）

使用随機遊走的統計方法和基于矩陣分解學習低維的embeddings

• Grarep: Learning graph representations with global structural information. In KDD, 2015
• node2vec: Scalable feature learning for networks. In KDD, 2016
• Deepwalk: Online learning of social - representations. In KDD, 2014
• Line: Large-scale information network embedding. In WWW, 2015
• Structural deep network embedding. In KDD, 2016

上述embedding算法直接訓練單個節點的節點embedding，本質上是transductive，而且需要大量的額外訓練（如随機梯度下降）使他們能預測新的頂點。

此外，Yang et al.的Planetoid-I算法，是一個inductive的基于embedding的半監督學習算法。然而，Planetoid-I在推斷的時候不使用任何圖結構資訊，而在訓練的時候将圖結構作為一種正則化的形式。

與上述方法不同，本文利用特征（feature）資訊來訓練可以對未見過的頂點生成embedding的模型。

2.2 Supervised learning over graphs

除了節點嵌入方法，還有大量關于圖結構資料的監督學習的文獻工作。這包括各種各樣的基于核心（graph kernels）的方法，其中圖的特征向量來自不同的圖核心(參見Weisfeiler-lehman graph kernels和其中的引用)。

一些神經網絡方法用于圖結構上的監督學習，本文的方法在概念上受到了這些算法的啟發。

• Discriminative embeddings of latent variable models for structured data. In ICML, 2016
• A new model for learning in graph domains
• Gated graph sequence neural networks. In ICLR, 2015
• The graph neural network model

然而，這些以前的方法是嘗試對整個圖(或子圖)進行分類的，但是本文的工作的重點是為單個節點生成有用的表示。

2.3 Graph convolutional networks

近幾年提出的幾種用于圖上學習的卷積神經網絡結構：

• Spectral networks and locally connected networks on graphs. In ICLR, 2014
• Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS, 2016
• Convolutional networks on graphs for learning molecular fingerprints. In NIPS,2015
• Semi-supervised classification with graph convolutional networks. In ICLR, 2016
• Learning convolutional neural networks for graphs. In ICML, 2016

上述方法中的大多數不能擴充到大型圖，或者設計用于全圖分類(或者兩者都是)。原始的GCN算法[17]是為在 設定下的半監督學習而設計的，算法要求在訓練過程中已知完整的圖拉普拉斯算子。GraphSAGE可以看作是對 的GCN架構對

三、Proposed method:GraphSAGE

3.1 Embedding generation algorithm

GraphSAGE的前向傳播算法如下，算法3.1描述了如何使用聚合函數對節點的鄰居資訊進行聚合，進而生成節點embedding。

在每次疊代(或搜尋深度)，頂點從它們的局部鄰居聚合資訊，并且随着這個過程的疊代，頂點會從越來越遠的地方獲得資訊。PinSAGE使用的前向傳播算法和GraphSAGE一樣，GraphSAGE是PinSAGE的理論基礎。

下圖算法1描述了在整個圖上生成embedding的過程，其中：

• 圖，
• 表示節點的屬性（特征向量），并且作為輸入
• 表示在層中節點的鄰居節點的embedding
• 表示在第層，節點的特征表示
• 定義為鄰居節點集合需要從中均勻采樣出固定數量的節點做聚合，即GraphSAGE中每一層的節點鄰居都是從上一層網絡采樣的，并不是所有鄰居參與，并且采樣後的鄰居的size是固定的。表示在第層，節點的所有鄰居節點的特征表示。

敲黑闆：

上圖的4-5行是核心代碼，介紹了卷積層操作：聚合與節點v相連的鄰居（采樣）k-1層的embedding，得到第k層鄰居聚合特征 ，與節點v第k-1層 embedding 拼接，并通過全連接配接層轉換，然後進入激活函數計算，得到節點v在第k層的embedding 。

第7行代碼：通過除以矢量範數來标準化節點嵌入，以防止梯度爆炸。

如上圖的栗子進行采樣，要預測 0 号節點，是以首先随機選擇 0 号節點的一階鄰居 2、4、5，然後随機選擇 2 号節點的一階鄰居 8、9，對于4、5号節點也是類似。為了将算法1擴充到mini-batch環境上，給定一組輸入頂點，先采樣采出需要的鄰居集合（直到深度K），然後運作内部循環（算法1的第三行）（附錄A包括了完整的mini-batch僞代碼）。

（1）Relation to the Weisfeiler-Lehman Isomorphism Test

（和同構測試的相關性）

GraphSAGE算法從概念上受到測試圖同構的經典算法的啟發。對于算法1，如果滿足條件：

• 設定權重矩陣為機關矩陣
• 使用一個适當的哈希函數作為一個聚合器(沒有非線性)

那麼算法1是Weisfeiler-Lehman的執行個體(WL)同構測試，也稱為“naive vertex refinement”[Weisfeiler-lehman graph kernels]。

如果對兩個子圖通過算法1的特征表示的集合 輸出是相同的，那麼ML測試就認為這兩個子圖是同構的。如果用可訓練的神經網絡聚合器替換了哈希函數，那麼GraphSAGE就是WL測試的一個連續近似。當然，文中使用GraphSAGE是為了生成有用的節點表示—而不是測試圖的同構。然而，GraphSAGE與經典的WL檢驗之間的聯系為算法設計學習節點鄰域的拓撲結構提供了理論基礎。

（2）Neighborhood definition

（采樣鄰居頂點）

出于對計算效率的考慮，對每個頂點采樣一定數量的鄰居頂點作為待聚合資訊的頂點。設需要的鄰居數量，即采樣數量為S，若頂點鄰居數少于S，則采用有放回的抽樣方法，直到采樣出S個頂點。若頂點鄰居數大于S，則采用無放回的抽樣。(即采用有放回的重采樣/負采樣方法達到S)

當然，若不考慮計算效率，完全可以對每個頂點利用其所有的鄰居頂點進行資訊聚合，這樣是資訊無損的。

文中在較大的資料集上實驗。是以，統一采樣一個固定大小的鄰域集，以保持每個batch的計算占用空間是固定的（即 graphSAGE并不是使用全部的相鄰節點，而是做了固定size的采樣）。

這樣固定size的采樣，每個節點和采樣後的鄰居的個數都相同，可以把每個節點和它們的鄰居拼成一個batch送到GPU中進行批訓練。

• 這裡需要注意的是，每一層的node的表示都是由上一層生成的，跟本層的其他節點無關，這也是一種基于層的采樣方式。
• 在圖中的“1層”，節點v聚合了“0層”的兩個鄰居的資訊，v的鄰居u也是聚合了“0層”的兩個鄰居的資訊。到了“2層”，可以看到節點v通過“1層”的節點u，擴充到了“0層”的二階鄰居節點。是以，在聚合時，聚合K次，就可以擴充到K階鄰居。
• 沒有這種采樣，單個batch的記憶體和預期運作時是不可預測的，在最壞的情況下是。相比之下，GraphSAGE的每個batch空間和時間複雜度是固定的：其中
• 實驗發現，K不必取很大的值，當K=2時，效果就很好了。至于鄰居的個數，文中提到，即兩次擴充的鄰居數之際小于500，大約每次隻需要擴充20來個鄰居時獲得較高的性能。
• 論文裡說固定長度的随機遊走其實就是随機選擇了固定數量的鄰居。

為啥這樣采樣，因為：

（1）友善批處理：在給定一批要更新的節點後，要先取出它們的K階鄰居節點集合。

（2）減低時間複雜度：隻采樣固定數量的鄰居節點而非所有的。

3.2 Learning the parameters of GraphSAGE

在定義好聚合函數之後，接下來就是對函數中的參數進行學習。文章分别介紹了無監督學習和監督學習兩種方式。

（1）基于圖的無監督損失

基于圖的損失函數傾向于使得相鄰的頂點有相似的表示，但這會使互相遠離的頂點的表示差異變大：

其中：

• 為節點
• 節點是節點
• 是sigmoid函數
• 是負采樣的機率分布（類似word2vec的負采樣），節點是從節點u的負采樣分布采樣的，Q為采樣樣本數。
• embedding之間相似度通過向量點積計算得到
• 負采樣指我們還需要一批不是v鄰居的節點作為負樣本，那麼上面式子就是指相鄰節點的embedding的相似度盡量大的情況下保證不相鄰節點的embedding的期望相似度盡可能小。

文中輸入到損失函數的表示 是從包含一個頂點局部鄰居的特征生成出來的，而不像之前的那些方法（如DeepWalk），那些方法是對每個頂點訓練一個獨一無二的embedding，然後簡單進行一個embedding lookup（查找）操作得到。

（2）基于圖的有監督損失

無監督損失函數的設定來學習節點embedding 可以供下遊多個任務使用。監督學習形式根據任務的不同直接設定目标函數即可，如最常用的節點分類任務使用交叉熵損失函數。

（3）參數學習

通過前向傳播得到節點 u 的embedding ，然後梯度下降（實作使用Adam優化器） 進行反向傳播優化參數

（4）新節點embedding的生成

是所謂的dynamic embedding核心，因為儲存下來了從節點原始的高維特征生成低維embedding的方式。現在，如果想得到一個點的embedding，隻需要輸入節點的特征向量，經過卷積（利用已經訓練好的

3.3 Aggregator Architectures

在圖中頂點的鄰居是無序的，是以希望構造出的聚合函數是對稱的（即改變輸入的順序，函數的輸出結果不變），同時具有較高的表達能力。 聚合函數的對稱性（symmetry property）確定了神經網絡模型可以被訓練且可以應用于任意順序的頂點鄰居特征集合上。

（1）均值聚合Mean aggregator

mean aggregator将目标頂點和鄰居頂點的第k − 1層向量拼接起來，然後對向量的每個次元進行求均值的操作，将得到的結果做一次非線性變換産生目标頂點的第k層表示向量。

文中用下面的式子替換算法1（3.1的圖）僞代碼中的4行和5行得到GCN的inductive變形：

原始第4、5行是：

• 均值聚合近似等價在transducttive GCN架構[Semi-supervised classification with graph convolutional networks. In ICLR, 2016]中的卷積傳播規則
• 文中稱這個修改後的基于均值的聚合器是convolutional的，這個卷積聚合器和文中的其他聚合器的重要不同在于它沒有算法1中第5行的CONCAT操作——卷積聚合器沒有将頂點前一層的表示和聚合的鄰居向量拼接起來
• 拼接操作可以看作一個是GraphSAGE算法在不同的搜尋深度或層之間的簡單的skip connection[Identity mappings in deep residual networks]的形式，它使得模型獲得了巨大的提升
• 舉個簡單例子，比如一個節點的3個鄰居的embedding分别為[1,2,3,4],[2,3,4,5],[3,4,5,6]按照每一維分别求均值就得到了聚合後的鄰居embedding為[2,3,4,5]

（2）LSTM聚合

文中也測試了一個基于LSTM的複雜的聚合器[Long short-term memory]。和均值聚合器相比，LSTMs有更強的表達能力。但是，LSTM不是symmetric的，也就是說不具有排列不變性（permutation invariant），因為它們以一個序列的方式處理輸入。是以，每次疊代時先随機打亂要聚合的鄰接點的順序，然後将鄰居序列的embedding作為LSTM的輸入。

排列不變性（permutation invariance）：指輸入的順序改變不會影響輸出的值。

（3）池化聚合Pooling aggregator

pooling聚合器，它既是對稱的，又是可訓練的。Pooling aggregator 先對目标頂點的鄰居頂點的embedding向量進行一次非線性變換，之後進行一次pooling操作(max pooling or mean pooling)，将得到結果與目标頂點的表示向量拼接，最後再經過一次非線性變換得到目标頂點的第k層表示向量。

一個element-wise max pooling操作應用在鄰居集合上來聚合資訊：

• max表示element-wise最大值操作，取每個特征的最大值
• 所有相鄰節點的向量共享權重，先經過一個非線性全連接配接層，然後做max-pooling
• 按次元應用 max/mean pooling，可以捕獲鄰居集上在某一個次元的突出的／綜合的表現。

池化聚合先讓所有鄰接點通過一個全連接配接層，然後做最大池化。

四、Experiments

4.1 Inductive learning on evolving graphs:Gitation and Reddit data

實驗背景

（1）實驗目的

• 比較GraphSAGE 相比baseline 算法的提升效果
• 比較GraphSAGE的不同聚合函數

（2）資料集和任務

Citation 論文引用網絡（節點分類）

Reddit 文章論壇 （節點分類）

PPI 蛋白質網絡 （graph分類）

（3）baselines

• Random，随機分類器
• Raw features，手工特征（非圖特征）
• deepwalk（圖拓撲特征）
• DeepWalk + features， deepwalk+手工特征

除此以外，還比較了GraphSAGE四個變種 ，并無監督生成embedding輸入給LR和端到端有監督。因為，GraphSAGE的卷積變體是一種擴充形式，是Kipf et al. 半監督GCN的inductive版本，稱這個變體為GraphSAGE-GCN。

以上baselines的分類器均采用LR。

在所有這些實驗中，預測在訓練期間看不到的節點，在PPI資料集的情況下，實驗在完全看不見的圖上進行了測試。

（4）實驗參數設定

• K=2，聚合兩跳内鄰居特征
• S1=25，S2=10： 對一跳鄰居抽樣25個，二跳鄰居抽樣10個
• RELU 激活單元
• Adam 優化器（除了DeepWalk，DeepWalk使用梯度下降效果更好）
• 文中所有的模型都是用TensorFlow實作
• 對每個節點進行步長為5的50次随機遊走
• 負采樣參考word2vec，按平滑degree進行，對每個節點采樣20個
• 保證公平性：所有版本都采用相同的minibatch疊代器、損失函數、鄰居采樣器
• 實驗測試了根據式1的損失函數訓練的GraphSAGE的各種變體，還有在分類交叉熵損失上訓練的可監督變體
• 對于Reddit和citation資料集，使用”online”的方式來訓練DeepWalk
• 在多圖情況下，不能使用DeepWalk，因為通過DeepWalk在不同不相交的圖上運作後生成的embedding空間對它們彼此說可能是arbitrarily rotated的（見文中附錄D）

資料集介紹

前兩個實驗是在演化的資訊圖中對節點進行分類，這是一個與高吞吐量生産系統特别相關的任務，該系統經常遇到不可見的資料。

（1）資料集Citation data

第一個任務是在一個大的引文資料集中預測論文主題類别。文中使用來自湯姆森路透科學核心資料庫（Thomson Reuters Web of Science Core

Collection）的無向的引文圖資料集（對應于2000-2005年六個生物相關領域的所有論文）。這個資料集的節點标簽對應于六個不同的領域的标簽。該資料集共包含302,424個節點，平均度數為9.15。文中使用2000-2004年的資料集對所有算法進行訓練，并使用2005年的資料進行測試(30%用于驗證)。對于特征，本文使用節點的度。此外，按照Arora等人的sentence embedding方法處理論文摘要（使用GenSim用word2vec實作訓練的300維單詞向量）。

（2）資料集Reddit data

第二個任務預測不同的Reddit文章（posts）屬于哪個社群。Reddit是一個大型的線上論壇，使用者可以在這裡對不同主題社群的内容進行釋出和評論。作者在Reddit上對2014年9月釋出的文章建構了一個圖形資料集。本例中的節點标簽是文章所屬的社群或“subreddit”。文中對50個大型社群進行了抽樣，并建構了一個文章-文章的圖，如果同一個使用者評論了兩個文章，就将這兩個文章連接配接起來。該資料集共包含232,965個文章，平均度為492。文中将前20天的用于訓練，其餘的用于測試(30%用于驗證)。對于特征，文中使用現成的300維GloVe CommonCrawl詞向量對于每一篇文章，将下面的内容連接配接起來：

• 文章标題的平均embedding
• 所有文章評論的平均embedding
• 該文章的得分
• 該文章的評論數量

（3）Generalizing across graphs: Protein-protein interactions

考慮跨圖進行泛化的任務，這需要了解節點的角色，而不是社群結構。文中在各種蛋白質-蛋白質互相作用(PPI)圖中對蛋白質角色進行分類，每個圖對應一個不同的人體組織。并且使用從Molecular Signatures Database中收集的位置基因集、motif基因集和免疫學signatures作為特征，gene ontology作為标簽(共121個)。圖中平均包含2373個節點，平均度為28.8。文中将所有算法在20個圖上訓練，然後在兩個測試圖上預測F1 socres(另外兩個圖用于驗證)。

實驗結果

• 可以看到GraphSAGE的性能顯著優于baseline方法
• 三個資料集上的實驗結果表明，一般是LSTM或pooling效果比較好，有監督都比無監督好（PS：每個資料集下有2個名額，Unsup是無監督，sup F1是有監督對應的F1值）
• 無監督版本的GraphSAGE-pool對引文資料和Reddit資料的連接配接（concatenation）性能分别比DeepWalk embeddings和raw features的連接配接性能好13.8%和29.1%，而有監督版本的連接配接性能分别提高了19.7%和37.2%
• 盡管LSTM是為有序資料而不是無序集設計的，但是基于LSTM的聚合器顯示了強大的性能
• 最後，可以看到無監督GraphSAGE的性能與完全監督的版本相比具有相當的競争力，這表明文中的架構可以在不進行特定于任務的微調（task-specific fine-tuning）的情況下實作強大的性能

4.2 Runtime and parameter sensitivity

運作時間和參數敏感性：

• 計算時間：GraphSAGE中LSTM訓練速度最慢，但相比DeepWalk，GraphSAGE在預測時間減少100-500倍（因為對于未知節點，DeepWalk要重新進行随機遊走以及通過SGD學習embedding）
• 鄰居采樣數量：圖B中鄰居采樣數量遞增，F1也增大，但計算時間也變大。 為了平衡F1和計算時間，将S1設為25
• 聚合K跳内資訊：在GraphSAGE， K=2 相比K=1 有10-15%的提升；但将K設定超過2，效果上隻有0-5%的提升，但是計算時間卻變大了10-100倍

4.3 Summary comparison between the different aggregator architectures

不同聚合器之間的比較：

• LSTM和pool的效果較好
• 為了更定量地了解這些趨勢，實驗中将設定六種不同的實驗，即(3個資料集)×(非監督vs.監督))
• GraphSAGE-LSTM比GraphSAGE-pool慢得多(≈2×)，這可能使基于pooling的聚合器在總體上略占優勢
• LSTM方法和pooling方法之間沒有顯著差異
• 文中使用非參數Wilcoxon Signed-Rank檢驗來量化實驗中不同聚合器之間的差異，在适用的情況下報告T-statistic和p-value。

五、Theoretical analysis

六、Conclusion

GraphSAGE能夠有效地泛化到未知節點，該方法也比很多baselines要強，但作者認為仍可以拓展和改進，例如擴充GraphSAGE以合并有向圖或多模态圖。作者認為未來工作的一個特别有趣的方向是探索非均勻鄰域采樣函數，甚至可能學習這些函數作為GraphSAGE優化的一部分。

最後小結下GraphSAGE 的優點和缺點：

優點：

（1）通過鄰居采樣的方式解決了GCN記憶體爆炸的問題，适用于大規模圖的表示學習；

（2）将 transductive 轉化為 inductive learning，而且支援增量特征；

（3）引入鄰居采樣，可有效防止訓練過拟合，增強泛化能力；GraphSAGE儲存了生成embedding的映射，可擴充性更強，對于節點分類和連結預測問題的表現也比較突出；

（4）可以根據不同領域的圖場景來自定義圖聚合方式。

缺點：

（1）鄰居采樣引入随機過程，推理階段同一節點 embedding 特征不穩定，且鄰居采樣會導緻反向傳播時梯度不穩定；

（2）鄰居采樣數目限制會導緻部分節點的重要局部資訊丢失；

七、附錄

Reference

（1）​​【Graph Neural Network】GraphSAGE: 算法原理，實作和應用，阿裡淺夢​​​

（3）​​​GraphSAGE代碼講解-知乎​​​

（4）​​網絡表示學習: 淘寶推薦系統&&GraphSAGE​​​

（5）​​魚佬GNN 系列（三）：GraphSAGE​​​

（6）​​GraphSAGE: GCN落地必讀論文​​​