基于圖神經(jīng)網(wǎng)絡(luò)的子圖匹配符號(hào)算法

楊 欣, 徐周波, 陳浦青, 劉華東

(桂林電子科技大學(xué) 計(jì)算機(jī)與信息安全學(xué)院,廣西 桂林 541004)

圖作為一種數(shù)據(jù)結(jié)構(gòu),可以有效刻畫事物之間的關(guān)系,現(xiàn)實(shí)世界中的許多復(fù)雜問題都可以用圖進(jìn)行抽象表示。子圖匹配問題作為圖分析中最基本的問題之一,其目標(biāo)是在數(shù)據(jù)圖g中查找與查詢圖q同構(gòu)的所有子圖[1],在圖像檢索、化學(xué)分子式檢索、知識(shí)圖譜查詢和社交網(wǎng)絡(luò)分析等領(lǐng)域有著廣泛應(yīng)用[2]。由于子圖匹配問題屬于NP難問題,隨著數(shù)據(jù)規(guī)模的急劇增加,其求解的復(fù)雜度呈指數(shù)增長(zhǎng),因此廣大研究者致力于擴(kuò)大子圖匹配問題的求解規(guī)模和提升求解效率。

在過(guò)去幾十年,大量子圖匹配算法被提出,其中基于回溯搜索的算法[3-13]更是被廣泛研究。著名的Ullmann算法[3]于1979年提出,該算法基于回溯的樹搜索在數(shù)據(jù)圖g中枚舉出與查詢圖q匹配的所有子圖。由于Ullmann算法只采用了簡(jiǎn)單的剪枝策略,無(wú)法高效地減少搜索空間。VF2[4]算法在Ullmann算法的基礎(chǔ)上,將節(jié)點(diǎn)的鄰居信息作為約束條件,增強(qiáng)了剪枝效果,有效地減少了搜索空間。GraphQL算法[5]提出以查詢圖的深度優(yōu)先搜索生成樹過(guò)濾數(shù)據(jù)圖中的節(jié)點(diǎn)。Spath算法[6]采用對(duì)查詢圖進(jìn)行層次遍歷并以每層節(jié)點(diǎn)的信息作為約束條件,引入復(fù)雜的結(jié)構(gòu)與語(yǔ)義信息過(guò)濾數(shù)據(jù)圖中的節(jié)點(diǎn)。這些算法雖然從不同角度增加剪枝過(guò)濾效果,從而改善了搜索效率,卻很難在合理時(shí)間內(nèi)對(duì)大規(guī)模數(shù)據(jù)圖進(jìn)行子圖匹配求解。為了擴(kuò)大求解規(guī)模,VF3 算法[7]在VF2的基礎(chǔ)上依據(jù)查詢圖節(jié)點(diǎn)的匹配點(diǎn)在數(shù)據(jù)圖中的出現(xiàn)概率計(jì)算匹配順序,并引入分類概念,將節(jié)點(diǎn)按照度與標(biāo)簽進(jìn)行分類,進(jìn)一步減少了搜索空間。CFL-Match[8]算法提出分解查詢圖延遲笛卡爾積,以有效減少冗余的中間結(jié)果的產(chǎn)生,采用輔助數(shù)據(jù)結(jié)構(gòu)CPI存儲(chǔ)候選集中的部分連邊。CECI[9]算法則將數(shù)據(jù)圖劃分為多個(gè)嵌入簇并進(jìn)行并行處理,采用剪枝技術(shù)對(duì)嵌入簇反復(fù)修剪,得到輔助數(shù)據(jù)結(jié)構(gòu)CECI。雖然構(gòu)造輔助數(shù)據(jù)結(jié)構(gòu)提高了在大規(guī)模數(shù)據(jù)圖中的搜索效率,卻存在消耗大量的內(nèi)存空間和預(yù)處理時(shí)間的問題。

