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

巴倫敦,梁 平,顧進廣

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

0 引 言

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

圖1 查詢圖與數據圖

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

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

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

1 相關定義

1.1 圖與子圖匹配

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

表1給出了與子圖匹配相關的經常使用的一些符號的定義。定義1～定義2給出了子圖同構及子圖匹配的定義。

表1 常用符號定義

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

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

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

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

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

1.2 候選頂點集與匹配順序

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

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

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

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

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

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

算法1:PE算法

輸入:查詢圖q和數據圖G

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

1.begin

/*提取候選集 */

2.C← ExtractCandidates(q,G);

/*生成匹配順序 */

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

/*建立輔助數據結構 */

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

/*枚舉方法 */

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

2.1 過濾方法

通過枚舉查找所有的匹配結果前,為了降低枚舉的耗時,在獲得一個完整候選集的前提下,需要通過過濾算法讓候選集盡可能的小。目前大部分算法直接采用標簽和度過濾方法(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得到新的生成規則1和過濾規則1,以提高算法在提取候選集時的過濾能力。

除了候選頂點集,還設計了一個輔助數據結構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'≠?。

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

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

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

2.2 匹配順序

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

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

輸入:查詢圖q,數據圖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 枚 舉

枚舉算法采用遞歸的方式來查找所有的匹配,為了方便計算,在輔助數據結構A中維護了候選點之間的邊。

算法4:Enumerate(枚舉)

輸入:查詢圖q,數據圖G,候選集C,輔助數據結構A和匹配順序π

輸出:子圖匹配結果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 實驗結果及分析

3.1 實驗環境

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

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

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

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

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

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

表2 數據圖集及其屬性

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

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

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

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

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

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

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

3.2 實驗結果分析

3.2.1 算法整體性能

算法整體性能比較不同算法在不同數據集的執行時間和相對性能。在實驗中發現WordNet,Youtube和US Patents有相近的實驗結果,Human與Yeast實驗結果也相近。所以選擇了HPRD,Yeast和Youtube的實驗結果進行展示。

(1)執行時間。

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

圖2 數據集HPRD上的執行時間

圖3 數據集Yeast上的執行時間

圖4 數據集Youtube上的執行時間

(2)相對性能。

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

3.2.2 過濾方法性能

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

(1)索引大小。

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

圖5 真實數據集的索引大小

(2)索引時間。

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

圖6 真實數據集的索引建立時間

4 結束語

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