基于鄰域安全壓縮的動態圖增量子圖匹配算法

徐周波 許昌勝 王嘉鑫

摘 要：針對目前最先進的增量子圖匹配算法Symbi中的索引結構DCS中存在的信息冗余問題，提出了一種新的索引結構CDCS（compressed dynamic candidate space），并提出了CDCS的更新算法INCCDCS來動態維護CDCS索引結構和匹配結果，最后提出了動態圖的增量子圖匹配算法CSymbi。該方法通過引入鄰域信息約束，在構建和更新輔助結構的過程中過濾候選集，提高算法的求解效率。最后，在Netflow和LSBench數據集上進行驗證，相較于現有方法，候選節點數量最高可以刪減56%，候選邊數量最高可以刪減62%，有效縮減了計算空間并提高了算法的求解效率。

關鍵詞：動態圖； 增量子圖匹配； 鄰域約束； CSymbi

中圖分類號：TP391.4?? 文獻標志碼：A?? 文章編號：1001-3695（2023）12-023-3672-06

doi：10.19734/j.issn.1001-3695.2023.04.0176

Incremental subgraph matching algorithm based on neighborhood safe compression on dynamic graph

Abstract：Aiming at the problem of information redundancy in the index structure DCS in Symbi， the most advanced incremental subgraph matching algorithm， this paper proposed a new index structure CDCS， and proposed the CDCS update algorithm INCCDCS to the CDCS index structure and dynamically maintained matching results， and finally proposed an incremental subgraph matching algorithm CSymbi for dynamic graphs. By introducing neighborhood information constraints， the method filtered candidate sets during the process of constructing and updating auxiliary structures， and improved the solution efficiency of the algorithm. Finally， it was verified on the Netflow dataset and LSBench dataset. Compared with the existing methods， the number of candidate nodes can be reduced by up to 56%， and the number of candidate edges can be reduced by up to 62%， which effectively reduces the calculation space and improves the solution efficiency.

Key words：dynamic graph; incremental subgraph matching; neighborhood constraint; CSymbi

0 引言

子圖匹配是圖數據分析中一種基本操作，被廣泛應用于社交網絡［1，2］、網絡安全［3，4］、醫學蛋白質等領域［5］。子圖匹配是指在數據圖中查詢所有與查詢圖同構的子圖。但在現實世界中，圖數據的結構和內容往往會隨著時間的推移而發生變化。以社交網絡為例，根據Facebook網站2010年的年鑒報告，僅2010年一年期間，用戶從3.37億人增加到5.85億人，平均每分鐘都有47 553對好友之間建立或者解除關系。2011年，Google+在上線后的兩周時間增長了1 000萬的用戶［6］。這些數據表明，現實世界中的實體對象和他們之間的關系無時無刻都可能經歷著變化。因此，研究動態圖上的子圖匹配問題具有重要的理論意義和應用價值。

增量子圖匹配技術是目前動態圖數據匹配的主流技術，其僅對動態圖數據更新的部分進行分析和匹配，即給定初始圖g0、查詢圖q和由邊插入和刪除（Δo1，Δo2，…）構成的圖更新流Δg，增量子圖匹配技術針對每個更新操作Δoi給出所產生的正向和負向匹配結果。現有的增量子圖匹配技術主要分為兩種：一種是不使用索引技術，在數據圖更新后為每個受影響的子圖執行子圖匹配算法；另一種方法則是采用索引—過濾—驗證策略，利用索引技術對不包含q作為子圖特征的數據圖進行過濾，然后在驗證階段為每個候選子圖執行子圖同構算法。索引技術可以有效減少計算中涉及的數據圖中節點的數量，是現階段主流的研究方向之一。

