基于圖連通支配集的子圖匹配優(yōu)化算法

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

0 引 言

模式匹配是一個(gè)子圖同構(gòu)問(wèn)題，給定一個(gè)查詢圖和數(shù)據(jù)圖，模式匹配是指搜索到所有同構(gòu)于查詢圖的數(shù)據(jù)子圖[1]。基于節(jié)點(diǎn)的子圖匹配方法是解決模式匹配問(wèn)題的一種有效方法，其以節(jié)點(diǎn)作為最小匹配單位，利用了SSR(State Space Representation)樹(shù)模型構(gòu)建模式匹配的執(zhí)行過(guò)程[2]。其中，狀態(tài)表示一個(gè)由查詢圖節(jié)點(diǎn)和數(shù)據(jù)圖節(jié)點(diǎn)組成的節(jié)點(diǎn)對(duì)。如果查詢圖節(jié)點(diǎn)和數(shù)據(jù)圖節(jié)點(diǎn)滿足匹配條件(查詢圖節(jié)點(diǎn)出度小于數(shù)據(jù)圖節(jié)點(diǎn)出度，查詢圖節(jié)點(diǎn)入度小于數(shù)據(jù)圖節(jié)點(diǎn)入度，查詢圖節(jié)點(diǎn)標(biāo)簽與數(shù)據(jù)圖標(biāo)簽相同等)，則將其加入SSR樹(shù)模型。當(dāng)匹配成功的節(jié)點(diǎn)數(shù)量等價(jià)于查詢圖節(jié)點(diǎn)數(shù)量，則輸出一個(gè)子圖匹配的答案集。

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

因此，本文提出一種基于圖連通支配集的子圖匹配優(yōu)化算法，其主要思想是通過(guò)查詢圖支配節(jié)點(diǎn)降低查詢節(jié)點(diǎn)在搜索過(guò)程中的迭代次數(shù)，即降低搜索空間的大小。

本文主要貢獻(xiàn)如下：給出查詢圖節(jié)點(diǎn)的最小連通支配集求解模型，構(gòu)造代價(jià)模型，編排最小連通支配集匹配序列，利用支配節(jié)點(diǎn)的結(jié)構(gòu)信息對(duì)搜索空間進(jìn)行有效剪枝，通過(guò)實(shí)驗(yàn)評(píng)估得出本文方法比其他同類算法具有更高的時(shí)間效率。

1 查詢圖節(jié)點(diǎn)重要度

1.1 節(jié)點(diǎn)匹配算法思想

節(jié)點(diǎn)匹配算法是一種回溯算法，其算法思想主要包括三個(gè)部分：(1) 利用查詢圖節(jié)點(diǎn)的出度(查詢圖節(jié)點(diǎn)的出度鄰接節(jié)點(diǎn)稱之為后繼節(jié)點(diǎn))和入度(查詢圖節(jié)點(diǎn)的入度鄰接節(jié)點(diǎn)稱之為前驅(qū)節(jié)點(diǎn))保障查詢節(jié)點(diǎn)匹配的連續(xù)性；(2) 通過(guò)優(yōu)化策略來(lái)優(yōu)化查詢圖節(jié)點(diǎn)的執(zhí)行序列；(3) 利用有效的剪枝規(guī)則降低搜索空間的大小。

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

如圖1所示，圖1(a)給出一個(gè)查詢圖，其為一個(gè)帶標(biāo)簽的有向圖。查詢圖Q包括10個(gè)查詢節(jié)點(diǎn)(u0,u1,…,u10)并標(biāo)注了相應(yīng)的節(jié)點(diǎn)標(biāo)簽(A,B,…,J)。圖1(b)給出一個(gè)數(shù)據(jù)圖，其圖結(jié)構(gòu)的描述與查詢圖類似。不同之處在于查詢圖規(guī)模遠(yuǎn)遠(yuǎn)小于數(shù)據(jù)圖規(guī)模。

(a) 查詢圖

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

1.2 問(wèn)題定義

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

定義1子圖匹配。給定一個(gè)查詢圖Q(VQ,EQ,LQ)和一個(gè)數(shù)據(jù)圖G(VG,EG,LG)，子圖匹配定義為從Q和G之間的一個(gè)映射函數(shù)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)表示節(jié)點(diǎn)標(biāo)簽。

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

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

