圖網(wǎng)絡(luò)層級信息挖掘分類算法綜述

魏文超，藺廣逢，廖開陽，康曉兵，趙凡

西安理工大學(xué)印刷包裝與數(shù)字媒體學(xué)院，西安 710048

0 引 言

深度學(xué)習(xí)(deep learning)作為機器學(xué)習(xí)的一個研究分支發(fā)展迅速(Zhou等，2018)，其將現(xiàn)實世界中的每個概念都表現(xiàn)為更加抽象的概念來定義，并通過神經(jīng)網(wǎng)絡(luò)提取樣本特征。深度學(xué)習(xí)在多領(lǐng)域的成功歸功于計算資源的快速發(fā)展、大量訓(xùn)練數(shù)據(jù)的收集，以及從歐氏數(shù)據(jù)(具有很好的平移不變性(Ali等，1990)的數(shù)據(jù))中提取潛在表征的有效性。例如，卷積神經(jīng)網(wǎng)絡(luò)(convolutional neural network，CNN)(Krizhevsky等，2012)可以利用平移不變性、局部連通性和圖像數(shù)據(jù)語意合成性提取與整個數(shù)據(jù)集共享的局部有意義的特征，用于各種圖像分析任務(wù)。深度神經(jīng)網(wǎng)絡(luò)的最新進展推進了模式識別和數(shù)據(jù)挖掘領(lǐng)域的研究。目標(biāo)檢測、機器翻譯和語音識別等許多機器學(xué)習(xí)任務(wù)曾高度依賴手工特征提取信息特征集合，但多種端到端深度學(xué)習(xí)方式，即卷積神經(jīng)網(wǎng)絡(luò)(Krizhevsky等，2012)、長短期記憶網(wǎng)絡(luò)(long short-term memory，LSTM)(Hochreiter等，1997)和自編碼器(AutoEncoders)(Vincent等，2010)改變了這種狀況。

盡管深度學(xué)習(xí)在歐幾里得數(shù)據(jù)中取得了很大成功，但非歐氏數(shù)據(jù)(不具有平移不變性的數(shù)據(jù))在實際中應(yīng)用更廣泛。例如，在電子商務(wù)領(lǐng)域，一個基于圖的學(xué)習(xí)系統(tǒng)能夠利用用戶與產(chǎn)品之間的交互實現(xiàn)高度精準(zhǔn)的推薦。在化學(xué)領(lǐng)域，分子被建模為圖，新藥研發(fā)需要測定其生物活性。在引文網(wǎng)絡(luò)中，文章之間通過引用關(guān)系互相連接，需要將它們分成不同類別的文獻(Wu等，2021)。

圖卷積神經(jīng)網(wǎng)絡(luò)(graph convolutional network, GCN)為解決圖問題提供了新的思路。借助于卷積神經(jīng)網(wǎng)絡(luò)對局部結(jié)構(gòu)的建模能力及圖上普遍存在的節(jié)點依賴關(guān)系，圖卷積神經(jīng)網(wǎng)絡(luò)將處理歐氏數(shù)據(jù)的卷積神經(jīng)網(wǎng)絡(luò)推廣到建模圖結(jié)構(gòu)數(shù)據(jù)，實現(xiàn)圖卷積，完成了節(jié)點之間的信息聚合。盡管圖卷積網(wǎng)絡(luò)取得了巨大成功，但在節(jié)點分類任務(wù)中，幾乎現(xiàn)有模型都只有兩三層的淺層模型架構(gòu)。傳統(tǒng)的深度學(xué)習(xí)模型在堆疊大量網(wǎng)絡(luò)層后，由于強大的表示能力，在很多問題上了取得了顯著效果。在計算機視覺領(lǐng)域，卷積神經(jīng)網(wǎng)絡(luò)的深度對性能起著至關(guān)重要的作用。Alex等人(2012)提出具有8層卷積層的AlexNet模型；Simonyan等人(2014)提出的VGG(Visual Geometry Group)模型具有19層卷積層；Szegedy等人(2014)提出的GoogLeNet模型具有22層卷積層。更深的深度神經(jīng)網(wǎng)絡(luò)模型能夠得到更大的接收域，從而獲取更多表達信息。受卷積神經(jīng)網(wǎng)絡(luò)的啟發(fā)，深度圖卷積神經(jīng)網(wǎng)絡(luò)模型也期望具有更強的表現(xiàn)力。

但圖卷積神經(jīng)網(wǎng)絡(luò)(GCN)的淺層設(shè)計似乎違反直覺，因為這些模型的深層版本原則上可以獲得更多信息，但實際情況卻性能表現(xiàn)得更差。主要原因在于深層圖結(jié)構(gòu)優(yōu)化的特有難點——過平滑現(xiàn)象(Li等，2018)。一個直觀解釋是圖卷積神經(jīng)網(wǎng)絡(luò)通過重復(fù)應(yīng)用拉普拉斯平滑融合來自不同鄰域的節(jié)點特征，平滑操作使得同一聚類中頂點特征相似，簡化了分類任務(wù)，但當(dāng)層數(shù)加深時，圖中每個節(jié)點的表達傾向于收斂到某一個值，不同聚類中的頂點變得無法區(qū)分。受到過平滑問題限制的淺模型體系結(jié)構(gòu)限制了其從高階鄰域提取知識的能力，也阻礙了節(jié)點分類任務(wù)的進一步發(fā)展。Dehmamy等人(2019)通過圖矩(graph moments)(Bondy等，1976；Lin等，1995)分析GCN在圖拓撲學(xué)習(xí)中的表示能力，表明更深的GCN具有更高能力學(xué)習(xí)更高階的圖矩。Loukas(2019)分析了圖神經(jīng)網(wǎng)絡(luò)的局限性，指出基于消息傳遞框架的圖神經(jīng)網(wǎng)絡(luò)的深度和寬度受到限制時，會失去很大部分的表達能力。

