利用局部評估的分布式圖模式匹配算法*

張麗霞，王偉平，高建良，王建新

(1.中南大學 信息科學與工程學院， 湖南 長沙　410083； 2.湖南師范大學 數學與計算機學院， 湖南 長沙　410081)

?

利用局部評估的分布式圖模式匹配算法*

張麗霞1,2，王偉平1，高建良1，王建新1

(1.中南大學 信息科學與工程學院， 湖南 長沙410083； 2.湖南師范大學 數學與計算機學院， 湖南 長沙410081)

摘要：為了在分布式存儲的大規模數據圖上進行快速圖模式匹配，提出利用局部評估的分布式圖模式匹配算法。各計算節點并行地執行本地匹配；協調器節點收集局部匹配結果、計算邊界點的匹配狀態并發送給相應的計算節點；計算節點根據邊界點的匹配狀態確定與邊界點相連的節點的匹配情況；協調器節點組合得出最大匹配集。實驗結果表明：與已有的分布式圖模式匹配算法相比，disGPM-PE算法都能夠在不顯著增加通信量的前提下避免數據片段間的依賴關系對執行時間的影響，從而減少圖模式匹配的時間。

關鍵詞：圖模式匹配；分布式算法；局部評估

來自互聯網及生活中的海量數據之間存在緊密的關聯性，圖作為一種被廣泛應用的數據結構，非常適合刻畫這種具有關聯性的數據，圖中的每個頂點代表現實世界中的實體對象，頂點之間的邊表示實體之間的關系。圖模式匹配是從一個數據圖中找出與給定查詢圖(模式圖)相同或相似的子圖。圖模式匹配通常定義為子圖同構[1]。由于子圖同構是NP完全問題(Non-determinsitic Polynomial Complete problem, NPC)并且在有些實際應用中發現有意義的匹配時過于嚴格，因此現實生活中圖模式匹配通常定義為圖模擬[2]。圖模擬把圖模式匹配定義為模式圖中節點和數據圖中節點之間的對應關系，要求數據圖中節點保持模式圖中對應節點的后繼關系。圖模式匹配應用十分廣泛，例如在社交網絡中用于社團發現，在萬維網中用于Web文檔分類，在軟件工程領域用于軟件代碼剽竊檢測[3]以及在生物領域用于蛋白質結構檢測和功能預測等。

隨著社交網絡、生物網絡和Web網絡等的快速發展，互聯網數據量急劇增長。已有的圖模式匹配算法面臨新的挑戰：一方面，大規模的數據無法集中存儲在一個數據中心上，只能分布存儲在多個數據中心上，而且數據中心的地理位置通常較遠；另一方面，數據規模的顯著增大導致用于表示數據及數據間關系的圖的規模顯著增大，即使采用分布式算法進行圖模式匹配也會面臨通信量大、延遲長的問題，如何面向大規模圖提高分布式算法的并行效率成為關鍵。文獻[4]提出的分布式圖模式匹配算法把存儲在不同計算節點上的連通子圖發送到一個計算節點上進行圖模式匹配，缺點是計算節點間通信量較大。文獻[5]提出的分布式算法只在計算節點間傳送邊界點的匹配狀態，但需要每個計算節點建立本地的邏輯依賴圖，對于存在多個節點上的連通子圖，各節點需要依次等待消息才能進行下一輪的匹配，執行時間與計算節點上數據片段間的依賴關系相關。文獻[6]提出了以頂點為中心的分布式圖模式匹配方法，當圖中節點個數多時，效率不高。另外，消息傳遞機制使得可以并行的操作序列化，從而降低了并發性。

