刘莹，杜奕智，邹乐



大图挖掘中一种基于云计算的改进SpiderMine算法

刘莹，杜奕智，邹乐

摘 要：现有的图挖掘算法在云环境下难以有效地进行大规模图形的高频模式挖掘。为此，对SpiderMine算法做了改进，提出一种基于云的SpiderMine算法（c-SpiderMine）。首先，利用最小切割算法将大规模图形数据分为多个子图，使分区/融合成本最小，然后，利用SpiderMine进行模式挖掘，显著降低了大型模式生成时的组合复杂度。最后，采用一种模式键函数来保存模式，以保证所有模式可被成功恢复和融合。基于3种真实数据集的仿真实验结果表明，c-SpiderMine可高效挖掘云环境下的前K个大型模式，在不同数据规模和最小支持设置条件下，c-SpiderMine在内存使用和运行时间方面的性能均优于SpiderMine。

关键词：图挖掘；云计算；高频模式；最小切割算法；模式键函数；运行时间

0 引言

图挖掘问题[1-3]在移动互联网、大数据处理等领域具有十分重要的应用价值，是目前的研究热点。文献[4]采用社会网络中的信息传播模型研究在单个大图中挖掘近邻频繁模式，提出了一种基于共生频繁项树和逆矩阵的图挖掘算法。该方法快过传统的单个大图频繁子图挖掘算法，返回的结果也多过频繁子图挖掘算法，并且可以发现一些传统频繁子图挖掘算法发现不了的有趣模式。然而，该算法的计算量较大。文献[5]中的SpiderMine算法采用概率挖掘理论来寻找前K个最大模式，通过将小规模高频率模式融合为大规模模式，克服了算法瓶颈，效率较高。文献[6]针对现有云计算平台资源随机调配与传统导出子图挖掘效率较低等问题，提出了一种自适应云端的大规模导出子图提取算法，以解决资源优化利用与海量图挖掘等问题。文献[7]提出一种图形挖掘系统OPAvion。该系统可引导用户逐渐探索图形，以选择的节点或标记后的异常节点开始，然后用户可扩展至节点的邻域，对它们贴上类别标签，因此可对图形的感兴趣部分进行交互式引导。然而，上述方法均无法进行云环境下大规模图形的高频率模式挖掘。其主要原因在于：（1）图分割问题。现有的算法难以生成小型等直径模式，如果模式切割不当则会在模式恢复、模式再搜索和模式融合方面产生模式成本。为此，如何定义并有效利用合适的模式切割是本文主要任务之一。（2）信息不对称。每台机器间缺乏沟通，可能导致信息丢失，增加不必要的计算负担。（3）模式保存融合问题。在融合步骤，必须要保证不同分区中的模式利用其他模式仍可实现有效检测和归纳。现有的算法难以做到这一点。

为了解决以上问题，本文针对文献[5]中的SpiderMine算法提出云环境下的新算法c-SpiderMine。已经证明SpiderMine可有效地对经过标识的图形进行挖掘。它是一种基于近似的图形模式挖掘算法，通过随机游走实现模式检测，但无法保证检测出所有模式。于是，本文试图通过完整的模式搜索来检测模式，在随机游走时对所有节点进行游走以避免模式丢失。c-SpiderMine包括3个阶段：分区；挖掘；融合。分区阶段利用最小切割算法将大规模图形数据分为多个子图，使分区/融合成本最小。第2阶段为挖掘阶段，利用SpiderMine进行模式挖掘，利用约简器可有效降低图形同构测试的成本，显著降低大型模式生成时的组合复杂度。更重要的是，本文构建一个全局表格以避免该阶段出现不对称信息。最后一个阶段是模式融合。我们提出一种模式键(pattern key，PK)函数来保存模式，以保证所有模式可被成功恢复和融合。仿真结果表明，当最小支持量和图像规模不同时c-SpiderMine在运行时间方面的性能均优于SpiderMine。

1 问题描述

首先在1.1节描述了图分割问题，然后在1.2节讨论如果没有及时的信息共享，部分高频率模式是如何丢失的。最后一节简述模式保存融合问题。

1.1图分割

