楊書新,譚 偉,魏朝奇

(江西理工大學(xué)信息工程學(xué)院，江西 贛州 341000)

1 引言

圖作為一種通用的數(shù)據(jù)結(jié)構(gòu)，能夠表示復(fù)雜的數(shù)據(jù)類型。近些年已經(jīng)在諸多領(lǐng)域得到了廣泛的應(yīng)用，包括生物領(lǐng)域(蛋白質(zhì)基因交互網(wǎng)絡(luò))、化學(xué)領(lǐng)域(化合物)、社會(huì)網(wǎng)絡(luò)社區(qū)、交通網(wǎng)絡(luò)等許多數(shù)據(jù)都利用圖來進(jìn)行建模。通過研究者的努力與研究，在圖數(shù)據(jù)管理及分析方面，已經(jīng)在一些基本問題上取得了一定的成果。例如，關(guān)于圖數(shù)據(jù)庫中頻繁模式挖掘算法的研究在近五年時(shí)間內(nèi)已經(jīng)出現(xiàn)至少10種新的算法。而今，越來越多的學(xué)者開始關(guān)注于圖數(shù)據(jù)的查詢領(lǐng)域。圖數(shù)據(jù)查詢大體分為兩類：精確查詢和近似查詢。

在圖數(shù)據(jù)查詢領(lǐng)域雖有不少研究，但是大部分的研究工作都集中在圖的精確匹配查詢，其算法有子圖查詢和超圖查詢兩大類。子圖查詢中Shasha D和Wang J T L在2002 年首先提出了基于路徑查詢的GraphGrep算法[1]，2004年在基于路徑查詢的基礎(chǔ)上Yan X等人[2]提出了利用頻繁子圖挖掘建立索引的gindex思想。Zou L等人[3]在2008年提出了基于樹結(jié)構(gòu)建立索引的 GCoding算法，其他算法還有GDIndex[4]、GString[5]等。超圖查詢中Chen等人在2007年提出cIndex[6]算法，利用contrast index得到不被q包含的索引模式。2009年Zhang S等人則從另一個(gè)角度出發(fā)，根據(jù)特征子圖的最優(yōu)排序提出了GPTree[7]算法，降低了查詢的時(shí)間復(fù)雜度。

精確匹配查詢雖然能夠準(zhǔn)確地找出目標(biāo)圖，但是由于真實(shí)數(shù)據(jù)庫的數(shù)據(jù)結(jié)構(gòu)復(fù)雜，圖數(shù)據(jù)庫具有信息不完整、含噪音等情形，精確查詢過程存在節(jié)點(diǎn)(邊)不匹配、節(jié)點(diǎn)錯(cuò)位、查詢條件苛刻等問題，往往無法得到我們實(shí)際想要的結(jié)果。然而，近似查詢有很好的容錯(cuò)性，對(duì)于節(jié)點(diǎn)的不匹配甚至圖結(jié)構(gòu)差異較大的情況，都能夠得到與查詢圖相近似的結(jié)果集。因此，近年來近似查詢開始越來越多地受到研究者們的關(guān)注。近似查詢可分為k-NN查詢和范圍查詢。k-NN查詢返回與查詢圖q最相似的k個(gè)結(jié)果，而范圍查詢則返回用戶定義的某個(gè)范圍內(nèi)的全部結(jié)果。目前研究者們對(duì)近似查詢的研究主要集中在以下三個(gè)問題：(1)如何有效存儲(chǔ)圖數(shù)據(jù)；(2)如何定義圖之間的相似度；(3)如何創(chuàng)建高效索引加速圖的匹配和查詢。

本文從索引構(gòu)建的角度出發(fā)，提出一種基于圖結(jié)構(gòu)分解的索引方法，對(duì)DAG圖(Directed Acyclic Graph)[8]建立索引，由查詢圖q的最小生成樹集進(jìn)行滿足條件θ的生成樹擴(kuò)展，通過索引得到近似結(jié)果集，減少近似查詢過程的子圖同構(gòu)驗(yàn)證次數(shù)，降低計(jì)算的復(fù)雜度，提高近似查詢的效率。

2 圖分解近似查詢算法

本文中的圖G可以采用一個(gè)五元組[8,9]來表示，G=(V,E,∑V,∑E,L)，其中V代表圖中節(jié)點(diǎn)的集合，E=V×V代表圖中邊的集合，∑V代表圖中所有節(jié)點(diǎn)標(biāo)號(hào)的集合，∑E代表圖中所有邊標(biāo)號(hào)的集合，L是標(biāo)號(hào)與節(jié)點(diǎn)或標(biāo)號(hào)與邊之間映射關(guān)系的函數(shù)，實(shí)現(xiàn)標(biāo)號(hào)向邊和節(jié)點(diǎn)的映射，即L：V→∑V,E→∑E。

