許 嘉，張千楨，趙 翔，呂 品，李陶深,2

1.廣西大學 計算機與電子信息學院，南寧 530004

2.廣西高校并行分布計算技術(shù)重點實驗室，南寧 530004

3.廣西多媒體通信與網(wǎng)絡(luò)技術(shù)重點實驗室，南寧 530004

4.國防科技大學 信息系統(tǒng)與管理學院，長沙 410073

1 引言

隨著信息科技與互聯(lián)網(wǎng)的快速發(fā)展，數(shù)據(jù)規(guī)模不斷增長，數(shù)據(jù)類型不斷增多，不同領(lǐng)域關(guān)注的實體對象之間的關(guān)系變得更加復雜，如何分析和挖掘大數(shù)據(jù)中蘊含的復雜關(guān)系吸引了諸多研究學者。圖（graph）作為一種廣泛使用的數(shù)據(jù)結(jié)構(gòu)，圖中的每個節(jié)點代表現(xiàn)實世界中的實體對象，節(jié)點之間的邊表示實體之間的關(guān)系，適合描述上述這種存在有內(nèi)在復雜關(guān)系的數(shù)據(jù)。子圖模式匹配返回數(shù)據(jù)圖中所有和給定模式圖相同或相似的子圖，是分析和挖掘圖數(shù)據(jù)的重要查詢操作，具有眾多實際應用。例如在社交網(wǎng)絡(luò)（新浪微博、微信等）中，子圖模式匹配通常用于挖掘目標客戶團體[1]；又如在生物分析領(lǐng)域中，子圖模式匹配可用于對未知性質(zhì)的蛋白質(zhì)進行輔助分析[2]。

然而在現(xiàn)實世界中，描述實體對象圖數(shù)據(jù)的結(jié)構(gòu)和內(nèi)容往往會隨著時間的推移發(fā)生變化。例如社交網(wǎng)絡(luò)中，2010年Facebook網(wǎng)站的用戶從3.37億人增加到5.85億人，平均每分鐘都會有47 553對好友之間建立或者解除關(guān)系；2011年，Google+在上線后的兩周時間增長了1 000萬的用戶[3]。生物分析領(lǐng)域中，蛋白質(zhì)與酶會發(fā)生復雜的交互與代謝關(guān)系，導致蛋白質(zhì)的結(jié)構(gòu)發(fā)生變化。這些數(shù)據(jù)表明，現(xiàn)實世界中的實體對象和它們之間的關(guān)系無時無刻都可能經(jīng)歷著變化。如果每一次變化都重新對如此大規(guī)模的數(shù)據(jù)圖進行一次完整的圖模式匹配必然耗費大量的時間和資源。由此可見，研究動態(tài)圖的增量圖模式匹配算法具有重要的意義，因為其能夠利用前次匹配結(jié)果，快速得到數(shù)據(jù)圖動態(tài)更新后變化的匹配結(jié)果。

本文設(shè)計與實現(xiàn)了面向動態(tài)數(shù)據(jù)圖的增量圖模式匹配算法，主要貢獻如下：

（1）提出了一種基于圖結(jié)構(gòu)分解的動態(tài)圖增量匹配算法框架，通過記錄中間結(jié)果并構(gòu)建匹配所需的索引，加速后續(xù)圖模式匹配的執(zhí)行效率。

（2）基于前次匹配結(jié)果和維護的索引信息，將數(shù)據(jù)圖中增加的邊事件進行分類，并為每類增加邊事件設(shè)計相應的增量匹配算法，快速更新模式圖和數(shù)據(jù)圖間的模式匹配結(jié)果，有效減少重復計算。

（3）在真實數(shù)據(jù)上對本文提出的算法進行全面測試，驗證了所提算法的有效性。結(jié)果表明本文提出的面向動態(tài)數(shù)據(jù)圖的增量圖模式匹配算法比目前最好的增量匹配算法在執(zhí)行效率上平均提升了1～2倍。

2 相關(guān)工作

2.1 圖模式匹配

