基于結構分解的動態圖增量匹配算法*

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

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

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

3.廣西多媒體通信與網絡技術重點實驗室，南寧 530004

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

1 引言

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

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

本文設計與實現了面向動態數據圖的增量圖模式匹配算法，主要貢獻如下：

（1）提出了一種基于圖結構分解的動態圖增量匹配算法框架，通過記錄中間結果并構建匹配所需的索引，加速后續圖模式匹配的執行效率。

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

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

2 相關工作

2.1 圖模式匹配

子圖模式匹配通常采用基于回溯的方法或基于探索的方法實現。基于回溯的方法首先根據節點的標簽為模式圖的每一個節點生成一個匹配候選集，然后根據一個匹配順序來連接這些候選的匹配點，得到最終匹配結果。該方法中匹配順序直接影響子圖匹配效率[4-5]。基于探索的方法是從數據圖的一個節點出發，根據模式圖指定的節點之間的關系對數據圖進行探索式匹配，即檢測訪問的數據圖節點是否滿足模式圖的匹配要求[6-7]。

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

2.2 增量圖模式匹配

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

上述面向單機環境的增量算法只能有效處理規模較小的模式圖，當模式圖增大時算法效率將顯著降低。本文提出一種基于結構分解的精確子圖匹配算法，利用增量計算的思想基于之前的匹配結果進一步約減數據圖動態變化時的受影響區域，從而有效提升算法匹配規模較大的模式圖的執行效率。

3 動態圖匹配問題的形式化描述

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

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

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

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

4 基于結構分解的增量匹配算法

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

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

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

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

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

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

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

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

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

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

4.2 面向數據圖增加邊的子算法AddEdges

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法1數據圖增加邊時的處理AddEdges

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

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

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

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

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

輸出：匹配的結果圖Gr。

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

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

5 算法復雜度分析

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

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

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

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

6 實驗與結果

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

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

6.1 模式圖規模對Inc_CFLS算法執行時間影響

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

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

6.2 數據圖規模對Inc_CFLS算法執行時間影響

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

Fig.7 Execution time of different algorithms by varying sizes of data graphs圖7 不同規模數據圖的算法執行時間

6.3 增加邊的數目對Inc_CFLS算法執行時間影響

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

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

7 結束語

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