基于圖連通支配集的子圖匹配優化算法

孫云浩 韓 冰 李冠宇 邢維康 李逢雨(大連海事大學信息科學技術學院 遼寧 大連 116026)

0 引 言

模式匹配是一個子圖同構問題，給定一個查詢圖和數據圖，模式匹配是指搜索到所有同構于查詢圖的數據子圖[1]?；诠濣c的子圖匹配方法是解決模式匹配問題的一種有效方法，其以節點作為最小匹配單位，利用了SSR(State Space Representation)樹模型構建模式匹配的執行過程[2]。其中，狀態表示一個由查詢圖節點和數據圖節點組成的節點對。如果查詢圖節點和數據圖節點滿足匹配條件(查詢圖節點出度小于數據圖節點出度，查詢圖節點入度小于數據圖節點入度，查詢圖節點標簽與數據圖標簽相同等)，則將其加入SSR樹模型。當匹配成功的節點數量等價于查詢圖節點數量，則輸出一個子圖匹配的答案集。

基于節點的子圖匹配算法主要通過優化節點匹配可行性規則、匹配的執行序列和搜索空間三方面提高算法的執行時間效率。最早的算法思想是由Ullmann[4]提出，其主要通過比對查詢圖節點和數據圖節點的度的大小來過濾數據圖節點。然而，這種過濾手段是粗糙的，其過濾后的候選數據圖節點過于龐大。VF2算法[5-6]在縮減候選數據圖節點方面貢獻突出，其通過添加鄰接節點的可行性規則來縮減候選數據圖節點的規模。然而，其匹配的執行序列是隨機的，忽略了執行序列對時間效率的影響，導致處理大規模數據時，查詢時間過高。文獻[5]提出了GADDI算法，定義了鄰近辨別子結構距離(NDS)，表示兩個節點及相鄰節點結構中頻繁子圖的數量，通過約束模式圖中節點的NDS距離來過濾備選節點。文獻[6]提出的Spath算法引入更復雜的鄰接結構，提出了以節點之間的最短路徑作為匹配最小單位，定義了以節點為中心，采用層次遍歷的三元組表示方法，通過更加復雜的結構和語義信息，提高篩選候選節點的能力。VF3[2]算法是針對大規模稠密的數據圖，其通過一種動態的代價計算模型，最大程度上兼顧了匹配序列的局部和全局優化，其次，通過查詢圖的節點標簽對數據圖節點分類，從而進一步縮減搜索空間的規模。VF3利用動態代價計算模型試圖編排最優的執行序列，然而最大回溯深度仍然等價于查詢圖節點的數量，其整個匹配過程中的迭代次數沒有得到真正意義的降低。

因此，本文提出一種基于圖連通支配集的子圖匹配優化算法，其主要思想是通過查詢圖支配節點降低查詢節點在搜索過程中的迭代次數，即降低搜索空間的大小。

本文主要貢獻如下：給出查詢圖節點的最小連通支配集求解模型，構造代價模型，編排最小連通支配集匹配序列，利用支配節點的結構信息對搜索空間進行有效剪枝，通過實驗評估得出本文方法比其他同類算法具有更高的時間效率。

1 查詢圖節點重要度

1.1 節點匹配算法思想

節點匹配算法是一種回溯算法，其算法思想主要包括三個部分：(1) 利用查詢圖節點的出度(查詢圖節點的出度鄰接節點稱之為后繼節點)和入度(查詢圖節點的入度鄰接節點稱之為前驅節點)保障查詢節點匹配的連續性；(2) 通過優化策略來優化查詢圖節點的執行序列；(3) 利用有效的剪枝規則降低搜索空間的大小。

節點匹配的過程可以看作順序執行的過程，依次激活查詢圖的節點并獲取當前查詢節點在數據圖中的候選集。一個查詢節點u的候選集是指數據圖中可以與u匹配的數據節點的集合。如果查詢節點與當前所有候選數據節點匹配失敗，需要回溯到上一查詢節點，匹配上一個查詢節點其他候選節點。其搜索空間可以用樹形結構表示。樹的根節點為空，其他節點為查詢圖節點與其匹配的數據圖節點組成的節點對。如果查詢圖節點的數量為n，那么樹結構中任意一條從根節點到第n層節點的路徑中的數據圖節點可以構成查詢圖的一個答案集。