因此，利用圖層級結(jié)構(gòu)至關(guān)重要，以便能夠以有效的方式聚合高階信息來進行更好的預(yù)測。很多研究人員探索圖上的深度學(xué)習(xí)方法并對其綜述，但對更重要的分支——層級結(jié)構(gòu)信息挖掘的研究和應(yīng)用總結(jié)仍存在空白。為此，本文對圖網(wǎng)絡(luò)層級挖掘算法的發(fā)展進行了深入分析和總結(jié)。同時，通過圖卷積神經(jīng)網(wǎng)絡(luò)層級特性實驗，表明現(xiàn)有的層級信息挖掘算法仍然沒有對圖的信息進行完全探索，其分類能力并沒有達到預(yù)期結(jié)果。

本文深入總結(jié)圖網(wǎng)絡(luò)層級信息挖掘算法的發(fā)展及存在的部分問題。貢獻如下：1)針對圖網(wǎng)絡(luò)的層級信息的關(guān)聯(lián)性，按照正則化方法和架構(gòu)調(diào)整方法對現(xiàn)有圖網(wǎng)絡(luò)層級信息挖掘算法進行綜述；2)對圖網(wǎng)絡(luò)層級挖掘算法進行系統(tǒng)分析，為每一類代表性圖網(wǎng)絡(luò)層級信息挖掘算法模型提供詳細說明分析；3)進行圖卷積神經(jīng)網(wǎng)絡(luò)層級特性實驗，表明圖結(jié)構(gòu)中存在層級特性節(jié)點且現(xiàn)有的圖層級信息挖掘算法仍然沒有對圖的信息進行完全探索，現(xiàn)存的圖網(wǎng)絡(luò)層級算法在節(jié)點分類任務(wù)上并沒有達到最好的分類結(jié)果；4)在分析現(xiàn)有方法的基礎(chǔ)上，論述了圖網(wǎng)絡(luò)層級挖掘算法存在的問題，并提出未來可能的研究方向。

1 定義和發(fā)展背景

1.1 符號定義

本文使用的常見符號及這些符號的詳細說明如表1所示。

表1 常見符號定義

1.2 圖卷積神經(jīng)網(wǎng)絡(luò)發(fā)展

按照傳統(tǒng)的卷積神經(jīng)網(wǎng)絡(luò)和循環(huán)神經(jīng)網(wǎng)絡(luò)的定義，標(biāo)準(zhǔn)神經(jīng)網(wǎng)絡(luò)是按特定順序堆疊節(jié)點特征進行輸入，因此無法正確處理圖結(jié)構(gòu)數(shù)據(jù)的輸入，因為圖中沒有自然的節(jié)點順序。為了完整地呈現(xiàn)圖結(jié)構(gòu)數(shù)據(jù)，需遍歷所有可能的順序作為模型輸入，如卷積神經(jīng)網(wǎng)絡(luò)(CNN)和循環(huán)神經(jīng)網(wǎng)絡(luò)(recurrent neural network，RNN)，這在計算時有大量冗余操作。為解決這個問題，圖神經(jīng)網(wǎng)絡(luò)分別在每個節(jié)點上傳播信息，避免了節(jié)點數(shù)據(jù)的輸入順序。同時，圖中的邊表示兩個節(jié)點之間的依賴關(guān)系信息。在標(biāo)準(zhǔn)神經(jīng)網(wǎng)絡(luò)中，依賴信息僅被視為節(jié)點的特征。圖神經(jīng)網(wǎng)絡(luò)(graph neural network，GNN)可以通過圖結(jié)構(gòu)進行傳播，而不是將其用做特征的一部分。通常，GNN通過其鄰域的狀態(tài)的加權(quán)和來更新節(jié)點數(shù)據(jù)的隱藏狀態(tài)。

隨著深度學(xué)習(xí)的發(fā)展，研究人員將深度學(xué)習(xí)的模型引入圖數(shù)據(jù)中進行端到端的建模，而圖卷積神經(jīng)網(wǎng)絡(luò)則是發(fā)展最活躍的一個方向。在建模圖卷積神經(jīng)網(wǎng)絡(luò)時，研究人員更關(guān)注如何在圖上構(gòu)建卷積算子(徐冰冰 等，2020)。

卷積定理如下：信號卷積的傅里葉變換等價于信號傅里葉變換的乘積(Shuman等，2013)，即

F(f*g)=F(f)·F(g)

(1)

式中，f和g表示兩個原始信號，F(xiàn)(f)表示f的傅里葉變換，·表示乘積算子，*表示卷積算子。對式(1)兩端進行傅里葉逆變換，可得

f*g=F-1(F(f)·F(g))

(2)

式中，F(xiàn)-1表示信號f的逆傅里葉變換。

利用卷積定理，可以對譜空間的信號做乘法，再利用逆傅里葉變換將信號轉(zhuǎn)換到原空間來實現(xiàn)圖卷積，從而避免了因圖數(shù)據(jù)不滿足平移不變性而造成的構(gòu)造傳統(tǒng)意義的卷積運算困難。

圖結(jié)構(gòu)的傅里葉變換依賴于圖中的拉普拉斯矩陣的特征向量，以特征向量作為譜空間下的一組基底，圖上信號x的傅里葉變換為

(3)

(4)

Brune等人(2013)提出第一個圖卷積神經(jīng)網(wǎng)絡(luò)，基于圖譜理論(spectral graph theory)從卷積定理出發(fā)，開發(fā)了一種圖卷積的變體，在譜空間定義圖卷積。該方法利用卷積定理在每一層定義圖卷積算子，在損失函數(shù)指導(dǎo)下，通過梯度反向傳播學(xué)習(xí)卷積核，并堆疊多層組成神經(jīng)網(wǎng)絡(luò)。譜卷積神經(jīng)網(wǎng)絡(luò)第m層的結(jié)構(gòu)為

(5)

Kipf 等人(2016)對譜方法中的卷積核進行參數(shù)化，提出了基于半監(jiān)督的圖卷積神經(jīng)網(wǎng)絡(luò)，降低了時空復(fù)雜度。

(6)

Kipf等人(2016)為圖結(jié)構(gòu)的半監(jiān)督節(jié)點分類如圖1所示，任務(wù)設(shè)計了兩層圖卷積網(wǎng)絡(luò)，并將模型簡化為

圖1 圖卷積神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)圖(Kipf等，2016)

(7)

譜方法通常同時處理整個圖，且難以并行或擴展到大圖上。對此，基于空間的圖卷積網(wǎng)絡(luò)在節(jié)點域使用注意力機制和序列化模型。

