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