在圖數(shù)據(jù)庫GD中，給定查詢圖q，圖近似查詢可以得到所有的滿足圖編輯距離[4]在θ內(nèi)的與q同構(gòu)的圖gi。存在特例θ=0，近似查詢問題也即是精確查詢。文獻(xiàn)[10]中提出了一種基于閉圖的圖近似匹配方法C-Tree，其定義了基于編輯距離的圖近似度，并且采用了啟發(fā)式圖匹配方法，提出了鄰接子樹和鄰接子圖方法在近似查詢中的應(yīng)用。但是，該算法僅僅能查詢到k個(gè)最近的近似結(jié)果。對(duì)于當(dāng)前信息數(shù)據(jù)的復(fù)雜化，其查詢結(jié)果及效率并不理想。因此，本文提出一種基于圖分解的近似查詢算法，提高查詢效率以及查詢結(jié)果集的完整性。本文算法通過對(duì)查詢圖q和圖數(shù)據(jù)G作DAG分解，利用分解后得到的DAG圖的哈希編碼構(gòu)建索引，通過q的最小生成樹集，枚舉生成滿足條件θ的生成樹，將其與DAG圖進(jìn)行快速驗(yàn)證，降低同構(gòu)測(cè)試次數(shù)，得到近似結(jié)果集，提高算法的查詢效率。

2.1 建立DAG索引

定義1(DAG圖) 將給定的圖g進(jìn)行圖分解，得到具有如下特點(diǎn)的結(jié)構(gòu)圖：

(1)任一節(jié)點(diǎn)P都是圖g的子圖；

(2)對(duì)節(jié)點(diǎn)P和Q而言，若P?Q，存在P指向Q的有向關(guān)系，則該分解稱為(圖的分解)DAG圖。

圖1給出了一個(gè)完全連通圖進(jìn)行分解后的DAG圖。DAG圖中有且只有一個(gè)節(jié)點(diǎn)ABBC代表圖G，有且只有一個(gè)節(jié)點(diǎn)表示空?qǐng)D。圖的分解DAG通過路徑反映出節(jié)點(diǎn)的尺寸大小和層次關(guān)系。如AB、AC、BB、BC具有相同的尺寸，即同一層上的節(jié)點(diǎn)具有相同的頂點(diǎn)數(shù)，而不同層之間則具有包含和被包含的關(guān)系。

Figure 1 Decomposition of graph in DAG圖1 圖分解DAG

本文對(duì)給定的查詢圖q和圖數(shù)據(jù)集G進(jìn)行DAG圖分解，得到的DAG圖將按照?qǐng)D的標(biāo)準(zhǔn)代碼[11]進(jìn)行編碼，采用哈希表完成索引的存儲(chǔ)與構(gòu)建。具體構(gòu)造DAG過程如下：

(1)選定一個(gè)空節(jié)點(diǎn)作為DAG起始的根節(jié)點(diǎn)。

(2)記特征圖中不重復(fù)的任意一個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)的下一級(jí)節(jié)點(diǎn)，在分解過程的每條路徑上，下一層總是比上一層多出一個(gè)節(jié)點(diǎn)。

(3)連接節(jié)點(diǎn)間有邊的節(jié)點(diǎn)，每次只增加一個(gè)節(jié)點(diǎn)，擴(kuò)展DAG。對(duì)于相連的兩個(gè)節(jié)點(diǎn)P和Q，如果P?Q，那么不存在P′使得P?P′?Q。所以，當(dāng)連接節(jié)點(diǎn)中包含圖節(jié)點(diǎn)的總數(shù)就是這個(gè)節(jié)點(diǎn)的大小。

(4)直至所有節(jié)點(diǎn)都包含在DAG中。

其算法步驟如下：

算法1DAG索引的建立DAGindex(G)

輸入：G∥輸入圖數(shù)據(jù)G

輸出：DAG圖、Ht/*輸出DAG圖，編碼后的Hash表Ht*/

1:DAG=?,Ht=?;

2: for eachgi∈G

3: ifgi?DAG

4:DAG=DAG∪gi;

5:Ht?Hash(gi);/*將gi哈希碼加入Hash表Ht中*/

6:Decom(gi,DAG,Hash);

7: end if

8: end for