給定一組節(jié)點特征作為圖注意力層的輸入，h={h1,h2,…,hN},hi∈RF，其中N是節(jié)點的數(shù)量，F(xiàn)為每個節(jié)點的特征數(shù)，通過注意力層可以生成一組新的節(jié)點特性，可能有不同的維數(shù)F′，輸出為h′={h′1,h′2,…,h′N},h′i∈RF′。對每個節(jié)點作用一個權(quán)值矩陣W∈RF′×F，然后對每個節(jié)點應(yīng)用注意力機制，一個共享的注意力機制α:RF′×RF′→R，計算注意力系數(shù)eij=α(Whi,Whj)，這表明節(jié)點j的特征對節(jié)點i的重要性。為了使不同節(jié)點間的系數(shù)易于比較，圖注意力網(wǎng)絡(luò)(graph attention network，GAT)使用softmax函數(shù)對所有j的選擇進行標(biāo)準(zhǔn)化，即

(8)

圖2 圖注意力機制結(jié)構(gòu)等，2017)

GAT基本思想是根據(jù)每個節(jié)點在其鄰節(jié)點上的注意力，對節(jié)點表示進行更新。GAT具有如下幾個特點：1)相比于GCN，無需特征分解等復(fù)雜的矩陣運算，計算速度快;2)引入注意力機制，計算節(jié)點的重要性，提高模型的表達能力;3)通過對鄰域信息的注意力加權(quán)，幫助節(jié)點融合相似性信息。

經(jīng)典的圖卷積神經(jīng)網(wǎng)絡(luò)算法在很多任務(wù)上取得了顯著效果，然而將這些算法應(yīng)用于實際數(shù)據(jù)時仍面臨一些挑戰(zhàn)。

Li等人(2018)證明了圖卷積算子為拉普拉斯平滑的一種特殊形式——對稱拉普拉斯平滑。

拉普拉斯平滑(Taubin，1995)在輸入特征的每個維度處理定義為

(9)

將其寫為矩陣形式為

(10)

圖結(jié)構(gòu)由于存在信息聚合傳播特性，拉普拉斯平滑法將節(jié)點的新特征表征為自身特征及其相鄰頂點的加權(quán)平均。由于同一聚類中的頂點往往是密集連接的，平滑引導(dǎo)它們的特征相似，使得分類任務(wù)更加容易(Li等，2018)。這是GCN的基本處理機制，但它也帶來了因卷積層數(shù)增加引起的潛在過平滑的問題，重復(fù)應(yīng)用拉普拉斯平滑可能會混合來自不同聚類的特征，導(dǎo)致數(shù)據(jù)難以區(qū)分。

圖3 Zachary’s karate club 數(shù)據(jù)集上針對GCN的15層級進行的節(jié)點嵌入(Li等，2018)

然而，由于圖卷積是一個局部濾波器——相鄰鄰居的特征向量的線性組合，一個淺層GCN不能充分傳播標(biāo)簽信息到只有少數(shù)標(biāo)簽的整個圖中，這反映了GCN模型無法探索全局圖結(jié)構(gòu)。同時，深層的GCN意味著更大的接收域，深層體系結(jié)構(gòu)在計算機視覺中的關(guān)鍵優(yōu)勢之一是它們能夠堆疊簡單的結(jié)構(gòu)形成深層結(jié)構(gòu)實現(xiàn)復(fù)雜功能。因此，圖卷積神經(jīng)網(wǎng)絡(luò)的層級信息挖掘是必要的，但受過平滑和過擬合現(xiàn)象的影響無法直接通過堆疊卷積層來構(gòu)建深度圖卷積網(wǎng)絡(luò)。過擬合現(xiàn)象會削弱小數(shù)據(jù)集的泛化能力，過平滑會隨著深度的增加將輸出表示與輸入特征隔離，從而阻礙模型訓(xùn)練?；趯蛹壗Y(jié)構(gòu)的研究則關(guān)注構(gòu)建一個層級的圖卷積模型，從而能夠獲取更多的表達信息。

2 圖卷積層級信息挖掘算法及其分類

受過平滑和過擬合問題影響的淺模型體系結(jié)構(gòu)限制了它們從高階鄰域提取知識的能力，即無法從當(dāng)前節(jié)點鄰域的遠程跳躍中提取特征。能否設(shè)計一種避免過平滑和過擬合的深層網(wǎng)絡(luò)結(jié)構(gòu)，且獲取到層級信息是一個迫切需要解決的問題。將層級結(jié)構(gòu)算法遷移到圖數(shù)據(jù)分析的核心在于圖層級卷積算子構(gòu)建與圖層級間信息融合。其中，圖層級卷積算子構(gòu)建的目的是刻畫節(jié)點的局部表示，層級信息融合目的是層級間信息的互補性探索。

圖網(wǎng)絡(luò)層級信息挖掘算法分類如表2所示。按圖層級研究方法關(guān)注點的不同，現(xiàn)有圖層級信息挖掘算法分為兩類。第1類是正則化技術(shù)(regularisation techniques)，該技術(shù)關(guān)注于圖層級卷積算子的構(gòu)造，例如DropEdge(Rong等, 2019)等方法利用圖結(jié)構(gòu)關(guān)系，通過每層隨機剔除部分邊來加深圖神經(jīng)網(wǎng)絡(luò)并減緩過平滑現(xiàn)象發(fā)生；第2類是架構(gòu)調(diào)整方法(structural adjustment method)，該方法關(guān)注于層級之間的信息融合，包括各類殘差連接，例如知識跳躍或仿射殘差連接。

表2 圖網(wǎng)絡(luò)層級信息挖掘算法

2.1 正則化方法

正則化方法主要是基于正則化技術(shù)處理圖的層級結(jié)構(gòu)信息，該類方法更關(guān)注于圖層級卷積算子構(gòu)建。圖卷積算子(按特定權(quán)重聚合鄰域節(jié)點的特征)是圖卷積神經(jīng)網(wǎng)絡(luò)方法的核心算子。在架構(gòu)調(diào)整方法中雖然按照某種機制將層級信息融合在一起，但并沒有關(guān)注每個層級模型的構(gòu)建，因此仍具有局限性，忽略了節(jié)點的拓撲關(guān)系以及邊信息等。正則化方法具有以下兩個特點：1)關(guān)注節(jié)點特性和邊特性構(gòu)建圖層級卷積算子；2)采用正則化方法緩解圖過平滑和過擬合現(xiàn)象，可以構(gòu)造出更深的圖網(wǎng)絡(luò)模型。正則化代表性方法如表3所示。

