基于对称破坏的子图同构约束求解算法

徐周波，梁轩瑜，刘华东,2+，戴瑀君

(1.桂林电子科技大学 广西可信软件重点实验室，广西 桂林 541004； 2.桂林电子科技大学 机电工程学院，广西 桂林 541004)

0 引 言

子图同构问题是图模式匹配[1]中的核心问题。求解子图同构问题的方法一般分为2类。基于树搜索的方法[2-5]，该类算法通常在状态空间表示(state space representation，SSR)中，采用基于回溯的深度优先搜索，结合启发式信息，以增量的方式，不断的在新状态下检查是否满足子图同构约束。该类算法的优点是不需要将所有状态保留在内存中，其分配的最大状态数与目标图节点数呈正比关系；基于约束满足问题(constraint satisfaction problem，CSP)求解的方法[6-9]，该类算法利用图中的属性和结构信息，结合约束传播、弧一致性等技术，迭代地在所有可能节点对中过滤掉一定不是解的节点对，最终留下的节点对即为所求解。该类算法优点是求解速度快，但是需要保留不满足约束的节点对以避免被重新搜索，因此对内存的需求较多。

研究者们从不同的角度致力于提高子图同构算法的求解效率并扩大问题求解规模，但子图同构问题所面临的组合复杂性问题，仍成为它们被广泛应用的瓶颈[10]。大量研究致力于使用更多的邻居关系来构建约束以减少搜索域，而忽略了重复解的问题。因此本文提出一种可避免解的重复搜索的子图同构约束求解算法，结合对称破坏思想，在求解过程中，利用对称破坏约束来避免解的重复搜索。通过一些标准库用例进行实验分析，其结果表明，与传统算法相比，本算法有效减少了重复解，提高了求解效率。

1 相关介绍

1.1 子图同构及约束满足问题

定义1 给定目标图Gt= 和模式图Gp=。 若存在单射函数f∶Vp→Vt使得 (u,v)∈Ep⟹(f(u),f(v))∈Et， 那么称Gp为Gt的一个同构子图。

子图同构问题是指在目标图中找到一个或所有与模式图同构的子图。本文的算法致力于求解所有与模式图同构的子图。

定义2 约束满足问题定义为三元组 ， 其中：

(1)X={x1,x2,…,xn} 为包含n个变量的有限集合；

(2)D={D(x1),D(x2),…,D(xn)} 为n个变量的值域；

(3)C={c1,c2,…,cm} 为约束集合，ci(xi1,xi2,…,xij)⊆Di1×Di2×…×Dij(i=1,2,…,m,1≤j≤n)， 其中xil∈X(l=1,2,…,j)，Dil为变量xil的域，称ci为定义在变量集 {xi1,xi2,…,xij}⊆X上的j元约束。

CSP求解的目标是找到变量集X的全部实例化，使得约束集C中的所有约束均得到满足。

将模式图中的节点构成变量域X，目标图中的节点构成值域D。 子图同构的一般CSP模型表示如下：

(1)变量域：X=Vp；

(2)值域： ∀xi∈Vp，Di=Vt；

