支持增量图数据的超图查询算法研究

孙勤红

(三江学院计算机科学与工程学院, 南京210012)



支持增量图数据的超图查询算法研究

孙勤红

(三江学院计算机科学与工程学院, 南京210012)

当前大部分图查询算法都是针对静态图数据，不适用于现实应用中不断更新的图数据。针对这一问题，提出支持增量图数据的超图查询算法。该算法将数据图分解成直至单个顶点的子图，然后从单个顶点的子图开始求它到查询图的子图同构，直到求出数据图到查询图的子图同构结果，算法在数据图增加时只需将新加入的数据图进行分解即可，不必重新计算。通过分析证明，所提算法时间和空间复杂度不随数据图的增加而呈线性增长，节省了大量时间和空间代价。

增量图数据;超图查询;算法;子图同构

引言

图作为一种复杂的数据结构被应用到各个领域中，因此图查询[1]作为图数据库管理的基本工具受到越来越多的关注。

图结构数据的复杂性决定了图查询的难度。图查询问题会最终转化到子图同构问题上来，所以子图同构是解决图查询问题的关键。子图同构是NPC问题[2]，求同构子图的最通用的方法是基于搜索树的回溯。为了防止搜索树变得过大，研究人员已提出了很多不同的优化方法，如Ullman方法[3]、VF方法[4]以及、VF2算法[5]，另外还有利用网格分割方法、神经网络方法和遗传算法等[6]。为了加快图查询处理过程，已有的方法大部分采用“过滤—验证”框架处理精确子图查询问题，索引的特征有基于路径的[7]，基于树的[8]，还有基于子图的[9-10]。

当前的算法基本采用“过滤—验证”框架结构，并需要对数据图与查询图逐个作子图同构验证。然而，这些方法都只适用于静态的图查询问题，而不适合在不断更新的图数据库上进行图查询。

动态图数据上的图查询问题面临的难点有两点：(1)图数据库是不断变化更新的；(2)数据库更新过程中用于回答查询的时间有限，不能让用户无限制地等待。正是基于动态图数据的这些特点，现有的方法不适用于动态图查询，除非每次更新都重新建立索引然后查询，这样的代价是很高的，而且更新后这些方法可能引起结果错误。

基于现有方法的不足以及动态图数据频繁更新的特点，本文提出了支持增量图数据的超图查询方法。支持增量图数据的超图查询方法的关键点在于当数据库增量更新后，只需将新加入数据图分解并将结果集合加入到原有分解集合中即可，并且在分解过程中可以用到原有结果，避免重新计算，提高了增量图数据的超图查询性能，节省时间和空间代价。

1 基本概念

给定图G=(VG，EG，lGV，lGE)，g=(Vg，Eg，lgV，lgE)为G的子图。VG和Vg分别表示图G和子图g中所有顶点的集合，EG和Eg分别表示图G和子图g中所有边的集合，lGV和lgV分别表示图G和子图g中所有顶点到点标签Vc的映射函数的集合，lGE和lgE分别表示图G和子图g中所有边到边标签Ec的映射的集合。

定义1子图同构。假设S是g的子图，如果存在一个函数f：VG→Vg，且f是从G到S的同构，那么，称f是从G到g的子图同构。

定义2图的差。如果Vg=VG，两者的差Gc=G-g是边集Ec=EG-Eg；如果Vg包含于VG，两者的差Gc=G-g是G的子图Gc=(Vc，Ec，lcV，lcE)，其中：

(1)Vc=VG-Vg其中lcV是Vc到点标签的映射函数；

(2)Ec=EG-Eg其中lcE是Ec到边标签的映射函数；

定义3超图查询。给定图数据库D={G1，G2，…，Gn}(n为有穷自然数)和查询图q，找出所有的Gi满足Gi子图同构于q。

定义4增量超图查询。给定图数据库D={G1，G2，…，Gn}(n为有穷自然数)和查询图q，完成超图查询后数据库D增量更新(增加数据图)变为Du，再次找出所有的Gi满足Gi子图同构于q。

2 图分解算法

在离线阶段，将每个数据库图分解成子图的集合和边的集合。在本文中，将每个数据库图分解为两个子图，然后分别进一步递归地分解两个子图，直到子图是单个顶点的图。

将一组数据库图D={G0，G1，G2，…，Gn}分解(n为有穷自然数)，这里所指的分解是将每个Gi分解，得到一组由四元组构成的有限集合DB称为图数据库D的数据图分解集合。