為了在減少網絡通信量的同時避免數據片段間的依賴關系對執行時間的影響，本文借鑒文獻[7]針對分布式圖上的節點間可達性查詢問題的解決方法，通過對其思想進行改進和優化，提出了基于局部評估的分布式圖模式匹配算法(distributed Graph Pattern Matching based on Partial Evaluation， disGPM-PE)。算法的基本過程如下：首先各計算節點并行地執行本地匹配，然后協調器節點收集局部匹配結果、計算邊界點的匹配狀態并發送給相應的計算節點，接著計算節點根據邊界點的匹配狀態確定與邊界點相連的節點的匹配情況，最后協調器節點組合得出最大匹配集。與先前的算法相比，disGPM-PE算法具有如下特點：①各計算節點并行進行本地匹配，能夠避免某些分布式算法將分布在不同計算節點上的連通子圖發送到一個計算節點上集中處理，造成較大通信量的問題；②所有計算節點進行局部評估時完全并行，收到協調器節點的求值結果后繼續確定與邊界點相連的節點的匹配狀態時仍然是完全并發執行的；③協調器節點收集來自所有計算節點的匹配結果、邊界點相關的布爾表達式，求值后將結果發給各計算節點。雖然在計算節點和協調器節點之間額外傳送布爾表達式和求值結果在一定程度上增加了通信量，但是各計算節點的匹配次數固定為兩次，匹配次數和并發度不受計算節點上的數據片段之間的依賴關系的限制。

1圖模式匹配相關定義

對于圖模式匹配，模式圖和數據圖都是帶標簽的有向圖，圖中的每個節點有且僅有一個標簽，該標簽定義了節點的屬性(如：關鍵詞、技能、等級、姓名、公司等)，相關定義如下：

定義1(圖)G=(V,E,L)是一個圖，V是節點集，EVV是邊集，L是一個標簽函數，V中的每個節點都有一個標簽att，即L(v)=att，att是v的屬性。

定義2(圖模式匹配)假設有一個模式圖P=(Vp,Ep,Lp)和一個數據圖G=(V,E,L)，u和v分別是P和G中的節點。如果存在一個二元關系RVpV，滿足：

1)如果(u,v)∈R，那么u和v有相同的標簽即Lp(u)=L(v)；

2)對Vp中的任意一個節點u，V中都存在一個節點v，使得：(u,v)∈R；對Ep中的任意一條邊(u,u′)，在E中都存在一條邊(v,v′)使得(u′,v′)∈R；

則說G匹配P，標識為P?G，R是一個匹配。對于任意P和G，如果G匹配P，一定存在一個最大的匹配關系。圖模式匹配問題就是：如果P?G，那么在G中為P找出一個最大匹配R。

定義3(分布式圖)G=(V,E,L)一個分布式圖，F={F1,F2,…,Fk}稱作G的一個劃分，其中每個片段Fi={Vi∪Fi.O,Ei∪CEi,Li∪Li.O}(1≤i≤k)且以下條件成立：

1)V={V1∪V2∪…∪Vk}；

2)任一(Vi,Ei,Li)是G的一個子圖；

3)對Vi中的任一節點u,如果E中存在一條邊(u,v)且v在另一個片段中，那么v稱作是Fi的一個虛節點(virtual node)，Fi.O是Fi的虛節點的集合。相應地，如果存在一條從片段Fj中的節點v到片段Fi中的節點u的跨邊(v,u)，那么u稱作是Fi的一個入節點(in node)，我們用Fi.I表示Fi的入節點集合；

4)CEi={(u,v)|(u,v)∈E,u∈Vi,V∈Fi.O}是從Vi到其他片段中節點跨邊的集合。

2disGPM-PE算法

2.1算法主要思想及流程