IncIsoMat［7］是最早提出的增量子圖匹配算法，其首先以更新邊為中心查找該邊端點周圍所有k跳范圍內的節點，其中k為模式圖的直徑；然后計算各節點的導出子圖，并分別與模式圖進行子圖匹配；最后查找出與原匹配結果有差異的匹配。此方法雖無須構建索引和維護原有匹配查詢結果，但因需對k跳范圍內的各節點的導出子圖計算子圖匹配，致使查詢效率低下。Graphflow［8］使用最壞情況最優連接算法來增量評估每次更新的子圖匹配［9，10］。其首先從匹配更新邊（ν，ν′）的每個查詢邊（u，u′）開始，解決從部分嵌入開始的子圖匹配并遞增地連接查詢圖中的其他邊，直到它獲得查詢圖的完整嵌入集合。此方法在每次更新后都需要重新執行子圖匹配，查詢效率低下。上述算法需要為每個更新操作執行子圖匹配，但子圖匹配是一個NP完全問題，因此在匹配上會產生顯著的開銷。為提高動態子圖匹配算法的效率，研究者們引入索引—過濾—驗證策略，通過優化匹配順序，或通過引入輔助數據結構構建索引來過濾不可行的解。文獻［11］提出了INC_CFLS算法，它利用分解策略對查詢圖進行分解，將查詢圖按照節點度的大小分解成核心、森林和葉子三個部分。當增加一條邊時首先確認模式圖的影響區域，然后采用從核心到森林，最后到葉子的匹配順序，依次約減無效的中間結果。基于該順序進行匹配可將笛卡爾積操作拖延到葉子節點進行，有效減少冗余笛卡爾積的產生，從而進一步約減查詢候選集。然而，該算法僅考慮了更新節點對受影響區域的影響，沒有考慮更新節點的鄰居節點對受影響區域的影響。文獻［12］引入了判斷更新節點的鄰居節點作為影響因素條件，進一步縮減匹配候選集和影響區域。SJTree［3］通過構建左深度連接樹索引來提高算法的執行效率。它將查詢圖q遞歸地分解為多個只含一條邊的子圖，每個子圖視為一個節點，并記錄各節點的兄弟和父親，同時維護一個哈希表存放該節點的匹配結果。當數據圖發生變化時，從左深度連接樹的葉子節點開始向上搜索來獲取新的匹配結果，但是SJTree需要為模式圖的每條邊存儲部分匹配結果，致使空間復雜度為指數級。為了降低算法的空間復雜度，TurboFlux［13］借鑒了Turboiso［14］的思想，通過構建數據中心圖（datacentric graph，DCG）來壓縮存儲空間，提高算法的執行效率。它首先通過刪除循環邊將查詢圖q轉換成生成樹qt，然后通過維護一個哈希表為qt中每一條邊存放該邊的匹配結果，并通過維護一個數組來記錄兩條邊之間的嵌入關系。對于每次圖更新操作，通過判斷更新邊是否存在組成查詢圖的嵌入來獲取新的匹配結果。TurboFlux相比于SJTree，其存儲空間明顯減少，但在剪枝時未考慮到非樹邊，導致候選集存在較多冗余。Symbi算法［15］通過將查詢圖q轉換成有向無環圖來解決TurboFlux中沒有考慮非樹邊的問題。它首先通過廣度優先搜索算法將查詢圖q轉換成有向無環圖Q，與TurboFlux類似，通過名為動態候選空間的輔助索引結構來維護候選節點集和候選邊集。有向無環圖比生成樹具有更好的修剪能力，相比于TurboFlux，過濾效果更好。在靜態圖匹配中，文獻［16］提出了一種新的子圖搜索算法VEQS。它也將查詢圖q轉換成有向無環圖，并將查詢圖中度為1的節點與其有相同標簽的鄰居節點相合并，最后基于有向無環圖和過濾函數構建緊湊的輔助索引結構，其中過濾函數利用了鄰域安全的概念，考慮了節點的鄰居標簽數量約束。雖然考慮了標簽數量約束對候選集的過濾具有良好的效果，但相比于完整的鄰域信息約束仍過于簡單。

在Symbi算法中，基于有向無環圖構建的索引結構能夠更好地過濾候選對象，但并未考慮利用候選節點的鄰域信息來進一步篩減節點以及邊的候選集，導致候選集中存在大量無用結果，影響算法的搜索效率。鑒于此，本文將鄰域約束應用到SymBi的DCS結構中，給出了更加緊湊的輔助索引結構CDCS，并提出了一種新的增量子圖匹配的算法CSymbi。通過在一些公開數據集的實驗分析表明，本文算法與SymBi算法相比能夠有效減少輔助結構DCS上的候選節點和邊集，同時因候選集的縮減，本文算法的執行效率也有明顯提升。

