侯雅靜,寧 博,海 潮,周 新,楊 超,李冠宇

1(大連海事大學(xué) 信息科學(xué)技術(shù)學(xué)院,遼寧 大連 116000)

2(國網(wǎng)遼寧信通公司,沈陽 110000)

1 引 言

互聯(lián)網(wǎng)的飛速發(fā)展產(chǎn)生了大量復(fù)雜并且相互關(guān)聯(lián)的數(shù)據(jù),這些數(shù)據(jù)通?？梢杂脠D結(jié)構(gòu)進(jìn)行表示.但如何高效地存儲和查詢這些圖數(shù)據(jù)一直以來都是一個研究熱點.圖數(shù)據(jù)具有強(qiáng)大的表達(dá)力,能夠很好地表示對象屬性以及對象之間的關(guān)系,因此圖相似性計算廣泛應(yīng)用于圖相似搜索和圖數(shù)據(jù)庫分析[1],例如計算機(jī)視覺中的圖像分類,疾病預(yù)測的蛋白相互作用網(wǎng)絡(luò)分析,計算機(jī)安全中的二元函數(shù)相似性搜索等.這些實際應(yīng)用的核心操作是計算兩個圖之間的距離/相似性.

如圖1所示,用熱力圖展示9個圖數(shù)據(jù)G0～G8之間的相似性,熱力圖越深表示相似性越高.熱力圖1(b)中的坐標(biāo)軸0～8分別對應(yīng)圖1(a)中G0～G8.

圖1 熱力圖展示圖數(shù)據(jù)之間的相似性

傳統(tǒng)方法采用多種度量指標(biāo)來計算圖相似性,例如圖編輯距離(Graph Edit Distance,GED)[2],最大公共子圖、圖同構(gòu)和圖核函數(shù)等.然而,這些度量的計算通常是一個NP完全問題[3],計算成本非常高.目前最常用的衡量圖相似性的指標(biāo)是基于編輯距離的圖相似,與其他度量不同,圖編輯距離具有以下3個優(yōu)勢:1)GED適用于各種類型的圖,它可以精確地捕獲任意類型圖之間的結(jié)構(gòu)與標(biāo)簽差異;2)GED具有通用性,其中最大公共子圖可以視為它的特殊情況;3)GED可以廣泛應(yīng)用在各種不同的領(lǐng)域,例如計算機(jī)視覺的圖像分類,化合物的分子分析等等.

在解決圖相似搜索問題中,主要分為兩大類方法:第1類方法使用過濾-驗證框架[4],過濾-驗證框架主要是通過迅速且粗略地計算查詢圖與數(shù)據(jù)圖之間的編輯距離,通過設(shè)定的圖編輯距離閾值進(jìn)行過濾,進(jìn)一步獲取到符合條件的數(shù)據(jù)圖的集合,然后再對集合中的數(shù)據(jù)圖進(jìn)行驗證;第2類方法是求解圖相似性的近似值[5],這種方法通常需要基于離散優(yōu)化或組合搜索的方式設(shè)計和實現(xiàn).降低了圖相似性計算的成本.同時,深度學(xué)習(xí)的快速發(fā)展為圖相似性計算提供新的思路,一些學(xué)者將圖相似性計算轉(zhuǎn)化為學(xué)習(xí)問題,具體是將輸入的一對圖映射為相似性的分?jǐn)?shù),其關(guān)鍵技術(shù)包括:1)表示圖數(shù)據(jù)的圖嵌入模型;2)圖嵌入的相似性計算模型.經(jīng)典的圖嵌入方法[6],可分為矩陣分解、深度學(xué)習(xí)、基于邊重構(gòu)的優(yōu)化、深度圖核與生成模型.并且隨著深度學(xué)習(xí)技術(shù)的發(fā)展,圖神經(jīng)網(wǎng)絡(luò)(Graph Neural Networks,GNN)[7]逐漸運(yùn)用于圖相似性計算.注意力模型(Attention Model)[8]也被廣泛使用在自然語言處理、圖像識別及語音識別等各種不同類型的深度學(xué)習(xí)任務(wù)中,注意力模型逐漸與神經(jīng)網(wǎng)絡(luò)緊密相連,并應(yīng)用在各種不同的領(lǐng)域中.如今,雖然有許多不同的圖嵌入方法被提出,但現(xiàn)有的大部分研究工作從圖的節(jié)點嵌入[9]或圖級嵌入[10]層面來對圖進(jìn)行表示,不能全面表示圖信息,如何有效提取圖上的信息仍然是一個極具挑戰(zhàn)性的任務(wù).為了能夠更好地表示圖的全局信息,本文采用了圖神經(jīng)網(wǎng)絡(luò)與注意力機(jī)制分別從節(jié)點嵌入與圖級嵌入兩個層面來表示圖數(shù)據(jù),并采用神經(jīng)張量網(wǎng)絡(luò)模型計算圖嵌入之間的相似性.