在disGPM-PE算法中，每個計算節點處理的節點被分為以下幾類：虛節點、內部節點、與虛節點相連的節點和入節點。虛節點是存儲在別的數據片段和計算節點上、被復制一份存在本地的節點，本地僅知道其標簽而不知其孩子節點，算法在進行本地處理時只能根據其標簽把它加入對應節點的匹配集中而不能根據后繼點對其進行篩選確定其最終匹配狀態，這種匹配可能不是真的匹配、不會出現在最終的匹配集中，屬于局部匹配；內部節點是指和虛節點沒有關系的節點，算法僅根據本地數據就可以確定這些節點的匹配狀態；與虛節點相連的節點是指有路徑到達虛節點的節點，如果本地不能確定其匹配狀態，就把它們加入局部匹配集中；入節點是指存在一條來自于其他數據片段上邊的節點，如果其匹配狀態與虛節點匹配狀態有關，則可用一個布爾表達式描述它們之間的關系。

假設數據圖G的一個劃分F={F1,F2,…，Fk}，每一個片段Fi存放在一個計算節點Mi上，模式圖及圖模式匹配請求發送給一個協調器節點Mc。disGPM-PE算法流程如圖1所示。

圖1　disGPM-PE算法流程圖Fig.1　Algorithm flow chart of disGPM-PE

算法具體操作過程如下：①協調器節點Mc把模式圖發給每個計算節點；②每個計算節點收到模式圖P后，并行地調用本地圖模式匹配子算法(local Graph Pattern Matching，localGPM)，根據本地數據執行圖模式匹配，產生三個集合：內部節點匹配結果Mi.C，與虛節點相連的節點的匹配結果Mi.U和布爾表達式集合Mi.beset；③每個計算節點把第二步產生的Mi.C和Mi.beset發送給協調器節點Mc；④Mc把從每個計算節點收集的Mi.beset組合成一個布爾表達式系統，調用布爾表達式求值子算法(evaluate Boolean Expressions，evalBE)求得各虛節點的匹配狀態；⑤Mc把虛節點的匹配狀態發給各計算節點；⑥各計算節點執行局部匹配篩選子算法(Refining Partial Matching，RPM)對局部匹配集Mi.U進行篩選，確定與虛節點相連的節點的匹配狀態，匹配結果存入最終匹配集Mi.F中；⑦各計算節點把與虛節點相連的節點的匹配結果發到Mc。最終，協調器節點Mc把從各計算節點收到的所有匹配結果組合在一起，就得到了最大匹配集M。

2.2本地圖模式匹配子算法localGPM

當每個計算節點Mi收到模式圖P后，并行地調用localGPM根據本地數據Fi執行圖模式匹配，輸出三個集合：內部節點的匹配集Mi.C、局部匹配集Mi.U和布爾表達式集Mi.beset。其執行過程如下：首先，僅根據標簽產生模式圖中的各個節點的候選匹配集；然后，對候選匹配集中的內部節點根據后繼進行篩選，產生內部節點的匹配集Mi.C；接著，對候選匹配集的虛節點w，假設它屬于模式圖中節點u的候選匹配集且u在模式圖中有后繼，則將w加入局部匹配集Mi.U中并在Mi.beset中加入一個布爾變量X(u,w)，表示需要從協調器節點獲知w是否匹配u，對于候選匹配集中與w相連的節點w′，如果其匹配狀態取決于w的匹配狀態，則將其加入局部匹配集Mi.U；最后，對局部匹配集中Fi中的入節點v，求出一個布爾表達式加入Mi.beset，該表達式表示v匹配u需要Fi中的虛節點滿足的條件。

圖2給出一個分布式數據圖和需要查找的模式圖的實例，圖2(a)為模式圖，圖2(b)為數據圖。

設F1～F4分別存放在計算節點M1～M4上。在M1上除A2為入節點且與虛節點相連外，A1～H1均為內部節點，在執行localGPM時，所有內部節點都是和模式圖中的點匹配的，因此M1.C包括所有的內部節點；B2和C2是虛節點，將它們加入局部匹配集Mi.U，并把X(B,B2)和X(C,C2)加入M1.beset，A2與虛節點B2及C2相連且其匹配狀態不確定的，因此A2也加入Mi.U；由于A2是入節點，因此將布爾表達式X(A,A2)=X(B,B2)∧X(C,C2)加入M1.beset。各計算節點執行localGPM算法后的結果如表1所示。

