作者：Tobias Skovgaard Jepsen

編譯：ronghuaiyang

導讀

這是第一部分，圖卷積網絡的高級介紹。

圖的機器學習是一項非常困難的任務，因為圖的結構非常複雜，但同時也提供了豐富的信息。本文是關於如何利用圖卷積網絡(GCNs)對圖進行深度學習的系列文章中的第一篇。GCNs是一種功能強大的神經網絡，旨在直接處理圖並利用圖的結構信息。

在本文中，我將介紹GCNs，並使用圖解的方式說明信息如何通過GCN的隱藏層進行傳播。我們將看到GCNs是如何聚合來自前一層的信息，以及這種機制如何生成圖中節點的有用特徵表示。

什麼是圖卷積網絡？

GCNs是一種非常強大的圖機器學習神經網絡結構。事實上，它們非常強大，甚至一個隨機初始化的2層GCN都可以生成網絡中節點的有用特徵表示。下圖展示了由這樣一個GCN生成的網絡中每個節點的二維表示。請注意，即使沒有任何訓練，網絡中節點的相對接近性也保留在二維表示中。

更正式地說，graph convolutional network (GCN)是一個對圖進行操作的神經網絡。給定一個圖G = (V, E)， GCN的輸入包括：

• 一個N×F⁰的輸入特徵矩陣X，其中N是節點的數量，F⁰是每個節點輸入特徵的數量
• 圖結構的N×N矩陣表示，如G.[1]的鄰接矩陣A

GCN中的一個隱藏層可以寫成H^i^ = f(H^i-1^，A))，其中，H⁰=X， f是前向傳播。每一層的H^i^對應於一個N×F^i^的特徵矩陣，其中每一是一個特性的表示一個節點的特徵。在每一層，使用傳播規則f聚合這些特徵，形成下一層的特徵。這樣，每個連續層的特徵都變得越來越抽象。在這個框架中，GCN的變體只在傳播規則f的選擇上有所不同。

一個簡單的傳播規則

最簡單的傳播規則之一是：

其中，W^i^是第i層的權值矩陣，σ是非線性激活函數，比如ReLU函數。權值矩陣的維度為F^i^×F^i+1^，換句話說，權值矩陣的第二個維度的大小決定了下一層的特徵的維度。如果你熟悉卷積神經網絡，這個操作類似於濾波操作，因為權值在圖中的各個節點上是共享的。

簡化

我們用最簡單的方法檢查一下傳播規則。令：

• i = 1的時候，f 是關於輸入特徵矩陣的函數
• σ 是恆等變換函數
• 選擇這樣的權值，使得，AH⁰W⁰ =AXW⁰ = AX.

換句話說， f(X,A

) =AX，這個傳播法則也許太簡單了一點，不過我們後面會加點東西。另外注意，AX現在相當於多層感知器的輸入層。

一個簡單的圖的例子

作為一個簡單的例子，我們使用下面的圖：

下面是 numpy的鄰接矩陣的表示：

A = np.matrix([ 
 [0, 1, 0, 0], 
 [0, 0, 1, 1], 
 [0, 1, 0, 0], 
 [1, 0, 1, 0]], 
 dtype=float
 )

下面，我們需要特徵！我們為每個節點生成了2個整數特徵，這樣後面手動計算會很方便。

In [3]: X = np.matrix([
 [i, -i] 
 for i in range(A.shape[0]) 
], dtype=float) 

XOut[3]: matrix([ 
 [ 0., 0.], 
 [ 1., -1.], 
 [ 2., -2.], 
 [ 3., -3.] 
])

應用傳播法則

好了，我們現在有了一個圖，鄰接矩陣 A還有一組特徵 X，我們看看應用傳播法則的時候發生了什麼：