如圖1所示，圖1(a)給出一個查詢圖，其為一個帶標簽的有向圖。查詢圖Q包括10個查詢節點(u0,u1,…,u10)并標注了相應的節點標簽(A,B,…,J)。圖1(b)給出一個數據圖，其圖結構的描述與查詢圖類似。不同之處在于查詢圖規模遠遠小于數據圖規模。

(a) 查詢圖

已知在給定的查詢圖(圖1(a))中，節點個數為10，節點的匹配執行順序有10!種。例如：是查詢圖的一個匹配序列，匹配到第4層，即獲取節點u6的候選節點，匹配次數達到10×100×1×10次，以的匹配序列，匹配到第四層匹配次數為1×10+10+2次。原因是查詢圖中節點u0在數據圖中候選集個數為100(節點v11到v111)，在匹配序列中需要回溯100次，導致查詢次數增多。由此可以得出結論，節點匹配順序的不同會導致迭代次數不同，進而影響查詢效率。因此，本文重點在如何降低迭代次數以提高查詢效率。

1.2 問題定義

查詢圖和數據圖可以形式化定義為(V,E,L)，其中：V指代的是一個有限的節點集合，E是一個有向邊的集合，L指代的是節點標簽。是由vi指向vj的邊。本文形式化定義查詢圖(如圖1(a)所示)和數據圖(如圖1(b)所示)為Q(VQ,EQ,LQ)和G(VG,EG,LG)。

定義1子圖匹配。給定一個查詢圖Q(VQ,EQ,LQ)和一個數據圖G(VG,EG,LG)，子圖匹配定義為從Q和G之間的一個映射函數f:VQ→VG,滿足以下條件，稱Q和G滿足子圖匹配。

?u,v∈VQ(u,v)∈EQ→(f(u),f(v))∈EG

(1)

LQ(u)=LG(f(u))LQ(v)=LG(f(v))

(2)

式中：L(u)表示節點標簽。

定義2查詢節點匹配序列。給定查詢圖Q(VQ,EQ,LQ)，查詢圖節點匹配序列被定義為一個序列sn=，滿足?ui∈V(sn),?uj∈V(si-1)，使得uj∈adj(ui)。adj(ui)為ui的鄰接節點集合。

定義3k查詢節點匹配序列。給定一個查詢圖Q并獲得一條Q的全節點匹配序列sn=。k查詢節點匹配序列指的是全節點匹配序列sn的子序列sk=，1≤k≤n，滿足以下條件：?ui∈V(sn)-V(sk),?uj∈V(sk)，使得uj∈adj(ui)。

獲取k查詢節點匹配序列是本文要解決的第一個問題，通過獲取k查詢節點來減小N，提高查詢效率；構造代價模型選取具有較好區分度節點，優化k查詢節點匹配序列是本文要解決的第二個問題；利用節點結構特征減少節點候選集的數量是本文要解決的第三個問題。

2 基于支配節點的子圖匹配

基于圖連通支配集的子圖匹配方法主要包括三個步驟：(1) 通過貪心算法獲取查詢圖的最小連通支配子圖(NP難問題)，構造k查詢節點匹配序列；(2) 優化k查詢節點匹配序列；(3) 利用支配節點結構特征對搜索空間剪枝。

2.1 支配集及最小支配集

對于查詢節點ui，其候選節點集為C(ui)。如果節點uj為節點ui的鄰接節點，那么uj的匹配節點一定包含在C(ui)的鄰接節點中。因此，已知節點ui的匹配節點，很容易搜尋到節點uj的匹配節點，可以稱節點ui支配節點uj?；谏鲜稣撟C，本文利用節點之間的支配關系，縮小全節點匹配序列的長度，構造k查詢節點匹配序列。節點之間的支配關系是源自于支配集的概念，因此首先介紹與節點支配集[9-13]以及支配子圖的相關定義。

定義4節點支配集。給定一個查詢圖Q(VQ,EQ,LQ)，節點支配集DS?VQ滿足：?u∈(VQ-DS)，?v∈DS，使得u與v存在一條邊，那么，u是v的被支配節點，或者說v是u的支配節點。

查詢圖中除節點支配集，剩余節點集合稱為被支配集，記作NDS。圖2給出了圖1查詢圖可能存在支配節點及其被支配節點。由節點支配集定義可知，在支配集中，任意兩個支配節點之間邊的數量可能為1、2、3，即支配集中任意兩個支配節點之間邊的數量小于等于3。