表1　各計算節點執行localGPM后的結果

(a)模式圖(a) Pattern graph　　　　　(b)數據圖(b) Data graph圖2　分布式數據圖和模式圖的一個實例Fig.2　An example of distributed data and pattern graph

2.3布爾表達式求值子算法evalBE

當各計算節點把本地匹配的結果Mi.C和Mi.beset發送給協調器節點Mc后，Mc先組合這些結果得到M和布爾表達式集合(BEset)，然后執行布爾表達式求值子算法evalBE得到所有布爾表達式的值。

子算法evalBE首先根據BEset建立虛節點匹配狀態邏輯關系圖，然后對邏輯關系圖中的各節點求值。建立虛節點匹配狀態邏輯關系圖的過程如下：Beset中的每個布爾變量對應邏輯關系圖中的一個節點；由于一個布爾等式左邊的布爾變量的值和右邊的布爾變量的值有關系，因此對于每個布爾等式，代表等式左邊的布爾變量的節點和每個代表等式右邊的變量的節點之間存在一條邊，連接等式右邊的變量之間的邏輯運算符作為代表等式左邊布爾變量的節點的屬性，當等式右邊只有一個布爾變量時，代表等式左邊布爾變量的節點的屬性為空。

對于圖2中的實例，建立的虛節點匹配狀態邏輯關系圖如圖3所示。根據該邏輯關系圖對圖中各節點求值的過程如下：首先，由于葉節點(G,G2)不屬于M，因此X(G,G2)為假；其次，因為節點X(E,E3)和節點X(G,G3)形成一個環，互為依賴條件，所以它們的值都為真；最后，按照廣度優先搜索的逆序依次對邏輯關系圖的剩余節點求值，能夠得到邏輯關系圖中所有節點的值。求值過程結束后，協調器節點把得到的布爾表達式的值發送給需要這些值的計算節點。

圖3　根據BEset建立的虛節點匹配狀態邏輯關系圖Fig.3　Constructed virtual node matching condition logic diagram according to BEset

2.4局部匹配篩選子算法

各計算節點接收到布爾表達式的值后，調用局部匹配篩選子算法RPM對局部匹配集Mi.U進行篩選，獲得最終的匹配結果Mi.F。算法的具體過程為：首先對每個收到的布爾等式進行處理，如果X(u,w)=1，則表示w匹配u，將w加入u的匹配集中；然后對P中節點u的局部匹配集中的每個節點w和Ep中的每條邊(u,u′)，如果u′的局部匹配集中有w的孩子節點且至少有一個孩子節點在u′的匹配集中，那么可以確定w匹配u。篩選操作完成后，各計算節點得到與虛節點相連的那些節點的最終匹配狀態，并把匹配結果發送給協調器節點。

3實驗與結果分析

3.1disGPM-PE算法與已有分布式算法的比較

根據兩個具有典型代表的分布式圖匹配算法[4-5]的基本思想設計參考算法并與disGPM-PE算法進行比較。參考算法1(refGPM-1)基于文獻[5]算法基本思想，不同計算節點之間僅傳送虛節點的匹配信息，當位于不同計算節點上的數據片段之間具有依賴關系時，不作任何優化，多個計算節點根據數據片段之間的依賴關系依次進行圖匹配。參考算法2(refGPM-2)基于文獻[4]算法基本思想，首先每個計算節點并行地對本地數據進行圖模式匹配，然后存儲在不同計算節點上的連通子圖被發送到一個計算節點上進行組合，最后再對組合后的子圖進行圖模式匹配。