子圖模式匹配通常采用基于回溯的方法或基于探索的方法實現(xiàn)?；诨厮莸姆椒ㄊ紫雀鶕?jù)節(jié)點的標簽為模式圖的每一個節(jié)點生成一個匹配候選集，然后根據(jù)一個匹配順序來連接這些候選的匹配點，得到最終匹配結(jié)果。該方法中匹配順序直接影響子圖匹配效率[4-5]?；谔剿鞯姆椒ㄊ菑臄?shù)據(jù)圖的一個節(jié)點出發(fā)，根據(jù)模式圖指定的節(jié)點之間的關(guān)系對數(shù)據(jù)圖進行探索式匹配，即檢測訪問的數(shù)據(jù)圖節(jié)點是否滿足模式圖的匹配要求[6-7]。

子圖同構(gòu)是NP完全問題，在子圖匹配的過程中，當?shù)ヅ淠Ｊ綀D中的每一個節(jié)點時，會產(chǎn)生很多無效的中間結(jié)果，影響匹配效率。針對這類問題，VF2[8]和QuickSI[4]技術(shù)利用模式圖的連通性特征對候選集進行剪枝，提高靜態(tài)圖上的模式匹配效率。TurboISO[9]技術(shù)通過將模式圖中具有相同標簽和相同鄰居的節(jié)點進行合并來減少無效候選對象的產(chǎn)生。除此之外，另一個關(guān)鍵問題是找到一個有效的圖節(jié)點匹配順序。QuickSI[4]技術(shù)采用稀有標簽優(yōu)先策略對模式圖節(jié)點進行排序，首先處理在數(shù)據(jù)圖中出現(xiàn)頻次較低的節(jié)點。SPath[5]技術(shù)采用稀有路徑優(yōu)先策略對模式圖節(jié)點進行排序，當模式圖規(guī)模增大時這類方法的執(zhí)行效率將隨之降低。Bi等人提出在子圖匹配的過程中，除了相似節(jié)點之外不相似節(jié)點也會導致冗余的笛卡爾積，并產(chǎn)生無效的中間結(jié)果[10]。Bi等人因而提出了一種查詢分解的策略，將模式圖分解為核心、森林和葉子三部分，并按照該順序進行模式圖匹配處理。由于核心部分的剪枝能力最強，其次是森林以及葉子部分。基于該順序進行匹配可將笛卡爾積操作拖延到葉子節(jié)點進行，有效減少冗余笛卡爾積的產(chǎn)生，從而達到進一步約減查詢候選集。

2.2 增量圖模式匹配

對于數(shù)據(jù)圖發(fā)生變化的情況，文獻[11]提出了快速不精確圖模式匹配算法及增量算法，將子圖查詢問題轉(zhuǎn)化為向量空間關(guān)系檢測，用近似的方法確定在一組圖流中是否包含給定的模式圖。當數(shù)據(jù)圖增加或者刪除邊時，修改相關(guān)節(jié)點的向量，然后重新檢查新的向量是否包含模式圖的向量來確定匹配狀態(tài)。然而，重新檢查仍然意味著對完整的數(shù)據(jù)圖進行匹配，影響匹配效率。文獻[12]提出了一種增量圖計算的匹配思想，根據(jù)數(shù)據(jù)圖的變化和匹配的影響區(qū)域（等于模式圖直徑）確定潛在會產(chǎn)生匹配結(jié)果的圖節(jié)點集并進行重新匹配，但是隨著模式圖規(guī)模的增大，影響區(qū)域范圍也會相應增大，算法效率大幅度下降。研究發(fā)現(xiàn)，當模式圖較大時，如果數(shù)據(jù)圖每次更新都需要對整個模式圖進行查找將浪費大量時間，因此可將模式圖進行分解。文獻[13]將模式圖分解為一系列單邊或者雙邊子圖，并按照選擇度的高低進行排序，優(yōu)先匹配選擇度高也即識別能力強的邊，有利于減少中間結(jié)果。然而由于分解特征相對簡單，當模式圖較大時，仍會產(chǎn)生大量中間結(jié)果，影響算法效率。文獻[14]提出了一種基于連接與基于探索相結(jié)合的匹配算法，將模式圖按照單匯點有向無環(huán)圖（single sink directed acyclic graph，SSD）進行分解，然后在每個子圖中將節(jié)點信息的傳遞規(guī)則映射到數(shù)據(jù)圖中，從而找到數(shù)據(jù)圖更新后變化的匹配結(jié)果。這種方法主要適用于分布式環(huán)境，不能直接運用于單機環(huán)境。上述所有增量算法的設(shè)計思路基本一致：根據(jù)數(shù)據(jù)圖的變化確定可能受影響的區(qū)域，對受影響的區(qū)域進行重新計算，得到數(shù)據(jù)圖更新后變化的匹配結(jié)果。