本文的貢獻(xiàn)總結(jié)如下:

1.提出了一個端到端的圖相似性計算模型NAGSim(Neural Networks and Attention Graph Similarity),該模型利用注意力機(jī)制與圖神經(jīng)網(wǎng)絡(luò)來進(jìn)行圖相似性計算,改進(jìn)了成對圖相似性計算的準(zhǔn)確性.

2.使用圖注意力網(wǎng)絡(luò)(Graph Attention Network,GAT)[11]與自注意力匯聚(Self-attention Graph Pooling,SAGPooL)[12]來生成圖的節(jié)點級嵌入,更好地保留了圖的全局特征,提升圖嵌入的表達(dá)能力.

3.為了生成輸入圖的圖級嵌入,本文采用了注意力機(jī)制來更好地聚合節(jié)點的特征,NAGSim根據(jù)卷積匯聚之后所保留的節(jié)點特征進(jìn)行計算,圖中的重要節(jié)點被分配更多的權(quán)重.將節(jié)點嵌入聚合為輸入圖的圖級嵌入.

4.基于真實的數(shù)據(jù)集實驗結(jié)果證明NAGSim的有效性,相比于傳統(tǒng)算法與現(xiàn)有的端到端學(xué)習(xí)模型,NAGSim的運(yùn)行時間更低,同時具有更高的準(zhǔn)確性.

2 相關(guān)工作

基于圖神經(jīng)網(wǎng)絡(luò)的相似性學(xué)習(xí),是以端到端的方式執(zhí)行相似性學(xué)習(xí)任務(wù),與此同時采用GNN學(xué)習(xí)圖的表示.例如,成對的輸入圖(GA,GB,yAB),其中yAB表示(GA,GB)實際的相似性得分,基于GNN的圖相似學(xué)習(xí)方法首先是采用多層GNN來學(xué)習(xí)圖的表示,對于編碼空間中的GA和GB,一對圖上每個圖的表示學(xué)習(xí)可能會通過某些機(jī)制而產(chǎn)生相影響,例如權(quán)重分配和兩個圖之間的GNN跨圖交互.GNN層將為每個圖輸出矩陣或矢量表示,然后添加點積層或全連接層用于預(yù)測兩圖之間的相似性得分.

根據(jù)在學(xué)習(xí)中計算圖相似性,將現(xiàn)有的基于GNN的圖相似性學(xué)習(xí)主要分為GNN-CNN模型、暹羅GNN模型、圖匹配網(wǎng)絡(luò).下面詳細(xì)介紹每個類別的相關(guān)工作.

2.1 用于圖形相似性預(yù)測的GNN-CNN模型

使用GNN-CNN混合網(wǎng)絡(luò)進(jìn)行圖相似性預(yù)測的工作主要是使用GNN學(xué)習(xí)圖表示,并將學(xué)到的圖表示映射到CNN中以生成相似性得分,通常用于分類或回歸問題.并在端到端模型中加入全連接層,用于生成相似性分?jǐn)?shù).

1)GSimCNN[13]提出了一種稱為GSimCNN的成對圖相似性預(yù)測方法,該方法包括3個階段.第1階段是由多層的圖卷積神經(jīng)網(wǎng)絡(luò)(Graph Convolutional Network,GCN)[16]生成節(jié)點表示,其中每層GCN定義為:

(1)

其中N(i)是包含節(jié)點i本身的一階鄰居的集合,di是節(jié)點i的度加1,W(l)是第l個GCN層的權(quán)重矩陣,b(l)表示偏差,而ReLU=max(0,x)是激活函數(shù).第2階段,通過不同GCN層,計算兩個圖之間所有節(jié)點嵌入對之間的內(nèi)積,從而生成了多個相似性矩陣.第3階段來自不同層的相似性矩陣由多個獨立的CNN處理,將CNN的輸出送入全連接層中,生成圖對GA和GB的相似性得分yAB.