首先使用默認實驗環境配置，模式圖中有9個節點，對disGPM-PE算法和兩種參考算法進行對比實驗。圖4為各算法的通信量的比較結果。如圖所示，無論是對于Amazon，Google還是合成數據集Synthetic，refGPM-1算法具有最小的通信量，因為使用該算法時，不同計算節點之間僅需要傳送邊界點的匹配信息。而refGPM-2算法的通信量最大，因為使用該算法時，需要根據數據圖的劃分情況，將存儲在多個計算節點上的連通子圖發送到一個計算節點上進行組合。所提出的disGPM-PE算法的通信量介于refGPM-1和refGPM-2算法的通信量之間，因為僅需要在計算節點之間傳輸布爾等式和虛節點的匹配狀態信息，避免傳輸整個連通子圖，因此通信量小于refGPM-2算法的通信量，但是大于refGPM-1算法僅傳輸邊界點的匹配信息所需的通信量。

圖4　各算法通信量的比較結果Fig.4　Network traffic of different algorithms

圖5為disGPM-PE與兩種參考算法的執行時間的比較結果。如圖5所示，對于三個數據集，refGPM-1算法的執行時間最長，原因是該算法執行過程中多個計算節點根據數據片段之間的依賴關系依次進行圖匹配，具有依賴關系的數據片段所在的計算節點不能獨立處理這些數據片段，依賴關系越多，并行性越差，執行時間越長。refGPM-2算法和disGPM-PE算法均能夠對本地數據并發地進行圖模式匹配，refGPM-2算法比disGPM-PE算法的執行時間稍長，因為其通信量較大造成通信時間較長。

圖5　各算法執行時間的比較結果Fig.5　Execution time of different algorithms

分析圖4和圖5的實驗結果發現：refGPM-1算法雖然具有最小的通信量，但是執行時間最長；refGPM-2算法雖然需要更多的通信量，但是卻能夠節省執行時間；所提出的disGPM-PE算法在具有比refGPM-2算法執行時間稍短的情況下，具有較小的通信量。對于大規模分布式圖來說，圖匹配算法的執行時間非常重要，通信量也是必須控制的關鍵指標，所提出的disGPM-PE算法能夠在降低執行時間的前提下控制節點間通信量的顯著增長。

3.2模式圖大小對disGPM-PE執行時間的影響

3.3數據圖大小對disGPM-PE執行時間的影響

(a) 模式圖節點個數對算法執行時間的影響(a) Execution time with different number of pattern graph nodes

(b) 模式圖的邊密度對算法執行時間的影響(b) Execution time with different edge density of pattern graph

(c) 數據圖規模對算法執行時間的影響(c) Execution time with different size of data graph圖6　模式圖和數據圖規模對算法執行時間的影響Fig.6　Effects of the sizes of pattern graph and data graph on the execution time of disGPM-PE

3.4模式圖大小對disGPM-PE通信量的影響

3.5數據圖大小對disGPM-PE通信量的影響

(a) 模式圖節點個數對網絡通信量的影響(a) Network traffic with different number of pattern graph nodes

(b) 模式圖的邊密度對網絡通信量的影響(b) Network traffic with different edge density of pattern graph

(c) 數據圖規模對網絡通信量的影響(c) Network traffic with different size of data graph圖7　模式圖和數據圖大小對算法網絡通信量的影響Fig.7　Effects of the sizes of pattern graph and data graph on the network traffic of disGPM-PE

4結論

針對分布式大圖提出一種基于局部評估的分布式圖模式匹配算法disGPM-PE，算法具有不需要明確知道數據是如何分布存儲的特點，對圖的劃分和存儲沒有任何限制，因此具有更好的適用性。算法通過僅傳輸布爾等式和虛節點的匹配狀態，能夠避免部分已有算法由于需要傳輸連通子圖而增加通信量，同時通過協調器節點統一計算虛節點匹配狀態，能夠在數據片段具有依賴關系時，避免串行進行圖模式匹配，因此執行時間不會隨依賴關系的增加而增加。實驗結果表明，和已有算法相比， disGPM-PE算法能夠在降低執行時間的前提下有效控制節點間通信量的顯著增長。