上述面向單機環(huán)境的增量算法只能有效處理規(guī)模較小的模式圖，當模式圖增大時算法效率將顯著降低。本文提出一種基于結(jié)構(gòu)分解的精確子圖匹配算法，利用增量計算的思想基于之前的匹配結(jié)果進一步約減數(shù)據(jù)圖動態(tài)變化時的受影響區(qū)域，從而有效提升算法匹配規(guī)模較大的模式圖的執(zhí)行效率。

3 動態(tài)圖匹配問題的形式化描述

本文研究的模式圖和數(shù)據(jù)圖是帶有標簽的無向圖，每個節(jié)點只有一個標簽，標簽決定節(jié)點屬性。

定義1（動態(tài)圖）已知初始數(shù)據(jù)圖G=(U,E,L)，U是圖節(jié)點集，E?U×U是邊集，L是一個標簽函數(shù)，U中每一個節(jié)點都有一個標簽。引發(fā)數(shù)據(jù)圖更新的操作可以用一個三元組＜op,ui,uj＞來表示，其中op={I,D}用來表示邊的增加或者刪除操作，I表示增加邊，D則表示刪除邊，ui和uj表示數(shù)據(jù)圖中的兩個節(jié)點。數(shù)據(jù)圖中增加一個新的節(jié)點可以用一系列跟該節(jié)點相關(guān)的增加邊操作來表示。與此類似，刪除一個節(jié)點可以用一系列跟該節(jié)點相關(guān)的刪除邊操作來表示。給定一個數(shù)據(jù)圖G上的更新操作集合C={＜op1,u1,u2＞,＜op2,u2,u3＞,…,＜opk,uk,uk+1＞}(k≥ 1)，G′則表示數(shù)據(jù)圖G基于操作集合C更新后的數(shù)據(jù)圖。

定義2（動態(tài)圖模式匹配）已知模式圖P(Vp,Ep,Lp)，數(shù)據(jù)圖G和數(shù)據(jù)圖的更新操作集合C，動態(tài)圖匹配問題是指模式圖P與執(zhí)行更新操作C后的數(shù)據(jù)子圖Gsub-t=(Vsub-t,Esub-t,Lsub-t)之間存在一個雙射函數(shù)f，滿足：

其中f(v)表示數(shù)據(jù)圖G中與模式圖節(jié)點v滿足雙射關(guān)系的節(jié)點，即數(shù)據(jù)圖中與節(jié)點v相匹配的節(jié)點。數(shù)據(jù)圖中所有跟模式圖匹配的節(jié)點及它們之間的邊可構(gòu)建出匹配的結(jié)果圖Gr。

4 基于結(jié)構(gòu)分解的增量匹配算法

增量算法是指在數(shù)據(jù)圖發(fā)生變化后，利用現(xiàn)有的匹配結(jié)果以及數(shù)據(jù)圖的變化來得到新增加的匹配結(jié)果，這樣可以最大限度地減小重復計算。在增量匹配過程中，使用索引可以快速縮小搜索空間。建立的索引越多，增量匹配的搜索空間越少，找到新增加的匹配結(jié)果的時間也會越少，但是存儲和維護索引的開銷也越大。為了限制索引存儲和維護開銷，本文僅為模式圖構(gòu)建以下兩類集合作為索引：

（1）match(·)集合：給定模式圖中任一節(jié)點v，match(v)表示數(shù)據(jù)圖中跟v匹配的節(jié)點集合，match(·)集合中所有的點都在匹配的結(jié)果圖中。

（2）candt(·)集合：給定模式圖中任一節(jié)點v，candt(v)表示數(shù)據(jù)圖中除了match(v)之外，標簽跟v相同的節(jié)點集合。

4.1 Inc_CFLS（incremental core-forest-leaf solution）算法基本框架

基于文獻[10]提出的核心-森林-葉子（core-forestleaf，CFL）結(jié)構(gòu)分解框架，本文將模式圖分解為核心、森林和葉子三部分，如圖1所示。

