基于預(yù)處理-枚舉的子圖匹配算法

巴倫敦,梁 平,顧進(jìn)廣

(1.武漢科技大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,湖北 武漢 430065;2.智能信息處理與實時工業(yè)系統(tǒng)湖北省重點(diǎn)實驗室,湖北 武漢 430065)

0 引 言

近年來,圖在各個領(lǐng)域發(fā)揮著越來越重要的作用。圖分析中最基本的問題之一是子圖匹配。給定一個數(shù)據(jù)圖G和一個查詢圖q,子圖匹配是在G中找到q的所有不同嵌入的問題。例如,對于圖1中的查詢圖q和數(shù)據(jù)圖G,{(u0,v0),(u1,v4),(u2,v5),(u3,v12)}是從查詢圖q到數(shù)據(jù)圖G的一種子圖匹配結(jié)果。子圖匹配具有廣泛的應(yīng)用場景,如生物信息學(xué)[1-2]、社會網(wǎng)絡(luò)分析[3-4]、化學(xué)復(fù)合搜索[5-6]等。在這些應(yīng)用中,子圖匹配是整體性能的瓶頸,因為它是典型的NP-hard問題之一[7-8]。

圖1 查詢圖與數(shù)據(jù)圖

由于子圖匹配的重要性,目前已經(jīng)提出了各種算法。這些算法專注于生成有效的匹配順序,并設(shè)計強(qiáng)大的過濾策略來最小化數(shù)據(jù)圖中候選的數(shù)量。SMID[9]提出了一種基于包含度的子圖匹配方法,找到與給定查詢圖結(jié)構(gòu)同構(gòu)并且對應(yīng)節(jié)點(diǎn)元素的加權(quán)集合包含度大于給定值的所有子圖。AC-Match[10]是一種可以根據(jù)數(shù)據(jù)集的標(biāo)簽密度和圖密度進(jìn)行自適應(yīng)調(diào)整的高效子圖匹配算法。VEQs[11]采用靜態(tài)等價和動態(tài)等價來解決響應(yīng)時間和可擴(kuò)展性有限的問題。QuickSi[12]設(shè)計了不常見的邊優(yōu)先排序技術(shù),該技術(shù)根據(jù)數(shù)據(jù)圖中出現(xiàn)的頻率升序?qū)Σ樵儓D的邊進(jìn)行排序。GraphQL[13]采用貪心策略,設(shè)計了基于左深度連接的排序方法生成匹配順序,將枚舉過程建模為連接問題。SPath[14]將路徑作為匹配的特征,在每一次的匹配過程中,將一次匹配一個節(jié)點(diǎn)優(yōu)化成為一次匹配一條路徑。Turbolso[15]設(shè)計了領(lǐng)域等價類來壓縮查詢圖,針對壓縮后的查詢圖進(jìn)行過濾以減少候選節(jié)點(diǎn),并且還對數(shù)據(jù)圖進(jìn)行了分區(qū),針對不同數(shù)據(jù)圖區(qū)域設(shè)計每個區(qū)域?qū)俚淖罴哑ヅ漤樞?。CFL[16]提出了核-森林-葉分解技術(shù),將查詢圖分解成核區(qū)域、森林區(qū)域和葉區(qū)域,并且通過優(yōu)先匹配核區(qū)域中的節(jié)點(diǎn)來推遲進(jìn)行笛卡爾積,從而減少候選節(jié)點(diǎn)。CECI[17]設(shè)計了緊湊嵌入聚類索引的輔助數(shù)據(jù)結(jié)構(gòu)幫助過濾節(jié)點(diǎn),同時采用了基于集合交集的枚舉方法進(jìn)行枚舉結(jié)果。DP-iso[18]改進(jìn)了CFL算法采用的生成樹模型,以有向無環(huán)圖模型代替生成樹,以充分利用非樹邊的強(qiáng)大剪枝能力,并基于有向無環(huán)圖設(shè)計了候選空間的輔助數(shù)據(jù)結(jié)構(gòu)來幫助過濾候選節(jié)點(diǎn)。