為了平衡子圖匹配求解算法的時(shí)間復(fù)雜度和空間復(fù)雜度,從增強(qiáng)過(guò)濾效果、優(yōu)化匹配順序和減少冗余搜索3方面出發(fā),提出了基于圖神經(jīng)網(wǎng)絡(luò)的子圖匹配符號(hào)(symbol solving algorithm for subgraph matching based of graph neural network,簡(jiǎn)稱SSMGNN)算 法。不 同 于 VFGCN 算 法[14],SSMGNN算法通過(guò)引入圖神經(jīng)網(wǎng)絡(luò)(graph neural networks,簡(jiǎn)稱GNN)[15-16]提取節(jié)點(diǎn)的特征向量,以該向量作為過(guò)濾條件來(lái)縮小節(jié)點(diǎn)候選集。其次,SSMGNN算法在文獻(xiàn)[9]的基礎(chǔ)上,綜合考慮了節(jié)點(diǎn)候選集的大小、節(jié)點(diǎn)度數(shù)以及待匹配節(jié)點(diǎn)的鄰居中已匹配節(jié)點(diǎn)數(shù)等信息,給出了一種新的優(yōu)化匹配順序。同時(shí),將引入的代數(shù)決策圖(algebraic decision diagram,簡(jiǎn)稱ADD)[17]作為圖的存儲(chǔ)結(jié)構(gòu),采用符號(hào)ADD操作對(duì)子圖匹配求解,在求解過(guò)程中,提出一種新的編碼使得并行處理候選區(qū)[18]的劃分,從而減少冗余搜索。因符號(hào)ADD 是隱式存儲(chǔ),使得SSMGNN算法能在較小的存儲(chǔ)空間中操作較大規(guī)模的圖。

1 相關(guān)概念

定義1 標(biāo)簽圖G=〈V,E,L,l〉,其中:V表示圖G的節(jié)點(diǎn)集合;E表示圖G中所有的邊集;L表示節(jié)點(diǎn)標(biāo)簽集合;l表示標(biāo)簽映射函數(shù):V→L。

定義2 給定數(shù)據(jù)圖g=〈Vg,Eg,Lg,lg〉與查詢圖q=〈Vq,Eq,Lq,lq〉。圖q與圖g存在子圖同構(gòu)關(guān)系,當(dāng)且僅當(dāng)存在一個(gè)單射函數(shù)f:Vq→Vg滿足:

1)?u∈Vq,?f(u)∈Vg,lq(u)=lg(f(u));

2)?(u,u′)∈Eq,?(f(u),f(u′))∈Eg.

定義3 ADD 是表示基于變量序π:x1＜x2＜…＜xn的一族偽布爾函數(shù)fi:{0,1}n→S的一個(gè)有向無(wú)環(huán)圖,它滿足[19]:

1)S為ADD代數(shù)結(jié)構(gòu)的有限值域,且S∈Z。

2)ADD中的節(jié)點(diǎn)分為根節(jié)點(diǎn)、終節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)3類。

3)終節(jié)點(diǎn)集合記為T。對(duì)任意t∈T,均被標(biāo)識(shí)為值域S中的一個(gè)元素是s(t)。每個(gè)非終節(jié)點(diǎn)u具有四元組屬性(fu,nvar,l,h),其中:fu表示節(jié)點(diǎn)u所對(duì)應(yīng)的偽布爾函數(shù);nvar表示節(jié)點(diǎn)u的標(biāo)記變量;l表示節(jié)點(diǎn)u的nvar=0時(shí),節(jié)點(diǎn)u的0-分支子節(jié)點(diǎn);h表示節(jié)點(diǎn)u的nvar=1時(shí),節(jié)點(diǎn)u的1-分支子節(jié)點(diǎn)。

4)圖中的每個(gè)節(jié)點(diǎn)u對(duì)應(yīng)唯一一個(gè)函數(shù)fu。

5)圖中任意一條從根節(jié)點(diǎn)到終節(jié)點(diǎn)的路徑中,所有變量均按變量序π的順序出現(xiàn),且僅出現(xiàn)一次。

2 基于圖神經(jīng)網(wǎng)絡(luò)的子圖匹配符號(hào)算法

