基于坐標映射及多重圖劃分的圖相似查詢研究

劉哲峰,梁 平,顧進廣

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

0 引 言

隨著信息技術的迅速發展,所獲得的數據呈爆炸式增加。根據國際數據公司(IDC)的統計,互聯網上的數據每年將增長50%以上,而且世界上90%以上的數據是最近幾年產生的[1]。這些數據中,容量巨大、結構復雜、種類繁多而且語義多變的數據占據了很大比例[2-3]。

總體而言,在數據及數據間的關系飛速增長的時代,圖數據庫被應用到越來越多的領域,如機電電力[4-5]、醫學信息[6]、信用卡欺詐檢測[7]等。而圖形的激增也激發了人們對在大型圖數據庫中實現高效訪問功能和靈活的結構感知查詢的興趣[8]。關于圖數據庫的查詢方式,有檢索條件約束[9]以及查詢結果約束兩大類,而基于查詢結果約束,已經出現了許多相關的研究,它們可以大致分為兩類:圖精確搜索[10-11]和圖相似性搜索[12-13]。與精確搜索相比,相似性搜索可以提供一種魯棒的解決方案,允許容錯并支持搜索未精確定義的模式。

兩個標記圖之間的相似性計算是圖相似性搜索的核心操作,目前最主要的相似性度量為:圖編輯距離[13-14]、最大公共子圖[15-16]、圖對齊[17]和圖核函數[18-19]。該文考慮基于圖編輯距離(GED)約束定義的相似性搜索問題,主要是因為其通用性和廣泛的適用性[20],GED是一種幾乎適用于任何類型的圖形的度量。直觀的圖編輯操作可以精確捕捉與圖形結構和內容相關的任何細粒度差異[21]。典型的編輯操作[22]是插入和刪除頂點或邊以及重新標記頂點或邊。

該文研究了以下圖相似性搜索問題:給定一個圖數據庫G={g1,g2,…,gn}和一個查詢圖q,需要找到圖G中的所有圖g,使其相對于查詢圖q的圖編輯距離GED(g,q)在用戶指定的閾值τ內。

然而,GED的計算是NP-hard,因此計算所有查詢圖q和g∈G的GED可能會導致較差的計算效率。現有的解決方案大多采用過濾驗證框架來加快圖形的相似性搜索。在過濾階段,通過種種算法相對快速地評估出一個GED下界,它被用于從圖數據庫中修剪盡可能多的假陽性圖,剩下的圖構成候選集C。在驗證階段,必須在q和每個候選圖之間執行GED計算來驗證。

到目前為止,已經提出了不同的GED下界[13,21,23-24],這些技術具有一些缺點:(1)對于圖數據庫G中的所有數據圖進行GED下界的評估,沒有考慮到圖規模的差距,會導致很多無意義的GED下界計算;(2)過于寬松的GED下界并沒有保證其過濾能力,導致很多假陽性圖無法識別;(3)GED下界評估耗時,會帶來較高的驗證成本。

該文考慮了一種基于坐標映射的多重圖劃分方法。首先,將圖數據庫以及查詢圖進行坐標系的映射,并以此為基礎構建坐標系上的查詢矩形對圖數據庫中不符合條件的圖進行粗粒度過濾,以降低后續圖劃分的計算成本。這種過濾方式十分快速,但是并不精密;然后,使用基于參數的圖劃分的選擇性計算方法有效地控制圖劃分的隨機性,并基于該方法得到有效的GED下界,來提升過濾精度;最后,通過不同的劃分方式以及參數控制構建不同的索引集,以實現多層索引過濾,更進一步提升過濾的精度。

1 問題定義

1.1 圖與相似查詢

該文采用的圖均為簡單的、無向的標記圖。圖g定義為一個四元組(Vg,Eg,lg,Σ),其中Vg是頂點集;Eg?Vg×Vg是邊集;lg:Vg∪Eg→Σ是一個標簽函數,其中Σ是頂點和邊的標簽集。