獲取k查詢節(jié)點(diǎn)匹配序列是本文要解決的第一個(gè)問(wèn)題，通過(guò)獲取k查詢節(jié)點(diǎn)來(lái)減小N，提高查詢效率；構(gòu)造代價(jià)模型選取具有較好區(qū)分度節(jié)點(diǎn)，優(yōu)化k查詢節(jié)點(diǎn)匹配序列是本文要解決的第二個(gè)問(wèn)題；利用節(jié)點(diǎn)結(jié)構(gòu)特征減少節(jié)點(diǎn)候選集的數(shù)量是本文要解決的第三個(gè)問(wèn)題。

2 基于支配節(jié)點(diǎn)的子圖匹配

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

2.1 支配集及最小支配集

對(duì)于查詢節(jié)點(diǎn)ui，其候選節(jié)點(diǎn)集為C(ui)。如果節(jié)點(diǎn)uj為節(jié)點(diǎn)ui的鄰接節(jié)點(diǎn)，那么uj的匹配節(jié)點(diǎn)一定包含在C(ui)的鄰接節(jié)點(diǎn)中。因此，已知節(jié)點(diǎn)ui的匹配節(jié)點(diǎn)，很容易搜尋到節(jié)點(diǎn)uj的匹配節(jié)點(diǎn)，可以稱節(jié)點(diǎn)ui支配節(jié)點(diǎn)uj。基于上述論證，本文利用節(jié)點(diǎn)之間的支配關(guān)系，縮小全節(jié)點(diǎn)匹配序列的長(zhǎng)度，構(gòu)造k查詢節(jié)點(diǎn)匹配序列。節(jié)點(diǎn)之間的支配關(guān)系是源自于支配集的概念，因此首先介紹與節(jié)點(diǎn)支配集[9-13]以及支配子圖的相關(guān)定義。

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

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

(a) (b)

(c) (d)圖2 支配節(jié)點(diǎn)以及被支配節(jié)點(diǎn)舉例(陰影為支配節(jié)點(diǎn))

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

證明：假設(shè)存在一個(gè)節(jié)點(diǎn)u既不屬于集合DS又不屬于集合DS中某些節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，則一定會(huì)出現(xiàn)以下情形：存在兩個(gè)支配節(jié)點(diǎn)之間的邊的數(shù)量大于3，與節(jié)點(diǎn)支配集定義相矛盾，因此定理1成立。

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

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

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

定理2說(shuō)明如果節(jié)點(diǎn)ui是支配節(jié)點(diǎn)，vi是ui的匹配節(jié)點(diǎn)，um是ui的被支配節(jié)點(diǎn)，那么um的匹配節(jié)點(diǎn)屬于vi的被支配節(jié)點(diǎn)。

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

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

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

2.2 最小連通支配子圖

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

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

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