1 相關定義

本文針對無向連通的節點屬性圖進行研究。本文算法也可以很容易地擴展到在頂點或邊上有多個標簽的有向圖。

定義1 圖。圖被定為g=（Vg，Eg，lg），其中Vg為圖g的節點集，Eg為圖g的邊集，lg：Vg→Σ是標簽函數，其中Σ是節點標簽集。

定義2 子圖同構。給定目標g=（Vg，Eg，lg）和查詢圖q=（Vq，Eq，lq），如果存在單射函數f：Vq→Vg，滿足：a）u∈Vq，存在f（u）∈Vg，使得lq（u）=lg（f（u））;b）u，v∈Vq，若u≠v，則f（u）≠f（v）;c）（u，v）∈Eq，存在（f（u），f（v））∈Eg。則稱g的子圖sub（g）和q是子圖同構的，并稱sub（g）為圖q的一個嵌入，表示為節點對（u， f（u））的集合。

例1 如圖1所示的查詢圖q和數據圖g0，其中Δo1和Δo2分別表示兩條插入邊的操作。在數據圖g0中不存在與查詢圖q同構的子圖，執行插入操作Δo1后數據圖更新為g1，在數據圖g1中存在2個與查詢圖q同構的子圖，即{（u1，v1），（u2，v2），（u3，v3）， （u4，v4），（u5，v5）}和{（u1，v1），（u2，v2），（u3，v3），（u4，v4），（u5，v6）}。

定義3 弱嵌入［15］。給定根節點u的有向無環圖Q=（VQ，EQ，lQ）和數據圖g=（Vg，Eg，lg），v∈V（g），設圖gv=（Vs，Es，lg）為圖g的包含節點v的節點集Vs的導出子圖，若存在單射函數M′：VQ→Vs，使得M′（u）=v，且在單射函數M′下，Q的路徑樹與gv同構，則稱M′為Q在g中v上的弱嵌入。

例2 圖1中的g0在Δo1插入后更新為g1，查詢圖q的有向無環圖Q如圖2所示。{（u3，v3），（u4，v4），（u5，v5）}是Qu3在g1中v3上的弱嵌入， 其中Qu3是Q中根節點u3的子圖。

定義4 圖更新流Δg。圖更新流Δg是指由一系列更新操作（Δo1，Δo2，…）組成的串。每個更新操作Δoi表示為三元組（op，v，v′），其中，op={+， -}表示更新操作的類型，“+”表示添加邊，“-”表示刪除邊，v和v′為圖g中與操作op相關的兩個節點。

定義5 增量子圖匹配［14］。給定初始數據圖g0、圖更新流Δg和查詢圖q，增量子圖匹配問題是為Δg中的每個更新操作找到所有正/負匹配。

2 動態圖增量子圖匹配算法CSymbi

本文基于鄰域約束提出了一種新的增量子圖匹配算法CSymbi，算法主要分為三個步驟：a）為了保證圖的層次性及其遍歷順序的準確性，利用BFS構建查詢圖q的有向無環圖Q；b）基于有向無環圖Q和數據圖g0，針對文獻［15］中的DCS結構存儲冗余的問題，利用鄰域信息進行優化，提出了一種新的輔助結構CDCS；c）基于CDCS提出了子圖匹配的增量更新算法INCCDCS，維護CDCS結構和匹配結果。CSymbi算法流程如算法1所示。

算法1 CSymbi

輸入：查詢圖q;數據圖g0;圖更新流Δg。

輸出：匹配結果result。

1 result←;

2 Q← BuildDAG（q）;

3 CDCS←ZipDCS（Q，g0）;

4 result←INCCDCS（CDCS，Q，g0，Δg）

5 return result

2.1 CDCS結構