9:return (DAG,Ht);

Decom(gi,DAG,Ht)∥圖的分解函數(shù)

1: for eachvingi∥gi中的每個(gè)節(jié)點(diǎn)

8: end if

9: end for

2.2 最小生成樹集

如圖2所示，查詢圖q為圖2a，對(duì)于q的三個(gè)子圖圖2b～圖2d都存在兩條邊的缺失。因此，對(duì)子圖2b～圖2d而言，它們都利用了同一個(gè)公共最小生成樹[12]，如圖中加粗黑邊所示。通過圖2可知，對(duì)于任何與圖2b～圖2d三個(gè)子圖精確匹配的目標(biāo)圖也必定和該最小生成樹匹配。由此可知，對(duì)于查詢圖q，得到其最小生成樹集并對(duì)最小生成樹進(jìn)行滿足條件θ的擴(kuò)展，容易得到查詢圖q的子圖。

Figure 2 Minimum common spanning tree圖2 公共最小生成樹

對(duì)于一個(gè)給定查詢圖q的圖數(shù)據(jù)集G，首先從查詢圖q中得到其最小生成樹集qt；其次，對(duì)qt進(jìn)行擴(kuò)展，使其能夠覆蓋最小生成樹并且與q的編輯距離不超過θ條邊，即對(duì)q的所有連通子圖而言，任意一個(gè)q′都是qt的超圖。

Figure 3 Query graph q & graph data G圖3 查詢圖q與圖數(shù)據(jù)G

如圖4所示，圖4a為圖3中q的精確匹配圖，同樣也可認(rèn)為是查詢圖q中滿足θ≤1的近似圖。通過該精確匹配，可以得到生成子圖圖4b～圖4e。由于其均為圖4a的連通子圖，并且都缺少一邊，因此可認(rèn)為是滿足θ=1時(shí)q的近似子圖。

Figure 4 Similary graph of query graph q (θ=1)圖4 q的近似子圖(θ=1)

本文采用Kruskal算法得到最小生成樹集qt。

首先，利用Kruskal得到一棵最小生成樹，將其邊權(quán)相同的邊置入一個(gè)邊組。根據(jù)同一個(gè)圖的不同最小生成樹之間度數(shù)相同的性質(zhì)[7]：

(1)每個(gè)邊組中所需的邊的個(gè)數(shù)一樣；

(2)對(duì)完成Kruskal運(yùn)算后的邊組所形成的聯(lián)通分量相同。Kruskal運(yùn)算對(duì)于同樣具有i(i=1,…,n,n為正整數(shù))條邊的邊組，其所形成的聯(lián)通分量具有相同數(shù)目。

其次，利用DFS枚舉所有可能的相同邊組，然后依次相乘。

最后，輸出全部最小生成樹，形成最小生成樹集。

在最小生成樹集的基礎(chǔ)上，通過對(duì)其進(jìn)行滿足θ條件的子圖擴(kuò)展，得到子圖集合。生成擴(kuò)展子圖算法如下：

算法2生成擴(kuò)展子圖Gensub(qt,θ)

輸入：qt∥最小生成樹集

θ∥近似圖編輯距離;

輸出：SUBset。

1:for eachqtiinqt

2:sub=qti;

3: for eachviinqti

4: if |E(sub)|-|E(qti)|<θ

5: ifviandvjnot connected/*vi、vj為sub中的節(jié)點(diǎn)*/

6:E(sub)=E(sub)+(vi,vj);

7: end if

8:SUBset=SUBset∪sub;

9: end if

10: end for

11:returnSUBset;∥返回?cái)U(kuò)展子圖集合

2.3 DAG近似查詢

對(duì)查詢圖q近似查詢之前，同樣需要將生成的擴(kuò)展子圖進(jìn)行DAG分解，這樣方便通過圖編碼找到查詢圖與目標(biāo)圖之間的公共子圖作為起點(diǎn)，逐步找到滿足條件θ的近似結(jié)果集。

如圖5所示，DAG圖中有且只有一個(gè)節(jié)點(diǎn)ABBC代表圖gi，有且有一個(gè)節(jié)點(diǎn)表示空?qǐng)D。圖的分解DAG通過路徑反映出節(jié)點(diǎn)的尺寸大小和層次關(guān)系。如AB、AC、BB、BC具有相同的尺寸，即同一層上的節(jié)點(diǎn)具有相同的頂點(diǎn)數(shù)，而不同層之間則具有包含和被包含的關(guān)系。

Figure 5 Decomposition of graph in DAG圖5 圖分解DAG

