原創(chuàng) | 一文讀懂圖神經(jīng)網(wǎng)絡(luò)

圖(Graph)是一種數(shù)據(jù)結(jié)構(gòu), 能夠很自然地建模現(xiàn)實(shí)場(chǎng)景中一組實(shí)體之間的復(fù)雜關(guān)系。在真實(shí)世界中，很多數(shù)據(jù)往往以圖的形式出現(xiàn), 例如社交網(wǎng)絡(luò)、電商購(gòu)物、蛋白質(zhì)相互作用關(guān)系等。因此，近些年來(lái)使用智能化方式來(lái)建模分析圖結(jié)構(gòu)的研究越來(lái)越受到關(guān)注, 其中基于深度學(xué)習(xí)的圖建模方法的圖神經(jīng)網(wǎng)絡(luò)(Graph Neural Network, GNN), 因其出色的性能已廣泛應(yīng)用于社會(huì)科學(xué)、自然科學(xué)等多個(gè)領(lǐng)域。

基本概念

1.1 圖的基本概念

通常使用G=(V, E)來(lái)表示圖，其中V表示節(jié)點(diǎn)的集合、E表示邊的集合。對(duì)于兩個(gè)相鄰節(jié)點(diǎn)u, v, 使用e=(u,v)表示這兩個(gè)節(jié)點(diǎn)之間的邊。兩個(gè)節(jié)點(diǎn)之間邊既可能是有向，也可能無(wú)向。若有向，則稱之有向圖(Directed Graph), 反之，稱之為無(wú)向圖(Undirected Graph)。

1.2 圖的表示

在圖神經(jīng)網(wǎng)絡(luò)中，常見(jiàn)的表示方法有鄰接矩陣、度矩陣、拉普拉斯矩陣等。

1)鄰接矩陣(Adjacency Matrix)

用于表示圖中節(jié)點(diǎn)之間的關(guān)系，對(duì)于n個(gè)節(jié)點(diǎn)的簡(jiǎn)單圖，有鄰接矩陣:

2)度矩陣(Degree Matrix)

節(jié)點(diǎn)的度(Degree)表示與該節(jié)點(diǎn)相連的邊的個(gè)數(shù)，記作d(v)。對(duì)于n個(gè)節(jié)點(diǎn)的簡(jiǎn)單圖G=(V, E)，其度矩陣D為，也是一個(gè)對(duì)角矩陣。

3）拉普拉斯矩陣 (Laplacian Matrix)

對(duì)于n個(gè)節(jié)點(diǎn)的簡(jiǎn)單圖G=(V, E)，其拉普拉斯矩陣定義為L(zhǎng)=D-A，其中D、A為上面提到過(guò)的度矩陣和鄰接矩陣. 將其歸一化后有 。

1.3 圖神經(jīng)網(wǎng)絡(luò)基本概念

圖神經(jīng)網(wǎng)絡(luò)(GNN)最早由Marco Gori [1]、Franco Scarselli [2,3]等人提出，他們將神經(jīng)網(wǎng)絡(luò)方法拓展到了圖數(shù)據(jù)計(jì)算領(lǐng)域。在Scarselli論文中典型的圖如圖1所示：

 圖1 典型的圖神經(jīng)網(wǎng)絡(luò)

為了根據(jù)輸入節(jié)點(diǎn)鄰居信息更新節(jié)點(diǎn)狀態(tài)，將局部轉(zhuǎn)移函數(shù)f定義為循環(huán)遞歸函數(shù)的形式, 每個(gè)節(jié)點(diǎn)以周圍鄰居節(jié)點(diǎn)和相連的邊作為來(lái)源信息來(lái)更新自身的表達(dá)h。為了得到節(jié)點(diǎn)的輸出o, 引入局部輸出函數(shù)g。因此，有以下定義：

其中x表示節(jié)點(diǎn)投中, h表示節(jié)點(diǎn)隱狀態(tài)，ne[n]表示表示節(jié)點(diǎn)n的鄰居節(jié)點(diǎn)集合，co[n]表示節(jié)點(diǎn)n的鄰接邊的集合。以圖1的L1節(jié)點(diǎn)為例，X1是其輸入特征,包含節(jié)點(diǎn) , 包含邊。

將所有局部轉(zhuǎn)移函數(shù)f堆疊起來(lái), 有：

