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

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

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

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

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

1 相關概念

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

定義2 給定數(shù)據(jù)圖g=〈Vg,Eg,Lg,lg〉與查詢圖q=〈Vq,Eq,Lq,lq〉。圖q與圖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的一個有向無環(huán)圖,它滿足[19]:

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

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

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

4)圖中的每個節(jié)點u對應唯一一個函數(shù)fu。

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

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

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

圖1 SSMGNN算法的基本框架

2.1 生成候選集

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

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

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

2.2 確定匹配順序

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

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

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

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

2.3 候選區(qū)

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

2.3.1 ADD表示

給定圖G,其節(jié)點數(shù)量｜V｜=n,首先對圖G的節(jié)點與邊進行編碼。節(jié)點編碼可采用長度為m=log2n的二進制串X=(x1,x2,…,xm)表示[22-23]。邊代表節(jié)點與節(jié)點間的二元關系,因此邊記為(X,Y)=(x1,x2,…,xm,y1,y2,…,ym),其中:X表示邊的起始節(jié)點;Y表示邊的終節(jié)點。將數(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é)點;Y表示數(shù)據(jù)圖的節(jié)點。候選集的ADD表示記為C(X,Y)。

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

2.3.2 候選區(qū)構建

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

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

2.4 SSMGNN算法

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

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

3 實驗結果及分析

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

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

圖3 human與yeast數(shù)據(jù)集的實驗結果

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

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

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

表1 查詢集的鄰域聚合時間

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

4 結束語

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