Fig.1 Core-Forest-Leaf decomposition圖1 核心-森林-葉子分解

其中核心部分是指模式圖中的密集子圖，圖中每個節(jié)點的度都大于1。核心結(jié)構(gòu)具有較高的識別能力，在子圖匹配的過程中，首先對核心結(jié)構(gòu)進行匹配可以約減查找空間。其次，對每一部分按照基于路徑的方法制定了一個查詢匹配順序，將模式圖節(jié)點按照制定的順序進行匹配可以進一步約減無效的中間結(jié)果。文獻[10]采用的方法是面向靜態(tài)圖的模式匹配，本文在此基礎(chǔ)上提出了面向動態(tài)圖的增量匹配算法，稱為Inc_CFLS。

本文所提出的增量圖模式匹配算法的基本框架如圖2所示。

Fig.2 Basic framework of Inc_CFLS algorithm圖2 Inc_CFLS算法的基本框架

首先使用文獻[10]提出的CPI（compact pathbased）算法，用于第一次在整個數(shù)據(jù)圖G上對模式圖P進行匹配，一方面獲得匹配的結(jié)果圖Gr1，另一方面建立后續(xù)增量匹配所需要的索引index1。對數(shù)據(jù)圖的更新，表示為ΔG，可以分為“增加邊”（E+）和“刪除邊”（E-）兩部分。首先對增加的邊調(diào)用算法Add-Edges，獲得匹配結(jié)果圖Gr2以及更新后的索引index2；接著調(diào)用算法DelEdges，獲得匹配結(jié)果圖Gr3和更新后的索引index3。根據(jù)匹配結(jié)果圖Gr3可得到數(shù)據(jù)圖更新后所有與模式圖相匹配的子圖，并完成結(jié)果輸出。index3可用于后續(xù)的增量匹配，即在下輪匹配中用上輪得到的index3替換本輪的index1即可。DelEdges算法是一個對結(jié)果圖的精簡過程，且目前的研究方法基本相似，因此本文重點考察對數(shù)據(jù)圖“增加邊”的操作，詳細闡述面向數(shù)據(jù)圖增加邊的子算法AddEdges。

4.2 面向數(shù)據(jù)圖增加邊的子算法AddEdges

研究發(fā)現(xiàn)，當模式圖為樹型結(jié)構(gòu)時（如圖3（a）），可以利用樹結(jié)構(gòu)的特性來進一步縮小匹配的影響區(qū)域。為模式圖中的每個節(jié)點v，產(chǎn)生match(v)和candt(v)這兩個集合作為索引，例如match(v0)為u1，u2。并根據(jù)match(·)集合中的節(jié)點及它們之間的邊構(gòu)建出匹配的結(jié)果圖Gr（如圖3（b））。

影響區(qū)域是指數(shù)據(jù)圖變化引起的結(jié)果圖Gr中可能會發(fā)生變化的索引match(·)對應的模式圖節(jié)點。根據(jù)文獻[10]提出的CPI算法找到模式圖中的根節(jié)點（root），并按照寬度優(yōu)先搜索確認模式圖中每一個節(jié)點所處的層次（level）。

對于每一條新增加的邊(u,u′)，首先需要判斷模式圖中是否存在一條邊(v,v′)與其相匹配，默認level(v)＜level(v′)。以圖3中的模式圖為例，若 (v2,v4)與其相匹配，則需要對(u,u′)進行分類討論來確定影響區(qū)域。

Fig.3 Corresponding result graph of pattern graph P圖3 模式圖P對應的結(jié)果圖

（1）u∈match(v2)，u′∈match(v4)（MM）：此時只需將結(jié)果圖Gr中的節(jié)點u，u′相連即可，不會引起索引的更新。

（2）u∈match(v2)，u′∈candt(v4)（MC）：此時的影響區(qū)域為模式圖中以節(jié)點v4為祖先的所有節(jié)點（affected area of MC，AFF_MC），也就是v6。證明如下：如果非影響區(qū)域（v0，v1，v3，v5，v7）中對應的索引發(fā)生變化，且滿足匹配條件的話，則在增加邊(u,u′)之前，該部分產(chǎn)生的匹配結(jié)果就可以與剩余部分結(jié)合產(chǎn)生新的匹配結(jié)果。因此非影響區(qū)域索引變化產(chǎn)生的匹配結(jié)果在增加邊(u,u′)之前就已經(jīng)在結(jié)果圖Gr中，增加邊(u,u′)不會引起非影響區(qū)域索引發(fā)生變化。