2)SimGNN[14].基于GSimCNN引入了SimGNN模型.除了將成對節(jié)點與GCN輸出中的節(jié)點級嵌入進(jìn)行比較外,還使用神經(jīng)張量網(wǎng)絡(luò)[15](Neural Tensor Network,NTN)關(guān)聯(lián)了兩個輸入圖的圖級嵌入.最后,輸入圖的節(jié)點級嵌入和圖級嵌入被聯(lián)合起來作為圖的表示,輸入CNN全連接層用于預(yù)測圖相似性.

與本文方法最具有相關(guān)性的工作是SimGNN,這兩項工作之間的主要區(qū)別是:1)圖的全局嵌入方法.SimGNN使用GCN來生成圖嵌入,因為GCN擴(kuò)展性較差,本文采用了圖注意力網(wǎng)絡(luò)(GAT)來生成圖嵌入,并添加了自注意力圖匯聚(SAGPooL)來減少參數(shù),降低處理時間,避免過度擬合.而SimGNN的3層卷積,導(dǎo)致其運(yùn)行時間成本非常高,并在訓(xùn)練過程中丟失了一定的局部節(jié)點信息,使模型最終并不能達(dá)到理想的擬合效果.而NAGSim采用了圖注意力網(wǎng)絡(luò)結(jié)合自注意力匯聚,可以更好的保留圖的全局信息,減少參數(shù)計算,實驗驗證NAGSim模型效果更好,不僅減少了運(yùn)行時間,還具有更低的錯誤率;2)節(jié)點注意力權(quán)重的初始化不同.SimGNN隨機(jī)初始化一個權(quán)重矩陣.但是NAGSim將節(jié)點級嵌入階段由池化層產(chǎn)生的權(quán)重矩陣,作為注意力模塊的初始權(quán)重矩陣.由池化層產(chǎn)生的權(quán)重矩陣比隨機(jī)的參數(shù)矩陣更接近真實的權(quán)重分布,訓(xùn)練過程更快,大大減少了訓(xùn)練時間.

2.2 用于圖相似學(xué)習(xí)的暹羅GNN模型

這類模型采用GNN作為雙網(wǎng)絡(luò)的暹羅網(wǎng)絡(luò)體系結(jié)構(gòu),同時從輸入的兩個圖中學(xué)習(xí)圖的表示,然后基于GNN的輸出表示形式獲得相似性估計.SiameseGCN[16]是在有監(jiān)督的情況下使用連體圖卷積神經(jīng)網(wǎng)絡(luò)(S-GCN)學(xué)習(xí)圖相似性.S-GCN將一對圖作為輸入,并使用頻譜GCN來獲取每個輸入圖的圖形嵌入,然后,使用點積層和全連接層來生成光譜中兩個圖之間的相似性估計域.

2.3 基于GNN的圖匹配網(wǎng)絡(luò)

此類模型在學(xué)習(xí)過程中結(jié)合GNN與匹配機(jī)制來適應(yīng)暹羅GNN,并在圖表示學(xué)習(xí)過程中考慮跨圖交互.

圖匹配網(wǎng)絡(luò)GMN[17]是基于GNN的架構(gòu),其中,每個傳播層中的節(jié)點更新考慮了圖邊緣上的聚合消息,并提出了跨圖匹配策略:圖的節(jié)點與另一個圖的節(jié)點的匹配程度.該模型在給定一對圖作為輸入的情況下,通過一種新的基于跨圖關(guān)注度的匹配機(jī)制,通過對一對圖進(jìn)行聯(lián)合推理來計算它們之間的相似性得分.

3 模型介紹

表1 符號定義

圖2 NAGSim的總體架構(gòu)和工作流程

3.1 基于GAT和Attention的圖嵌入

3.1.1 圖的節(jié)點級嵌入

節(jié)點嵌入階段旨在提取圖的節(jié)點特征.對于輸入一對圖GA和GB,分別經(jīng)過圖注意力網(wǎng)絡(luò)(GAT)和自注意力匯聚(SAGPooL)最終提取了各自的節(jié)點特征,生成了張量表示UA和UB.

