深度圖形卷積網路 Deep Learning on Graphs with Graph Convolutional Networks
在大家風靡於圖像(Images) 捲積網路(CNN)或順序行文字(一般text CNN、RNN)的深度學習技術時，以圖學(Graph)為基礎的神經網路也是目前正在興起的一個方向。這邊基於Tobias Skovgaard Jepsen、Thomas Kipf的文章整理翻譯，提供中文的解讀。
什麼是圖(Graph)?
圖學是一套廣泛應用於社群網路、推薦系統或文字結構的一套方法。以社群網路為例：人為節點(Node 或 Vertex)，人與人之間的關係(如：追蹤、好友等)就是邊(Edges，這樣就形成一張社群網路圖，稱為 G，其中 G =(V, E)，V 就是剛剛的一堆節點：人，而 E 就是人與人之間的邊。應用於文字上的話，那節點 V 就是一堆字，邊 E 就代表字跟字的相連。圖的優點在能保存良好的相互關係。以文字來說，這樣子的表示方式，可以表達出很多原本順序排列的文字無法呈現的文字架構、用法等。但也是會有相對應的缺點，如：文句較短，則圖會很小，保留的資訊可能會比原本的少等問題。
圖形卷積網路Graph Convolutional Networks?
在深度學習中，一般圖片(Images)上有表現很好的卷積神經網路(CNN)來作為特徵萃取器(Feature extractor)，但這樣的CNN無法應用再圖學上，所以衍生出了圖形卷積神經網路(GCN)。GCNs是一套強大的方法，一般的兩層隨機初始化的GCN就能夠作出很好的特徵表示。下面這張圖代表從Graph到二維特徵表示的GCN轉換，轉換後的特徵保留了原先Graph中各個node間的相對關係。
正式來說，先給出定義：
Graph Convolutional Networks圖形卷積網路是一個在圖(Graph)上的卷積神經網路。圖 G = (V, E)，如上所述：V 為一堆節點：人， E 為節點間的邊，其中GCN的輸入(Input)為：
- 特徵矩陣(Feature matrix) X，為 N × F⁰ 維度，N為節點數量，F⁰ 為每個節點的特徵數量。
2.相鄰矩陣(Adjacency matrix) A ，用來表示圖 G 的架構，為 N × N 維度。
有了輸入之後，接下來是卷積的隱藏層(Hidden layer)，公式表示為：
Hⁱ = f(Hⁱ⁻¹, A))
其中，第 0 層輸入為 H⁰ = X ，就是剛剛的特徵矩陣 X ，而方法 f 是一個傳遞(propagation)函數，將特徵 X 與代表圖形架構的相鄰矩陣 A 整合並輸出的結果作為下一層的輸入。
傳遞函數 Propagation Rule
數學表示為:
f(Hⁱ, A) = σ(AHⁱWⁱ)
於卷積傳遞函數 f 中，Wⁱ 代表第 i+1 層給輸入 Hⁱ加權用的權重矩陣(Weight matrix)， σ 是非線性的激活函數 (non-linear activation function)，如：ReLU 等。Wⁱ 的維度為 Fⁱ⁻¹× Fⁱ，Fⁱ⁻¹為前一層的網路的節點數量，若i = 1，則 Fⁱ⁻¹ = F⁰ 為每個節點的特徵數量。 Fⁱ則是這一層的權重節點數量。其實就跟一般的神經網路一樣，若輸入的特徵(Fⁱ⁻¹)有 128 維度，這層(Fⁱ)有64維度，則 Wⁱ 的維度為 128 × 64。
簡易範例+程式碼理解 (改寫自: Tobias Skovgaard Jepsen)
假設有一張簡單的圖，如下：
這張圖的相鄰矩陣可以用numpy表示為：
+-----+---+---+---+---+
| 節點 | 0 | 1 | 2 | 3 |
+-----+---+---+---+---+
| 0 | X | X | X | O |
| 1 | O | X | O | X |
| 2 | X | O | X | O |
| 3 | X | O | X | X |
+-----+---+---+---+---+O 有被指; X 沒被指
A = np.matrix(
[[0, 0, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[0, 1, 0, 0]],
dtype=float
)
# 這邊 1 代表被指向
其中，這裡的圖是有向圖，故指出去的才算相鄰。
假設每個節點的特徵為：
X = np.matrix([[i, -i]
for i in range(A.shape[0])
], dtype=float)"""
matrix([[ 0., 0.], # 節點 0
[ 1., -1.], # 節點 1
[ 2., -2.], # 節點 2
[ 3., -3.] # 節點 3
])
"""
卷積
有了圖、節點、節點相互關係及節點特徵後，就可以進行第一次卷積傳遞：
A * X"""
matrix([[ 3., -3.], # 節點 0
[ 2., -2.], # 節點 1
[ 4., -4.], # 節點 2
[ 1., -1.]] # 節點 3
)
"""
這個矩陣乘法代表了對於每個節點來說，它們的值代表了每個指向該節點的節點們的特徵總和。舉例而言，節點 1 的值[ 2., -2.]，即為指向它的節點 0與節點 2 加總而得([ 0., 0.] + [ 2., -2.])。這邊可以自己算算看會更有感覺。
但這邊幾個問題！
- 自己的特徵值沒有被算到：剛才的計算只有整合指向自己的所有節點，除非有自己指向自己(自我迴圈 Self-loops)，否則本身節點的特徵值不會被計算進去。
- 被愈多節點指到的節點，其傳遞後的值就越大，反之亦然。這樣的情況可能會導致梯度消失(Vanishing gradients)或是梯度爆炸(Exploding gradients)的問題。
為了解決以上兩個問題，提出了這兩個方法：
- 自我迴圈(Self-loops)：預設這個節點有自我迴圈的關係，使其考慮自己的特徵值。實際作法只要把原本的相鄰矩陣 A 加上 單位矩陣 (Identity matrix) I 即完成自我迴圈的效果。
I = np.matrix(np.eye(A.shape[0])) ###
matrix([[1., 0., 0., 0.],
[0., 1., 0., 0.],
[0., 0., 1., 0.],
[0., 0., 0., 1.]])
"""A_hat = A + I"""
matrix([[1., 0., 0., 1.],
[1., 1., 1., 0.],
[0., 1., 1., 1.],
[0., 1., 0., 1.]])
"""
接下來，未來在傳遞參數時就會考慮自己的特徵值了。
A_hat * X"""
matrix([[ 3., -3.],
[ 3., -3.],
[ 6., -6.],
[ 4., -4.]])
"""
- 標準化(Normalize) 相鄰矩陣：
由於剛剛假設的情況是雙向圖，而本文中的例子只考慮指向自己的節點(In-degree)來計算節點的值，故在此標準化的對象也是指考慮指向自己的這些節點。實際上可以考慮圖的特性來設計，如無向圖(Undirected Graph)等。
標準化的步驟也非常簡單，只需要將相鄰矩陣 A 乘上反節點數的矩陣(Inverse degree matrix) D 即可。因此，卷積函數會變成：
f(Hⁱ, A) = σ(D⁻¹A Hⁱ Wⁱ)
這邊先解釋一下，D⁻¹A 的效果：
D = np.array(np.sum(A_hat, axis=1)).reshape(-1) # 考慮自迴圈
D = np.matrix(np.diag(D))# D轉換後的結果，如下：
"""
matrix([[2., 0., 0., 0.],
[0., 3., 0., 0.],
[0., 0., 3., 0.],
[0., 0., 0., 2.]])
"""
這樣標準化的相鄰矩陣就出來了
D**-1 * A_hat"""
matrix([[0.5 , 0. , 0. , 0.5 ],
[0.33333333, 0.33333333, 0.33333333, 0. ],
[0. , 0.33333333, 0.33333333, 0.33333333],
[0. , 0.5 , 0. , 0.5 ]])
"""
原本為
A_hat"""
matrix([[1., 0., 0., 1.],
[1., 1., 1., 0.],
[0., 1., 1., 1.],
[0., 1., 0., 1.]])
"""
這樣兩個問題就得到基本的解決了～
首先，增加了自迴圈，讓傳遞函數能考慮到自己的特徵值。
接下來，考慮了標準化，弭平了節點連接數不同造成的差異。
激活函數 (Activation function)
這邊簡單使用 ReLU 作為激活函數，來演示整個傳遞公式：
f(Hⁱ, A) = σ(D⁻¹A Hⁱ Wⁱ)
def relu(x): # 定義 ReLU 函數
return np.maximum(x,0)W = np.matrix([[1, -1], # 定義第一層的權重
[-1, 1]])relu(D** -1 * A_hat * X * W) # D為 A_hat 的反節點數矩陣"""
matrix([[3., 0.],
[2., 0.],
[4., 0.],
[4., 0.]])
"""
完成，一層的卷積網路，裡面有 改良後的相鄰矩陣 D⁻¹A、節點特徵值 Hⁱ 與這層的權重值Wⁱ。
用實際資料實戰
這邊使用的資料是 Zachary’s karate club，為一個社群網路資料，其節點代表俱樂部會員，邊代表會員的相互關係。中間有一些糾葛，最後分成 A 及 I 兩群。
建置GCN
這邊要先使用networkx這個python的圖套件來取得Zachary’s Karate Club圖資料。接下來算 D 與 A 的函數：
from networkx import * # 引用networkx套件zkc = karate_club_graph() # 取得俱樂部圖
order = sorted(list(zkc.nodes())) #取得照順序排的節點
# order = [0, 1, 2, ..., 33]A = to_numpy_matrix(zkc, nodelist=order) # 取得相鄰矩陣
I = np.eye(zkc.number_of_nodes()) # 為了自循環所定義的單位矩陣A_hat = A + I # 有自循環的相鄰矩陣
D_hat = np.array(np.sum(A_hat, 1)).reshape(-1) #
D_hat = np.matrix(np.diag(D_hat))
隨機定義兩層神經網路的權重
W_1 = np.random.normal(
loc=0, scale=1, size=(zkc.number_of_nodes(), 4)) # 維度=(節點數, 特徵數)W_2 = np.random.normal(
loc=0, size=(W_1.shape[1], 2)) # 最後要分兩群，所以維度定為(前一層特徵數, 2)
把網路搭建起來
def gcn_layer(A_hat, D_hat, X, W):
return relu(D_hat**-1 * A_hat * X * W)H_1 = gcn_layer(A_hat, D_hat, I, W_1)
H_2 = gcn_layer(A_hat, D_hat, H_1, W_2)output = H_2"""
output = matrix([
[1.07066469, 0. ],
[0.85368845, 0. ],
[0.36304432, 0.02877576],
[0.81091611, 0. ],
[1.4729507 , 0. ],
...
[0.05405459, 0.44707327]
])"""
輸出 (output)的每一列為 one-hot encoded 的分類類別(Categorical label)。並將這些值分離出來，並繪於平面上：
feature_representations = {
node: np.array(output)[node]
for node in zkc.nodes()}
以上就是圖形卷積網路 Graph Convolutional Networks 的基本概念，剛剛的例子其實都還沒有開始訓練呢！
題外話，基於Kipf & Welling (ICLR 2017)的半監督式學習法來演示一下圖形學習的變化：
https://tkipf.github.io/graph-convolutional-networks/images/video.mp4
Semi-supervised classification with GCNs: Latent space dynamics for 300 training iterations with a single label per class. Labeled nodes are highlighted.
結論
這篇文章整理了圖形卷積網路的超簡單介紹，介紹特徵及圖的結構要怎麼被整合進去神經網路中，使用python的numpy套件來實作，從結果來看：好像甚至隨機初始化都真的能區分出Zachary’s Karate Club的兩個類別呢！
References
[1] Blog post on graph convolutional networks by Thomas Kipf.
[2] Paper called Semi-Supervised Classification with Graph Convolutional Networks by Thomas Kipf and Max Welling.