（3）u∈candt(v2)，u′∈match(v4)（CM）：首先找到以節(jié)點v4為祖先的所有模式圖節(jié)點（此例為v6），然后將這些節(jié)點以及節(jié)點v2、v4刪除，剩余部分就是影響區(qū)域（affected area of CM，AFF_CM），證明同上。

（4）u∈candt(v2)，u′∈candt(v4)（CC）：此時的影響區(qū)域為模式圖中除了v2、v4的所有節(jié)點。在子圖匹配的過程中，若影響區(qū)域中節(jié)點v6的候選集節(jié)點u6滿足u6∈match(v6)，則可以將u6從v6候選集中刪除，因為u6不會引起后續(xù)產(chǎn)生新的匹配結(jié)果，證明同（2）和（3）。

綜上所述，當模式圖為樹型結(jié)構(gòu)時，增加邊(u,u′)可以迅速確認影響區(qū)域，減小查找空間。基于此，給出數(shù)據(jù)圖增加邊時的處理算法AddEdges的基本設(shè)計思路：

（1）對于任意給定的模式圖P，首先找到其對應的生成樹PT，如圖4所示。其中模式圖P中的邊可以分為兩部分：一部分是在生成樹PT中的邊，稱為tree邊；另一部分是不在生成樹中的邊，稱為non-tree邊。

Fig.4 Corresponding spanning tree PTof pattern graph P圖4 模式圖P對應的生成樹PT

（2）將PT作為模式圖，在整個數(shù)據(jù)圖G上進行圖模式匹配，得到每個節(jié)點對應的索引match(·)和candt(·)，以及匹配的結(jié)果圖GT。

（3）當增加一條邊(u,u′)時，判斷模式圖P中是否存在一條邊(v,v′)與其相匹配，若存在，則需繼續(xù)對(v,v′)的類型進行討論。當 (v,v′)為tree邊，可以直接根據(jù)(u,u′)的類型來確定匹配的影響區(qū)域。當(v,v′)為non-tree邊時，由于在PT中不存在non-tree邊，此時相當于在PT中增加了一條邊。模式圖增加邊后只會導致匹配結(jié)果減少，因此只需判斷v和v′對應的match(v)和match(v′)中是否有u、u′即可，如果沒有則直接刪除該候選對象。

（4）當增加完所有的邊之后，利用non-tree邊進行剪枝，將結(jié)果圖GT中不滿足non-tree邊關(guān)系的部分刪除，即可得到模式圖P對應的結(jié)果圖Gr。

在子圖匹配方面采用基于相鄰節(jié)點關(guān)系的匹配方式，由于PT是樹結(jié)構(gòu)，可以將PT分解為森林和葉子兩部分，然后根據(jù)CPI算法得到每一部分的匹配順序。當增加的邊的類型為MC，此時只需對影響區(qū)域中的節(jié)點按匹配順序進行匹配即可。在匹配過程中，若影響區(qū)域中節(jié)點v″的候選集節(jié)點u″滿足u″∈match(v″)，則可以將u″從v″的候選集中刪除，因為u″不會引起后續(xù)產(chǎn)生新的匹配結(jié)果。當增加邊的類型為CM時，首先從節(jié)點v開始，按照level遞減的方向找到一條到根節(jié)點的路徑進行匹配，然后從根節(jié)點開始，按照模式圖節(jié)點的匹配順序進行匹配即可，匹配方法與MC相同，若除了u″之外，v″的候選集為? 時，可以進一步確認影響區(qū)域為以v″為祖先的所有節(jié)點。當增加的邊的類型為CC時，匹配方式與CM相同。

從匹配結(jié)果的完整性方面來看，算法將模式圖刪除non-tree邊之后與數(shù)據(jù)圖進行子圖匹配得到的匹配結(jié)果是原模式圖與數(shù)據(jù)圖進行子圖匹配得到的匹配結(jié)果的超集，其后利用non-tree邊的性質(zhì)將無效的結(jié)果從超集里刪除，與在模式圖中增加邊類似[15],這樣就保證了匹配結(jié)果的完整性。從匹配結(jié)果的正確性方面來看，算法采用的是精確的子圖模式匹配算法，找到數(shù)據(jù)圖中與模式圖滿足雙射關(guān)系的子圖，且在剪枝的過程中，僅僅移除無效的節(jié)點以及跟該節(jié)點相關(guān)的邊，因此能夠保證結(jié)果的正確性。