基于圖神經(jīng)網(wǎng)絡(luò)的子圖匹配符號(hào)算法由3個(gè)步驟組成,即生成候選集、生成匹配順序和求解子圖同構(gòu),算法的基本框架如圖1所示。首先,從提升過(guò)濾效率的角度出發(fā),引入圖神經(jīng)網(wǎng)絡(luò)提取圖節(jié)點(diǎn)的特征向量,并以該向量作為過(guò)濾條件為查詢圖生成候選集。其次,根據(jù)查詢圖節(jié)點(diǎn)的候選集、度以及查詢圖的層次結(jié)構(gòu)等屬性對(duì)匹配順序進(jìn)行優(yōu)化。最后,使用ADD表示候選集與圖,并結(jié)合ADD 符號(hào)操作在數(shù)據(jù)圖中以查詢圖的半徑為范圍并行構(gòu)建候選區(qū),并在候選區(qū)中采用回溯算法進(jìn)行求解。

圖1 SSMGNN算法的基本框架

2.1 生成候選集

目前,大量的子圖匹配算法可分為過(guò)濾與驗(yàn)證2個(gè)步驟,其過(guò)濾階段將在數(shù)據(jù)圖中探索查詢圖每個(gè)節(jié)點(diǎn)可能匹配的節(jié)點(diǎn),這些匹配節(jié)點(diǎn)的集合稱為該節(jié)點(diǎn)的候選集。在驗(yàn)證階段,根據(jù)候選集的節(jié)點(diǎn)在數(shù)據(jù)圖中進(jìn)行搜索,從而得到子圖匹配的可行解集。為了盡可能減少候選集中錯(cuò)誤候選節(jié)點(diǎn)的數(shù)量,現(xiàn)有的子圖匹配算法大多基于節(jié)點(diǎn)的標(biāo)簽與度信息對(duì)候選集進(jìn)行過(guò)濾,卻忽略了節(jié)點(diǎn)的局部鄰域結(jié)構(gòu)與屬性信息。為此,用圖神經(jīng)網(wǎng)絡(luò)對(duì)圖的節(jié)點(diǎn)進(jìn)行鄰域信息聚合,得到節(jié)點(diǎn)特征向量,使得節(jié)點(diǎn)包含更多的局部信息,從而提升過(guò)濾效率。

首先利用圖注意力網(wǎng)絡(luò)[20]學(xué)習(xí)數(shù)據(jù)圖與模式圖的節(jié)點(diǎn)特征,得到其表示向量。其次,在文獻(xiàn)[21]提出的子圖預(yù)測(cè)函數(shù)的基礎(chǔ)上,設(shè)計(jì)了函數(shù)p(xv,xu),該函數(shù)通過(guò)比較節(jié)點(diǎn)的表示向量中每個(gè)位置的數(shù)值大小來(lái)判斷2個(gè)節(jié)點(diǎn)的鄰域結(jié)構(gòu)是否可能存在包含關(guān)系,如式(1)所示。

其中:xv為節(jié)點(diǎn)v的特征向量;xv[i]表示xv的第i個(gè)值;d為特征向量的維度。通過(guò)式(1)對(duì)數(shù)據(jù)圖與查詢圖的每個(gè)節(jié)點(diǎn)的特征向量中每個(gè)位置的數(shù)值進(jìn)行比較。若p(xv,xu)為1,表示節(jié)點(diǎn)v的節(jié)點(diǎn)鄰域結(jié)構(gòu)可能包含節(jié)點(diǎn)u的鄰域結(jié)構(gòu),從而檢查節(jié)點(diǎn)u與v的標(biāo)簽與度是否一致,一致則將節(jié)點(diǎn)v加入節(jié)點(diǎn)u的候選集。若p(xv,xu)為0,則說(shuō)明2個(gè)節(jié)點(diǎn)的鄰域信息不存在包含關(guān)系,從而節(jié)點(diǎn)v不能成為節(jié)點(diǎn)u的候選點(diǎn)。

2.2 確定匹配順序

