Graph 11 - Scaling up GNN to Large Graph

現實中的常會有非常大張的 Graph ，例如 Facebook 社群網路，如果直接將 GNN 套用在這種大圖記憶體會不夠，以往的做法會是sample M (<<N) 個 mini batch，用這個 mini batch 算 loss 用 SGD 更新，但這會有個問題，如果 sample 的 node 很多彼此之間都沒有連線，就沒辦法 msg passing，導致訓練不起來或效果很差，那如果拿 full batch，又因為太大了，GPU記憶體不夠，被迫用CPU，CPU運算效力又不如GPU。

以下會介紹三篇把 GNN 用在大圖的論文，可以分成兩個方向 :

• 在mini batch subgraph上做msg passing (1) Neighbor Sampling (NeuralIPS 2017) (2) Cluster-GCN (KDD 2019)
• 簡化GNN到feature preprocessing operation (1) Simplified GCN (ICML 2019)

GraphSAGE Neighbor Sampling (NeuralIPS 2017)

先 sample 出有 m nodes 的mini batch，然後用 k-hop neighborhood 建出 computation graph ，但這樣會很費運算資源，為了算一個 node 的 embedding 要算好幾個 node embedding 還有一種狀況是有包含到hub node (high-degree node)，這會讓要算的node embedding暴增 所以也對 neighbor 做抽取 ，每一層 hop 都做 sample(由近的開始sample)

但這可能會有以下幾個問題：

1. 會讓neighbor aggregation的variance變得更大
2. 即使已縮小規模了，subgraph仍然很大，假設有n個鄰居，每個鄰居再隨機抽m個鄰居，這樣也會有n*m個embedding
3. Random sample 是否公平 -> Random Walk with Restart

Random Walk with Restart

問題 3 的解決辦法，先用random walk去隨機走，然後記下哪個node被走到的次數比較高，次數高的分數就高，在sample鄰居時優先選分數高的。

Cluster-GCN (KDD 2019)

full-batch GNN的 好處是所有的 node embedding 都會每層一起更新，但full-batch graph很龐大，很難套用到真實世界資料。這篇論文提出了利用 layer-wise node的方法，layer-wise node 是允許可以使用之前算的embedding的node。

論文提出了Subgraph Sampling，sample 出很多 subgraph，對這些 subgraph 算 embedding，且套用 layer-wise node，為了要能這麼做，subgraph應該要保留edge connectivity structure， Left 的 subgraph 就是有保留的，這種的相對 right 好訓練。真實世界中的graph是有辦法做到這樣的，之前有提到真實的 Grpah 具有community structure。

既然有 community 在，那就先用 community detection 的方法找出來，對 community 做抽樣。以此為核心思想，Cluster-GCN 可以分為兩步驟 :

• Pre-processing : 將一張大圖分割成幾組 node group
• Mini-batch training : 隨機抽取 node group 做 msg passing 求 Loss 做訓練，這裏會把 subgraph 中的所有 node 都當成 layer-wise node

這個Cluster-GCN其實做的事就是把所有跨 community 的邊移除，雖然可以降低很多運算成本，但也會有一些問題：

1. 會少掉一些其他community來的資訊
2. 由於subgraph都是整張圖的一個community，算出來的結果只包含整張圖的一小部分
3. 因為每次用subgraph train都只能代表一小部分，所以要train很多次才會慢慢收斂

此篇論文提出的解法是在一個 mini-batch 中多 aggregate 幾個 subgraph (community)，先把整張圖分成許多更小的 node group，然後一次 sample 和 aggregate 多一點 node group，分成更小的 group 同時也為了降低 variance

跟前面的 neighbor sampling 比起來 :

• 如果是 neighbor sampling 的話，每層 sample H個，對於一個 K 層的 GNN，如果一個subgraph 有 M 個 node
  • –> 總共要算 M * H ^ K個embedding，複雜度是exponential to K
• 如果是 Clustering GCN，假設 subgraph 有 M 個 node，D_avg 為整張圖的 Degree 平均，對於一個 K layers 的 GNN
  • –> 總共要算 K * M * D_avg 如果是無向圖可能多一個(* 2)，但複雜度差不多

所以比較兩個複雜度，Cluster-GCN 做到的是把K從次方項拉下來，這運算量差很多。

Simplifying GCN (ICML 2019)

神經網路之所以厲害，其中一個原因是因為有一個 non-linear function 可以讓 model 去 fit，但這也是讓GCN變得複雜的原因之一。這篇論文的貢獻在作者發現當把 non-linear 拿掉以後，GCN效果沒有差很多，是一個划算的作法，供使用者取捨。 一般的 GCN 有加上 activation，例如ReLU 如果把 activation 拿掉，前面一坨 A 相乘就直接用Ak代替，後面一坨W直接拿WT代替，後面可以這樣代的原因是因為都是linear，沒有non-linear的轉換，因為learnable parameters都在後面的W裡，前面的AX沒有，所以說在整個訓練過程中可以視為固定的，那就可以先算好，因為是pre-computed，可以X <- AX 做 K 次

把可以事先算好的 A,X 合起來，把他們當作是一個linear transformation，可以再進一步化簡

這個 transformation 又是基於他周遭的結構來的，所以現在有了 pre-computed 部分就不用再管每次計算時都要 aggregate 鄰居，重算一次，而是在 train 之前就根據Adjacency (A)跟feature (X) 求出一個transformation。

與前面模型的比較 :

• 相對於 Neighbor Sampling 快很多，因為不用再建每個 node 的 computation graph
• 跟 Cluster GCN 比的話， Simplifying 不用像 Cluster GCN 一樣分到到這麼細，可以允許相對大一點的圖，所以Variance就比較低
• 論效果的話，大部分任務中效果都是會變差一點的!

但令人意外的是在semi-supervised node classfication任務中，Simplifying GCN效果沒什麼差， Why? Graph Homophily : 兩個相連的node，他們的label相同的機率較高 Simplifying GCN 的 pre-computed 結合 adjacency matrix 與 feature 可以表現Graph Homophily 這個特性，在 semi-supervised node classfication 中 Graph Homophily 的影響特別明顯，所以在這個任務中正確率沒有掉太多。