綜上，數(shù)據(jù)圖增加邊時的處理算法AddEdges的偽代碼如算法1所示。

算法1數(shù)據(jù)圖增加邊時的處理AddEdges

輸入：模式圖PT，結(jié)果圖GT=(VT,ET)，match(·)，candt(·)，插入的邊的集合E+，節(jié)點匹配順序order。

輸出：新的匹配的結(jié)果圖GT，更新后的索引match(·)和candt(·)。

算法1首先檢查模式圖P中是否有與(u,u′)相匹配的邊，然后對模式圖邊的類型進行分類討論，其中函數(shù)character_choice1()用來判斷所增加的邊是否屬于tree邊（第1行～第4行）。當對應的模式圖的邊的類型為tree邊時，對(u,u′)的類型進行分類討論，按照(u,u′)的類型來確定影響區(qū)域，相應的在影響區(qū)域中進行子圖匹配（第5行～第22行）。當對應的模式圖的邊的類型為non-tree邊時，分別判斷v、v′所對應的match(v)和match(v′)中是否包含u和u′（第23行～第24行）。對結(jié)果圖GT進行剪枝（第25行），同時GT可繼續(xù)用于后續(xù)增加邊時的匹配計算。

算法2結(jié)果圖GT的剪枝算法CandVerify()

輸入：結(jié)果圖GT=(VT,ET)，模式圖P。

輸出：匹配的結(jié)果圖Gr。

算法2首先檢查non_tree邊對應的(u,u′)是否滿足連接關(guān)系，若不滿足，將這條邊加入到棧中（第1行～第3行）。其次，檢查端點的鄰節(jié)點對應的match(·)中是否有節(jié)點和端點滿足連接關(guān)系，若沒有則將GT中端點的鄰邊及端點刪除，并將刪除的邊加入到棧中（第4行～第11行）。最后返回結(jié)果圖Gr（第12行）。

以圖5為例，圖5（a）表示模式圖P，圖5（b）表示生成樹PT，插入邊集合包括{(u2,u3),(u8,u4),(u15,u14)}。圖5（c）表示增加邊(u2,u3)之后的結(jié)果圖GT1，(u2,u3)為MM邊，將邊(u2,u3)直接加入到結(jié)果圖中即可。圖5（d）表示數(shù)據(jù)圖增加一條邊(u8,u4)后的結(jié)果圖GT2，(u8,u4)為MC邊。此時根據(jù)AddEdges算法確定匹配的影響區(qū)域為節(jié)點v9，需要判斷節(jié)點v9對應的match(v9)和candt(v9)中是否有與u4相連的節(jié)點。由于candt(v10)中u6與u4相連，因此會產(chǎn)生新的匹配結(jié)果。然后分別將u4和u6加入到相應的match(v6)、match(v10)中，并將它們分別從candt(v6)和candt(v10)中刪除。圖5（e）表示數(shù)據(jù)圖增加一條邊(u15,u14)之后的結(jié)果圖，(u15,u14)為CC邊，首先從v2開始找到一條到根節(jié)點的路徑v2、v0。其中v0的候選集為u2且u2∈match(v0)，因此可以將u2從候選集中刪除，此時v0的候選集為空集，因此可以進一步確認影響區(qū)域為v5、v8、v9，并按照v5、v9、v8的匹配順序找到匹配結(jié)果后更新相應的索引。圖5（f）表示經(jīng)過CandVerify()算法剪枝后得到的模式圖P的結(jié)果圖Gr。由于u5與u15不相連，需要將GT3中的相應部分刪除。

5 算法復雜度分析

Inc_CFLS算法主要分為三方面，當增加一條邊時首先確認模式圖的影響區(qū)域，之后在新增加邊周圍的影響區(qū)域范圍內(nèi)利用精確子圖匹配算法得到匹配的結(jié)果圖，最后對得到的結(jié)果圖進行剪枝。

