Graph 5 - Basic GNN and GCN

GNN是整個Graph最重要的部分，前面講了很多Graph的基本概念，就是為了學GNN，全名是Graph Neural Network，簡單來說就是直接套用在Graph結構的Neural Network，有些資料本身就是Graph的結構(如下圖)，直接將feature排成陣列形式丟進NN就錯失了原本的結構訊息，這種資料直接在Graph結構上用Neural Network效果會更好。

但直接用GNN也會遇到一些問題 :

1. 因為現實世界中的Graph非常巨大，會需要大量參數 O(|V|)
2. 拓展性可能不夠，隨便新增一個node就會讓整張圖的Adjency Matrix改變
3. 根據從哪一個node開始看，這個順序對結果影響也很大

GCN (Graph Convolutional Network)

為了解決前面提到的問題，有人提出使用CNN的概念，利用sliding window，一次只看Graph的一部分，於是GCN誕生了 :
在圖的觀點上，sliding window應該如何實現，我們可以使用hop的概念(類似幾等親屬關係)，就是多少關係以內的node才能影響一個node的結果，對於這個sliding window，又有一些問題要被解決，例如neighbor太多會需要sample或是有個seper node (現實中的超級現充，人脈超廣，算他進去會延伸出算不完的鄰居)，這些之後會介紹。

Raw input graph and Computational graph

這裡要先提兩個專有名詞 – Raw input graph 跟 Computational graph，Raw input graph是我們原始的Graph，但不一定適合運算，會有上面提到的問題，需要經過處理才是真正丟進GNN的Graph，這個實際丟進GNN跑的Graph就是Computational graph，例如一些之後會介紹的issue :

• feature太少或是沒有 -> train不起來 -> 需要增加特徵才train得起來
• 圖太稀疏 -> 傳遞msg沒有效率 ->add virtual nodes/edges
• 圖太密集 -> 傳遞msg花費太大 -> pass msg 時 sample neighbors
• 圖太大 -> 無法在電腦運算 -> sample subgraphs to compute embeddings

GNN Eample

下圖是一個簡單的GNN實例，左邊是Raw input graph，如果要預測node A，假設將hop設為2，也就是兩層GNN，那會從node A的所有鄰居延伸出去找到BCD，然後再從這些鄰居找到他們各自的鄰居來會合，例如B的鄰居有AC，這裡也可以發現node A自己的特徵也可以透過鄰居間接影響到自己，所以我們還是有把要預測的node本身的特徵給考慮進去。同一層的所有方格部分是共享weight的，會一起train，後面會講到。

Graph中的所有node都可以根據hop得到各自的Computational graph，有label的nodes用這些Computational graph算出的結果與label做比較，就可以算出loss進而往回更新每層GNN Layer的參數。

順便一提，有時會提到Layer 0就是node feature本身，也是可以在這加一些轉換。

GNN Layer

以下是一個最基本的GNN Layer，他代表的是上圖中的方塊部分，h_u(l)代表node u在經過l層聚合所得到的embedding結果，我們由近往遠看，一開始是0層，所以所有nodes直接拿自己的feature x來用，接著是第一層，把目標node v所有neighbors經過0層的embedding加起來乘上W，再除以Neighbors總數做Normalize (取平均是最簡單的方法之一) ，然後加上B乘以目標node在前一層得到的embedding，這裡的embedding是前面幾層的累積結果，跟前面提到neighbor本身會把node v考慮進去的意義不同，然後經過一個non-linear的轉換，重複以上步驟直到指定層數，最終可以得到一個embedding，用z_v表示，這裡的Ｗ跟B是trainable的。

以上是用公式好表達的方式，實際運算會把藍色區域用矩陣來做，會比較方便。D是degree Matrix，他是一個對角矩陣，記錄每個node的degree(鄰居數)，A是Adjency Matrix，紀錄node之間是否有edge，可以用以下關係表示原本的聚合neighbor再normalize的部分 :

GNN Layer Framework

講完了embedding和aggregation，在實作GNN layer時會把它分成Message跟Aggregation兩個部分 :

Message function

Message表示一個node在收集完neighbor的資訊後傳給下一個node的訊息，他跟前面提到的embedding很像，但意義有點差別，embedding是某個node藉由computational Graph一層一層更新最終得到的結果，Message只代表這個node要傳給下個node的訊息，m_u(l)是node u在第 l 層所傳出的msg，每個node都會有msg，如果是linear function，可以用以下公式表示。

Aggregation function

Aggregation function是把node收到的所有msg聚合起來，簡單的有Sum,Mean,Max等，把鄰居的都聚合後再concate自己的特徵作為這個node v的hv(l)傳遞出去(前面範例用加的也可以，那是一種Aggregation方式，不過Aggregation function這個詞被提出後似乎都是用concate，我猜可能因為後來GraphSAGE出現有關，之後會介紹)，要加non-linear才好model一些任務，例如ReLU，可以加在Msg function或是Aggregation，同一層的W是共享參數的。

以前面提過的GCN為例：

• 除以鄰居數做normalize，代表每個鄰居一樣重要
• 用Sum作為Aggregation function

Loss Function

接著就是定最後的Loss function讓他更新，GNN也分Supervised跟Unsupervised :

• Supervised : 拿預測出的label直接跟groud truth label做比較。
  

• Unsupervised : 利用相似的node要有相似的embedding，比較GNN算出的相似程度與Embedding的相似度的差異，Embedding相似前面介紹過。以下的CE是Cross Entropy，DEC是Decoder，自訂function，例如之前提到的兩個embedding直接算dot product來看相似程度。
  

Summary

所以具體要設定一個GNN應該要麼做，以下是大致整理的流程 :

1. 確認任務目標，決定要用什麼Loss function，例如要做Label classification，是Supervised Learning task並用Cross entropy算Loss
2. 決定Neighbor Aggregation function 和 Message function，訂出Neighbor的聚合規則
3. 決定GNN Layers的設定，要用幾層layer、activation function要用哪種等
4. 把Raw input Graph 轉成 Computational Graph
5. 開始算各node的embedding，再根據結果學習wight，同一層的weight是共享的。