表3 正則化代表性方法

2.1.1 基于卷積定理的正則化方法

基于卷積定理的譜圖神經(jīng)網(wǎng)絡(luò)的建模必須基于拉普拉斯矩陣的特征值分解，且拉普拉斯矩陣帶來拉普拉斯平滑現(xiàn)象。因此有研究人員提出改變圖傅里葉變換實現(xiàn)圖卷積定理。

小波神經(jīng)網(wǎng)絡(luò)(Xu等，2019)提出用小波基代替圖卷積中的傅里葉基(Hammond等，2011)。按照原理，小波基可表示為Ψs=(ψs1,ψs2,…,ψsn)，其中，每一個小波都對應(yīng)一個從節(jié)點i擴散到圖上的信號，且s為尺度參數(shù)。小波基底的定義依賴于拉普拉斯矩陣的特征向量，即

Ψs=UGsUT

(11)

(12)

相比于圖傅里葉變換(式(4))，圖小波變換對節(jié)點鄰域的調(diào)整更加靈活，通過改變尺度參數(shù)s調(diào)節(jié)中心節(jié)點的信息擴散范圍。圖小波神經(jīng)網(wǎng)絡(luò)卷積層定義為

(13)

考慮到小波變換通常比傅里葉變換具有更強的提取有用信息的能力，Wang等人(2021a)提出深度圖小波卷積網(wǎng)絡(luò)(deep graph wavelet convolutional neural network，DeepGWC)用于半監(jiān)督節(jié)點分類任務(wù)。其中，DeepGWC的第l層表示為

Hl+1=σ(Hl′Wl′)

(14)

式中，σ為激活函數(shù)，Hl′是在H上進行圖卷積的結(jié)果，Wl′是可優(yōu)化的特征映射矩陣。Hl′和Wl′具體為

(15)

Wl′=βlWl+(1-βl)I

(16)

(17)

式中，γ表示初始殘差項圖小波變換項的比例。通過殘差機制和小波變化的信息獲取能力，DeepGWC構(gòu)建了一個64層深度模型，并減弱了過平滑現(xiàn)象。

Bianchi等人(2022)基于自回歸移動平均(auto regressive moving average，ARMA)濾波器(Narang等, 2013)提出一種新穎的圖卷積層，與多項式濾波器相比，該卷積層提供了更靈活的頻率響應(yīng)，對噪聲更魯棒且可以更好地捕獲全局圖結(jié)構(gòu)，并定義新的GCS(graph convolutional skip)層為

(18)

圖4 ARMA卷積層結(jié)構(gòu)(Bianchi等，2022)

(19)

實驗表明，PairNorm使更深的GCN、GAT和SGC(simplifying graph convolutional networks)模型對過度平滑具有更強的魯棒性，并極大提高了更深網(wǎng)絡(luò)構(gòu)架的性能。

Rong等人(2019)認(rèn)為圖神經(jīng)網(wǎng)絡(luò)無法加深主要有兩個原因，過擬合(over-fitting)和過平滑(over-smoothing)，并提出了DropEdge機制，在模型訓(xùn)練時，隨機刪減掉原始圖中的邊來緩解這兩個問題，其定義DropEdge 中的鄰接矩陣為

Adrop=A-A′

(20)

式中，A′是原始邊集中的隨機子集，并通過丟棄率α控制子集大小。Rong等人(2019)從理論上證明，DropEdge既可以降低過平滑的收斂速度，又可以減少由過平滑引起的信息損失，且可用于許多GNN模型以增強性能。例如，JKNet(jumping knowledge networks)(Xu等，2018)、GCN(Kipf等，2016)、ResGCN(Li等，2019b)和GraphSAGE(Hamilton等，2017)等。

圖5展示了多層GCN在Cora數(shù)據(jù)集上的表現(xiàn)能力(Rong等，2019)。可以看出，GCN-4陷入過擬合問題，訓(xùn)練誤差小，但驗證誤差大；GCN-8的訓(xùn)練由于過平滑而不能令人滿意地收斂。通過應(yīng)用DropEdge，GCN-4和GCN-8在訓(xùn)練和驗證方面都能很好地工作。

圖5 多層GCN在Cora數(shù)據(jù)集上的表現(xiàn)能力(Rong等, 2020)

上述方法從卷積定理出發(fā)，關(guān)注于卷積定理中卷積核、節(jié)點特征和邊的處理，通過重新構(gòu)建圖卷積聚合方式來減弱過平滑現(xiàn)象。

2.1.2 基于注意力機制的正則化法

基于卷積定理的圖神經(jīng)網(wǎng)絡(luò)可以看做以拉普拉斯矩陣或其變體作為聚合函數(shù)。在注意力機制的啟發(fā)下，一些研究通過注意力機制方式從節(jié)點域?qū)W習(xí)聚合函數(shù)。

Klicpera等人(2019a)探索了GCN與PageRank算法(Page等, 1999)之間的關(guān)系，提出基于personalized page rank 的改進版本的信息傳遞方式，認(rèn)為根據(jù)圖卷積網(wǎng)絡(luò)(GCN)的消息傳遞算法與隨機游走之間的關(guān)系，隨著層數(shù)的增加，GCN會收斂到該隨機游走的極限分布。極限分布是整個圖的一個屬性，沒有考慮隨機游走的起始(根)節(jié)點。因此，該方法不適合描述根節(jié)點的鄰域。GCN的性能會因大量層聚合或傳播而下降。為了將PageRank的影響分?jǐn)?shù)用于半監(jiān)督分類，Klicpera等人(2019a)根據(jù)每個節(jié)點的自身特征生成預(yù)測，然后通過personalized page rank方案進行傳播，以生成最終預(yù)測，并基于此提出PPNP(personalized propagation of neural predictions)算法，具體為

