GraphSAGE 圖神經網絡

GraphSAGE 是 2017 年提出的一種圖神經網絡算法，解決了 GCN 網絡的侷限性: GCN 訓練時需要用到整個圖的鄰接矩陣，依賴於具體的圖結構，一般只能用在直推式學習 Transductive Learning。GraphSAGE 使用多層聚合函數，每一層聚合函數會將節點及其鄰居的信息聚合在一起得到下一層的特徵向量，GraphSAGE 採用了節點的鄰域信息，不依賴於全局的圖結構。

1.前言

在之前的文章《圖神經網絡 GNN 之圖卷積網絡 (GCN)》和《GAT 圖注意力網絡 Graph Attention Network》分別介紹了 GCN 和 GAT，不熟悉的童鞋可以參考一下。

圖神經網絡的任務一般有 Transductive (直推式) 和 Inductive (歸納式)。Transductive 通常指要預測的節點在訓練時已經出現過， 例如有一個作者關係網絡，知道部分作者的類別，用整個網絡訓練 GCN，最後預測未知類別的作者。Inductive 指要預測的節點在訓練時沒有出現，例如用今天的圖結構訓練，預測明天的圖。

GCN 利用了圖的整個鄰接矩陣和圖卷積操作融合相鄰節點的信息，因此一般用於 Transductive 任務而不能用於處理 Inductive 任務。因此 2017 年 GraphSAGE 算法被提出，用於解決 GCN 的問題，《Inductive Representation Learning on Large Graphs》。

2.GraphSAGE

GraphSAGE 包含採樣和聚合 (Sample and aggregate)，首先使用節點之間連接信息，對鄰居進行採樣，然後通過多層聚合函數不斷地將相鄰節點的信息融合在一起。用融合後的信息預測節點標籤。下圖展示了 GraphSAGE 的聚合過程，採用了兩層聚合層。

GraphSAGE 聚合示意圖

上圖中的包括兩層聚合，對應的聚合函數為 aggregator1 和 aggregator2。通過 k 層聚合之後，可以得到節點最終的表示向量，GraphSAGE 的偽代碼如下：

GraphSAGE 偽代碼

偽代碼中的 h0 表示節點 v 的初始特徵向量，包含 K 層聚合操作。在第 k 次聚合生成 v 節點特徵向量時，會採用聚合函數把 v 節點的鄰居信息融合在一起。這一操作也可改成 minibatch 的，偽代碼如下：

GraphSAGE minibatch 偽代碼

上面的偽代碼中，B = BK 為要生成向量的節點集合， Bk-1 是深度為 1 的鄰域，

B0 為深度為 K 的鄰域，B0 包含的節點最多。Nk(v) 表示 v 節點在第 k 次聚合時的鄰域，節點在每一層的鄰域數量都不同，通過採樣得到。

2.1 GraphSAGE 聚合函數

GraphSAGE 提供了四種聚合節點的函數：

Mean aggregator: 對節點 v 進行聚合時，對節點 v 和鄰域的特徵向量求均值。

Mean aggregator

GCN aggregator: 採用了類似 GCN 卷積的方式進行聚合，公式和 Mean aggregator 類似：

GCN aggregator

LSTM aggregator: 作者任務 LSTM 有比較好的抽取特徵能力，因此也使用了 LSTM 進行聚合，但是因為節點之間沒有明顯的順序關係，因此會打亂之後放入 LSTM。

Pooling aggregator: 先把所有鄰居節點的特徵向量傳入一個全連接層，然後使用 max-pooling 聚合。

Pooling aggregator

2.2 GraphSAGE 訓練

GraphSAGE 可以採用無監督訓練或者有監督訓練。無監督訓練採用負採樣算法，公式如下：

無監督損失函數

公式中的 zu 是經過 GraphSAGE 聚合之後的特徵向量，節點 v 是節點 u 鄰域內的節點，而 Q 表示負採樣次數。

對於有監督訓練可以使用任務相關的目標函數，例如節點分類時採用交叉熵損失函數。

3.實驗結果

作者對比了不同算法的性能，也對比了 GraphSAGE 四種聚合方式的效果，如下表所示。

不同算法的性能

下圖 A 是訓練和測試時間的實驗結果，B 是採樣鄰域大小對性能影響的結果。

4.參考文獻

Inductive Representation Learning on Large Graphs