李甜甜，張榮梅，張佳慧

(河北經(jīng)貿(mào)大學(xué) 信息技術(shù)學(xué)院，河北 石家莊 050061)

0 引言

近年來，深度學(xué)習(xí)技術(shù)在諸多領(lǐng)域，如圖像處理，自然語言理解等領(lǐng)域廣泛應(yīng)用，主要用于處理圖像、語音、文本等形式的歐幾里得數(shù)據(jù)。但一直以來深度學(xué)習(xí)技術(shù)對于非結(jié)構(gòu)化的圖數(shù)據(jù)難以高效處理。而作為一類主要描述關(guān)系的通用數(shù)據(jù)表示方法，圖能夠很自然地表示出現(xiàn)實場景中實體與實體之間復(fù)雜的關(guān)系，在產(chǎn)業(yè)界有著更加廣闊的應(yīng)用場景，例如在社交網(wǎng)絡(luò)、物聯(lián)網(wǎng)等場景中數(shù)據(jù)多以圖的形式出現(xiàn)。受到深度學(xué)習(xí)技術(shù)的啟發(fā)，2005年Marco Gori等人首次將深度學(xué)習(xí)技術(shù)與圖數(shù)據(jù)結(jié)合，提出了圖神經(jīng)網(wǎng)絡(luò)(Graph Neural Networks, GNN)的概念，使深度學(xué)習(xí)能夠在圖數(shù)據(jù)的相關(guān)場景中得到有效利用。GNN的應(yīng)用領(lǐng)域十分廣泛，包括計算機視覺、化學(xué)生物、推薦系統(tǒng)以及自然語言處理等領(lǐng)域。

1 圖的定義及表示

1.1 圖的基本概念

圖定義為G=(V,E)，其中V表示節(jié)點集合，E表示邊集合。VR是兩頂點之間關(guān)系的集合，若εVR,則表示從v到w的一條弧，且稱v為弧頭或初始點，w為弧尾或終端點，此時的圖稱為有向圖；若對于任意的εVR必有εVR，即VR是對稱的，則以無序?qū)?v,w)代替這兩個有序?qū)Γ硎緑和w之間的一條邊，此時的圖稱為無向圖[1]。如圖1所示，(a)表示無向圖，(b)表示有向圖。

圖1 圖示例

1.2 圖的表示

在圖神經(jīng)網(wǎng)絡(luò)中，常用鄰接矩陣、度矩陣、拉普拉斯矩陣等來表示節(jié)點之間的連接關(guān)系。

(1)鄰接矩陣A:用來表示圖中節(jié)點之間的關(guān)系。若節(jié)點vi和vj之間有邊相連則ai,j=1，否則為0；

圖1的鄰接矩陣、度矩陣以及拉普拉斯矩陣如表1所示。

表1 圖表示

2 深度學(xué)習(xí)的相關(guān)技術(shù)

2.1 卷積

卷積操作是k×k的卷積核以一定的步長在輸入特征圖上遍歷移動；每次移動卷積核就會與輸入特征圖出現(xiàn)重合區(qū)域，重合區(qū)域?qū)?yīng)元素相乘、求和得到輸出特征的一個像素點[4]。卷積的定義如(1)式所示：

(1)

圖2 卷積示例

2.2 池化

池化使用n×n的滑窗，在輸入特征矩陣上滑動，每次將滑動區(qū)域內(nèi)的元素聚合為一個值作為輸出。池化將卷積層得到的特征矩陣作為輸入進行降維以實現(xiàn)減小參數(shù)量的目標(biāo)。根據(jù)聚合方式的不同，池化分為平均池化和最大池化。每個滑窗平均池化后的輸出為輸入矩陣滑動區(qū)域內(nèi)元素的平均值。每個滑窗最大池化后的輸出為輸入矩陣滑動區(qū)域內(nèi)元素的最大值。如圖3所示利用步長為2，2*2的滑窗在4*4的輸入矩陣上最大池化以及平均池化所得結(jié)果。

圖3 池化示意圖

2.3 自編碼器