Hi,:=fθ(Xi,:)

(21)

式中，X是特征矩陣，fθ是帶有參數(shù)集θ的神經(jīng)網(wǎng)絡(luò)，生成預(yù)測H∈Rn×c。PPNP從傳播步驟中分離出了用于預(yù)測的神經(jīng)網(wǎng)絡(luò)，使得PPNP算法可以聚合無限多個鄰域。

為了加快計算速度，Klicpera等人(2019a)提出APPNP(approximate personalized propagation of neural predictions)算法，采用近似的方法來避免計算矩陣的逆，即

Z(0)=H=fθ(X)

(22)

(23)

(24)

式中，K定義了迭代的步數(shù)，在PPNP和APPNP中，可以通過概率α來調(diào)整影響每個節(jié)點的鄰域的大小，從而針對不同類型的網(wǎng)絡(luò)調(diào)整模型。圖6解釋了如何將個性化網(wǎng)頁排名(personalized page rank)用于網(wǎng)絡(luò)預(yù)測。

圖6 Personalized page rank用于網(wǎng)絡(luò)預(yù)測(Klicpera等, 2019a)

Klicpera等人(2019b)通過引入一個強大的、空間局部化的圖卷積——圖擴散卷積(graph diffusion convolution，GDC)來消除圖卷積中只使用直接鄰居的限制。GDC模型通過擴散矩陣定義廣義擴散模型，具體為

(25)

Chen等人(2020a)提出GCNII模型，利用初始殘差和恒等映射解決過平滑問題，有效緩解了過平滑問題。GCNII的l層定義為

((1-βl)In+βlW(l)))

(26)

在上述方法中，拉普拉斯矩陣帶來的過平滑問題阻礙了深度圖模型的研究。為此，重新設(shè)計神經(jīng)網(wǎng)絡(luò)來學(xué)習(xí)聚合函數(shù)，基于正則化技術(shù)處理圖的層級結(jié)構(gòu)信息，即圖卷積層級算子的重新構(gòu)造能夠自適應(yīng)于任務(wù)和具體的圖結(jié)構(gòu)，有更大的靈活性。

2.2 架構(gòu)調(diào)整方法

與卷積神經(jīng)網(wǎng)絡(luò)層級卷積相對應(yīng)，圖卷積層級結(jié)構(gòu)也具有類似的性質(zhì)，不同深度的層級模型捕獲不同的語義特征，淺層模型受節(jié)點特性影響較大，更關(guān)注于節(jié)點的局部信息，而深層模型則受圖拓撲結(jié)構(gòu)的影響，更關(guān)注于圖全局信息，將不同層的嵌入基于注意力方式結(jié)合起來，可以獲取更全面的信息。架構(gòu)調(diào)整方法主要是利用圖卷積層之間的相互關(guān)系進行深層疊加，并通過某種機制進行信息融合。一個簡單的解決方案是通過殘差連接(ResNets)實現(xiàn)的，但是這種做法在構(gòu)建的深度圖模型的預(yù)測性能和計算效率方面都不令人滿意。

架構(gòu)方法具有以下特點：1)靈活利用每個節(jié)點的不同鄰域范圍，實現(xiàn)更好的結(jié)構(gòu)感知；2)關(guān)注圖局部信息和全局信息；3)引入注意力機制，獲取層級的互補性信息，增強節(jié)點的表達。

最新代表性的架構(gòu)調(diào)整方法如表4所示。

表4 最新代表性的架構(gòu)調(diào)整方法

針對圖結(jié)構(gòu)的層級特性，Xu 等人(2018)提出JKNet(jumping knowledge networks)。為了適應(yīng)局部鄰域?qū)傩院腿蝿?wù)，采用基于跳躍知識網(wǎng)絡(luò)的跳躍連接和注意力機制，將GCN每一層分別與最終層連接，并利用concatenation、maximization pooling、long short-term memory attention等操作自適應(yīng)聚合每一層特征作為最終節(jié)點表示。模型結(jié)構(gòu)如圖7所示。

圖7 4層JKNet模型示意圖(Xu等, 2018)

Abu-El-Haija等人(2020)提出了模型N-GCN(network of GCNs)，與JKNet不同，N-GCN使用GCN隨機游走中在不同距離處發(fā)現(xiàn)的節(jié)點對上層訓(xùn)練多個全局控制網(wǎng)絡(luò)實例，并將每層輸出拼接在一起，最后利用全連接網(wǎng)絡(luò)進行層級信息融合。N-GCN模型結(jié)構(gòu)如圖8所示。

圖8 N-GCN結(jié)構(gòu)示意圖(Abu-El-Haija等, 2020)

Sun 等人(2021)提出AdaGCN，使用集成學(xué)習(xí)方法探索層級特性。針對前一層模型在測試數(shù)據(jù)集上的準(zhǔn)確度，優(yōu)化該層在最終模型的注意力系數(shù)。準(zhǔn)確度越低則注意力系數(shù)越低，這樣使得模型能夠以AdaBoost的方式對層級特征進行融合。AdaGCN模型關(guān)注的是每一層模型在測試數(shù)據(jù)集上的準(zhǔn)確度，對同一層節(jié)點分配的注意力系數(shù)相同。AdaGCN模型結(jié)構(gòu)如圖9所示。

圖9 AdaGCN模型結(jié)構(gòu)示意圖(Sun等, 2021)

Abu-El-Haija等人(2019a)提出MixHop-GCN,通過重復(fù)混合不同距離的鄰域特征表示來學(xué)習(xí)鄰域混合關(guān)系，并利用超參數(shù)融合層級特征。

Li等人(2019b)利用卷積神經(jīng)網(wǎng)絡(luò)的概念，特別是殘差/密集連接和擴展卷積，構(gòu)建了一個非常深的56層GCN體系結(jié)構(gòu)，在點云語義分割任務(wù)中可以顯著提高性能。圖10展示了3種GCN的主干塊結(jié)構(gòu)。大量實驗表明，這些深度GCN框架具有積極作用。

圖10 三種GCN的主干塊結(jié)構(gòu)(Li等，2019b)

在DeepGCN中，研究人員認(rèn)為通用GCN網(wǎng)絡(luò)從l層到l+1層的傳播方式為

