鄭睿剛 ，陳偉福 , 馮國燦

(1. 中山大學數(shù)學學院，廣東 廣州 510275；2. 中山大學廣東省計算科學重點實驗室，廣東 廣州 510275)

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

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

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

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

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

本文綜述了以圖譜卷積和空間卷積為兩大脈絡的各圖卷積神經網絡定義與模型沿革，并對圖上池化操作、圖卷積網絡表達能力與實際應用作了相應的介紹。本文內容順序如下：第1節(jié)為相關的數(shù)學符號與定義，第2節(jié)為圖譜卷積模型，第3節(jié)為空間卷積模型，第4節(jié)介紹圖上池化操作，第5節(jié)為關于圖卷積網絡的表達能力探討，第6節(jié)為相關實際應用，第7節(jié)為全文總結。

1 符號與定義

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

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

(1)

或

(2)

同理有邊e在節(jié)點vj上的邊導數(shù)，符號與上述相反。

記關于節(jié)點vi的局部波動為

(3)

定義關于f的圖上光滑性為

(4)

事實上，對應式(1)，有

fTLuf=S(f)

(5)

對應式(2)，有

fTLsf=S(f)

(6)

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

fTLf=S(f)

(7)

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

定義4面向節(jié)點分類和鏈接預測的圖卷積神經網絡通常包括輸入層，卷積層，激活層和輸出層，其結構示意圖如圖2所示。

圖2 面向節(jié)點分類的圖卷積神經網絡結構示意圖[8]

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

面向圖分類的卷積網絡，在前述網絡的基礎上通常會加多池化(pooling)層和Readout層[9]。圖3顯示了該類網絡的結構。我們在后面將專門介紹池化層，對于Readout層，一般是從各節(jié)點的隱層表示中，通過Readout函數(shù)得到能代表整個圖的一個向量，最后對圖分類轉變?yōu)閷υ搱D的表示向量進行分類。

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

圖3 面向圖分類的圖卷積神經網絡結構示意圖[8]

表1 符號表

2 圖譜卷積模型

=U(UTx⊙UTy)

(8)

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

圖4 圖卷積網絡第k層圖例

2.1 Spectral CNN[11]

(9)

2.2 Chebyshev Spectral CNN[12]

(10)

其中gi,j是某Chebyshev多項式。由于參數(shù)為多項式系數(shù)，與圖的節(jié)點數(shù)無關，因此以上定義可用于涉及不同大小的圖分類問題。

2.3 CayleyNet[13]

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

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

(11)

(12)

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

(13)

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

(14)

(15)

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

2.4 Graph Convolutional Network (GCN)[14]

對于圖上的半監(jiān)督問題，由于有監(jiān)督樣本的占比往往是比較小的，相應模型的復雜度不應過大，否則易導致對有監(jiān)督樣本的過擬合?；谝陨峡紤]，GCN模型極大簡化了Chebyshev Spectral CNN[12]中Chebyshev多項式函數(shù)的設置，具體而言，Chebyshev多項式的階數(shù)設為1，且合并了常數(shù)項與一階項的系數(shù)，并對圖上各節(jié)點添加自環(huán)，即

(16)

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

表2 四種圖譜卷積層

3 圖的空間卷積模型

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

3.1 GraphSAGE[16]

圖譜卷積需要在給定圖上定義，因為無法處理具有變化結構的圖學習問題，例如動態(tài)社交網絡上的實體分類。通過觀察(16)我們可以看出，GCN[20]實際上是在各節(jié)點的一階鄰域內加權求和，GraphSAGE模型[16]因而從宏觀的角度將圖卷積網絡的學習目標定義為結合圖結構和鄰域節(jié)點的關于各節(jié)點特征的學習，并將圖卷積看做是各節(jié)點與其鄰域內節(jié)點的的聚合過程，即某種意義上的相關性計算。在此圖卷積定義下，若相關性計算的定義可隨節(jié)點的鄰域的變化而變化，則此卷積定義可應用于具有變化結構的圖學習問題。GraphSAGE[16]將圖卷積層定義為領域表示的獲得和關于中心節(jié)點與其鄰域表示的結合，即

(17)

3.2 Graph Attention Network[17]

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

(18)

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

表3 圖卷積網絡及其卷積層類別[8]

4 圖卷積網絡中的池化

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

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

5 圖卷積網絡的表達能力

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

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

6 圖卷積網絡的應用

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

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

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

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

圖5 三個文獻引用網絡中最大連通分量的平面圖示

7 總結與展望

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

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

表5 準確率[14,17]