單曉歡，王廣香，宋寶燕，丁琳琳，許 巖

遼寧大學(xué) 信息學(xué)院，沈陽 110036

1 引言

圖作為重要的數(shù)據(jù)結(jié)構(gòu)能夠有效描述現(xiàn)實生活中各類實體之間的復(fù)雜關(guān)系,已廣泛應(yīng)用于社交網(wǎng)、生物信息網(wǎng)及智能交通網(wǎng)[1-4]等眾多新興領(lǐng)域。隨著網(wǎng)絡(luò)技術(shù)的深度發(fā)展和普及，圖規(guī)模日益龐大且動態(tài)變化。在大規(guī)模動態(tài)圖中，某些結(jié)構(gòu)是頻繁出現(xiàn)且穩(wěn)定存在的，這些圖結(jié)構(gòu)可能隱藏著大量有價值的信息。例如蛋白質(zhì)相互作用網(wǎng)中，挖掘蛋白質(zhì)間相互作用形成的頻繁結(jié)構(gòu)并在此基礎(chǔ)上進行分析，這將在生物過程及防治疾病等研究中起到重要作用。因此，如何高效且準確地查詢這類頻繁結(jié)構(gòu)，已成為當今圖數(shù)據(jù)管理的熱點研究問題之一。

近年來，數(shù)據(jù)量雖爆炸式增長，但其中隱藏的信息并非完全具有價值，為消除信息過載帶來的負面影響，Top-K查詢應(yīng)運而生，并在電子商務(wù)等領(lǐng)域應(yīng)用廣泛[5-6]。在實際應(yīng)用中，以社交網(wǎng)中的微信為例，一些電商為了進行精準營銷，可查詢具有某種特定結(jié)構(gòu)的團隊，每個成員錢包余額均大于某值且團隊余額總數(shù)靠前的K個團隊，并向其定時發(fā)送消費廣告、熱門推薦等，針對不同階層推送熱門商品，促進消費以謀求更大利潤。該類查詢可抽象為大規(guī)模動態(tài)圖上具有約束條件的頻繁子圖Top-K查詢，此類查詢在實際應(yīng)用中具有重要意義。

鑒于上述查詢的實際需求，本文在大規(guī)模動態(tài)圖上，針對具有約束限制的頻繁子圖Top-K查詢展開研究，具體包括：

（1）提出一種頻繁結(jié)構(gòu)映射和標簽值聚合的二級索引（frequent structure mapping and label value aggregated secondary indexes，F(xiàn)SM-LVA），利用該二級索引，快速鎖定查詢圖結(jié)構(gòu)，并利用標簽約束限制對候選頻繁子圖結(jié)果進行剪枝過濾，有效縮小查詢范圍，進而提高查詢效率。

（2）提出基于FSM-LVA索引的頻繁子圖Top-K查詢方法，該方法利用頻繁結(jié)構(gòu)映射索引搜索同構(gòu)于查詢圖的頻繁結(jié)構(gòu)，從而排除非查詢結(jié)構(gòu)的干擾；然后利用標簽值聚合索引，快速剪枝過濾不滿足約束的頻繁子圖，縮小查詢范圍，快速獲得查詢結(jié)果。

（3）基于真實數(shù)據(jù)集和模擬數(shù)據(jù)集進行了大量的實驗并在此基礎(chǔ)上進行分析，在空間和時間上驗證了本文方法的有效性。

2 相關(guān)工作

普通意義上的Top-K查詢是從海量數(shù)據(jù)中返回最符合用戶需求的K個結(jié)果，典型應(yīng)用如搜索引擎、數(shù)據(jù)庫檢索及文件搜索等。PABF（probabilistic approximate based framework）框架[7]支持近似連續(xù)Top-K查詢，能夠有效地對數(shù)據(jù)庫對象進行檢索。Bortnikov等人[8]提出的方法中通過引入迭代器，在Top-K查詢處理過程中，能夠提高動態(tài)剪枝算法的效率。

