基于路径信息比较的图同构新算法

何洁月 沈 斌

(1东南大学计算机科学与工程学院,南京210096)(2东南大学计算机网络和信息集成教育部重点实验室,南京210096)

基于路径信息比较的图同构新算法

何洁月1,2沈 斌1

(1东南大学计算机科学与工程学院,南京210096)(2东南大学计算机网络和信息集成教育部重点实验室,南京210096)

为了在多项式时间内解决图同构问题,首先证明了2个同构图相等长度的路径信息必相同是图同构判定更为严格的必要条件.然后,根据此条件,提出了一种基于路径信息比较的图同构PIC算法.该算法依次比较各长度的路径信息,对邻接矩阵进行调整,从而实现了2个图的快速同构判定.为了减少路径信息的计算时间，引入Hash函数对PIC算法进行改进，从而得到了HPIC算法.实验结果表明,所提的2种算法均能够正确判定1×104对不同类型、不同大小的随机图是否同构,并且图同构判定的时间复杂度明显降低.HPIC算法的运行速度快于PIC算法；这2种算法在时间性能方面均优于CS算法,略劣于Nauty算法;但对于规则2维网孔图,Nauty算法失效,所提的2种算法则仍能快速进行图同构判定.

图同构;幂阶比较;大规模图;路径信息比较

图的同构判定问题是图论学科中的基本问题之一,在模式识别、电路分析、分子结构和生物信息学[1-3]等领域有着广泛的应用.图同构问题既未被归入 NPC 问题,也未被归入P问题[4].目前,学者们已提出了一些有效的图同构判定算法,然而,针对特定类型图进行判定时这些算法通常会失效.图同构算法大致可以分为3类:① 基于模型的判定算法.文献[5]提出了一种基于神经网络的图同构判定算法,并通过简化能量函数建立相应的数学模型,是一种能够模拟局部功能的超大规模并行计算方法.② 基于搜索的算法.Ullmann算法利用预测方程减少了搜索的空间[6];Nauty算法先将图表示为某种规范形式,然后判断是否同构[7].③ 根据图的特征信息(如图的出入度序列、回路数、树数、连通片数等)提出的算法,如度序列法、电路模拟比较法[8]等.然而,这些算法均具有各自的局限性.例如,基于神经网络的图同构算法在每次判定时都需要在能量函数的步长上进行探索,易于陷入局部最优值,影响算法的效率.文献[9]发现Nauty算法是综合效率最高的算法,但在网孔图的情况下完全失效.文献[10]对电路模拟比较法进行了改进,在大节点下获得了较好的效率,但当图中出现孤立点时失效,且对于对称性强的图效率不高.

根据图的局部或全局特征信息来判断图同构性的条件强度较弱,不同构的2个图也可能会出现完全相同的特征信息[11].本文首先证明了2个同构图相等距离的路径信息必相同是图同构判定中更为严格的必要条件.基于此,提出了一种由局部到全局的路径信息比对法(PIC)算法,然后利用Hash函数对获取路径信息过程进行改进,得到路径信息比对(HPIC)算法.

1 算法描述

1.1 基本概念

图同构是指2个图的拓扑结构完全相同,即顶点到顶点、边到边之间存在着一一对应的关系.

定义1[12]对于图G=〈V,E〉与图G′=〈V′,E′〉,存在双射f:V→V′和双射h:E→E′,使得对于每条边ek∈E,点vi,vj为ek在图G中的端点,在图G′中存在且唯一存在一条以f(vi),f(vj)为端点的边h(ek),则称这2个图同构,记做G≈G′.其中,V,E分别为顶点集合和边的集合.

定义2 图可以用邻接矩阵表示.对于具有n个顶点的图,其邻接矩阵D为n×n阶矩阵,矩阵中元素可表示为

式中,[vi,vj]表示从点vi指向点vj的边.

定理1[13]图G与图G′的邻接矩阵经过行(列)互换的合同变换后,若邻接矩阵相同,则G与G′同构.即若存在非奇异列交换矩阵P1,P2,…,Pm,使得D={P1,P2,…,Pm}D′{Pm,Pm-1,…,P1},则G≈G′.反之也成立.

1.2 基于路径信息比较的图同构判断算法