在將圖送入GAT之前,需要首先明確圖的輸入形式.給定任意一個圖G=〈V,E〉,其中V是G中所有節(jié)點的集合,E是G中所有邊的集合.其中每個節(jié)點vi采用1個D維的向量xi∈D表示節(jié)點特征,圖G的特征矩陣表示為X∈N×D.

如圖3所示,圖3(a)表示真實圖數(shù)據(jù),圖中共有6個頂點.其中不同類型的節(jié)點代表具有相同屬性的節(jié)點,表示節(jié)點屬性(例如度、組成元素)的不同.圖3(b)表示由不同的節(jié)點屬性所組成的圖.節(jié)點采用one-hot編碼,具有相同屬性的節(jié)點采用相同的one-hot編碼.

圖3 圖輸入示例

明確圖的輸入形式后,接下來通過圖注意力網(wǎng)絡(luò)(GAT)提取圖中的節(jié)點特征,匯聚鄰居信息.GAT利用注意力權(quán)重將鄰居節(jié)點的表達(dá)以加權(quán)和的形式聚合到自身,注意力權(quán)重和表達(dá)更新的計算公式分別如式(2)、式(3)所示:

(2)

(3)

其中,參數(shù)W用于完成每個節(jié)點的特征維度變換,參數(shù)a是可學(xué)習(xí)的參數(shù)向量,‖表示串聯(lián)操作,進(jìn)行向量拼接,αij表示在參數(shù)向量下計算得到的節(jié)點i,j之間的權(quán)重,σ表示非線性激活函數(shù),例如ReLU.

圖結(jié)構(gòu)中節(jié)點經(jīng)過GAT圖卷積之后來到池化層.池化層使得模型能夠通過縮小表示的大小來減少參數(shù)數(shù)量,從而避免過度擬合.這一部分主要用于特征降維,減少權(quán)重參數(shù),減小過擬合,同時提高模型的容錯性.通過池化層可以利用相對較少的參數(shù)以端到端的方式來學(xué)習(xí)分層表示.

本文采用了自注意力圖匯聚(SAGPool).這是一種在分層圖匯聚背景下用于GNN的自注意圖匯聚方法.利用自注意力機(jī)制來區(qū)分應(yīng)該丟棄的節(jié)點和應(yīng)該保留的節(jié)點,基于圖卷積計算注意力分?jǐn)?shù)的self-attention機(jī)制,同時考慮了節(jié)點特征和圖的拓?fù)浣Y(jié)構(gòu).

要深入貫徹落實《吉林省人民政府辦公廳關(guān)于加快發(fā)展棚膜經(jīng)濟(jì)促進(jìn)農(nóng)民增收的實施意見》，把發(fā)展棚膜經(jīng)濟(jì)作為加快推進(jìn)農(nóng)業(yè)供給側(cè)結(jié)構(gòu)性改革，轉(zhuǎn)變農(nóng)業(yè)發(fā)展方式，促進(jìn)農(nóng)業(yè)增效、農(nóng)民增收，培育農(nóng)業(yè)農(nóng)村發(fā)展新動能的重要途徑。做到主要領(lǐng)導(dǎo)整體抓，分管領(lǐng)導(dǎo)具體抓，層層落實責(zé)任[1]。

SAGPool是第1個使用self-attention進(jìn)行圖匯聚并實現(xiàn)高性能的方法.關(guān)鍵在于它使用GNN來提供self-attention分?jǐn)?shù),關(guān)注的是注意力本身公式(4)中計算self-attention分?jǐn)?shù):

(4)

idx=top_rank(Z,「kn?)

(5)

(6)

其中Z∈F×1為self-attention分?jǐn)?shù),θatt∈F×1是SAGPool中唯一的參數(shù),A表示鄰接矩陣,是單位矩陣,是的度矩陣,X代表每一層的特征.公式(5)利用自注意力機(jī)制來區(qū)分應(yīng)該丟棄的節(jié)點和應(yīng)該保留的節(jié)點.其中k∈(0,1]表示池化比率,是一個超參數(shù),決定要保留的節(jié)點數(shù).top「kn?的節(jié)點是由Z值進(jìn)行選擇的.top_rank是返回top「kn?的節(jié)點索引的函數(shù).公式(6)中n表示節(jié)點數(shù)量,xi表示第i個節(jié)點的特征,U輸出了節(jié)點特征.由于使用圖卷積計算注意力分?jǐn)?shù)的自注意力機(jī)制,模型同時考慮了節(jié)點特征和圖拓?fù)?