輔助索引結構在增量子圖匹配中能夠有效篩選候選節點集，提高算法在匹配階段的速度。輔助索引結構的設計一般從空間和時間兩個方面考慮。在空間上，希望占用盡可能小的空間的同時還能夠包含足夠多的信息；在時間上，希望索引更新足夠快，以幫助快速檢測圖模式。Symbi算法利用有向無環圖構建DCS索引結構，并使用所有查詢邊來篩選候選節點集。在構建DCS結構時，對于Q中每條邊考慮了節點之間的標簽信息和邊上的標簽信息，使用數組結合哈希表的結構D1和D2分別存儲Q和Q-1兩個方向上的弱嵌入，其中 Q-1是將Q的所有邊反向后所得的圖，具體構建過程如例3所示。

例3 對于圖1所示的查詢圖q，通過寬度優先搜索算法轉換成如圖2所示的有向無環圖Q。然后根據Q中節點的標簽信息篩選候選集，例如u2的標簽為A，在數據圖中v2、v5、v6和v7與其具有相同的標簽A，因此，C（u2）={v2，v5，v6，v7}。在Q中，如果存在ua到ub的邊，同時在數據圖中存在va∈C（ua）到vb∈C（ub）的邊，則將這條邊添加到DCS結構中。例如邊（u1，u2）∈Q在DCS中需要存儲（v1，v2）和（v2，v1）兩條邊。因為u2滿足Q－1u2的弱嵌入，所以D1［u2］［v2］=1。但是因為D2［u4］［v4］=0，v2不滿足Q u2的弱嵌入，所以D2［u2］［v2］=0。最終得到如圖3所示的初始DCS輔助結構。

Symbi算法在構建DCS結構時，對于Q中每條邊的候選集，僅考慮了節點之間的標簽信息和邊上的標簽信息，忽略了節點的鄰域信息，導致DCS結構中存在冗余節點和冗余邊。特別是在無向圖中，這些不滿足鄰域約束，無法成為匹配結果的邊會在DCS中存儲2次。冗余結果既加大了輔助結構的存儲空間，又擴大了匹配階段的搜索空間，從而降低了算法的求解效率。為此，本文考慮到鄰域約束對輔助結構的影響，在構建和更新輔助結構的過程中過濾候選集，優化輔助結構的存儲空間，提出了CDCS結構。具體地，對于滿足標簽匹配條件的候選集節點v∈C（u），獲取Q中節點u的所有父親節點，構成集合up。對于任一父親節點upi∈up，如果它的候選節點vpi∈C（upi）與v在數據圖存在連接關系，判斷vpi是否滿足查詢圖Q-1upi的弱嵌入條件，如果vpi不滿足，從DCS中刪除（vpi，v）。

CDCS結構包括給定查詢圖q的有向無環圖Q和數據圖g0，CDCS由以下部分組成：

a）針對u∈V（q），候選集C（u）是一組滿足lq（u）=lg（v）的頂點集合，其中v∈V（g0）。

b）對于任意u∈V（q）和v∈C（u），如果在節點v處存在Q－1u的弱嵌入，D1［u，v］=1；否則D1［u，v］=0。

c）對于任意u∈V（q）和v∈C（u），如果在節點v處存在Qu的弱嵌入M′，并且對于M′中的每個映射（u′，v′）都滿足D1［u′，v′］=1，則D2［u，v］=1；否則D2［u，v］=0。

d）當（u，u′）∈E（q），（v，v′）∈E（g），且滿足D1［u，v］=1、D1［u′，v′］=1時，則在〈u，v〉和〈u′，v′〉之間存在一條邊（〈u，v〉，〈u′，v′〉）。

CDCS的構建如算法2所示。算法2中，第1行表示構建基于Q的DCS輔助結構；第2～6行為獲取存儲在DCS中的候選集，其中getCandid函數用于獲取節點up到節點u的候選集；第5、6行為判斷節點v的父親節點vp是否滿足Q－1up弱嵌入條件，Remove函數對于不滿足的邊從DCS中移除；第7行返回輔助索引結構CDCS。

算法2 ZipDCS

輸入：有向無環圖Q;數據圖g0。

輸出：輔助結構CDCS。

1 DCS←BuildDCS（g0，Q）;

2 for each u in Q.NumVertices

3? ?for each up in u.Parents

4??? ?for each ［vp，v］ in getCandid（DCS，up，u）

5????? ?if D1［up， vp］=0 then