自編碼器由編碼器與解碼器構(gòu)成，是一種可進行數(shù)據(jù)降維及特征提取的無監(jiān)督學(xué)習(xí)方法；自編碼器模型如圖4所示，分為輸入層、隱藏層及輸出層。其中，Encoder通過編碼函數(shù)h=f(x)將輸入的x編碼得到中間表示h；Decoder通過解碼函數(shù)r=g(h)重構(gòu)中間表示h；自編碼器對于輸入進行重構(gòu)的目的在于能夠讓隱藏表示h獲得數(shù)據(jù)更顯著的特征[5]。

圖4 自編碼器模型

2.4 注意力機制

注意力機制是一種模擬人腦注意力機制的模型，其從大量的輸入信息中選擇對當(dāng)前任務(wù)更為關(guān)鍵的信息，提高任務(wù)執(zhí)行的效率及準(zhǔn)確性[6]。以機器翻譯為例，將輸入序列X(x1,x2,…,xm)利用Encoder-Decoder框架得到目標(biāo)序列Y(y1,y2,…,yn)。Encoder對輸入序列編碼后得到隱藏表示C=F(x1,x2,…,xm)，Decoder利用隱藏表示C及已得到的y1,y2,…,yi-1解碼得到i時刻單詞yi=g(C,y1,y2,…,yi-1)。在未加入注意力機制之前，Encoder-Decoder只能經(jīng)由定長的隱藏表示C實現(xiàn)數(shù)據(jù)的傳輸，若輸入句子較長，會導(dǎo)致信息丟失，翻譯錯誤率提高。引入注意力機制后，編碼器將所有輸出發(fā)送給解碼器，解碼器的記憶單元會計算這些輸出的加權(quán)求和，從而確定在該步長中將重點放在哪一單詞上，從而更好地提升翻譯效果[7]。注意力機制原理如圖5所示。

圖5 注意力機制原理圖

其中，Key為關(guān)鍵字；Value為關(guān)鍵字權(quán)重；Query為給定目標(biāo)序列的一個查詢；F表示相似度函數(shù)。si=F(Q,Ki)表示Keyi與Query間的相似度；ai表示注意力系數(shù)；Attention表示輸出的注意力數(shù)值。計算Attention的階段如下：

(1)利用F(Q,Ki)計算Query與Keyi間的相似度si。

(2)使用softmax函數(shù)對si進行歸一化，得到注意力權(quán)重系數(shù)ai如式(2)所示：

(2)

(3)對ai與Valuei的乘積進行加權(quán)求和即可得到Attention數(shù)值，如式(3)所示：

(3)

Lx代表輸入序列的長度。

3 圖神經(jīng)網(wǎng)絡(luò)模型原理及應(yīng)用

常見的GNN模型有：圖卷積神經(jīng)網(wǎng)絡(luò)、圖注意力網(wǎng)絡(luò)、GraphSAGE以及門控圖神經(jīng)網(wǎng)絡(luò)。

3.1 圖神經(jīng)網(wǎng)絡(luò)

圖神經(jīng)網(wǎng)絡(luò)通過嵌入傳播迭代地聚合目標(biāo)節(jié)點鄰域的信息，通過堆疊多個傳播層獲得高階鄰域信息，更新目標(biāo)節(jié)點表示[8]。以單層嵌入傳播為例，目標(biāo)節(jié)點v計算聚合后的節(jié)點表示如式(4)所示：

(4)

(5)

3.2 圖卷積神經(jīng)網(wǎng)絡(luò)(Graph Convolutional Network)

3.2.1 GCN模型原理

GCN對圖的拓?fù)浣Y(jié)構(gòu)和節(jié)點特征信息進行學(xué)習(xí)，將原始圖數(shù)據(jù)結(jié)構(gòu)G=(V,E)映射到一個新的特征空間中fG→f*，以單層向前傳播圖卷積神經(jīng)網(wǎng)絡(luò)為例，對于圖上的每個節(jié)點vi在計算節(jié)點表示時，每一層神經(jīng)網(wǎng)絡(luò)的輸出H(l+1)都可以用一個非線性函數(shù)表示，如公式(6)所示：

(6)

圖6 GCN模型

3.2.2 GCN模型應(yīng)用

