用于非精確圖匹配的改進注意圖卷積網(wǎng)絡(luò)

李昌華，劉 藝，李智杰

(西安建筑科技大學 信息與控制工程學院，西安 710055)

1 引 言

圖結(jié)構(gòu)信息在生活中普遍存在，例如，社交網(wǎng)絡(luò)，生物網(wǎng)絡(luò)和分子結(jié)構(gòu)等都可以由圖的節(jié)點和邊表示.研究人員已經(jīng)在圖中以監(jiān)督和非監(jiān)督的方式對許多重要的機器學習應(yīng)用進行了廣泛的研究[1],例如圖像分類、自然語言處理、強化學習以及推薦系統(tǒng)，但圖數(shù)據(jù)的復雜性給許多任務(wù)帶來了巨大的挑戰(zhàn).由于從大量圖數(shù)據(jù)中獲取有意義的信息的重要性，其中圖分類問題是該領(lǐng)域的中心任務(wù)之一.目前，最受歡迎的技術(shù)是核方法：1)圖嵌入算法，將圖結(jié)構(gòu)嵌入到向量空間,得到圖結(jié)構(gòu)的向量化表示，然后直接應(yīng)用基于向量的核函數(shù)處理，但是這類方法將結(jié)構(gòu)化數(shù)據(jù)降維到向量空間損失了大量結(jié)構(gòu)化信息；2)圖核算法，它使用核函數(shù)來測量圖之間的半正定圖相似性[2].然后可以在相似性矩陣上進行分類任務(wù).通過使用支持向量機[3]等監(jiān)督算法.通過將圖分解為子結(jié)構(gòu)，圖核能夠直接處理圖數(shù)據(jù)而無需將其轉(zhuǎn)換為特征向量.既保留了核函數(shù)計算高效的優(yōu)點，又包含了圖數(shù)據(jù)在希爾伯特高維空間的結(jié)構(gòu)化信息，使得它在節(jié)點分類、鏈路預測、節(jié)點聚類等方面取得了巨大成功.然而，基于圖核的算法仍然受到自然限制.近年來，基于深度學習的方法(如圖神經(jīng)網(wǎng)絡(luò))也已廣泛應(yīng)用于網(wǎng)絡(luò)表示，并被證明大大優(yōu)于傳統(tǒng)方法.GNN可以了解數(shù)據(jù)的局部結(jié)構(gòu)和特征.該模型可以直接對圖數(shù)據(jù)進行特征學習.但是，雖然圖結(jié)構(gòu)數(shù)據(jù)保留了更多的關(guān)系信息，與其他數(shù)據(jù)格式相比，它也會產(chǎn)生更復雜的噪聲.如何在篩選圖中每個節(jié)點的復雜噪聲引起的干擾的同時學習良好的表示已成為一項重大挑戰(zhàn).

圖數(shù)據(jù)在很多方面都很復雜;例如，當尺寸變化時，不同子圖的拓撲結(jié)構(gòu)信息是變化無常的.處理這種分散的信息時，大多數(shù)現(xiàn)有的圖神經(jīng)網(wǎng)絡(luò)框架受到兩個因素的限制：1)當只使用最大的子圖結(jié)構(gòu)用于鄰域聚合時，在圖卷積中容易丟失早期提取的重要信息;2)使用平均/最大池化時，易損失每個節(jié)點或節(jié)點之間的拓撲.

本文通過在圖卷積運算中引入自注意技術(shù)，以捕獲圖中的任意局部結(jié)構(gòu)信息，提出自注意分層圖池化的方法，用較少的參數(shù)以端到端的方式學習分層表示，用于圖分類任務(wù).

2 基于圖卷積網(wǎng)絡(luò)的圖匹配算法

2.1 圖匹配問題

本文研究的圖對象是指拓撲圖，它是由節(jié)點和邊組成的網(wǎng)絡(luò).圖可以表示為g=(Vg,Eg,Ag,Xg)，其中Vg是頂點集合vi,i= 1,…,n.Eg表示節(jié)點之間的邊，表示為ei,j= ∈E,i≠j.未加權(quán)鄰接矩陣Ag∈{0,1}Ni×Ni，Ni是圖gi的大小.X∈Rn×c表示與每個節(jié)點vi相關(guān)聯(lián)的c個信道的類標簽.給定一組圖G=(g1,g2,…,gn)，其標簽為Y=(y1,y2,…,yn)，所以本文的圖分類匹配問題其實是學習函數(shù)f(gi)→yi∈L，其中L= {c1,…,c|L|}是圖的類標簽.在本文中，將提出一種新的圖卷積網(wǎng)絡(luò)，它在節(jié)點級和圖上都采用雙重注意，用于解決圖的分類匹配問題.

2.2 傳統(tǒng)圖卷積網(wǎng)絡(luò)