如果图数据库中的几个图Gi，Gj，…有公共子图g′，或者在一个数据图Gi中出现多次子图g′，那么子图g′成为公共子图。在DB中用四元组表示G的分解就可以省去重新分解和计算的工作。

在已分解的DB中，最大的数据库图的公共子图Smax称为最大公共子图。

具体的分解算法如算法1所示，算法Decomposition(D)的输入是要被分解的数据库图集合D={G0，G1，G2，……，Gn}，分解后输出元组集合用DB表示，其初值为空。

算法首先计算出数据库D中的每个数据图Gi的顶点个数，按照顶点个数从小到大对数据图进行排序，再对排序后的数据图调用Decompose(G)将其分解。

算法用四元组集合记录分解得到的所有子图。子图的个数与子图的平均顶点个数成反比。如果子图的个数增加，那么子图的平均顶点个数就会减少。反之，子图的平均顶点个数就会增加。为了保证子图的平均顶点个数增加，算法对待处理的数据图按顶点个数进行排序，并按照顶点个数从小到大的顺序进行分解。当数据图中存在“包含”关系时，小图首先被分解，大图的分解也会节省代价[11]。

算法1数据图分解算法

输入：图数据库D={G1，G2，…，Gn}；

输出：数据图分解集合DB；

1：Decomposition(D)

2： 数据图库D={G1，G2，…，Gn+1}，DB=Φ；

3： 按顶点个数从小到大的顺序将D中的数据图进行排序，得到D={Gt1，Gt2，…，Gtn+1}；

4：FORi=t1totn+1

5：Decompose(Gi)；

6：ENDFOR;

7：Decompose(Gi)

8： 设DB是已有的分解结果，Smax=Φ；

9：IF(G中只有一个顶点)THEN

10： 返回结果；

11：ELSE调用子图匹配算法Matchgraph(G)在已分解的tuple∈DB中求每个parent

12： 到G的子图同构，并找出其中的最大子图Smax，即

13：Smax=max{parent|∃

∈DB∧parent是G的子图}；

14：ENDIF

15：IF(Smax与G同构)THENEXIT；//同构是指Smax与G的维数相同；

16：ELSEIF(Smax=NULL)THEN

17： 随机选择G的一个子图Smax；

18： 求G中Smax与G-Smax之间的边集E；

19： 将加入到DB中；

20：Decompose(Smax)；

21：Decompose(G-Smax)；