GCN模型應(yīng)用領(lǐng)域有：計算機視覺、生物化學(xué)、推薦系統(tǒng)以及自然語言處理等。常見的數(shù)據(jù)集包括：Cora、Citeseer、shapeNet、ModelNet40、ZINC等。在計算機視覺領(lǐng)域，Wu等人[10]提出一種基于圖卷積網(wǎng)絡(luò)的視頻人物社交關(guān)系圖生成模型HC-GCN，該模型首先將短期的多模態(tài)線索如視頻、音頻及文本等通過圖卷積技術(shù)為人物生成幀級子圖，再沿時間軌跡聚合所有的幀級子圖形成一個全局的社交關(guān)系圖。Wang等人[11]提出了神經(jīng)網(wǎng)絡(luò)模塊EdgeConv，在點云數(shù)據(jù)上使用GCN，在保證置換不變性的同時能夠獲取足夠的局部鄰域信息，經(jīng)過實驗證明，該模型在形狀分類和局部分割任務(wù)上有不錯的效果。在生物化學(xué)領(lǐng)域，Duvenaud等人[12]提出了一種用于學(xué)習(xí)分子指紋的GCN模型，該模型將大小和形狀任意的分子圖作為輸入，通過圖卷積學(xué)習(xí)原子的特征并將其組合為分子指紋，該模型可解釋性強且預(yù)測性能良好。You等人[13]提出了結(jié)合強化學(xué)習(xí)、對抗性訓(xùn)練的圖卷積策略網(wǎng)絡(luò)GCPN，首先利用GCN獲得生成圖狀態(tài)的嵌入，將對抗性損失作為獎勵，最后利用強化學(xué)習(xí)技術(shù)訓(xùn)練目標(biāo)有向圖。該模型通過策略梯度來優(yōu)化特定領(lǐng)域的獎勵和對抗性損失，并在一個包含特定領(lǐng)域規(guī)則的環(huán)境中運行，實驗結(jié)果表明，GCPN在化學(xué)性能優(yōu)化方面比基線方法提高了61%。在推薦系統(tǒng)中，Wang等人[14]提出一種基于圖卷積網(wǎng)絡(luò)的NGCF模型，利用用戶-項目圖結(jié)構(gòu)，通過傳播嵌入顯式建模用戶-項目之間的高階連通性，有效地將用戶和項目嵌入相互交互的協(xié)同信號注入到嵌入過程中，以學(xué)習(xí)更好的用戶和項目表示。He等人[15]提出了LightGCN模型，該模型實現(xiàn)了將用戶嵌入和項目嵌入在用戶-項目交互圖上線性傳播達到學(xué)習(xí)用戶以及項目嵌入的目的，并將在所有層上學(xué)習(xí)的嵌入的加權(quán)和作為最終嵌入。在自然語言處理領(lǐng)域，Yao等人[16]提出將單詞和文檔作為節(jié)點來構(gòu)建語料庫，并用TextGCN學(xué)習(xí)單詞和文檔的嵌入。該模型可以很好地捕獲單詞和文檔之間的關(guān)系，具有很好的文本分類效果。

3.3 圖注意力網(wǎng)絡(luò)(Graph Attention Network)

3.3.1 GAT模型原理

GAT是圖卷積與注意力機制相結(jié)合的網(wǎng)絡(luò)模型，在傳播過程中不再使用拉普拉斯矩陣更新節(jié)點狀態(tài)，而是在每個節(jié)點更新狀態(tài)時引入注意力機制計算其鄰居節(jié)點的重要程度，為每個相鄰節(jié)點分配不同的權(quán)重，關(guān)注作用較大的節(jié)點，提高模型計算的效率[17]。

(7)

eij為節(jié)點i的鄰接點j的重要程度，eij的數(shù)值越大，鄰接點j對于節(jié)點i來說越重要。eij通過softmax函數(shù)進行歸一化操作，使節(jié)點間的注意力系數(shù)容易比較，如式(8)所示：

(8)

圖7 GAT模型注意力機制

(9)

3.3.2GAT模型應(yīng)用