Inc_CFLS 算法使用match(·)和candt(·)作為索引，用來判斷增加邊的類型，以及判斷數(shù)據(jù)圖節(jié)點與相應的模式圖節(jié)點是否匹配。索引match(·)和candt(·)的大小為O(V(P)×V(G))。其中，V(P)表示模式圖節(jié)點數(shù)目，V(G)表示數(shù)據(jù)圖節(jié)點數(shù)目。當數(shù)據(jù)圖增加一條邊后，用E(AFFP)表示模式圖對應的影響區(qū)域中邊的數(shù)目，E(AFFG)表示數(shù)據(jù)圖中增加邊周圍影響區(qū)域范圍內(nèi)邊的數(shù)目。因此，增加一條邊需要O(E(AFFP)×E(AFFG))時間來更新結(jié)果圖GT。當增加完所有的邊之后需要利用non-tree邊的性質(zhì)對更新后的結(jié)果圖GT進行剪枝，得到最終的結(jié)果圖Gr。若用V(AFFGT)表示GT中的無效的節(jié)點，E(AFFGT)表示與GT中無效節(jié)點相連的邊，則剪枝所花費的時間為O(V(AFFGT)×E(AFFGT))。

IncIsoMatch算法采用模式圖的直徑作為匹配的影響區(qū)域，因此，增加一條邊需要消耗的時間為O(E(P)×E(AFFG))，其中E(P)大于E(AFFP)。而且在子圖匹配的過程中，Inc_CFLS算法采用查詢分解策略進行剪枝，能夠推遲冗余笛卡爾積。由此可見，Inc_CFLS算法要優(yōu)于IncIsoMatch算法。

Fig.5 Pattern graph P and its corresponding result graphGr圖5 模式圖P以及相應的結(jié)果圖Gr

6 實驗與結(jié)果

下面對本文提出的Inc_CFLS算法的執(zhí)行時間進行評估。對Inc_CFLS算法和基于快照的VF2算法[8]以及IncIsoMatch算法進行評估，其中IncIsoMatch算法采用模式圖的直徑作為匹配的影響區(qū)域，并在影響區(qū)域內(nèi)用VF2算法進行子圖匹配，比較和分析3種算法的執(zhí)行時間。由于算法的執(zhí)行時間和數(shù)據(jù)圖規(guī)模、模式圖規(guī)模以及增加邊的數(shù)目有關(guān)，因此考察了數(shù)據(jù)圖規(guī)模、模式圖規(guī)模及增加邊數(shù)目發(fā)生變化時對Inc_CFLS算法執(zhí)行時間的影響。

實驗使用一臺PC設(shè)備，配有Linux 64位操作系統(tǒng)，32 GB內(nèi)存，主頻3.50 GHz，所有編程用C++語言實現(xiàn)。實驗采用兩個真實的蛋白質(zhì)交互網(wǎng)絡(luò)數(shù)據(jù)集HPRD和Human，其中HPRD數(shù)據(jù)集有37 081條邊、9 460個節(jié)點。Human數(shù)據(jù)集有86 282條邊、4 674個節(jié)點，且Human數(shù)據(jù)集的節(jié)點的平均度是HPRD的4.7倍。模式圖采用從數(shù)據(jù)圖中提取的連通子圖。通過10次圖模式匹配實驗，取平均結(jié)果作為最終結(jié)果。

6.1 模式圖規(guī)模對Inc_CFLS算法執(zhí)行時間影響

從HPRD選擇35 081條邊作為初始數(shù)據(jù)圖，1 000條邊作為增加的邊集加入到初始數(shù)據(jù)圖中。從Human中選取和HPRD相同規(guī)模的邊作為初始數(shù)據(jù)圖，1 000條邊作為增加的邊集加入到數(shù)據(jù)圖中。為了考察模式圖規(guī)模對算法執(zhí)行時間的影響，使用3種不同規(guī)模的模式圖進行實驗，分別包括25、50和100個節(jié)點。實驗結(jié)果如圖6所示：基于快照的VF2算法執(zhí)行時間最長，是其他兩種增量算法執(zhí)行時間的10～100倍。當模式圖規(guī)模相同時，Inc_CFLS算法比IncIsoMatch算法執(zhí)行時間更短，且這種差距會隨著模式圖規(guī)模的增大而變顯著。在Human數(shù)據(jù)集上IncIsoMatch算法的執(zhí)行時間明顯增加。上述兩種實驗現(xiàn)象的原因是IncIsoMatch算法把增加邊周圍模式圖直徑范圍內(nèi)的區(qū)域作為待匹配區(qū)域，當模式圖規(guī)模變大或者數(shù)據(jù)圖密度增加時，IncIsoMatch算法的效率會變差。而Inc_CFLS算法可以迅速地確認受影響區(qū)域，將大量無效的中間結(jié)果剪枝，因此效率更高。