圖卷積有許多定義.其他類型的圖卷積可以提高性能.具有k深度的圖卷積的一般形式可以通過廣泛遵循的卷積結(jié)構(gòu)遞歸地表達，表示為：

(1)

2.3 池化方法

圖卷積層的池化方法有全局池化和分層池化[4].圖1是全局池化和分層池化的結(jié)構(gòu)圖.目前，常用的圖神經(jīng)網(wǎng)絡(luò)是利用傳統(tǒng)的圖卷積方法，使用全局池化的方法，即將每一跳的結(jié)果都作為下一步的輸入，然后將最終結(jié)果輸入線性聚合層中(即全局池化)，缺點是隨著層數(shù)的增加，在每個卷積步驟期間丟失大量早期信息，這嚴重影響最終預測輸出(僅僅是k-hop的子結(jié)構(gòu)信息)(如左圖所示).本文提出的自注意圖卷積池化方法，使用分層池化的方法，即通過將每個卷積步驟的信息進行聚合，從每一跳中獲取有用信息，最終結(jié)果輸入到線性層來解決該問題(如右圖所示).

圖1 全局池化結(jié)構(gòu)(左)和分層池化結(jié)構(gòu)(右)Fig.1 Global pooling structure(left)and hierarchical pooling structure(right)

3 基于改進注意圖網(wǎng)絡(luò)的圖匹配算法

3.1 自注意機制

近年來，注意力模型廣泛應(yīng)用于深度學習的各個領(lǐng)域，例如，圖像處理、語音識別、自然語言處理等領(lǐng)域.因此，了解注意力機制對研究人員來說十分重要.

注意力機制最早是在視覺領(lǐng)域內(nèi)提出來的，2014年google mind團隊[5]在RNN模型上中應(yīng)用Attention機制用于圖像分類，隨后，Bahdanau將Attention機制運用到自然語言處理領(lǐng)域上，后來，Attention機制被廣泛的應(yīng)用于基于RNN和CNN等網(wǎng)絡(luò)模型中，用于NLP領(lǐng)域中.2017年，Vaswani等人[6]提出了自注意力機制，用來學習文本表示.自此，自注意力機制成為研究人員近幾年來研究的熱點.

Attention機制其實是從大量信息中篩選出對當前任務(wù)目標中更有效的信息.下面給出Attention的計算過程，如在NLP中，在計算attention時主要分為3步，第1步是將查詢和每個鍵-值進行相似度計算得到權(quán)重，常用的相似度函數(shù)有點積、拼接、感知機等；然后第2步一般是使用一個softmax函數(shù)對這些權(quán)重進行歸一化；最后將權(quán)重和相應(yīng)的鍵值、進行加權(quán)求和得到最后的attention.

自注意機制是注意力機制的一種特殊情況，在self-attention中，Q=K=V每個序列中的單元和該序列中所有單元進行attention計算[7].

3.2 提出的算法模型

為了解決傳統(tǒng)圖卷積網(wǎng)絡(luò)模型的缺點，提出了一種新的雙重注意圖卷積網(wǎng)絡(luò)(Dual Attention Graph Convolutional Networks,DAGCN).它主要是由兩個模塊組成.即注意圖卷積模塊和自注意池化層.DAGCN的工作原理如下：首先通過利用注意圖卷積網(wǎng)絡(luò)來自動學習子圖結(jié)構(gòu)(k-hop neighbor)，其次，再加入自注意池化層，將最終圖嵌入矩陣M發(fā)送到線性層以進行最終預測.

·注意圖卷積模塊 注意圖卷積模塊由幾個注意圖卷積層構(gòu)成.每個層采用特征X和鄰接矩陣A來從不同跳的鄰域提取頂點的分層局部子結(jié)構(gòu)特征.

·自注意池化層 注意池層使用節(jié)點嵌入來學習不同方面的多個圖表示，并輸出固定大小的矩陣圖嵌入.

3.3 注意圖卷積模型

在公式(1)中，除了Hk之外，每個步驟中的結(jié)果只能用于生成下一個卷積結(jié)果.隨著卷積層數(shù)的增加，將丟失大量早期信息，并且只有最后的卷積結(jié)果Hk(代表最大的子圖)可用于后續(xù)任務(wù).這種操作可能會導致嚴重的信息丟失.卷積層僅捕獲k跳本地結(jié)構(gòu).

DAGCN模型中的注意圖卷積層旨在通過集中聚合來自每個卷積步驟的信息來解決該問題.不僅依賴于k-hop卷積結(jié)果，而且還可以從每一跳中捕獲有價值的信息.因此，卷積結(jié)果將是包含來自不同跳躍卷積過程的最有價值信息的分層表示.分層節(jié)點表示γvn表示如下：

(2)