算法開(kāi)始時(shí)，初始化支配集合MCDS=?，M=V(Q)(表示查詢圖中所有節(jié)點(diǎn))，不斷向集合MCDS中加入節(jié)點(diǎn)，刪除集合M中度最小的非支配節(jié)點(diǎn)，直到M=MCDS。在算法1中查詢圖中的節(jié)點(diǎn)分為兩類：一類是支配節(jié)點(diǎn)，記作MCDS；另一類是非支配節(jié)點(diǎn)M。算法的基本思想是對(duì)于給定的查詢圖在保證圖連通的前提下，不斷刪減M集合中度最小的非支配節(jié)點(diǎn)。為了保證圖的連通性，在刪除節(jié)點(diǎn)時(shí)需要判斷其鄰接節(jié)點(diǎn)中是否存在度為1的節(jié)點(diǎn)；如果存在，則將該節(jié)點(diǎn)標(biāo)記為支配節(jié)點(diǎn)，加入集合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，需要不斷從查詢圖中刪除節(jié)點(diǎn)，直到再刪除其中任何一個(gè)節(jié)點(diǎn)都會(huì)破壞其連通性。圖1(a)中查詢圖的最小連通支配子圖過(guò)程是：初始化MCDS=?，M=V(Q)；根據(jù)查詢圖中節(jié)點(diǎn)度的大小降序排序得到節(jié)點(diǎn)u1且該節(jié)點(diǎn)不存在度為1的鄰接點(diǎn)，執(zhí)行第9行，找到節(jié)點(diǎn)u1鄰接點(diǎn)中度最大的節(jié)點(diǎn)u4。節(jié)點(diǎn)u4加入支配集MCDS中(圖4(a))；節(jié)點(diǎn)u9的鄰居節(jié)點(diǎn)u4為支配集節(jié)點(diǎn)，因此節(jié)點(diǎn)u9可以直接刪除(圖4(b),算法第8行)；繼續(xù)執(zhí)行下一個(gè)循環(huán)，選擇下一個(gè)度最小的節(jié)點(diǎn)，此時(shí)節(jié)點(diǎn)u0、u5的度數(shù)均為2，假設(shè)選擇節(jié)點(diǎn)u5。節(jié)點(diǎn)u5不存在度為1的鄰接點(diǎn)，且節(jié)點(diǎn)v5的鄰接點(diǎn)v4屬于支配節(jié)點(diǎn)，所以可以判斷節(jié)點(diǎn)u5是非支配節(jié)點(diǎn)，可以直接刪除(圖4(c))。依次類推，節(jié)點(diǎn)u8直接刪除(圖4(d))，節(jié)點(diǎn)u7的支配節(jié)點(diǎn)為u6(圖4(e))，此時(shí)MCDS={u4,u6},M={u0,u2,u3,u4,u6}，需要?jiǎng)h除節(jié)點(diǎn)u0，其鄰居節(jié)點(diǎn)為u2、u3。如果將節(jié)點(diǎn)u2置為支配節(jié)點(diǎn)，M集合中只有節(jié)點(diǎn)u3不屬于支配集MCDS，但節(jié)點(diǎn)u3存在度為1的鄰接點(diǎn)u4(第6行)，節(jié)點(diǎn)u3不能被刪除。將節(jié)點(diǎn)u3加入支配集MCDS(圖4(f))。至此，M集合中不存在任何一個(gè)非支配節(jié)點(diǎn)(MCDS=M)，最終最小連通支配集為MCDS={u2,u3,u4,u6}。圖3給出的支配子圖為最小連通支配子圖，其存在不同的節(jié)點(diǎn)匹配序列，如、。由于查詢節(jié)點(diǎn)的出度入度大小不同，節(jié)點(diǎn)標(biāo)簽不同，導(dǎo)致在數(shù)據(jù)圖中候選節(jié)點(diǎn)個(gè)數(shù)不同，因此查詢節(jié)點(diǎn)不同的執(zhí)行順序會(huì)造成查詢響應(yīng)時(shí)間的不同。下節(jié)將詳細(xì)介紹如何選取最優(yōu)k查詢節(jié)點(diǎn)匹配序列，提高查詢響應(yīng)效率。

(a) 刪除節(jié)點(diǎn)u1，標(biāo)記支配節(jié)點(diǎn)u4 (b) 刪除節(jié)點(diǎn)u9

(c) 刪除節(jié)點(diǎn)u5 (d) 刪除節(jié)點(diǎn)u8

2.3 最優(yōu)k查詢節(jié)點(diǎn)路徑

1.1節(jié)舉例說(shuō)明了查詢節(jié)點(diǎn)的匹配順序影響子圖匹配的效率。因此，通過(guò)優(yōu)先選擇區(qū)分度高的節(jié)點(diǎn)，快速確定第一個(gè)查詢節(jié)點(diǎn)的答案集并以此縮小其他查詢節(jié)點(diǎn)的搜索范圍，提高查詢速度，其核心在于查詢節(jié)點(diǎn)的處理順序。本文修改了文獻(xiàn)[14]提出的代價(jià)模型，通過(guò)對(duì)數(shù)據(jù)圖與查詢圖節(jié)點(diǎn)標(biāo)簽，節(jié)點(diǎn)度的大小及節(jié)點(diǎn)間結(jié)構(gòu)信息進(jìn)行代價(jià)分析，設(shè)計(jì)成本模型。其模型函數(shù)如下：

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

(3)

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

(4)

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

(5)

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

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

(2)NG(u)越小，|deg(u)|越大，W(u)則越小，表示節(jié)點(diǎn)u在數(shù)據(jù)圖中的候選節(jié)點(diǎn)越少，所支配的節(jié)點(diǎn)個(gè)數(shù)越多。

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

本節(jié)重點(diǎn)闡述通過(guò)選擇區(qū)分度高、候選集少的節(jié)點(diǎn)進(jìn)行優(yōu)先匹配來(lái)提高匹配效率。除此之外，通過(guò)有效的剪枝規(guī)則減少候選節(jié)點(diǎn)的數(shù)量也是降低查詢響應(yīng)時(shí)間的重要因素。

2.4 剪枝策略

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

