圖神經網絡 Graph Neural Network (GNN)

傳統的神經網絡比較適合用於歐式空間的數據，而圖神經網絡 GNN 可以把神經網絡用在圖結構 (Graph) 中。圖神經網絡的種類很多，包括圖卷積網絡 GCN、圖注意力網絡 GAT、圖自編碼器 GAE 等。本文介紹最早被提出的圖神經網絡 (Graph Neural Network) GNN。

1.相關概念

之前的文章介紹過圖卷積網絡 GCN 和圖注意力網絡 GAT，其中 GCN 是 2016 年被提出的，GAT 是 2018 年提出的。本文介紹最早期的圖神經網絡 Graph Neural Network，簡稱 GNN。GNN 2009 年已經出現了，發表在論文《The graph neural network model》中。

1.1 graph_focused 和 node_focused

圖領域的應用通常分為兩類：graph_focused 和 node_focused。graph_focused 更關注於整個圖結構，對整個圖結構進行預測；node_focused 會關注節點的信息，可以進行節點的預測。

node_focused 可以理解為一個函數 τ，將圖 G 和節點 n 轉化為歐式空間中的一個 m 維向量：

node_focused

graph_focused 不關注於具體的節點 n，只需要得到圖 G 的向量 (包含整個圖 G 的信息)，因此函數 τ 可以改為：

graph_focused

下圖展示了graph_focused 和 node_focused 的應用。圖 (a) 為化學分子結構，需要預測分子結構對人體是否有害，則使用 graph_focused 的方法判斷整個分子結構是否有害，而不用判斷具體某個原子的有害性。圖 (b) 是一個城堡圖片，判斷圖中每一個節點是否屬於城堡內部 (即黑點)，此時需要得到每一個節點的特徵，並預測節點的類別，屬於 node_focused。圖 (c) 是網頁連接結構，可以通過 node_focused 判斷每一個網頁的類型。

graph_focused 和 node_focused 的應用

1.2 positional graph 和 nonpositional graph

GNN 可以用於 positional graph 和 nonpositional graph。nonpositional graph 是指節點的鄰居節點是沒有順序關係的，即可以隨意排列，這種 graph 比較常見。 而 positional graph 是指對於一個節點 n，需要為其所有鄰居指定一個獨一無二的整數位置，位置用 injective function 計算，如下公式所示：

positional 計算 (injective function)

可以理解為 nonpositional graph 不區分節點的鄰居，對於所有鄰居採用相同的方法計算。而 positional graph 會考慮鄰居的具體位置 (即 position)。

1.3 數學符號

下面是 GNN 中用到的一些符號含義：

符號含義

2.GNN 模型

2.1 傳播和輸出模型

在圖結構中，一個節點可以表示一個對象或概念，而邊可以表示節點之間的關係。GNN 用一個狀態向量 xn 表示節點 n 的狀態，節點 n 的狀態需要用四個部分的向量進行計算：節點 n 的特徵向量、鄰居節點的特徵向量、鄰居節點的狀態向量、邊 (與 n 相連) 的特徵向量。如下圖所示：

節點 1 的狀態向量 x1 計算方法

GNN 計算的公式主要包括傳播和輸出兩個部分。傳播部分主要是用 transition function f將鄰居節點和邊的信息結合在一起，得到當前節點的狀態向量。輸出部分用 output function o 將節點的特徵和狀態向量轉為輸出向量。transition function 和 output function 如下面的公式：

傳播公式和輸出公式

對於 positional graph，在使用 transition function 時，需要把鄰居節點的位置信息也包含進來。例如可以將鄰居節點的特徵 l_ne[n]、狀態 x_ne[n] 和邊的特徵 l_co[n] 按照 position 的順序排列，然後還需要進行 pad，把不存在的鄰居節點的位置置為空值。

對於 nonpositional graph，可以將 transition function 改成下面的形式，即對於所有鄰居採用相同的方式處理，最後再相加。

nonpositional 傳播公式

2.2 迭代計算

GNN 通過迭代計算節點的狀態 x，如下所示：

狀態向量迭代計算公式

GNN 整體結構如下圖所示：

GNN 整體結構

2.3 GNN 優化

GNN 中利用了巴拿赫不動點定理(Banach’s Fixed Point Theorem)，假設 transition function 是壓縮映射函數 (contraction map)，從而保證節點的狀態向量 x最終收斂到一個不動點。

為了確保 transition function f是一個壓縮映射，GNN 在 f 對 x 的偏導數矩陣中加上了懲罰項。最後再通過梯度下降學習模型的參數

3.參考文獻

The graph neural network model