為了最大化深度學習的優(yōu)勢并學習更深層次的潛在特征，使用殘差學習技術(shù)來疊加注意卷積層并開發(fā)注意圖卷積模塊以獲得更好的最終節(jié)點表示γvn.每個注意圖卷積層的輸入是前一層輸出和原始X的總和.最后，使用一個密集層來處理來自每個卷積層的輸出組合.

(3)

(4)

其中Dense()是一個密集層，它結(jié)合了每個注意圖卷積層的輸出.

3.4 自注意池化

注意機制已被廣泛用于最近的深度學習研究中[5-7].目的是將任意圖編碼為固定大小的嵌入矩陣，同時最大化節(jié)點表示下的信息.本文通過將從卷積模塊獲知的圖的節(jié)點表示作為輸入來使用注意力機制來輸出權(quán)重向量α.

β=softmax(u2tanh(u1GT))

(5)

在該公式中，u1和u2是分別具有c-by-c和c-by-r形狀的權(quán)重矩陣，其中r是針對子空間的數(shù)量設(shè)置的超參數(shù)，以從節(jié)點表示學習圖表示.當r≥1時，α變?yōu)闄?quán)重矩陣而不是矢量，然后可以將公式(5)寫為:

B=softmax(u2tanh(u1GT))

(6)

圖2 DAGCN算法流程圖Fig.2 DAGCN algorithm flow chart

B的每一行代表一個節(jié)點在不同子空間中的權(quán)重.softmax函數(shù)沿其輸入的第二維執(zhí)行.然后，根據(jù)來自公式(6)的B進行加權(quán)求和，以獲得具有形狀n-by-r的圖表示矩陣M.

(7)

最后，一個完全連接的層后面跟著一個softmax層，以M為輸入，得到了最終的分類結(jié)果Y，完成圖的分類.

Y=softmax(ZM+C)

(8)

具體算法步驟如下：

1)給定數(shù)據(jù)集X={x1,x2,…,xn}，給定A,T,K,M，其中T是迭代更新，A是無權(quán)重鄰接矩陣，vn是節(jié)點Vn的特征向量，K是卷積運算中hop的數(shù)量，M是注意圖卷積層的數(shù)量.

4)利用公式(4)計算所有節(jié)點vn∈g的歸一化最終節(jié)點表示γvn,

5)公式(6)得出歸一化注意力池化層的系數(shù)矩陣M.

6)利用公式(7)計算圖g的權(quán)重之和.

7)使用隨機梯度更新所有的權(quán)重參數(shù).

8)迭代結(jié)束后，公式(8)得出Y∈Rn*|c|.

具體的算法流程圖如圖2所示.

4 實驗結(jié)果與分析

4.1 數(shù)據(jù)集

本文使用5個基準生物信息學數(shù)據(jù)集，根據(jù)圖分類任務(wù)的準確性來評估DAGCN模型(比較DAGCN與圖核的圖分類精度).使用的數(shù)據(jù)集是：

·NCI1[8]：NCI是用于抗癌活性分類的生物學數(shù)據(jù)集.其中原子代表節(jié)點，化學鍵代表邊.NCI1數(shù)據(jù)集分別包含4100個化合物，標簽是判斷化合物是否有阻礙癌細胞增長得性質(zhì).

·MUTAG[9]：MUTAG數(shù)據(jù)集包含188個硝基化合物，標簽是判斷化合物是芳香族還是雜芳族.

·PROTEINS[10]：蛋白質(zhì)是一個圖形集合，其中的節(jié)點是二級結(jié)構(gòu)元素，邊緣表示氨基酸序列或3D空間中的鄰域.圖分類為酶或非酶.

·PTC[11]：PTC數(shù)據(jù)集由344種化合物組成，其類別表明對雄性和雌性大鼠有致癌性.

·D&D[12]：D&D數(shù)據(jù)集是1178種蛋白質(zhì)結(jié)構(gòu)的數(shù)據(jù)集，分為酶和非酶.

表1 各個數(shù)據(jù)集的基本信息Table 1 Basic information of each data set

表1是各個數(shù)據(jù)集的基本信息，其中Nodes_max表示數(shù)據(jù)集中拓撲圖的最大節(jié)點數(shù)，Nodes_avg表示數(shù)據(jù)集的平均節(jié)點數(shù)，Graphs表示數(shù)據(jù)集中包含的圖的數(shù)量.

4.2 實驗設(shè)置

將DAGCN與兩個最經(jīng)典的圖核算法、與4種最先進的GCN進行比較：

·圖核算法：a)the SP kernel(SP)[13]，b)the Weisfeiler-Lehman(WL)[7].

·g-CNNs方法：PSCN[10],ECC[14]

