基于符號OBDD的子圖同構(gòu)約束求解算法

劉桂珍， 徐周波

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

作為一種結(jié)構(gòu)化數(shù)據(jù)，圖數(shù)據(jù)所含語義信息豐富，實(shí)際生活中大部分?jǐn)?shù)據(jù)都能夠轉(zhuǎn)化為圖進(jìn)行描述。圖匹配技術(shù)是實(shí)現(xiàn)圖數(shù)據(jù)高效處理的重要方法之一，其目標(biāo)是確定模式圖和目標(biāo)圖中頂點(diǎn)和邊之間的對應(yīng)關(guān)系，從而判斷2個圖之間的相似度。圖匹配問題可通過定義子圖同構(gòu)、圖同構(gòu)、最大公共子圖等方式進(jìn)行求解。其中，子圖同構(gòu)要求2個圖的頂點(diǎn)和邊之間嚴(yán)格遵循一一對應(yīng)關(guān)系，匹配結(jié)果與模式圖的結(jié)構(gòu)和屬性完全一致[1]。子圖同構(gòu)主要應(yīng)用于生物化學(xué)[2]、社交網(wǎng)絡(luò)[3]等對匹配要求較高的領(lǐng)域。目前，已存在Ullman算法[4]、VF2算法[5]等大量經(jīng)典的子圖同構(gòu)求解算法，但隨著圖數(shù)據(jù)規(guī)模的不斷增大，這些算法的復(fù)雜度呈指數(shù)級增長，無法有效完成問題的求解。

約束滿足問題(constraint satisfaction problem，簡稱CSP)作為人工智能領(lǐng)域一種通用的求解范例，在裝配規(guī)劃、調(diào)度配置、圖匹配等領(lǐng)域有著廣泛的應(yīng)用[6]。研究人員已經(jīng)提出了眾多基于CSP的子圖同構(gòu)求解算法[7-9]。約束滿足問題的求解屬于NP-hard問題，因此，在對子圖同構(gòu)問題進(jìn)行約束求解過程中，其計(jì)算復(fù)雜度較高。為此，引入有序二叉決策圖(ordered binary decision diagram，簡稱OBDD)概念及其相關(guān)的符號操作技術(shù)[10-11]。OBDD是布爾函數(shù)的一種等價形式的圖形表示，具有高緊湊性、易操作等特點(diǎn)，其所有的運(yùn)算操作都以集合的方式進(jìn)行處理，能夠在CSP求解過程中提供一種隱式表示和搜索的方法，同時能降低組合復(fù)雜度和狀態(tài)空間復(fù)雜度。文獻(xiàn)[12-13]采用基于OBDD的符號算法，通過實(shí)驗(yàn)證明了符號技術(shù)能提高CSP的求解效率。Cortadella等[14]將符號OBDD運(yùn)用于子圖同構(gòu)問題的求解中，并通過實(shí)驗(yàn)證明了基于OBDD的方法明顯優(yōu)于傳統(tǒng)的Ullman算法，但該算法未充分利用圖中的結(jié)構(gòu)信息，導(dǎo)致求解過程中存在冗余搜索。針對上述問題，提出了基于符號OBDD的子圖同構(gòu)約束求解算法。

1 相關(guān)基礎(chǔ)知識

1.1 子圖同構(gòu)

給定模式圖Gp=(Np，Ep)與目標(biāo)圖Gt=(Nt，Et)，其中Np和Nt分別為2個圖頂點(diǎn)的集合，Ep、Et分別為2個圖邊的集合，且模式圖與目標(biāo)圖均為無向圖。

定義1對于給定的模式圖Gp=(Np，Ep)有?u，u′∈Np，且(u，u′)∈Ep，目標(biāo)圖Gt=(Nt，Et)有?v，v′∈Nt，(v，v′)∈Et，若存在一個單射函數(shù)f：Np→Nt，滿足?(u，u′)∈Ep??(v，v′)∈Et，且Gp?Gt，則Gp與Gt的子圖是同構(gòu)的。模式圖和目標(biāo)圖示例如圖1所示。

圖1 模式圖和目標(biāo)圖示例

1.2 約束滿足問題

約束滿足問題(CSP)是人工智能和計(jì)算機(jī)科學(xué)領(lǐng)域中一項(xiàng)重要研究內(nèi)容[12]。一個約束滿足問題一般可定義為一個三元組P〈V，D，C〉，其中：

1)V為由n個變量v1，v2，…，vn組成的有限變量集，即V={v1，v2，…，vn}。

