Graph 7 - GNN Layer Design and Issue

前面大都只討論作法，沒有特別討論會引發的一些問題以及如何解決，以下會重新回顧實作GNN Layer的過程並把會遇到的問題與解法拿出來討論。

一個General GNN Layer從收到msg到丟出embedding的過程如下
Linear -> BatchNorm -> Dropout -> Activation -> Attention -> Aggregation Aggregation之前的步驟可以視為Transformation，在AGG前幫忙做一些對結果有幫助的Transformation

• Linear : 前面公式的乘以W就是在做這件事
• BatchNorm : Re-center 把這些node embedding的mean變成0, Re-scale 把這些node embedding的var變成1
• 其他的跟一般NN差不多

Receptive Field

Receptive Field是指會影響某個node結果的所有node，例如GNNs有3層，那一個node的receptive field會是他的3-hop範圍，但如果層數越多，receptive field會很大，不同node之間的receptive field差異就變小了，每個node的computational Graph包含的node重疊度高，得出的結果可能會很像，因此衍生出一個問題 : over-smoothing problem

over-smoothing problem

GNN無法設太多layers，通常我們可以看graph diameter決定能用多少層，以下有幾種解法

• 不要硬加，維持低層數GNN(Shallow GNNs)，從其他地方尋求解決辦法
  • 想法：既然層數無法增加，那就在每一層裡面讓他多做一些事
  • 解法一 : 前面提到的AGG跟transformer是用一層NN，把他多加幾層
  • 解法二 : 增加一些不會傳遞msg的layer，例如MLP，GNN裡面不一定都是GNN layer，可以加一些傳統的MLP。
• 硬加，我就是要增加層數的解法
  • 想法：前幾層的Node embeddings對Node的鑑別度是較高的，因為隨著層數增加，聚合的node變多，大家會越來越像
  • 解法三 : 增加捷徑(skip connenction)，加一條路讓GNN input可以不要進入這層layer，試圖把前幾層鑑別度高的embedding結果往後送(送批純的:D)，還有一種shortcut是直接跳到最後一層去，在所有GNN的最後一層用一個AGG來彙整全部的msg(包含走捷徑的跟走GNN來的)

Feature Augmentation

缺乏features

很多時候就只有相鄰矩陣而沒有特徵矩陣，也就是只有結構訊息能利用而沒有每個node本身的資訊。

• 解法一 : 直接把每個node加上一個constant feature(常數值)，反正每個node的結構不一樣還是可以學出不一樣的東西，是最簡單的做法
• 解法二 : 每個node都給一個id，然後用one hot encoder，node一樣可以拿到一個自己的feature，而且每個人的feature還不一樣

以上兩者的比較 :

• Expressive power : one-hot 勝 因為每個node特徵不一樣
• Inductive learning : constant 勝 new node進來完全沒門檻，根本不用改任何東西，
• Computational cost : constant 勝 特徵都一樣，且特徵只有一維，所以cost超低
• Use cases : constant可用在任何圖或是inductive任務，one-hot用在小圖或是transductive任務

註 : Inductive learning 是指對原本Graph沒有，新增進來的node之效果

還有一種情況是一定要做feature augmentation，那就是Cycle Graph，degree都一樣，不管幾層都沒差… 解決辦法：cycle count 標出裡面node的特徵，例如在cycle 3的成員node上都給[0,0,0,1,0]的onehot特徵

矩陣過於稀疏

• add virtual edges 將原本的相鄰矩陣A改成A' = A + A^2，某種特殊狀況特別需要這麼做–Bipartite graphs 例如作者與paper的graph，作者有寫該片paper則連一條edge ->這樣的graph會有一個特性，edge集中在author與paper之間，author之間或是paper之間的edge是完全沒有的(極端稀疏) 這時就很適合在他們之間加上virtual edge

• add virtual nodes 如何知道這是一個非常sparse的graph -> 他們的diameter很大。 加入一個virtual node以某種規則連接原本的node，例如有個node跟原本所有node都有edge，那原本圖中任兩node的最短路徑就會變2，可以幫助快速聚合。

Node Neighborhood Sampling

遇到Node太多的情況可以用Neighborhood Sampling，可以讓computing cost降到很低。