基于回溯模式總結的魯棒近似子圖查詢算法

古險峰，程艷艷，楊立英

(1.鄭州工業(yè)應用技術學院 信息工程學院，河南 鄭州 451100； 2.吉林大學 應用技術學院，吉林 長春 130022)

0 引 言

圖數(shù)據(jù)在網(wǎng)頁鏈接結構、社會關系和金融交易等各種信息分析中發(fā)揮著重要作用。近似子圖查詢[1]是一種典型的圖數(shù)據(jù)操作，即在數(shù)據(jù)圖中對一個查詢圖的同構嵌入進行枚舉。圖數(shù)據(jù)庫上的流行查詢語言有SPARQL、Cypher等[2]。此外，在惡意軟件檢測[3]、復雜網(wǎng)絡分析[4]等數(shù)據(jù)分析中，子圖匹配也是必不可少的組件。由于子圖匹配是NP困難問題，其較高計算成本限制了實用價值。

近似子圖查詢的研究主要針對兩類問題而設定。

第一類問題是針對一個查詢圖枚舉同構子圖。如Antonino等[5]利用數(shù)據(jù)圖和查詢圖生成樹之間的近似同構，利用啟發(fā)式算法過濾候選頂點。也有很多方法[6,7]通過圖結構分析來縮小回溯法的搜索空間。但這類方法一般不能在搜索樹中進行剪枝操作。Xu等[8]提出一種基于卡方統(tǒng)計的改進型近似子圖匹配方法。但該方法不能有效處理具有相同局部結構且頻繁出現(xiàn)的復雜圖。

第二類問題是“一對多”：取一個查詢圖和很多個小數(shù)據(jù)圖，找到包含該查詢圖的數(shù)據(jù)圖。大部分研究著眼于如何總結數(shù)據(jù)圖，對路徑和頻繁子圖[9]進行捕捉。如Guan等[10]提出資源描述框架(resource description framework，RDF)的三元組模式，提高了面向RDF圖的子圖查詢效率。Chen等[11]提出一種基于馬爾科夫鏈蒙特卡羅框架的子圖學習方法，該方法的優(yōu)點是可以減少離散值的影響。

目前很多方法的性能取決于給定圖的結構，在穩(wěn)定性和精確度方面有待提高，因此，提出的子圖查詢算法沒有在回溯之前進行結構分析，而是在回溯過程中執(zhí)行剪枝。當部分嵌入導致搜索失敗時，可以提取并記錄下不能導向同構嵌入的模式，本文主要創(chuàng)新之處是：①利用回溯提供的信息降低了對圖結構的敏感性，由此大幅減少搜索失敗的數(shù)量；②僅對無用的部分嵌入進行剪枝，從而對所有的同構嵌入完成精確枚舉。

1 問題定義

本文針對帶頂點標簽的非定向圖G=(VG,EG,∑,l)。其中VG為頂點集合，EG?VG×VG為邊集合，∑為標簽集，l表示將一個頂點映射到其標簽的函數(shù)。在子圖查詢中，G稱為數(shù)據(jù)圖。查詢圖Q=(VQ,EQ,∑,l)，其中，頂點編號為u1,u2,…,un。

(1)標簽約束： ?ui∈VQ，l(ui)=l(M[ui])；

(2)邊約束： ?(ui,u′i)∈EQ， (M[ui],M[u′i])∈EG；

(3)注入約束： ?ui,u′i∈VQ，ui≠u′i?M[ui]≠M[u′i]。

定義2 子圖匹配：給定查詢圖Q和數(shù)據(jù)圖G，則子圖匹配問題為枚舉Q在G中的所有子圖同構嵌入。

子圖匹配要求對所有嵌入進行枚舉，但這經(jīng)常是無法實現(xiàn)的，因為嵌入數(shù)量可能會產(chǎn)生海量組合。因此在實踐中，當發(fā)現(xiàn)的嵌入數(shù)量達到指定閾值時即會停止枚舉[12]。本文使用的重要符號見表1。

2 提出的算法

2.1 基本框架思想

所提方法的核心思想是從回溯過程中出現(xiàn)的搜索失敗模式中進行學習，以避免重復相同的失敗，其基本框架如圖1所示。當部分嵌入中包含的頂點映射違反了定義1中3個約束的任何一個約束時，會發(fā)生搜索失敗。只要部分嵌入中包含一個會造成搜索失敗的映射，那么無論其它映射如何改變，其都會導致搜索失敗，基于這一點，所提方法會在每次遇到搜索失敗時提取出違反約束的模式(即映射集合)。在后續(xù)搜索中對與提取出的模式相匹配的部分嵌入進行剪枝。因此，所提方法通過避免搜索失敗提升了近似子圖查詢的性能。