圖匹配相關(guān)算法致力于有效解決圖結(jié)構(gòu)的匹配問題。文獻[9]基于圖壓縮的思想，提出了一種滿足頂點“局部雙擬”關(guān)系的且具有自適應(yīng)更新特性的有向標簽圖結(jié)構(gòu)概要模型，在縮小數(shù)據(jù)圖規(guī)模的基礎(chǔ)上，能夠適應(yīng)查詢圖的結(jié)構(gòu),根據(jù)查詢圖頂點之間的rank差值在結(jié)構(gòu)概要模型中實現(xiàn)頂點匹配。Amin等人[10]提出了加權(quán)查詢的概念，基于加權(quán)查詢語義提出了兩種興趣度測量方法，即影響邊緣匹配IE-Match和最接近的匹配C-Match。BOOSTISO算法[11]利用節(jié)點間的等價關(guān)系和包含關(guān)系構(gòu)建SE圖和SC圖，雖可有效提高子圖匹配效率，但構(gòu)建SE圖需提取復(fù)雜的鄰接點關(guān)系，同時需展開合并節(jié)點以獲取查詢結(jié)果，影響查詢效率，且該算法不支持動態(tài)查詢。

圖數(shù)據(jù)Top-K查詢由圖匹配和Top-K查詢兩部分構(gòu)成，已有研究中大致分為兩種類型：先匹配后排序和匹配時排序。先匹配后排序，首先篩選出與查詢圖結(jié)構(gòu)匹配的所有子圖，再對候選子圖進行排序，典型算法如文獻[12-13]的算法等。該類方法需要進行大量比較，計算開銷相對較大，尤其當查詢的K值較小或與候選子圖數(shù)目差值較大時，需要進行多次不必要的比較，影響查詢效率。匹配時排序是在進行查詢圖同構(gòu)計算時對結(jié)果進行排序，這類方法對于規(guī)模較小的查詢圖效率較高，但是隨著查詢圖規(guī)模的增大，由于匹配代價過高，算法效率大幅度下降，如RWM（ranking while matching）[14]算法，該算法利用候選邊生成與查詢圖同構(gòu)的子圖，并進行Top-K排序，在Top-K堆中維持K個最佳結(jié)果，然而當查詢圖較大時，由于匹配代價過高，嚴重影響算法效率。

在現(xiàn)實應(yīng)用中，隨著圖數(shù)據(jù)規(guī)模日益龐大且不斷更新，上述不論是普遍意義的Top-K查詢、子圖匹配算法，還是現(xiàn)有的圖數(shù)據(jù)Top-K查詢算法均難以應(yīng)對大規(guī)模動態(tài)圖數(shù)據(jù)處理的挑戰(zhàn)。而且利用已有算法無法有效處理圖數(shù)據(jù)中具有約束條件的Top-K查詢。

3 頻繁結(jié)構(gòu)映射和標簽值聚合的二級索引

標簽約束的頻繁子圖Top-K查詢，既要匹配同構(gòu)于查詢圖的頻繁結(jié)構(gòu)，又要在該結(jié)構(gòu)的眾多頻繁子圖中搜索滿足約束條件的前K個。因此，本文為快速鎖定查詢圖結(jié)構(gòu)，同時利用約束條件進行剪枝過濾以縮小查詢范圍，提出了由頻繁結(jié)構(gòu)映射（FSM）和標簽值聚合（LVA）構(gòu)成的二級索引（FSM-LVA索引）。

3.1 FSM索引

