作者：鐘陽揚
審校：陳之炎

本文約2500字，建議閱讀5分鐘
本文對圖神經(jīng)網(wǎng)絡(luò)基本概念以及典型的模型做簡要的介紹。

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

基本概念

1.1 圖的基本概念

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

1.2 圖的表示

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

1)鄰接矩陣(Adjacency Matrix)

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

?

2)度矩陣(Degree?Matrix)

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

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

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

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ù)計算領(lǐng)域。在Scarselli論文中典型的圖如圖1所示：

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

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

?

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

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

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

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

基于不動點定理，對于任意初始值，GNN會按照公式(5)收斂到公式(3)描述的解。

經(jīng)典模型

2.1 GCN-開山之作

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

?圖2 ?Thomas N. Kipf等人提出GCN

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

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

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

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

?

來源：

https://www.zhihu.com/question/426784258

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

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

?

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

2.2 GAT?- attention機制

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

?

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

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

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

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

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

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

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

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

???????

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

2.3 GraphSAGE?-歸納式學習框架

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

?

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

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

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

?

圖6?GraphSAGE的傳播方法

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

直觀一點，可以看看下面這幅圖：

?圖7?圖節(jié)點的傳播方式

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

結(jié)論

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

參考文獻

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

作者簡介

鐘陽揚，數(shù)據(jù)派研究部志愿者，碩士畢業(yè)于東北大學，主要研究方向為計算機視覺、圖神經(jīng)網(wǎng)絡(luò)等。

編輯：于騰凱

校對：林亦霖

數(shù)據(jù)派研究部介紹

數(shù)據(jù)派研究部成立于2017年初，以興趣為核心劃分多個組別，各組既遵循研究部整體的知識分享和實踐項目規(guī)劃，又各具特色：

算法模型組：積極組隊參加kaggle等比賽，原創(chuàng)手把手教系列文章；

調(diào)研分析組：通過專訪等方式調(diào)研大數(shù)據(jù)的應(yīng)用，探索數(shù)據(jù)產(chǎn)品之美；

系統(tǒng)平臺組：追蹤大數(shù)據(jù)&人工智能系統(tǒng)平臺技術(shù)前沿，對話專家；

自然語言處理組：重于實踐，積極參加比賽及策劃各類文本分析項目；

制造業(yè)大數(shù)據(jù)組：秉工業(yè)強國之夢，產(chǎn)學研政結(jié)合，挖掘數(shù)據(jù)價值；

數(shù)據(jù)可視化組：將信息與藝術(shù)融合，探索數(shù)據(jù)之美，學用可視化講故事；

網(wǎng)絡(luò)爬蟲組：爬取網(wǎng)絡(luò)信息，配合其他各組開發(fā)創(chuàng)意項目。

點擊文末“閱讀原文”，報名數(shù)據(jù)派研究部志愿者，總有一組適合你~

轉(zhuǎn)載須知

如需轉(zhuǎn)載，請在開篇顯著位置注明作者和出處（轉(zhuǎn)自：數(shù)據(jù)派THUID：DatapiTHU），并在文章結(jié)尾放置數(shù)據(jù)派醒目二維碼。有原創(chuàng)標識文章，請發(fā)送【文章名稱-待授權(quán)公眾號名稱及ID】至聯(lián)系郵箱，申請白名單授權(quán)并按要求編輯。

未經(jīng)許可的轉(zhuǎn)載以及改編者，我們將依法追究其法律責任。

點擊“閱讀原文”加入組織~