前言：前段時間了解了一下圖神經網絡，本篇博客記錄一下相關知識，以備不時之需。

強烈推薦這篇博客（作者來自 Google Research），個人認為是圖神經網絡基礎入門的不二選擇！

---

一、圖數據

隨著機器學習、深度學習的發展，語音、圖像、自然語言處理逐漸取得了很大的突破，然而語音、圖像、文本都是很簡單的序列或者網格數據，是很結構化的數據，深度學習很善于處理該種類型的數據。

然而現實世界中并不是所有的事物都可以表示成一個序列或者一個網格，例如社交網絡、知識圖譜、復雜的文件系統等，也就是說很多事物都是非結構化的。

1.1 定義&表示形式

圖數據是由節點（Node）和邊（Edge）組成的數據，最簡單的方式是使用鄰接矩陣來表示圖形結構，從而捕捉圖形中的節點和邊的相關性。假設圖中的節點數為n，那么鄰接矩陣就是一個n*n的矩陣，如果節點之間有關聯，則在鄰接矩陣中表示為1，無關聯則為0。如下圖，魯班與其他英雄都沒有關聯，表現在鄰接矩陣當中就是它所在的行與列為全零。

圖數據的信息包含3個層面，分別是節點信息（V）、邊信息（E）、圖整體（U）信息，它們通常是用向量來表示。而圖神經網絡就是通過學習數據從而得到3個層面向量的最優表示。

1.2 相關任務

1.2.1 圖層面的分類 / 回歸

例：分子是天然的圖，原子是節點，化學鍵是邊。現在要做一個分類，有一個苯環的分子分一類，兩個苯環的分子分一類。這是圖層面的分類任務。

1.2.2 節點層面的分類 / 回歸

例：假設一個跆拳道俱樂部里有A、B兩個教練，所有的會員都是節點。有一天A、B兩個跆拳道教練決裂，那么各個學員是愿意和A在一個陣營還是愿意和B在一個陣營？這是節點層面的分類任務。

1.2.3 邊層面的分類 / 回歸

例：UFO拳擊賽上，首先通過語義分割把臺上的人和環境分離開來。賽場上的人都是節點，現在要做一個預測，預測的是這些人之間的關系，是對抗關系？還是觀眾watch的關系？還是裁判watch的關系？這是邊層面的分類任務。

1.3 建模難點

相比于簡單的文本和圖像，這種網絡類型的非結構化的數據非常復雜，處理它的難點包括：

• 圖的大小是任意的，圖的拓撲結構復雜，沒有像圖像一樣的空間局部性
• 圖沒有固定的節點順序，或者說沒有一個參考節點
• 圖經常是動態圖，而且包含多模態的特征

那么對于這類數據我們該如何建模呢？能否將深度學習進行擴展使得能夠建模該類數據呢？這些問題催生了圖神經網絡。

---

二、圖神經網絡

相比較于神經網絡最基本的網絡結構全連接層（MLP），特征矩陣乘以權重矩陣，圖神經網絡多了一個鄰接矩陣。計算形式很簡單，三個矩陣相乘再加上一個非線性變換。

2.1 工作原理

一個比較常見的圖神經網絡的應用模式如下圖，輸入是一個圖，經過多層圖卷積等各種操作以及激活函數，最終得到各個節點的表示，以便于進行節點分類、鏈接預測、圖與子圖的生成等任務。

對圖神經網絡有一個直觀的感受與理解之后，我們來了解一下它的工作原理，如下圖所示，GNN是對圖中的所有屬性進行的一個可以優化的變換，它的輸入是一個圖，輸出也是個圖。它只對屬性向量（即上文所述的V、E、U）進行變換，但它不會改變圖的連接性（即哪些點互相連接經過GNN后是不會變的）。在獲取優化后的屬性向量之后，再根據實際的任務，后接全連接神經網絡，進行分類和回歸。大家可以把圖神經網絡看做是一個圖數據的在三個維度的特征提取器。

GNN對屬性向量優化的方法叫做消息傳遞機制。比如最原始的GNN是SUM求和傳遞機制；到后面發展成圖卷積網絡（GCN）就考慮到了節點的度，度越大，權重越小，使用了加權的SUM；再到后面發展為圖注意力網絡GAT，在消息傳遞過程中引入了注意力機制；目前的SOTA模型研究也都專注在了消息傳遞機制的研究。見下圖所示。

接下來將以幾個經典的GNN models為線來介紹圖神經網絡的發展歷程。

2.2 經典模型

2.2.1 Graph Convolution Networks (GCN)

論文信息：SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS (ICLR, 2017)
代碼：https://github.com/tkipf/pygcn
數據集：https://linqs-data.soe.ucsc.edu/public/lbc/cora.tgz

GCN可謂是圖神經網絡的“開山之作”，它首次將圖像處理中的卷積操作簡單的用到圖結構數據處理中來。

GCN的缺點也是很顯然易見的，第一，GCN需要將整個圖放到內存和顯存，這將非常耗內存和顯存，處理不了大圖；第二，GCN在訓練時需要知道整個圖的結構信息(包括待預測的節點), 這在現實某些任務中也不能實現(比如用今天訓練的圖模型預測明天的數據，那么明天的節點是拿不到的)。

2.2.2 Graph Sample and Aggregate (GraphSAGE)

為了解決GCN的兩個缺點問題，GraphSAGE被提了出來。在介紹GraphSAGE之前，先介紹一下Inductive learning（歸納學習）和Transductive learning（轉導學習）。注意到圖數據和其他類型數據的不同，圖數據中的每一個節點可以通過邊的關系利用其他節點的信息。這就導致一個問題，GCN輸入了整個圖，訓練節點收集鄰居節點信息的時候，用到了測試和驗證集的樣本，我們把這個稱為Transductive learning。然而，我們所處理的大多數的機器學習問題都是Inductive learning，因為我們刻意的將樣本集分為訓練/驗證/測試，并且訓練的時候只用訓練樣本。這樣對圖來說有個好處，可以處理圖中新來的節點，可以利用已知節點的信息為未知節點生成embedding，GraphSAGE就是這么干的。

GraphSAGE是一個Inductive Learning框架，具體實現中，訓練時它僅僅保留訓練樣本到訓練樣本的邊，然后包含Sample和Aggregate兩大步驟，Sample是指如何對鄰居的個數進行采樣，Aggregate是指拿到鄰居節點的embedding之后如何匯聚這些embedding以更新自己的embedding信息。

2.2.3 Graph Attention Networks (GAT)

GAT在傳播過程引入自注意力（self-attention）機制，每個節點的隱藏狀態通過注意其鄰居節點來計算。

論文信息：GRAPH ATTENTION NETWORKS (ICLR, 2018)
代碼：https://github.com/Diego999/pyGAT

---

參考資料

1. A Gentle Introduction to Graph Neural Networks (distill.pub)
2. Understanding Convolutions on Graphs (distill.pub)
3. 圖神經網絡（GNN）最簡單全面原理與代碼實現！ - 知乎 (zhihu.com)
4. 圖神經網絡從入門到入門 - 知乎 (zhihu.com)
5. 圖神經網絡入門（一）GCN圖卷積網絡 - 知乎 (zhihu.com)
6. pytorch框架下—GCN代碼詳細解讀_gcn代碼詳解_MelvinDong的博客-CSDN博客
7. Graph Attention Networks （GAT）pytorch源碼解讀 - 知乎 (zhihu.com)
8. 零基礎多圖詳解圖神經網絡（GNN/GCN）【論文精讀】_嗶哩嗶哩_bilibili
9. 1. 1.1_圖基本知識_嗶哩嗶哩_bilibili