今天我們來聊一聊在大規(guī)模圖神經(jīng)網(wǎng)絡上必用的GNN加速算法。GNN在圖結(jié)構(gòu)的任務上取得了很好的結(jié)果，但由于需要將圖加載到內(nèi)存中，且每層的卷積操作都會遍歷全圖，對于大規(guī)模的圖，需要的內(nèi)存和時間的開銷都是不可接受的。

現(xiàn)有一些用于加速GNN的算法，基本思路是使用mini-batch來計算，用min-batch的梯度估計full-batch的梯度，通過多次迭代達到基本一致的效果。

根據(jù)使用的方法不同，大致分為以下三類：

• Neighbor sampling

• Layer-wise sampling

• Subgraph sampling

1.Neighbor sampling

1.1 GraphSage

論文標題：Inductive Representation Learning on Large Graphs

論文來源：NIPS2017

論文方向：圖表示學習

論文鏈接：https://arxiv.org/abs/1706.02216

GraphSAGE 是 2017 年提出的一種圖神經(jīng)網(wǎng)絡算法，解決了 GCN 網(wǎng)絡的局限性: GCN 訓練時需要用到整個圖的鄰接矩陣，依賴于具體的圖結(jié)構(gòu)，一般只能用在直推式學習 Transductive Learning。GraphSAGE 使用多層聚合函數(shù)，每一層聚合函數(shù)會將節(jié)點及其鄰居的信息聚合在一起得到下一層的特征向量，GraphSAGE 采用了節(jié)點的鄰域信息，不依賴于全局的圖結(jié)構(gòu)。

GraphSAGE 的運行流程如上圖所示，可以分為三個步驟：

1、對圖中每個頂點鄰居頂點進行采樣；

2、根據(jù)聚合函數(shù)聚合鄰居頂點蘊含的信息；

3、得到圖中各頂點的向量表示供下游任務使用；

出于對計算效率的考慮，對每個頂點采樣一定數(shù)量的鄰居頂點作為待聚合信息的頂點。設采樣數(shù)量為k，若頂點鄰居數(shù)少于k,則采用有放回的抽樣方法，直到采樣出k個頂點。若頂點鄰居數(shù)大于k，則采用無放回的抽樣。

即為每個結(jié)點均勻地抽樣固定數(shù)量的鄰居結(jié)點，使用Batch去訓練。

復雜度正比于卷積層數(shù)  的指數(shù)。

1.2 ScalableGCN

阿里媽媽的Euler中使用的加速算法，主要思想是用空間換時間。對于  階GCN模型，開辟存儲空間:  ，將mini-batch SGD中各頂點最新的前階embedding存儲起來，前向Aggregate的時候直接查詢緩存。

同時也開辟存儲空間  ，來存儲  ,根據(jù)鏈式法則來獲得參數(shù)梯度從而更新  。

我們在兩個開源的數(shù)據(jù)集Reddit和PPI上驗證了我們的工作。由于GraphSAGE的簡單和通用性，我們選擇其為baseline。并且為了對齊與其論文中的實驗結(jié)果，我們在共享了GraphSAGE和ScalableGCN代碼中的大多數(shù)模塊，并利用Tensorflow中的Variable存儲和，使用累加作為算子。

我們使用均勻分布來初始化，并將初始化為0。對于每階的卷積操作，我們采樣10個鄰接頂點。所有的實驗均使用512的batch size訓練20個epoch。在評估階段，我們統(tǒng)一維持GraphSAGE的方法進行Inference。以下是選擇Mean作為AGG函數(shù)的micro-F1 score：

PPI:

Reddit:

可以看到ScalableGCN訓練出來模型與GraphSAGE的訓練結(jié)果相差很小，同時可以取得多層卷積模型的收益。

在時間上，以下是8 core的機器上Reddit數(shù)據(jù)集（23萬頂點）每個mini-batch所需的訓練時間：

注意到ScalableGCN的訓練時間相對于卷積模型層數(shù)來說是線性的。

總結(jié)：

GCN是目前業(yè)界標準的網(wǎng)絡圖中特征抽取以及表示學習的方法，未來在搜索、廣告、推薦等場景中有著廣泛的應用。多階的GCN的支持提供了在圖中挖掘多階關系的能力。ScalableGCN提出了一種快速訓練多階GCN的方法，可以有效的縮短多階GCN的訓練時間，并且適用于大規(guī)模的稀疏圖。本方法與對采樣進行裁剪和共享的方法也并不沖突，可以同時在訓練中使用

1.3 VR-GCN

論文標題：Stochastic Training of Graph Convolutional Networks with Variance Reduction

論文來源：ICML2018

論文方向：圖卷積網(wǎng)絡

論文鏈接：https://arxiv.org/abs/1706.02216

主要思路：利用結(jié)點歷史表示  來作為控制變量（control variate）來減小方差，從而減小batch training中的采樣鄰居的數(shù)量。

使用蒙特卡方法來洛近似  ，而  上的平均計算是可接受的（不用遞歸）。

因此其矩陣表示為：

該算法具有理論保障，可以獲得0偏差和0方差的結(jié)果，且無論每層鄰居結(jié)點的抽樣個數(shù)  是多少，都不影響 GCN收斂到局部最優(yōu)。（理論細節(jié)請看原文，較為復雜，不展開）

因此每個結(jié)點僅僅采樣兩個鄰居，極大提升模型訓練效率的同時，也能保證獲得良好的模型效果。

2.1 FastGCN

論文標題：FastGCN: fast learning with graph convolutional networks via importance sampling

論文來源：ICLR2018

論文方向：圖卷積網(wǎng)絡

論文鏈接：https://arxiv.org/abs/1801.10247

我們已知，GCN的形式為：

從積分的角度看待圖卷積，假設圖是無限大圖的子集，所有結(jié)點為獨立同分布的結(jié)點，滿足  

則可以應用蒙特卡洛法，對每一層進行采樣  個結(jié)點，  來近似積分，以前層的結(jié)點作為共享鄰居集合：

此外為了減少估計方差（Variance Reduction），采用重要性采樣(Importance samling)，結(jié)點根據(jù)以下概率分布采樣：

2.2 ASGCN

論文標題：Adaptive Sampling Towards Fast Graph Representation Learning

論文來源：NIPS2018

論文方向：圖卷積網(wǎng)絡

論文鏈接：https://arxiv.org/abs/1809.05343

對FastGCN的最后一個公式，其最優(yōu)的解（最小化從  抽樣出的結(jié)點的方差，  ）為：

其中  ，而  則是上一層結(jié)點從鄰居聚集而來的隱層表示。在FastGCN中，則有  

為了防止遞歸困境，為importance sampling學習一個獨立的決定其重要性的函數(shù)(Adaptive sampling)，基于結(jié)點的特征  來計算：

因此最終的抽樣結(jié)點的分布為:

3.1 cluster-GCN

論文標題：Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks

論文來源：KDD2019

論文方向：圖卷積網(wǎng)絡

論文鏈接：https://arxiv.org/abs/1905.07953

主要思路：為了限制鄰居數(shù)量的擴張和提高表示的效用，將圖分割成多個cluster（限制子圖的規(guī)模），在cluster上進行結(jié)點的batch training。

使用METIS進行圖分割，使得cluster內(nèi)的邊多，cluster之間的邊少。

具體來說，對于圖  分割成   個部分，  ，  由第  個分割中的結(jié)點構(gòu)成，   僅由  中結(jié)點之間的邊構(gòu)成，故有  個子圖：

因此，鄰居矩陣可以分為  的子矩陣：

同理也可以對結(jié)點特征矩陣  和  進行分割，  。

Loss可以分解為：

兩種訓練方式：

1.隨機挑選一個cluster進行訓練（coarse clustering）

2.隨機挑選 k 個cluster，然后連接他們再進行訓練（stochastic multiple clustering）

3.2 GraphSAINT

論文標題：GraphSAINT: Graph Sampling Based Inductive Learning Method

論文來源：ICLR2020

論文方向：圖卷積網(wǎng)絡

論文鏈接：https://arxiv.org/abs/1907.04931

主要思路：先采樣子圖，之后在子圖上做完全連接的GCN。

通過在子圖的GCN上添加歸一化系數(shù)（通過預處理計算）來使得估計量無偏，Aggregation 的normalization為：

Loss的normalization為：

從而：

一個好的Samper應該使得：

1、相互具有較大影響的結(jié)點應該被sample到同一個子圖；

2、每條邊多有不可忽略的抽樣概率。

設計Sampler減少評估的方差：

Random node sampler：

Random edge sampler：

Random walk based sampler：