6???????? CDCS←remove（DCS，vp，v）;

7 return CDCS

例4 D1［u］［v］=0表示節點v不滿足Q－1u的弱嵌入關系，所以將把v作為起始節點或者終節點的特征邊從DCS結構中刪除。例如邊（v7，v3），因為v7不滿足Q－1u2的弱嵌入，D1［u2］［v7］=0，所以（v7，v3）這條邊被刪除，同時（v3，v7）也會被刪除。圖3中所有不滿足鄰域約束的邊用紅色標注（見電子版），將所有不滿足約束條件的邊刪除后，結果如圖4所示。

從圖3和4的對比可以看出，經過壓縮后，相比于DCS結構，CDCS結構所包含的邊集數量減少了50%。這是因為CDCS結構在構建過程中將鄰域約束加入到了輔助結構的構建過程中，減少不符合匹配條件的候選集，從而達到了壓縮邊集的目的。相比之下，DCS結構只考慮了節點之間的標簽信息和邊上的標簽信息，沒有考慮鄰域信息，導致結構中存在大量冗余邊，浪費了存儲空間。

2.2 CDCS更新

當數據圖中的邊發生更新時，CDCS中將插入或刪除一組邊，下面分別對插入邊和刪除邊的更新操作進行介紹。

a）邊插入。DCS針對插入邊e（vp，v），如果D1［up］［vp］=0，則邊e（vp，v）的插入不影響D1及其后代的更新，因此不會產生新的匹配結果，停止更新并移動到下一條邊的判斷；如果D1［up］［vp］=1，則（u，v）及其后代的D1可能因為e（vp，v）的插入發生改變而產生新的匹配結果。首先更新（u，v）及其后代的D1信息，如果D1［u］［v］=1，將e（vp，v）插入到CDCS結構中（針對無向圖），然后繼續向下判斷后代節點，直至D1不滿足為1終止。針對邊插入的CDCS結構的更新操作如算法3所示。

算法3的DCS第1行為初始化隊列;第2行獲取更新邊；第3行InsertToDataGraph函數更新數據圖；第4行將邊的起始節點添加到隊列中；第5～13行依次從隊列中取出節點，遞歸更新D1；其中第8行getChild函數獲取（u，v）的孩子節點集（uc_candid，vc_candid）；第9行遍歷節點集，依次更新節點（uc，vc）∈（uc_candid，vc_candid）的D1；第12行CDCSInsertUpdate函數獲取uc的父親節點up∈Q，針對up的候選集，如果D1［up］［vp］=1且（vp，v）∈Eg，則將（vp，v）和（v，vp）存儲到CDCS中；第14行UpdateD2函數更新D2；第15行UpdateMathches函數根據已更新的D1和D2尋找新的匹配，并更新匹配結果；第16行返回匹配結果result。

算法3 CDCSInsert

輸入：輔助結構CDCS;有向無環圖Q;數據圖g;圖更新操作Δo。

輸出：匹配結果result。

1 queue←;

2 e（v，vc）←（Δo.v，Δo.vc）;

3 InsertToDataGraph（g，e）;

4 queue.add（［u，v］）;

5 while （！queue.isEmpty（））

6 ［u，v］←queue.pop（）;

7 if （D1［u］［v］==1）then

8?? （uc_candid，vc_candid）←getChild（（u，v））;

9?? for each（uc，vc）∈（uc_candid，vc_candid）

10??? update D1（uc，vc）;

11??? if （D1［uc］［vc］==1） then

12???? CDCSInsertUpdate（CDCS，Q，v，vc）;

13???? queue.add（［uc，vc］）;

14 update D2（u，uc，v，vc）;

15 result←UpdateMathches（e）;

16 return result

b）邊刪除。DCS針對刪除邊e（vp，v），首先更新匹配結果，然后將其從數據圖和CDCS結構中刪除。接著更新（u，v）及其后代的D1信息。如果某些節點 D1由1變為0，同時指向該節點的邊存在于CDCS中，將其從CDCS中移除。針對邊刪除的CDCS結構的更新操作如算法4所示。

算法4 CDCSDelete

輸入：輔助結構CDCS;有向無環圖Q;數據圖g;圖更新操作Δo。