在子圖匹配求解過(guò)程中,查詢圖節(jié)點(diǎn)匹配順序的選擇對(duì)搜索效率有著嚴(yán)重影響。如圖2所示,查詢圖q中的每個(gè)節(jié)點(diǎn)在數(shù)據(jù)圖g中的候選節(jié)點(diǎn)表示為(u1,{v1,v2})、(u2,{v3,v90})、(u3,{v5,v6,v91})、(u4,{v7,v8,…,v91})、(u5,{v4,v88,…,v89})。針對(duì)查詢圖q,若給定匹配順序P1={u4,u1,u5,u2,u3},根據(jù)回溯搜索算法在數(shù)據(jù)圖g中進(jìn)行搜索求解,其搜索次數(shù)為1 280次,幾乎需要遍歷整個(gè)搜索空間。若匹配順序?yàn)镻2={u1,u2,u3,u5,u4},其搜索次數(shù)為175次。由此可見,合適的匹配順序能夠有效減少搜索次數(shù),從而提高搜索效率。

圖2 查詢圖q與數(shù)據(jù)圖g

因此,將綜合考慮查詢圖節(jié)點(diǎn)的候選集、度數(shù)以及查詢圖的結(jié)構(gòu)3個(gè)方面來(lái)對(duì)查詢圖匹配順序進(jìn)行優(yōu)化。具體來(lái)說(shuō),優(yōu)先匹配候選集小且度數(shù)大的節(jié)點(diǎn),可降低中間結(jié)果的產(chǎn)生。由于在子圖搜索的過(guò)程中會(huì)檢查待匹配節(jié)點(diǎn)與已匹配節(jié)點(diǎn)的結(jié)構(gòu)關(guān)系與查詢圖q是否一致,優(yōu)先考慮與已匹配節(jié)點(diǎn)連邊多的節(jié)點(diǎn),也可提高搜索效率。因此,綜合考慮節(jié)點(diǎn)候選集的大小、節(jié)點(diǎn)度數(shù)以及待匹配節(jié)點(diǎn)的鄰居中已匹配數(shù)量,并選擇兩者之和的最大的節(jié)點(diǎn)作為下一個(gè)匹配節(jié)點(diǎn),具體如式(2)所示。

其中:｜·｜表示取集合中元素的個(gè)數(shù);C(u)表示節(jié)點(diǎn)u的候選集;d(u)表示節(jié)點(diǎn)u的度;N(u)為節(jié)點(diǎn)u的鄰居節(jié)點(diǎn)集合;M為已匹配節(jié)點(diǎn)的集合且初始值為空集;｜N(u)∩M｜為節(jié)點(diǎn)u的鄰居中已匹配的數(shù)量。第一個(gè)匹配節(jié)點(diǎn)稱為根節(jié)點(diǎn),因?yàn)檫x擇根節(jié)點(diǎn)時(shí)M為空集,從而根據(jù)節(jié)點(diǎn)度數(shù)與節(jié)點(diǎn)候選點(diǎn)的數(shù)量的比值進(jìn)行選擇,優(yōu)先選擇兩者比值大的節(jié)點(diǎn)作為根節(jié)點(diǎn),并將根節(jié)點(diǎn)加入M。下一個(gè)節(jié)點(diǎn)的選擇,將會(huì)在節(jié)點(diǎn)度數(shù)與節(jié)點(diǎn)候選點(diǎn)的數(shù)量的基礎(chǔ)上考慮該節(jié)點(diǎn)與M中節(jié)點(diǎn)的連邊數(shù)量,若度數(shù)與節(jié)點(diǎn)候選點(diǎn)的數(shù)量的比值相同,則優(yōu)先選擇與M連邊的節(jié)點(diǎn)作為下一個(gè)節(jié)點(diǎn)。以此類推,確定所有節(jié)點(diǎn)的匹配順序。

2.3 候選區(qū)