表1 使用的符號及說明

2.2 死端模式剪枝

“死端”是指回溯搜索中永遠得不到完整嵌入的路徑。具體定義如下：

定義3 死端模式：設D為一個部分嵌入。若不存在能夠滿足D?M的完整嵌入M，則D是死端模式(或簡單稱為死端)。當且僅當D為死端時，判定Dead(D)為真。

(1)

圖2給出了一個本文方法中的死端剪枝示例，在回溯過程的搜索樹中，當部分嵌入導致搜索失敗時，提取并記錄下不能導向同構嵌入的頂點映射模式。在后續(xù)的搜索中，進行失敗模式匹配，這樣就可以顯著減少搜索失敗的數(shù)量。

2.3 死端模式管理

本文將死端模式記錄在集合D中，并對與D中的死端模式相匹配的部分嵌入進行剪枝。但由于存在空間和時間限制，該機制并不能直接實施。從空間角度，死端模式的數(shù)量最多可增加至候選頂點(即 |C[u1]| |C[u2]|…|C[un]|) 所有可能的組合數(shù)，該大小可能會超出存儲容量限制[14]。從時間角度，為進行剪枝操作，需要檢查部分嵌入中是否包含D中的死端模式。若在D上執(zhí)行線性搜索，并進行逐元素內容檢驗，則會產(chǎn)生不可接受的過大開銷。為使本文的剪枝具有可行性，提出了以下兩種對死端模式的管理方式。

2.3.1 固定散列表中的死端模式

2.3.2 數(shù)值表示的死端模式

(2)

(3)

Φ[μ]=?

(4)

整個匹配檢查可在O(1)時間內完成，因為訪問Δ和比較嵌入ID的時間復雜度為O(1)，所以死端剪枝的開銷較低。

2.4 子圖匹配算法

輸入：查詢Q，數(shù)據(jù)圖G；

輸出：G中Q的所有嵌入；

(3)ifk=|VQ|then

(5)return?

(6)C′←以邊約束定義的候選

(7)if存在ui滿足C′[ui]=?then

(9)else

(10) Γ*←?

(11)foreachv∈C′[uk1]do

(15) Γ*←Γ*∪Δ[uk+1,v]

(16)else

(18) ?！?

(21)returnΓ

(22)return?

3 實驗與分析

實驗平臺是Intel酷睿i3雙核2.40 GHz，RAM為4.0 GB，操作系統(tǒng)是Ubauntn 12.04，編譯環(huán)境是gcc/c++。對比兩種不同算法，綜合比較了精確度和查詢效率，同時分析了不同頂點查詢數(shù)目的影響。

3.1 數(shù)據(jù)集