2)D為n個變量的值域集組成的集合，對于?vi∈V，有Di∈D，i=1，2,…，n，即D={D1，D2，…，Dn}。

3)C為約束關(guān)系集合，C={c1，c2，…，cm}，m=1，2，…；約束ci與變量集{vi1，vi2，…，vij}?X相關(guān)，ci?D(xi1)×D(xi2)×… ×D(xij)，則稱ci為定義在變量集{vi1，vi2，…，vij}?X上的j元約束(i=1，2，…，m，1≤j≤n)；若C中所有約束均為一元或二元約束，則稱該CSP為二元CSP，本文只討論二元CSP的求解。

CSP的求解目標(biāo)就是在滿足約束集C的所有約束條件下，找到變量集V在值域D的一個解或所有解。

1.3 有序二叉決策圖

有序二叉決策圖(OBDD)是布爾函數(shù)的一種圖形、數(shù)學(xué)描述技術(shù)。

定義2對于從{0，1}n到{0，1}的布爾函數(shù)f(x1，x2，…，xn)和給定變量序π，在表示布爾函數(shù)族#f(x1，x2，…，xn)的二叉決策圖(binary decision diagram，簡稱BDD)中，若任一有向路徑上的變量x1，x2，…，xn均以變量序π所規(guī)定的次序依次出現(xiàn)，則稱該BDD為布爾函數(shù)f(x1，x2，…，xn)的有序二叉決策圖。

OBDD是一個有向無環(huán)圖，節(jié)點(diǎn)包含根節(jié)點(diǎn)、終節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)3種類型。其中，終節(jié)點(diǎn)有且僅有2個，用來表示布爾常量的0和1。每個非終節(jié)點(diǎn)都有2條輸出的分支分別連接到下一節(jié)點(diǎn)，即0分支和1分支。在OBDD任何一條路徑上，每個變量都依照變量序π所限定的次序出現(xiàn)一次。

OBDD常用的符號操作包括Apply操作、ITE操作、置換操作和量化操作，能夠?qū)崿F(xiàn)許多布爾函數(shù)的運(yùn)算，以解決由問題規(guī)模變大帶來的組合爆炸問題。

1.4 弧一致性技術(shù)

CSP求解方法主要分為基于回溯的搜索方法和基于推理的方法兩大類[13]?；谒阉鞯姆椒ㄖ饕曰诨厮莸姆椒榇恚厮菟惴ㄊ且环N完備的算法，能夠求出問題所有的解，但求解較大規(guī)模的CSP效率較低?；谕评淼姆椒ㄖ饕s束傳播算法、桶消元算法、樹分解算法等，能夠縮減問題的規(guī)模。其中，約束傳播算法是指在變量賦值過程中，將與變量相關(guān)的約束條件進(jìn)行判斷，若存在一組賦值情況不滿足約束條件，則對該賦值進(jìn)行刪除，并通過約束傳播的方式將該刪除操作擴(kuò)展到整個搜索空間。

約束傳播技術(shù)主要包括節(jié)點(diǎn)一致性技術(shù)、弧一致性(arc consistency，簡稱AC)技術(shù)[15-16]、路徑一致性技術(shù)等。其中，弧一致性技術(shù)是提高CSP求解效率的一種方法，能夠在求解過程中對不滿足約束條件的值進(jìn)行過濾，其定義如下。

定義3對于二元CSP約束圖中的任一約束C(xi，yi)，若xi的值域能滿足xi上的一元約束的每一個值a，都能在xj的值域中找到一個值b滿足xj上的一元約束，且(a，b)滿足C(xi，yi)，則稱它是弧一致的。

根據(jù)定義3可知，當(dāng)且僅當(dāng)約束圖的每一條約束都滿足弧一致，則說明一個CSP是弧一致的。本算法采用弧一致性技術(shù)與回溯算法相結(jié)合方法對子圖同構(gòu)進(jìn)行求解。在子圖同構(gòu)回溯求解過程中，對約束條件進(jìn)行弧一致性檢查，將不滿足弧一致的分支不進(jìn)行拓展，減少搜索次數(shù)，達(dá)到降低狀態(tài)空間復(fù)雜度的目的。

2 基于OBDD的子圖同構(gòu)約束求解算法

2.1 子圖同構(gòu)問題的CSP模型

給定模式圖Gp=(Np，Ep)與目標(biāo)圖Gt=(Nt，Et)，通過建立子圖同構(gòu)問題的CSP模型，將子圖同構(gòu)問題轉(zhuǎn)化為CSP進(jìn)行求解。為此，定義一個CSP三元組P〈V，D，C〉，其中：