Fig.6 Execution time of different algorithms by varying sizes of pattern graphs圖6 不同規(guī)模模式圖的算法執(zhí)行時間

6.2 數(shù)據(jù)圖規(guī)模對Inc_CFLS算法執(zhí)行時間影響

為了考察數(shù)據(jù)圖規(guī)模對算法執(zhí)行時間的影響，分別從HPRD選擇13 624、24 793、35 081條邊作為初始的數(shù)據(jù)圖，1 000條邊作為增加的邊集加入到初始的數(shù)據(jù)圖中。Human的選擇方式與HPRD相同。選取50個節(jié)點作為模式圖，實驗結(jié)果如圖7所示：Inc_CFLS算法的效率要明顯優(yōu)于另外兩種算法，當數(shù)據(jù)圖規(guī)模變大時，Inc_CFLS算法和IncIsoMatch算法的執(zhí)行時間增加，因為數(shù)據(jù)圖規(guī)模越大，匹配的候選集也就越多，匹配所花費的時間則會相應增加。對于Human數(shù)據(jù)集，Inc_CFLS算法的優(yōu)勢更加明顯，原因是當數(shù)據(jù)圖規(guī)模變大時，會導致數(shù)據(jù)圖的密度也相應增加，IncIsoMatch算法的效率則會降低。

Fig.7 Execution time of different algorithms by varying sizes of data graphs圖7 不同規(guī)模數(shù)據(jù)圖的算法執(zhí)行時間

6.3 增加邊的數(shù)目對Inc_CFLS算法執(zhí)行時間影響

為了考察增加邊的數(shù)目對算法執(zhí)行時間的影響，從HPRD選擇35 081條邊作為初始的數(shù)據(jù)圖，分別選擇500、1 000、1 500、2 000條邊作為增加的邊集加到初始數(shù)據(jù)圖中。Human的選擇方式與HPRD相同。選擇50個節(jié)點作為模式圖，當數(shù)據(jù)圖增加邊的數(shù)目較多時，使用VF2算法無法進行處理，因此本部分僅對Inc_CFLS算法以及IncIsoMatch算法進行評估。結(jié)果如圖8所示：隨著邊的數(shù)目增加，算法的執(zhí)行時間也會增加，且IncIsoMatch算法的執(zhí)行時間是Inc_CFLS算法的1～2倍。這是因為每增加一條邊，IncIsoMatch算法都會把增加邊周圍模式圖直徑范圍內(nèi)的區(qū)域作為匹配區(qū)域，而Inc_CFLS算法能把影響區(qū)域進一步縮小，所以隨著邊的數(shù)目增加，Inc_CFLS算法效率提升顯著。

Fig.8 Execution time of algorithms by varying the number of inserted edges圖8 改變增加邊數(shù)目時的算法執(zhí)行時間

7 結(jié)束語

本文提出了一種基于結(jié)構(gòu)分解的增量圖模式匹配算法Inc_CFLS。該算法不僅能夠在模式圖匹配的過程中更高效地計算出當前的匹配結(jié)果，而且利用增量計算的思想充分利用之前匹配的候選集來降低后續(xù)模式匹配中的重復計算。設(shè)計實現(xiàn)了面向增邊的子算法AddEdges用于增量圖模式匹配。選取真實數(shù)據(jù)集進行實驗，結(jié)果表明Inc_CFLS算法比目前最好的增量匹配算法在執(zhí)行效率上平均提升了1～2倍。同時隨著數(shù)據(jù)圖或模式圖規(guī)模的增大，Inc_CFLS算法比目前最好的增量匹配算法在執(zhí)行時間上的優(yōu)勢會越發(fā)顯著，展示了處理大圖數(shù)據(jù)的良好可擴展性。