實驗采用兩種不同的數(shù)據(jù)集：酵母細胞數(shù)據(jù)、數(shù)字書目索引和圖書館項目(digital bibliography & library project，DBLP)，其中，酵母細胞數(shù)據(jù)集[15](http://www.imcb.osaka-u.ac.jp/nakai/psort.html)中包含3112個頂點、12 519條邊和71個頂點標簽。DBLP[16](www.informatik.uni-trier.de/ley/db/)是參考文獻數(shù)據(jù)集，包含數(shù)據(jù)庫挖掘、信息檢索等。作者用節(jié)點表示，標簽表示研究方向，邊表示作者間的關系。共有標簽數(shù)3752，節(jié)點數(shù)797 787，邊數(shù)1 301 298。

實驗中，每種算法均處理一個包含10 000條查詢的查詢集。查詢集在查詢圖中的頂點數(shù)量各有不同。若算法無法在12 h內完成查詢集的處理，則考慮該處理是未能完成的任務(mission not finished，MNF)，在得到1000個嵌入后就停止枚舉操作。

3.2 精確度比較

實驗所用的度量是平均準確度(P)，召回率(R)，以及F1測度(F1)，F(xiàn)1測度是P與R的調和平均值，F(xiàn)1測度越高表示綜合水平越高。對于查詢圖考慮兩種情形，一種是無噪聲的；另一種查詢圖是由目標圖子集加一部分結構噪聲構成。比較了文獻[8]的卡方統(tǒng)計法和文獻[5]提出的啟發(fā)式算法，在酵母數(shù)據(jù)集和DBLP數(shù)據(jù)集上的評價結果見表2和表3。

表2 酵母數(shù)據(jù)集上的精確度結果/%

表3 DBLP數(shù)據(jù)集上的精確度結果/%

由表2和表3可知，無噪聲和有結構噪聲的兩種情形，本文算法均表現(xiàn)出較高的平均準確度、召回率和F1測度，在酵母數(shù)據(jù)集上的平均F1測度達90.98%，在DBLP數(shù)據(jù)集上的平均F1測度達89.14%。此外，本文算法對有結構噪聲的敏感性很弱，即，無噪聲和有結構噪聲的結果差異很小，說明魯棒性較好。這主要是因為本文利用回溯提供的信息，降低了對圖結構的敏感性?？ǚ浇y(tǒng)計法也具有相似特征，這是因為少量的結構噪聲不能影響卡方值的計算。但啟發(fā)式算法表現(xiàn)出更大的波動，這可能與啟發(fā)式算法在搜索頂點解時，結構噪聲影響了初始解，導致后續(xù)求解過程的偏差。

3.3 查詢處理時間比較

本小節(jié)比較不同算法的處理時間，以評估死端剪枝的性能收益。其結果如圖3所示。當酵母數(shù)據(jù)集上和DBLP數(shù)據(jù)集上的查詢頂點數(shù)分別達到40個和14個時，所有算法均為MNF。總之，所提算法在幾乎所有查詢大小和數(shù)據(jù)集上均取得了較優(yōu)性能，對于大型查詢更是如此。例如，對于酵母數(shù)據(jù)集上的26～36個頂點的查詢，卡方統(tǒng)計法[8]和啟發(fā)式算法[5]處于MNF狀態(tài)，而本文算法的每個查詢時間較低，因此性能更好。這是因為卡方統(tǒng)計法和啟發(fā)式算法的有效性很大程度上取決于給定圖的結構。該問題在較大查詢數(shù)中更加明顯，這是因為較大查詢包含更多的候選頂點組合數(shù)，卡方統(tǒng)計法和啟發(fā)式算法需要搜索的組合數(shù)更多。與之相比，本文算法通過死端剪枝，避免了不必要的搜索。由此降低了對圖結構的敏感性。這也驗證了所提算法能夠降低處理時間，且對大型查詢同樣有效。

3.4 頂點查詢數(shù)的影響

為進一步分析所提算法的性能，實驗分析了不同頂點查詢數(shù)，算法中SEARCH函數(shù)的遞歸調用次數(shù)，比較本文算法與其它算法的(即不包含本文子圖匹配算法的第(14)行和第(15)行)調用次數(shù)。最終的結果如圖4所示，其中，酵母數(shù)據(jù)集上設置了20個以內的頂點查詢，DBLP數(shù)據(jù)集上設置了9個以內的頂點查詢。不同算法處理過程中的遞歸調用次數(shù)如圖4所示，可以看出，對于較小查詢，剪枝數(shù)量很少，但隨著查詢大小的增加，剪枝數(shù)量也會增加。例如，對于酵母數(shù)據(jù)集上的18個頂點的查詢，啟發(fā)式算法約遞歸6.6×1010次，卡方統(tǒng)計法的遞歸次數(shù)也有1.1×108次，而本文算法則僅遞歸約2.3×107次。這是因為較大的查詢會涉及到更多的搜索失敗。隨著查詢圖中頂點和邊的數(shù)量增加，單射性約束和邊約束的違反次數(shù)也會增加。本文算法通過降低由這些原因引起的搜索失敗，顯著提高了性能。同時，本文算法對于較小查詢也表現(xiàn)出較好性能。這是因為與死端模式的高效管理相比，死端剪枝的開銷是非常小的。

4 結束語

子圖匹配是一個NP困難問題，其計算成本非常高。為此，本文提出了一種子圖匹配算法，在回溯過程中利用會導致搜索失敗的部分嵌入來生成死端模式，并在回溯的后續(xù)過程中，對與死端模式相匹配的部分嵌入進行剪枝。實驗結果表明，所提算法優(yōu)于其它同類方法。未來，本文將探討該算法是否可以推廣到其它應用領域，比如生物蛋白網(wǎng)絡的全局查詢對比、RDF動態(tài)數(shù)據(jù)平臺的圖查詢問題等。