輸出：匹配結果result。

1 queue←;

2 e（v，vc）←（Δo.v，Δo.vc）;

3 result←UpdateMathches（e）;

4 DeleteFromDataGraph（g，e）;

5 queue.add（［uc，vc］）;

6 while （！queue.isEmpty（））

7 ［u，v］←queue.pop（）;

8 CDCSDelUpdate（CDCS，Q，v，vc）;

9 （uc_candid，vc_candid）←getChild（（u，v））;

10 for each （uc，vc）∈（uc_candid，vc_candid）

11? update D1（uc，vc）;

12? if （D1［uc］［vc］==0） then

13??? queue.add（［uc，vc］）;

14 update D2（u，uc，v，vc）;

15 return result

例5 圖5（a）（b）分別是圖1（b）中Δo1和Δo2更新后的結果。Δo1={+，v3，v4}插入數據圖g0后，首先從隊列中獲取節點對（u3，v3）。因D1［u3］［v3］=1，重新計算（u3，v3）的孩子節點（u4，v4），（u5，v5），（u5，v6），（u5，v7）的D1。因為u4的每一個父親節點都有一個與v4相鄰的候選集，其D1的值為1，所以D1［u4］［v4］由0變為1，將（u4，v4）存儲到隊列中，然后獲取u4在Q中的父親節點u2和u3。因D1［u2］［v2］=1和D1［u3］［v3］=1，所以將（v2，v4），（v4，v2），（v3，v4）和（v4，v3）插入到CDCS中。繼續從隊列中獲取（u4，v4），因為該節點無孩子節點且隊列為空，更新結束。D1更新結束后繼續更新D2，因D1［u4］［v4］=1，且滿足Qu4的弱嵌入，所以D2［u4］［v4］=1，繼續向上更新，最終得到{（u1，v1），（u2，v2），（u3，v3），（u4，v4），（u1，v1），（u5，v5）}和{（u1，v1）， （u2，v2），（u3，v3），（u4，v4），（u1，v1），（u5，v6）}兩個匹配結果。同理當Δo2={+，v1，v7}插入時，CDCS結構如圖5（b）所示。

基于此，CDCS結構的更新算法INCCDCS如算法5所示。以輔助結構CDCS，有向無環圖Q，數據圖g0和圖更新流Δg為輸入，更新CDCS并返回匹配結果。

算法5 INCCDCS

輸入：輔助結構CDCS;有向無環圖Q;數據圖g;圖更新流 Δg。

輸出：匹配結果result。

1 result←;

2 for each Δo∈Δg

3 ?if （Δo.op=+） then

4?? result←CDCSInsert（CDCS，Q，g，Δo）;

5 ?if （Δo.op=-） then

6?? result←CDCSDelete（CDCS，Q，g，Δo）;

7 return result

3 實驗

為證明本文算法CSymbi的有效性，使用公開數據集Netflow和LSBench數據集與Symbi算法進行實驗對比，其中Symbi源碼從文獻［17］中獲取。實驗是在一臺Corei56500@3.2 GHz、16 GB內存的機器上進行的，源碼使用C語言進行編寫，運行在 CentOS Linux操作系統上。

LSBench是由鏈接流基準數據生成器生成的合成RDF社交媒體流數據，包含23 317 563個三元組。Netflow是一個真實的數據集，包含從CAIDA獲得的匿名被動流量追蹤，約包含18 520 759個三元組。考慮到內存限制，從數據集中選取0.1的三元組，約2 000 000的三元組作為實驗數據。默認情況下將數據集的90%三元組分成初始圖，10%分成圖更新流。查詢圖參照文獻［13，15］，通過從數據圖中隨機提取子圖來生成查詢圖。其中查詢圖的類型分為樹型圖T和循環圖G兩種。對于每種類型，將查詢圖的節點數量以3的增量從6增長到12，例如T6表示樹型圖節點數量為6，G12表示循環圖節點數量為12。為每種大小和類型的查詢圖生成了100個實例作為一個查詢集。實驗過程中將本文的CSymbi和Symbi算法進行對比，將輔助結構包含的候選集大小、更新過程中的平均運行時間、程序的平均峰值內存使用情況以及解決的查詢圖數量作為算法之間的衡量標準，其中峰值內存定義為實際程序輸出中虛擬集大小的最大值。

