圖神經網絡 GNN 把深度學習應用到圖結構 (Graph) 中，其中的圖卷積網絡 GCN 可以在 Graph 上進行卷積操作。但是 GCN 存在一些缺陷：依賴拉普拉斯矩陣，不能直接用於有向圖；模型訓練依賴於整個圖結構，不能用於動態圖；卷積的時候沒辦法為鄰居節點分配不同的權重。因此 2018 年圖注意力網絡 GAT (Graph Attention Network) 被提出，解決 GCN 存在的問題。
1.GCN 缺點
在之前的文章《圖神經網絡 GNN 之圖卷積網絡 (GCN)》介紹了圖卷積神經網絡 GCN，不熟悉的童鞋可以參考一下。GNN 模型可以分為頻譜域 (spectral domain) 和空間域 (spatial domain) 兩大類：spectral 的方法通常利用了拉普拉斯矩陣，藉助圖譜的方式進行卷積操作；spatial 的方法通常使用更直接的方式聚合鄰居節點的信息。
之前介紹的該 GCN 模型是基於頻譜域 (spectral domain) 的，利用了拉普拉斯矩陣，總的來說 GCN 存在下面的缺點：
GCN 假設圖是無向的，因為利用了對稱的拉普拉斯矩陣 (只有鄰接矩陣 A 是對稱的，拉普拉斯矩陣才可以正交分解)，不能直接用於有向圖。GCN 的作者為了處理有向圖，需要對 Graph 結構進行調整，要把有向邊劃分成兩個節點放入 Graph 中。例如 e1、e2 為兩個節點，r 為 e1，e2 的有向關係，則需要把 r 劃分為兩個關係節點 r1 和 r2 放入圖中。連接 (e1, r1)、(e2, r2)。
GCN 不能處理動態圖，GCN 在訓練時依賴於具體的圖結構，測試的時候也要在相同的圖上進行。因此只能處理 transductive 任務，不能處理 inductive 任務。transductive 指訓練和測試的時候基於相同的圖結構，例如在一個社交網絡上，知道一部分人的類別，預測另一部分人的類別。inductive 指訓練和測試使用不同的圖結構，例如在一個社交網絡上訓練，在另一個社交網絡上預測。
GCN 不能為每個鄰居分配不同的權重，GCN 在卷積時對所有鄰居節點均一視同仁，不能根據節點重要性分配不同的權重。
2018 年圖注意力網絡 GAT 被提出，用於解決 GCN 的上述問題，論文是《GRAPH ATTENTION NETWORKS》。GAT 採用了 Attention 機制，可以為不同節點分配不同權重，訓練時依賴於成對的相鄰節點，而不依賴具體的網絡結構，可以用於 inductive 任務。
2.GAT
假設 Graph 包含 N 個節點，每個節點的特徵向量為 hi，維度是 F，如下所示：
節點特徵向量 h
對節點特徵向量 h 進行線性變換，可以得到新的特徵向量 h'i，維度是 F'，如下所示，W 為線性變換的矩陣：
節點特徵向量線性變換 h'
節點 j 是節點 i 的鄰居，則可以使用 Attention 機制計算節點 j 對於節點 i 的重要性，即 Attention Score：
Attention Score
GAT 具體的 Attention 做法如下，把節點 i、j 的特徵向量 h'i、h'j 拼接在一起，然後和一個 2F' 維的向量 a 計算內積。激活函數採用 LeakyReLU，公式如下：
GAT Attention 計算方式
Attention 如下圖所示：
GAT Attention 示意圖
經過 Attention 之後節點 i 的特徵向量如下：
Attention 後的特徵向量
GAT 也可以採用 Multi-Head Attention，即多個 Attention，如下圖所示：
GAT Multi-Head Attention
如果有 K 個 Attention，則需要把 K 個 Attention 生成的向量拼接在一起，如下：
K 個 Attention 輸出結果拼接
但是如果是最後一層，則 K 個 Attention 的輸出不進行拼接，而是求平均。
最後一層 Attention 輸出結果
取出節點在 GAT 第一層隱藏層向量，用 T-SNE 算法進行降維可視化，得到的結果如下，可以看到不同類別的節點可以比較好的區分。
GAT 節點向量降維可視化
3.GAT 總結
- GAT 的時間複雜度為 O(|V|FF'+|E|F')，其中 |V|FF' 是計算所有節點特徵向量變換的時間複雜度 (即 Wh)，|E|F' 是計算 Attention 的時間複雜度。
- GAT 不依賴於完整的圖結構，只依賴於邊，因此可以用於 inductive 任務。
- GAT 可用於有向圖。
- 採用 Attention 機制，可以為不同的鄰居節點分配不同的權重。
4.參考文獻
GRAPH ATTENTION NETWORKS
SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS
