鄭睿剛 ，陳偉福 , 馮國(guó)燦

(1. 中山大學(xué)數(shù)學(xué)學(xué)院，廣東 廣州 510275；2. 中山大學(xué)廣東省計(jì)算科學(xué)重點(diǎn)實(shí)驗(yàn)室，廣東 廣州 510275)

深度神經(jīng)網(wǎng)絡(luò)有著悠久的研究歷史。由于模型大，參數(shù)多，對(duì)訓(xùn)練數(shù)據(jù)和計(jì)算條件要求非?？量?。2006 年Hinton 和Salakhutdinov[1]在Science上發(fā)表了一篇用神經(jīng)網(wǎng)絡(luò)來(lái)對(duì)數(shù)據(jù)進(jìn)行降維的論文引起人們極大的關(guān)注。此外，以AlexNet[2]在2012年ImageNet[3]圖像識(shí)別大賽上表現(xiàn)大放異彩為肇始，深度學(xué)習(xí)的熱潮由此開啟。有賴于大數(shù)據(jù)量、非凸優(yōu)化、硬件計(jì)算和網(wǎng)絡(luò)結(jié)構(gòu)等多方面的進(jìn)展，以卷積神經(jīng)網(wǎng)絡(luò)、循環(huán)神經(jīng)網(wǎng)絡(luò)、生成對(duì)抗網(wǎng)絡(luò)為代表的深度學(xué)習(xí)方法近年來(lái)在圖像、音頻、視頻、文本等規(guī)則數(shù)據(jù)處理方面都取得了優(yōu)異的甚至大幅超越傳統(tǒng)方法的結(jié)果。以卷積神經(jīng)網(wǎng)絡(luò)(Convolutional Neural Network, CNN)為例，殘差神經(jīng)網(wǎng)絡(luò)(Residual Networks, ResNet)[4]在ImageNet[3]上的圖片分類中top5的錯(cuò)誤率只有3.57%，能力超越人類水平。由于深度神經(jīng)網(wǎng)絡(luò)在規(guī)則數(shù)據(jù)處理上取得了極大的成功，進(jìn)一步考慮如何將深度學(xué)習(xí)方法推廣到其他不同于網(wǎng)格與序列的非規(guī)則數(shù)據(jù)結(jié)構(gòu)上是目前神經(jīng)網(wǎng)絡(luò)領(lǐng)域一個(gè)研究熱點(diǎn)。

以圖(graph)為代表的非規(guī)則數(shù)據(jù)，如以城市為節(jié)點(diǎn)的交通流量網(wǎng)絡(luò)、以用戶為節(jié)點(diǎn)的社交網(wǎng)絡(luò)和以各類原子為節(jié)點(diǎn)的分子結(jié)構(gòu)網(wǎng)絡(luò)等，在數(shù)據(jù)的存儲(chǔ)和描述實(shí)體間的關(guān)系方面正發(fā)揮著越來(lái)越重要的作用?；趫D結(jié)構(gòu)的數(shù)據(jù)處理，主要涉及到圖節(jié)點(diǎn)的表示學(xué)習(xí)、圖節(jié)點(diǎn)的分類、圖上邊的預(yù)測(cè)(鏈接預(yù)測(cè))、圖的分類等問(wèn)題。比如說(shuō)，對(duì)于文獻(xiàn)引用網(wǎng)絡(luò)(citation network),節(jié)點(diǎn)的分類主要是預(yù)測(cè)節(jié)點(diǎn)代表的文獻(xiàn)是屬于哪一個(gè)主題(如圖1(a)所示)，在社交網(wǎng)絡(luò)(social network)中經(jīng)常需要預(yù)測(cè)哪兩者之間是有關(guān)聯(lián)的則屬于鏈接預(yù)測(cè)(如圖1(b)所示)。

圖1 圖結(jié)構(gòu)數(shù)據(jù)處理圖例(部分圖片取自文[5])

經(jīng)典的圖結(jié)構(gòu)數(shù)據(jù)處理算法主要依據(jù)圖譜嵌入、隨機(jī)游走、圖核等，然而此類淺層模型主要的缺點(diǎn)在于模型能夠?qū)W習(xí)的表達(dá)能力較為簡(jiǎn)單，無(wú)法從大規(guī)模復(fù)雜的網(wǎng)絡(luò)中提取有價(jià)值的信息。然而，如果直接運(yùn)用傳統(tǒng)的深度神經(jīng)網(wǎng)絡(luò)的方法來(lái)處理這些非規(guī)則結(jié)構(gòu)的數(shù)據(jù)，效果也并不理想。為了更有效處理這些圖結(jié)構(gòu)的數(shù)據(jù)，近年來(lái)涌現(xiàn)了大量圖卷積網(wǎng)絡(luò)。不同于經(jīng)典方法，這些圖卷積算法模型參數(shù)量大，表達(dá)能力強(qiáng)，且可結(jié)合樣本特征與圖結(jié)構(gòu)作端到端的各項(xiàng)任務(wù)，既利用了圖結(jié)構(gòu)，亦減少了對(duì)圖結(jié)構(gòu)的依賴，在處理圖結(jié)構(gòu)數(shù)據(jù)中取得了超越經(jīng)典圖方法的良好效果。

目前圖卷積算法主要是考慮如何將處理規(guī)則數(shù)據(jù)的卷積網(wǎng)絡(luò)遷移過(guò)來(lái)。對(duì)于像網(wǎng)格那樣的規(guī)則數(shù)據(jù)，由于有內(nèi)在的序的關(guān)系，很容易在同一模板上定義具有緊支撐的卷積算子。然而，圖等不規(guī)則數(shù)據(jù)不具有這樣序的關(guān)系，因此無(wú)法在空間上定義這樣的卷積算子。由歐氏空間中的卷積定理可知，兩個(gè)光滑函數(shù)的卷積的傅立葉變換等價(jià)于函數(shù)傅立葉變換后的乘積。因此，目前定義圖卷積的一個(gè)主要思路是先將傅立葉變換推廣到圖結(jié)構(gòu)數(shù)據(jù)上，然后再根據(jù)卷積定理和逆傅立葉變換求得圖譜卷積。另一方面，從計(jì)算上角度出發(fā)，規(guī)則數(shù)據(jù)的卷積運(yùn)算等價(jià)于相關(guān)性計(jì)算，即中心點(diǎn)與周圍網(wǎng)格數(shù)據(jù)的加權(quán)求和，類似地可以將圖上的卷積定義問(wèn)題轉(zhuǎn)化為圖上相關(guān)性計(jì)算的定義問(wèn)題，對(duì)相關(guān)節(jié)點(diǎn)加權(quán)求和，由此引出圖上的空間卷積。類比于傳統(tǒng)的卷積網(wǎng)絡(luò)，當(dāng)定義好卷積層后，可考慮圖上的池化(pooling)操作。對(duì)于圖卷積后結(jié)果應(yīng)該以何種方式聚合最后，不同論文從層次聚類和Weisfeiler-Lehmance測(cè)試[6]等角度給出了不同的池化定義。最后，對(duì)于理論上界定不同圖卷積網(wǎng)絡(luò)的表達(dá)能力的問(wèn)題，已有若干結(jié)果，這些結(jié)果對(duì)于本質(zhì)上理解和搭建圖卷積網(wǎng)絡(luò)具有重要的指導(dǎo)意義。

本文綜述了以圖譜卷積和空間卷積為兩大脈絡(luò)的各圖卷積神經(jīng)網(wǎng)絡(luò)定義與模型沿革，并對(duì)圖上池化操作、圖卷積網(wǎng)絡(luò)表達(dá)能力與實(shí)際應(yīng)用作了相應(yīng)的介紹。本文內(nèi)容順序如下：第1節(jié)為相關(guān)的數(shù)學(xué)符號(hào)與定義，第2節(jié)為圖譜卷積模型，第3節(jié)為空間卷積模型，第4節(jié)介紹圖上池化操作，第5節(jié)為關(guān)于圖卷積網(wǎng)絡(luò)的表達(dá)能力探討，第6節(jié)為相關(guān)實(shí)際應(yīng)用，第7節(jié)為全文總結(jié)。

1 符號(hào)與定義

本小節(jié)將給出后續(xù)內(nèi)容涉及的較為基本的數(shù)學(xué)符號(hào)及其定義，并以表格的形式匯總。