In [6]: A * X
Out[6]: matrix([ 
 \t\t\t\t\t\t\t\t\t\t\t\t\t\t[ 1., -1.], 
 [ 5., -5.], 
 [ 1., -1.], 
 [ 2., -2.]]
 ）

發生了什麼？每個節點(每一行)的表示現在是其鄰居特徵的總和！換句話說，圖卷積層將每個節點表示為其鄰域的集合。我鼓勵你自己檢查一下計算結果。注意，在本例中，如果存在一條從v到n的邊，則節點n是節點v的鄰居。

問題浮出水面！

你可能已經發現問題了：

• 節點的聚合表示不包括它自己的特徵！表示是鄰居節點特徵的集合，因此只有具有自循環的節點才會在集合中包含自己的特徵
• 度大的節點的特徵表示值較大，度小的節點的特徵表示值較小。這可能導致梯度消失或爆炸，對於隨機梯度下降算法也存在問題，這些算法通常用於訓練此類網絡，並且對每個輸入特徵的尺度(或值範圍)敏感。

下面，我將分別討論這些問題。

加入自循環

要解決第一個問題，只需向每個節點添加一個自循環。實際上，這是通過在應用傳播規則之前將單位矩陣I添加到鄰接矩陣A來實現的。

In [4]: I = np.matrix(np.eye(A.shape[0])) 
IOut[4]: matrix([ 
 \t\t\t\t\t\t[1., 0., 0., 0.], 
 \t\t\t\t\t\t[0., 1., 0., 0.], 
 \t\t\t\t\t\t[0., 0., 1., 0.], 
 \t\t\t\t\t\t[0., 0., 0., 1.]  

\t\t\t\t\t\t\t])

In [8]: A_hat = A + I 
 A_hat * X
Out[8]: matrix([ 
 \t\t\t\t\t\t\t[ 1., -1.], 
 \t\t\t\t\t\t\t[ 6., -6.], 
 \t\t\t\t\t\t\t[ 3., -3.], 
 \t\t\t\t\t\t\t[ 5., -5.]
\t\t\t\t\t\t])

由於節點現在是其自身的鄰居，所以在聚合其鄰居的特徵時將包含該節點自己的特徵！

特徵表示的歸一化

特徵表示可以通過節點的度來歸一化，將鄰接矩陣 A與度矩陣 D的逆矩陣相乘進行轉換。因此，我們的簡化傳播規則是這樣的：

我們看看發生了什麼，我們先計算度矩陣。

In [9]: D = np.array(np.sum(A, axis=0))[0] 
\t\t\t\t\tD = np.matrix(np.diag(D)) 
\t\t\t\t\tD
 
Out[9]: matrix([ 
 \t\t\t\t\t\t\t[1., 0., 0., 0.], 
 \t\t\t\t\t\t\t[0., 2., 0., 0.], 
 \t\t\t\t\t\t\t[0., 0., 2., 0.], 
 \t\t\t\t\t\t\t[0., 0., 0., 1.] 
\t\t\t\t\t\t\t])

在應用規則之前，讓我們看看在鄰接矩陣轉換之後會發生什麼。

之前

A = np.matrix([ 
 \t\t\t\t\t\t[0, 1, 0, 0], 
 \t\t\t\t\t\t[0, 0, 1, 1], 
 \t\t\t\t\t\t[0, 1, 0, 0], 
 \t\t\t\t\t\t[1, 0, 1, 0]
\t\t\t\t\t\t\t], 
 dtype=float)

之後

In [10]: D**-1 * A
Out[10]: matrix([ 
 \t\t\t\t\t\t\t[0. , 1. , 0. , 0. ], 
 \t\t\t\t\t\t\t[0. , 0. , 0.5, 0.5], 
 \t\t\t\t\t\t\t[0. , 0.5, 0. , 0. ], 
 \t\t\t\t\t\t\t[0.5, 0. , 0.5, 0. ]
\t\t\t\t\t\t\t])

我們發現鄰接矩陣中的每一行的權值都除以了對於行的節點的度。我們在變換後的鄰接矩陣上應用傳播法則

In [11]: D**-1 * A * X
Out[11]: matrix([ 
 \t\t\t\t\t\t\t\t[ 1. , -1. ], 
 \t\t\t\t\t\t\t\t[ 2.5, -2.5], 
 \t\t\t\t\t\t\t\t[ 0.5, -0.5], 
 \t\t\t\t\t\t\t\t[ 2. , -2. ] 
\t\t\t\t\t\t\t\t])

得到與相鄰節點特徵均值對應的節點表示。這是因為(轉換後的)鄰接矩陣中的權值對應於相鄰節點特徵加權和中的權值。我再次鼓勵你親自驗證這一觀察結果。

合在一起

現在我們結合了自循環和歸一化技巧。此外，我們還將重新介紹先前為簡化討論而放棄的權值和激活函數。

把權值加回來

首先要做的是使用權重。注意這裡 D_hat是 A_hat=A+I的度矩陣，即加了自循環的A的度矩陣。

In [45]: W = np.matrix([ 
 \t\t\t\t\t\t\t\t\t\t\t[1, -1], 
 \t\t\t\t\t\t\t\t\t\t\t[-1, 1] 
\t\t\t\t\t\t\t\t\t\t]) 
\t\t\t\t\t\tD_hat**-1 * A_hat * X * W

Out[45]: matrix([ 
 \t\t\t\t\t\t\t\t\t[ 1., -1.], 
 \t\t\t\t\t\t\t\t\t[ 4., -4.], 
 \t\t\t\t\t\t\t\t\t[ 2., -2.], 
 \t\t\t\t\t\t\t\t\t[ 5., -5.] 
\t\t\t\t\t\t\t\t]) 

如果我們想減小輸出特徵表示的維數，我們可以減小權值矩陣 W的大小:

In [46]: W = np.matrix([ 
 \t\t\t\t\t\t\t\t\t\t\t\t\t\t[1], 
 \t\t\t\t\t\t\t\t\t\t\t\t\t\t[-1] 
\t\t\t\t\t\t\t\t\t\t\t\t]) 
\t\t\t\t\t\tD_hat**-1 * A_hat * X * W

Out[46]: matrix([[1.], 
 \t\t\t\t\t[4.], 
 \t\t\t\t\t[2.], 
 \t\t\t\t\t[5.]])

添加激活函數

我們選擇保留特徵表示的維數，並應用ReLU激活函數。

In [51]: W = np.matrix([ 
 \t\t\t\t\t\t\t\t\t\t\t\t\t\t[1, -1], 
 \t\t\t\t\t\t\t\t\t\t\t\t\t\t[-1, 1] 
\t\t\t\t\t\t\t\t\t\t\t\t]) 
\t\t\t\t\t\trelu(D_hat**-1 * A_hat * X * W)

Out[51]: matrix([[1., 0.], 
 \t\t\t\t\t[4., 0.], 
 \t\t\t\t\t[2., 0.], 
 \t\t\t\t\t[5., 0.]])

看！一個完整的帶有鄰接矩陣，輸入特徵，權重和激活函數的隱藏層！

回到現實中

最後，我們可以把一個圖卷積網絡應用到一個真實的圖上。我將向你展示如何生成我們在本文前面看到的特徵表示。

Zachary的空手道俱樂部

Zachary的空手道俱樂部是一個常用的社交網絡，每個節點代表一個空手道俱樂部的成員，並將他們之間的關係用邊來表示。在Zachary學習空手道的時候，管理員和教練發生了衝突，導致空手道俱樂部一分為二。下圖顯示了網絡的圖表示，節點的標記表示了這個人屬於俱樂部的哪個部分。管理員和教練分別用“A”和“I”標記。

構建GCN

現在我們來構建這個圖卷積網絡。實際上，我們不會訓練網絡，而只是隨機初始化它來生成我們在本文開頭看到的特徵表示。我們將使用 networkx，它有一個現成的俱樂部的圖形表示，並很容易計算 A_hat和 D_hat矩陣。

from networkx import karate_club_graph, to_numpy_matrixz
kc = karate_club_graph()
order = sorted(list(zkc.nodes()))
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, axis=0))[0]
D_hat = np.matrix(np.diag(D_hat))