可以將目前的研究算法分為三種類型。第一類算法(例如,QuickSi)遵循直接枚舉框架,直接探索G枚舉所有結(jié)果。大多數(shù)基于狀態(tài)空間表示模型的算法也采用了這個框架。第二類算法(例如,SPath)利用索引枚舉框架,該框架在G上構(gòu)造索引,并在索引的幫助下完成所有查詢。第三類算法(例如,GraphQL,TurboIso,CFL,CECI和DP-iso)采用預(yù)處理枚舉框架,該框架廣泛用于數(shù)據(jù)庫社區(qū)的最新算法。一些研究發(fā)現(xiàn)現(xiàn)有工作可以從更強(qiáng)的過濾策略中受益,以最小化候選集,因為這樣可以進(jìn)一步減少部分結(jié)果的搜索廣度,并為匹配順序生成提供更準(zhǔn)確的統(tǒng)計數(shù)據(jù)。

該文提出了一種基于預(yù)處理-枚舉的子圖匹配算法(Preprocessing-Enumeration,PE),整體包含四個步驟:(1)計算查詢圖q生成候選頂點(diǎn)的索引順序;(2)根據(jù)步驟1順序正向地生成候選集,逆向地對候選集進(jìn)行精化;(3)根據(jù)候選的統(tǒng)計數(shù)據(jù)生成匹配順序;(4)基于輔助數(shù)據(jù)結(jié)構(gòu)枚舉所有結(jié)果。該算法通過考慮相鄰頂點(diǎn)之間的邊來計算候選頂點(diǎn)集的生成順序,根據(jù)前向鄰居頂點(diǎn)來生成頂點(diǎn)的候選集,再根據(jù)后向鄰居頂點(diǎn)來對頂點(diǎn)的候選集進(jìn)行精化。與樹結(jié)構(gòu)索引相比,將非樹的邊也考慮到了,從而細(xì)化得到一個更小的候選集。在此基礎(chǔ)上,根據(jù)查詢頂點(diǎn)的候選數(shù)量和度生成匹配順序,從而消除了基于樹結(jié)構(gòu)的路徑和只考慮候選數(shù)量生成匹配順序帶來的限制。

1 相關(guān)定義

1.1 圖與子圖匹配

文中采用的圖均為具有標(biāo)號的無向連通簡單圖。通過簡單處理,文中算法也可適用于其他簡單圖的子圖匹配。圖G定義為G(V,E,∑,L),其中V={v1,v2,…,vm}表示頂點(diǎn)集合;E={(vi,vj)|vi,vj∈V}表示邊的集合;∑是頂點(diǎn)標(biāo)簽集;L是一個將頂點(diǎn)v與標(biāo)簽L(v)∈∑相關(guān)聯(lián)的函數(shù)。

表1給出了與子圖匹配相關(guān)的經(jīng)常使用的一些符號的定義。定義1～定義2給出了子圖同構(gòu)及子圖匹配的定義。

表1 常用符號定義

定義1(子圖同構(gòu)):給定一個查詢圖q=(V,E,∑,L)和一個數(shù)據(jù)圖G=(V',E',∑',L')。子圖同構(gòu)是一個單射函數(shù)f:V->V',滿足:

(1)?u∈V,L(u)=L'(f(u));

(2)?e(u,v)∈E,?e(f(u),f(v))∈E'。

如果從q到G存在子圖同構(gòu),則q是與G同構(gòu)的子圖,表示為q?G。

定義2(子圖匹配):給定一個數(shù)據(jù)圖G和一個查詢圖q,子圖匹配是找到G中所有與q同構(gòu)的子圖。

1.2 候選頂點(diǎn)集與匹配順序

定義3～定義6給出了與候選頂點(diǎn)集及匹配順序相關(guān)的一些定義。

