基于符号OBDD的子图同构约束求解算法

刘桂珍， 徐周波

(桂林电子科技大学 计算机与信息安全学院，广西 桂林 541004)

作为一种结构化数据，图数据所含语义信息丰富，实际生活中大部分数据都能够转化为图进行描述。图匹配技术是实现图数据高效处理的重要方法之一，其目标是确定模式图和目标图中顶点和边之间的对应关系，从而判断2个图之间的相似度。图匹配问题可通过定义子图同构、图同构、最大公共子图等方式进行求解。其中，子图同构要求2个图的顶点和边之间严格遵循一一对应关系，匹配结果与模式图的结构和属性完全一致[1]。子图同构主要应用于生物化学[2]、社交网络[3]等对匹配要求较高的领域。目前，已存在Ullman算法[4]、VF2算法[5]等大量经典的子图同构求解算法，但随着图数据规模的不断增大，这些算法的复杂度呈指数级增长，无法有效完成问题的求解。

约束满足问题(constraint satisfaction problem，简称CSP)作为人工智能领域一种通用的求解范例，在装配规划、调度配置、图匹配等领域有着广泛的应用[6]。研究人员已经提出了众多基于CSP的子图同构求解算法[7-9]。约束满足问题的求解属于NP-hard问题，因此，在对子图同构问题进行约束求解过程中，其计算复杂度较高。为此，引入有序二叉决策图(ordered binary decision diagram，简称OBDD)概念及其相关的符号操作技术[10-11]。OBDD是布尔函数的一种等价形式的图形表示，具有高紧凑性、易操作等特点，其所有的运算操作都以集合的方式进行处理，能够在CSP求解过程中提供一种隐式表示和搜索的方法，同时能降低组合复杂度和状态空间复杂度。文献[12-13]采用基于OBDD的符号算法，通过实验证明了符号技术能提高CSP的求解效率。Cortadella等[14]将符号OBDD运用于子图同构问题的求解中，并通过实验证明了基于OBDD的方法明显优于传统的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均以变量序π所规定的次序依次出现，则称该BDD为布尔函数f(x1，x2，…，xn)的有序二叉决策图。

OBDD是一个有向无环图，节点包含根节点、终节点和内部节点3种类型。其中，终节点有且仅有2个，用来表示布尔常量的0和1。每个非终节点都有2条输出的分支分别连接到下一节点，即0分支和1分支。在OBDD任何一条路径上，每个变量都依照变量序π所限定的次序出现一次。

OBDD常用的符号操作包括Apply操作、ITE操作、置换操作和量化操作，能够实现许多布尔函数的运算，以解决由问题规模变大带来的组合爆炸问题。

1.4 弧一致性技术

CSP求解方法主要分为基于回溯的搜索方法和基于推理的方法两大类[13]。基于搜索的方法主要以基于回溯的方法为代表，回溯算法是一种完备的算法，能够求出问题所有的解，但求解较大规模的CSP效率较低。基于推理的方法主要包括约束传播算法、桶消元算法、树分解算法等，能够缩减问题的规模。其中，约束传播算法是指在变量赋值过程中，将与变量相关的约束条件进行判断，若存在一组赋值情况不满足约束条件，则对该赋值进行删除，并通过约束传播的方式将该删除操作扩展到整个搜索空间。

约束传播技术主要包括节点一致性技术、弧一致性(arc consistency，简称AC)技术[15-16]、路径一致性技术等。其中，弧一致性技术是提高CSP求解效率的一种方法，能够在求解过程中对不满足约束条件的值进行过滤，其定义如下。

定义3对于二元CSP约束图中的任一约束C(xi，yi)，若xi的值域能满足xi上的一元约束的每一个值a，都能在xj的值域中找到一个值b满足xj上的一元约束，且(a，b)满足C(xi，yi)，则称它是弧一致的。

根据定义3可知，当且仅当约束图的每一条约束都满足弧一致，则说明一个CSP是弧一致的。本算法采用弧一致性技术与回溯算法相结合方法对子图同构进行求解。在子图同构回溯求解过程中，对约束条件进行弧一致性检查，将不满足弧一致的分支不进行拓展，减少搜索次数，达到降低状态空间复杂度的目的。

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。

边的起始节点用x表示，终节点用y表示，则节点之间的边用x到y的二元关系表示。对于模式图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);//创建节点

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

6 endif

7E=ITE(func，p，0);//创建边

8G=ITE(E，1，0);//创建图

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) 在变量赋值过程中执行弧一致检查。采用OBDD的Apply操作对当前赋值是否满足约束条件进行判断，将约束条件进行“合取操作”。操作结果若非空集，则证明满足约束条件，继续从Q中取出下一个变量进行赋值；若OBDD符号操作得到的结果为空集，则算法产生回溯，对当前变量重新赋值。重复执行上述过程，直至变量集V中所有的变量都被赋值，且所有变量的赋值均满足约束条件C。此时算法执行结束，得到目标图与模式图所有同构的子图，完成对子图同构问题的求解。

3 实验分析

基于符号OBDD的子图同构约束求解算法(OBDD-SI)，结合了Colorado大学开发的CUDD软件包，在VS2012环境下采用C语言编程实现。硬件环境为Inter Core i5-4690 CPU，主频3.5 GHz，内存8 GiB，操作系统为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可看出，针对目标图规模较小的AIDS数据集，VF2算法和LAD算法计算时间较少，优于本算法，这是由于在本算法执行过程中，构建OBDD需要消耗一定的时间。然而，对于M4Dr-n和Scale-free数据集，本算法和LAD算法均优于VF2算法，且本算法在目标图规模较大的情况下优于LAD算法。

表2 实验1数据集信息

表3 实验1运行时间对比

2)本组实验采用一类由图像分割生成的中型规模的数据集Images-PR15进行测试，实验2运行时间对比如表4所示。从表4可看出，传统的VF2算法无法在规定时间内求得子图同构的全部解，本算法优于VF2算法和LAD算法。

表4 实验2运行时间对比

3)本组实验采用生物化学领域中规模较大的PDBSv1、PDBSv3、PPI三种数据集进行算法验证。其中，PDBSV1、PDBSV2为稀疏图，PPI为稠密图，数据集中模式图顶点数np=8。实验3数据集信息如表5所示。本组实验将本算法与LAD算法进行对比，实验3运行时间对比如表6所示。从表6可看出，随着目标图规模的增大，本算法逐渐体现其良好的求解性能，尤其是稠密图，本算法明显优于LAD算法。

表5 实验3数据集信息

表6 实验3运行时间对比

由上述实验结果可知，由于OBDD高效紧凑的特点以及符号操作可以实现状态空间或变量组合的隐式表示和搜索，在对子图同构的CSP模型进行求解时，可以完成多条约束的并行处理，本算法能提高子图同构问题的求解效率，在目标图规模相对较大的情况下，算法具有明显优势。

4 结束语

随着图规模的增大，传统的算法无法对子图同构进行求解，提出了基于OBDD的子图同构约束求解算法。通过分析模式图和目标图中顶点度数、边、邻域和结构特征等信息，建立子图同构问题的CSP模型。采用OBDD对CSP模型进行符号化描述，并基于OBDD的操作技术，结合回溯算法和弧一致性技术，求得子图同构所有的解。实验结果表明，在图规模较大的情况下，本算法的求解效率优于传统的VF2算法和LAD算法。