Gl+1=F(Gl,Wl)=

(27)

受到ResNet的啟發(fā)，Spinelli等人(2021)對GCN進行更改，稱為ResGCN。具體為

Gl+1=H(Gl,Wl)=

(28)

同時，為了利用各層之間的緊密連通性，改善網(wǎng)絡(luò)的信息流，受DenseNet(Huang等，2017)的啟發(fā)，Huang等人(2017)將類似想法應(yīng)用于GCNs，以便利用不同GCN層的信息流，將DenseGCN定義為

Gl+1=H(Gl,Wl)=T(F(Gl,Wl),Gl)=

T(F(Gl,W),…,F(G0,W0),G0)

(29)

式中，T表示頂點級連接函數(shù)，將輸入圖G0與所有中間GCN層輸出密集融合。

DeepGCNs利用ResGCN和DenseGCN處理GCNs的梯度消失問題，使GCN可以進行深層學(xué)習(xí)。

Spinelli等人(2021)提出AP-GCN(adaptive propagation GCN)模型，通過在每個節(jié)點上獨立調(diào)整通信步驟的數(shù)量，特別是賦予每個節(jié)點一個暫停單元，利用線性網(wǎng)絡(luò)對每個節(jié)點的層級輸出特征進行判斷，在每次信息傳播后決定該節(jié)點是否繼續(xù)通信。最終，利用線性網(wǎng)絡(luò)判斷出的停止概率值對層級特征進行融合。由于AP-GCN依據(jù)節(jié)點級別判斷層級特性，且通過停止概率值阻斷部分節(jié)點信息傳播，因此獲得了最新的分類表現(xiàn)。AP-GCN模型結(jié)構(gòu)如圖11所示。

圖11 AP-GCN模型結(jié)構(gòu)(Spinelli等, 2021)

Pei等人(2022)提出殘差圖卷積網(wǎng)絡(luò)(residual graph convolutional network，ResGCN)用于網(wǎng)絡(luò)中的異常檢測，框架如圖12所示。異常節(jié)點與其他節(jié)點有兩方面不同；1)異常節(jié)點在結(jié)構(gòu)上連接所有其他節(jié)點；2)異常節(jié)點屬性與多數(shù)節(jié)點明顯不同。Pei等人(2022)提出的方法是一種基于注意力的深度殘差建模方法，使用GCN建模屬性網(wǎng)絡(luò)可以捕獲稀疏性和非線性。利用深度神經(jīng)網(wǎng)絡(luò)可直接從輸入中學(xué)習(xí)殘差，而基于殘差的注意力機制可減少異常節(jié)點帶來的不利影響并防止過度平滑。

圖12 ResGCN框架(Pei等, 2022)

為了在模型構(gòu)建中考慮高階結(jié)構(gòu)關(guān)系來提高節(jié)點分類模型的表現(xiàn)，研究人員通過以上方式融合大范圍和小范圍的特征組合，自適應(yīng)地調(diào)整每個節(jié)點的影響半徑，聚合不同層級節(jié)點表達產(chǎn)生節(jié)點的最終表達，以此探索層級互補性信息。

3 圖卷積網(wǎng)絡(luò)層級特性實驗

圖結(jié)構(gòu)節(jié)點受到的結(jié)構(gòu)影響不同，從鄰域獲取信息的能力不同，自身攜帶信息的能力也不同。為了驗證圖結(jié)構(gòu)節(jié)點存在層級特性以及其過平滑現(xiàn)象，在3種標(biāo)準(zhǔn)引文數(shù)據(jù)集Cora、CiteSeer和PubMed上對圖卷積神經(jīng)網(wǎng)絡(luò)層級進行實驗，探索不同深度的圖卷積神經(jīng)網(wǎng)絡(luò)對其節(jié)點的分類能力。

GCN-0：

Y=σ(XW),W∈RF×C

(30)

GCN-1：

(31)

GCN-2：

W1∈RF×H,W2∈RH×C

(32)

GCN-3：

W1∈RF×H,W2∈RH×H,W3∈RH×C

(33)

在實驗中，模型基于PyTorch Geometric(Fey等，2019)標(biāo)準(zhǔn)圖神經(jīng)網(wǎng)絡(luò)庫設(shè)計，各數(shù)據(jù)集參數(shù)如表5

表5 層級特性實驗參數(shù)定義

所示，為了可復(fù)現(xiàn)結(jié)果，隨機種子設(shè)置為42。

表6 圖卷積網(wǎng)絡(luò)層級特性實驗結(jié)果

圖網(wǎng)絡(luò)層級信息挖掘算法均采用不同的信息挖掘手段，試圖使用一個統(tǒng)一的模型，利用端到端的學(xué)習(xí)方式將不同特性節(jié)點分類成功。從預(yù)期結(jié)果來看，如果有一個模型可以將每個層級的特性節(jié)點均分類成功，圖網(wǎng)絡(luò)節(jié)點分類任務(wù)將顯著性突破，但遺憾的是，目前的算法尚未能達到預(yù)期結(jié)果。

4 應(yīng) 用

圖卷積神經(jīng)網(wǎng)絡(luò)提出以來，受到網(wǎng)絡(luò)分析、推薦系統(tǒng)、計算機視覺和自然語言處理等領(lǐng)域研究人員的關(guān)注。其中，圖網(wǎng)絡(luò)層級信息挖掘算法主要應(yīng)用于網(wǎng)絡(luò)分析、推薦系統(tǒng)和計算機視覺領(lǐng)域，相關(guān)算法及任務(wù)如表7所示。

表7 圖網(wǎng)絡(luò)層級信息挖掘算法應(yīng)用總結(jié)

4.1 在網(wǎng)絡(luò)分析中的應(yīng)用

在網(wǎng)絡(luò)分析領(lǐng)域，引文網(wǎng)絡(luò)是最常見的數(shù)據(jù)。該網(wǎng)絡(luò)中，節(jié)點為論文的特征，特征中的0和1表示該論文有無對應(yīng)的詞匯，邊為論文節(jié)點之間引用關(guān)系，是無向圖網(wǎng)絡(luò)。

常見的數(shù)據(jù)集包括Cora、CiteSeer和PubMed等，具體描述如表5所示。

