大規模動態圖中標簽約束的頻繁子圖Top-K查詢*

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

遼寧大學 信息學院，沈陽 110036

1 引言

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

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

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

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

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

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

2 相關工作

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

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

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

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

3 頻繁結構映射和標簽值聚合的二級索引

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

3.1 FSM索引

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

Fig.1 Data graph and frequent subgraph structure圖1 數據圖及頻繁子圖結構

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

Table 1 Frequent structure mapping index表1 頻繁結構映射索引表

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

3.2 LVA索引

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

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

Fig.2 LVAindex of FG-1 structure圖2 FG-1結構LVA索引

Table 2 LVAindex table of FG-1 structure表2 FG-1結構LVA索引表

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

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

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

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

4.1 頻繁結構查詢

以查詢圖中節點個數作為FSM索引中哈希函數的輸入，若在FSM索引中有與該數目對應的索引項，即可根據索引項定位到同構于查詢圖的頻繁結構；反之，則無有效的查詢結果。

4.2 標簽約束的Top-K匹配

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

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

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

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

5 實驗與分析

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

5.1 實驗環境及數據集

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

Table 3 Experimental dataset表3 實驗數據集

5.2 實驗分析

實驗1α選取對LVA索引創建時間的影響。

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

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

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

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

Fig.5 Storage size圖5 存儲開銷

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

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

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

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

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

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

6 結束語

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

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