隨著圖數(shù)據(jù)規(guī)模日益增大，若針對每次頻繁子圖查詢，均通過遍歷完整數(shù)據(jù)圖而獲取結(jié)果，將會帶來巨大的計算開銷，嚴重影響查詢效率。為此，本文首先利用頻繁子圖挖掘算法[15]挖掘大規(guī)模圖中的頻繁子圖結(jié)構(gòu)，并在此基礎(chǔ)上建立FSM索引，各索引項包含頻繁結(jié)構(gòu)及其映射的頻繁子圖結(jié)果集。每一個頻繁子圖結(jié)果集對應(yīng)該結(jié)構(gòu)的子圖信息，因此將其以集合的形式表示，每一項為一個頻繁子圖，包含節(jié)點及其標簽值信息，即以（u,v,w,…,lu,lv,lw,…）形式表示。通過頻繁結(jié)構(gòu)可以快速鎖定查詢圖結(jié)構(gòu)，通過映射該結(jié)構(gòu)的頻繁子圖結(jié)果集可獲得最終的查詢結(jié)果。如圖1所示為數(shù)據(jù)圖G及頻繁子圖結(jié)構(gòu)。

Fig.1 Data graph and frequent subgraph structure圖1 數(shù)據(jù)圖及頻繁子圖結(jié)構(gòu)

大規(guī)模圖中頻繁結(jié)構(gòu)往往有很多，為快速匹配到同構(gòu)于查詢圖的頻繁結(jié)構(gòu)，避免其他頻繁結(jié)構(gòu)帶來的干擾，在FSM索引中，引入哈希表來索引大規(guī)模圖中的頻繁子圖結(jié)構(gòu)，頻繁子圖中的節(jié)點個數(shù)作為關(guān)鍵字，哈希函數(shù)為關(guān)鍵字自身。通過索引中的哈希表可快速定位同構(gòu)于查詢圖的頻繁結(jié)構(gòu)，進而獲得該結(jié)構(gòu)的頻繁子圖結(jié)果集。以圖1為例，建立的FSM索引如表1所示。

Table 1 Frequent structure mapping index表1 頻繁結(jié)構(gòu)映射索引表

利用FSM索引進行標簽值約束的頻繁子圖Top-K查詢時，可利用哈希表快速鎖定查詢圖結(jié)構(gòu)，并遍歷該結(jié)構(gòu)對應(yīng)的頻繁子圖結(jié)果集，找到滿足約束條件的候選集，并從中選取前K個即為查詢結(jié)果。

3.2 LVA索引

經(jīng)分析可知，大規(guī)模圖中各頻繁結(jié)構(gòu)映射的頻繁子圖結(jié)果項很多，在進行約束Top-K查詢時，利用FSM索引，遍歷整個結(jié)果集判斷是否滿足約束限制，再進行Top-K篩選將產(chǎn)生一定的計算開銷，影響查詢效率。因此，本文在FSM索引基礎(chǔ)上，提出標簽值聚合索引（LVA索引），作用于FSM索引中每個頻繁結(jié)構(gòu)上，利用多維空間將頻繁子圖結(jié)果集中各頻繁子圖根據(jù)標簽值進行聚合劃分，映射到坐標空間，根據(jù)查詢圖約束條件，可在空間坐標中快速剪枝過濾不滿足約束的區(qū)域，進而縮小查詢范圍，避免不必要的計算開銷，極大地提高了查詢效率。具體創(chuàng)建過程如算法1所示，其中α為劃分密度，即將每個維度的標簽坐標空間劃分為α部分，min和max分別對應(yīng)頻繁子圖結(jié)果集中的最小和最大標簽值，LVA索引中各索引項由聚合索引編號和映射的頻繁子圖結(jié)果集組成。

