用于非精確圖匹配的改進注意圖卷積網絡

李昌華，劉 藝，李智杰

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

1 引 言

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

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

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

2 基于圖卷積網絡的圖匹配算法

2.1 圖匹配問題

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

2.2 傳統圖卷積網絡

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

(1)

2.3 池化方法

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

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

3 基于改進注意圖網絡的圖匹配算法

3.1 自注意機制

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

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

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

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

3.2 提出的算法模型

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

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

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

3.3 注意圖卷積模型

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

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

(2)

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

(3)

(4)

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

3.4 自注意池化

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

β=softmax(u2tanh(u1GT))

(5)

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

B=softmax(u2tanh(u1GT))

(6)

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

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

(7)

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

Y=softmax(ZM+C)

(8)

具體算法步驟如下：

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

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

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

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

7)使用隨機梯度更新所有的權重參數.

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

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

4 實驗結果與分析

4.1 數據集

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

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

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

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

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

·D&D[12]：D&D數據集是1178種蛋白質結構的數據集，分為酶和非酶.

表1 各個數據集的基本信息Table 1 Basic information of each data set

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

4.2 實驗設置

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

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

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

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

表2 實驗環境及配置Table 2 Experimental environment and configuration

4.3 實驗結果

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

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

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

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

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

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

4.4 結果分析

4.4.1 復雜度對比

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

4.4.2 圖識別結果的比較

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

5 結束語

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