GAT常應(yīng)用領(lǐng)域為推薦系統(tǒng)、生物化學(xué)、文本分類及計算機視覺等。常用的數(shù)據(jù)集有：Decagon、VQA、MR、Amozon-book等。在推薦系統(tǒng)領(lǐng)域，F(xiàn)an等人[18]提出了GraphRec模型，該模型在社交聚合階段使用注意力機制，為用戶不同的社交好友分配不同權(quán)重，選擇更有代表性的社交好友對用戶信息進行表征，從而提升模型性能。Wang等人[19]提出了一種知識圖譜與圖注意力網(wǎng)絡(luò)相結(jié)合的KGAT模型，該模型在鄰域節(jié)點嵌入傳播階段使用注意機制為鄰居節(jié)點分配不同權(quán)重，并利用輔助信息知識圖譜設(shè)計額外的損失優(yōu)化推薦性能。在生物化學(xué)領(lǐng)域，Andreea等人[20]提出了一種基于圖注意力網(wǎng)絡(luò)的模型，其利用藥物的副作用類型和藥物的分子結(jié)構(gòu)，在學(xué)習(xí)每種藥物代表時使用共同注意力機制，使不同的早期整合藥物對聯(lián)合信息的重要程度不同，該模型能夠?qū)崿F(xiàn)對藥物不良反應(yīng)較好的預(yù)測效果。在文本分類領(lǐng)域，Hu等人[21]提出了一種異質(zhì)圖注意力網(wǎng)絡(luò)模型HGAT，通過層次注意力機制，使鄰域內(nèi)不同節(jié)點的重要程度不同，降低噪聲信息，該模型對短文本的分類具有較好的效果。在計算機視覺領(lǐng)域，黨等人[22]提出了一種基于圖注意卷積神經(jīng)網(wǎng)絡(luò)的三維模式識別的方法，在圖注意力卷積層使用多個注意力機制聚合鄰域的特征，豐富聚合特征信息的多樣性。Li等人[23]提出了一種關(guān)系感知圖注意力網(wǎng)絡(luò)模型ReGAT，該模型將輸入的每個數(shù)據(jù)建模成圖的形式，并通過圖注意力機制對多種類型的關(guān)系分配不同的權(quán)重，找到與目標(biāo)最相關(guān)的關(guān)系。Li等人[24]提出了一個基于圖注意力網(wǎng)絡(luò)的模型SIGN，該模型通過圖注意力層整合原子之間的距離和角度信息，交替?zhèn)鞑ス?jié)點和邊的嵌入，進行三維空間結(jié)構(gòu)建模。

3.4 GraphSAGE

3.4.1 GraphSAGE原理

GCN模型利用圖的拓?fù)浣Y(jié)構(gòu)和節(jié)點特征信息學(xué)習(xí)節(jié)點嵌入表示且能夠捕捉圖的全局信息，但是其要求在固定不變的圖上進行學(xué)習(xí)，不能直接泛化到未知的節(jié)點上，當(dāng)圖結(jié)構(gòu)發(fā)生變化或者有新節(jié)點出現(xiàn)時，GCN模型需重新訓(xùn)練，從而會帶來巨大的計算開銷，GraphSAGE(Graph Sample and AggreGatE)將GCNs擴展到歸納的無監(jiān)督學(xué)習(xí)任務(wù)中，能夠利用鄰域節(jié)點的特征信息為未知節(jié)點高效地生成節(jié)點嵌入[25]。其核心思想是如何學(xué)習(xí)一個函數(shù)從目標(biāo)節(jié)點的局部鄰域中聚合這些節(jié)點的特征信息。GraphSAGE模型如圖8所示。

圖8 GraphSAGE模型

第一步通過對目標(biāo)節(jié)點的k階鄰域由高到低逐階隨機采樣獲得目標(biāo)節(jié)點的第k階特征。設(shè)Sk為第k階需采樣鄰居節(jié)點數(shù)目，若目標(biāo)節(jié)點鄰居節(jié)點的數(shù)目小于Sk，則采用有放回抽樣；若目標(biāo)節(jié)點鄰居節(jié)點數(shù)目≥Sk，則采用無放回抽樣。圖8中k=1時Sk=3；k=2時Sk=5。