(3)约束域： ∀i,j∈Gp(i

1.2 变量对称

用置换来描述对称性。In为包含1到n用于表示变量的整数集合，集合Sn表示In的所有置换，一个置换σ描述为向量 [1σ,2σ,…,nσ]。

定义3[11]给定i∈In和置换群G∈Sn，iσ为变量i经σ置换后对应的变量，则iG表示置换群G中i置换后对应的变量的集合：iG={iσ|σ∈G}。

定义4[11]给定i和置换群G，iG表示在置换群G中，能使节点i经置换σ不变的置换集：iG={σ∈G|iσ=i}。

CSP中的变量对称指能使 (xi=j)ρ=(xiσ=j) 的置换，其中j∈D(xi)，ρ为满足解的变量-值对之间的双射。例如，有如下约束满足问题。变量集为 {1,2,3}， 每个变量的值域为 {0,1,2,3,4,5}， 约束为{x1+x2+x3=5}。 可以知道，该CSP的其中两个解为 {x1=0,x2=2,x3=3} 和 {x1=2,x2=0,x3=3}， 即 [1σ,2σ,3σ]=[2,1,3]， 在同样的变量域和值域下，值0分配给变量x1或x2皆满足该CSP解的条件，那么称x1和x2为变量对称的。在本文中考虑的是变量对称。

2 基于对称性破坏的子图同构约束求解算法(VFSBC)

将子图同构约束求解与对称破坏技术结合，应用于子图同构CSP模型。首先通过检测模式图的自同构得到一系列置换，这些置换构成置换群。再对置换群进行群操作得到稳定链和陪集。最后，通过陪集生成节点间的字典序约束，构建子图同构CSP模型并使用回溯算法对其求解。

2.1 自同构检测

图的自同构指的是图与自身的同构。Houbraken[12]检测自同构的方法在迭代过程中存在保留大量冗余节点问题，针对此问题，本文在每次配对只记录邻居节点，然后根据当前记录信息与其它节点比较，从而降低了匹配次数及内存占用。本文自同构的检测方法，主要分为以下3个步骤。

步骤1 按节点的度将节点进行分类，将度相同的节点归入同一单元。整个检测过程依靠πa和πb两个划分，其中πa={A1|A2|…|Aa}， πb={A1|A2|…|Ab}， 每个划分由不同单元构成。此时上下层单元数都为n，具有相同度节点的上层划分单元与对应的下层划分单元具有相同的标记。图1(a)所示的模式图，其自同构检测过程如图1(b)所示。在搜索树顶部的初始划分中，节点1，2和3由于度数相同，因此位于同一单元中。

图1 自同构检测过程

步骤2 当上层划分单元Ai内的节点数量大于1时，将Ai内的每个节点依次与对应Bi内的所有节点进行组合配对。将当前配对的节点中，原属于Ai的节点放入新建的上层划分单元An+i中，原属于Bi的节点放入新建的下层划分单元Bn+i中。对于新建的An+i和新建的Bn+i内的节点，观察其邻接点，为邻接点添加连接边标记neibor，并记录新建上层分区单元An+i内节点的邻接点所属单元标记。对每个邻接点的所属单元标记所对应的上层分区单元Ai和下层分区单元Bi内的节点进行分类，对于Ai内的节点：将有neibor标记的节点保留在该Ai内，将没有neibor标记的节点从原所属单元移入到新建的上层分区单元A2n+i中，同时记录此新建A2n+i的单元标记并存入临时标记集Nlabel中。同理对Bi内节点进行分类，但并不需要保存新建B2n+i的单元标记。如图1(b)中步骤2(圆圈内的数字表示检测步骤)所示，πa中节点1与πb中节点1配对，置入具有相同单元标记的上下两个新单元中，其邻接点节点2与节点3因具有neibor标记而保留在原单元内。检查上层划分与下层划分内各单元，若上层单元Ai与下层单元Bi内的节点数量不一致，则向上回溯至重新选取节点配对，否则取临时标记集合Nlabel内的单元标记，找到与此单元标记对应的上层分区单元Ai，重复步骤2。

步骤3 当上层划分与下层划分的每个单元均仅包含一个节点时，若上层划分中的节点a与下层分区中的节点b的所属单元标记相同，且上层划分中的节点b与下层划分中的节点a的所属单元标记相同，则节点a和节点b构成一组生成置换。如图1(b)中步骤3所示，得到一组生成置换P1=(2，3)。 一系列生成置换构成自同构群G， 此自同构群即为作用于图中节点的置换群。在图1所示例子中，自同构群由P1和P2构成。

剪枝是一种缩小搜索空间的群优化技术，用于删除部分搜索树。通过已检测的生成置换构建映射集合，用于避免不必要的配对过程，同一映射集合内的节点可以映射到自身或集合内的其它节点。在图1(b)所示步骤2中，得到映射集合 {1}，{2}，{3}。 通过P1更新映射集合为 {1}，{2,3}。 由P2知，根据传递性，更新映射集合为{1,2,3}。在自同构检测过程中，若配对的节点属于同一映射集合，则删除当前搜索分支。

2.2 对称破坏约束

子图同构约束求解中，图的自同构导致重复解。如何将检测得到的自同构转化为一种约束，是约束求解中减少重复解的关键点。本文引入Puget[11]的生成破坏对称约束方法。首先通过置换群得到稳定链，其次利用稳定链求得陪集，最后，通过陪集生成字典序约束从而破坏对称。

置换群G中的置换通过将节点交换到序列中的不同位置而作用于节点序列。对于未改变节点位置的置换，如定义4中iG所示，称其为稳定。由稳定，稳定链定义为： ∀i∈In,Gi={iGi-1|G0=G,Gi={σ∈G∶1σ=1∧…∧iσ=i}}。 由P1和P2可得置换群G为： {[1, 2, 3], [1, 3, 2], [2,1, 3]}。 陪集Ui定义为：Ui=iGi-1，Ui表示在置换群Gi-1中，节点i所能映射的节点集合。在图1所示的例子中，U1={1,2},U2={2,3},U3={3}。

令r(j) 为能使j属于Ui且不等于j的最大i， 若除了Uj之外没有这样的Ui使之满足，则令r(j)=j， 由此可得对称破坏约束： ∀j∈In,r(j)≠j⟹xr(j)

在图1所示的例子中，r(1)=1，r(2)=1，r(3)=2， 由此可得对称破坏字典序约束为：x1

2.3 子图同构CSP模型

给定目标图Gt= 和模式图Gp=， 结合2.2节的对称破坏约束，给出本文子图同构问题的CSP模型：

(1)变量域：X=Vp；

(2)值域： ∀xi∈Vp,Di=Vt；

(3)约束域：

1)边约束c(i,j)： 如1.1节所述。