首先，在Netflow數據集上對比每次更新操作中DCS和CDCS包含的平均節點數和平均邊數。實驗數據是在數據圖不變的情況下，不同類型和大小的查詢圖q的100個實例運行的平均結果。按照模式圖的規模將實驗分成了六組，實驗結果如表1所示。其中DCS|V|表示DCS中包含的平均節點數量，DCS|E|表示DCS中包含的平均邊的數量，CDCS類似。而R|V|和R|E|分別表示相比于DCS，CDCS中節點數量和邊數量減少的比例。從表1中可以看出，CSymbi算法的候選集大小始終小于Symbi算法，從縮減比例中可以看出，相比于原算法，本文算法對候選節點的過濾最高可以達到56%，對候選邊集的過濾最高可以達到54%。同樣在LSBench中進行相同的實驗，實驗結果如表2所示，其中節點數量最多降低49%，而邊集數量則可以降低62%。從實驗結果可見，加入鄰域約束對輔助結構中候選集的過濾有明顯優勢。

其次，分別在Netflow和LSBench上對比了本文算法與Symbi在插入邊時算法的平均耗時。實驗過程中插入率為10%，實驗結果如圖6（a）和（b）所示。從實驗結果可以看出，在兩個數據集的六組實驗上，CSymbi算法的平均耗時均優于Symbi算法。這是因為候選集數量的減少將會縮減算法在匹配階段的搜索空間，能夠提高算法在匹配階段的求解效率。在實驗過程中，發現在個別的查詢實例下，CSymbi比Symbi慢，主要原因是Symbi在初始化DCS結構時會將所有標簽匹配的節點和邊使用哈希表進行存儲，在數據圖發生變化時，通過DCS查找候選集;但CSymbi刪除了不滿足鄰域約束的邊集和節點，在后續更新中需要從原數據圖中查找可能滿足匹配的新節點和邊，所以在某些實例中速度較慢。但從整體實驗的平均結果中可以看出，CSymbi始終優于Symbi。

然后，為了驗證算法在運行過程中實際所占用的內存大小，將兩個算法在運行過程中所占的峰值內存大小進行了實驗對比。圖7（a）和（b）顯示了在Netflow和LSBench上執行增量子圖匹配的平均峰值內存。從實驗結果可以看出，在不同查詢圖規模下，CSymbi使用的內存都明顯少于SymBi。原因是CSymbi算法中各候選集在CDCS輔助結構中存儲，不論是節點集還是邊集，相較于Symbi都有明顯減少。

進一步，在相同的實驗環境下對比了執行刪除操作時兩個算法的平均查詢時間和平均峰值內存。刪除率設置為10%。實驗結果如圖8和9所示。在執行刪除操作時，Symbi和CSymbi算法在刪除邊時同樣會將要刪除的邊從輔助結構中移除，但是CSymbi在更新受影響節點的D1時會判斷值是否由1變為0，如果變為0，會將其從候選集中移除，因此在內存上同樣優于Symbi算法。

最后對比了Turboflux、Symbi和CSymbi算法在解決查詢圖數量上的性能差異。本文將算法的運行時間設置為1 h，統計不同算法在規定時間內所能解決的查詢圖數量，實驗結果如圖10所示。從圖中可以看出，Turboflux算法在規定時間有較多查詢不能解決，而Symbi和CSymbi算法能夠解決大部分的查詢，但隨著查詢圖規模的增大，Symbi算法在個別查詢圖上無法得出結果。主要原因在于部分查詢圖的候選集數量過于龐大，在執行更新操作時，搜索速度過慢，導致算法的求解效率降低，無法在規定時間內得到結果。

4 結束語

為了進一步壓縮增量子圖匹配問題的求解空間，本文提出了一種基于鄰域約束的增量子圖匹配算法CSymbi。該算法考慮節點周圍的鄰居約束關系，對輔助索引結構DCS的候選集作進一步篩選，壓縮輔助結構的存儲空間，提出了CDCS索引結構，同時提出輔助索引結構CDCS的更新算法，對CDCS及其匹配結果進行更新。實驗結果表明，該算法與Symbi算法相比較，有效地壓縮了輔助索引結構的存儲空間，同時因為候選集的減少，更新過程明顯加快。在未來的工作中，將研究輔助索引結構的符號壓縮技術，并結合增量算法對其進行求解。