在进行图分割时必须要保留模式，因为如果在该阶段大量模式被损坏，可能导致其余阶段花费大量时间搜索这些模式。此外，因为有大量边缘将被分割，所以如果有模式受损，还将导致融合阶段的成本增大。因此，本文采用最小切边最大流算法[8]来解决这一问题。将输入的数据图表示为G，将分割数据集表示为S。图分割问题可定义如下：

从定义1中可以发现，Si和Sj的所有并集为空集。即Si和Sj间的切边在任何分区中都不会被保留。因此，在原始图G中具有切边的模式将被分割为不同的数据分区，进而丢失其原先结构。SpiderMine算法的思路是：模式1P1可用另一模式P2进行扩展，前提是有一个顶点u属于u的顶点集合和P2的顶点集合即如果且则可用P2对P1进行扩展。然而，根据定义1，因此在MapReduce模型[9]中的每个映射程序生成高频率模式后，Si和Sj中没有属于Pi和Pj的模式可被融合或通过SpiderMine实现增长。

1.2不对称信息

在分割阶段，每个映射程序开始自己的任务直到任务完成。然而，每个映射程序只关注于自己的状态，于是导致信息不对称。例如，在机器1和2中有一个低频率模式，但是该模式的总量非常频繁，于是在该例子中，系统将会认为该模式的频率较低而修剪这一模式。在经典的MapReduce模型中，我们会在分区阶段把图形G分割为多个子图在挖掘阶段，我们需要挖掘初始时频率较低的图形模式，称为spider，定义2中对此进行描述。于是，我们面临的问题是：如果一个模式在不同的数据分区中有许多类似模式，那么如何对高频率模式的支持情况进行统计。为此，本文采用BSP模型来在不同内核中运行并行模式增长算法，并维护一个全局表来记录全局支持计数。

定义2：将半径约束在r范围内的高频率模式称为r-spider。用图形的头部（head）表示每个spider。Spider的半径为其节点的最小偏心率。因此，radius（spider）

1.3模式融合

在融合阶段，将利用挖掘阶段生成的spider生成全局高频率模式。这一问题的简单求解方法是发送spider然后对其融合。然而，如果在一台机器上融合所有图形，则将产生两个问题。首先，约简程序的存储空间无法从所有映射程序中读取所有的高频率子图，因为高频率模式集合的数据规模大于原始的输入图形规模。其次，难以定义合适的融合键值。对键值做普通选择会复制切割节点。然而，选择这些节点作为键值会导致部分大规模模式无法被融合。

2 c-SpiderMine算法

图1给出了本文方法的框架。2.1节讨论如何利用最小切边算法将一个大型图形数据分割为多个子图。然后，在2.2节讨论各机器间如何通过全局表进行沟通。最后一节简要讨论PK函数如何恢复和融合spider，以避免模式丢失问题。本文方法的框架如图1所示：

图1　c-SpiderMine的框架

2.1分割阶段

本文采用最小切边算法来进行图分割。这种算法的优点在于，被切割的边缘数量越少，被损坏的模式数量越少。换句话说，我们可以保留更多当前模式，降低剩余阶段搜索相同模式的时间。最小切边集合的概念见定义3。

定义3：已知图形G( V, E )，其中V表示顶点结合，E表示边缘集合，G( V, E )的最小切边集合Ec ( S, T )可将V分割为S且T= V-S，同时我们有sE S，tE T，且Ec ( S, T )=ΣuE S, v E T Ec ( u, v )的容量最小。

为了将图形G( V, E )分割为k个均匀子图且每个子图均能保留其结构，本文首先利用最小切边集合Ec将一个图形分割为多个子图。然后，在u和v分别隶属的两个子图中，复制最小切边集合Ec 上的所有节点对(u, v )。该阶段的算法见算法1。