22：ELSEIF(Smax的顶点数=G的顶点数&&Smax边数

23： 求属于G而不属于Smax的边集E；

24： 从G中删除边集E；

25： 分解G，将tuple1加入DB中；

26：ELSE求G中Smax与G-Smax之间的边集E；

27： 将加入到DB中；

28：Decompose(G-Smax)；

29：ENDIF

30：ENDIF

31：ENDIF

32：RETURNDB；

在分解一个数据图G时，首先在已经得到的子图中查找最大的子图Smax，然后将图G分解为Smax和G-Smax两部分。只有当找不到这样的Smax时，才将G随机分解为两部分。当Smax与图数据库中的一个数据图Gi的顶点数相同，但是Smax的边数小于Gi的边数时，求属于Gi而不属于Smax的边集E，从Gi中删除这些边，并分解Gi，增加四元组。这样既能保证子图顶点个数的最大化，又能节省计算代价。

Decomposition(D)算法最重要的特点是对增量图数据的分解效果明显，图数据库D已经应用Decomposition(D)算法分解后，在D中又新增加了一个数据图Gn+1，传统的超图查询方法需要重新构造索引进行更新，而应用Decomposition(D)算法只需执行Decompose(Gn+1)将新加入的数据图Gn+1分解即可，达到只对增量更新，而无需全部重新计算的特点。Decomposition(D)尤其适用于图数据较大以及需要在运行时向数据库中新增数据图的情况。

3 子图的映射集合

首先采用标准测试问题比较chaoticMOPSO与经典的NSGA2以及当前最新提出的BB-MOPSO两种算法以验证本文所提算法的性能。

将分解得到的分解结果集DB中的单个顶点的子图先与查询图进行匹配，匹配成功的这些单个顶点的图合并成大的子图再与查询图进行匹配，这一过程递归地进行直至合并成的最后图为图数据库中的数据图本身。在此过程中会遇到两个问题：

(1)分解出的最小子结构是单个顶点的子图，需要有方法能够求得单个顶点子图到查询图的子图同构过程；

(2)得出分解结果集合DB且∈DB，所有这样的元组中已求出G′和G″到查询图的子图同构，那么需要有方法将G′和G″合并成G，进而求子图同构。

本文采用算法2给出的单点同构检测算法来解决问题(1)。

算法2单点同构检测算法

//单点同构检测Vertex_Test(v，lable，GI)

输入：分解结果DB，GI；

输出：同构映射集合F。

1：GI=(VGI，EGI，lGIV，lGIE)；F=Φ；lable=lGIV(v);

2：Vertex_Test(v，lable，GI)

3：FOREACHvI∈VI

4：IF(lable=lGIV(vI))THEN

5：f(v)=vI；

6：F=F∪{f}；

7：ENDIF

8：ENDFOR

9：RETURNF；

采用算法3的子图映射组合算法MergeTuple(Tupletuple，Graphtarget)可获得分解DB。

算法3图映射组合算法

输入：sub1，sub2，GI，E，F1，F2；

输出：同构映射集合F。

1：MergeTuple(Tupletuple，Graphtarget)

2：tuple=

∈DB；

3：IF(sub2==NULL) //对于子图sub1到target的每种可能的映射组合f1∈F1进行如下检查：

4：FOREACHe∈Eparent&&eEsub1，fromparentV(e)=v1，toparentV(e)=v2

5：IF(e1∈Etarget&&from

Vtarget(e1)=f1(v1) &&to

targetV(e1)=f1(v2)

6： &&arg

type

tetV(e1)=type

parentV(e))

7：f1∈F1，得到新的映射f：Vsub1→Vtarget，且f(n)=f1(n)；

8： 将f加入到parent的同构映射表F中，即F=F∪{f}；

9：ENDIF

10：ENDFOR

11：ELSE//对于每个f1∈F1，f2∈F2进行如下检查：

12：IF(f1(Vsub1)∩f2(Vsub2)=Φ&& //检查两个子图到target中的映射是不相交的

13： // 对于两个子图到target的每种可能的映射组合，判断边的约束：

14：FOREACHe∈Eparent&&from

parentV(e)=v1∈Vsub1&&to

parentV(e)=v2∈Vsub2

15：IF((e1∈Etarget&&from

Vtarget(e1)=f1(v1) &&to

targetV(e1)=f1(v2)

16： &&arg

type

tetV(e1)=type

parentV(e))OR

17：FOREACHe∈Eparent&&to

parentV(e)=v1∈Vsub1&&from

parentV(e) =v2∈Vsub2

18：IF((e1∈Etarget&&arg

to

Vtet(e1)=f1(v1) &&from

parentV(e1)=f1(v2)

19： &&arg

type

tetV(e1)=type

parentV(e))

20：f：Vsub1∪Vsub2→Vtarget//对于满足a和b的每种组合合成新的映射

21： 将f加入到parent的同构映射表F中，即F=F∪{f}；

22：ENDIF

23：ENDFOR

24：ENDIF

25：ENDIF

26：RETURNF；

对于DB中一个四元组

∈DB已经找到了所有从sub1和sub2到查询图的子图同构f1和f2，那么需要将他们组合成从parent到查询图的子图同构f，即需要判断由f1和f2能否组合成parent到target的子图同构f，这一工作由MergeTuple(Tupletuple，Graphtarget)完成。该首先对sub2为空的子图的情况进行了分析，若sub2为空，那么只需要对属于parent而不属于sub1的边进行检测即可。检测包括两部分：分别是边的连接顶点类型和边类型，对于无向图且边上无标签的图可以将边的类型检测忽略；其次对sub1和sub2都不为空的情况进行检测，此时需要对属于parent而不属于sub1也不属于sub2的边进行检测，检测的步骤同前面。

4 实验仿真

为了验证本文算法的有效性和可靠性，采用MIT地质图像测试数据库为研究对象，选择测试图像1和测试图像2验证本文算法的可扩展性和运行效率。对比本文算法和cIndex算法，评价指标包括算法可扩展性、执行效率、离线构造时间、索引特征的过滤能力。对比结果如图1～图6所示。

图1 测试图像1及其分解结果

图2 测试图像2及其分解结果

图3 候选集大小和执行时间

图4 可扩展性

图5 离线构造性能

图6 阈值敏感性

由图3可知，本文算法所需响应时间比cIndex方法小很多，运行效率得到了大约1个数量级的提升，主要是因为本文算法可以实现数据集的压缩，从而达到大大降低运行计算的代价。

由图4可知，本文算法的可扩展性优于cIndex方法效果较好。由图5离线构造性能实验结果可知，本文算法在执行效率和预处理结果两个方面均优于cIndex方法。

由图6可知，随着阈值敏感性的增大，数据图集的索引特征呈现下降趋势，而执行时间却变长，从而说明索引特征的大小和执行效率上存在矛盾的关系。

通过对可扩展性、执行效率、离线构造时间、索引特征的过滤能力四个性能评价指标的仿真实验可知，本文算法不但执行效率高，同时也具有较低复杂度，效果较好。

5 结束语

本文提出了一种新的超图查询算法—支持增量图数据的超图查询算法，该算法将数据图分解成直至单个顶点的子图，然后从单个顶点的子图开始求它到查询图的子图同构，直到求出数据图到查询图的子图同构结果。通过文中的分析表明，相较cIndex算法，本文提出的算法对超图的查询更加地简单省时，同时，所提算法空间复杂度不随数据图的增加而呈线性增长，节省了大量空间代价。

[1] Wang Xiaoli,Ding Xiaofeng,Tung A,et al.An efficient graph indexing method[C]//Proceeding of IEEE 28th International Conference on Data Engineering(ICDE),DC,Washington,April 1-5,2012:210-221.

[2] France R,Gabriel V.Chemical graphs,chemical reaction graphs,and chemical graph transformation[J].Theoretical Computer Science,2005,127(1):157-166.

[3] Moustafa W,Deshpande A,Getoor L.Ego-centric graph pattern census[C]//Proceeding of IEEE 28th International Conference on Data Engineering(ICDE),DC,Washington,April 1-5,2012:234-245.

[4] Hu Y,Wu W,Zhang B.A fast method to identify the order of frequency-dependent network equivalent[J].IEEE Transactions on Power Systems,2015,PP(99):1-9.[5] Shang Huiliang,Tao Yudong,Gao Yuan,et al.An improved invariant for matching molecular graphs based on VF2 algorithm[J].IEEE Transactions on Systems,Man,and Cybernetics:Systems,2015,45(1):122-128.

[6] Perez-Ortiz M,Gutierrez P A,Hervas-Martinez C,et al.Graph-based approaches for over-sampling in the context of ordinal regression[J].IEEE Transactions on Knowledge and Data Engineering,2015,27(5):1233-1245.

[7] Llados J,Marti E,Villanueva J.Symbol recognition by error-tolerant sub-graph matching between region adjacency graphs[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,23(10):1137-1143.

[8] Akrivi V,Michalis V,Klaus B.Algorithms and models for the Web-Graph[M].Berlin Heidelberg:Springer-Verlag,2008.

[9] Jin R,Ruan N,Dey S,et al.Scaling reachability computation on large graphs[C]//Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data,Arizona,May 20-24,2012:169-180.

[10] Thomsen J,Yiu M,Jensen C.Effective caching of shortest paths for location-based services[C]//Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data,Arizona,May 20-24,2012:313-324.

[11] 张硕,李建中,高宏,等.一种多到一子图同构检测方法[J].软件学报,2010,21(3):401-414.

Research on Supergraph Query Algorithm of Support Incremental Graph Data

SUNQinhong

(School of Computer Science and Engineering, Sanjiang University, Nanjing 210012, China)

Most current graph query algorithms are applicable for static graph data, but cannot be used in constantly updated map data in real world applications. Aiming at this problem, the supergraph query algorithm of support incremental map data is put forward. The data graph is divided into subgraphs with a single vertex by using the proposed algorithm, and then from the single vertex subgraph to find it’s subgraph isomorphic to query graph, until the subgraph isomorphism results of data graph to query graph are found. When data graph increases, algorithm only needs to decomposition the newly added data graphs, and do not need to compute. The analysis shows that, the time and space complexity of proposed algorithm does not increase linearly with the increase of data graph, which saves much time and space costs.

increment map data; supergraph query; algorithm; subgraph isomorphism

2015-04-21

孙勤红(1979-),女,山东郯城人,讲师,硕士,主要从事数据挖掘方面的研究,(E-mail) 22113460@qq.com

1673-1549(2015)03-0027-06

10.11863/j.suse.2015.03.06

TP311

A