2)全不同alldiff约束：alldiff(x1,x2,…,xn)={(d1,d2,…,dn)|∀di∈D(xi),∀i≠j,di≠dj,i=1,2,…,n}。

3)度约束Ri： Ri={va∈Vt|deg(Gp,i)≤deg(Gt,va)}， 其中deg(Gp,i) 用于表示模式节点i的度， deg(Gt,va) 表示对应目标节点va的度。

5)对称破坏约束SBC：根据2.2节的方法生成对称破坏约束SBC。若变量受到alldiff约束的限制，那么最多可以用n-1个二元约束破坏CSP中的对称解。这些约束构成了对称性破坏约束SBC。

其中，alldiff约束用于在CSP求解中保证单射，限制一一对应的节点映射关系。Ri约束用于构造初始域，删除不满足此约束的变量值域。当模式节点和目标节点匹配时，只有目标节点的度大于或等于模式节点的度，才可能是导出子图同构。NDC约束用于获取更多的邻居信息以减少值的范围。选取不同k值效果不一，并不是k的值越大，效果越好，因为当图的规模很大时，矩阵计算是非常耗时的。在本文中，最小的模式图有4条边，因此统一设k值为4。

2.4 VFSBC算法伪代码

算法主要分4个步骤，第一步为各变量赋初始值域，第二步为自同构检测，第三步生成对称破坏约束，第四步完成约束求解。给出伪代码如下。

VFSBCAlgorithm:Gp=(Vp,Ep),Gt=(Vt,Et)

(1) domains(variablexvp)←Ri(Vp,Vt); //step1

(2) automorphism groupG←autoDetect(Gp); //step2

(3) symmetry break constraints←analyze(G); //step3

(4)selectvariablexvp∈Vp//step4

(5)selectvaluevt∈domain (xvp)

(6)ifsatisSBC && satisNDC

(7)ifsatisfy constrains in VF2then

(8) removexvpfromVp;

(9) removevtfrom domain (xvp);

(10) update values of variables;

(11)ifdomain (xvp)==∅then

(12) throw exception INCONSISTENT;

(13)ifvariables ((xvp)==∅)then

(14) solutions.add();

(15) return solutions;