定義3(完整的候選頂點(diǎn)集):給定q和G,u∈V(q)的完整候選頂點(diǎn)集C(u)是一組數(shù)據(jù)頂點(diǎn),使得對于每個v∈V(G),如果(u,v)存在于從q到G的匹配中,則v屬于C(u)。

定義4(匹配順序):匹配順序π是V(q)的排列。π[i]是π中的第i個頂點(diǎn)。

2 基于預(yù)處理-枚舉的子圖匹配算法

為了提高算法性能,提出的預(yù)處理-枚舉的子圖匹配算法在枚舉之前引入了一個預(yù)處理階段,以減少每個查詢頂點(diǎn)的候選大小,獲得準(zhǔn)確的統(tǒng)計量來優(yōu)化匹配順序。特別的,預(yù)處理階段是為每個查詢頂點(diǎn)生成一個完整的候選頂點(diǎn)集。整個算法過程分為候選集生成、匹配順序和枚舉三個階段。

算法1給出了PE算法描述,它以q和G作為輸入,輸出從q到G的所有匹配。首先為每個查詢頂點(diǎn)提取G中的候選者,提取過程在算法2進(jìn)行了詳細(xì)描述(第2行)。接下來,生成匹配順序π,在算法3給出了匹配順序的計算過程(第3行)。第4行建立輔助數(shù)據(jù)結(jié)構(gòu)A。將這三個步驟稱為索引階段。在索引階段之后,枚舉階段基于輔助數(shù)據(jù)結(jié)構(gòu)A沿匹配順序π遞歸地擴(kuò)展部分結(jié)果,并將結(jié)果存放在M中,算法4給出了完整的枚舉過程(第5行)。

算法1:PE算法

輸入:查詢圖q和數(shù)據(jù)圖G

輸出:從q到G的所有匹配

1.begin

/*提取候選集 */

2.C← ExtractCandidates(q,G);

/*生成匹配順序 */

3.π← GenerateMatchingOrder(q,G,C);

/*建立輔助數(shù)據(jù)結(jié)構(gòu) */

4.A← BuildAuxStructure(q,G,C,π);

/*枚舉方法 */

5.Enumerate(q,G,C,A,π,M,u,i);

2.1 過濾方法

通過枚舉查找所有的匹配結(jié)果前,為了降低枚舉的耗時,在獲得一個完整候選集的前提下,需要通過過濾算法讓候選集盡可能的小。目前大部分算法直接采用標(biāo)簽和度過濾方法(LDF)或鄰居標(biāo)簽頻率過濾方法(NLF)來進(jìn)行過濾。LDF基于L(u)和d(u)生成候選集,C(u)={v∈V(G)|L(v)=L(u)∧d(v)≥d(u)}。NLF利用u的鄰居頂點(diǎn)N(u)過濾C(u)來獲得更精確的候選集,即給定v∈C(u),如果存在l∈L(N(u))使得|N(u,l)|>|N(v,l)|,其中L(N(u))和N(u,l)分別滿足L(N(u))={L(u')|u'∈N(u)}和N(u,l)={u'∈N(u)|L(u')=l},就從C(u)中刪除v。由于直接使用LDF或NLF提取的候選集存在大量錯誤候選頂點(diǎn),所以該文利用下述定理1得到新的生成規(guī)則1和過濾規(guī)則1,以提高算法在提取候選集時的過濾能力。

除了候選頂點(diǎn)集,還設(shè)計了一個輔助數(shù)據(jù)結(jié)構(gòu)A,用于存放壓縮路徑索引。A的空間復(fù)雜度為O(|V(q)|×|E(G)|)。

定理1:假設(shè)對于每個u∈V(q),C(u)都是完整的。Su'表示N(v)∩C(u'),其中V∈C(u),u'∈N(u)。如果映射(u,v)存在于從q到G的匹配中,則v必須滿足每個u'∈N(u),Su'≠?。