其次，利用mean/LSTM/pooling聚合器聚合鄰居節(jié)點的特征信息，并采用拼接操作更新目標(biāo)節(jié)點的節(jié)點表示供下游任務(wù)使用。聚合操作由下列公式組成：

(10)

(11)

3.4.2 GraphSAGE應(yīng)用

GraphSAGE模型常應(yīng)用于推薦系統(tǒng)，圖像分類、文本分類及欺詐檢測等領(lǐng)域。其常用的數(shù)據(jù)集有Pinteres、Reddit、Camelyon16。在推薦系統(tǒng)領(lǐng)域，Ying等人[26]提出了基于GraphSAGE的PinSage模型，能夠利用隨機游走的方式并通過圖卷積的方式聚合鄰居節(jié)點的特征信息，實現(xiàn)更新節(jié)點嵌入的同時減小了模型計算成本。該模型在大規(guī)模工業(yè)推薦任務(wù)中具有很好的推薦效果。在圖像分類領(lǐng)域，崔等人[27]提出了一種基于細(xì)胞圖卷積的組織病理圖像分類方法，將高分辨率的病理圖像建模為圖結(jié)構(gòu)，在GraphSAGE模型中加入圖池化，使模型能夠提取出病理圖中更顯著的特征。在欺詐檢測領(lǐng)域，郭等人[28]提出了一種帶權(quán)采樣GraphSAGE模型，該模型的采樣以節(jié)點間的相似度為依據(jù)。經(jīng)實驗表明，該模型準(zhǔn)確率較高并對之前未發(fā)現(xiàn)的兩個作弊團隊進行召回。GraphSAGE在Reddit數(shù)據(jù)集上有很好的論文預(yù)測和文章分類的效果。

3.5 門控圖神經(jīng)網(wǎng)絡(luò)(Gated Graph Sequence Neural Network)

3.5.1 GGNN模型原理

GGNN在圖神經(jīng)網(wǎng)絡(luò)更新節(jié)點表示的步驟中使用了門控循環(huán)單元(gate recurrent unit,GRU)[29]，且節(jié)點表示的更新次數(shù)固定為T，通過門控循環(huán)單元控制網(wǎng)絡(luò)傳播中的節(jié)點表示更新次數(shù)T來迭代循環(huán)的實現(xiàn)門控圖神經(jīng)網(wǎng)絡(luò)。有向圖及其鄰接矩陣示例如圖9所示，圖(a)中為一個示例圖G=(V,E)，其中節(jié)點表示v∈V，邊表示e∈E；(b)代表(a)的鄰接矩陣A，其由輸入邊和輸出邊鄰接矩陣構(gòu)成，B，C，B′，C′是邊的特征。

圖9 有向圖及其鄰接矩陣

門控圖神經(jīng)網(wǎng)絡(luò)的傳播過程主要包括公式(12)-公式(17)所示：

(12)

(13)

(14)

(15)

(16)

(17)

(18)

對于整張圖的輸出如式(19)所示：

(19)

3.5.2GGNN模型的應(yīng)用

門控圖神經(jīng)網(wǎng)絡(luò)主要的應(yīng)用領(lǐng)域為計算機視覺、推薦系統(tǒng)、機器翻譯及預(yù)測化學(xué)反應(yīng)等。其常用的數(shù)據(jù)集有COCO、Gowalla、USPTO。在場景圖生成領(lǐng)域，Damien等人[31]分別對視覺模態(tài)和文本模態(tài)進行圖構(gòu)建，再利用GGNN模型訓(xùn)練兩種模態(tài)的圖結(jié)構(gòu)得到最終嵌入，供預(yù)測任務(wù)中使用，該模型預(yù)測效果較好。干等人[32]提出一種模型將門控圖卷積用于骨架模態(tài)的動作識別中，該模型通過門控時序卷積模塊來提取時域頂點之間的多時期依賴關(guān)系；通過多維注意力機制來增強圖的全局表征。在推薦系統(tǒng)領(lǐng)域，Wu等人[33]提出了一種用于會話推薦的GGNN模型SR-GNN，該模型將輸入的數(shù)據(jù)建模成圖的形式，用門控圖神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)項目節(jié)點的嵌入，該模型相較于其他先進方法有更好的性能。Tao等人[34]利用門控圖神經(jīng)網(wǎng)絡(luò)在項目趨勢表示建模中的作用提高模型的表示能力。在機器翻譯領(lǐng)域，Beck等人[35]在語法可感知神經(jīng)機器翻譯任務(wù)中使用GGNN，通過將邊變成新節(jié)點，將句法依存圖轉(zhuǎn)換成Levi圖，進而將邊的標(biāo)簽表示為嵌入，從而更好地學(xué)習(xí)引入的句法信息。在化學(xué)反應(yīng)預(yù)測領(lǐng)域，John等人[36]將化學(xué)反應(yīng)描述為分子中電子的逐步重新分布，提出一種電子路徑預(yù)測模型。使用四層GGNN表示節(jié)點和圖嵌入，然后優(yōu)化分解路徑的生成概率，用以預(yù)測化學(xué)反應(yīng)產(chǎn)物。

