大圖挖掘中一種基于云計算的改進SpiderMine算法

劉瑩，杜奕智，鄒樂

?

大圖挖掘中一種基于云計算的改進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