因此，若q的擴(kuò)展子圖sub的節(jié)點(diǎn)為BC，則通過圖編碼是否相同進(jìn)行子圖同構(gòu)判斷，可以迅速通過索引定位到DAG中，得到近似圖ABC、BBC、ABBC。

生成候選集算法如下所示，通過枚舉得到滿足閾值θ的候選集，此時(shí)只需將候選集中出現(xiàn)的重復(fù)項(xiàng)過濾即可得到近似結(jié)果集。

算法3生成候選集CandidateSearch(DAG,SUBset,θ)

輸入：DAG∥查詢圖q和圖數(shù)據(jù)G的圖分解

SUBset∥擴(kuò)展子樹

θ∥近似圖編輯距離;

輸出：近似結(jié)果集。

1:candidate=?;

2:for eachsubinSUBset

3: ifsubexist inDAG

4: iflevel

5:candidate=candidate∪sub’schildren;/*從DAG中得到當(dāng)前節(jié)點(diǎn)的孩子節(jié)點(diǎn)*/

6: nextlevel;

7: end if

8: end if

9:end for

10:returncandidate;

3 實(shí)驗(yàn)結(jié)果及性能分析

3.1 實(shí)驗(yàn)環(huán)境

本文提出方法的實(shí)驗(yàn)環(huán)境是Intel CPU Pentium T4500，主頻為2.3 GHz，內(nèi)存DDR3 2 GB，硬盤320 GB，操作系統(tǒng)為Windows XP professional sp3；所有算法均用C++在VC 6.0環(huán)境下實(shí)現(xiàn)。

3.2 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)數(shù)據(jù)采用真實(shí)數(shù)據(jù)和模擬數(shù)據(jù)。真實(shí)數(shù)據(jù)來自于DTP(Developmental Therapeutics Program)提供的化合物數(shù)據(jù)集合[13]。該數(shù)據(jù)集合包含10 000個(gè)圖，每個(gè)圖平均有5.6個(gè)頂點(diǎn)，其中頂點(diǎn)表示一個(gè)化合物分子，邊表示兩個(gè)分子之間的連接。模擬數(shù)據(jù)集使用GraphGen生成，可生成類似“D10kT20i10V5E5”的文件名來記錄的數(shù)據(jù)，它表示生成圖的總數(shù)為10 000個(gè)，圖的平均尺寸為20條邊，生成圖的平均尺寸為10條邊，圖節(jié)點(diǎn)的標(biāo)號(hào)個(gè)數(shù)是5個(gè)，圖邊的標(biāo)號(hào)個(gè)數(shù)是5個(gè)。

3.3 實(shí)驗(yàn)結(jié)果及性能分析

C-Tree利用啟發(fā)式圖映射方法來判斷編輯距離，進(jìn)而得到近似圖。但是，該算法僅僅能查詢到k個(gè)最近的近似結(jié)果。對(duì)于當(dāng)前信息數(shù)據(jù)的復(fù)雜化，其查詢結(jié)果及效率并不理想；而DAGindex算法屬于范圍查詢則返回用戶定義的某個(gè)范圍內(nèi)的全部結(jié)果。時(shí)間復(fù)雜度對(duì)比來看，C-Tree的復(fù)雜度為O(2n·2n)，而DAGindex復(fù)雜度為O(nlogn·2n)，查詢效率有一定的提高。實(shí)驗(yàn)分別從索引構(gòu)建性能和實(shí)驗(yàn)結(jié)果集的查準(zhǔn)率進(jìn)行比較，比較結(jié)果如下所述：

(1)索引構(gòu)建比較：將DAGindex算法與C-Tree的索引構(gòu)建用真實(shí)數(shù)據(jù)集進(jìn)行比較分析，分別取真實(shí)數(shù)據(jù)集為1 KB、2 KB、4 KB、6 KB、8 KB和10 KB進(jìn)行測(cè)試。圖6中X軸表示圖數(shù)據(jù)庫的大小尺寸，Y軸表示生成的索引尺寸大小，單位為KB。而在圖7中Y軸用來表示生成索引的時(shí)間，單位為ms。從圖6和圖7中的數(shù)據(jù)曲線比較可知，兩種算法的索引大小以及構(gòu)建索引的時(shí)間均和圖數(shù)據(jù)中的頂點(diǎn)數(shù)成線性增長(zhǎng)關(guān)系。但是，隨著圖尺寸逐漸增大，本文算法中的索引構(gòu)建尺寸及時(shí)間均保持在一個(gè)較平穩(wěn)的增長(zhǎng)，說明其對(duì)大圖數(shù)據(jù)也能生成質(zhì)量較高的索引。同時(shí)，由圖6和圖7可知，本文算法的曲線圖線條比C-Tree要低，說明在本文算法構(gòu)建索引性能上效率更高。