(a) (b)

(c) (d)圖2 支配節點以及被支配節點舉例(陰影為支配節點)

定理1節點支配集定理。給定圖G，集合DS為G的支配集，滿足：(1)DS?VQ,(2)?u∈VG→u∈DS∨u∈adj(v)(v∈DS)。

證明：假設存在一個節點u既不屬于集合DS又不屬于集合DS中某些節點的鄰居節點，則一定會出現以下情形：存在兩個支配節點之間的邊的數量大于3，與節點支配集定義相矛盾，因此定理1成立。

由支配集節點構成的子圖稱之為支配子圖，記作QD，圖3給出圖2(c)的支配子圖。由圖2可知，給定一個查詢圖，查詢圖中可能存在多種不同的支配集，如(u0,u4,u5,u7)、(u3,u4,u6)、(u2,u3,u4,u6)、(u3,u4,u7)。在圖2給出的支配集中，由圖2(a)、(b)、(d)的支配集構成的支配子圖是非連通的。依據k查詢節點匹配序列定義，節點之間滿足連通性。要在保證連通性的前提下尋找最小支配子圖，即保證連通性條件下使得支配集中節點個數盡可能地少。文獻[8]證明：任意一個節點個數為n的圖模型，其支配子圖數目的最小值和最大值是1.570 4n和1.715 9n。而找出最小支配子圖是一個NP難問題，在已有的方法中，最快的精確查找最小支配子圖算法時間復雜度為O(1.495 7n)。文獻[9]提出一種貪心算法來找出近似最小支配集，但是在該方法得到支配集在查詢圖上是非連通的，即支配集節點之間可能不存在邊關系。綜合考慮，本文在此基礎上進行改進，提出一種基于貪心搜索近似最小連通支配子圖算法。

定理2鄰接定理。假設查詢圖Q是數據圖G中的一個子圖匹配。圖XD是支配子圖QD的一個子圖匹配(XD?G,QD?Q)。?ui∈QD,uj∈Q，∈E(Q),一定存在節點vi=f(ui),vi∈XD,vj=f(uj),vj∈G,滿足:∈E(G)。

證明：假設節點ui的匹配節點為vi，且ui存在一個被支配節點um，在節點vi的被支配節點集搜索不到節點um的匹配節點。不滿足定義1中式(1)，因此節點vi不是節點ui的匹配節點，與假設節點vi是節點ui的匹配節點相矛盾，因此定理2成立。

定理2說明如果節點ui是支配節點，vi是ui的匹配節點，um是ui的被支配節點，那么um的匹配節點屬于vi的被支配節點。

定理3k查詢節點匹配序列不失完整性。由k查詢節點匹配序列得到子圖匹配，記作G(k)，由全查詢節點匹配序列得到子圖匹配，記作G(n)。G(n)?G(k)。

證明：由k查詢節點匹配序列定義知k查詢節點匹配序列指的是全節點匹配序列s的子序列sk=,1≤k≤n，即sk?sn。因此滿足全查詢節點匹配序列的子圖匹配必然滿足k查詢節點匹配序列。

由定理3可知，由k查詢節點匹配序列搜索得到的子圖匹配包含查詢圖的所有子圖匹配，證明利用k查詢節點匹配序列在降低了搜索空間大小的前提下，可以匹配到所有答案集。

2.2 最小連通支配子圖

本節主要對于最小連通支配子圖的查找做出詳細論述。文獻[9]采用貪心的方法來查找最小支配集，找到的最小支配集是非連通的。與本文問題定義不一致，因此本文對該方法進行改進，提出一種新的基于貪心搜索最小連通支配子圖算法。本節首先介紹最小連通支配子圖的概念，然后介紹如何尋找最小連通支配子圖。

定義5連通支配集。給定一個查詢圖Q(VQ,EQ,LQ)，節點支配集DS中，如果節點在圖Q上是連通，就稱為連通支配集，記作CDS。支配節點數最小的連通支配集稱為最小連通支配集，記作MCDS。

定義6最小連通支配子圖。圖Q的所有支配子圖中，節點數目|V(QD)|最少且節點在圖Q上是連通的支配子圖稱為Q的最小連通支配子圖，記作QMCD。