文獻(xiàn)[9]指出在候選區(qū)中進(jìn)行子圖匹配能夠有效減少搜索次數(shù),并且在構(gòu)造候選區(qū)的過(guò)程中可以進(jìn)一步對(duì)候選集進(jìn)行過(guò)濾。為了得到數(shù)據(jù)圖中的所有同構(gòu)子圖,在構(gòu)建候選區(qū)時(shí),根節(jié)點(diǎn)的候選集中所有節(jié)點(diǎn)分別作為中心節(jié)點(diǎn),在數(shù)據(jù)圖中挖掘大小與查詢圖半徑相同的子圖作為候選區(qū)。然而,這一做法造成不同的候選區(qū)之間存在許多相同的節(jié)點(diǎn)和邊,導(dǎo)致需要花費(fèi)大量的空間來(lái)存儲(chǔ)。ADD 是一種高緊湊、易操作的數(shù)據(jù)結(jié)構(gòu),可以對(duì)數(shù)據(jù)進(jìn)行壓縮存儲(chǔ),是克服存儲(chǔ)容量限制的一種有效措施。因此,引入了符號(hào)ADD,將其作為候選區(qū)的存儲(chǔ)結(jié)構(gòu),并且可以并行地在數(shù)據(jù)圖中進(jìn)行搜索,得到所有候選區(qū),有效解決了存儲(chǔ)空間問題,且提高了構(gòu)建候選區(qū)的效率。

2.3.1 ADD表示

給定圖G,其節(jié)點(diǎn)數(shù)量｜V｜=n,首先對(duì)圖G的節(jié)點(diǎn)與邊進(jìn)行編碼。節(jié)點(diǎn)編碼可采用長(zhǎng)度為m=log2n的二進(jìn)制串X=(x1,x2,…,xm)表示[22-23]。邊代表節(jié)點(diǎn)與節(jié)點(diǎn)間的二元關(guān)系,因此邊記為(X,Y)=(x1,x2,…,xm,y1,y2,…,ym),其中:X表示邊的起始節(jié)點(diǎn);Y表示邊的終節(jié)點(diǎn)。將數(shù)據(jù)圖g的邊集Eg轉(zhuǎn)化為ADD表示,記為Eg(X,Y),查詢圖q邊集的ADD 表示記為Eq(X,Y)。候選集的ADD表示與邊相同,記為(X,Y)=(x1,x2,…,xm,y1,y2,…,ym),其中:X表示查詢圖的節(jié)點(diǎn);Y表示數(shù)據(jù)圖的節(jié)點(diǎn)。候選集的ADD表示記為C(X,Y)。

為了壓縮存儲(chǔ)空間并實(shí)現(xiàn)并行搜索,將所有候選區(qū)合并存儲(chǔ)。因此,候選區(qū)的ADD 表示添加變量Z,以區(qū)分不同的候選區(qū),記為(Z,X,Y)=(z1,z2,…,zm,x1,x2,…,xm,y1,y2,…,ym)。其中:Z表示候選區(qū)區(qū)分標(biāo)志;X表示候選區(qū)中邊的起始節(jié)點(diǎn);Y表示候選區(qū)中邊的終節(jié)點(diǎn)。如圖2(b)所示,R1與R2為數(shù)據(jù)圖中的2個(gè)候選區(qū),分別由根節(jié)點(diǎn)u1的候選點(diǎn)v1與v2作為起始節(jié)點(diǎn)與該區(qū)的區(qū)分標(biāo)志,數(shù)據(jù)圖g的節(jié)點(diǎn)數(shù)n=97,則m=7,通過(guò)Z變量編碼0000001與0000010來(lái)區(qū)分R1與R2候選區(qū)。

2.3.2 候選區(qū)構(gòu)建

候選區(qū)的構(gòu)建首先需要基于2.1節(jié)計(jì)算得到根節(jié)點(diǎn),并通過(guò)根節(jié)點(diǎn)得到查詢圖的廣度優(yōu)先搜索樹與查詢圖的半徑r。其次,根節(jié)點(diǎn)的候選點(diǎn)分別作為起始節(jié)點(diǎn)vs并作為區(qū)別候選區(qū)的標(biāo)志。然后,根據(jù)vs在數(shù)據(jù)圖中利用廣度優(yōu)先搜索構(gòu)造以r為范圍的候選區(qū),在此過(guò)程中,每層候選區(qū)中的節(jié)點(diǎn)都會(huì)與查詢圖中該層節(jié)點(diǎn)的候選集做集合操作,以保留候選區(qū)中屬于候選集的節(jié)點(diǎn)。構(gòu)建候選區(qū)的偽代碼如算法1所示。