搜尋查詢節(jié)點(diǎn)的候選節(jié)點(diǎn)，基本方法是利用節(jié)點(diǎn)標(biāo)簽及度的大小，例如在圖1中C(u4)={v123,v124,…,v133}。把查詢圖轉(zhuǎn)化為由支配節(jié)點(diǎn)構(gòu)成的最小連通支配子圖，保存節(jié)點(diǎn)的鄰接節(jié)點(diǎn)時(shí)間復(fù)雜度為O(1)，因此可以通過(guò)保存支配節(jié)點(diǎn)結(jié)構(gòu)特征，利用支配節(jié)點(diǎn)的結(jié)構(gòu)特征對(duì)搜索空間進(jìn)行剪枝。

定義7被支配節(jié)點(diǎn)標(biāo)簽集合。給定數(shù)據(jù)圖G,節(jié)點(diǎn)v∈V(G),節(jié)點(diǎn)標(biāo)簽l∈L。被支配節(jié)點(diǎn)標(biāo)簽l集合NDLSl(v)的定義如下：NDLSl(v)={u|u∈NDS(v),L(u)=l}。

NDLSl(v)表示由節(jié)點(diǎn)v的被支配節(jié)點(diǎn)中標(biāo)簽為l的節(jié)點(diǎn)構(gòu)成的集合。被支配節(jié)點(diǎn)標(biāo)簽集合NDLS(v)={NDLSl(v)|l∈L}，表示NDLSl(v)的集合。

在圖1(a)中，數(shù)據(jù)圖中節(jié)點(diǎn)v133的被支配節(jié)點(diǎn)標(biāo)簽集合NDLS(v133)={{v10:B},{v256:J},{v357:H},{v234:G}}，同理，對(duì)于圖1(b)中查詢圖中節(jié)點(diǎn)u4的被支配節(jié)點(diǎn)標(biāo)簽集NDLS(u4)={{u3:B},{u9:J},{u5:H},{u1:G},{u8:I}}。

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

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

證明：給定數(shù)據(jù)圖G查詢圖Q,已知G中存在Q的一個(gè)子圖匹配(Q?G)，則會(huì)出現(xiàn)以下情形：

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

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

綜上所述，定理4成立。

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

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

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集設(shè)置

近年來(lái)，模式匹配技術(shù)在學(xué)術(shù)界獲得越來(lái)越多的關(guān)注，研究機(jī)構(gòu)發(fā)布了許多評(píng)測(cè)數(shù)據(jù)集。數(shù)據(jù)集主要分為真實(shí)數(shù)據(jù)圖數(shù)據(jù)集、合成數(shù)據(jù)圖數(shù)據(jù)集。本文實(shí)驗(yàn)采用AIDS Antiviral數(shù)據(jù)集[15-16]、Yeast數(shù)據(jù)集[17-18]、YAGO2數(shù)據(jù)集[19]。AIDS Antiviral數(shù)據(jù)集主要包含結(jié)構(gòu)稀疏的無(wú)向圖，每幅圖表示一種化學(xué)物質(zhì)的原子結(jié)構(gòu)，原始數(shù)據(jù)來(lái)源于發(fā)展治療項(xiàng)目。Yeast數(shù)據(jù)集包含一個(gè)唯一大圖，邊12 519條，節(jié)點(diǎn)3 112個(gè)。圖中每個(gè)節(jié)點(diǎn)代表一種蛋白質(zhì)，邊代表兩個(gè)蛋白質(zhì)之間的作用關(guān)系，Yeast數(shù)據(jù)集中節(jié)點(diǎn)的度大小平均為8.05。與AIDS Antiviral數(shù)據(jù)集相比，該數(shù)據(jù)集的圖更加稠密。YAGO2數(shù)據(jù)集包含一個(gè)唯一大圖，邊86 282條，節(jié)點(diǎn)4 675個(gè)，圖中每個(gè)節(jié)點(diǎn)的度平均為36.82。相比于Yeast數(shù)據(jù)集，規(guī)模更大結(jié)構(gòu)更加稠密。數(shù)據(jù)集詳細(xì)信息如表2所示。

將本文方法與模式匹配代表算法(GADDI、SPath)，以及近幾年的算法(VF2++[20]、VF3、SubISO[21])進(jìn)行比較,測(cè)試的代碼以及相應(yīng)的數(shù)據(jù)來(lái)源于文獻(xiàn)[2,15,20-21]。Ullmann和VF2算法是基礎(chǔ)的模式匹配的算法，后續(xù)改進(jìn)算法在性能上已遠(yuǎn)遠(yuǎn)超過(guò)原始算法，本文不再對(duì)Ullmann和VF2的性能進(jìn)行比較。本文一共做了三組對(duì)比實(shí)驗(yàn)，分別從數(shù)據(jù)庫(kù)構(gòu)建時(shí)間、存儲(chǔ)空間和查詢響應(yīng)時(shí)間三個(gè)方面對(duì)算法的性能進(jìn)行分析。

