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

古險峰，程艷艷，楊立英

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

0 引 言

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

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

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

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

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

1 問題定義

本文針對帶頂點標簽的非定向圖G=(VG,EG,∑,l)。其中VG為頂點集合，EG?VG×VG為邊集合，∑為標簽集，l表示將一個頂點映射到其標簽的函數。在子圖查詢中，G稱為數據圖。查詢圖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和數據圖G，則子圖匹配問題為枚舉Q在G中的所有子圖同構嵌入。

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

2 提出的算法

2.1 基本框架思想

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

表1 使用的符號及說明

2.2 死端模式剪枝

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

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

(1)

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

2.3 死端模式管理

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

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

2.3.2 數值表示的死端模式

(2)

(3)

Φ[μ]=?

(4)

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

2.4 子圖匹配算法

輸入：查詢Q，數據圖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，操作系統是Ubauntn 12.04，編譯環境是gcc/c++。對比兩種不同算法，綜合比較了精確度和查詢效率，同時分析了不同頂點查詢數目的影響。

3.1 數據集

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

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

3.2 精確度比較

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

表2 酵母數據集上的精確度結果/%

表3 DBLP數據集上的精確度結果/%

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

3.3 查詢處理時間比較

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

3.4 頂點查詢數的影響

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

4 結束語

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