摘要：传统模式匹配搜索首先定义用户查询图,然后在目标图中搜索匹配的所有子图模式。这种查询包含最短路径查询、可达性验证和模式匹配查询,但常常面临计算复杂度剧增的瓶颈。如何从大规模数据图中高效检索所有匹配子图模式成为研究焦点。本文创新性地提出了快速子图模式挖掘算法,采用基于标签约束的遍历策略,在遍历过程中记录所有访问节点,结合“先深度遍历、后广度遍历”方式快速搜索所有匹配子图模式。与两种最新算法对比,本算法执行效率实现了大幅提升,能快速高效地搜索出所有子图模式。

　　关键词：子图模式；快速搜索；高效算法

　　0引言

　　现实世界中不断产生海量数据。为了研究数据之间的关系,常用节点表示实体、边表示实体间的关系,这些节点和边就构成了图结构模型。图结构广泛应用于数据建模、社交网络分析、生物信息网络和万维网等。在此背景下,大数据中的查询问题可转化为图上的查询任务,典型查询包括最短路径查询、可达性查询以及子图查询等。这些查询需要对图结构进行高效存储与分析。传统匹配查询主要针对节点和边,随着图数据结构日益复杂,近年来出现了专门针对图数据结构中的数据执行的查询。这类查询需要找到一组顶点之间的关系,与可达性和最短路径查询相比,需要更多的信息,因此,此类查询的底层机制很复杂,计算成本也很高。

　　1模式匹配算法概述

　　模式匹配查询问题,定义如下。

　　给定目标图G、查询图q、距离参数δ以及匹配判定条件。定义两节点A和B之间的距离为从节点A到节点B所需经过的边的最小数量。当以下两个条件同时成立时,称查询图q在目标图G中存在模式匹配。

　　（1）目标图G（n个顶点）的标签与查询图q中对应的顶点相同；

　　（2）查询图q中任意两个相邻的顶点之间的距离小于或等于距离参数δ。

　　模式匹配查询在现实世界中有很多应用。例如,定义合作作者为合作发表文章的团队,在平台中查询任意k个合作作者子模式；又如定义互关为好友,在平台中查询任意k个好友子模式。

　　显然,这样的模式匹配查询问题包含最短路径查询、可达性查询、子图查询,但不会涉及子图同构。

　　2模式匹配算法在数据挖掘中的应用

　　2.1针对特定类型的图的模式匹配算法

　　现有的子图匹配大部分工作都是针对特定类型的图,如平面图、化合价图和设计指标图[1]。文献[2]侧重于子图匹配问题本身,并应用于任何模式匹配查询。文献[3]解决了二次时间内的可达性查询和三次时间内的模式查询,提出了一种为可达性查询开发的高效二次时间算法。文献[4]介绍了在图模式匹配问题中使用top-k的多样化方法,设计输出节点和函数定义图模式,修改后的图模式能够更好地测量匹配的相关性和多样性。文献[5]以一种不同的方式解决模式匹配查询,用于处理DAG有向无环图的小枝、路径和查询。

　　G-Ray[6]算法为了降低不精确模式匹配问题的计算复杂度,应用了各种优化策略,当条件δ≤2满足时运行模式匹配查询,极端情况下仍能表现出线性复杂性,但由于无法获得稳定的运行结果,算法的鲁棒性较差。

　　2.2针对特定类型的图的模式匹配算法

　　文献[7]引入了有效的索引和挖掘图数据库的技术,主要基于频繁出现的子结构。文献[8]发现了频繁的大规模模式,并应用拓扑的概念来挖掘。文献[9]提出了在单图内进行图挖掘的算法,实验评估表明其算法在某些数据集运行时优于Cook等人[10]的算法。文献[11]提出了图挖掘的另一种方法。文献[12]提出了一种主动学习范式,该范式基于查询的成对实例做出决策,并利用成对同质性数据改进主动学习器。Yi等人[13]提出了GFOCUS框架,提出单调的子模块排序函数,利用图查询公式的用户焦点,针对用户提供的焦点生成全面的查询。Komamizu等人[14]解决了关联数据(LD)中实体搜索的问题,设计了一种基于个性化的重新排名方法PPRSD。

　　3基于深度广度混合模式的匹配算法

　　本文算法（BSW）基于深度广度混合模式,可以分为以下六步。

　　（1）对目标图基于查询模式建立查询索引表；

　　（2）从左向右依次扫描查询索引表中的节点,以每次的节点作为根节点,在目标图中进行深度搜索,同时标记搜索的节点；

　　（3）搜索目标图,若搜索满足条件,且路径长度小于等于δ,则继续步骤（3）；

　　（4）若搜索不满足条件,但路径长度小于等于δ,则向上回溯到上一节点,继续步骤（3）；

　　（5）若搜索满足条件,但路径长度大于δ,则选出,向上回溯到上一节点,继续步骤（3）；

　　（6）若向上回溯到表1的节点,则重复步骤（2）。

　　为了保证每次查询都从q的节点开始,查询索引表以q的节点优先（ABC之间不分优先级别）从左向右排列。

　　3.2按照序列搜索目标图

　　按照图1的节点序列从左至右搜索G,得到搜索序列如表2所示。

　　3.3算法时间复杂度分析

　　整个算法分为2个部分,分别为深度搜索和广度搜索。

　　3.3.1深度搜索时间复杂度

　　每次从查询索引表节点开始深度查询,标记已搜索的节点,确保搜索节点不会重复。该搜索过程时间复杂度为O(n)。n是图G的节点数。