參考文獻(References)

[1]Gallagher B. Matching structure and semantics: a survey on graph-based pattern matching [C]// Proceedings of AAAI Fall Symposium on Capturing and Using Patterns for Evidence Detection, Boston, USA, 2006: 45-53.

[2]Fan W F, Li J Z, Ma S, et al. Graph homomorphism revisited for graph matching [C]// Proceedings of the 36th International Conference on Very Large Data Bases, Singapore, 2010: 1161-1172.

[3]Liu C, Chen C, Han J W, et al. GPLAG: detection of software plagiarism by program dependence graph analysis[C]// Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Philadelphia, USA, 2006: 872-881.

[4]Ma S, Cao Y, Huai J P, et al. Distributed graph pattern matching[C]// Proceedings of the 21th International World Wide Web Conference, Lyon, France, 2012: 949-958.

[5]Fan W F, Wang X, Wu Y H,et al. Distributed graph simulation: impossibility and possibility [C]// Proceedings of the 40th International Conference on Very Large Data Bases, Hangzhou, China, 2014: 1083-1094.

[6]Frad A, Nisar M U, Ramaswamy L, et al. A distributed vertex-centric approach for pattern matching in massive graphs [C]// Proceedings of IEEE International Conference on Big Data, Santa Clara Marriott, CA, USA, 2013: 403-411.

[7]Fan W F, Wang X, Wu Y H. Performance guarantees for distributed reachability queries[C]// Proceedings of the 38th International Conference on Very Large Data Bases, Istanbul, Turkey, 2012: 1304-1315.

[8]Stanford University. Stanford large network dataset collection[EB/OL] (2014-01-15)[2014-04-10]. http://snap.stanford.edu/data/index.html.

[9]Dean J, Ghemawat S. Mapreduce: simplified data processing on large clusters [C]// Proceedings of the 6th Symposium on Operating Systems Design and Implementation, San Francisco, USA, 2004.

[10]Malewicz G, Austern M H, BikA J C, et al. Pregel: a system for large-scale graph processing [C]// Proceedings of International Conference on Management of Data, Indianapolis, Indiana, 2010: 135-145.

doi:10.11887/j.cn.201602013

*收稿日期：2015-03-27

基金項目：國家自然科學基金資助項目(61232001，61173169)；湖南省教育廳資助項目(15C0824)

作者簡介：張麗霞(1979—)，女，河南周口人，講師，博士研究生，E-mail：smilingilsa6@163.com；王偉平(通信作者)，女，教授，博士，博士生導師，E-mail：wpwang@csu.edu.cn

中圖分類號：TP311

文獻標志碼：A

文章編號：1001-2486(2016)02-075-07

A distributed graph pattern matching algorithm using partial evaluation

ZHANG Lixia1, 2, WANG Weiping1, GAO Jianliang1, WANG Jianxin1

(1. School of Information Science and Engineering, Central South University, Changsha 410083, China；2. School of Mathematics and Computer Science, Hunan Normal University, Changsha 410081, China)

Abstract：In order to execute graph pattern matching quickly in distributed large-scale graphs, an effective distributed algorithm using partial evaluation, namely disGPM-PE was proposed. Firstly, partial matching was performed locally at each computer nodes in parallel. Secondly, a coordinator node assembled the partial matching results, evaluated and sent the matching conditions of boundary nodes to corresponding computer nodes. Thirdly, each computer nodes determines the matching conditions of the nodes connected to the boundary nodes. Finally, the maximum matching set was collected at the coordinator node. Experiment results show that the disGPM-PE algorithm can avoid the impact of the dependent relations between data fragments on the execution time. Compared with the previous distributed graph pattern matching algorithms, the disGPM-PE algorithm can reduce the execution time of graph pattern matching while do not increase the network traffic obviously.

Key words：graph pattern matching; distributed algorithms; partial evaluation

http://journal.nudt.edu.cn