算法開始時，初始化支配集合MCDS=?，M=V(Q)(表示查詢圖中所有節點)，不斷向集合MCDS中加入節點，刪除集合M中度最小的非支配節點，直到M=MCDS。在算法1中查詢圖中的節點分為兩類：一類是支配節點，記作MCDS；另一類是非支配節點M。算法的基本思想是對于給定的查詢圖在保證圖連通的前提下，不斷刪減M集合中度最小的非支配節點。為了保證圖的連通性，在刪除節點時需要判斷其鄰接節點中是否存在度為1的節點；如果存在，則將該節點標記為支配節點，加入集合MCDS。

算法1FindMCDS-Graph

輸入：查詢圖Q。

輸出：最小連通支配子圖QMCD。

1.function FindMCDS-Graph(Q){

2.setMCDS=?,M=V(Q)

3.while(?v={v|v∈M∧v?MCDS}){

5.Q=M-v;

6.if(alld(N(v))>1){

7.M=Q;

8.if(?N(v)∈MCDS){continue};

10.MCDS=MCDS∪u;

11.else{

12.MCDS=MCDS∪v;

13.}

14.FindE(QMCD) based onMCDS

15.returnQMCD;

16.}

按照算法1，需要不斷從查詢圖中刪除節點，直到再刪除其中任何一個節點都會破壞其連通性。圖1(a)中查詢圖的最小連通支配子圖過程是：初始化MCDS=?，M=V(Q)；根據查詢圖中節點度的大小降序排序得到節點u1且該節點不存在度為1的鄰接點，執行第9行，找到節點u1鄰接點中度最大的節點u4。節點u4加入支配集MCDS中(圖4(a))；節點u9的鄰居節點u4為支配集節點，因此節點u9可以直接刪除(圖4(b),算法第8行)；繼續執行下一個循環，選擇下一個度最小的節點，此時節點u0、u5的度數均為2，假設選擇節點u5。節點u5不存在度為1的鄰接點，且節點v5的鄰接點v4屬于支配節點，所以可以判斷節點u5是非支配節點，可以直接刪除(圖4(c))。依次類推，節點u8直接刪除(圖4(d))，節點u7的支配節點為u6(圖4(e))，此時MCDS={u4,u6},M={u0,u2,u3,u4,u6}，需要刪除節點u0，其鄰居節點為u2、u3。如果將節點u2置為支配節點，M集合中只有節點u3不屬于支配集MCDS，但節點u3存在度為1的鄰接點u4(第6行)，節點u3不能被刪除。將節點u3加入支配集MCDS(圖4(f))。至此，M集合中不存在任何一個非支配節點(MCDS=M)，最終最小連通支配集為MCDS={u2,u3,u4,u6}。圖3給出的支配子圖為最小連通支配子圖，其存在不同的節點匹配序列，如、。由于查詢節點的出度入度大小不同，節點標簽不同，導致在數據圖中候選節點個數不同，因此查詢節點不同的執行順序會造成查詢響應時間的不同。下節將詳細介紹如何選取最優k查詢節點匹配序列，提高查詢響應效率。

(a) 刪除節點u1，標記支配節點u4 (b) 刪除節點u9

(c) 刪除節點u5 (d) 刪除節點u8

2.3 最優k查詢節點路徑

1.1節舉例說明了查詢節點的匹配順序影響子圖匹配的效率。因此，通過優先選擇區分度高的節點，快速確定第一個查詢節點的答案集并以此縮小其他查詢節點的搜索范圍，提高查詢速度，其核心在于查詢節點的處理順序。本文修改了文獻[14]提出的代價模型，通過對數據圖與查詢圖節點標簽，節點度的大小及節點間結構信息進行代價分析，設計成本模型。其模型函數如下：

N(ui)=|E(ui,uj)|(0≤j

(3)

W(u)=NG(u)/|deg(u)|

(4)

NG(u)=|{LG(u)|LG(u)∈G}|

(5)

式中：函數N(ui)匹配序列中第i個節點與前i-1個節點之間的邊的數量；|deg(u)|代表節點u的度的大??；函數NG(u)表示查詢圖節點u候選節點個數。成本模型遵循以下規則：

(1)N(ui)的值越大代表節點ui與已匹配節點存在邊數量越多，受約束越大，候選集越少，匹配代價越低。如果N(ui)相同，遵循規則(2)。

(2)NG(u)越小，|deg(u)|越大，W(u)則越小，表示節點u在數據圖中的候選節點越少，所支配的節點個數越多。

表1給出了查詢圖支配節點成本模型的計算值，基于此可以初步確定k查詢節點匹配序列為。需要注意的是，最小連通支配子圖的任意一個節點一定與圖中某一節點存在至少一條邊關系，如果當前節點與已匹配成功節點之間有盡可能多的邊關系，可以減少當前節點的搜索空間。因此，確定節點順序過程中，優先考慮N(ui)值。對于初始節點N(ui)的值均為0，選取W(u)值最小的節點u2。按成本模型計算，此時剩余節點中N(u3)=1、N(u6)=1、N(u4)=0、W(u3)=10、W(u6)=50,所以k查詢節點路徑中第2個節點為u6。依次類推，此時剩余節點中N(u3)=1，N(u4)=0，k查詢節點路徑中第3個節點為u3。因此，查詢圖的全節點路徑順序為。

本節重點闡述通過選擇區分度高、候選集少的節點進行優先匹配來提高匹配效率。除此之外，通過有效的剪枝規則減少候選節點的數量也是降低查詢響應時間的重要因素。

2.4 剪枝策略

由定義4可知，支配節點的被支配節點，均為該節點的鄰接節點。圖1(a)中，節點v133的被支配集NDS(v133)={v10,v256,v357,v234}。同理，對于圖1(b)中查詢圖中節點u4的支配集NDS(u4)={u3,u9,u5,u1,u8}。

搜尋查詢節點的候選節點，基本方法是利用節點標簽及度的大小，例如在圖1中C(u4)={v123,v124,…,v133}。把查詢圖轉化為由支配節點構成的最小連通支配子圖，保存節點的鄰接節點時間復雜度為O(1)，因此可以通過保存支配節點結構特征，利用支配節點的結構特征對搜索空間進行剪枝。

定義7被支配節點標簽集合。給定數據圖G,節點v∈V(G),節點標簽l∈L。被支配節點標簽l集合NDLSl(v)的定義如下：NDLSl(v)={u|u∈NDS(v),L(u)=l}。

NDLSl(v)表示由節點v的被支配節點中標簽為l的節點構成的集合。被支配節點標簽集合NDLS(v)={NDLSl(v)|l∈L}，表示NDLSl(v)的集合。

在圖1(a)中，數據圖中節點v133的被支配節點標簽集合NDLS(v133)={{v10:B},{v256:J},{v357:H},{v234:G}}，同理，對于圖1(b)中查詢圖中節點u4的被支配節點標簽集NDLS(u4)={{u3:B},{u9:J},{u5:H},{u1:G},{u8:I}}。

定義8候選約束。給定節點u∈V(Q),v∈V(G),如果，l∈L,都滿足|NDLSl(u)|≤|NDLSl(v)|,則稱NDLS(u)受約束于NDLS(v)，記作NDLS(u)?NDLS(v)。

定理4給定數據圖G和查詢圖Q，如果G中存在Q的一個子圖匹配，即Q?G，那么?u∈V(Q),NDSQ(u)?NDSG(f(u)),f(u)∈V(G)。

證明：給定數據圖G查詢圖Q,已知G中存在Q的一個子圖匹配(Q?G)，則會出現以下情形：

(1) |V(Q)|=|V(G)|,|E(Q)|=|E(G)|時，Q中邊的數量與G中邊的數量相同，此時Q中任意支配節點的被支配節點數量等于G。?u∈Q,v=f(u),|NDLSl(u)|=|NDLSl(v)|。

(2) |V(Q)|<|V(G)|,|E(Q)|<|E(G)|時，Q中節點和邊的數量均小于G的數量，且Q?G，?u∈Q,u′=f(u)(u′∈G),均滿足?v∈NDS(u),?m∈NDS(u′)且m=f(v)，|NDLSl(u)|≤|NDLSl(v)|。

綜上所述，定理4成立。

由定理4，節點u∈V(Q),v∈V(G)且v∈C(u)，如果|NDLSl(u)|>|NDLSl(v)|，則證明節點v并非正確候選集，可以從節點v的候選集C(u)中刪除，來降低搜索空間大小。例如，在圖1給出的數據圖和查詢圖中，節點v133∈C(u4),是節點u4的候選節點，但是由于|NDLSi(u4)|=1，|NDLSi(v133)|=0，|NDLSi(u4)|>|NDLSi(v133)|，不滿足定理4，節點v133非正確候選集，可以將節點從集合C(u4)中刪除，以此減少搜索空間。

k查詢節點匹配序列執行完成后，繼而搜索剩余節點(非支配節點)的匹配節點。剩余節點的候選節點均為k查詢節點匹配序列中節點(支配節點)的鄰接節點。由定理2可知，通過支配節點的匹配節點可以搜索到非支配節點的候選集。例如：被支配節點u0存在2個支配節點，分別為支配節點u2和支配節點u3。易分析，被支配節點u0的候選節點需要同時為節點u2和節點u3匹配節點的被支配節點，因此可得節點u0的候選集節點:C(u0)={adj(C(u2))∩adj(C(u3))∩C(u0)}。adj(C(u2)),adj(C(u3))分別表示節點u2、u3的候選節點的一階鄰居節點，其中adj(C(u2))={v1,v2,…,v122},adj(C(u3))={v11,v111,v123,…,v133}，C(u0)={v1,v2,…,v111}。節點u0的候選集為C(u0)={v11,v111}，縮小了被支配節點候選集的大小。

3 實 驗

3.1 實驗環境與數據集設置

近年來，模式匹配技術在學術界獲得越來越多的關注，研究機構發布了許多評測數據集。數據集主要分為真實數據圖數據集、合成數據圖數據集。本文實驗采用AIDS Antiviral數據集[15-16]、Yeast數據集[17-18]、YAGO2數據集[19]。AIDS Antiviral數據集主要包含結構稀疏的無向圖，每幅圖表示一種化學物質的原子結構，原始數據來源于發展治療項目。Yeast數據集包含一個唯一大圖，邊12 519條，節點3 112個。圖中每個節點代表一種蛋白質，邊代表兩個蛋白質之間的作用關系，Yeast數據集中節點的度大小平均為8.05。與AIDS Antiviral數據集相比，該數據集的圖更加稠密。YAGO2數據集包含一個唯一大圖，邊86 282條，節點4 675個，圖中每個節點的度平均為36.82。相比于Yeast數據集，規模更大結構更加稠密。數據集詳細信息如表2所示。

將本文方法與模式匹配代表算法(GADDI、SPath)，以及近幾年的算法(VF2++[20]、VF3、SubISO[21])進行比較,測試的代碼以及相應的數據來源于文獻[2,15,20-21]。Ullmann和VF2算法是基礎的模式匹配的算法，后續改進算法在性能上已遠遠超過原始算法，本文不再對Ullmann和VF2的性能進行比較。本文一共做了三組對比實驗，分別從數據庫構建時間、存儲空間和查詢響應時間三個方面對算法的性能進行分析。

本實驗設備采用Windows 10 64位系統，CPU：Intel(R)Core(TM)i7-7700U CPU@3.6 GHz,內存：16 GB。

3.2 實驗分析

實驗一分析了數據集構建時間。表3中給出了GADDI、SPath、VF2++、VF3、SubISO、VF-SMDS算法在AIDS、Yeast、YAGO2數據集上數據庫構建時間的比較。由表3可見，在構建數據庫過程中，VF2++、VF3、VF-SMDS在三個數據集上的數據庫構建時間相差較小，與其他三種算法相比所需時間比較短，這是因為VF2++、VF3對數據圖無須提取輔助結構，預處理所需時間短。VF-SMDS需要保存節點鄰接結構信息。SPath需要計算并保存k階鄰居結構。SubISO算法需要預先計算節點偏心率(節點間最短路徑的最大值)，GADDI需要預先計算NDS距離，所以數據庫構建的時間與其他三種算法相比最長。

實驗二分析了數據集存儲空間。表4是不同算法在三種數據集上的存儲空間的比較。由于Spath引入了復雜的鄰接信息，以節點為中心采用層次遍歷的三元組表示方法，因此除了數據圖節點還需要額外存儲節點的k階鄰接信息，Spath的存儲空間是VF-SMDS的2.1～5.0倍。而GADDI則需要存儲兩個節點及相鄰節點的NDS距離，SubISO需要存儲節點偏心率，存儲空間是VF-SMDS的1.2～2.1倍。VF2++、VF3存儲空間略低于VF-SMDS，因為VF-SMDS更好的利用鄰接節點的結構信息來降低查詢響應時間。

查詢圖中三元組的數量范圍區間為[3，15](查詢圖中三元組的數量表示查詢圖的規模)。在AIDS、Yeast和YAGO2數據集中，查詢圖規模小于6時，查詢圖結構較為簡單，只有在查詢圖規模大于等于6時，才會出現復雜結構。

實驗三分析了算法的平均查詢響應時間。圖5給出以上六種算法在三種數據集上針對不同規模的查詢圖進行子圖匹配的平均查詢響應時間。在AIDS數據集上，VF3匹配速度最快，VF-SMDS、SubISO、VF2++、GADDI、SPath的平均查詢響應時間分別是VF3的1.06倍、1.7倍、2.1倍、2.8倍、6.1倍。SPath平均查詢響應時間最高主要在于篩選備選節點時，需要匹配節點周圍大量的鄰接節點。GADDI算法在匹配過程中需要計算查詢圖中任意兩個節點間的DNS距離，導致過高的時間復雜度；此外AIDS數據集結構稀疏，存在大量DNS距離為0，降低了GADDI算法篩選備用節點的能力。VF2++和VF3算法的優化策略分為兩步：確定節點匹配順序，縮小候選集大小。但是VF2++算法確定節點匹配順序僅考慮到了節點的標簽及度的大小，過濾效果比VF3算法差。SubISO算法通過比較查詢圖節點與候選節點的偏心率來縮小數據圖候選區域規模，AINDS多為規模較小數據圖，導致SubISO篩選效果較差。Yeast數據集上，數據集的稠密度增大，GADDI、SPath、VF2++分別在查詢圖規模大于7、9、9時出現指數級的匹配時間，而VF3、SubISO和VF-SMDS查詢響應時間上升趨勢遠遠小于GADDI和SPath，這主要是因為SPath需要計算節點周圍標簽路徑及對標簽路徑合并，導致大規模圖查詢響應時間高；GADDI缺乏有效節點合并順序。VF2++算法過濾候選集時，僅考慮節點標簽以及度的大小，導致搜索空間過大，回溯次數較多，查詢時間過長。在YAGO2數據集上，GADDI、SPath、VF2++、SubISO、VF3算法在查詢圖規模分別為5、7、7、9、11時表現出指數級別的匹配時間。YAGO2數據集結構更為稠密，隨著查詢圖規模的增大，查詢圖的結構更為繁瑣，VF3算法未充分考慮查詢圖的結構信息，在查詢過程中回溯次數過高，導致平均查詢時間的上升。而SubISO算法雖然縮小了數據圖候選區域的大小，但子圖匹配的過程是基于VF2算法，時間復雜度隨查詢圖增大呈指數上升。

(a) AIDS

(c) YAGO2圖5 不同算法的平均查詢響應時間變化曲線

上述實驗結果表明：VF-SMDS在結構稠密數據集表現最好，在結構稀疏數據集上的平均查詢響應時間優于GADDI、SPath、VF2++和SubISO算法，對于規模較大結構復雜的查詢圖平均響應時間也優于GADDI、SPath、SubISO、VF2++和VF3。在數據集構建時間上，VF-SMDS在六種算法中表現僅次于VF2++和VF3，數據集的存儲空間明顯優于GADDI、SPath和SubISO。因此，從三組實驗中共同得出結論，針對大規模數據圖子圖匹配，VF-SMDS效率更高。

4 結 語

為了提高子圖匹配的效率，提出了一種基于圖連通支配集的子圖匹配優化算法——VF-SMDS。首先，通過貪心算法獲取查詢圖的最小連通支配子圖；然后，利用代價模型確定最優k查詢節點匹配序列；最后，利用支配節點的結構信息對搜索空間進行有效剪枝。本文分別采用了AIDS Antiviral數據集、Yeast數據集、YAGO2數據集并與主流算法(GADDI,Spath)和近幾年的算法(VF2++、SubISO、VF3)進行實驗對比，驗證了VF-SMDS的可擴展性和高效性。實驗結果表明：在處理大數據圖、查詢圖規模較大、查詢圖節點較多的情況下，VF-SMDS的查詢時間更少，效率更高。未來工作將對VF-SMDS進行充分研究，將VF-SMDS應用在分布式處理平臺上，進一步研究支配節點對子圖匹配的影響。