其中F是全局轉(zhuǎn)移函數(shù)(Global Transition Function), G是全局輸出函數(shù)(Global Output Function)。

根據(jù)巴拿赫不動(dòng)點(diǎn)定理[4]，假設(shè)公式(3)的F是壓縮映射，那么不動(dòng)點(diǎn)H的值就可以唯一確定，根據(jù)以下方式迭代求解:

基于不動(dòng)點(diǎn)定理，對(duì)于任意初始值，GNN會(huì)按照公式(5)收斂到公式(3)描述的解。

經(jīng)典模型

2.1 GCN-開(kāi)山之作

2017年，Thomas N. Kipf等人提出GCN[5]. 其結(jié)構(gòu)如圖2所示：

 圖2  Thomas N. Kipf等人提出GCN

假設(shè)需要構(gòu)造一個(gè)兩層的GCN，激活函數(shù)分別采用ReLU和Softmax，則整體的正向傳播的公式如下所示：

其中W0表示第一層的權(quán)重矩陣，W1表示第二層的權(quán)重矩陣，X為節(jié)點(diǎn)特征，等于鄰接矩陣A和單位矩陣相加，為的度矩陣。

從上面的正向傳播公式和示意圖來(lái)看，GCN好像跟基礎(chǔ)GNN沒(méi)什么區(qū)別。接下里給出GCN的傳遞公式(8)：

觀察一下歸一化的矩陣與特征向量矩陣的乘積：

來(lái)源：https://www.zhihu.com/question/426784258

可以發(fā)現(xiàn)，GCN引入度矩陣D用于對(duì)鄰接矩陣的歸一化后，層間傳播將不再單單地對(duì)領(lǐng)域節(jié)特征點(diǎn)取平均，它不僅考慮了節(jié)點(diǎn)i對(duì)度，也考慮了鄰接節(jié)點(diǎn)j的度，對(duì)于度數(shù)較大的節(jié)點(diǎn)，它在聚合時(shí)貢獻(xiàn)地會(huì)更少。

文章[5]通過(guò)實(shí)驗(yàn)證明GCN性能出色，GCN即使不訓(xùn)練，提取出來(lái)的特征已經(jīng)非常優(yōu)秀,作者做了一個(gè)實(shí)驗(yàn)，使用俱樂(lè)部關(guān)系網(wǎng)絡(luò)數(shù)據(jù)，如圖3所示：

圖3  GCN在空間上自動(dòng)聚類從上圖可以發(fā)現(xiàn)，使用隨機(jī)初始化的GCN進(jìn)行特征提取，經(jīng)過(guò)GCN的提取出的embedding，已經(jīng)在空間上自動(dòng)聚類了。

2.2 GAT - attention機(jī)制

GAT[6]是典型的基于注意力機(jī)制的圖神經(jīng)網(wǎng)絡(luò)。圖注意網(wǎng)絡(luò)結(jié)構(gòu)如圖4所示,節(jié)點(diǎn)i，j的特征作為輸出，計(jì)算兩節(jié)點(diǎn)之間的注意力權(quán)重。

圖4 圖注意網(wǎng)絡(luò)結(jié)構(gòu)

對(duì)于節(jié)點(diǎn)i,j 的注意力系數(shù)（Attention Coefficients）計(jì)算方式為：

其中W是一個(gè)共享參數(shù)的線性映射對(duì)于節(jié)點(diǎn)特征的增維，h就是節(jié)點(diǎn)的特征，a(W，W)可以表示兩個(gè)向量?jī)?nèi)積計(jì)算相似度。再經(jīng)過(guò)softmax得到注意力權(quán)重：

那么有如下注意力權(quán)重計(jì)算公式：

其中Ni表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)，||表示特征拼接。

最終節(jié)點(diǎn)的輸出如下公式所示，很好理解，就是給鄰居節(jié)點(diǎn)分配不同的權(quán)重來(lái)聚合信息。

在文章[6]中，作者還引入了多頭注意力，結(jié)構(gòu)如圖5所示，公式如（13）所示：

 圖5 多頭注意力機(jī)制結(jié)構(gòu)

多頭注意力本質(zhì)是引入并行的幾個(gè)獨(dú)立的注意力機(jī)制，可以提取信息中的多重含義，防止過(guò)擬合。

2.3 GraphSAGE -歸納式學(xué)習(xí)框架

提到GraphSAGE[7]模型, 不得不又提到GCN，我們回顧一下GCN的迭代公式：