過濾規(guī)則1:給定X∈N(u)和v∈C(u),其中u∈V(q),如果存在u'∈X使得C(u')∩N(v)=?,那么可以安全地從C(u)中刪除且不會破環(huán)完整性。

算法2:ExtractCandidates(提取候選集)

輸入:查詢圖q和數(shù)據(jù)圖G

輸出:候選集C

1.begin

2.π'← GenerateIndexingOrder(q);

/*前向鄰居頂點(diǎn)生成候選集 */

3.u←π'[1], setu'.Cto empty for allu'∈V(q);

4.foreachv∈V(G) do

5.if LDF(u,v) is true and NLF(u,v) is true then

6.u.C←u.C∪{v};

7.fori←2 to |π'| do

8.u←π'[i];

10.if LDF(u,v) is true and NLF(u,v) is true thenu.C←u.C∪{v};

/*后向鄰居精化候選集*/

11.fori← |π'| to 1 do

12.u←π'[i];

14.removevfromu.C;

算法2給出了候選集的提取過程:首先生成查詢頂點(diǎn)的連接順序(第2行),為了與匹配順序區(qū)分開,將提取候選者的順序命名為索引順序,表示為π'。索引順序的初始點(diǎn)綜合考慮了通過LDF計算后的候選頂點(diǎn)數(shù)和頂點(diǎn)的度,后面的順序通過選擇與已排序的頂點(diǎn)相鄰最多的頂點(diǎn)。第4～6行得到π'中起始頂點(diǎn)的候選集,滿足LDF和NLF的過濾條件。接下來,沿著π'通過前向鄰居頂點(diǎn)生成候選集(第7～11行)。在第12～15行沿著π'相反的順序,由后向鄰居頂點(diǎn)對候選集精化,得到一個更小的候選集。算法2的時間復(fù)雜度為O(|E(q)|×|E(G)|)。

2.2 匹配順序

由于基于路徑的排序沒有考慮路徑中鄰接點(diǎn)之間的影響,在本質(zhì)上限制了算法性能,所以采用基于左深連接的方法來生成匹配順序,將查詢圖建模為左深連接樹。同時,因為現(xiàn)有子圖匹配實驗結(jié)果中存在稀疏查詢圖往往會比同頂點(diǎn)數(shù)的稠密查詢圖消耗更多時間的問題,所以為提高稀疏查詢圖的查詢效率,在計算匹配順序的開始頂點(diǎn)時,不僅考慮了頂點(diǎn)候選數(shù)量,也將頂點(diǎn)的度帶入計算。

算法3:GenerateMatchingOrder(生成匹配順序)

輸入:查詢圖q,數(shù)據(jù)圖G和候選集C

輸出:匹配順序π

1.begin

2.π[1]← selectStartVertex(q,C);

3.fori← 2 to |π| do

4.foreachu∈qdo

5.if unvisited(u) &adjacent(u) is true then

6.if |C(u)|

7.π[i] =u;

8.returnπ;

2.3 枚 舉

枚舉算法采用遞歸的方式來查找所有的匹配,為了方便計算,在輔助數(shù)據(jù)結(jié)構(gòu)A中維護(hù)了候選點(diǎn)之間的邊。

算法4:Enumerate(枚舉)

輸入:查詢圖q,數(shù)據(jù)圖G,候選集C,輔助數(shù)據(jù)結(jié)構(gòu)A和匹配順序π

輸出:子圖匹配結(jié)果M

1.begin

2.Enumerate(q,G,C,A,π,M,i);

3.Procedure Enumerate(q,G,C,A,π,M,i);

4.ifi=|π|+1 then OutputM, return;

5.u←π[i];

6.ifi=1 thenC'←C(u);

8.foreachv∈C'do

9.ifv?Mthen

10.Add(u,v)toM;

11.Enumerate(q,G,C,A,π,M,i+1);

