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