定義3設(shè)f∈Rn為一圖上向量。設(shè)邊e連接節(jié)點(diǎn)vi與vj。定義關(guān)于邊e在節(jié)點(diǎn)vi上的邊導(dǎo)數(shù)為

(1)

或

(2)

同理有邊e在節(jié)點(diǎn)vj上的邊導(dǎo)數(shù)，符號(hào)與上述相反。

記關(guān)于節(jié)點(diǎn)vi的局部波動(dòng)為

(3)

定義關(guān)于f的圖上光滑性為

(4)

事實(shí)上，對(duì)應(yīng)式(1)，有

fTLuf=S(f)

(5)

對(duì)應(yīng)式(2)，有

fTLsf=S(f)

(6)

從而可以用統(tǒng)一形式

fTLf=S(f)

(7)

表達(dá)，依采用的拉普拉斯矩陣L=Lu或L=Ls確定圖上光滑性S(f)對(duì)應(yīng)的邊導(dǎo)數(shù)定義。

定義4面向節(jié)點(diǎn)分類和鏈接預(yù)測(cè)的圖卷積神經(jīng)網(wǎng)絡(luò)通常包括輸入層，卷積層，激活層和輸出層，其結(jié)構(gòu)示意圖如圖2所示。

圖2 面向節(jié)點(diǎn)分類的圖卷積神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)示意圖[8]

此處，輸入層的輸入為圖G，包括節(jié)點(diǎn)信息和邊信息。隱層為卷積層，卷積函數(shù)記為Gconv,根據(jù)不同的卷積算法，Gconv有不同的定義方法。卷積層是圖卷積神經(jīng)網(wǎng)絡(luò)的核心層，下面介紹各種算法時(shí)，重點(diǎn)也是介紹各卷積算子的動(dòng)機(jī)、物理意義和定義形式。在卷積層中，當(dāng)節(jié)點(diǎn)帶有多維屬性時(shí)，通常需要對(duì)屬性進(jìn)行拼接，我們以‖ 表示向量拼接操作，例如x=[x1,…,xn]，y=[y1,…,ym]，則x‖y=[x1,…,xn,y1,…,ym]。激活層是模擬人腦對(duì)接收信息的處理方式，當(dāng)信息的強(qiáng)度大于某一閾值時(shí)，閥門打開，信息通過(guò)，反之，閥門關(guān)閉，信息丟棄。為了方便訓(xùn)練網(wǎng)絡(luò)參數(shù)，激活函數(shù)σ一般定義為非線性的可導(dǎo)函數(shù)，常是有Sigmoid函數(shù)，tanh函數(shù)，Relu函數(shù)等，由于Sigmoid函數(shù)和tanh函數(shù)容易出現(xiàn)梯度消失的問(wèn)題，目前的神經(jīng)網(wǎng)絡(luò)主要使用Relu函數(shù)作為激活函數(shù)，圖2顯示了Relu函數(shù)的形式，需要注意的是，當(dāng)σ作用于向量或矩陣時(shí)，是對(duì)其每一個(gè)元素分別作激活。對(duì)于節(jié)點(diǎn)分類的問(wèn)題，網(wǎng)絡(luò)的輸出層一般為節(jié)點(diǎn)的類標(biāo)或隸屬于各類的概率。

面向圖分類的卷積網(wǎng)絡(luò)，在前述網(wǎng)絡(luò)的基礎(chǔ)上通常會(huì)加多池化(pooling)層和Readout層[9]。圖3顯示了該類網(wǎng)絡(luò)的結(jié)構(gòu)。我們?cè)诤竺鎸ｉT介紹池化層，對(duì)于Readout層，一般是從各節(jié)點(diǎn)的隱層表示中，通過(guò)Readout函數(shù)得到能代表整個(gè)圖的一個(gè)向量，最后對(duì)圖分類轉(zhuǎn)變?yōu)閷?duì)該圖的表示向量進(jìn)行分類。

為便于查看，表1給出了本文所用數(shù)學(xué)符合及其所代表的意義。

圖3 面向圖分類的圖卷積神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)示意圖[8]

表1 符號(hào)表

2 圖譜卷積模型

=U(UTx⊙UTy)

(8)