12.remove (u,v) fromM;

3 實驗結(jié)果及分析

3.1 實驗環(huán)境

實驗主要評估并比較了以下具有不同索引和排序策略的算法:

PE:基于預(yù)處理-枚舉的子圖匹配算法。

QuickSi:沒有任何索引并采用不常見的邊優(yōu)先排序策略。

CFL:最先進(jìn)的算法之一。采用樹結(jié)構(gòu)索引CPI和基于路徑的排序策略。

GraphQL:采用鄰域簽名過濾器和左深度連接排序策略。

實驗共選擇了六個真實數(shù)據(jù)集,這些數(shù)據(jù)集在以前的工作中被廣泛使用[19-20]。各數(shù)據(jù)集及屬性如表2所示,其中|V|表示頂點(diǎn)的個數(shù),|E|表示邊的個數(shù),|Σ|表示標(biāo)簽的類別數(shù),d表示頂點(diǎn)的平均度。Yeast,Human,HPRD和WordNet數(shù)據(jù)集都包含標(biāo)簽,而Youtube和US Patents數(shù)據(jù)集沒有標(biāo)簽,實驗采用隨機(jī)分配不同標(biāo)簽的方式進(jìn)行。

表2 數(shù)據(jù)圖集及其屬性

查詢集通過數(shù)據(jù)圖中隨機(jī)選擇子圖來生成查詢圖,以保證至少存在一個匹配。對于每個數(shù)據(jù)圖,實驗生成八個查詢集作為默認(rèn)查詢來評估不同算法的性能。每個查詢集包括200個具有相同頂點(diǎn)數(shù)的查詢圖,每個查詢圖都是連通圖。有一半查詢集包含非稀疏查詢圖(平均度數(shù)大于等于3),另外的查詢集包含稀疏查詢圖(平均度數(shù)小于3)。

實驗中不同算法整體性能比較主要考慮了以下評估指標(biāo):

(1)執(zhí)行時間:在查詢集中處理查詢圖的平均時間,這排除了將數(shù)據(jù)從磁盤加載的時間。它由索引時間和枚舉時間組成。

不同算法的過濾方法性能比較則主要考慮了以下指標(biāo):

(1)索引時間:在處理查詢圖的索引階段花費(fèi)的平均時間。

(2)索引大小:用于處理查詢圖的索引中候選的平均數(shù)量,用于評估索引的過濾能力。

實驗運(yùn)行環(huán)境如下:16 GB內(nèi)存的AMD Ryzen 7 4800H八核電腦;所有涉及的算法均采用C++編程語言實現(xiàn),使用的編譯器GCC版本為11.3.0。

3.2 實驗結(jié)果分析

3.2.1 算法整體性能

算法整體性能比較不同算法在不同數(shù)據(jù)集的執(zhí)行時間和相對性能。在實驗中發(fā)現(xiàn)WordNet,Youtube和US Patents有相近的實驗結(jié)果,Human與Yeast實驗結(jié)果也相近。所以選擇了HPRD,Yeast和Youtube的實驗結(jié)果進(jìn)行展示。

(1)執(zhí)行時間。

不同算法在三個數(shù)據(jù)集上的執(zhí)行時間如圖2～圖4所示,其中每個數(shù)據(jù)集都按稠密查詢圖及稀疏查詢圖規(guī)模來顯示實驗結(jié)果?？梢园l(fā)現(xiàn)所有算法通常在更大的查詢上花費(fèi)更多的時間,相比于非稀疏查詢圖,稀疏查詢的查詢難度可能會提高不止一個數(shù)量級。PE,QuickSi,GraphQL和CFL的性能在不同的數(shù)據(jù)圖上有所不同。PE在不同數(shù)據(jù)圖上始終優(yōu)于其他算法,這證明了PE的效率和穩(wěn)定性。GraphQL,CFL和PE之間的性能差距在HPRD上很小,因為大量不同的標(biāo)簽使得HPRD成為查詢的簡單數(shù)據(jù)集。在圖4中,PE,QuickSi,GraphQL和CFL的執(zhí)行時間變化對查詢大小的增加不敏感。這是因為大量的查詢無法在時間限制內(nèi)完成,并且它們的執(zhí)行時間被替換為10分鐘。