以表1中頻繁結(jié)構(gòu)FG-1為例，由圖1可知FG-1對應(yīng)的頻繁子圖結(jié)果集為{(v1,v2,6.4,6.8)，(v1,v3,6.4,0),(v1,v4,6.4,5.3),…,(v6,v11,8.0,5.2)}，標簽值區(qū)間為[0,8]，設(shè)定劃分密度α=4，則各子區(qū)間分別為[0,2)、[2,4)、[4,6)、[6,8]。頻繁子圖(v1,v2,6.4,6.8)各節(jié)點對應(yīng)的索引編號為index(6.4)=4,index(6.8)=4，將各索引編號組合形成聚合索引項，則(v1,v2,6.4,6.8)對應(yīng)的聚合索引項為(4,4)。為所有FG-1結(jié)構(gòu)的頻繁子圖分配索引項，即可得到FG-1的LVA索引，如圖2所示，其對應(yīng)LVA索引表如表2所示。

Fig.2 LVAindex of FG-1 structure圖2 FG-1結(jié)構(gòu)LVA索引

Table 2 LVAindex table of FG-1 structure表2 FG-1結(jié)構(gòu)LVA索引表

由于LVA索引將頻繁子圖結(jié)果集根據(jù)標簽值特性劃分在若干空間區(qū)域，因此該索引支持范圍查詢，根據(jù)查詢圖的標簽值及約束限制可立即縮小查詢范圍。最大程度地剪枝以減少比較次數(shù)，進而提高查詢效率。為滿足本文后續(xù)的Top-K查詢，將空間坐標系由最大索引項(α,α)向最小索引項(1,1)方向逐索引項對角劃分，且稱相鄰兩條劃分線之間的部分為相容索引空間，稱最大索引項對角線以上部分為初始索引空間，最小索引項對角線以下部分為終止索引空間。

在LVA索引上進行約束Top-K查詢，相較于FSM中遍歷頻繁子圖結(jié)果更為有效。因此,為有效降低存儲開銷，可在建立LVA索引基礎(chǔ)上將FSM索引中對應(yīng)該結(jié)構(gòu)的頻繁子圖結(jié)果集刪除。

4 標簽約束的頻繁子圖Top-K查詢

本文提出的支持大規(guī)模動態(tài)圖中標簽約束的頻繁子圖Top-K查詢方法（LVC-FS Top-K）基于FSM-LVA索引，其查詢主要包含兩方面：頻繁結(jié)構(gòu)查詢和標簽約束的Top-K匹配。頻繁結(jié)構(gòu)查詢將利用FSM索引對同構(gòu)于查詢圖的頻繁結(jié)構(gòu)進行查找。標簽約束的Top-K匹配利用查詢圖的約束條件及K值限制對頻繁子圖進行篩選,極大地縮小了比較空間，進一步加快了查詢效率。

4.1 頻繁結(jié)構(gòu)查詢

以查詢圖中節(jié)點個數(shù)作為FSM索引中哈希函數(shù)的輸入，若在FSM索引中有與該數(shù)目對應(yīng)的索引項，即可根據(jù)索引項定位到同構(gòu)于查詢圖的頻繁結(jié)構(gòu)；反之，則無有效的查詢結(jié)果。

4.2 標簽約束的Top-K匹配

標簽約束的Top-K匹配包括約束限制條件的篩選以及K值篩選兩部分。約束限制下篩選，即計算查詢圖約束所對應(yīng)的LVA聚合編號，若落在某聚合索引項內(nèi)，則該索引項以及大于該編號的索引項所對應(yīng)的所有子圖為候選子圖，小于該編號的所有索引項不在計算范圍內(nèi)，大大減少了計算范圍；若約束對應(yīng)聚合編號落在索引項劃分線上，則小于該劃分線的索引項不在計算范圍內(nèi)，計算大于該編號的索引項所對應(yīng)的所有子圖。K值篩選，即將K值與初始索引空間中的子圖個數(shù)m相比較：（1）若K≤m，計算初始索引空間中各子圖的節(jié)點標簽值之和并選取K個最佳結(jié)果。（2）若K>m，計算下一相容索引空間中的子圖個數(shù)m′，并將m′與m相加得sum，若K≤sum，則在這sum個子圖中選取K個最佳結(jié)果；否則重復(fù)操作（2），直到終止索引空間中的子圖個數(shù)也被加入到sum中為止。若此時仍有K>sum，則說明總的子圖個數(shù)不足K個，無法選取到K個最佳結(jié)果，只需在這已有的sum個子圖當中查找出符合條件的子圖即可。具體查詢過程如算法2所示。

