什么是GCN

由于高度的復(fù)雜性和信息的結(jié)構(gòu)特征，圖上的機(jī)器學(xué)習(xí)是一項(xiàng)困難的任務(wù)?！窯CN是被設(shè)計(jì)用來針對(duì)圖結(jié)構(gòu)的神經(jīng)網(wǎng)絡(luò)，它能從之前的網(wǎng)絡(luò)層中聚合信息。在圖中，這種機(jī)制能夠?qū)?jié)點(diǎn)產(chǎn)生有用的特征表示?！?/span>

GCN是基于圖機(jī)器學(xué)習(xí)的非常強(qiáng)大的神經(jīng)網(wǎng)絡(luò)體系結(jié)構(gòu)。

實(shí)際上，它們是如此強(qiáng)大，以至于隨機(jī)發(fā)起的2層GCN都可以產(chǎn)生網(wǎng)絡(luò)中節(jié)點(diǎn)的有用特征表示。

下圖說明了由此類GCN生成的網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的二維表示。請(qǐng)注意，即使沒有任何訓(xùn)練，網(wǎng)絡(luò)中節(jié)點(diǎn)的相對(duì)接近度仍保留在二維表示中。

更正式地說，圖卷積網(wǎng)絡(luò)（GCN）是在圖上運(yùn)行的神經(jīng)網(wǎng)絡(luò)。給定圖G =（V，E），V表示節(jié)點(diǎn)，E表示邊，則GCN作為輸入

輸入特征矩陣X（N×F?），其中N是節(jié)點(diǎn)數(shù)，F(xiàn)?是每個(gè)節(jié)點(diǎn)的輸入特征數(shù)，以及圖結(jié)構(gòu)的N×N矩陣表示形式，例如G的鄰接矩陣A

因此，GCN中的隱藏層可以寫成H?= f（H??1，A））。

其中H?= X，f是傳播（propagation）方式。每一層H?對(duì)應(yīng)于一個(gè)N×Fi特征矩陣，其中每一行是一個(gè)節(jié)點(diǎn)的特征表示。在每一層，使用傳播規(guī)則f聚合這些特征，以形成下一層的特征。這樣，特征在連續(xù)層上變得越來越抽象。在此框架中，GCN的變體僅在傳播規(guī)則f的選擇上有所不同。

一個(gè)簡(jiǎn)單的傳播規(guī)則

傳播規(guī)則中最簡(jiǎn)單的一種是：

f（H?，A）=σ（AH?W?）

其中W?是第i層的權(quán)重矩陣，而σ是非線性激活函數(shù)，例如ReLU函數(shù)。權(quán)重矩陣的尺寸為F?×F??1；換句話說，權(quán)重矩陣的第二維的大小確定了下一層的特征數(shù)量。如果你熟悉卷積神經(jīng)網(wǎng)絡(luò)，則此操作類似于過濾操作（filtering operation），因?yàn)檫@些權(quán)重在圖中的節(jié)點(diǎn)之間共享。

簡(jiǎn)化

讓我們從最簡(jiǎn)單的角度檢查傳播規(guī)則：

i = 1，滿足 f是輸入特征矩陣的函數(shù)

σ是恒等函數(shù)

選擇權(quán)重 AH?W?=AXW?= AX

換句話說，f（X，A）= AX。這個(gè)傳播規(guī)則可能有點(diǎn)太簡(jiǎn)單了，稍后我們會(huì)添加缺失的部分。AX現(xiàn)在等效于多層感知器的輸入層。

一個(gè)簡(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

）

接下來，根據(jù)其索引為每個(gè)節(jié)點(diǎn)生成2個(gè)整數(shù)特征，便于以后手動(dòng)確認(rèn)矩陣計(jì)算。

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.］

］）

應(yīng)用傳播規(guī)則

好吧！現(xiàn)在，我們有了一個(gè)圖形，其鄰接矩陣A和一組輸入要素X。讓我們看看應(yīng)用傳播規(guī)則時(shí)會(huì)發(fā)生什么：

In ［6］： A * X

Out［6］： matrix（［

［ 1.， -1.］，

［ 5.， -5.］，

［ 1.， -1.］，

［ 2.， -2.］］

發(fā)生了什么？現(xiàn)在，每個(gè)節(jié)點(diǎn)（每行）的表示形式都是其鄰居特征的總和！換句話說，圖卷積層將每個(gè)節(jié)點(diǎn)表示為其鄰居的集合。注意，在這種情況下，如果存在從v到n的邊，則節(jié)點(diǎn)n是節(jié)點(diǎn)v的鄰居。

問題

你可能已經(jīng)發(fā)現(xiàn)了問題：

節(jié)點(diǎn)的匯總表示不包括其自身的功能！

該表示是鄰居節(jié)點(diǎn)特征的集合，因此只有具有自環(huán)的節(jié)點(diǎn)才會(huì)在集合中包括自己的特征。度數(shù)較大的節(jié)點(diǎn)的特征將具有較大的值，而度數(shù)較小的節(jié)點(diǎn)將具有較小的值。這可能會(huì)導(dǎo)致梯度消失或爆炸，但對(duì)于隨機(jī)梯度下降算法（通常用于訓(xùn)練此類網(wǎng)絡(luò)并且對(duì)每個(gè)輸入特征的比例（或值的范圍）敏感）也存在問題。在下文中，我將分別討論每個(gè)問題。

添加自環(huán)

為了解決第一個(gè)問題，可以簡(jiǎn)單地向每個(gè)節(jié)點(diǎn)添加一個(gè)自環(huán)。實(shí)際上，這是通過在應(yīng)用傳播規(guī)則之前將單位矩陣I與鄰接矩陣A相加來完成的。

In ［4］： I = np.matrix（np.eye（A.shape［0］））

IOut［4］： matrix（［

［1.， 0.， 0.， 0.］，

［0.， 1.， 0.， 0.］，

［0.， 0.， 1.， 0.］，

［0.， 0.， 0.， 1.］

］）

In ［8］： A_hat = A + I

A_hat * X

Out［8］： matrix（［

［ 1.， -1.］，

［ 6.， -6.］，

［ 3.， -3.］，

［ 5.， -5.］］）

由于該節(jié)點(diǎn)現(xiàn)在是其自身的鄰居，因此在總結(jié)其鄰居的特征時(shí)會(huì)包括該節(jié)點(diǎn)自己的特征！

規(guī)范特征表示

通過將鄰接矩陣A與D的逆矩陣相乘來變換鄰接矩陣A，可以按節(jié)點(diǎn)度對(duì)特征表示進(jìn)行歸一化。因此，我們簡(jiǎn)化的傳播規(guī)則如下所示：

f（X，A）=D?1AX

讓我們看看發(fā)生了什么。我們首先計(jì)算度矩陣。

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)行轉(zhuǎn)換后會(huì)發(fā)生什么。