圖中紅框位置所做的操作可以簡(jiǎn)單理解為對(duì)鄰接矩陣A的歸一化變換，去掉該部分會(huì)發(fā)現(xiàn)剩下的結(jié)構(gòu)等同于深度神經(jīng)網(wǎng)絡(luò)，加上紅色部分后，通過(guò)矩陣乘法實(shí)際上所做的就是將節(jié)點(diǎn)與節(jié)點(diǎn)相鄰節(jié)點(diǎn)特征信息進(jìn)行相加。

GraphSAGE在特征聚合方式上與GCN簡(jiǎn)單相加不同，GraphSAGE支持max-pooling、LSTM、mean等聚合方式。另外，GraphSAGE與GCN的最大不同點(diǎn)在于，GCN是直推式方法，即所有節(jié)點(diǎn)都在圖中，對(duì)于新出現(xiàn)的節(jié)點(diǎn)無(wú)法處理。GraphSAGE是歸納式，對(duì)于沒(méi)見(jiàn)過(guò)的節(jié)點(diǎn)也能生成embedding。

GraphSAGE的傳播方法如圖6所示：

圖6 GraphSAGE的傳播方法

可以看到對(duì)于圖G中的某個(gè)節(jié)點(diǎn)v，需要聚合k層信息，那么先有個(gè)對(duì)層數(shù)遍歷的for循環(huán)，第二層循環(huán)便是遍歷節(jié)點(diǎn)v的鄰居節(jié)點(diǎn)，然后通過(guò)聚合函數(shù)AGGEGATE(可以是mean、max、LSTM或者其他)來(lái)聚合k-1層的鄰居節(jié)點(diǎn)信息，得到聚合后的k層鄰居節(jié)點(diǎn)信息，然后將聚合后的k層鄰居節(jié)點(diǎn)信息與k-1層節(jié)點(diǎn)v的信息進(jìn)行拼接，然后通過(guò)權(quán)重參數(shù)W進(jìn)行計(jì)算得到K層關(guān)于節(jié)點(diǎn)v的信息。

直觀一點(diǎn)，可以看看下面這幅圖：

 圖7 圖節(jié)點(diǎn)的傳播方式

以為紅色節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)，在一次步驟中，對(duì)紅色節(jié)點(diǎn)的一階鄰居和二階段鄰居做隨機(jī)采樣。然后通過(guò)聚合策略，把節(jié)點(diǎn)的特征信息從二階鄰居聚合到目標(biāo)節(jié)點(diǎn)上，然后用更新后的目標(biāo)節(jié)點(diǎn)的表征可以應(yīng)用到不同需求的任務(wù)上。

結(jié)論

綜上所述，GraphSAGE相對(duì)于GCN可以避免需要一次性加載整張網(wǎng)絡(luò)、能夠靈活設(shè)計(jì)聚合方式、具備Transductive性質(zhì)。可以適配測(cè)試集的節(jié)點(diǎn)變化，不需要像GCN一樣會(huì)因?yàn)楣?jié)點(diǎn)變化造成拉普拉斯矩陣變化導(dǎo)致需要重新訓(xùn)練模型。

參考文獻(xiàn)[1] M. Gori, G. Monfardini and F. Scarselli, "A new model for learning in graph domains," Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., 2005, pp. 729-734 vol. 2, doi: 10.1109/IJCNN.2005.1555942.[2] Scarselli F , Tsoi A C ,  Gori M , et al. Graphical-Based Learning Environments for Pattern Recognition[J]. DBLP, 2004.[3]Franco,Scarselli,Marco,Gori,AhChung,Tsoi,Markus,Hagenbuchner,Gabriele,Monfardini.The graph neural network model.[J].IEEE transactions on neural networks,2009,20(1):61-80.DOI:10.1109/TNN.2008.2005605.[4]MA Khamsi, WA Kirk. An Introduction to Metric Spaces and Fixed Point Theory. 2011.[5] Kipf T N , Welling M . Semi-Supervised Classification with Graph Convolutional Networks[J].  2016.[6] Velikovi P , Cucurull G ,  Casanova A , et al. Graph Attention Networks[J].  2017.[7] W. Hamilton, Z. Ying and J. Leskovec, "Inductive representation learning on large graphs" in Advances in Neural Information Processing Systems, pp. 1025-1035, 2017.