典型的分類任務(wù)是給定每篇文章的內(nèi)容信息與文章之間的引用關(guān)系，將每篇文章分類到對應(yīng)的領(lǐng)域。在該類任務(wù)中，圖卷積神經(jīng)網(wǎng)絡(luò)對節(jié)點文本屬性和引用網(wǎng)絡(luò)結(jié)構(gòu)進行有效建模，取得了巨大成功。部分模型分類結(jié)果如表8所示。包括直接使用內(nèi)容信息，如MLP(multilayer perceptron)(Gardner等, 1998)；僅使用結(jié)構(gòu)信息，如DeepWalk(Perozzi等，2014)和傳統(tǒng)圖上半監(jiān)督節(jié)點分類方法，如Planetoid(Yang等，2016)。實驗結(jié)果表明，以GCN為代表的圖卷積神經(jīng)網(wǎng)絡(luò)算法及其融合層級信息后的分類準(zhǔn)確度遠高于傳統(tǒng)方法。

表8 不同模型在Cora、CiteSeer和PubMed數(shù)據(jù)集上的節(jié)點分類結(jié)果

網(wǎng)絡(luò)分析中另一個發(fā)展分支為社交網(wǎng)絡(luò)分析，主要任務(wù)有用戶畫像、輿情分析、社交垃圾郵件檢測和謠言檢測等。Zhang等人(2018)在鏈接預(yù)測問題中，通過在每個目標(biāo)鏈接周圍提取局部子圖，學(xué)習(xí)一種映射子圖模式，以鏈接存在的函數(shù)，從而自動學(xué)習(xí)適合當(dāng)前網(wǎng)絡(luò)的“啟發(fā)式”方法，并證明可以從局部子圖很好地近似所有這些啟發(fā)式方法。Qiu等人(2018)關(guān)注于用戶級社會影響力的預(yù)測，通過將網(wǎng)絡(luò)嵌入、圖卷積和圖注意力網(wǎng)絡(luò)構(gòu)建到一個統(tǒng)一的框架DeepInf中，設(shè)計了一種端到端的方法來自動發(fā)現(xiàn)社會影響中的隱藏和預(yù)測信號。

確定影響媒體討論新聞事件方式的政治視角是一項重要而富有挑戰(zhàn)性的任務(wù)，Li等人(2019a)提出通過GCN來捕獲文檔的社交環(huán)境，以此來預(yù)測作者的政治傾向。Peng等人(2019)基于知識元路徑實例的社交事件相似度度量(knowledgeable meta-paths instances based social event similarity，KIES)，提出基于GCN的社交事件分類算法。Wu等人(2020)基于Markov random field reasoning(Li，1994)提出一種基于圖卷積網(wǎng)絡(luò)的社交垃圾郵件發(fā)送者檢測模型。Bian等人(2020)提出一種雙向圖模型，稱為雙向圖卷積網(wǎng)絡(luò)(bi-directional graph convolutional networks，Bi-GCN)，通過對謠言自上而下和自下而上的傳播進行操作來探索這兩個特征，以此進行社交謠言檢測。

4.2 在推薦系統(tǒng)中的應(yīng)用

基于圖的推薦系統(tǒng)將項目和用戶作為節(jié)點。通過利用項目與項目之間、用戶與用戶之間以及用戶與項目之間的關(guān)系，使得系統(tǒng)能夠產(chǎn)生高質(zhì)量的建議。推薦系統(tǒng)的關(guān)鍵是對用戶評價項目的重要性。因此，可以將其視為鏈接預(yù)測或矩陣補全問題，從而能夠有效建模商品與用戶之間的聯(lián)系。

He等人(2020)將圖卷積層級信息用于推薦系統(tǒng)，提出LightGCN模型，在將每個用戶(項目)與ID(identity)嵌入關(guān)聯(lián)后，在用戶—項目交互圖上傳播嵌入以對其改進，然后將不同傳播層的嵌入信息與加權(quán)和相結(jié)合，得到最終的預(yù)測嵌入信息。Ying等人(2018)將卷積神經(jīng)網(wǎng)絡(luò)應(yīng)用于推薦系統(tǒng)，提出一個數(shù)據(jù)高效的圖卷積神經(jīng)網(wǎng)絡(luò)算法PinSage，對商品節(jié)點產(chǎn)生嵌入表達。這些表達包含圖結(jié)構(gòu)和節(jié)點特征信息。相比傳統(tǒng)的圖卷積方式，該方法使用一個高效的隨機游走策略建模卷積，設(shè)計了一個新的訓(xùn)練策略，成功地將圖卷積神經(jīng)網(wǎng)絡(luò)應(yīng)用于超大規(guī)模推薦系統(tǒng)。

相比于傳統(tǒng)方法，圖卷積神經(jīng)網(wǎng)絡(luò)能夠更好地利用在推薦系統(tǒng)普遍存在的用戶屬性和商品屬性信息，這也是圖卷積神經(jīng)網(wǎng)絡(luò)能夠在推薦系統(tǒng)任務(wù)上引起人們廣泛關(guān)注的原因。

4.3 在計算機視覺中的應(yīng)用

計算機視覺方面的應(yīng)用主要為物體識別、圖片分類和語義分割等任務(wù)，同時更關(guān)注于少樣本分類以及復(fù)雜語義情況下的建模和學(xué)習(xí)。

在點云分割任務(wù)中，Li等人(2019b)通過構(gòu)建的56層深度圖卷積，在點云分割任務(wù)中達到了目前最好的表現(xiàn)結(jié)果。在點云生成任務(wù)中，Valsesia等人(2019)將圖卷積引入生成對抗網(wǎng)絡(luò)(generative adversarial network，GAN)(Goodfellow等, 2014)中，并研究了在圖卷積生成器中定義上采樣層的問題，以使其學(xué)會在數(shù)據(jù)分布前先利用自相似性更有效地采樣，來解決點云生成任務(wù)中不規(guī)則分布無序點采樣問題。在RGBD語義分割任務(wù)中，Qi等人(2017)提出一個3D圖神經(jīng)網(wǎng)絡(luò)(3DGNN)，該網(wǎng)絡(luò)在3D點云之上構(gòu)建了一個k最近鄰圖。圖中的每個節(jié)點對應(yīng)于一組點，并與隱藏的表示向量相關(guān)聯(lián)，該向量由一元CNN從2D圖像提取的外觀特征初始化。依靠循環(huán)功能，每個節(jié)點都會根據(jù)當(dāng)前狀態(tài)和來自鄰居的傳入消息動態(tài)更新其隱藏表示。在一定數(shù)量的時間步長上展開此傳播模型，并將最終的每個節(jié)點表示形式用于預(yù)測每個像素的語義類別。在語義分割任務(wù)中，Zhang等人(2019a)為了捕獲不同語義級別的對應(yīng)關(guān)系，受特征金字塔(Lin等，2017)的啟發(fā)，提出一種金字塔狀結(jié)構(gòu)，將不同大小的圖像區(qū)域建模為圖節(jié)點，并在不同級別進行圖推理。

