圖卷積網絡到底怎么做，這是一份極簡的Numpy實現
由于圖結構非常復雜且信息量很大，因此對于圖的機器學習是一項艱巨的任務。本文介紹了如何使用圖卷積網絡(GCN)對圖進行深度學習，GCN 是一種可直接作用于圖并利用其結構信息的強大神經網絡。
本文將介紹 GCN，并使用代碼示例說明信息是如何通過 GCN 的隱藏層傳播的。讀者將看到 GCN 如何聚合來自前一層的信息，以及這種機制如何生成圖中節點的有用特征表征。
何為圖卷積網絡?
GCN 是一類非常強大的用于圖數據的神經網絡架構。事實上，它非常強大，即使是隨機初始化的兩層 GCN 也可以生成圖網絡中節點的有用特征表征。下圖展示了這種兩層 GCN 生成的每個節點的二維表征。請注意，即使沒有經過任何訓練，這些二維表征也能夠保存圖中節點的相對鄰近性。
更形式化地說，圖卷積網絡(GCN)是一個對圖數據進行操作的神經網絡。給定圖 G = (V, E)，GCN 的輸入為：
- 一個輸入維度為 N × F⁰ 的特征矩陣 X，其中 N 是圖網絡中的節點數而 F⁰ 是每個節點的輸入特征數。
- 一個圖結構的維度為 N × N 的矩陣表征，例如圖 G 的鄰接矩陣 A。[1]
因此，GCN 中的隱藏層可以寫作 Hⁱ = f(Hⁱ⁻¹, A))。其中，H⁰ = X，f 是一種傳播規則 [1]。每一個隱藏層 Hⁱ 都對應一個維度為 N × Fⁱ 的特征矩陣，該矩陣中的每一行都是某個節點的特征表征。在每一層中，GCN 會使用傳播規則 f 將這些信息聚合起來，從而形成下一層的特征。這樣一來，在每個連續的層中特征就會變得越來越抽象。在該框架下，GCN 的各種變體只不過是在傳播規則 f 的選擇上有所不同 [1]。
傳播規則的簡單示例
下面，本文將給出一個最簡單的傳播規則示例 [1]：
- f(Hⁱ, A) = σ(AHⁱWⁱ)
其中，Wⁱ 是第 i 層的權重矩陣，σ 是非線性激活函數(如 ReLU 函數)。權重矩陣的維度為 Fⁱ × Fⁱ⁺¹，即權重矩陣第二個維度的大小決定了下一層的特征數。如果你對卷積神經網絡很熟悉，那么你會發現由于這些權重在圖中的節點間共享，該操作與卷積核濾波操作類似。
簡化
接下來我們在最簡單的層次上研究傳播規則。令：
- i = 1，(約束條件 f 是作用于輸入特征矩陣的函數)
- σ 為恒等函數
- 選擇權重(約束條件： AH⁰W⁰ =AXW⁰ = AX)
換言之，f(X, A) = AX。該傳播規則可能過于簡單，本文后面會補充缺失的部分。此外，AX 等價于多層感知機的輸入層。
1. 簡單的圖示例
我們將使用下面的圖作為簡單的示例：
一個簡單的有向圖。
使用 numpy 編寫的上述有向圖的鄰接矩陣表征如下：
- A = np.matrix([
- [0, 1, 0, 0],
- [0, 0, 1, 1],
- [0, 1, 0, 0],
- [1, 0, 1, 0]],
- dtype=float
- )
接下來，我們需要抽取出特征!我們基于每個節點的索引為其生成兩個整數特征，這簡化了本文后面手動驗證矩陣運算的過程。
- In [3]: X = np.matrix([
- [i, -i]
- for i in range(A.shape[0])
- ], dtype=float)
- X
- Out[3]: matrix([
- [ 0., 0.],
- [ 1., -1.],
- [ 2., -2.],
- [ 3., -3.]
- ])
2. 應用傳播規則
我們現在已經建立了一個圖，其鄰接矩陣為 A，輸入特征的集合為 X。下面讓我們來看看，當我們對其應用傳播規則后會發生什么：
- In [6]: A * X
- Out[6]: matrix([
- [ 1., -1.],
- [ 5., -5.],
- [ 1., -1.],
- [ 2., -2.]]
每個節點的表征(每一行)現在是其相鄰節點特征的和!換句話說，圖卷積層將每個節點表示為其相鄰節點的聚合。大家可以自己動手驗證這個計算過程。請注意，在這種情況下，如果存在從 v 到 n 的邊，則節點 n 是節點 v 的鄰居。
問題
你可能已經發現了其中的問題：
- 節點的聚合表征不包含它自己的特征!該表征是相鄰節點的特征聚合，因此只有具有自環(self-loop)的節點才會在該聚合中包含自己的特征 [1]。
- 度大的節點在其特征表征中將具有較大的值，度小的節點將具有較小的值。這可能會導致梯度消失或梯度爆炸 [1, 2]，也會影響隨機梯度下降算法(隨機梯度下降算法通常被用于訓練這類網絡，且對每個輸入特征的規模(或值的范圍)都很敏感)。
接下來，本文將分別對這些問題展開討論。
1. 增加自環
為了解決***個問題，我們可以直接為每個節點添加一個自環 [1, 2]。具體而言，這可以通過在應用傳播規則之前將鄰接矩陣 A 與單位矩陣 I 相加來實現。
- In [4]: I = np.matrix(np.eye(A.shape[0]))
- I
- Out[4]: matrix([
- [1., 0., 0., 0.],
- [0., 1., 0., 0.],
- [0., 0., 1., 0.],
- [0., 0., 0., 1.]
- ])
- In [8]: AA_hat = A + I
- A_hat * X
- Out[8]: matrix([
- [ 1., -1.],
- [ 6., -6.],
- [ 3., -3.],
- [ 5., -5.]])
現在，由于每個節點都是自己的鄰居，每個節點在對相鄰節點的特征求和過程中也會囊括自己的特征!
2. 對特征表征進行歸一化處理
通過將鄰接矩陣 A 與度矩陣 D 的逆相乘，對其進行變換，從而通過節點的度對特征表征進行歸一化。因此，我們簡化后的傳播規則如下：
- f(X, A) = D⁻¹AX
讓我們看看發生了什么。我們首先計算出節點的度矩陣。
- In [9]: D = np.array(np.sum(A, axis=0))[0]
- D = np.matrix(np.diag(D))
- D
- Out[9]: matrix([
- [1., 0., 0., 0.],
- [0., 2., 0., 0.],
- [0., 0., 2., 0.],
- [0., 0., 0., 1.]
- ])
在應用傳播規則之前，不妨看看我們對鄰接矩陣進行變換后發生了什么。
變換之前
- A = np.matrix([
- [0, 1, 0, 0],
- [0, 0, 1, 1],
- [0, 1, 0, 0],
- [1, 0, 1, 0]],
- dtype=float
- )
變換之后
- In [10]: D**-1 * A
- Out[10]: matrix([
- [0. , 1. , 0. , 0. ],
- [0. , 0. , 0.5, 0.5],
- [0. , 0.5, 0. , 0. ],
- [0.5, 0. , 0.5, 0. ]
- ])
可以觀察到，鄰接矩陣中每一行的權重(值)都除以該行對應節點的度。我們接下來對變換后的鄰接矩陣應用傳播規則：
- In [11]: D**-1 * A * X
- Out[11]: matrix([
- [ 1. , -1. ],
- [ 2.5, -2.5],
- [ 0.5, -0.5],
- [ 2. , -2. ]
- ])
得到與相鄰節點的特征均值對應的節點表征。這是因為(變換后)鄰接矩陣的權重對應于相鄰節點特征加權和的權重。大家可以自己動手驗證這個結果。
整合
現在，我們將把自環和歸一化技巧結合起來。此外，我們還將重新介紹之前為了簡化討論而省略的有關權重和激活函數的操作。
1. 添加權重
首先要做的是應用權重。請注意，這里的 D_hat 是 A_hat = A + I 對應的度矩陣，即具有強制自環的矩陣 A 的度矩陣。
- In [45]: W = np.matrix([
- [1, -1],
- [-1, 1]
- ])
- D_hat**-1 * A_hat * X * W
- Out[45]: matrix([
- [ 1., -1.],
- [ 4., -4.],
- [ 2., -2.],
- [ 5., -5.]
- ])
如果我們想要減小輸出特征表征的維度，我們可以減小權重矩陣 W 的規模：
- In [46]: W = np.matrix([
- [1],
- [-1]
- ])
- D_hat**-1 * A_hat * X * W
- Out[46]: matrix([[1.],
- [4.],
- [2.],
- [5.]]
- )
2. 添加激活函數
本文選擇保持特征表征的維度，并應用 ReLU 激活函數。
- In [51]: W = np.matrix([
- [1, -1],
- [-1, 1]
- ])
- relu(D_hat**-1 * A_hat * X * W)
- Out[51]: matrix([[1., 0.],
- [4., 0.],
- [2., 0.],
- [5., 0.]])
這就是一個帶有鄰接矩陣、輸入特征、權重和激活函數的完整隱藏層!
在真實場景下的應用
***，我們將圖卷積網絡應用到一個真實的圖上。本文將向讀者展示如何生成上文提到的特征表征。
1. Zachary 空手道俱樂部
Zachary 空手道俱樂部是一個被廣泛使用的社交網絡，其中的節點代表空手道俱樂部的成員，邊代表成員之間的相互關系。當年，Zachary 在研究空手道俱樂部的時候，管理員和教員發生了沖突，導致俱樂部一分為二。下圖顯示了該網絡的圖表征，其中的節點標注是根據節點屬于俱樂部的哪個部分而得到的，「A」和「I」分別表示屬于管理員和教員陣營的節點。
Zachary 空手道俱樂部圖網絡
2. 構建 GCN
接下來，我們將構建一個圖卷積網絡。我們并不會真正訓練該網絡，但是會對其進行簡單的隨機初始化，從而生成我們在本文開頭看到的特征表征。我們將使用 networkx，它有一個可以很容易實現的 Zachary 空手道俱樂部的圖表征。然后，我們將計算 A_hat 和 D_hat 矩陣。
- from networkx import to_numpy_matrix
- zkc = karate_club_graph()
- order = sorted(list(zkc.nodes()))
- A = to_numpy_matrix(zkc, nodelist=order)
- I = np.eye(zkc.number_of_nodes())
- AA_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(
- loc=0, scale=1, size=(zkc.number_of_nodes(), 4))
- W_2 = np.random.normal(
- loc=0, size=(W_1.shape[1], 2))
接著，我們會堆疊 GCN 層。這里，我們只使用單位矩陣作為特征表征，即每個節點被表示為一個 one-hot 編碼的類別變量。
- 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
我們進一步抽取出特征表征。
- feature_representations = {
- node: np.array(output)[node]
- for node in zkc.nodes()}
你看，這樣的特征表征可以很好地將 Zachary 空手道俱樂部的兩個社區劃分開來。至此，我們甚至都沒有開始訓練模型!
Zachary 空手道俱樂部圖網絡中節點的特征表征
我們應該注意到，在該示例中由于 ReLU 函數的作用，在 x 軸或 y 軸上隨機初始化的權重很可能為 0，因此需要反復進行幾次隨機初始化才能生成上面的圖。
結語
本文中對圖卷積網絡進行了高屋建瓴的介紹，并說明了 GCN 中每一層節點的特征表征是如何基于其相鄰節點的聚合構建的。讀者可以從中了解到如何使用 numpy 構建這些網絡，以及它們的強大：即使是隨機初始化的 GCN 也可以將 Zachary 空手道俱樂部網絡中的社區分離開來。
參考文獻
- Blog post on graph convolutional networks by Thomas Kipf.
- Paper called Semi-Supervised Classification with Graph Convolutional Networks by Thomas Kipf and Max Welling.
原文鏈接：
https://towardsdatascience.com/how-to-do-deep-learning-on-graphs-with-graph-convolutional-networks-7d2250723780
【本文是51CTO專欄機構“機器之心”的原創譯文，微信公眾號“機器之心( id: almosthuman2014)”】