即將圖上的卷積定義為兩圖上函數(shù)(信號(hào))在圖上頻譜(圖譜)的逐分量相乘后再經(jīng)逆傅立葉變換得到的圖上函數(shù)(信號(hào))。以上圖信號(hào)處理的內(nèi)容圍繞無(wú)向圖展開，事實(shí)上，存在更為廣泛的圖傅立葉變換與圖濾波算子定義[10]。一般卷積層如圖4所示。下面介紹四種經(jīng)典的圖譜卷積網(wǎng)絡(luò)。

圖4 圖卷積網(wǎng)絡(luò)第k層圖例

2.1 Spectral CNN[11]

(9)

2.2 Chebyshev Spectral CNN[12]

(10)

其中g(shù)i,j是某Chebyshev多項(xiàng)式。由于參數(shù)為多項(xiàng)式系數(shù)，與圖的節(jié)點(diǎn)數(shù)無(wú)關(guān)，因此以上定義可用于涉及不同大小的圖分類問(wèn)題。

2.3 CayleyNet[13]

盡管Chebyshev Spectral CNN[13]通過(guò)采用多項(xiàng)式函數(shù)擬合卷積核頻譜系數(shù)函數(shù)減少了計(jì)算復(fù)雜度，但其依舊缺乏關(guān)于頻譜濾波方面的一些理想性質(zhì)。以具有簇結(jié)構(gòu)的圖為例，這些圖上的簇內(nèi)連邊較為密集，簇間連邊較為稀疏，圖信號(hào)在頻譜上的表現(xiàn)為集中在低頻部分。為了在卷積過(guò)程中捕捉到這種信號(hào)的頻帶集中特點(diǎn)，卷積核的頻譜系數(shù)應(yīng)在低頻部分取較大的值，對(duì)卷積核頻譜系數(shù)函數(shù)而言，則應(yīng)與某區(qū)間上的特征函數(shù)I[a,b](x)盡可能相似。文[13]提到了Chebyshev多項(xiàng)式擬合區(qū)間特征函數(shù)所需的參數(shù)量大致與區(qū)間長(zhǎng)度成反比，因而捕捉越短狹的頻帶需要更高階的Chebyshev多項(xiàng)式，從而導(dǎo)致了計(jì)算量的增加。

文[13]提出的CayleyNet通過(guò)結(jié)合Cayley變換與復(fù)系數(shù)多項(xiàng)式函數(shù)的Cayley多項(xiàng)式實(shí)現(xiàn)了低階多項(xiàng)式下的頻帶捕捉。文中的卷積核頻譜函數(shù)被定義為Cayley變換與復(fù)系數(shù)多項(xiàng)式函數(shù)實(shí)部的復(fù)合：

(11)

(12)

gc,h(λ)=c0+2R(p(C(λ))-c0)

(13)

若記C(hL)=(hL-iI)(hL+iI)-1，相應(yīng)的卷積與卷積層定義為：

(14)

(15)

由于Cayley變換的非線性特點(diǎn)，實(shí)軸的任意區(qū)間頻帶[a,b]可通過(guò)調(diào)整h改變映射至復(fù)平面單位環(huán)的放縮程度，從而可以實(shí)現(xiàn)對(duì)特定頻帶的過(guò)濾。

2.4 Graph Convolutional Network (GCN)[14]

對(duì)于圖上的半監(jiān)督問(wèn)題，由于有監(jiān)督樣本的占比往往是比較小的，相應(yīng)模型的復(fù)雜度不應(yīng)過(guò)大，否則易導(dǎo)致對(duì)有監(jiān)督樣本的過(guò)擬合。基于以上考慮，GCN模型極大簡(jiǎn)化了Chebyshev Spectral CNN[12]中Chebyshev多項(xiàng)式函數(shù)的設(shè)置，具體而言，Chebyshev多項(xiàng)式的階數(shù)設(shè)為1，且合并了常數(shù)項(xiàng)與一階項(xiàng)的系數(shù)，并對(duì)圖上各節(jié)點(diǎn)添加自環(huán)，即

(16)

以上四個(gè)圖卷積模型，圍繞圖譜卷積這一主題，從最初簡(jiǎn)單地將頻譜系數(shù)設(shè)為參數(shù)，發(fā)展到定義卷積和頻譜系數(shù)函數(shù)，模型定義逐步改善，模型間具有明顯的邏輯上的先后關(guān)系。表2匯總了以上四個(gè)模型的定義和主要特點(diǎn)。