3.6 圖神經(jīng)網(wǎng)絡(luò)的開放資源

基于上述對四種常用GNN模型應(yīng)用的介紹總結(jié)了常用的GNN數(shù)據(jù)集以及GNN庫。常用的數(shù)據(jù)集包括Reddit、Gowalla及Movielens-1M。其經(jīng)常用于推薦任務(wù)。按照模型不同，統(tǒng)計了GCN、GAT、GraphSAGE及GGNN四個圖神經(jīng)網(wǎng)絡(luò)模型主要數(shù)據(jù)集，如表2所示。

表2 開放數(shù)據(jù)集

常用的圖神經(jīng)網(wǎng)絡(luò)庫如下：

(1)Deep Graph Library：支持PyTorch、TensorFlow等多種框架的開源GNN庫，包含消息傳遞機制、自動批處理以及用以提升模型速度的靈活調(diào)整的稀疏矩陣。

(2)PyTorch Geometric是基于PyTorch框架封裝的GNN平臺，其包含了圖數(shù)據(jù)的處理、多種常用的GNN模型及數(shù)據(jù)集等。

(3)TensorFlow Geometric是基于TensorFlow框架的使用消息傳遞機制實現(xiàn)GNN的庫，其內(nèi)置了多種GNN常用的模型及數(shù)據(jù)集，利用稀疏矩陣提升框架性能。

(4)AliGraph是阿里集團開發(fā)的一個大規(guī)模的GNN平臺，致力于數(shù)據(jù)采樣建模及訓(xùn)練一體化。由數(shù)據(jù)層、采樣層、算子層及算法層構(gòu)成，適用于大規(guī)模圖、多種類型的圖。

4 問題與總結(jié)

近年來圖神經(jīng)網(wǎng)絡(luò)已在許多重要領(lǐng)域得到了廣泛應(yīng)用，但是目前圖神經(jīng)網(wǎng)絡(luò)發(fā)展不夠完善，仍然存在一些問題有待解決。

(1)深度神經(jīng)網(wǎng)絡(luò)通過堆疊不同網(wǎng)絡(luò)層使網(wǎng)絡(luò)結(jié)構(gòu)加深，參數(shù)增多，以便提升表達能力[37]。但現(xiàn)有的圖神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)層次較少，例如GCN在參數(shù)較多時會存在過平滑的問題，而限制圖神經(jīng)網(wǎng)絡(luò)的表達能力，因此如何設(shè)計深度的圖神經(jīng)網(wǎng)絡(luò)是未來的一個重要研究方向。

(2)在社交網(wǎng)絡(luò)、推薦系統(tǒng)等應(yīng)用場景，GNN往往需要對大規(guī)模的圖結(jié)構(gòu)數(shù)據(jù)進行處理，而現(xiàn)有的許多GNN還不能滿足處理大規(guī)模圖的需求。GCN在使用拉普拉斯矩陣進行圖卷積計算時需要很高的時間復(fù)雜度及空間復(fù)雜度，并且GraphSAGE、GAT等模型在更新節(jié)點表達時過分依賴大量的鄰域節(jié)點，計算代價過大。目前主要通過快速采樣、子圖訓(xùn)練的方式處理。