在經(jīng)過實驗對比(詳見表8、表9)后,本文發(fā)現(xiàn)采用GraphSAGE作為SAGPool的卷積方式時,SAGPool可以更有效地學(xué)習(xí)節(jié)點的重要性得分.GraphSAGE方法不同于原始的GNN方法,因為它通過匯總節(jié)點整個鄰域的采樣子集中的特征來定義節(jié)點的鄰域.表示為:

(7)

(8)

(9)

在本文中,將GAT層設(shè)置為1,SAGPool層設(shè)置為1.

3.1.2 圖級嵌入

一旦獲得了圖的節(jié)點嵌入表示,下一步就是有效地組合節(jié)點嵌入,以生成整個圖的圖級嵌入h.這一部分對應(yīng)圖2總體框架圖中的圖級嵌入階段,其中Att代指Attention.本文通過注意力機(jī)制為節(jié)點分配不同權(quán)重,使用節(jié)點嵌入的加權(quán)和表示圖級嵌入.

輸入一個圖的節(jié)點級嵌入U,首先通過平均所有節(jié)點嵌入并通過非線性激活函數(shù)對其進(jìn)行轉(zhuǎn)換來計算上下文向量(context vector)嵌入c:

(10)

其中WZ是由3.1節(jié)中池化層的公式(4)所構(gòu)成的權(quán)重矩陣.所得到的上下文向量c提供了整個圖的結(jié)構(gòu)屬性,激活函數(shù)σ為ReLU.公式(11)中為了計算每個節(jié)點n的注意力權(quán)重an,取每個節(jié)點嵌入Un與上下文向量c的內(nèi)積.這樣計算將對上下文向量c產(chǎn)生更大的影響,并且與上下文向量c最相似的節(jié)點嵌入將獲得更多的注意力權(quán)重.其中激活函數(shù)σ(·)為sigmoid函數(shù),再將an映射到(0,1)范圍內(nèi),并且可以通過圖中節(jié)點的個數(shù)更好地反映圖的大小.公式(12)綜合了公式(10)、公式(11)計算出h∈D的整體圖嵌入.

(11)

(12)

NAGSim的圖級嵌入沒有使用隨機(jī)初始化的權(quán)重矩陣張量W,而是采用節(jié)點嵌入階段之后所保留的特征WZ(參看公式(4)),這樣省去了很多參數(shù)訓(xùn)練過程,大大減少了訓(xùn)練時間.

3.2 相似性計算

3.2.1 基于神經(jīng)張量網(wǎng)絡(luò)的圖關(guān)聯(lián)

現(xiàn)在已經(jīng)獲得了每個圖的整體嵌入h,接下來使用神經(jīng)張量網(wǎng)絡(luò)(NTN)來比較兩個圖嵌入來估計它們的相似性.與傳統(tǒng)的線性方法相比,神經(jīng)張量網(wǎng)絡(luò)的優(yōu)勢在于它能夠有效地比較多個維度上的兩個嵌入矢量,用一個雙線性張量層代替一個標(biāo)準(zhǔn)的線性神經(jīng)網(wǎng)絡(luò)層.給定兩個圖GA和GB的圖級嵌入hA與hB,NTN使用雙線性張量,用以下函數(shù)來計算兩個嵌入之間的關(guān)系:

(13)

3.2.2 相似性得分計算

最后將NTN(hA,hB)輸入到全連接神經(jīng)網(wǎng)絡(luò)來生成相似性得分yAB,并使用一個均方誤差損失函數(shù)將其與真實數(shù)據(jù)相似性得分進(jìn)行比較,并使用梯度下降策略將均方誤差(MSE)損失降至最低:

(14)

其中P是訓(xùn)練集中圖對的集合,而yAB是GA和GB之間的真實相似性.

算法1.圖相似性計算模型NAGSim

輸入：給定圖數(shù)據(jù)庫P={G1,G2,…,GA,GB,…,GN},x表示輸入的節(jié)點特征,圖卷積層選擇1層GAT,αij為注意力系數(shù),池化層選擇1層SAGPool,Z為自注意力分?jǐn)?shù),U為節(jié)點嵌入矩陣,WZ是由Z構(gòu)成的權(quán)重矩陣,h代表圖嵌入,NTN中的超參數(shù)為k,W[1:k}為張量權(quán)重,Q∈k×2d為權(quán)重向量,偏置向量b∈k.全連接層數(shù)為l.