　　3.3.2广度搜索时间复杂度

　　若深度搜索失败,则回溯继续搜索。当回溯至根节点时,从查询索引表中选择下一个节点作为新的根节点继续搜索。由此,目标图G被转化为以查询索引表中m个节点为根的m棵树。对图G的搜索,等价于对这m棵树分别执行深度优先搜索；而在树与树之间的跳转,则相当于广度优先搜索。因此,算法的整体时间复杂度为O(m),其中m为查询图q的节点数。

　　3.3.3总时间复杂度

　　显然,整个混合算法的时间复杂度为O(n)*O(m)。

　　4实验与结果

　　实验在两大数据集合Circuit-4和Citeseer中进行,并且与两种密切相关的最新方法(即MD-Join[15]和Gua[16])进行对比。实验环境为微软Windows10操作系统、英特尔酷睿i7处理器和8GB RAM。

　　Circuit-4是电路仿真数据集。在这个数据集中,顶点表示坐标,边表示它们之间的关系。数据集中有80200个顶点和227400条边。采用随机函数随机生成与顶点相关的标签,并确定标签的范围在1~2500之间。

　　Citesee数据集是合著者相关网络。在网络中,顶点表示作者,边表示顶点之间的关系。网络图中有227300个顶点和814100条边。采用随机函数为每一个节点生成一个标签,范围从1到1000。

　　在以上两个数据集中分别执行q1和q2查询,如图2所示。

　　先在Circuit-4中实验,实验结果如图3、图4所示。可以看出,当顶点距离δ从2变到12,三种算法执行时间都有所增加,但是本文算法搜索时间最小、增长最缓。搜索时间较大的是MD-Join算法,增长速度较快的是Gua算法。

　　在Citeseer中实验,实验结果如图5、图6所示。可以看出,当顶点距离δ从2变到12,三种算法执行时间都有所增加。相对于Circuit-4,在Citeseer数据集中,三种算法的搜索时间明显增加。

　　总之,搜索时间是随查询图任意两个顶点之间的距离变大而增加,q2查询搜索时间要比q1长。本文搜索算法在三种算法中表现最佳,当顶点距离δ增加时耗时增长也最缓。

　　5结语

　　本文创新性地提出了快速子图模式挖掘算法,通过基于标签约束的遍历策略,在遍历过程中记录所有访问节点,通过“先深度遍历、后广度遍历”的方式快速搜索所有匹配子图模式。实验显示,与当前2种最新算法对比,本算法执行效率实现了大幅提升,能快速、高效地搜索出所有子图模式。

参考文献

　　[1]ANTONOVA V M,ZAKHIR B M,KUZNETS OV N A.Modeling Of Graphs With Different Types Of Reachability In Python[J].Journal of Communications Technology and Electronics,2019,64(2):1464–1472.

　　[2]靳思萌,李仲伟,解晓芳,等.一种高效的大规模图数据频繁子图挖掘算法[J].计算机光盘软件,2016,13(4):12-21.

　　[3]FAN W,LI J,MA S,et al.Adding Regular Expressions To Graph Reachability and Pattern Queries[J].Frontiers of Computer Science in China,2012,6(3):313-338.

　　[4]AISSAM A,SAÏD Y,LAMIA S,et al.Scalable Diversified Top-K Pattern Matching in Big Graphs[J].Big Data Research,2024,36(2):100-116.

　　[5]春燕.基于藏文音节特征的模式匹配算法的研究[J].计算机光盘软件与应用,2014,17(4):21-25.

　　[6]TONG H,CHRISTOS F,BRIAN G,et al.Fast Best-effort Pattern Matching in Large Attributed Graphs[J].Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2007,15(4):737-746.

　　[7]胡自松,王丽珍,VANHA T,等.基于图数据库的空间频繁并置模式挖掘[J].计算机科学与探索,2022,16(3):16–24.

　　[8]刘勇,李建中,高宏.从图数据库中挖掘频繁跳跃模式[J].软件学报,2010,21(10):17-28.

　　[9]MICHIHIRO K,GEORGE K.Finding Frequent Patterns in A Large Sparse Graph*[J].Data Mining and Knowledge Discovery,2005,11(3):243-271.

　　[10]COOK D J,HOLDER L B.Substructure Discovery Using Minimum Description Length And Background Knowledge[J].Journal of Artificial Intelligence Research,1994,14(2):231-255.

　　[11]汤小春,周佳文,田凯飞,等.大图中全部极大团的并行挖掘算法研究[J].计算机学报,2019,15(3):19-24.

　　[12]郭虎升,王文剑.基于主动学习的模式类别挖掘模型[J].计算机研究与发展,2014,51(10):12-18.

　　[13]YI P,BYRON C,ZHANG Z,et al.GFocus:User Focus-based Graph Query Autocompletion[J].IEEE Transactions on Knowledge and Data Engineering,2020,16(4):15-26.

　　[14]TAKAHIRO K.Random Walk-based Entity Representation Learning And Re-ranking For Entity Search[J].Knowledge and Information Systems,2020,62(8):2989-3013.

　　[15]ZOU L,CHEN L,TAMERÖM.Distance-join:Pattern Match Query in A Large Graph Database[J].Proceedings of the VLDB Endowment,2009,12(3):886-897.

　　[16]CHEN Y,BIN G,HUANG X.On Evaluation of Graph Pattern Matching In Large Databases[C]//2018 International Conference on Computational Science and Computational Intelligence(CSCI).Las Vegas,NV,USA:IEEE,2018:1242–1247.