算法1的第1行函數(shù)GetRootCand是將根節(jié)點(diǎn)root(X)與查詢圖節(jié)點(diǎn)的候選集C(X,Y)做ADD符號(hào)操作,返回根節(jié)點(diǎn)的候選集Croot(X)。第3行函數(shù)Region Mark是通過(guò)符號(hào)操作構(gòu)造以Croot(X)中的每個(gè)節(jié)點(diǎn)為起始點(diǎn)與區(qū)分候選區(qū)節(jié)點(diǎn)的候選區(qū)Rtmp(Z,X)。第5～8行是一個(gè)以查詢圖的半徑為范圍的for循環(huán),根據(jù)廣度遍歷搜索,在數(shù)據(jù)圖中一層一層地往下搜索并更新候選區(qū)。其中第6行函數(shù)Get-Layer Node是為了得到候選區(qū)的第i+1層的節(jié)點(diǎn),首先通過(guò)查詢圖操作得到第i+1層的節(jié)點(diǎn)并得到該層節(jié)點(diǎn)的候選集,用該候選集過(guò)濾數(shù)據(jù)圖操作得到第i+1層的節(jié)點(diǎn),從而得到候選區(qū)的第i+1層的節(jié)點(diǎn)Ln(Z,X)。第7行函數(shù)UpdateRegion為更新增加候選區(qū)的邊集,將候選區(qū)R(Z,X,Y)中第i層節(jié)點(diǎn)與Ln(Z,X)節(jié)點(diǎn)的連邊和每個(gè)候選區(qū)中Ln(Z,X)節(jié)點(diǎn)間的連邊加入候選區(qū)R(Z,X,Y)。第8行函數(shù)UpdateParameter為更新數(shù)據(jù)圖在不同候選區(qū)中已經(jīng)遍歷過(guò)的節(jié)點(diǎn)、查詢圖已經(jīng)遍歷的節(jié)點(diǎn)、已經(jīng)分區(qū)待操作的數(shù)據(jù)集中的節(jié)點(diǎn)和查詢圖中待操作的節(jié)點(diǎn),更新后進(jìn)入下一次for循環(huán)。第9行返回候選區(qū)R(Z,X,Y)。

2.4 SSMGNN算法

結(jié)合符號(hào)ADD技術(shù)構(gòu)建候選區(qū)并進(jìn)行求解,給出基于圖神經(jīng)網(wǎng)絡(luò)的子圖匹配符號(hào)算法(SSMGNN)。該算法主要步驟為:第1步產(chǎn)生候選集,利用GNN對(duì)圖節(jié)點(diǎn)鄰域信息聚合并得到特征向量,使用該向量計(jì)算得到查詢圖候選點(diǎn)。第2步優(yōu)化匹配順序,為后續(xù)的搜索匹配做準(zhǔn)備。第3步構(gòu)建候選區(qū),在數(shù)據(jù)圖中利用符號(hào)ADD操作構(gòu)建候選集的各個(gè)候選區(qū)域。第4步子圖匹配求解,結(jié)合ADD操作與回溯搜索進(jìn)行求解。SSMGNN 算法的偽代碼如算法2所示。