表2 四種圖譜卷積層

3 圖的空間卷積模型

除圖譜卷積外，另一個(gè)在圖上推廣經(jīng)典卷積定義的思路是仿照經(jīng)典卷積計(jì)算過(guò)程，即圖上空間卷積。經(jīng)典卷積的計(jì)算過(guò)程實(shí)際是同一模板在網(wǎng)格不同位置作加權(quán)求和計(jì)算的結(jié)果，且對(duì)于奇數(shù)長(zhǎng)度的卷積核而言，其涉及計(jì)算范圍實(shí)際上是中心網(wǎng)格與其在八連通網(wǎng)格圖上的k階鄰域。從更一般的角度出發(fā)，經(jīng)典卷積與相關(guān)性計(jì)算是等價(jià)的，卷積的計(jì)算等同于用翻轉(zhuǎn)過(guò)的卷積核計(jì)算空間上的相關(guān)性，因而對(duì)于圖這種不規(guī)則的結(jié)構(gòu)，定義了圖上的相關(guān)性計(jì)算即定義了圖上的空間卷積，由此圖上的卷積的定義問(wèn)題化歸為圖上相關(guān)性計(jì)算的定義問(wèn)題。以下小節(jié)將從隨機(jī)采樣和注意力機(jī)制的角度介紹兩篇較為具有代表性的工作。

3.1 GraphSAGE[16]

圖譜卷積需要在給定圖上定義，因?yàn)闊o(wú)法處理具有變化結(jié)構(gòu)的圖學(xué)習(xí)問(wèn)題，例如動(dòng)態(tài)社交網(wǎng)絡(luò)上的實(shí)體分類。通過(guò)觀察(16)我們可以看出，GCN[20]實(shí)際上是在各節(jié)點(diǎn)的一階鄰域內(nèi)加權(quán)求和，GraphSAGE模型[16]因而從宏觀的角度將圖卷積網(wǎng)絡(luò)的學(xué)習(xí)目標(biāo)定義為結(jié)合圖結(jié)構(gòu)和鄰域節(jié)點(diǎn)的關(guān)于各節(jié)點(diǎn)特征的學(xué)習(xí)，并將圖卷積看做是各節(jié)點(diǎn)與其鄰域內(nèi)節(jié)點(diǎn)的的聚合過(guò)程，即某種意義上的相關(guān)性計(jì)算。在此圖卷積定義下，若相關(guān)性計(jì)算的定義可隨節(jié)點(diǎn)的鄰域的變化而變化，則此卷積定義可應(yīng)用于具有變化結(jié)構(gòu)的圖學(xué)習(xí)問(wèn)題。GraphSAGE[16]將圖卷積層定義為領(lǐng)域表示的獲得和關(guān)于中心節(jié)點(diǎn)與其鄰域表示的結(jié)合，即

(17)

3.2 Graph Attention Network[17]

Graph Attention Network (GAT)模型[17]通過(guò)注意力機(jī)制，將GCN模型中一階鄰域加權(quán)求和的固定權(quán)重改為需要通過(guò)樣本特征表示的變化權(quán)重，使得模型表達(dá)的豐富性和靈活性進(jìn)一步提高。GAT模型[17]中的卷積層定義為

(18)

事實(shí)上，以k階多項(xiàng)式函數(shù)的為頻譜系數(shù)函數(shù)的圖譜卷積實(shí)質(zhì)是在各節(jié)點(diǎn)的k階鄰域求加權(quán)和[7]，因此一部分圖譜卷積模型本身亦是空間卷積模型，但求和權(quán)重固定，測(cè)試樣本和訓(xùn)練樣本需要同時(shí)存在，在半監(jiān)督學(xué)習(xí)框架中屬于直推式學(xué)習(xí)。以上兩空間卷積模型則可看做是對(duì)采取固定加權(quán)求和策略的空間卷積模型的改進(jìn)。這些模型從不同角度放寬空間卷積的定義，基于樣本與其鄰接樣本學(xué)習(xí)卷積定義中的參數(shù)，在放寬定義的同時(shí)保證圖上的有效語(yǔ)義提取，且可用于半監(jiān)督學(xué)習(xí)框架下的歸納式學(xué)習(xí)，但也因此喪失了圖譜卷積中關(guān)于特定頻譜提取的模型可解釋性。表3匯總了迄今為止的大部分圖卷積網(wǎng)絡(luò)模型。