輸出：圖相似性得分yAB

1.Begin

2.從圖數(shù)據(jù)庫P中選擇一對圖GA和GB

3.{xv,?v∈Vi}←輸入圖GA中結(jié)點的one-hot編碼

4.{xu,?u∈Vj}←輸入圖GB中結(jié)點的one-hot編碼

5.UA=SAGPool(GAT(xv,αij),Z)

6.UB=SAGPool(GAT(xu,αij),Z)

7.hA=GraphEmbedding(UA,WZ)

8.hB=GraphEmbedding(UB,WZ)

9.score=NTN(hA,hB,W[1:k],Q,b)

10.yAB←fullyconnected(score,l)

11.End

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

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

1)ENZYMES.酶素,化合物分子,包含600個圖和6個類別,ENZYMES的每個數(shù)據(jù)都是1個圖.本文從中選擇了600個圖.

2)NCI-1.用于抗癌活性分類的生物學(xué)數(shù)據(jù)集.在數(shù)據(jù)集中,每個圖代表一種化學(xué)化合物,節(jié)點和邊分別代表原子和化學(xué)鍵.NCI-1數(shù)據(jù)集中包含4110個化合物和2個類別,標(biāo)簽是判斷化合物是否有阻礙癌細(xì)胞增長的性質(zhì).本文從中隨機(jī)選擇了50個圖,如表2所示.

表2 數(shù)據(jù)集統(tǒng)計

表3表示了數(shù)據(jù)集的基本信息.graphs表示數(shù)據(jù)集中包含的圖的數(shù)量,Avg.Nodes表示數(shù)據(jù)集的平均節(jié)點數(shù),Avg.Edges表示數(shù)據(jù)集的平均連邊數(shù),classes表示數(shù)據(jù)集包含幾種類別.

表3 數(shù)據(jù)集特征

4.2 實驗設(shè)置

對于每個數(shù)據(jù)集,分別將所有圖的80%和20%隨機(jī)分為訓(xùn)練集和測試集.數(shù)據(jù)集中的標(biāo)簽評估反映了圖查詢的實際情況:對于測試集中的每個圖,將其視為查詢圖,然后通過模型計算查詢圖與數(shù)據(jù)庫中各個圖之間的相似性.根據(jù)相似性得分進(jìn)行排序.

由文獻(xiàn)[3]已知即使是最先進(jìn)的算法也無法在具有超過16個節(jié)點的圖之間的合理時間內(nèi)可靠地計算出精確的GED.那么為了正確處理文中數(shù)據(jù)集,采用了3種著名的近似算法,即Hungarian[18],VJ[19]和HED[20]來計算出近似GED,并選擇計算出的最小距離.之所以采用最小值而不是平均值,因為確保返回的GED大于或等于真實的GED.

在本文研究中,選擇近似的GED值作為每個圖對的基本真實值.如圖4、圖5所示,描述了數(shù)據(jù)集中的測試集與訓(xùn)練集的近似GED的分布,可以看出GED分布比例相近,差異并不大.首先將真實的GED歸一化,然后通過指數(shù)函數(shù)將其映射到區(qū)間(0,1),然后將這些真實的GED值轉(zhuǎn)換為真實的相似性得分Yground truth.其中|GA|表示GA中的節(jié)點數(shù).

圖4 EMZYMES訓(xùn)練和測試集中的近似GED值分布

圖5 NCI-1訓(xùn)練和測試集中的近似GED值分布

(15)

Yground truth=e-norm

(16)

模型將GAT層數(shù)設(shè)置為1,多頭注意的數(shù)量(Number of multi-head-attentions)設(shè)為1,并使用ReLU作為激活函數(shù).GAT的輸出尺寸為32.之后的池化層的池化比率k設(shè)置為0.8.對于NTN層,將超參數(shù)K設(shè)置為16.使用4個全連接層將NTN模塊的合并結(jié)果維數(shù)從32減小為16、16至8、8至4和4至1.

實驗環(huán)境及配置如表4所示.在訓(xùn)練過程中,將批處理大小設(shè)置為256,使用Adam算法進(jìn)行優(yōu)化[21],并將初始學(xué)習(xí)率固定為0.001.將迭代次數(shù)設(shè)置為100,然后根據(jù)最低的驗證損失選擇最佳的模型.

