巴倫敦,梁 平,顧進廣

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

0 引 言

近年來,圖在各個領域發(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é)果。子圖匹配具有廣泛的應用場景,如生物信息學[1-2]、社會網(wǎng)絡分析[3-4]、化學復合搜索[5-6]等。在這些應用中,子圖匹配是整體性能的瓶頸,因為它是典型的NP-hard問題之一[7-8]。

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

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

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

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

1 相關定義

1.1 圖與子圖匹配

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

表1給出了與子圖匹配相關的經(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 候選頂點集與匹配順序

定義3～定義6給出了與候選頂點集及匹配順序相關的一些定義。

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

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

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

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

算法1給出了PE算法描述,它以q和G作為輸入,輸出從q到G的所有匹配。首先為每個查詢頂點提取G中的候選者,提取過程在算法2進行了詳細描述(第2行)。接下來,生成匹配順序π,在算法3給出了匹配順序的計算過程(第3行)。第4行建立輔助數(shù)據(jù)結(jié)構(gòu)A。將這三個步驟稱為索引階段。在索引階段之后,枚舉階段基于輔助數(shù)據(jù)結(jié)構(gòu)A沿匹配順序π遞歸地擴展部分結(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é)果前,為了降低枚舉的耗時,在獲得一個完整候選集的前提下,需要通過過濾算法讓候選集盡可能的小。目前大部分算法直接采用標簽和度過濾方法(LDF)或鄰居標簽頻率過濾方法(NLF)來進行過濾。LDF基于L(u)和d(u)生成候選集,C(u)={v∈V(G)|L(v)=L(u)∧d(v)≥d(u)}。NLF利用u的鄰居頂點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提取的候選集存在大量錯誤候選頂點,所以該文利用下述定理1得到新的生成規(guī)則1和過濾規(guī)則1,以提高算法在提取候選集時的過濾能力。

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

定理1:假設對于每個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);

/*前向鄰居頂點生成候選集 */

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

2.2 匹配順序

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

算法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中維護了候選點之間的邊。

算法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:基于預處理-枚舉的子圖匹配算法。

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

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

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

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

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

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

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

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

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

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

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

實驗運行環(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é)果進行展示。

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

不同算法在三個數(shù)據(jù)集上的執(zhí)行時間如圖2～圖4所示,其中每個數(shù)據(jù)集都按稠密查詢圖及稀疏查詢圖規(guī)模來顯示實驗結(jié)果。可以發(fā)現(xiàn)所有算法通常在更大的查詢上花費更多的時間,相比于非稀疏查詢圖,稀疏查詢的查詢難度可能會提高不止一個數(shù)量級。PE,QuickSi,GraphQL和CFL的性能在不同的數(shù)據(jù)圖上有所不同。PE在不同數(shù)據(jù)圖上始終優(yōu)于其他算法,這證明了PE的效率和穩(wěn)定性。GraphQL,CFL和PE之間的性能差距在HPRD上很小,因為大量不同的標簽使得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)相對性能。

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

3.2.2 過濾方法性能

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

(1)索引大小。

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

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

(2)索引時間。

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

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

4 結(jié)束語

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