表3 圖卷積網(wǎng)絡(luò)及其卷積層類別[8]

4 圖卷積網(wǎng)絡(luò)中的池化

圖卷積中的鄰域聚合過(guò)程與Weisfeiler-Lehmance測(cè)試[6]在計(jì)算方面十分相似。Weisfeiler-Lehmance測(cè)試是判別兩圖是否同構(gòu)的算法，概括而言，此算法在一輪聚合過(guò)程中先對(duì)每一節(jié)點(diǎn)賦予一特殊字符，并根據(jù)各節(jié)點(diǎn)的一階鄰域內(nèi)各節(jié)點(diǎn)字符構(gòu)造字符串，以對(duì)字符串的哈希結(jié)果作為節(jié)點(diǎn)新的對(duì)應(yīng)字符，兩圖的同構(gòu)與否則通過(guò)比較每一輪聚合后字符集的相同與否判別。圖卷積可類似地看做是以節(jié)點(diǎn)特征作為“連續(xù)型字符”構(gòu)造“連續(xù)型字符串”的過(guò)程，池化操作則是獲取“連續(xù)型字符集”的相關(guān)操作，網(wǎng)絡(luò)依據(jù)池化的結(jié)果進(jìn)行關(guān)于圖的分類，相當(dāng)于“連續(xù)型字符集”之間的比較?；谝陨嫌^點(diǎn)，DGCNN模型[29]將各層圖卷積的結(jié)果合并后排序，截取序列的前k個(gè)節(jié)點(diǎn)作為“連續(xù)型字符集”的表示，并將此截?cái)嘈蛄休斎肫胀ㄒ痪S卷積層和全連接層從而獲得關(guān)于圖的最終表示。

以上例子僅從層次聚類和Weisfeiler-Lehmance測(cè)試的角度介紹了圖上池化定義，限于篇幅，仍有其余方面的工作未被涉及。定義計(jì)算效率更高且在理論上更具有可解釋性的圖上池化定義仍舊是當(dāng)前值得探討的問(wèn)題。

5 圖卷積網(wǎng)絡(luò)的表達(dá)能力

從原理上理解模型各方面能力對(duì)于確定模型關(guān)于具體問(wèn)題的適用性是必要的，且有助于我們分析模型效果的成因，對(duì)于圖卷積網(wǎng)絡(luò)亦不例外。遺憾的是，在數(shù)學(xué)上確立圖卷積模型的能力與模型之間的比較準(zhǔn)則等機(jī)理探討是此前大部分工作所欠缺的。以圖分類為目標(biāo)的圖卷積網(wǎng)絡(luò)為例，大部分模型缺乏對(duì)其能夠區(qū)分的圖的多樣性，即以區(qū)分為目的的模型表達(dá)能力在數(shù)學(xué)上刻畫與證明。