仍以圖1的數(shù)據(jù)圖G為例，若經(jīng)頻繁結(jié)構(gòu)查詢獲得查詢圖結(jié)構(gòu)為FG-1，約束條件為各節(jié)點標簽值不低于4.5且標簽值之和不小于14，K=4。由查詢圖的約束條件計算其聚合索引index(4.5)=3，因此索引編號小于3的聚合索引項均無需考慮，如圖3中虛線部分。K=4，而初始索引空間中子圖個數(shù)m=2,K>2,則計算與其相鄰的相容索引空間，發(fā)現(xiàn)其子圖個數(shù)為3，此時sum=5>4，則在這5個子圖中選取4個標簽值之和最大的子圖。由于約束中同時要求節(jié)點標簽值之和不小于14，經(jīng)計算滿足約束條件的子圖只有(v5,v6,6.5,8)和(v2,v6,6.8,8)，到此結(jié)果集已產(chǎn)生。

Fig.3 Constraint and K-value filtration圖3 約束及K值篩選

由上述例子可知，最終滿足約束條件限制的查詢結(jié)果可能不足K個，針對此類問題，若查詢需嚴格滿足標簽約束限制，則根據(jù)實際情況返回結(jié)果；若查詢需嚴格滿足K值限制，則可降低標簽約束以獲得K個結(jié)果。

5 實驗與分析

本章將從劃分密度對LVA索引創(chuàng)建時間的影響、索引存儲空間、頻繁子圖約束Top-K查詢性能三方面進行實驗，驗證本文方法的有效性和可行性。

5.1 實驗環(huán)境及數(shù)據(jù)集

本文實驗在Intel Pentium?CPU?G3220 3.00 GHz處理器，8 GB內(nèi)存，500 GB硬盤的計算機上完成，編程語言為Java。實驗分別在真實數(shù)據(jù)集及模擬數(shù)據(jù)集上完成。真實數(shù)據(jù)集為理財錢包用戶網(wǎng)絡(luò)（簡稱FPUN），圖中每個節(jié)點代表一個賬戶，邊代表用戶好友關(guān)系，節(jié)點標簽值為賬戶余額。模擬數(shù)據(jù)集則模擬社交網(wǎng)絡(luò)（簡稱SN），節(jié)點標簽值假設(shè)為年齡，隨機賦值1～70，如表3所示。

Table 3 Experimental dataset表3 實驗數(shù)據(jù)集

5.2 實驗分析

實驗1α選取對LVA索引創(chuàng)建時間的影響。

構(gòu)建標簽值聚合索引時，劃分密度α的選取會影響索引的創(chuàng)建時間。當劃分密度α較小時，所得的索引項區(qū)間較大，聚合劃分較粗糙，索引創(chuàng)建時間較小。若α設(shè)置過小，會造成每個索引項中頻繁子圖數(shù)目過多，從而增加查詢比較次數(shù)，影響查詢效率；當劃分密度α較大時，所得的索引項區(qū)間則變小，聚合劃分較精細，索引創(chuàng)建時間較大，但在進行Top-K查詢時可減少一定的比較次數(shù)。因此，α的合理設(shè)置對LVA索引的創(chuàng)建及查詢效率均有影響。圖4顯示了不同分段密度下，F(xiàn)PUN和SN上索引創(chuàng)建時間情況。

實驗2存儲開銷性能分析。