算法2第1行函數(shù)NodeEmbedding用于對(duì)查詢圖的節(jié)點(diǎn)進(jìn)行鄰居信息聚合并表示為特征向量。第2行函數(shù)ComputeCand使用式(1)計(jì)算數(shù)據(jù)圖與查詢圖的節(jié)點(diǎn)特征,得到查詢圖節(jié)點(diǎn)在數(shù)據(jù)圖中的候選集。第3行Order函數(shù)用于優(yōu)化模式圖的節(jié)點(diǎn)匹配順序。通過(guò)候選集和查詢節(jié)點(diǎn)的度等信息確定查詢圖的根節(jié)點(diǎn)root。以root為起始點(diǎn)對(duì)查詢圖進(jìn)行廣度遍歷搜索,并對(duì)每層的節(jié)點(diǎn)進(jìn)行排序,該排序按照已匹配節(jié)點(diǎn)的連邊、候選集大小與度等條件得到最終的匹配順序。第4行函數(shù)CreateADD是將排序后的節(jié)點(diǎn),查詢圖的邊集、候選集與根節(jié)點(diǎn)轉(zhuǎn)化為ADD圖表示。第5行函數(shù)ADDPartition使用ADD 操作在數(shù)據(jù)集構(gòu)建多個(gè)候選區(qū)R(Z,X,Y),具體過(guò)程在算法1中給出。第7行函數(shù)GetRootCand通過(guò)ADD符號(hào)操作返回root的候選集Croot(X)。第8～14行是以Croot(X)的節(jié)點(diǎn)為起始節(jié)點(diǎn)的每個(gè)候選區(qū)進(jìn)行子圖同構(gòu)匹配。其中第9行函數(shù)ChooseRegion將選擇Croot(X)中的一個(gè)節(jié)點(diǎn)與候選區(qū)R(Z,X,Y)做符號(hào)操作,并返回其中的一個(gè)候選區(qū)Ri(X,Y);第10～13行Cheak Region函數(shù)是檢查Ri(X,Y)的可行性,查看每個(gè)查詢點(diǎn)的候選集在Ri(X,Y)中是否為空,若為空,則說(shuō)明該區(qū)域無(wú)解,需要重新選擇一個(gè)候選區(qū),否則,使用第13行函數(shù)Match進(jìn)行求解,在Ri(X,Y)中按照order的匹配順序?qū)ψ兞窟M(jìn)行賦值,采用回溯搜索算法尋找可行解并將其加入解集;第14行返回所有可行解。

3 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)環(huán)境為Core i5-1038NG7 CPU@2.00 GHz,16 GiB內(nèi)存,操作系統(tǒng)為Windows 10 64位,編譯語(yǔ)言為Python和C/C++。實(shí)驗(yàn)使用的2個(gè)公開數(shù)據(jù)集分別是human和yeast。其中human數(shù)據(jù)集為人類蛋白質(zhì)相互作用的數(shù)據(jù)圖,由86 282條邊、4 674個(gè)節(jié)點(diǎn)和44 個(gè)不同的標(biāo)簽組成的無(wú)向圖;yeast數(shù)據(jù)集包含了12 519條邊、3 112個(gè)節(jié)點(diǎn)與71個(gè)不同的標(biāo)簽。對(duì)于每個(gè)數(shù)據(jù)集,構(gòu)造4種不同的查詢集,分別為Q4、Q8、Q16、Q32,其中Qi表示包含i個(gè)節(jié)點(diǎn)的查詢圖的查詢集。每個(gè)查詢集包含50個(gè)具有相同數(shù)量節(jié)點(diǎn)的連通圖。由于VF3算法是單機(jī)上非常高效的算法,其性能優(yōu)于VF2[4]、L2G[24]、LAD[11]和RI[10]算法,因此本實(shí)驗(yàn)將與VF3算法進(jìn)行比較。實(shí)驗(yàn)結(jié)果中,平均時(shí)間為每組查詢圖得到子圖同構(gòu)所有解計(jì)算的總時(shí)間與查詢數(shù)量的商,平均時(shí)間作為評(píng)估指標(biāo)更能體現(xiàn)子圖同構(gòu)算法的時(shí)間效率。

實(shí)驗(yàn)結(jié)果如圖3所示,SSMGNN-yeast與VF3-yeast分別表示SSMGNN 算法與VF3算法在yeast數(shù)據(jù)集上的平均運(yùn)行時(shí)間;同理,SSMGNN-human與VF3-human分別表示2種算法在human數(shù)據(jù)集上的平均運(yùn)行時(shí)間。通過(guò)實(shí)驗(yàn)對(duì)比可知:

圖3 human與yeast數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果

