劉桂珍， 徐周波

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

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

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

1 相關基礎知識

1.1 子圖同構

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

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

圖1 模式圖和目標圖示例

1.2 約束滿足問題

約束滿足問題(CSP)是人工智能和計算機科學領域中一項重要研究內容[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為約束關系集合，C={c1，c2，…，cm}，m=1，2，…；約束ci與變量集{vi1，vi2，…，vij}?X相關，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的求解目標就是在滿足約束集C的所有約束條件下，找到變量集V在值域D的一個解或所有解。

1.3 有序二叉決策圖

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

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

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

OBDD常用的符號操作包括Apply操作、ITE操作、置換操作和量化操作，能夠實現許多布爾函數的運算，以解決由問題規(guī)模變大帶來的組合爆炸問題。

1.4 弧一致性技術

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

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

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

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

2 基于OBDD的子圖同構約束求解算法

2.1 子圖同構問題的CSP模型

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

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

2)D={D1，D2,…，Dn}，表示變量X對應的值域集，D中的值分別對應于目標圖中的m個頂點{w1，w2,…，wm}。

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

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

d(u)

(1)

邊約束c2。設a(u)表示u的所有鄰接點，若有?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個相鄰的頂點，即

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

(3)

設f(u)為變量vu在目標圖中對應的取值，若滿足f(u)=w，則有f(u′)=w′，且w和w′滿足：

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

(4)

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

(5)

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

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

(6)

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

2.2 CSP模型的符號OBDD描述

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

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

圖2 變量v1的OBDD表示

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

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

2)邊約束c2。約束圖中的邊表示頂點與頂點之間的二元關系，針對模式圖，設邊的兩端頂點分別用二進制向量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é)點用x表示，終節(jié)點用y表示，則節(jié)點之間的邊用x到y(tǒng)的二元關系表示。對于模式圖Gp，CSP模型中的約束條件c2可表示為一個布爾函數：

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

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

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

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

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

根據該布爾函數可得到相應的OBDD表示形式。根據上述方法，依次得到各個頂點的相鄰約束。

2.3 符號求解算法

基于OBDD的子圖同構約束求解算法偽代碼為算法1，構建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);//根據變量序進行匹配

9X=X-{vi};

10 whileD(vi)≠? do;

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

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

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

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

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

16 else return false

17 return result。

算法2CreateOBDD

輸入:圖的頂點數n；

輸出：G的OBDD表示。

1 for (i=1 ton) do

2 pos=v&(int)pow(2，i);//轉換成二進制

3 if pos=0

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

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) 構建子圖同構的CSP模型P〈X，D，C〉，基于已知的變量序π，對CSP模型進行OBDD描述。

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

3) 設變量集V={v1，v2，…，vn}為初始等待隊列Q，結合步驟2)的計算結果，得到頂點最大度數匹配順序π；當等待隊列Q不為空時，根據匹配順序π，從中取出變量x1，x2，…，xn依次進行賦值。

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

3 實驗分析

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

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

表2 實驗1數據集信息

表3 實驗1運行時間對比

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

表4 實驗2運行時間對比

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

表5 實驗3數據集信息

表6 實驗3運行時間對比

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

4 結束語

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