1)V={v1，v2,…，vn}，表示n個變量的有限集，分別對應(yīng)于模式圖的n個頂點(diǎn){u1，u2，…，un}。

2)D={D1，D2,…，Dn}，表示變量X對應(yīng)的值域集，D中的值分別對應(yīng)于目標(biāo)圖中的m個頂點(diǎn){w1，w2,…，wm}。

3)C={c1，c2，…，ci}為約束關(guān)系集。根據(jù)目標(biāo)圖和模式圖的特征，建立以下約束條件：

度約束c1。對于?u∈Np，頂點(diǎn)u的度數(shù)表示為d(u)；對于?w∈Nt，頂點(diǎn)w的度數(shù)表示為d(w)，則有

d(u)

(1)

邊約束c2。設(shè)a(u)表示u的所有鄰接點(diǎn)，若有?u，u′∈Np∧?u′∈a(u)，在Gt中滿足?w，w′∈Nt，且?w′∈a(w)，則有

?(u，u′)∈Ep??(w，w′)∈Et。

(2)

相鄰約束c3。對于?u,u′∈Vp，?w,w′∈Vt，若u和u′是Gp中任意2個相鄰的頂點(diǎn)，即

a(u)={u′|(u,u′)∈Ep}，

(3)

設(shè)f(u)為變量vu在目標(biāo)圖中對應(yīng)的取值，若滿足f(u)=w，則有f(u′)=w′，且w和w′滿足：

a(w)={w′|(w,w′)∈Et}。

(4)

局部全不同約束c4。在滿足c3的條件下，對于模式圖中任意頂點(diǎn)u及其鄰接點(diǎn)u′、u″所對應(yīng)的變量在目標(biāo)圖中的取值分別為f(u′)、f(u″)，滿足：

(5)

全局全不同約束c5。令T()表示全局全不同約束(GAllDifferent)，對于Gp中各個頂點(diǎn)所對應(yīng)的變量V={v1，v2，…，vn}，在Gt所對應(yīng)的取值均不相同，約束表示為

?vi∈X?T({f(vi)|vi=f(vi)}),i=1,2,…,n。

(6)

CSP求解的目標(biāo)是找到變量集V的完全賦值，使約束集C定義的約束條件均得到滿足。CSP的一個解表示找到一個子圖同構(gòu)的解，CSP的所有解表示在目標(biāo)圖中找到所有與模式圖同構(gòu)的子圖。

2.2 CSP模型的符號OBDD描述

表1 變量的編碼與布爾表示形式

根據(jù)OBDD的表示方法及相關(guān)操作，得到變量的OBDD表示形式。例如，在已知變量序π:x0

圖2 變量v1的OBDD表示

CSP模型的約束條件可描述為：

1)度約束c1。通過OBDD符號操作計(jì)算圖中各個頂點(diǎn)的度。例如，設(shè)模式圖Gp對應(yīng)的OBDD表示為Gp(x，y)，其頂點(diǎn)編碼為X=(x1，x2，…，xn)，則采用OBDD操作技術(shù)中的存在量化操作?X(Gp(x，y))進(jìn)行計(jì)算，結(jié)果為真的賦值的個數(shù)，即任意頂點(diǎn)u∈Gp的度數(shù)。

2)邊約束c2。約束圖中的邊表示頂點(diǎn)與頂點(diǎn)之間的二元關(guān)系，針對模式圖，設(shè)邊的兩端頂點(diǎn)分別用二進(jìn)制向量X=(x1，x2，…，xn)，Y=(y1，y2，…，yn)表示，得到圖Gp中的邊的編碼分別為：000001、000010、000011、001000、001010、001100、001101、010000、010001、010011、011000、011010、011100、011101、100001、100011、101001、101011。

邊的起始節(jié)點(diǎn)用x表示，終節(jié)點(diǎn)用y表示，則節(jié)點(diǎn)之間的邊用x到y(tǒng)的二元關(guān)系表示。對于模式圖Gp，CSP模型中的約束條件c2可表示為一個布爾函數(shù)：

根據(jù)上述布爾函數(shù)Gp(x，y)，在已知變量序π:x0

圖3 Gp中邊約束c2的OBDD表示

同理，對于目標(biāo)圖中邊的兩端頂點(diǎn)分別用二進(jìn)制向量V=(v1,v2,…，vn)，W=(w1,w2,…，wn)表示。在已知變量序π的前提下，得到約束條件c2的OBDD表示如圖4所示。