圖g可以被執行的圖編輯操作為:(1)刪除一條邊;(2)在兩個頂點間插入一條邊;(3)修改一條邊的標簽;(4)刪除一個孤立的頂點;(5)插入一個孤立的頂點;(6)修改一個頂點的標簽。

定義1(相似查詢):給定一個圖數據庫G={g1,g2,…,gn},一個查詢圖q和一個GED閾值τ,相似查詢的問題是找到一個數據圖gi∈G,使得GED(gi,q)≤τ。

1.2 半邊圖與圖劃分

定義2(半邊圖):半邊圖g=(Vg,Eg,lg,Σ),其中,Eg?Vg×(Vg∪{*})是一個可能存在半邊(u,*)∈Eg的圖,其中一個關聯頂點u∈Vg是一個確定的頂點,但該半邊的另一個頂點(及其標號)沒有明確的指定,表示為*。

定義3(圖劃分):圖g可以劃分為集合窮舉、互斥和非空半邊圖的集合p,如下所示:

P(g)={pi|∪iVpi=Vg'∪iEpi?Eg∪Vg×{*},pi∩pj=?,?i,j≠j}

其中,P被稱為g的一個劃分。

將圖劃分為半邊子圖對GED有一個明顯的優勢,就是在給定任何圖編輯操作的情況下,它最多只能影響一個半邊圖的劃分。

2 基于坐標映射的多重圖劃分

2.1 坐標映射

在現實的圖數據庫中,圖的規模均有較大的差異,而在圖編輯操作中,對于頂點和邊的刪除或增加均是從圖規模上進行操作。基于這一點,設計了一個坐標映射的批量過濾方法。

對于任一數據圖g,將其以坐標(|Vg|,|Eg|),也就是基于頂點-邊的方式,映射于二維坐標系中,其中,x坐標和y坐標分別代表圖g的頂點數和邊數。因此,對于圖數據庫G,可以獲得點集{(|Vg|,|Eg|):g∈G},而這些點可以組成一個矩形區域A=[xmin,xmax]×[ymin,ymax],其中xmin/xmax和ymin/ymax分別是節點和邊的最小數量和最大數量。

定義4(查詢矩形):給定一個查詢圖q和閾值τ,查詢矩形Aq被定義為由點集{(x,y):|x-|Vq‖+|y-|Eq‖≤τ}組成的矩形。

對于一個數據圖g,如果GED(g,q)≤τ,那么必定會有:‖Vg|-|Vq‖+‖Eg|-|Eq‖≤τ。由此可以在矩形區域A中進行圖規模上的批量過濾,圈定出如圖1所示的查詢矩形Aq。

圖1 圖數據庫的坐標矩形A和查詢矩形Aq

坐標映射的著眼點在于圖的大小,考慮的是一種邊界情況,這有助于從圖規模上剔除了那些不符合要求的圖,是一種粗粒度的過濾手段,以減少后續精細過濾的時間開銷。因此,經過這坐標映射這一層的粗粒度過濾之后,所需要參與后續多重圖劃分的細粒度過濾的數據圖數量明顯減少,能顯著加快后續細粒度過濾方法的索引構建時間。

算法1給出了坐標映射方法的算法描述。首先,初始化坐標矩形A的最大值和最小值(行1);然后,對于圖數據庫中的每個圖,計算其頂點數和邊數并更新A的最大值和最小值(行2～6),并將其坐標存儲到坐標矩形A中(行7);接著,使用查詢圖的頂點數和邊數計算查詢矩形Aq,并找到與查詢圖相似的圖的坐標(行9～11);最后,返回坐標矩形A和查詢矩形Aq(行12)。

算法1:坐標映射方法

輸入:圖數據庫G; 閾值τ;查詢圖q;

輸出:坐標矩形A和查詢矩形Aq

1→xmin=infinity,xmax=-infinity,ymin=infinity,ymax=-infinity;

2→for eachginGdo

3→····if |Vg|

4→····if |Vg|>xmaxthenxmax=|Vg|;

5→····if |Eg|

6→····if |Eg| >ymaxthenymax=|Eg|;

7→····A.add((|Vg|, |Eg|));

8→Aq= set();

9→for eachginGdo

10→··if abs(|Vg|-|Vq|) + abs(|Eg|-|Eq|) ≤τthen

11→······Aq.add((|Vg|, |Eg|))

12→returnA,Aq

2.2 參數化的GED下界

由1.2中的定義3,可以推導出如下定理:

定理1:給定一個圖g,該圖被劃分為(τ+k)個半邊圖,該半邊圖的集合為P(g),其中τ為閾值,k(k≥1)是一個整數參數。對于給定的查詢圖q,如果GED(g,q)≤τ,則在半邊圖集合P(g)中至少存在k個半邊圖:pi1,pi2,…,pik∈P(g),滿足pil?q(1≤l≤k)。

對于任意數據圖g∈G,其分區集合為P(g)={p1,p2,…,pτ+k},如果pi?q,則稱pi為匹配分區,否則稱其為不匹配分區。根據定理1,如果分區集合P中的匹配分區數小于k,則圖編輯距離GED(g,q)必然是大于τ的,由此可判斷出g是一個假陽性圖,大大節約了時間成本。同時,為了更好地了解圖劃分方法的使用,給出了例子1進行說明。

例子1 對于圖2中的數據圖g1以及查詢圖q,假設閾值τ=2。令整數參數k=2,那么g1需要劃分出四個半邊圖。對于圖g1的劃分P(g1)如圖2所示。因為P(g1)相對于圖q來說有三個不匹配分區:p1,p2和p4。因此g1是一個假陽性圖。

圖2 g1的四個半邊圖:P(g1)={p1,p2,p3,p4}

定理1提供了一個參數化的,基于分區的GED下界,通過設置不同的k值,就可以生成一系列新的GED下界。同時當k取不同的值時,新生成的GED下界的過濾能力也具有了一定的差異。當k=1時,實例化的GED下界歸結為一個特殊的降級情況。對于給定的一個假陽性圖g∈G,它的(τ+1)個分區,可以很容易地找到1個(k=1)匹配分區,一旦找到,g將被錯誤的納入候選圖中,然而當k>1時,g作為假陽性圖將更有可能被識別和過濾,因為從g中檢測k>1個匹配分區的可能性要遠小于k=1時。

因此,k>1時,它比k=1這種退化情況更有可能識別出假陽性圖。當k>1時,GED下界可以實例化為一系列更緊密的下界,對相似性搜索具有更好的過濾能力。

2.3 選擇性圖劃分

對于給定的任意一個數據圖來說,可以有很多種劃分方法,能將其劃分為(τ+k)個不同大小和結構分區。因此如果不加以限制,圖劃分方法會充滿隨機性,針對這種情況同樣給出了例子2進行說明。

例子2 同樣是圖2中的數據圖g1,如果采用圖3的劃分方式,P1(g1)中,p2和p3均為匹配分區,此時數據圖g1會通過篩選。

圖3 g1的四個半邊圖:P1(g1)={p1,p2,p3,p4}

為了對這種隨機劃分方式進行限制,為每個分區賦予了一個如式1所示的選擇性增益s(pi),它表明如果g是假陽性圖,pi作為不匹配分區pi?q的選擇性有多高,其中f()是圖數據庫G中的頂點/邊的標簽頻率。為此,對于數據圖的最優劃分的目標是將數據圖劃分為具有最高總體選擇值的(τ+k)個分區。

(1)

式中,s(pi)的值受兩個因素的影響:

(1)分區大小:較大的分區更有可能受圖編輯距離的影響,從而使得該分區成為不匹配分區的概率更大;

(2)頂點/邊標簽的頻率:在查詢圖q中,標簽頻率在G中較小的分區可能按比例很少出現。因此,包含低頻率頂點/邊的分區更有可能是不匹配分區。

選擇性劃分的算法如算法2所示。對于輸入的數據圖g,首先創建一個布爾數組M,它表示是否將頂點v分配給某個分區,并將M初始化為false(行1);同時初始化另一個集合Una,它保存即將處理的數據圖g的未分配頂點,初始化為空(行2);接下來選擇τ+k個頂點,以此作為τ+k個分區的初始頂點,同時這些頂點的相鄰且未被分配的頂點N(·)添加到Una中,這些存放在Una中的頂點將在下一步中考慮用于分區分配(行3～8);接著通過評估將每個頂點v分配給每個現有分區pi的選擇性增益(由式1計算)來檢查每個未分配的頂點,使得每個頂點分配到該分區后具有最大的選擇性增益,并將頂點v的相鄰且未被分配的頂點添加到Una中(行9～15);在所有頂點都分配完成后,就需要開始考慮跨區的邊,并將它們作為半邊分配給其中一個參與分區,同樣需要計算所分配半邊的選擇性增益(行16～22)。這樣通過貪心算法,將每一個除了初始化頂點以外的頂點和跨分區的邊進行選擇性增益的計算,最終返回相對最優的分區集合。

算法2:選擇性圖劃分

輸入:數據圖g,閾值τ,參數k,查詢圖q

輸出:圖劃分P(g)={p1,p2,…,pτ+k}

1→for eachv∈VgdoM[v]=false;

2→Una = ?*, /*Una為未分配頂點集合*/

3→fori=1 toτ+kdo

4→····for onev∈VgandM[v]== false

5→········pi={v};

6→········M[v]= true;

7→········for eachu∈N(v),M[u]==false andu? Una

8→············Una = Una∪{u};

9→for eachv∈Una

10→··fori=1 toτ+kdo

11→······ei=s(pi∪{v})-s(pi);

13→··M[v]=true;

14→··for eachu∈N(v),M[u]==false andu? Una

15→······Una = Una∪{u};

16→for each (u,v)∈Eg,uandv∈pi,i≠j

17→··ei=s(pi∪(u, *))-s(pi);

18→··ej=s(pi∪(v, *))-s(pi);

19→··ifei≥ejthen

20→······pi=pi∪{(u, *)};

21→··else

22→······pi=pi∪{(v, *)};

23→returnP(g)={p1,p2,…,pτ+k}

頂點和邊標簽的頻率可以在構建坐標矩形階段進行一次預計算,因此,該算法的時間復雜度為O((τ+k)|Vg|+|Eg|)。

2.4 標簽頻率表與倒排索引

上述的選擇性圖劃分方式給原本的隨機劃分提供了一個約束,使得不穩定的隨機劃分變的更加可控。然而半邊子圖的匹配算法同樣具有很高的代價,因此為了進一步降低半邊子圖匹配的驗證成本,可以構建以下兩個表進行進一步過濾:

(1)標簽頻率表:為分區p構造一個標簽頻率表R(p),其中存儲分區p的頂點和邊標簽的頻率。在執行半邊子圖同構的計算之前,首先比較它們的頻率表R(p)和R(q):對于R(p)中每個頂點/邊標簽的頻率不應該超過R(q),記為R(p)≤R(q),這樣可以節省半邊子圖同構的計算代價;

(2)倒排索引:為圖g的一個劃分p構建一個倒排索引I(p)。對于給定的查詢圖q,如果p?q,可以在圖數據庫G中快速找到包含劃分p的所有數據圖。這樣,在進行完必要的劃分p的半邊子圖同構計算后,可以通過倒排索引找到所有包含劃分p的數據圖,以此減少大量的計算。

通過構建與維護上述兩個表單,將子半邊子圖匹配的過程同樣劃分為過濾-驗證兩個部分,以進一步壓縮計算成本。

2.5 多層索引

雖然可以基于上訴方法選擇一個緊湊的、基于劃分的GED下界,并利用選擇性劃分的方法產生相對優秀的半邊子圖,然而可能仍然有一些假陽性圖未被識別。因此選擇采用多層索引結構來對圖數據庫進行過濾。

為了充分利用多個GED下界,采用集中過濾策略,考慮了L種不同的圖劃分方法,P1,P2,…,PL,其中Pi將g∈G劃分為(τ+ki)個分區。具體來說,在第i層,評估由ki參數化的第i個GED下界,并生成候選圖Ci,并由該候選圖Ci繼續進行下一層的過濾,當且僅當通過了所有層的GED下界評估之后,才能得到最終的候選集C。

為了保證索引分區和GED下界約束能在多層索引結構的不同層之間顯著變化,考慮了以下策略:

(1)在不同層應用選擇性分區方法時,從數據圖g中隨機選擇初始節點;

(2)在不同層間選擇不同的參數ki的值。

這樣可以使用相同的選擇性分區方法,通過不同的初始節點和不同的參數ki,保證每層索引都能產生不同的分區索引集,以此為GED下界提供嚴密性保證。

3 實驗結果及分析

3.1 實驗環境

為了檢測該算法的效率與準確性,將與Pars算法[23]進行對比實驗。Pars算法是采用單個降級GED下界(k=1)和隨機劃分進行索引生成和相似性搜索的圖索引方法,相較于其他的算法具有更好的效率,Pars算法所采用的半邊子圖同構算法與文中算法均為A*算法。同時為了體現坐標映射所帶來的性能提升,將對文中算法以及Pars算法進行有無坐標映射的對比實驗。

而對于文中算法,為了體現出在2.5節中提出的多層索引結構的過濾層數對算法的影響,實驗中選取雙層索引結構和三層索引結構進行對比。

隨機從NCI/NIH數據集中選擇10 000個圖作為數據集,并從中隨機選擇一個圖作為查詢圖。

在實驗中主要考慮了以下性能評估指標:

(1)索引構建成本:包括參與索引算法的圖數量、索引構建時間;

(2)候選圖數量:即在進行過濾之后所產生的候選圖數量;

(3)查詢執行時間:相似性搜索的真實響應時間,是候選集生成時間及GED驗證時間之和,同樣這里的時間是多次實驗后平均的響應時間。

實驗運行環境如下:Window11操作系統、16 GB內存的Core i7-11800H 2.30 GHz 8核電腦;Pars算法和文中算法均采用C++編程語言實現,編譯環境為Microsoft Visual Studio 2022。

3.2 實驗結果分析

3.2.1 索引構建成本

首先,在圖數據庫中評估不同方法的索引構建成本。值得注意的是,圖索引是離線預構建的,對于圖數據庫G,考慮GED閾值τ是很小的(τ≤4),其主要原因是用戶會更傾向于從圖數據庫中搜索相似的圖。

表1為在不同閾值τ下,無坐標映射和有坐標映射時,參與索引構建的數據圖數量。從表1可知,有坐標映射時,會過濾掉相當一大批從圖的規模上就不符合要求的數據圖,從而大大減輕了索引的構建負擔。同樣,當閾值越大時,說明用戶對相似度的要求越松,通過坐標映射的數據圖數量也會大幅度上升,但是哪怕閾值τ已經為6了,它仍然能過濾掉近2/3的數據圖。

表1 有無坐標映射時參與索引構建的圖數量

圖4表示在無坐標映射時Pars算法、采用雙層索引及采用三層索引的文中算法的時間開銷。可以看到可以有效構建多層索引。同樣,因為需要構建多層索引,以及需要選擇較好的圖劃分,多層索引在構建時間上略長于Pars算法的單層隨機劃分的索引。而隨著閾值τ的增加,這種索引構建時間的差距開始變的微不足道,這是因為當τ變得更大時,每個數據圖會相應地被劃分為更大數量的更小分區,從而導致半邊子圖同構計算加速,而半邊子圖同構的計算時間通常會占用總索引構建時間的90%以上。

圖4 無坐標映射的索引構建時間

表2給出了在AIDS中不同閾值、無標簽頻率表及倒排索引表的情況下,半邊子圖同構所需要的時間。之所以排除標簽頻率表和倒排索引表的干擾,是因為這兩者很大程度上會受到圖劃分的影響,若是采用隨機劃分方法,那么在不排除標簽頻率表和倒排索引表的情況下,半邊子圖同構時間會變的相對隨機,若是采用文中的選擇性劃分方法,那么半邊子圖同構時間的影響因子又會變的過多。從表2可以看出,隨著閾值的增大,半邊子圖同構的時間會被加速。

表2 半邊子圖同構時間

圖5表示在有坐標映射時,Pars算法、采用雙層索引和采用三層索引的文中算法的索引構建時間對比。從圖5可知,其與圖4變化趨勢不同:隨著閾值τ增大,索引構建的時間整體呈上升趨勢。結合表1可以發現,當閾值τ增大時,表明對查詢圖的相似性要求越來越低,通過坐標映射的圖的數量顯然會越來越多,這就導致了參與索引構建的圖的數量上升,因此在閾值變大的情況下,哪怕有著半邊子圖同構的計算加速,參與計算的圖數量顯然影響更大。

圖5 有坐標映射的索引構建時間

3.2.2 候選圖數量

其次,比較了不同方法所產生的候選圖數量。圖6表示Pars算法、采用雙層索引及采用三層索引的文中算法所產生的候選圖數量,其中Real表示實際的相似圖數量。從圖中可以看出,文中所采用的算法,其過濾出的候選圖始終小于Pars,哪怕是雙層索引結構都能比Pars算法減少近45%的假陽性圖。原因有兩個:首先,參數k>1的廣義GED下界比降級(k=1)的更緊密;其次,選擇性分區方法比Pars中的隨機分區更有效地生成高選擇性的索引分區,這有助于更進一步地過濾假陽性圖。另外,可以看到當索引層數增多,被過濾掉的假陽性圖也顯著增加,這表明多層索引方法具有更出色的過濾能力,與Pars的單層隨機劃分的方法相比,可以保證假陽性圖數量的減少。

圖6 候選圖數量

3.2.3 查詢執行時間

最后,評估了Pars算法、采用雙層索引及采用三層索引的文中算法的總體運行的時間成本。因為評估的是最終的候選圖及GED驗證的時間,故而有無坐標映射對該部分幾乎是沒有影響的。評估結果如圖7所示。可以發現,相比于隨機劃分的單層過濾方法Pars,文中的多層索引的過濾效果要更好,因為坐標軸是按指數增加的,所以就算看起來沒有增加多少,但實際上是差距越來越大的,這主要是因為多層索引所生成的候選集明顯更少,這樣總體運行時間才會更少,說明選擇性圖劃分方法的多層索引結構明顯具有更好的,更精確的過濾效果。

圖7 查詢執行時間

綜合上述的實驗結果可以得出以下結論:首先,基于坐標映射的預過濾方法可以有效減少參與后續細粒度過濾方法的數據圖數量,從而明顯減少細粒度過濾方法的索引構建時間;其次,雖然在索引構建階段,文中算法因為需要對分區質量進行調整,所以整體索引構建時間要略長于隨機劃分的Pars算法,但是圖6和圖7的實驗結果表明,其過濾性能與精度是要明顯優于Pars算法的,從整體的查詢速度來看,文中算法的整體查詢速度是要明顯優于Pars算法的。

4 結束語

相似性搜索問題在管理和查詢圖結構數據中起著最基本的和最關鍵的作用,并且在現實世界中大規模的圖數據庫中有廣泛的應用。該文探討了在圖編輯距離的約束下的相似性搜索問題,并在Pars算法的基礎上進一步引入多層索引結構來解決圖相似性搜索這一問題,同時針對多層索引結構的構建時間開銷過大的問題,提出了坐標映射的批量圖處理方式來有效減少過濾階段的時間成本。首先采用坐標映射來過濾掉一大批從規模上就超出相似度閾值的圖,然后使用參數化的、選擇性圖劃分方式的GED下界來過濾假陽性圖,以此使得圖劃分變得更加可控,同時通過倒排索引和標簽頻率表來減少子圖同構的時間開銷,最終通過生成多個索引集來對批量過濾后的圖再次進行交叉檢查,以此提升過濾的精度。這樣,在保證多層索引過濾精度的同時,使用坐標映射大大減少了時間成本。模擬實驗結果證明,坐標映射提升了算法的時間性能,而多層索引的引入提升了算法過濾的精度。