文[35,41]中的結(jié)果改變了以上局面。由于一階鄰域聚合與Weisfeiler-Lehmance測(cè)試在計(jì)算上的天然的相似性所帶來(lái)的啟發(fā)，文[35,41]都證明了Weisfeiler-Lehmance測(cè)試的圖同構(gòu)分辨能力是采用一階鄰域聚合的圖卷積網(wǎng)絡(luò)的上界。文[41]進(jìn)一步證明了存在相應(yīng)的圖卷積網(wǎng)絡(luò)，其表達(dá)能力等價(jià)于Weisfeiler-Lehmance測(cè)試[6]。由于Weisfeiler-Lehmance測(cè)試本身圖同構(gòu)判別能力的限制，文[41]構(gòu)造了近似k維Weisfeiler-Lehmance測(cè)試且表達(dá)能力更為強(qiáng)大的圖卷積網(wǎng)絡(luò)。文[35]中的理論結(jié)果則更為全面。若將Weisfeiler-Lehmance測(cè)試[6]中的哈希過(guò)程解包，則Weisfeiler-Lehmance測(cè)試實(shí)際上是對(duì)以各節(jié)點(diǎn)為根的子樹，或更一般地，對(duì)多重集合進(jìn)行統(tǒng)計(jì)。基于此觀點(diǎn)，若一圖卷積網(wǎng)絡(luò)能夠達(dá)到Weisfeiler-Lehmance測(cè)試的區(qū)分能力，則應(yīng)至少能夠?qū)⒉煌亩嘀丶嫌成涞讲煌闹担淳W(wǎng)絡(luò)為一關(guān)于多重集合的單映射。文[35]證明了圖卷積網(wǎng)絡(luò)網(wǎng)絡(luò)相應(yīng)模塊的單映射性是達(dá)到Weisfeiler-Lehmance測(cè)試區(qū)分能力的充分條件，在此基礎(chǔ)上結(jié)合多層感知機(jī)的逼近能力定義了能夠達(dá)到Weisfeiler-Lehmance測(cè)試區(qū)分能力的GIN模型，并刻畫了其余圖卷積網(wǎng)絡(luò)的缺陷所在，建立了平均池化(對(duì)所有節(jié)點(diǎn)表示取均值)與區(qū)分多重集合分布、最大池化(對(duì)所有節(jié)點(diǎn)取最大值)與區(qū)分多重集合的潛在集(即去重后的集合)之間的對(duì)應(yīng)關(guān)系。

6 圖卷積網(wǎng)絡(luò)的應(yīng)用

由于實(shí)體與節(jié)點(diǎn)、實(shí)體間互動(dòng)與邊的自然對(duì)應(yīng)，現(xiàn)實(shí)中大量數(shù)據(jù)形式是可以由圖表示的，圖卷積網(wǎng)絡(luò)因此具有廣闊的應(yīng)用領(lǐng)域?；ヂ?lián)網(wǎng)應(yīng)用是其中主要的一個(gè)工業(yè)應(yīng)用場(chǎng)景。以推薦系統(tǒng)和惡意賬戶識(shí)別應(yīng)用為例，文[42]利用用戶-物品之間的關(guān)系二分圖與用戶、物品的豐富特征，結(jié)合RW-GCN空間圖卷積網(wǎng)絡(luò)，學(xué)得各用戶、物品的向量表示，以選取近鄰的方式確定推薦給用戶的物品；GEM[43]則將網(wǎng)絡(luò)購(gòu)物系統(tǒng)中的賬戶與賬戶所涉及的設(shè)備(電話號(hào)碼、MAC(media access control address)、IMEI(international mobile equipment identity)、SIM(subscriber identity module)卡號(hào)等)作為節(jié)點(diǎn)，對(duì)每一類設(shè)備單獨(dú)構(gòu)建表示設(shè)備與賬戶活動(dòng)關(guān)系的異構(gòu)設(shè)備二分圖，結(jié)合空間圖卷積網(wǎng)絡(luò)，將各設(shè)備圖上的圖卷積結(jié)果聚合，得到賬戶節(jié)點(diǎn)的類型預(yù)測(cè)結(jié)果，在線下實(shí)驗(yàn)與線上應(yīng)用都取得了十分良好的識(shí)別效果。

圖卷積網(wǎng)絡(luò)在計(jì)算機(jī)視覺(jué)和自然語(yǔ)言處理領(lǐng)域的應(yīng)用亦表現(xiàn)出了不俗的效果。例如STGCN[44]，能夠通過(guò)結(jié)合視頻每幀人體骨架構(gòu)建關(guān)于人體骨架動(dòng)態(tài)變化的時(shí)空?qǐng)D，定義時(shí)空上的卷積從而實(shí)現(xiàn)對(duì)視頻動(dòng)作類型的高準(zhǔn)確率判定；在神經(jīng)機(jī)器翻譯方面，Bastings等[45]通過(guò)在語(yǔ)法樹上定義考慮邊方向與語(yǔ)法類標(biāo)信息的圖卷積網(wǎng)絡(luò)，使得模型能夠利用語(yǔ)料庫(kù)中的語(yǔ)法結(jié)構(gòu)信息，提升了英-德與英-捷克語(yǔ)翻譯的效果；TextGCN[46]通過(guò)定義詞之間和詞與文本之間的特殊邊權(quán)構(gòu)建結(jié)合詞與文本的混合圖，結(jié)合GCN模型實(shí)現(xiàn)文本分類目標(biāo)。