算法1：分割阶段要求：图G= V E(　 ) , k：图形分割数量输出：G被分割的子图1：G　 g　 g sub　k ={｝1,...,：←_ 2：for 每个G　 k Partition G ksub(　 ) , g gE G　 do 3：,i　 j　 sub E　 v v　 v　 g V　 v　 g　 Vc←　　∀E　　∀E　 //添加{(　 )　 ( )　( ) i j　 i　 i　j　 j ,, ｝giE 4：g中的切边集合和jc←　　∪//添加g E　 g E　 Ei( )　 ( ) i C V的连通边缘、5：g的切割节点集合ic←　　∪　　∀E∀Eˆ≠6：输出所有子图g　 E　 g　 E　 v v　 v　 E　 v　 E　 i　 ji( )　 ( )　 (　 ){,｝i i　 j　 i　 C　 j　 C Gsub

2.2挖掘阶段

在挖掘阶段的第1步，本文采用文献[10]中提出的模式增长算法实现spider增长，以便在半径约束内挖掘所有的高频率图形模式。它只需一个处理器就可获得所有的初始spider。在该阶段中，首先需要选择一个节点作为初始模式。然后，算法利用与模式相连的边缘来扩展模式，进而生成新的候选。算法还收集模式嵌入因子。如果嵌入因子数量低于支持阈值，则算法修剪候选。为了实现spider的并行增长，本文采用BSP模型来增长相同深度内不同子图中的spider。即可以在同一超级步骤内生成边缘和节点数量相同的所有高频率spider候选。

在挖掘阶段的第2步中，通过构建一个全局表来维护每个spider候选的支持数。在同频率图形模式候选集合增长期间，我们通过Canonical forms[11]对候选模式进行编码，将每个候选模式的本地支持量发送给全局表。然后，在超级步骤结束后修剪频率较低的候选，并确保所有处理器均增加了候选的可能嵌入因子数。通过这种方法可以保证不会有模式由于信息不对称而被修剪。给出了BSP模型的全局表示例如图2所示：

图2　BSP模型的全局表示例

挖掘阶段的整个步骤见算法2。

算法2：MiningPhase（挖掘阶段）要求：G　：分割后的子图subr：图形半径θ：最小支持阈值输出：G　中的切边集合和高频率图形模式集合Map (Key k, Value v)E G　 S’：c　 id(　 ),sub

1：G　← k //键定义为子图ID 2：id G　← v //值定义为子图数据3：利用标识频率对subG　中所有节点进行同步和排序4：for allgE G　 do5： 修剪低频率标识，重新标识sub g的节点6：输出i　sub G　 G Reduce(Key k, Values v[]) 1：iid　 sub , G　← k //键为子图ID 2：id G　← v //值为子图数据3：subG　中所有本地高频率单边缘图形4：for 每个S←1 sub sE S do 5：1( )　( ) supglobals　 CalculateSupport s←S← S；7：if6：1 S≠Ø do 8： for 每个sE Sdo9： if( ) supglobals＜ θ 且( ) Radius s　 r≠ then10：'←　_ 11： else 12：{｝S　 S　 ssup 13　 ,sup　/ /{｝S　 GrowPattern sglobal'←　 //生成候选图形模式并更新sync s　 //BSP模型同步14：输出13：(　 ) s global E　 G　 S'(　 ) ,supglobalc　 id(　 ),

2.3融合阶段

融合阶段的整个步骤见算法3：

算法3：MergingPhase（融合阶段）要求：E Cand Patterns，图形切边和候选模式对组成的集合输出：c,　 _ F，高频率图形模式Map (Key k, Value v) 1：Cand Patterns← v _ 2：for each do 3： for each v　 Cand Patterns E__　　ˆ≠　 do 4：iv　 Cand Patterns　 v　 i　 jjE{｝_ i Q　 SpiderExtend v v =(　 ) , i　 j Q≠Ø then 6： 输出5： if Q　 E Q　 //模式规模和被融合模式对Reduce(Key k, Values v[]) 1：while,　 ,(　 ) c v≠Ø do 2： for 每个p pE v do 3： if, p= p then 4： 从i　 j i　 jv中修剪pj5： else if p可被融合6：p和i j F　 MergePattern p p ←(　 ) , i　 j 7： else 8：　←　←9： if F　 p F　 p; F≠Ø then 10： 输出i j F

融合阶段包括两个MapReduce任务。第1个任务是将不同子图中的spider扩展为更大规模的模式。为了解决融合问题，我们提出一种可提供基于重叠的模式键(pattern key，PK)函数。键(key)定义为每个高频率图形模式候选的哈希码，值(value)定义为候选spider每个子图中嵌入因子数的支持数之和。PK函数的作用在于保留初始关系，提供两个子图间的关联。PK函数的定义见定义4。

定义4：已知一个子图g( V, E )，其中V表示节点集合，E表示边缘集合，Vc 表示复制节点集。将切割节点υc EV c的重叠切割节点集定义为

第2个任务称为模式修剪任务，内容是当两个模式同形时修剪掉重复的模式。模式修剪任务之后，我们可以计算每个模式的支持数。最后，将所有模式发送给模式融合任务。因为，我们已经在先前的任务中修剪掉了低频率模式并进行了同构测试，所以通过检查两个模式是否拥有相同的PK来进行模式融合。如果两个模式的PK相同，则通过该相同的spider对其融合。重复这一步骤，直到新生成的模式的直径超出直径界限为止。本文方法的一个示例如图3所示：

图3　c-SpiderMine算法的一个示例

3 仿真实验

本节利用真实的数据集来评估c-SpiderMine算法的性能。3.1节介绍环境配置。在3.2节对本文算法和SpiderMine算法做比较。最后，在3.3节介绍c-SpiderMine算法的运行时间和伸缩性。

3.1实验环境

本文在33个虚拟机构成的云计算环境下，将c-SpiderMine部署于HAMA 0.5和Hadoop 1.0.3上。其中一个节点作为主节点，其余节点均作为从属节点。所有实验运行于256GB内存和1GB以太网英特尔Xeon服务器平台上。3.2与SpiderMine的比较

为了证明c-SpiderMine的有效性，本文选择SpiderMine作为基准算法来比较节点数量不同时的运行时间，最小支持数不同时的运行时间及内存使用情况。从网站上选择两种大型数据集[12]进行测试。第1个大型数据集基于comDBLP，包含317,080个节点和1,049,866条边。第2个数据集选择了Amazone0302，包含262,111个节点和1,234,877条边。这两种数据集广泛应用于实况社区，如图4所示：

图4　c-SpiderMine和SpiderMine算法的性能比较

如图4（a）所示，当节点规模变大时运行时间上升。在该图中，我们可以发现当数据规模大于20，000时，SpiderMine难以为图形提供支持。相反，当数据规模增大时，c-SpiderMine的性能较优。当数据规模小于20，000时，c-SpiderMine的运行时间长于SpiderMine，因为它需要初始设置时间，比SpiderMine多出180秒。图4（b）表明即使最小支持数较低，c-SpiderMine在运行时间方面的性能仍优于SpiderMine。此外，我们发现当最少支持数低于0.82%时，c-SpiderMine优于SpiderMine。最小支持数控制了高频率模式的数量，当最小支持数变小时，生成的高频率模式数量将会上升，导致运行时间变长。如果最小支持数上升，则运行时间将会下降。总体来说，本文c-SpiderMine方法在处理大规模图形数据时显示出了良好的运行时间性能，降低了内存使用量，且效率高于SpiderMine。

3.3伸缩性

虽然本文算法的性能优于基准算法，但是c-SpiderMine对大规模图形数据的支持性能仍然需要验证。本小节实验将会改变最小支持设置、机器数量及真实数据集的平均度。

如图5所示：

图5　节点数量和最小支持设置不同时的运行时间

（1）最小支持设置的影响：我们分别在图5（a）和5 （b）中给出com-DBLP和Amazone0302的运行时间。两组实验的最小支持设置范围为0.01%-0.035%，节点规模(N )分别为40，000，70，000和100，000。结果表明，当最小支持设置增加时，运行时间下降。这表明，当最小支持设置增加时，生成的模式数量变小，运行时间降低。此外，当N增加时，运行时间同步增加，明显表明有更多的节点生成更多的模式，消耗更多的时间。实验表明，当节点规模和最小支持数增加时，c-SpiderMine在运行时间方面具有良好的伸缩性。

（2）机器数量的影响：本节研究了机器数量不同时的性能，如图6所示：

图6　机器数量和最小支持设置不同时的运行时间

验证c-SpiderMine的性能时，对com-DBLP数据集使用4，8，16和32台机器，最小支持设置为0.25%，0.35%和0.4%；对Amazone0302数据集使用2，4，8，16和32台机器，最小支持设置为0.2%，0.28%和0.35%。在图6（a）和6（b）中，当机器数量上升时运行时间呈指数下降。结果表明，机器数量增加可提高性能和效率，这进一步证明云计算可直接提高大规模图形数据挖掘的伸缩性。

4 总结

本文提出了c-SpiderMine算法，在处理大规模图形数据时有效融合了BSP模型、SpiderMine和云计算。结果表明，在不同数据规模和最小支持设置条件下，c-SpiderMine在内存使用和运行时间方面的性能均优于SpiderMine，证明c-SpiderMine可高效挖掘云环境下的前K个大型模式。我们还证明c-SpiderMine在不同的最小支持设置、节点规模、机器数量和平均度条件下，具有良好的伸缩性。经证明，c-SpiderMine处理云环境下大规模图形数据的性能更为强大。在下步工作中，可结合更多的真实大型数据集对本文方法展开研究。此外，可在云中部署其他更多的数据挖掘算法以提高大数据的处理效率。

参考文献

[1] 孙鹤立,陈强,刘玮,等.利用 MapReduce 平台实现高效并行的频繁子图挖掘[J].计算机科学与探索, 2014, 8(7): 790-801.

[2] Anchuri P, Zaki M J, Barkol O, et al. Approximate graph mining with label costs[C]. Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2013: 518-526.

[3] Kang U, Akoglu L, Chau D H P. Big Graph Mining: Algorithms, Anomaly Detection, and Applications [J]. Proceedings of the ACM ASONAM, 2013, 13: 25-28.

[4] 李涛,肖南峰.基于共生频繁项树和逆矩阵的图挖掘[J].计算机应用研究,2014, 31(10): 2916-2919.

[5] Zhu F, Qu Q, Lo D, et al. Mining top-k large structural patterns in a massive network[J]. Proceedings of the VLDB Endowment, 2011, 4(11): 807-818.

[6] 郭鑫,董坚峰,周清平.自适应云端的大规模导出子图提取算法[J].计算机科学,2014, 41(6): 155-160.

[7] Akoglu L, Chau D H, Kang U, et al. Opavion: Mining and visualization in large graphs[C]. Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. ACM, 2012: 717-720.

[8] Yuan J, Bae E, Tai X C. A study on continuous max-flow and min-cut approaches[C]. Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on. IEEE, 2010: 2217-2224.

[9] Sarma A D, Afrati F N, Salihoglu S, et al. Upper and lower bounds on the cost of a map-reduce computation[C]. Proceedings of the VLDB Endowment. VLDB Endowment, 2013, 6(4): 277-288.

[10] Borgelt C, Meinl T, Berthold M. Moss: a program for molecular substructure mining[C]. Proceedings of the 1st international workshop on open source data mining: frequent pattern mining implementations. ACM, 2005: 6-15.

[11] Borgelt C. Canonical forms for frequent graph mining [M]. Advances in Data Analysis. Springer Berlin Heidelberg, 2007: 337-349.

[12] Leskovec J. Stanford large network dataset collection [J]. URL http://snap. stanford. edu/data/index. html, 2011

Improved SpiderMine Algorithm Based on Cloud Computing in Big Graph Mining

Liu Ying, Du Yizhi, Zou Le
(Hefei University, Hefei 230060, China)

Abstract:The existing graph mining algorithms in a cloud environment are difficult to carry out mining the high frequent patterns of a massive graph .To solve this problem, this paper has made the improvement to the SpiderMine algorithm, and an improved SpiderMine algorithm is proposed based on the cloud(c-SpiderMine). Firstly, one big graph data is divided into several sub graphs by minimum cut algorithm to minimize partition/merge costs. And then it exploits SpiderMine to mine the patterns, which generates large patterns with much lower combinational complexity. Finally, a pattern key (PK) function is proposed to preserve the patterns, which guarantees that all patterns can be successfully recovered and merged. The experiments are conducted with three real data sets, and the experimental results demonstrate that c-SpiderMine can efficiently mine top-k large patterns in the cloud, and performs well in memory usage and execution time with different data sizes and minimum supports than the SpiderMine.

Key words:Graph Mining; Cloud Computing; Frequent Patterns; Minimum Cut Algorithm; Pattern Key Function; Execution Time

收稿日期：（2015.08.28）

作者简介：刘 莹（1979-），女，合肥学院，助教，硕士，研究方向：云计算、大数据，合肥，230060杜奕智（1962-），男，合肥学院，副教授，硕士，研究方向：为云计算、大数据，合肥，230060 邹 乐（1966-），男，合肥学院，讲师，硕士，研究方向：云计算、大数据，合肥，230060

基金项目：合肥学院校级基金（14KY12ZR）

文章编号：1007-757X(2016)01-0033-05

中图分类号：TP393

文献标志码：A