1)當(dāng)查詢集為Q4時(shí),VF3算法在2個(gè)數(shù)據(jù)集上的平均求解時(shí)間較少,優(yōu)于本算法,其原因是在算法執(zhí)行過(guò)程中,構(gòu)建ADD 需要消耗一定的時(shí)間,并且SSMGNN 算法利用圖神經(jīng)網(wǎng)絡(luò)提取節(jié)點(diǎn)的鄰域信息作為過(guò)濾條件,在模式圖較小的時(shí)候,其鄰域包含信息較少,從而過(guò)濾效果并不明顯。然而,隨著查詢圖規(guī)模的增加,SSMGNN 算法的平均時(shí)間性能明顯優(yōu)于VF3算法,且時(shí)間增幅小于VF3算法,這表明本算法在處理較大規(guī)模的查詢圖時(shí)更具有優(yōu)勢(shì)。盡管當(dāng)查詢圖規(guī)模增加時(shí),2個(gè)算法的時(shí)間復(fù)雜度都明顯增加,但是本算法通過(guò)優(yōu)化匹配順序與增加節(jié)點(diǎn)鄰域信息作為過(guò)濾條件,有效減小了搜索空間,使得時(shí)間效率得到提升。

2)VF3算法在human數(shù)據(jù)集的求解時(shí)間比在yeast數(shù)據(jù)集上耗時(shí)更長(zhǎng)。其原因是,human數(shù)據(jù)集是稠密圖并且標(biāo)簽更少,VF3算法在human數(shù)據(jù)集需要花費(fèi)更多的時(shí)間進(jìn)行搜索求解。但是,SSMGNN 算法在稠密和稀疏數(shù)據(jù)集上的求解時(shí)間相當(dāng)。由此表明,本算法不僅在稀疏圖上能夠高效求解,并且在稠密圖上的求解效率遠(yuǎn)超于VF3。

查詢集的聚合時(shí)間如表1所示,對(duì)于不同規(guī)模下的查詢圖,鄰域信息聚合的平均時(shí)間都在0.001 2 s左右,由此可見,圖神經(jīng)網(wǎng)絡(luò)在4～32個(gè)節(jié)點(diǎn)的規(guī)模下都能夠花費(fèi)非常少的時(shí)間對(duì)節(jié)點(diǎn)的鄰域信息進(jìn)行特征提取。

表1 查詢集的鄰域聚合時(shí)間

在實(shí)驗(yàn)的過(guò)程中發(fā)現(xiàn),對(duì)于鄰域信息聚合時(shí),并不是聚合越多的鄰域信息,其過(guò)濾效果越好,在聚合時(shí)所選擇的k值(節(jié)點(diǎn)的k步鄰居)為2時(shí),效果最好。原因是human與yeast數(shù)據(jù)集中的查詢圖的半徑范圍幾乎不超過(guò)3,當(dāng)k值越大時(shí),會(huì)使得所有節(jié)點(diǎn)的鄰域信息趨于一致,從而降低其過(guò)濾效果。

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

提出了一種結(jié)合圖神經(jīng)網(wǎng)絡(luò)與符號(hào)代數(shù)決策圖解決子圖同構(gòu)問題的算法。該算法利用圖神經(jīng)網(wǎng)絡(luò)聚合節(jié)點(diǎn)鄰居信息,提高了過(guò)濾候選節(jié)點(diǎn)的效率,并且基于候選集、度與子圖的結(jié)構(gòu)等特征提出了一種優(yōu)化的匹配順序。其次,構(gòu)建了關(guān)于數(shù)據(jù)集、查詢圖與候選集的ADD 圖,使用符號(hào)ADD 操作實(shí)現(xiàn)了在單機(jī)上并行劃分候選區(qū)并進(jìn)行回溯求解。實(shí)驗(yàn)結(jié)果表明,該算法有效提高了子圖同構(gòu)問題的求解效率。在未來(lái)的工作中,將研究如何使用符號(hào)ADD并行求解子圖同構(gòu)問題,進(jìn)一步提高在單機(jī)上的求解效率。