传统的图特征信息法仅关注了局部或全局特征信息,这是比较弱的必要条件,在判断2个图是否同构时失效情况较多.为此,考虑1～n-1阶的路径信息,根据由局部逐步推向整体的比对信息进行判定.对于图G中点A与图G′中点B,如果其邻接点信息相同,则称点A与点B的1阶路径信息相似;如果长度为k的链路信息完全相同,则称点A与点B为k阶相似;如果点A与点B的1～n-1阶路径信息均相似,则点A必与点B对应;若2个图中所有点一一对应,则2个图同构.

显然可以推出,若存在非奇异行(列)交换矩阵P1,P2,…,Pm,使得R=R′{Pm,Pm-1,…,P1},则R≈R′.

定理3 如果图G与图G′同构,则Dk≈D′k.

证明 由定理1可知,存在非奇异行变换矩阵P1,P2,…,Pm,使得

D1={P1,P2,…,Pm}D′1{Pm,Pm-1,…,P1}

由定义4可知,D1≈D′1，故Dk=(PD′Q)k,又因为PQ={P1,P2,…,Pm}{Pm,Pm-1,…,P1}=I,则Dk=PD′kQ,即可得Dk≈D′k.证毕.

定理3是PIC算法的基础,是2个图同构的更为严格的必要条件.对邻接矩阵进行n-1次比较,若Dk≠D′k,则2个图不同构.

定理3为证明2个图不同构提供了必要条件,推论2为邻接矩阵的调整提供了依据.每经过一次比较,都可以利用必要条件进行一次检验,同时可以根据顶点的路径信息对矩阵调整进行一次充分性检验.若经过调整的矩阵相等,则2个图必同构.

1.3 PIC算法

PIC算法利用定理3与推论2对2个图的对应点进行划分,缩小了比对范围,提高了图同构判定的速度.

算法1 PIC算法

输入: 图G1=〈V1,E1〉,图G2=〈V2,E2〉.

输出: 2个图同构的判定结果.

//计算2个图的邻接矩阵

A=AP1=GetM(G1),B=BP1=GetM(G2)

//判定2个图是否同构

if (A==B)

return true

end if

//计算矩阵路径信息

return false

end if

//根据路径信息调整邻接矩阵

If (A==B)

return true

end if

APi+1=APiA

BPi+1=BPiB

end for

//枚举同构判定结果

return enum(A,B)

1.4 算法复杂度分析及改进

本文算法的最优情况是指只需进行1次矩阵比较便可判定2个图是否同构,此时算法的时间复杂度为O(n2).最坏情况是指经过n-1次检验才能判定2个图是否同构.其中,每一次判定都需要利用排序算法对行内元素进行调整,以得到每个点的路径信息,得到n个点的路径信息时间复杂度为O(n2lgn);然后,对整理后的矩阵进行初等行变换,时间复杂法度为O(n2);在Matlab软件中,矩阵的乘法函数复杂度为O(n2.8).因此,总的时间复杂度为(n-1)(O(n2lgn)+O(n2)+O(n2.8))=O(n3.8).实际上,仅当2个图都是旋转对称图且旋转周期大于4时,才需要经过n-1次检验来判定2个图是否同构.因此,本文中将算法平均时间复杂度取为O(n3).

由于无向图(或有向图)邻接矩阵的元素都为0(或1),因此,可以利用Hash函数对PIC算法进行改进,从而得到HPIC算法.在HPIC算法中,计算每个点的路径信息时,先用Hash函数对邻居矩阵中每一行元素出现的次数进行统计;然后,比较2个图的路径信息集合是否相等.该算法将得到每个点路径信息的时间复杂度从O(nlgn)降低为O(n),从而减少了程序运行时间.该算法在最优情况下的时间复杂度为O(n2);在最坏情况下,由于高阶邻接矩阵中元素差异性大,Hash函数法不再适用,故时间复杂度仍为O(n3.8).

2 实验与结果分析

参照文献[11],构造出同构测试图库,生成了1×104对同构测试样本.待测图类型主要包括:随机图(3×103对)、规则2维网孔图(1×103对)、非规则2维网孔图(3×103对)和固定度数图(3×103对).

CS算法[10]是一种适用于大图比对的图特征法算法.文献[9]对Ullmann算法、SD算法、VF算法、VF2算法和Nauty算法进行了比较,发现Nauty算法在平均性能方面优于其他4种算法.本文实验中,使用2.0b版Nauty算法,并在Matlab软件中实现了CS算法、PIC算法和HPIC算法.