圖4 Gt中邊約束c2的OBDD表示

3)相鄰約束c3。采用OBDD中的“合取操作”，可以依次得到各個頂點(diǎn)的所有相鄰頂點(diǎn)。例如，對于圖Gp中的頂點(diǎn)u1，其對應(yīng)的相鄰約束可表示為一個布爾函數(shù)：

根據(jù)該布爾函數(shù)可得到相應(yīng)的OBDD表示形式。根據(jù)上述方法，依次得到各個頂點(diǎn)的相鄰約束。

2.3 符號求解算法

基于OBDD的子圖同構(gòu)約束求解算法偽代碼為算法1，構(gòu)建OBDD的偽代碼為算法2。

算法1OBDD-SI

輸入：P(X，D，C)、變量集X、值域D、約束集C、變量匹配順序S；

輸出：得到CSP的解，返回result。

1 procedure Pre(P(X，D，C))

2 if 滿足d(u)≤d(v) doD←D′;

3 procedure solver

4 CreateOBDD(P(X，D，C)); Pre(P(X，D，C));

5 ifX=? then

6 return result;

7 else

8xi=VarOrder(S);//根據(jù)變量序進(jìn)行匹配

9X=X-{vi};

10 whileD(vi)≠? do;

11a=ValueSelect(vi);//對變量vi進(jìn)行賦值

12D(vi)=D(vi)-{a};//從值域中刪除a

13S(vi)=ITE(vi，0，1);//構(gòu)建OBDD

14 APPLY(G，func(x)，0);//根據(jù)OBDD中的Apply操作進(jìn)行判斷

15 if 滿足AC(X，D，C) then solver

16 else return false

17 return result。

算法2CreateOBDD

輸入:圖的頂點(diǎn)數(shù)n；

輸出：G的OBDD表示。

1 for (i=1 ton) do

2 pos=v&(int)pow(2，i);//轉(zhuǎn)換成二進(jìn)制

3 if pos=0

4p=ITE(x，0，1);//創(chuàng)建節(jié)點(diǎn)

5 elsep=ITE(1，x，0);

6 endif

7E=ITE(func，p，0);//創(chuàng)建邊

8G=ITE(E，1，0);//創(chuàng)建圖

9 endfor

10 returnG。

算法2的主要求解步驟為：

1) 構(gòu)建子圖同構(gòu)的CSP模型P〈X，D，C〉，基于已知的變量序π，對CSP模型進(jìn)行OBDD描述。

2) 預(yù)處理。通過OBDD符號操作計(jì)算圖中各頂點(diǎn)的度，根據(jù)約束條件c1，從值域中刪除不可能成為變量取值的值，從而完成對變量值域的初步縮減。

3) 設(shè)變量集V={v1，v2，…，vn}為初始等待隊(duì)列Q，結(jié)合步驟2)的計(jì)算結(jié)果，得到頂點(diǎn)最大度數(shù)匹配順序π；當(dāng)?shù)却?duì)列Q不為空時，根據(jù)匹配順序π，從中取出變量x1，x2，…，xn依次進(jìn)行賦值。

4) 在變量賦值過程中執(zhí)行弧一致檢查。采用OBDD的Apply操作對當(dāng)前賦值是否滿足約束條件進(jìn)行判斷，將約束條件進(jìn)行“合取操作”。操作結(jié)果若非空集，則證明滿足約束條件，繼續(xù)從Q中取出下一個變量進(jìn)行賦值；若OBDD符號操作得到的結(jié)果為空集，則算法產(chǎn)生回溯，對當(dāng)前變量重新賦值。重復(fù)執(zhí)行上述過程，直至變量集V中所有的變量都被賦值，且所有變量的賦值均滿足約束條件C。此時算法執(zhí)行結(jié)束，得到目標(biāo)圖與模式圖所有同構(gòu)的子圖，完成對子圖同構(gòu)問題的求解。

3 實(shí)驗(yàn)分析

基于符號OBDD的子圖同構(gòu)約束求解算法(OBDD-SI)，結(jié)合了Colorado大學(xué)開發(fā)的CUDD軟件包，在VS2012環(huán)境下采用C語言編程實(shí)現(xiàn)。硬件環(huán)境為Inter Core i5-4690 CPU，主頻3.5 GHz，內(nèi)存8 GiB，操作系統(tǒng)為Windows 764 bit。實(shí)驗(yàn)選取不同的公開數(shù)據(jù)集進(jìn)行測試，數(shù)據(jù)集中每一對模式圖和目標(biāo)圖為一個實(shí)例，將求解全部實(shí)例得到子圖同構(gòu)所有解的計(jì)算總時間作為算法性能的評價標(biāo)準(zhǔn)，并將本算法與LAD算法和VF2算法進(jìn)行對比。