Figure 6 Comparison of index size圖6 索引尺寸的比較

Figure 7 Comparison of index construct time圖7 索引構(gòu)建時(shí)間的比較

(2)結(jié)果集比較：本文采用真實(shí)數(shù)據(jù)集進(jìn)行，取查詢圖q的尺寸分別劃分為5、10、15、20、25，采用尺寸為10 000的圖數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。閾值θ決定查詢的近似程度，當(dāng)θ=0時(shí)，近似查詢的實(shí)質(zhì)就是精確查詢。因此，此處用DAGindex與gindex進(jìn)行測(cè)試對(duì)比，用實(shí)驗(yàn)測(cè)試文章算法的查準(zhǔn)率。如圖8所示，X軸表示查詢圖q的尺寸大小(圖q的頂點(diǎn)數(shù))，Y軸表示查詢結(jié)果集的尺寸大小(圖個(gè)數(shù))。由圖8可知，DAGindex曲線隨著q尺寸的增大，其候選集尺寸也隨之減小。與gindex的候選結(jié)果集基本接近，表明了算法的有效性。

Figure 8 Comparison of result size圖8 結(jié)果集尺寸比較

4 結(jié)束語

圖近似查詢具有廣泛的應(yīng)用背景，已成為圖數(shù)據(jù)領(lǐng)域中的熱點(diǎn)。本文討論了近似查詢中存在的信息不全等問題，提出了一種基于圖分解的近似查詢方法。實(shí)驗(yàn)表明，利用該方法可以有效減少查詢時(shí)間，降低了計(jì)算復(fù)雜度，能夠得到準(zhǔn)確的候選集，從而提高查詢效率。隨著圖數(shù)據(jù)信息量的急劇膨脹，大圖數(shù)據(jù)中的近似查詢方法研究將成為今后研究中的重點(diǎn)。

[1] Shasha D，Wang J T L，Giugno R．Algorithmics and applications of tree and graph searching[C]∥Proc of the 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2002:39-52.

[2] Yan X，Yu P S，Han J. Graph indexing：A frequent structure-based approach[C]∥Proc of the 2004 ACM SIGMOD International Conference on Management of Data, 2004:335-346.

[3] Zou L, Chen L, Yu J X, et al. A novel spectral coding in a large graph database[C]∥Proc of the 11th International Conference on Extending Database Technology (EDBT), 2008:181-192.

[4] Williams D W, Huan J, Wang W. Graph database indexing using structured graph decomposition[C]∥Proc of IEEE 23rd International Conference on Data Engineering, 2007:976-985.

[5] Jiang H, Wang H, Yu P S, et al. GString：A novel approach for efficient search in graph databases [C]∥Proc of IEEE 23rd International Conference on Data Engineering, 2007:566-575.

[6] Chen C, Yan X, Yu P S, et al. Towards graph containment search and indexing[C]∥Proc of the 33rd International Conference on Very Large Data Bases, 2007:926-937.

[7] Zhang S, Li J, Gao H,et al. A novel approach for efficient supergraph query processing on graph databases[C]∥Proc of the 12th International Conference on Extending Database Technology, 2009:204-215.

[8] Wang Fang, Jin R, Agrawal G, et al. Graph and Topological Structure Mining on Scientific Articles[C]∥ Proc of the 7th BIBE, 2007:1318-1322.

[9] Zou Xiao-hong,Chen Xiao,Guo Jing-feng,et al. An improved algorithm for mining closegraph[J]. ICIC Express Letters,2010,4(4):1135-1140.

[10] He Hua-hai,Singh A K.Closure-tree:An index structure for graph queries[C]∥ Proc of the 22nd ICDE, 2006:38.

[11] Huan Jun, Bandyopadhyay D, Wang Wei, et al. Comparing graph representations of protein structure for mining family-specific residue-based packing motifs[J]. Journal of Computational Biology, 2005, 12(6):657-671.

[12] Zhu Gao-ping, Lin Xue-min, Zhu Ke, et al. TreeSpan:Efficiently computing similarity all-matching[C]∥Proc of 2012 SIGMOD, 2012:529-540.

[13] DTP chemical data [EB/OL]. [2012-11-15]. http:∥dtp.nci.nih.gov/docs/aids/aids_data.html.