2.1 随机图

对于给定顶点,每2个顶点按照概率p(0≤p≤1)连接而成的图即为随机图.本实验中产生了10组(共1 000对)随机图,其中每组图的顶点数分别为20,40,60,80,100,200,400,600,800,1 000.对于p=0.05的随机图,利用4种算法判定2个图是否同构所需的平均时间见图1.由图可知,4种算法运行速度由快到慢依次排序为: Nauty算法、HPIC算法、PIC算法、CS算法.当图的顶点数增加到1 000时,CS算法的运行时间分别约为PIC算法和HPIC算法的8.9和19.3倍.值得注意的是,当图中存在孤立点时,CS算法完全失效,需要通过枚举法来判定2个图是否同构,时间复杂度为O(n!).这种情况在随机图中出现的概率随顶点数的增加而减少.当图的顶点数为60时,一个图中出现孤立点的概率为0.225;当顶点数为100时,此概率为0.007;当顶点数大于100后,随机图中出现孤立点的现象为小概率事件.因此,CS算法适合于顶点数较多的图.

图1 随机图中不同算法平均运行时间比较

2.2 规则2维网孔图

规则2维网孔图是指规则的有向网格图.本实验中产生了10组(共1 000对)随机图,其中每组图的顶点数分别为9,16,25,36,64,100,225,400,625,1 024.对于规则2维网孔图,利用4种算法判定2个图是否同构所需的平均时间见图2.

图2 规则2维网孔图中不同算法平均运行时间比较

由图2可知,Nauty算法在规则2维网孔图中完全失效.在程序运行时间方面,HPIC算法最短,PIC算法与CS算法接近.当图的顶点数增加到1 024时,CS算法的运行时间分别约为HPIC算法和PIC算法的1.9和1.3倍.

2.3 非规则2维网孔图

在规则2维网孔图的基础上添加一些随机连接边,得到非规则2维网孔图.本实验中,在10组规则网孔图的基础上加入0.2N条随机边,得到10组非规则网孔图,其中N为图的顶点数.对于非规则2维网孔图,利用4种算法判定2个图是否同构所需的平均时间见图3.

图3 非规则2维网孔图中不同算法平均运行时间比较

由图3可知,4种算法运行速度由快到慢依次排序为: Nauty算法、HPIC算法、PIC算法、CS算法.当图的顶点数增加到1 000时,CS算法的运行时间分别约为PIC算法和HPIC算法的7.9和10.2倍.

2.4 固定度数图

固定度数图是指每个顶点出入度之和为定值的图.本实验中产生了10组(共1 000对)随机图,其中每组图的顶点数分别为20,40,60,80,100,200,400,600,800,1 000.对于定值为3的固定度数图,利用4种算法判定2个图是否同构所需的平均时间见图4.

图4 固定度数图中不同算法平均运行时间比较

由图4可知,CS算法的运行时间最长,其次是PIC算法,HPIC算法和Nauty算法接近.当图的顶点数大于600时,HPIC算法的运行速度比Nauty算法快.当图的顶点数增加到1 000时,CS算法的运行时间分别约为PIC算法和HPIC算法的2.8和7.6倍.

综上所述,PIC算法和HPIC算法在大部分情况下都能较快地对2个图进行同构判定.此外,对于规则2维网孔图,Nauty算法已经失效,所提2种算法则能够较快地进行同构判定.

3 结语

图同构问题是经典的图论问题,现有的图同构判定算法都具有一定的局限性.本文首先证明了2个同构图相等长度的路径信息必相同是图同构判定更为严格的必要条件.基于此,提出了PIC算法和HPIC算法,分析了算法的时间复杂度.试验结果表明,PIC算法和HPIC算法均具有较优的综合性能.

References)

[1]Bunke H, Riesen K. Recent advances in graph-based pattern recognition with applications in document analysis [J].PatternRecognition, 2011, 44(5):1057-1067.

[2]Dehmer M, Sivakumar L, Varmuza K. Uniquely discriminating molecular structures using novel eigenvalue-based descriptors [J].CommunicationsinMathematicalandComputerChemistry, 2012, 67(3)： 147-172.

[3]He J Y, Wang C Y, Qiu K P, et al. An novel frequent probability pattern mining algorithm based on circuit simulation method in uncertain biological networks[J].BMCSystemsBiology, 2014, 8(S3): S6.