圖2 數(shù)據(jù)集HPRD上的執(zhí)行時間

圖3 數(shù)據(jù)集Yeast上的執(zhí)行時間

圖4 數(shù)據(jù)集Youtube上的執(zhí)行時間

(2)相對性能。

算法的相對性能受到查詢時間的影響,當(dāng)查詢時間越短,相對性能的值越小,代表算法的性能越好。從圖2～圖4的實驗結(jié)果可以發(fā)現(xiàn),PE在不同數(shù)據(jù)集的運(yùn)行時間都是最短或者接近最短,因此PE相對性能是最接近1的。相比于其他3個算法PE具有更強(qiáng)的競爭力,原因在于這3類算法的候選集存在大量錯誤候選頂點(diǎn),并且生成匹配順序也比PE差。

3.2.2 過濾方法性能

由于實驗中所有算法的空間復(fù)雜度均為O(|E(G)|×|V(q)|),實際索引的內(nèi)存成本非常小,在每個數(shù)據(jù)集上消耗不到10 MB,因此在驗證過濾方法的有效性時,忽略了索引內(nèi)存成本,只需比較四種算法的索引策略在索引大小和索引時間兩個指標(biāo)上的性能。

(1)索引大小。

不同算法在6個數(shù)據(jù)集上的索引大小如圖5所示?？梢钥吹絈uickSi比其他算法生成更多的候選者,QuickSi本身沒有過濾算法,實驗是使用NLF作為替代與其他算法進(jìn)行對比。PE在大部分?jǐn)?shù)據(jù)集上都獲得了比其他算法更少的候選者,這表明PE具有更強(qiáng)的過濾能力。由于Human是密集的,WordNet中的大多數(shù)頂點(diǎn)具有相同的標(biāo)簽,PE在這兩個數(shù)據(jù)圖上過濾效果對比其他算法更加顯著。

圖5 真實數(shù)據(jù)集的索引大小

(2)索引時間。

不同算法在6個數(shù)據(jù)集上的索引時間如圖6所示。可以看到QuickSi通常比其他算法運(yùn)行得更快,因為QuickSi使用的過濾算法NLF只有一趟候選集生成過程。NLF算法在Human和WordNet索引建立時間優(yōu)勢更加明顯,因為其他算法在密集數(shù)據(jù)圖和標(biāo)簽種類少的數(shù)據(jù)圖計算量更大,性能更差。PE在標(biāo)簽類別多的HPRD和Yeast時間略慢于CFL,但是在其他四個數(shù)據(jù)圖有一定優(yōu)勢。從整體性能表現(xiàn)上來看,PE還是最具有競爭力。

圖6 真實數(shù)據(jù)集的索引建立時間

4 結(jié)束語

為了提高子圖匹配算法的性能,提出了一種基于預(yù)處理-枚舉的子圖匹配算法(PE)。該算法在預(yù)處理階段,通過將過濾階段分為索引順序生成、自前向鄰居生成候選集和自后向鄰居對候選集進(jìn)行精化,以得到一個更小的候選集。同時,為了提高稀疏圖查詢的效率,在生成匹配順序時,將頂點(diǎn)的候選集大小和度作為條件進(jìn)行計算,以解決現(xiàn)有排序策略只考慮候選頂點(diǎn)數(shù)量的問題。模擬實驗結(jié)果表明,基于預(yù)處理-枚舉的子圖匹配算法(PE)與現(xiàn)有算法相比,在候選集過濾效果及匹配速度上有一定的優(yōu)勢,具有更好的整體性能。