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

李昌華，劉 藝，李智杰

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

1 引 言

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

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

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

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

2.1 圖匹配問(wèn)題

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

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

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

(1)

2.3 池化方法

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

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

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

3.1 自注意機(jī)制

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

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

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

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

3.2 提出的算法模型

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

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

·自注意池化層 注意池層使用節(jié)點(diǎn)嵌入來(lái)學(xué)習(xí)不同方面的多個(gè)圖表示，并輸出固定大小的矩陣圖嵌入.

3.3 注意圖卷積模型

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

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

(2)

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

(3)

(4)

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

3.4 自注意池化

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

β=softmax(u2tanh(u1GT))

(5)

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

B=softmax(u2tanh(u1GT))

(6)

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

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

(7)

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

Y=softmax(ZM+C)

(8)

具體算法步驟如下：

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

本文使用5個(gè)基準(zhǔn)生物信息學(xué)數(shù)據(jù)集，根據(jù)圖分類任務(wù)的準(zhǔn)確性來(lái)評(píng)估DAGCN模型(比較DAGCN與圖核的圖分類精度).使用的數(shù)據(jù)集是：

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

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

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

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

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

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

表1是各個(gè)數(shù)據(jù)集的基本信息，其中Nodes_max表示數(shù)據(jù)集中拓?fù)鋱D的最大節(jié)點(diǎn)數(shù)，Nodes_avg表示數(shù)據(jù)集的平均節(jié)點(diǎn)數(shù)，Graphs表示數(shù)據(jù)集中包含的圖的數(shù)量.

4.2 實(shí)驗(yàn)設(shè)置

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

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

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

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

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

4.3 實(shí)驗(yàn)結(jié)果

表3顯示了比較深度學(xué)習(xí)方法的平均分類準(zhǔn)確度.表中的“-”表示源代碼不可用或先前的報(bào)告不包含相關(guān)結(jié)果.從結(jié)果中可以看出，DAGCN模型在5個(gè)數(shù)據(jù)集中，始終優(yōu)于其他深度學(xué)習(xí)方法，在D&D上排名第2.特別是，NCI1的分類準(zhǔn)確度提高了7%，其他3個(gè)數(shù)據(jù)集(不包括D&D)的準(zhǔn)確度提高了1%-3%.在每種情況下，DAGCN都優(yōu)于PSCN和ECC，證明了簡(jiǎn)單求和節(jié)點(diǎn)特征是無(wú)效的，并且會(huì)導(dǎo)致拓?fù)湫畔⒌膩G失.PSCN與DAGCN在PROTEINS和PTC上的模型大致相同，但在NCI1上糟糕，因?yàn)樗锌赡苓^(guò)度擬合預(yù)定義的節(jié)點(diǎn)排序.通過(guò)使用注意池化避免這個(gè)問(wèn)題，注意池動(dòng)態(tài)地學(xué)習(xí)圖上的有價(jià)值的節(jié)點(diǎn)分布.

表3 深度學(xué)習(xí)算法的平均分類準(zhǔn)確率Table 3 Average classification accuracy of deep learning algorithms

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

為了評(píng)價(jià)分類效率，進(jìn)行對(duì)比實(shí)驗(yàn)，可用一些指標(biāo)(錯(cuò)誤率，準(zhǔn)確率，召回率等)對(duì)模型進(jìn)行評(píng)價(jià)(如圖3所示).

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

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

4.4 結(jié)果分析

4.4.1 復(fù)雜度對(duì)比

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

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

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

5 結(jié)束語(yǔ)

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