圖5展示了本文算法與BOOSTISO算法的存儲開銷性能的對比情況。兩種算法對數(shù)據(jù)圖的存儲開銷相仿，但本文額外存儲僅為FSM-LVA二級索引，由于頻繁結(jié)構(gòu)相較于數(shù)據(jù)圖規(guī)模較小且數(shù)量較少，同時LVA索引構(gòu)建后，F(xiàn)SM索引中對應(yīng)該結(jié)構(gòu)的頻繁子圖結(jié)果集即可刪除，這將進一步節(jié)省存儲空間。BOOSTISO算法需額外存儲SE圖、SC圖、DR表以及節(jié)點間等價關(guān)系，當存在等價或包含關(guān)系的節(jié)點數(shù)目較少時，其存儲消耗僅次于對數(shù)據(jù)圖的存儲，存儲開銷較大。

Fig.4 Building time of LVAindex圖4 LVA索引建立時間

Fig.5 Storage size圖5 存儲開銷

實驗3頻繁子圖約束Top-K查詢性能分析。

頻繁子圖的約束Top-K查詢由頻繁結(jié)構(gòu)匹配以及約束Top-K查詢兩部分構(gòu)成。頻繁結(jié)構(gòu)匹配時間與查詢圖節(jié)點個數(shù)相關(guān)，圖6、圖7分別展示了LVCFS方法與RWM、BOOSTISO算法在不同數(shù)據(jù)集上運行時間對比情況。如圖所示，匹配時間隨節(jié)點個數(shù)的增多而增大，在節(jié)點個數(shù)較少時，LVS-FS與RWM方法、BOOSTISO方法匹配時間相差不大，但是隨節(jié)點個數(shù)增多，由于RWM算法需要逐邊生成查詢圖，需進行大量計算，耗費較多時間，BOOSTISO方法需要依賴查詢圖的包含關(guān)系對DR表進行維護，同時利用節(jié)點順序依次遍歷查詢子圖時，耗費時間較多。而本文算法可通過FSM索引直接索引到查詢圖結(jié)構(gòu)，計算量小，匹配時間較短。

Fig.6 Query graph matching time on FPUN圖6 數(shù)據(jù)集FPUN上查詢圖匹配時間

Fig.7 Query graph matching time on SN圖7 數(shù)據(jù)集SN上查詢圖匹配時間

圖8、圖9分別展示了查詢圖為FG-2結(jié)構(gòu)時，不同K值下，LVC-FS、RWM以及BOOSTISO方法在不同數(shù)據(jù)集上的查詢時間對比情況。如圖所示，與其他兩種算法相比，LVC-FS受K值影響較小，這是因為其能夠利用約束限制有效剪枝過濾，縮小查詢范圍；并利用K值，在有效索引空間內(nèi)進行搜索并返回結(jié)果。RWM算法是采用匹配時排序的思想，隨著K值的增大，計算量隨之變大，嚴重影響查詢效率；BOOSTISO算法需先找出所有符合查詢圖結(jié)構(gòu)的子圖再進行排序并取前K個結(jié)果，這一過程計算量較大，影響查詢效率。

Fig.8 Time of constraint Top-Kquery on FPUN圖8 數(shù)據(jù)集FPUN上約束Top-K查詢時間

6 結(jié)束語

本文針對大規(guī)模動態(tài)圖中標簽約束的頻繁子圖Top-K查詢問題進行了研究，提出了一種標簽約束的頻繁子圖Top-K查詢方法，該方法通過創(chuàng)建頻繁結(jié)構(gòu)映射與標簽值聚合的二級索引，快速準確地鎖定查詢圖結(jié)構(gòu)并根據(jù)約束限制剪枝過濾以獲得查詢結(jié)果。實驗結(jié)果表明該方法能夠快速準確地在大規(guī)模動態(tài)圖中進行具有約束限制的頻繁子圖Top-K查詢，且查詢結(jié)果在現(xiàn)實應(yīng)用中具有實際意義。

Fig.9 Time of constraint Top-Kquery on SN圖9 數(shù)據(jù)集SN上約束Top-K查詢時間