接下來，我們隨機初始化權值。

W_1 = np.random.normal( 
 \t\t\t\t\t\t\t\t\t\t\t\t\tloc=0, 
 scale=1, size=(zkc.number_of_nodes(), 4))W_2 = np.random.normal( loc=0, size=(W_1.shape[1], 2))

堆疊GCN層。這裡我們只使用單位矩陣作為特徵表示，即每個節點都表示為一個類別變量的獨熱編碼。

def gcn_layer(A_hat, D_hat, X, W): 
\t\t\treturn 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

我們提取特徵表示。

feature_representations = { 
 \t\t\tnode: np.array(output)[node]  

 \t\t\tfor node in zkc.nodes()}

看！在Zachary的空手道俱樂部中，特徵表示可以很好的將社區分開。我們還沒開始訓練呢！

應該注意到，在這個示例中，由於ReLU函數的作用，隨機初始化的權重很可能在x軸或y軸上給出0個值，因此需要多做幾次隨機初始化才能生成上面的圖。

結論

在這篇文章中，我對圖卷積網絡做了一個高層次的介紹，並說明了GCN中每一層節點的特徵表示是如何基於其鄰域來進行聚合的。我們看到了如何使用numpy來構建這些網絡，以及它們是多麼強大:即使是隨機初始化的GCNs也可以在Zachary的空手道俱樂部中分隔社區。

英文原文：https://towardsdatascience.com/how-to-do-deep-learning-on-graphs-with-graph-convolutional-networks-7d2250723780