表4 實驗環(huán)境及配置

4.3 評估指標(biāo)

為了評估和比較NAGSim的有效性,本文使用了以下指標(biāo)評估所有模型:

·運(yùn)行時間(Time).運(yùn)行時間是指每種方法估算整個數(shù)據(jù)集的圖對相似性得分所花費的總時間.

·均方誤差(MSE).使用均方誤差(MSE)來計算公式(14)中定義的預(yù)測分?jǐn)?shù)與真實相似性之間的損失.MSE具有凸性、對稱性和可微性的數(shù)學(xué)性質(zhì),并且對數(shù)據(jù)集中的異常值具有敏感性.

·Spearman的排名相關(guān)系數(shù)(ρ)[22]和Kendall的排名相關(guān)系數(shù)(τ)[23]衡量預(yù)測排名結(jié)果與真實排名結(jié)果的匹配程度.因此兩個系數(shù)越大表示效果越好,預(yù)測和真實數(shù)據(jù)越相關(guān).公式(17)是計算x、y的Spearman相關(guān)系數(shù),公式(18)是計算Kendall相關(guān)系數(shù),對于x、y的兩對觀察值xi,yi和xj,yj,如果xiyi并且xj>yj,則稱這兩對觀察值是一致的,否則就是不一致的:

(17)

(18)

(19)

以上的4個評估指標(biāo)中,運(yùn)行時間(Time)、均方誤差(MSE)越小越好,相關(guān)系數(shù)(ρ、τ)與決定系數(shù)(R2)越大越好.

4.4 Baseline方法

本文把以下6個方法作為Baseline,實驗對比分析Baseline和NAGSim的性能:

1)Hungarian[18].基于匈牙利二部圖匹配算法用于計算近似GED的傳統(tǒng)算法;2)VJ[19].基于Volgenant算法和Jonker算法的兩種立方時間算法,只考慮有限的邊的信息,是用于計算近似GED的次優(yōu)算法;3)HED[20].根據(jù)HausdorffEdit距離計算局部子結(jié)構(gòu)之間的雙向分配,確定圖形編輯距離的下限;4)SimGNN[14].最初的提出使用圖神經(jīng)網(wǎng)絡(luò)的計算圖相似性的模型;5)funcGNN[24].使用圖神經(jīng)網(wǎng)絡(luò)的計算程序流程圖相似性的模型;6)GMN[17].基于跨圖注意力的匹配機(jī)制來計算相似性分?jǐn)?shù)的圖匹配網(wǎng)絡(luò).

4.5 實驗結(jié)果

表5表示在相同數(shù)據(jù)集上,不同Baseline所運(yùn)行的時間對比.實驗環(huán)境詳見表4,所有Baseline均是在相同的實驗環(huán)境下運(yùn)行.由于GED估算非常耗時,因此利用了并行計算的功能來加快計算速度.傳統(tǒng)方法的近似GED是通過ProcessPoolExecutor6[25]使用24個并發(fā)進(jìn)程池異步計算的.實驗結(jié)果表明,與所有近似方法的并行執(zhí)行(24個過程)相比,即使在串行執(zhí)行時NAGSim也會提供更快的結(jié)果.與現(xiàn)有的端到端的圖神經(jīng)網(wǎng)絡(luò)方法相比(1個進(jìn)程),NAGSim達(dá)到最優(yōu),降低了運(yùn)行時間.

表5 ENZYMES數(shù)據(jù)集上,不同方法運(yùn)行時間的對比

如圖6所示,為NAGSim針對訓(xùn)練和測試數(shù)據(jù)集獲得的MSE損失函數(shù)曲線.可以推斷出,針對訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集,NAGSim模型已經(jīng)收斂.針對模型的性能和收斂行為表明,MSE是優(yōu)化NAGSim模型以學(xué)習(xí)成對圖之間相似性的好的方法.在表6、表7中比較了NAGSim與不同圖神經(jīng)網(wǎng)絡(luò)模型方法獲得的MSE誤差值.與現(xiàn)有的端到端方法相比,可以看出NAGSim在不同的數(shù)據(jù)集上均取得了較好的結(jié)果.

表6 不同圖神經(jīng)網(wǎng)絡(luò)模型在ENZYMES數(shù)據(jù)集的精確性