本實(shí)驗(yàn)設(shè)備采用Windows 10 64位系統(tǒng)，CPU：Intel(R)Core(TM)i7-7700U CPU@3.6 GHz,內(nèi)存：16 GB。

3.2 實(shí)驗(yàn)分析

實(shí)驗(yàn)一分析了數(shù)據(jù)集構(gòu)建時(shí)間。表3中給出了GADDI、SPath、VF2++、VF3、SubISO、VF-SMDS算法在AIDS、Yeast、YAGO2數(shù)據(jù)集上數(shù)據(jù)庫(kù)構(gòu)建時(shí)間的比較。由表3可見(jiàn)，在構(gòu)建數(shù)據(jù)庫(kù)過(guò)程中，VF2++、VF3、VF-SMDS在三個(gè)數(shù)據(jù)集上的數(shù)據(jù)庫(kù)構(gòu)建時(shí)間相差較小，與其他三種算法相比所需時(shí)間比較短，這是因?yàn)閂F2++、VF3對(duì)數(shù)據(jù)圖無(wú)須提取輔助結(jié)構(gòu)，預(yù)處理所需時(shí)間短。VF-SMDS需要保存節(jié)點(diǎn)鄰接結(jié)構(gòu)信息。SPath需要計(jì)算并保存k階鄰居結(jié)構(gòu)。SubISO算法需要預(yù)先計(jì)算節(jié)點(diǎn)偏心率(節(jié)點(diǎn)間最短路徑的最大值)，GADDI需要預(yù)先計(jì)算NDS距離，所以數(shù)據(jù)庫(kù)構(gòu)建的時(shí)間與其他三種算法相比最長(zhǎng)。

實(shí)驗(yàn)二分析了數(shù)據(jù)集存儲(chǔ)空間。表4是不同算法在三種數(shù)據(jù)集上的存儲(chǔ)空間的比較。由于Spath引入了復(fù)雜的鄰接信息，以節(jié)點(diǎn)為中心采用層次遍歷的三元組表示方法，因此除了數(shù)據(jù)圖節(jié)點(diǎn)還需要額外存儲(chǔ)節(jié)點(diǎn)的k階鄰接信息，Spath的存儲(chǔ)空間是VF-SMDS的2.1～5.0倍。而GADDI則需要存儲(chǔ)兩個(gè)節(jié)點(diǎn)及相鄰節(jié)點(diǎn)的NDS距離，SubISO需要存儲(chǔ)節(jié)點(diǎn)偏心率，存儲(chǔ)空間是VF-SMDS的1.2～2.1倍。VF2++、VF3存儲(chǔ)空間略低于VF-SMDS，因?yàn)閂F-SMDS更好的利用鄰接節(jié)點(diǎn)的結(jié)構(gòu)信息來(lái)降低查詢響應(yīng)時(shí)間。

查詢圖中三元組的數(shù)量范圍區(qū)間為[3，15](查詢圖中三元組的數(shù)量表示查詢圖的規(guī)模)。在AIDS、Yeast和YAGO2數(shù)據(jù)集中，查詢圖規(guī)模小于6時(shí)，查詢圖結(jié)構(gòu)較為簡(jiǎn)單，只有在查詢圖規(guī)模大于等于6時(shí)，才會(huì)出現(xiàn)復(fù)雜結(jié)構(gòu)。

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

(a) AIDS

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

上述實(shí)驗(yàn)結(jié)果表明：VF-SMDS在結(jié)構(gòu)稠密數(shù)據(jù)集表現(xiàn)最好，在結(jié)構(gòu)稀疏數(shù)據(jù)集上的平均查詢響應(yīng)時(shí)間優(yōu)于GADDI、SPath、VF2++和SubISO算法，對(duì)于規(guī)模較大結(jié)構(gòu)復(fù)雜的查詢圖平均響應(yīng)時(shí)間也優(yōu)于GADDI、SPath、SubISO、VF2++和VF3。在數(shù)據(jù)集構(gòu)建時(shí)間上，VF-SMDS在六種算法中表現(xiàn)僅次于VF2++和VF3，數(shù)據(jù)集的存儲(chǔ)空間明顯優(yōu)于GADDI、SPath和SubISO。因此，從三組實(shí)驗(yàn)中共同得出結(jié)論，針對(duì)大規(guī)模數(shù)據(jù)圖子圖匹配，VF-SMDS效率更高。

4 結(jié) 語(yǔ)

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