除以上較為常見的應(yīng)用領(lǐng)域外，圖卷積網(wǎng)絡(luò)亦可應(yīng)用其他學(xué)科中的計(jì)算問(wèn)題。如GIN[35]、DGCNN[29]等用于圖分類的圖卷積網(wǎng)絡(luò)自然適用于蛋白質(zhì)圖類型的判別；文[24]利用度量學(xué)習(xí)學(xué)得殘差拉普拉斯矩陣，結(jié)合圖譜卷積模塊，對(duì)化合物分子所涉及得若干指標(biāo)作出估計(jì)；文[47]利用空間圖卷積網(wǎng)絡(luò)作為預(yù)處理模塊，通過(guò)機(jī)器學(xué)習(xí)得方式估計(jì)兩圖之間的編輯距離，高效近似地求解了一NP難問(wèn)題。

我們以文獻(xiàn)網(wǎng)絡(luò)為例詳述圖卷積網(wǎng)絡(luò)在節(jié)點(diǎn)分類問(wèn)題上的表現(xiàn)。文獻(xiàn)網(wǎng)絡(luò)上的節(jié)點(diǎn)分類一般涉及三個(gè)數(shù)據(jù)集：Cora[48]、Citeseer[48]、Pubmed[48]。以上文獻(xiàn)網(wǎng)絡(luò)的圖為無(wú)向圖，圖上的節(jié)點(diǎn)對(duì)應(yīng)文獻(xiàn)，邊對(duì)應(yīng)文獻(xiàn)間的引用關(guān)系且邊權(quán)為1，即兩節(jié)點(diǎn)間存在一條邊當(dāng)且僅當(dāng)兩文獻(xiàn)存在引用關(guān)系。圖5給出了這三個(gè)文獻(xiàn)引用網(wǎng)絡(luò)最大連通分量的平面示意圖。在文獻(xiàn)網(wǎng)絡(luò)節(jié)點(diǎn)分類中，我們需要預(yù)測(cè)無(wú)標(biāo)簽節(jié)點(diǎn)(文獻(xiàn))所屬的類別。表4和表5給出了數(shù)據(jù)集的具體指標(biāo)和以GCN與GAT為代表的圖卷積網(wǎng)絡(luò)在各數(shù)據(jù)集上的分類表現(xiàn)?？梢钥闯?，相對(duì)于沒(méi)有利用圖結(jié)構(gòu)的分類方法(MLP多層感知機(jī))與沒(méi)有利用節(jié)點(diǎn)特征傳統(tǒng)類標(biāo)傳播方法LP[49]，圖神經(jīng)網(wǎng)絡(luò)能夠大幅提升分類準(zhǔn)確率。

圖5 三個(gè)文獻(xiàn)引用網(wǎng)絡(luò)中最大連通分量的平面圖示

7 總結(jié)與展望

本文綜述了圖卷積神經(jīng)網(wǎng)絡(luò)所涉及的理論背景、各網(wǎng)絡(luò)模塊、相關(guān)理論研究與實(shí)際應(yīng)用，以較為具有代表性的工作為例介紹了圖譜卷積網(wǎng)絡(luò)、空間卷積網(wǎng)絡(luò)和相關(guān)模型沿革與對(duì)比。從層次聚類和Weisfeiler-Lehmance測(cè)試的角度介紹了圖上池化模塊，概述了聯(lián)系Weisfeiler-Lehmance測(cè)試與圖卷積網(wǎng)絡(luò)表達(dá)能力的理論工作，并簡(jiǎn)單介紹了圖卷積神經(jīng)網(wǎng)絡(luò)的應(yīng)用實(shí)例。圖卷積神經(jīng)網(wǎng)絡(luò)的出現(xiàn)正值當(dāng)前的深度學(xué)習(xí)熱潮，由于其理論的開拓性與潛在應(yīng)用的廣泛性，相關(guān)的理論與應(yīng)用研究日益受到重視，未來(lái)圖卷積神經(jīng)網(wǎng)絡(luò)必將擁有廣闊的應(yīng)用前景。

表4 數(shù)據(jù)集指標(biāo)

表5 準(zhǔn)確率[14,17]