表7 不同圖神經(jīng)網(wǎng)絡(luò)模型在NCI-1數(shù)據(jù)集的精確性

圖6 ENZYMES訓(xùn)練集和測試集的錯誤率

為了確定本文模型的有效性與準(zhǔn)確性,對模型自身進(jìn)行了對比實驗.本文評估NAGSim的各個關(guān)鍵模塊對NAGSim性能的影響:

1)GCN.基于頻域卷積的方式融合圖結(jié)構(gòu)特征;2)GraphSAGE.使用隨機(jī)采樣方法生成子圖,通過子圖更新節(jié)點嵌入;3)GAT.使用注意力來學(xué)習(xí)邊上權(quán)重的圖神經(jīng)網(wǎng)絡(luò);4)GAT+SAGPool(GCN).卷積方式采用GAT,池化層選擇SAGPool,SAGPool中選擇GCN學(xué)習(xí)注意力分?jǐn)?shù)的self-attention機(jī)制;5)GAT+SAGPool(GraphSAGE).卷積方式采用GAT,池化層選擇SAGPool,SAGPool中選擇GraphSAGE學(xué)習(xí)注意力分?jǐn)?shù)的self-attention機(jī)制;6)GAT+SAGPool(GAT).卷積方式采用GAT,池化層選擇SAGPool,SAGPool中選擇GAT學(xué)習(xí)注意力分?jǐn)?shù)的self-attention機(jī)制.

通過不同的對比實驗,本文最終確定模型的各模塊組成部分.表8、表9表示在不同數(shù)據(jù)集上的對比實驗,從中可以看出NAGSim效果均達(dá)到最優(yōu).因此可以判斷模型的有效性.如表8、表9所示,在GCN、GraphSAGE、GAT 3種卷積方式中,GAT采用注意力機(jī)制可以更好融合提取圖的節(jié)點特征.在確定了卷積層(GAT)后,加入SAGPool池化層避免了過擬合,減少參數(shù)從而降低了時間復(fù)雜度.在SAGPool中采用GraphSAGE作為卷積方式,可以更為有效地學(xué)習(xí)節(jié)點的注意力分?jǐn)?shù).GraphSAGE通過聚合采樣可以更好地匯聚鄰居節(jié)點的特征.在確定了卷積層(GAT)與池化層(SAGPool)后,最后加入注意力機(jī)制從而生成圖級嵌入,送入神經(jīng)張量網(wǎng)絡(luò)層與全連接層輸出相似性得分.

表8 ENZYMES數(shù)據(jù)集下NAGSim變種模型的準(zhǔn)確性對比

表9 NCI-1數(shù)據(jù)集下NAGSim變種模型的準(zhǔn)確性對比

5 結(jié) 論

傳統(tǒng)的基于圖編輯距離的圖相似性計算算法模型復(fù)雜,時間成本高并且精確度不高,深度學(xué)習(xí)技術(shù)的發(fā)展為傳統(tǒng)的圖相似計算問題提供了新的思路.本文提出了NAGSim——一種基于圖神經(jīng)網(wǎng)絡(luò)與注意力機(jī)制的圖相似計算模型,在圖數(shù)據(jù)庫中查找與給定的查詢圖相似的圖的集合,來預(yù)測圖結(jié)構(gòu)之間的相似性.為了預(yù)測一對圖結(jié)構(gòu)之間的相似性,本文首先分析了圖的整體結(jié)構(gòu)表示.NAGSim繼承了圖卷積網(wǎng)絡(luò)的歸納和節(jié)點順序不變屬性,并使用它為圖中的每個節(jié)點創(chuàng)建語義豐富的嵌入,并加入了注意力機(jī)制使得模型優(yōu)于現(xiàn)有的端到端學(xué)習(xí)模型.實驗結(jié)果表明,NAGSim與現(xiàn)有的經(jīng)典算法和端到端的學(xué)習(xí)方法相比,模型在近似的圖編輯距離計算上運(yùn)行速度非常快,在各項評價指標(biāo)上都有一定的提升,并且具有非常高的競爭力.之后還將考慮如何應(yīng)用NAGSim解決相關(guān)的圖相似性挑戰(zhàn),例如蛋白質(zhì)分子查找,程序流程圖的安全性,對于這些實際應(yīng)用而言,尋找圖結(jié)構(gòu)的相似性至關(guān)重要.