算法第(1)行函数Ri根据模式图和目标图节点的度为每个变量返回初始值域。第(2)行函数autoDetect用于检测图中自同构并返回自同构群G。第(3)行函数analyze分析自同构群G并返回对称破坏约束。在求解过程中，按节点度的大小依次选取变量，结合CSP的基于回溯求解方法，若当前赋值满足SBC约束，NDC约束以及VF2相关约束，则通过alldiff约束更新剩余待匹配变量的值域。若变量未完全实例化前引起空值域，说明当前搜索分支无法找到解，算法向上回溯重新赋值；若变量完全实例化，变量集合为空，且对应赋值满足所有约束条件，说明找到一个解，并将其添加进解集中。

3 实验结果及分析

为验证本文算法的效率和正确性，在PC，Windows 7，3.5 GHz，8 GB内存环境下，使用Java语言实现算法程序，将本文算法与VF2算法及ILF算法进行了比较。实验使用AIDS(http://jenalib.leibniz-fli.de)和PDBSV2(http://www.rcsb.org)两个数据集，其中AIDS为抗艾滋病毒数据集，包含大量稀疏无向图，每个图表示化合物的原子结构。目标图数据集中包含10 000个图，平均每个图包含27.4条边。模式图按边的数量分为Q4、Q8、Q12、Q16、Q20、Q24这6组，每组内包含1000个小图。PDBSV2 数据集包含40种蛋白质，将模式图按边数量分为Q4、Q8、Q16、Q32、Q64、Q128这6组，每组内包含8个小图。目标图为包含4000个-12 000个节点的中等稀疏图。实验结果以求解速度作为主要评价标准，其中实验图表中平均时间，通过统计所有模式图与目标图的求解时间，求解平均值所得，其计算公式如下

(1)

其中，Timeall为求解分组内所有模式图和目标图的总时间，Numpattern为分组内模式图的数量，平均时间体现了求解单个模式图与所有目标图的所有解的效率。

基于本文所述，VFSBC算法通过对称破坏约束，避免对称子树的搜索，从而有效避免对称解的求解，降低了问题求解规模。在AIDS数据集中，平均求解时间如图2所示，其对应自同构检测时间如图3所示。由对比结果可知，在规模为Q4时，本数据集下VFSBC算法求解速度达到最快，为VF2算法的2.57倍，统计Q4-Q24这6组实验组，其平均求解速度是VF2算法的1.83倍。图的自同构数量越多，本文算法的优势越大，而自同构的检测时间仅占求解时间的极小比例。若图中没有自同构，如模式图为Q24的规模时，由于邻域约束的限制，在一定程度上减少了值域范围，相较VF2及ILF算法，同样具有一些优势。

图2 AIDS数据集中求解速度对比

图3 自同构检测耗时

在PDBSV2数据集中，算法求解平均时间见表1，其对应自同构检测时间见表2。表中参数“解的数量”用于比较在同一问题实例下，本文算法与其它算法求得解的数量。如在Q4规模下，VFSBC求得10 848个解，VF2求得 13 696 个解，说明其中有2848个解是重复解，在求解时，是不需要被计算的。实验结果显示，VFSBC算法的表现同样优于VF2及ILF算法。在规模为Q16时，本文算法的求解速度是VF2的1.55倍，统计Q4-Q128这6组实验组，其平均求解速度是VF2算法的1.18倍，平均减少1015个重复解。当模式图的规模处于Q32以下时，自同构检测时间依然占比甚微，但是随着模式图的规模增加，自同构检测的时间所占比例逐渐增大。因为自同构检测是一个连续发散的过程，一方面其检测时间受划分内单元数量影响；另一方面，其复杂度随搜索树深度的增加呈指数级增长。如何解决图规模增大带来的自同构检测负担，是需要进一步解决的问题。

表1 PDBSV2数据集实验结果

表2 自同构检测时间

4 结束语

针对子图同构约束求解中重复解问题，本文提出一种破坏重复解的子图同构约束求解算法。该算法基于改进的自同构检测方法，生成对称破坏约束，构建子图同构问题的新的CSP模型，并利用CSP算法进行求解。实验结果表明，该算法与传统算法相比，有效减少了重复解的求解，在小规模及中等规模图匹配中具有良好的求解效率。下一步工作将研究一种自同构预测模型，针对预测结果进行自同构检测分类处理，以缓解图规模增大时，原自同构检测方法耗时过大的问题。