4.4 在其他領(lǐng)域的應(yīng)用

圖網(wǎng)絡(luò)層級信息挖掘分類算法的研究方向不限于上述領(lǐng)域和任務(wù)，還包括自然語言處理(Song等，2018；Liu等，2019b)、問題解答(Chen等，2018)、行人交互(Qi等，2018)和視覺推理(Wang等，2020)等。由于圖網(wǎng)絡(luò)層級信息挖掘分類算法可以建模圖結(jié)構(gòu)數(shù)據(jù)，并且通過圖卷積和注意力機制等能夠改善圖卷積經(jīng)典算法在實際應(yīng)用中的多尺度和過平滑等局限性，因此具有廣泛的應(yīng)用前景。

5 存在問題及發(fā)展方向

1)計算效率方面。相比較于淺層圖卷積模型，深度層級模型的研究必然導(dǎo)致模型參數(shù)量的增多，同時帶來過擬合、梯度消失和梯度爆炸等問題。盡管殘差連接、密集連接和圖層級信息挖掘等可緩解深度圖模型的梯度消失、梯度爆炸等問題，但相比較淺層模型，深層模型需要更多的訓(xùn)練樣本引導(dǎo)模型收斂。時間復(fù)雜度和空間復(fù)雜度成為制約深度圖卷積模型學(xué)習(xí)的一個難點。

2)問題設(shè)置方面。圖神經(jīng)網(wǎng)絡(luò)應(yīng)用中一個具有挑戰(zhàn)性的問題是如何處理具有動態(tài)結(jié)構(gòu)的圖，例如異構(gòu)圖和時序圖。靜態(tài)圖是穩(wěn)定的，因此可以利用拉普拉斯矩陣對其進行卷積處理，而動態(tài)圖則引入了變化的結(jié)構(gòu)。STGCN(spatial temporal graph convolutional network)(Yan等，2018)引入時間通道卷積建模人體運動過程中骨骼節(jié)點的運動序列信息；MRA-BGCN(multi-range attentive bicomponent GCN)(Chen等，2020c)在交通網(wǎng)絡(luò)信號圖中引入二分圖卷積模型，建模節(jié)點和邊在時序中的交互機制。但在上述研究中，圖結(jié)構(gòu)的節(jié)點固定，只有狀態(tài)發(fā)生改變，依然可以依靠拉普拉斯矩陣建?？臻g相關(guān)性。當(dāng)引入層級信息后，層級之間的節(jié)點信息傳播不再遵循初始鄰接關(guān)系的傳播路徑，節(jié)點的增加和消失導(dǎo)致信息傳播出現(xiàn)變化，無法完全探索節(jié)點的層級特性，嚴(yán)重影響了圖層級模型的穩(wěn)定性和判斷能力。

3)應(yīng)用場景方面。圖數(shù)據(jù)無處不在，圖神經(jīng)網(wǎng)絡(luò)也已經(jīng)在各種深度學(xué)習(xí)任務(wù)發(fā)揮至關(guān)重要的作用。相比較淺層圖神經(jīng)網(wǎng)絡(luò)，使用層級圖神經(jīng)網(wǎng)絡(luò)的優(yōu)點在于，節(jié)點的局部子圖和全局圖結(jié)構(gòu)之間的關(guān)系保留在節(jié)點表征中，豐富了節(jié)點的表達，在節(jié)點分類任務(wù)中已經(jīng)得到有效應(yīng)用，如點云識別、推薦系統(tǒng)等。而探索層級結(jié)構(gòu)在其他各類數(shù)據(jù)圖任務(wù)中的應(yīng)用也非常重要，因為層級圖卷積模型從不同角度為圖任務(wù)提供了有效的解決方案。

6 結(jié) 語

深度圖神經(jīng)網(wǎng)絡(luò)的訓(xùn)練過程非常艱難，除了深層神經(jīng)體系結(jié)構(gòu)中的典型難點(如大量參數(shù)導(dǎo)致反向傳播梯度消失和過度擬合)外，還有一些圖特有的難點，例如過平滑，這是由于應(yīng)用了多個圖卷積層，節(jié)點特征趨于收斂到同一向量并逐漸變得難以區(qū)分。這些問題都影響著圖網(wǎng)絡(luò)中的層級問題。而如何通過層級信息挖掘來捕獲層級之間的互補信息，增大模型的表現(xiàn)能力是研究人員致力解決的問題。

本文介紹圖卷積神經(jīng)網(wǎng)絡(luò)的發(fā)展及其典型算法，并將其分為正則化方法和架構(gòu)調(diào)整方法兩類。同時，總結(jié)最新的圖卷積神經(jīng)網(wǎng)絡(luò)層級信息挖掘模型以及主要應(yīng)用方向。針對圖的層級特性進行實驗，可以看出圖結(jié)構(gòu)中存在一些特殊節(jié)點，該節(jié)點受圖的結(jié)構(gòu)影響較大，因此表現(xiàn)出層級特性。層級信息挖掘算法的目的在于使用一個統(tǒng)一的模型，針對不同層級特性節(jié)點均有良好的分類效果?？偟膩碚f，雖然已經(jīng)提出一些基于層級的圖卷積網(wǎng)絡(luò)算法，并能夠減緩過平滑現(xiàn)象的發(fā)生，但如何有效挖掘?qū)蛹壷g的信息仍是一個迫切需要解決的問題。