參考文獻：

[1]于靜，劉燕兵，張宇，等.大規模圖數據匹配技術綜述［J］.計算機研究與發展，2015，52（2）：391-409.（Yu Jing， Liu Yanbing， Zhang Yu， et al. A survey of largescale graph data matching technology［J］.Computer Research and Development，2015，52（2）：391-409.）

［2]Zou Lei， Chen Lei， zsu M T. Distancejoin：pattern match query in a large graph database［J］.Proceedings of the VLDB Endowment，2009，2（1）：886-897.

［3]Choudhury S， Holder L， Chin G， et al. A selectivity based approach to continuous pattern detection in streaming graphs［J］.Computer Science，2015，93（8）：939-945.

［4]Gao Jun， Zhou Chang， Yu J X. Toward continuous pattern detection over evolving large graph with snapshot isolation［J］.The VLDB Journal，2016，25：269-290.

［5]He Huahai， Singh A K. Query language and access methods for graph databases［M］//Managing and Mining Graph Data.2010：125-160.

［6]許嘉，張千楨，趙翔，等.動態圖模式匹配技術綜述［J］.軟件學報，2018，29（3）：663-688.（Xu Jia， Zhang Qianzhen， Zhao Xiang， et al. A survey of dynamic graph pattern matching technology［J］.Journal of Software，2018，29（3）：663-688.）

［7]Fan Wenfei， Wang Xin， Wu Yinghui. Incremental graph pattern matching［J］.ACM Trans on Database Systems，2013，38（3）：1-47.

［8]Kankanamge C， Sahu S， Mhedbhi A， et al. Graphflow： an active graph database［C］//Proc of the 44th ACM International Conference on Management of Data.New York：ACM Press，2017：1695-1698.

［9]Mhedhbi A， Salihoglu S. Optimizing subgraph queries by combining binary and worstcase optimal joins［J］.Proceedings of the VLDB Endowment，2019，12（11）：1692-1704.

［10]Ngo H Q， Ré C， Rudra A. Skew strikes back： new developments in the theory of join algorithms［J］.ACM SIGMOD Record，2014，42（4）：5-16.

［11]許嘉，張千楨，趙翔，等.基于結構分解的動態圖增量匹配算法［J］.計算機科學與探索，2018，12（8）：1214-1224.（Xu Jia， Zhang Qianzhen， Zhao Xiang， et al. Dynamic graph incremental matching algorithm based on structural decomposition［J］.Computer Science and Exploration，2018，12（8）：1214-1224.）

［12]張芳.基于增量的動態圖匹配算法研究［D］.秦皇島：燕山大學，2021.（Zhang Fang. Research on dynamic graph matching algorithm based on increment［D］.Qinhuangdao：Yanshan University，2021.）

［13]Kim K， Seo I， Han W S， et al. TurboFlux： a fast continuous subgraph matching system for streaming graph data［C］//Proc of the 6th International Conference on Management of Data.New York：ACM Press，2018：411-426.

［14]Han W S， Lee J， Lee J H. TurboISO： towards ultrafast and robust subgraph isomorphism search in large graph databases［C］//Proc of ACM SIGMOD International Conference on Management.New York：ACM Press，2013：337-348.

［15]Min S， Park S G， Park K， et al. Symmetric continuous subgraph matching with bidirectional dynamic programming［J］.Proceedings of the VLDB Endowment，2021，14（8）：1298-1310.

［16]Kim H， Choi Y， Park K， et al. Versatile equivalences：speeding up subgraph query processing and subgraph matching［C］//Proc of the 4th International Conference on Management of Data.New York：ACM Press，2021：925-937.

［17]Sun Xibo， Sun Shixuan， Luo Qiong， et al. An indepth study of continuous subgraph matching［J］.Proceedings of the VLDB Endowment，2022，15（7）：1403-141.