對于圖核參數(shù)，按照常規(guī)設(shè)置，采用了與以前工作相同的程序，以便進行公平的比較.所有密集層和卷積層的隱藏層大小設(shè)置為64，k從集合{1,5,10}中選擇，并且所選擇的跳數(shù)是k∈{3,5,10}.本文使用Adam[15]優(yōu)化策略，其中L2正則化和學習率從{0.01,0.001,0.0001}中選擇，以確保模型的最佳發(fā)揮.批量大小固定為50，并且進行10倍交叉驗證(訓練9倍，測試1倍)，以報告平均分類準確度和標準偏差.WL的高度參數(shù)選自集合{0,1,2,3,4,5}.其他的結(jié)果來自文獻[13].所有實驗設(shè)置都是相同的，以便進行公平的比較.本文中所有實驗環(huán)境及配置如表2所示.

表2 實驗環(huán)境及配置Table 2 Experimental environment and configuration

4.3 實驗結(jié)果

表3顯示了比較深度學習方法的平均分類準確度.表中的“-”表示源代碼不可用或先前的報告不包含相關(guān)結(jié)果.從結(jié)果中可以看出，DAGCN模型在5個數(shù)據(jù)集中，始終優(yōu)于其他深度學習方法，在D&D上排名第2.特別是，NCI1的分類準確度提高了7%，其他3個數(shù)據(jù)集(不包括D&D)的準確度提高了1%-3%.在每種情況下，DAGCN都優(yōu)于PSCN和ECC，證明了簡單求和節(jié)點特征是無效的，并且會導致拓撲信息的丟失.PSCN與DAGCN在PROTEINS和PTC上的模型大致相同，但在NCI1上糟糕，因為它更有可能過度擬合預定義的節(jié)點排序.通過使用注意池化避免這個問題，注意池動態(tài)地學習圖上的有價值的節(jié)點分布.

表3 深度學習算法的平均分類準確率Table 3 Average classification accuracy of deep learning algorithms

表4顯示了比較圖核算法的平均分類準確度.將DAGCN模型與最先進的圖核算法進行比較，由表4可知，盡管所有數(shù)據(jù)集都使用了單一結(jié)構(gòu)，但DAGCN與最先進的圖核非常競爭，其中包括MUTAG，PROTEINS和D&D的準確性最高.與WL相比，DAGCN在所有數(shù)據(jù)集上的精度都更高(除NCI1外)，這表明DAGCN能夠更有效地利用節(jié)點和結(jié)構(gòu)信息.

為了評價分類效率，進行對比實驗，可用一些指標(錯誤率，準確率，召回率等)對模型進行評價(如圖3所示).

表4 圖核算法的平均分類準確率Table 4 Average classification accuracy of the graph kernel algorithm

圖3 4種算法的分類識別率Fig.3 Classification recognition rate of four algorithm

4.4 結(jié)果分析

4.4.1 復雜度對比

圖核首先需要計算訓練中每兩個圖之間的相似度數(shù)據(jù)集以形成相似性矩陣.給定大小的數(shù)據(jù)集N，則需要N(N- 1)/2個計算步驟.當數(shù)據(jù)集的大小時，這個數(shù)字隨著數(shù)據(jù)集的尺寸的增加呈指數(shù)增長.另外，計算一對圖之間的相似度也是基于圖中的節(jié)點數(shù).這限制了圖核僅適用于小型數(shù)據(jù)集.通過設(shè)計，DAGCN的計算復雜度數(shù)據(jù)集大小和圖的大小均線性增長.

4.4.2 圖識別結(jié)果的比較

本文利用圖的識別率指標比較了DAGCN和現(xiàn)有方法.本文將密集隱藏層的輸出用作圖數(shù)據(jù)的特征向量.由圖3可知，在PTC，PROTEIN，NCI1和MUTAG數(shù)據(jù)集上，DAGCN優(yōu)于其他方法.DAGCN在大多數(shù)數(shù)據(jù)集上均優(yōu)于最近提出的g-CNN方法，因為對節(jié)點鄰域進行正則化的過程會導致丟失有關(guān)節(jié)點鄰域的信息，提出的DAGCN模型消除了節(jié)點鄰域正則化期間的本地信息丟失.

5 結(jié)束語

在本文中，提出了一種新的雙重注意圖卷積網(wǎng)絡(luò)(DAGCN)模型，其核心思想是最大限度地利用圖輸入的原始信息.使用注意機制來解決傳統(tǒng)GCN模型的弱點.DAGCN模型中的注意力卷積層能夠捕獲比其他模型更多的層次結(jié)構(gòu)信息，并提供單個節(jié)點和整個圖的更多信息表示.注意力池層通過使用自注意機制來關(guān)注圖的不同方面，生成固定大小的圖嵌入矩陣.實驗結(jié)果表明，DAGCN模型在多個標準數(shù)據(jù)集中優(yōu)于其他深度學習方法和大多數(shù)圖核.