Berfore

A = np.matrix（［

［0， 1， 0， 0］，

［0， 0， 1， 1］，

［0， 1， 0， 0］，

［1， 0， 1， 0］］，

dtype=float

）

After

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. ］

］）

請(qǐng)注意，鄰接矩陣每一行中的權(quán)重（值）已除以與該行相對(duì)應(yīng)的節(jié)點(diǎn)的度。我們將傳播規(guī)則與變換后的鄰接矩陣一起應(yīng)用：

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)椋ㄞD(zhuǎn)換后的）鄰接矩陣權(quán)重，與相鄰節(jié)點(diǎn)特征加權(quán)和的權(quán)重相對(duì)應(yīng)。我鼓勵(lì)你自己驗(yàn)證此觀察。

放在一起

現(xiàn)在，我們結(jié)合了自循環(huán)和標(biāo)準(zhǔn)化技巧。此外，我們將重新介紹先前為簡(jiǎn)化討論而丟棄的權(quán)重和激活函數(shù)。

加重權(quán)重

首要任務(wù)是應(yīng)用權(quán)重。請(qǐng)注意，這里D_hat是A_hat = A + I的度矩陣，即具有強(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.］

］）

如果我們想減小輸出特征表示的維數(shù)，可以減小權(quán)重矩陣W的大?。?/p>

In ［46］： W = np.matrix（［

［1］，

［-1］

］）

D_hat**-1 * A_hat * X * W

Out［46］： matrix（［［1.］，

［4.］，

［2.］，

添加激活功能

我們選擇保留特征表示的維數(shù)并應(yīng)用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.］］）

瞧！具有鄰接矩陣，輸入函數(shù)，權(quán)重和激活功能的完整隱藏層！

簡(jiǎn)單樣例

最后，我們可以在真實(shí)圖上應(yīng)用圖卷積網(wǎng)絡(luò)。我將向你展示如何產(chǎn)生我們?cè)谖恼麻_頭看到的要素表示。

扎卡里的空手道俱樂部

扎卡里（Zachary）的空手道俱樂部是一種常用的社交網(wǎng)絡(luò)，其中節(jié)點(diǎn)代表空手道俱樂部的成員，其邊緣相互聯(lián)系。當(dāng)扎卡里（Zachary）研究空手道俱樂部時(shí)，管理者與教練之間發(fā)生了沖突，導(dǎo)致俱樂部分裂為兩部分。下圖顯示了網(wǎng)絡(luò)的圖形表示，并且根據(jù)俱樂部的哪個(gè)部分標(biāo)記了節(jié)點(diǎn)。管理員和講師分別標(biāo)有“ A”和“ I”。

建立GCN

現(xiàn)在來建立圖卷積網(wǎng)絡(luò)。實(shí)際上我們不會(huì)訓(xùn)練網(wǎng)絡(luò)，只是簡(jiǎn)單地隨機(jī)初始化，以產(chǎn)生在本文開頭看到的功能表示。我們將使用圖網(wǎng)絡(luò)networkx表示整個(gè)圖，并計(jì)算A_hat和D_hat矩陣。

from networkx import karate_club_graph， to_numpy_matrixzkc = 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））

接下來，我們隨機(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））

堆疊GCN層：在這里，我們僅使用單位矩陣作為特征表示，即，每個(gè)節(jié)點(diǎn)都表示為單次熱編碼的分類變量。

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ū)分隔開來。而且我們還沒有開始訓(xùn)練！

對(duì)于此示例，由于ReLU函數(shù)的作用，隨機(jī)初始化的權(quán)重很有可能在x軸或y軸上給出0值，因此需要進(jìn)行幾次隨機(jī)初始化才能產(chǎn)生上圖。

結(jié)論在這篇文章中，我對(duì)圖卷積網(wǎng)絡(luò)進(jìn)行了高級(jí)介紹，并說明了GCN中每一層節(jié)點(diǎn)的特征表示是如何基于其鄰域聚合而得出的。我們了解了如何使用numpy構(gòu)建這些網(wǎng)絡(luò)以及它們的強(qiáng)大功能：即使是隨機(jī)初始化的GCN，也可以在Zachary的空手道俱樂部中分離社區(qū)。

編輯：lyn