引言

本文為GNN教程的第三篇文章 【GraghSAGE算法】，在GCN的博文中我們重點討論了圖神經網絡的逐層傳播公式是如何推導的，然而，GCN的訓練方式需要將鄰接矩陣和特征矩陣一起放到內存或者顯存里，在大規模圖數據上是不可取的。 其次，GCN在訓練時需要知道整個圖的結構信息(包括待預測的節點), 這在現實某些任務中也不能實現(比如用今天訓練的圖模型預測明天的數據，那么明天的節點是拿不到的)。GraphSAGE的出現就是為了解決這樣的問題，這篇博文中我們將會詳細得討論它。

一、Inductive learning v.s. Transductive learning

首先我們介紹一下什么是inductive learning。與其他類型的數據不同，圖數據中的每一個節點可以通過邊的關系利用其他節點的信息，這樣就產生了一個問題，如果訓練集上的節點通過邊關聯到了預測集或者驗證集的節點，那么在訓練的時候能否用它們的信息呢? 如果訓練時用到了測試集或驗證集樣本的信息(或者說，測試集和驗證集在訓練的時候是可見的), 我們把這種學習方式叫做transductive learning, 反之，稱為inductive learning。

顯然，我們所處理的大多數機器學習問題都是inductive learning, 因為我們刻意的將樣本集分為訓練/驗證/測試，并且訓練的時候只用訓練樣本。然而，在GCN中，訓練節點收集鄰居信息的時候，用到了測試或者驗證樣本，所以它是transductive的。

二、概述

GraphSAGE是一個inductive框架，在具體實現中，訓練時它僅僅保留訓練樣本到訓練樣本的邊。inductive learning 的優點是可以利用已知節點的信息為未知節點生成Embedding. GraphSAGE 取自 Graph SAmple and aggreGatE, SAmple指如何對鄰居個數進行采樣。aggreGatE指拿到鄰居的embedding之后如何匯聚這些embedding以更新自己的embedding信息。下圖展示了GraphSAGE學習的一個過程：

對鄰居采樣

采樣后的鄰居embedding傳到節點上來，并使用一個聚合函數聚合這些鄰居信息以更新節點的embedding

根據更新后的embedding預測節點的標簽

三、算法細節

3.1 節點 Embedding 生成(即：前向傳播)算法

這一節討論的是如何給圖中的節點生成(或者說更新)embedding, 假設我們已經完成了GraphSAGE的訓練，因此模型所有的參數(parameters)都已知了。具體來說，這些參數包括個聚合器(見下圖算法第4行)中的參數, 這些聚合器被用來將鄰居embedding信息聚合到節點上，以及一系列的權重矩陣(下圖算法第5行), 這些權值矩陣被用作在模型層與層之間傳播embedding的時候做非線性變換。

下面的算法描述了我們是怎么做前向傳播的：

算法的主要部分為：

(line 1)初始化每個節點embedding為節點的特征向量

(line 3)對于每一個節點

(line 4)拿到它采樣后的鄰居的embedding并將其聚合，這里表示對鄰居采樣

(line 5)根據聚合后的鄰居embedding()和自身embedding()通過一個非線性變換()更新自身embedding.

算法里的這個比較難理解，下面單獨來說他，之前提到過，它既是聚合器的數量，也是權重矩陣的數量，還是網絡的層數，這是因為每一層網絡中聚合器和權重矩陣是共享的。

網絡的層數可以理解為需要最大訪問到的鄰居的跳數(hops)，比如在figure 1中，紅色節點的更新拿到了它一、二跳鄰居的信息，那么網絡層數就是2。

為了更新紅色節點，首先在第一層()我們會將藍色節點的信息聚合到紅色節點上，將綠色節點的信息聚合到藍色節點上。在第二層()紅色節點的embedding被再次更新，不過這次用的是更新后的藍色節點embedding，這樣就保證了紅色節點更新后的embedding包括藍色和綠色節點的信息。

3.2 采樣 (SAmple) 算法

GraphSAGE采用了定長抽樣的方法，具體來說，定義需要的鄰居個數, 然后采用有放回的重采樣/負采樣方法達到,。保證每個節點(采樣后的)鄰居個數一致是為了把多個節點以及他們的鄰居拼成Tensor送到GPU中進行批訓練。

3.3 聚合器 (Aggregator) 架構

GraphSAGE 提供了多種聚合器，實驗中效果最好的平均聚合器(mean aggregator)，平均聚合器的思慮很簡單，每個維度取對鄰居embedding相應維度的均值，這個和GCN的做法基本一致(GCN實際上用的是求和)：

舉個簡單例子，比如一個節點的3個鄰居的embedding分別為 ，按照每一維分別求均值就得到了聚合后的鄰居embedding為.

論文中還闡述了另外兩種aggregator:LSTM aggregator和Pooling aggregator, 有興趣的可以去論文中看下。

3.4 參數學習

到此為止，整個模型的架構就講完了，那么GraphSAGE是如何學習聚合器的參數以及權重變量的呢? 在有監督的情況下，可以使用每個節點的預測label和真實label的交叉熵作為損失函數。在無監督的情況下，可以假設相鄰的節點的輸出embeding應當盡可能相近，因此可以設計出如下的損失函數：

其中是節點的輸出embedding,是節點的鄰居(這里鄰居是廣義的，比如說如果和在一個定長的隨機游走中可達，那么我們也認為他們相鄰)，是負采樣分布，是負采樣的樣本數量，所謂負采樣指我們還需要一批不是鄰居的節點作為負樣本，那么上面這個式子的意思是相鄰節點的embedding的相似度盡量大的情況下保證不相鄰節點的embedding的期望相似度盡可能小。

四、后話

GraphSAGE采用了采樣的機制，克服了GCN訓練時內存和顯存上的限制，使得圖模型可以應用到大規模的圖結構數據中，是目前幾乎所有工業上圖模型的雛形。然而，每個節點這么多鄰居，采樣能否考慮到鄰居的相對重要性呢，或者我們在聚合計算中能否考慮到鄰居的相對重要性? 這個問題在我們的下一篇博文Graph Attentioin Networks中做了詳細的討論。

責任編輯：lq