[4]Torán J. On the hardness of graph isomorphism [J].SIAMJournalonComputing, 2004, 33(5): 1093-1108.

[5]许进,张军英,保铮.基于Hopfield网络的图的同构算法 [J].电子科学学刊, 1996, 18(S1): 116-121. Xu Jin, Zhang Junying, Bao Zheng. Graph isomorphism algorithm based on the Hopfield network[J].ChinaJournalofElectronics, 1996, 18(S1): 116-121. (in Chinese)

[6]Ullmann J R. An algorithm for subgraph isomorphism [J].JournaloftheAssociationforComputingMachinery, 1976, 23(1): 31-42.

[7]McKay B D, Piperno A. Practical graph isomorphism, Ⅱ [J].JournalofSymbolicComputation, 2014, 60: 94-112.

[8]Shang H L, Li F, Tang X D, et al.A new algorithm for isomorphism determination of undirected graphs-circuit simulation method [J].CircuitsSystemsandSignalProcessing, 2011, 30(5): 1115-1130.

[9]Foggia P, Sansone C, Vento M. A performance comparison of five algorithms for graph isomorphism [C]//Proceedingsofthe3rdIAPRTC-15WorkshoponGraph-basedRepresentationsinPatternRecognition. Napoli, Italy, 2001: 188-199.

[10]赵愉, 李锋, 商慧亮. 同构图判定: 改进的电路模拟法[J]. 信息与电子工程, 2011, 9(4): 478-482. Zhao Yu, Li Feng, Shang Huiliang. Improved circuit simulation method for testing isomorphism [J].ChinaInformationandElectronicEngineering, 2011, 9(4): 478-482.(in Chinese)

[11]Gori M, Maggini M, Sarti L. Exact and approximate graph matching using random walks [J].IEEETransactionsonPatternAnalysisandMachineIntelligence, 2005, 27(7): 1100-1111.

[12]Bondy J A, Murty U S R.Graphtheorywithapplications[M]. London: Macmillan, 1976: 4-7.

[13]谢科, 饶怀章. 图同构的充要条件[J]. 西南民族大学学报:自然科学版, 2011,37(5): 703-705. Xie Ke, Rao Huaizhang. Necessary and sufficient condition of graph isomorphism [J].ChinaJournalofSouthwestUniversityforNationalities:NaturalScienceEdition, 2011, 37(5): 703-705. (in Chinese)

Novel graph isomorphism algorithm based on path information comparison

He Jieyue1,2Shen Bin1

(1School of Computer Science and Engineering, Southeast University,Nanjing 210096, China)(2Key Laboratory of Computer Network and Information Integration of Ministry of Education, Southeast University, Nanjing 210096, China)

To solve the graph isomorphism problem in polynomial time, it is proved that the fact that the path information with same length of two isomorphism graphs must be the same is a more rigorous prerequisite for judging whether two graphs are isomorphism. Then, according to this prerequisite, the PIC (path information comparison) algorithm based on graph isomorphism comparison is proposed. In this algorithm, the path information with different lengths of two graphs is compared successively. The adjacent matrixes are adjusted based on the vertex path information in the comparing process and quick isomorphism of the two graphs is realized. By introducing the Hash function to improve the PIC algorithm, the HPIC (hash path information comparison) algorithm is proposed to reduce the computation time of the path information. The experiment results demonstrate that the two proposed algorithms can correctly judge whether the 1×104pairs of figures with different types and sizes are isomorphism graphs, and the time complexity is obviouly reduced. The HPIC algorithm is faster than the PIC algorithm. Furthermore, these two algorithms are faster than the CS(circuit simulation) algorithm, but slightly slower than the Nauty algorithm. However, as for the regular two-dimensional meshes, the Nauty algorithm is invalid while the two proposed algorithms can still solve the graph isomorphism problem quickly.

graph isomorphism; matrix power comparison; large graph; path information comparison

10.3969/j.issn.1001-0505.2015.02.007

2014-11-08. 作者简介: 何洁月(1964—),女,博士,教授,Jieyuehe@seu.edu.cn.

江苏省自然科学基金资助项目(BK2012742).

何洁月，沈斌.基于路径信息比较的图同构新算法[J].东南大学学报:自然科学版,2015,45(2):236-240.

10.3969/j.issn.1001-0505.2015.02.007

TP301

A

1001-0505(2015)02-0236-05