摘要：圖神經(jīng)網(wǎng)絡(luò)，GCN
圖數(shù)據(jù)的特征性質(zhì)
圖像數(shù)據(jù)是一種特殊的圖數(shù)據(jù)苦酱，圖像數(shù)據(jù)是標(biāo)準(zhǔn)的2D網(wǎng)格結(jié)構(gòu)圖數(shù)據(jù)踢关。圖像數(shù)據(jù)的CNN卷積神經(jīng)網(wǎng)絡(luò)算法不能直接用在圖數(shù)據(jù)上咐鹤，原因是圖數(shù)據(jù)具有以下特殊性
- 節(jié)點(diǎn)分布不均勻：圖像數(shù)據(jù)及網(wǎng)格數(shù)據(jù)誒個(gè)節(jié)點(diǎn)只有4個(gè)鄰接點(diǎn)，因此可以定義均勻的卷積操作侨核，但是圖數(shù)據(jù)節(jié)點(diǎn)的度數(shù)可以任意變化草穆，即鄰節(jié)點(diǎn)不確定，因此無(wú)法直接卷積搓译。
- 排列不變性：排列不變性（置換不變性）表示輸入的順序改變不會(huì)導(dǎo)致函數(shù)結(jié)果的變化（例如函數(shù)f(x, y, z) = x × y × z）悲柱。圖數(shù)據(jù)具有排列不變性，即在空間中改變圖中節(jié)點(diǎn)（對(duì)圖進(jìn)行折疊扭曲）的位置對(duì)最后的圖關(guān)系沒有影響些己，而圖像數(shù)據(jù)只有變更了兩個(gè)像素的位置整個(gè)圖像的表達(dá)會(huì)發(fā)生變化豌鸡，因此無(wú)法使用卷積，因?yàn)榫矸e的方式不符合排列不變性段标。
- 節(jié)點(diǎn)的額外屬性：圖數(shù)據(jù)的每個(gè)節(jié)點(diǎn)具有自身的屬性涯冠，即每個(gè)節(jié)點(diǎn)都具有自身的特征向量，相比如圖像數(shù)據(jù)中的三通道表達(dá)更加豐富怀樟。
- 邊的額外屬性：圖中的節(jié)點(diǎn)可以擁有權(quán)重和類型功偿，在圖像網(wǎng)格數(shù)據(jù)中邊沒有任何屬性或者權(quán)重，CNN卷積神經(jīng)網(wǎng)絡(luò)也沒有而已處理邊的機(jī)制。
GCN的目的和與CNN的聯(lián)系
GCN要解決的是不規(guī)則的圖結(jié)構(gòu)數(shù)據(jù)的通用的特征提取方案械荷，考慮節(jié)點(diǎn)自身的屬性以及節(jié)點(diǎn)的鄰接節(jié)點(diǎn)屬性獲得節(jié)點(diǎn)的特征向量共耍，最終實(shí)現(xiàn)圖節(jié)點(diǎn)分類，回歸等任務(wù)吨瞎。GCN和CNN一樣都是對(duì)節(jié)點(diǎn)/像素的周邊節(jié)點(diǎn)/像素進(jìn)行加權(quán)求和套激活函數(shù)作為特征提取痹兜，經(jīng)過(guò)多輪特征提取之后最后被一層套類似softmax函數(shù)實(shí)現(xiàn)分類。
圖知識(shí)準(zhǔn)備
（1）鄰接矩陣
圖的結(jié)構(gòu)表示使用鄰接矩陣（用A表示）進(jìn)行表達(dá)颤诀，鄰接矩陣就是統(tǒng)計(jì)Vij（V代表節(jié)點(diǎn)字旭，ij代表從Vi->Vj）的連接權(quán)重，如果不考慮權(quán)重兩個(gè)相連的節(jié)點(diǎn)的Vij值等于1崖叫，不相連的為0構(gòu)成鄰接矩陣遗淳，鄰接矩陣是上下三角對(duì)稱的。
（2）度矩陣
度矩陣（用D表示）是由節(jié)點(diǎn)的度構(gòu)成的矩陣心傀，度矩陣是對(duì)角陣屈暗，對(duì)角線上記錄了各節(jié)點(diǎn)的度值，即Dii為節(jié)點(diǎn)i的度值脂男，在無(wú)向圖的情況下節(jié)點(diǎn)的度值是相連的邊的數(shù)量养叛，如上圖度矩陣如下：
（3）矩陣的逆
設(shè)A是一個(gè)n階矩陣，若存在另一個(gè)n階矩陣B宰翅，使得： AB=BA=E 弃甥，E為單位陣，則稱方陣A可逆汁讼，并稱方陣B是A的逆矩陣淆攻。逆矩陣可以使用初等行變換求得，例如求上式的度矩陣掉缺，相當(dāng)于每一行除以該節(jié)點(diǎn)的度卜录。
（4）譜域和空域圖神經(jīng)網(wǎng)絡(luò)
圖神經(jīng)網(wǎng)絡(luò)分為基于譜域的模型和基于空域的模型，GCN起源于譜域模型眶明，但也可以被認(rèn)為是一個(gè)空域的神經(jīng)網(wǎng)絡(luò)艰毒，現(xiàn)在主流的方法都是以空域?yàn)橹鞯腉CN。譜域GCN理論知識(shí)多晦澀難懂搜囱，空域GCN很多套路和傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)比較類似丑瞧。
GCN的輸入輸出
GCN每一次卷積（隱藏層）的輸入是圖的鄰接矩陣A和節(jié)點(diǎn)的特征屬性H（l），輸出是新的節(jié)點(diǎn)特征屬性H（l+1）蜀肘，在初始輸入層特征屬性H（l）就是特征矩陣X绊汹，若圖上有n和節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有d維特征扮宠，則X是一個(gè)n×d的矩陣X西乖，即輸入數(shù)據(jù)。
GCN公式理解
（1）GCN的卷積核表示
以函數(shù)f作為GCN的卷積表達(dá)式，即圖卷積是一個(gè)對(duì)節(jié)點(diǎn)和鄰接節(jié)點(diǎn)的函數(shù)操作获雕，卷積的表達(dá)式如下
圖卷積實(shí)際上是對(duì)
特征屬性和鄰接矩陣的操作薄腻，具體為每一層（或者說(shuō)每一階）卷積下鄰接矩陣和該層的特征屬性、該層權(quán)重相乘届案，再一層套激活函數(shù)庵楷，得到的結(jié)果作為新的特征屬性繼續(xù)循環(huán)操作，其中H0為初始的節(jié)點(diǎn)屬性矩陣楣颠，由n行節(jié)點(diǎn)數(shù)尽纽，d維節(jié)點(diǎn)屬性組成。由這個(gè)公式可知GCN的卷積核在每一層/階是權(quán)重共享童漩，即在同一階下圖上任意一個(gè)節(jié)點(diǎn)對(duì)周邊鄰居加權(quán)求和的權(quán)重表是一樣的弄贿。
（2）鄰居節(jié)點(diǎn)加權(quán)求和的矩陣表達(dá)
A 和 H 的乘積其實(shí)就是把所有的鄰居節(jié)點(diǎn)向量進(jìn)行相加，如下圖所示矫膨，表示A × H
A表示的是鄰接矩陣挎春，H表示的是4個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有一個(gè)5維的特征向量豆拨，將A 和H點(diǎn)乘會(huì)得到右邊矩陣AH的結(jié)果，得到 A×H 之后再和 W訓(xùn)練參數(shù)相乘能庆，最后經(jīng)過(guò)激活函數(shù) σ 就得到下一層4個(gè)節(jié)點(diǎn)的特征向量了施禾。
（3）融入中心節(jié)點(diǎn)自身特征屬性
A×H只獲得了某個(gè)節(jié)點(diǎn)的鄰居信息，而忽略了節(jié)點(diǎn)本身信息搁胆。為了解決這個(gè)問題弥搞，在鄰接矩陣A中將對(duì)角線的值設(shè)為 1，即每個(gè)節(jié)點(diǎn)會(huì)指向自身渠旁，新的卷積公式如下：
（4）節(jié)點(diǎn)向量聚合取平均
在上一步中聚合的結(jié)果由兩部分組成：鄰居屬性加權(quán)求和+中心節(jié)點(diǎn)自身屬性
下一步需要對(duì)加權(quán)求和的結(jié)果
求平均（歸一化）作為最終的這一層下節(jié)點(diǎn)的特征向量值攀例，原因是如果不采取取平均的方式，度多的節(jié)點(diǎn)計(jì)算的特征向量會(huì)變得很大顾腊，度小的節(jié)點(diǎn)特征向量小粤铭，這樣會(huì)改變每個(gè)節(jié)點(diǎn)特征原本的分布，產(chǎn)生一些不可預(yù)測(cè)的問題杂靶，可能會(huì)導(dǎo)致梯度消失或梯度爆炸梆惯，解決的辦法是用度矩陣D的逆矩陣直接點(diǎn)乘（AX+X）
最終的表達(dá)式代表節(jié)點(diǎn)Xi的經(jīng)過(guò)卷積核聚合之后，新的特征向量為每一個(gè)鄰居節(jié)點(diǎn)的特征向量乘以（該鄰居節(jié)點(diǎn)和節(jié)點(diǎn)i的邊權(quán)重 / i節(jié)點(diǎn)的度）吗垮，使用度矩陣的逆剛好是度值的倒數(shù)垛吗，乘起來(lái)正好是（AX+X）的值除以度和自身得到平均值。
（5）對(duì)稱矩陣歸一化
D的逆矩陣乘上鄰接矩陣是一種歸一化手段烁登，實(shí)際上是對(duì)各鄰居節(jié)點(diǎn)的屬性求平均怯屉，這樣有兩個(gè)問題：
-
結(jié)果不是對(duì)稱陣：相乘之后A失去對(duì)稱性，加入D的逆目的是歸一化，但是不能歸一化破壞了整體的對(duì)稱性锨络，影后后面和特征向量赌躺、權(quán)重相乘。對(duì)稱陣元素以主對(duì)角線為對(duì)稱軸對(duì)應(yīng)相等足删，舉例如下
D的逆乘鄰接矩陣 -
聚合沒有考慮節(jié)點(diǎn)權(quán)重：聚合時(shí)各個(gè)鄰居的信息全部取平均聚合寿谴，沒有考慮鄰居節(jié)點(diǎn)自身所處的位置，比如自身的度信息失受，當(dāng)經(jīng)過(guò)多輪卷積提取讶泰，重復(fù)多次聚合循環(huán)之后，存在聚合值異常大的情況拂到，例子如下
平均法的問題
在第一階卷積之后B拿到了自身和周邊的聚合向量痪署，A拿到了B的初始向量，由于A只有B一個(gè)鄰居兄旬，因此分母是2（和B的邊以及自身）狼犯，自身特征和B的特征各占1/2，A在第二階卷積之后领铐，A拿到了B的一階特征向量悯森，此時(shí)B聚合周邊眾多節(jié)點(diǎn)的特征，明顯A和B的周多鄰居沒有連接绪撵，而經(jīng)過(guò)多輪聚合之后這種僅有一個(gè)鄰居且鄰居為眾多節(jié)點(diǎn)的鄰居的情況瓢姻。該節(jié)點(diǎn)計(jì)算失真。解決的方法是引入對(duì)稱矩陣歸一化音诈，對(duì)鄰接矩陣做對(duì)稱歸一化幻碱。
GCN的最終卷積表達(dá) A波浪=A+I，I是單位矩陣
D波浪是A波浪的度矩陣
H是每一層的特征细溅，對(duì)于輸入層的話褥傍，H就是X
σ是非線性激活函數(shù)
該公式將逆拆開左乘D的-1/2右乘D的1/2，近似的歸一化也保持了矩陣對(duì)稱性喇聊。將公式中的對(duì)稱歸一化部分單獨(dú)拿出來(lái)看某個(gè)中心節(jié)點(diǎn)i
在將i的周邊節(jié)點(diǎn)j和自身一起聚合時(shí)恍风，每次都考慮了兩者的度，不論是自身i的度還是鄰居j的度越大誓篱，來(lái)自于它的節(jié)點(diǎn)信息權(quán)重應(yīng)該越辛诟（分母越大），類似
B->A<-C<-[D,E,F]這樣的圖關(guān)系燕鸽，C和B在聚合到A時(shí)都會(huì)和A計(jì)算一次度的根號(hào)下乘積作為分母兄世，C的作用應(yīng)該比B的作用小，因?yàn)镃的度大啊研。
實(shí)際上它的目的是在
它不僅考慮了節(jié)點(diǎn)i對(duì)度御滩，也考慮了鄰接節(jié)點(diǎn)j的度鸥拧，當(dāng)鄰居節(jié)點(diǎn)j度數(shù)較大時(shí)，它在聚合時(shí)貢獻(xiàn)地會(huì)更少削解。
GCN實(shí)際使用
（1）GCN如何完成節(jié)點(diǎn)分類
GCN在對(duì)節(jié)點(diǎn)進(jìn)行聚合富弦、更新、循環(huán)之后氛驮，每個(gè)節(jié)點(diǎn)都會(huì)獲得低維的特征向量表示腕柜，，維度大小和節(jié)點(diǎn)的特征屬性向量長(zhǎng)度一致矫废，相當(dāng)于GCN的結(jié)果是對(duì)是節(jié)點(diǎn)進(jìn)行了embedding
如上圖所示經(jīng)過(guò)幾輪特征提取之后盏缤，每個(gè)節(jié)點(diǎn)的屬性向量從Xn變成了Zn，最后基于Zn特征向量有監(jiān)督地學(xué)習(xí)Yn值蓖扑。即在在embedding結(jié)果之后再套一層全連接softmax即可實(shí)現(xiàn)節(jié)點(diǎn)分類唉铜，公式如下
此公式?jīng)]有帶入歸一化，整體沒有問題律杠。
（2）GCN需要學(xué)習(xí)的參數(shù)
以numpy和networkx實(shí)現(xiàn)一個(gè)案例了解一下模型需要訓(xùn)練的參數(shù)個(gè)數(shù)潭流。通過(guò)networkx導(dǎo)入karate_club_graph數(shù)據(jù)，數(shù)據(jù)包括34個(gè)節(jié)點(diǎn)柜去，節(jié)點(diǎn)帶有club屬性灰嫉，屬性有Mr. Hi和Officer兩種。
import numpy as np
import networkx as nx
from networkx import to_numpy_matrix
import matplotlib.pyplot as plt
zkc = nx.karate_club_graph()
def plot_graph(G):
plt.figure()
pos = nx.spring_layout(G)
edges = G.edges()
nodelist1 = []
nodelist2 = []
for i in range(zkc.number_of_nodes()):
if zkc.nodes[i]['club'] == 'Mr. Hi':
nodelist1.append(i)
else:
nodelist2.append(i)
nx.draw_networkx(G, pos, edges=edges)
nx.draw_networkx_nodes(G, pos, nodelist=nodelist1, node_size=300, node_color='r', alpha=0.8)
nx.draw_networkx_nodes(G, pos, nodelist=nodelist2, node_size=300, node_color='b', alpha=0.8)
plot_graph(zkc)
通過(guò)上面可視化的方法將不同標(biāo)簽的兩類節(jié)點(diǎn)標(biāo)記為兩種顏色
假設(shè)這是一個(gè)節(jié)點(diǎn)分類問題嗓奢，每個(gè)節(jié)點(diǎn)自身帶有特征向量熬甫，預(yù)測(cè)節(jié)點(diǎn)的類型，設(shè)節(jié)點(diǎn)特征向量為一個(gè)34×10的隨機(jī)數(shù)特征向量（34個(gè)節(jié)點(diǎn)蔓罚，10維特征）
feature_num = 10
X = np.random.normal(loc=0, scale=1, size=(zkc.number_of_nodes(), feature_num)) # 10個(gè)特征
基于GCN的原理，圖的鄰接矩陣和逆矩陣是確定的瞻颂，調(diào)用networkx的to_numpy_matrix得到鄰接矩陣
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))
在不考慮對(duì)稱歸一化的情況下豺谈，每輪卷積操作就是relu(DAXW)，下面先定義relu激活函數(shù)計(jì)算
def relu(x):
return (abs(x) + x) / 2
relu的激活函數(shù)圖像如下
接下來(lái)設(shè)置權(quán)重W贡这，設(shè)置兩層W使用卷積提取兩次
W_1 = np.random.normal(loc=0, scale=1, size=(feature_num, 4))
W_2 = np.random.normal(loc=0, size=(4, 2))
第一層W1承接DAX茬末，DAX的列等于X的feature數(shù)，因此輸入維度是feature_num盖矫，輸出維度自定義為4丽惭，第二層W2承接W1，輸入維度是4辈双，輸出維度自定義為2责掏，這下整體打包一個(gè)函數(shù)表示DAXW和激活函數(shù)的操作
def gcn_layer(A_hat, D_hat, X, W):
return relu(D_hat ** -1 * A_hat * X * W)
調(diào)用兩次查看2層卷積之后的計(jì)算結(jié)果
H_1 = gcn_layer(A_hat, D_hat, X, W_1)
H_2 = gcn_layer(A_hat, D_hat, H_1, W_2)
# H_2
matrix([[0.27327855, 0. ],
[0.75371181, 0. ],
[0. , 0. ],
[0.87060424, 0.17736305],
[0. , 0. ],
[0.45686008, 0. ],
[0.41671791, 0.03714612],
[0.826826 , 0. ],
[0. , 0. ],
[0. , 0. ],
[0. , 0. ],
[0. , 0. ],
[0.95007397, 0.530803 ],
[0.42302904, 0. ],
[0. , 0. ],
[0. , 0. ],
[0.82499985, 0.83492651],
[0.6565228 , 0. ],
[0. , 0. ],
[0.13741573, 0. ],
[0. , 0. ],
[0.69028615, 0. ],
[0. , 0. ],
[0. , 0. ],
[0.5668888 , 0.29175253],
[0.27512282, 0. ],
[0. , 0. ],
[0.04185367, 0. ],
[0. , 0. ],
[0. , 0. ],
[0. , 0. ],
[0. , 0. ],
[0. , 0. ],
[0. , 0. ]])
下一步加入最后一層sigmoid
last_layer_w = np.random.normal(loc=0, scale=1, size=(2, 1))
last_layer_b = np.random.normal()
output = sigmoid(H_2 * last_layer_w + last_layer_b)
查看最終輸出
matrix([[0.89480523],
[0.92797 ],
[0.87041837],
[0.93672788],
[0.87041837],
[0.90882886],
[0.90659049],
[0.93208024],
[0.87041837],
[0.87041837],
[0.87041837],
[0.87041837],
[0.944768 ],
[0.90637759],
[0.87041837],
[0.87041837],
[0.9424882 ],
[0.9221511 ],
[0.87041837],
[0.88323198],
[0.87041837],
[0.92421981],
[0.87041837],
[0.87041837],
[0.92107516],
[0.89495514],
[0.87041837],
[0.87444298],
[0.87041837],
[0.87041837],
[0.87041837],
[0.87041837],
[0.87041837],
[0.87041837]])
此時(shí)根據(jù)標(biāo)簽可以計(jì)算loss梯度下降反向求導(dǎo)迭代了∨韧總結(jié)一下計(jì)算過(guò)程中矩陣大小和需要訓(xùn)練的參數(shù)數(shù)量
| 計(jì)算階段 | 矩陣大小 | 訓(xùn)練參數(shù)個(gè)數(shù) | 備注 |
|---|---|---|---|
| D_hat | 34 × 34 | 0 | 鄰接矩陣+自身的度矩陣 |
| A_hat | 34 × 34 | 0 | 鄰接矩陣+自身 |
| D**-1*A | 34 × 34 | 0 | 度逆矩陣*鄰接矩陣 |
| X | 34 × 10 | 0 | 特征向量 |
| D**-1*A*X | 34 × 10 | 0 | 度逆矩陣*鄰接矩陣*特征向量 |
| D**-1*A*X*W1 | 34 × 4 | 10 × 4 | 度逆矩陣*鄰接矩陣*特征向量*W1 |
| D**-1*A*X*W1*W2 | 34 × 2 | 4 × 2 | 度逆矩陣*鄰接矩陣*特征向量*W1* W2 |
| (D*A*X*W1*W2)*w+b | 34 × 1 | 2 + 1 | sigmoid(w(度逆矩陣*鄰接矩陣*特征向量*W1* W2) +b) |
需要訓(xùn)練的參數(shù)有兩層卷積的W换衬，以及最后sigmoid的w+b痰驱，一共有參數(shù)51個(gè)，鄰接矩陣和度矩陣都是確定的瞳浦，隱藏層的H特征向量每一層都更新担映，同一層下共享卷積權(quán)重W。