1)實(shí)驗(yàn)1采用M4Dr-n、Scalefree、AIDS三種數(shù)據(jù)集進(jìn)行測試。其中，M4Dr-n表示正則網(wǎng)格圖，Scale-free表示無標(biāo)度網(wǎng)絡(luò)圖，AIDS代表多種抗HIV活性分子的拓?fù)浣Y(jié)構(gòu)圖。實(shí)驗(yàn)1數(shù)據(jù)集信息如表2所示，模式圖和目標(biāo)圖的頂點(diǎn)個數(shù)分別為np、nt，模式圖與目標(biāo)圖的頂點(diǎn)個數(shù)比值為p。實(shí)驗(yàn)1運(yùn)行時間對比如表3所示，其中“-”表示在5 min內(nèi)無法求得全部解。從表3可看出，針對目標(biāo)圖規(guī)模較小的AIDS數(shù)據(jù)集，VF2算法和LAD算法計(jì)算時間較少，優(yōu)于本算法，這是由于在本算法執(zhí)行過程中，構(gòu)建OBDD需要消耗一定的時間。然而，對于M4Dr-n和Scale-free數(shù)據(jù)集，本算法和LAD算法均優(yōu)于VF2算法，且本算法在目標(biāo)圖規(guī)模較大的情況下優(yōu)于LAD算法。

表2 實(shí)驗(yàn)1數(shù)據(jù)集信息

表3 實(shí)驗(yàn)1運(yùn)行時間對比

2)本組實(shí)驗(yàn)采用一類由圖像分割生成的中型規(guī)模的數(shù)據(jù)集Images-PR15進(jìn)行測試，實(shí)驗(yàn)2運(yùn)行時間對比如表4所示。從表4可看出，傳統(tǒng)的VF2算法無法在規(guī)定時間內(nèi)求得子圖同構(gòu)的全部解，本算法優(yōu)于VF2算法和LAD算法。

表4 實(shí)驗(yàn)2運(yùn)行時間對比

3)本組實(shí)驗(yàn)采用生物化學(xué)領(lǐng)域中規(guī)模較大的PDBSv1、PDBSv3、PPI三種數(shù)據(jù)集進(jìn)行算法驗(yàn)證。其中，PDBSV1、PDBSV2為稀疏圖，PPI為稠密圖，數(shù)據(jù)集中模式圖頂點(diǎn)數(shù)np=8。實(shí)驗(yàn)3數(shù)據(jù)集信息如表5所示。本組實(shí)驗(yàn)將本算法與LAD算法進(jìn)行對比，實(shí)驗(yàn)3運(yùn)行時間對比如表6所示。從表6可看出，隨著目標(biāo)圖規(guī)模的增大，本算法逐漸體現(xiàn)其良好的求解性能，尤其是稠密圖，本算法明顯優(yōu)于LAD算法。

表5 實(shí)驗(yàn)3數(shù)據(jù)集信息

表6 實(shí)驗(yàn)3運(yùn)行時間對比

由上述實(shí)驗(yàn)結(jié)果可知，由于OBDD高效緊湊的特點(diǎn)以及符號操作可以實(shí)現(xiàn)狀態(tài)空間或變量組合的隱式表示和搜索，在對子圖同構(gòu)的CSP模型進(jìn)行求解時，可以完成多條約束的并行處理，本算法能提高子圖同構(gòu)問題的求解效率，在目標(biāo)圖規(guī)模相對較大的情況下，算法具有明顯優(yōu)勢。

4 結(jié)束語

隨著圖規(guī)模的增大，傳統(tǒng)的算法無法對子圖同構(gòu)進(jìn)行求解，提出了基于OBDD的子圖同構(gòu)約束求解算法。通過分析模式圖和目標(biāo)圖中頂點(diǎn)度數(shù)、邊、鄰域和結(jié)構(gòu)特征等信息，建立子圖同構(gòu)問題的CSP模型。采用OBDD對CSP模型進(jìn)行符號化描述，并基于OBDD的操作技術(shù)，結(jié)合回溯算法和弧一致性技術(shù)，求得子圖同構(gòu)所有的解。實(shí)驗(yàn)結(jié)果表明，在圖規(guī)模較大的情況下，本算法的求解效率優(yōu)于傳統(tǒng)的VF2算法和LAD算法。