大規模標簽圖中的動態Top-K興趣子圖查詢

宋寶燕，賈春杰，單曉歡，丁琳琳，丁興艷

(遼寧大學 信息學院，沈陽 110036)(*通信作者電子郵箱shanxiaohuan@lnu.edu.cn)

0　引言

圖因獨有的結構化特征而廣泛用于描述生物技術[1]、軍事管理等領域的復雜網絡關系，而網絡中數據類型的多樣化則可通過具有節點特征標識能力的標簽圖表示。子圖查詢[2]是圖數據處理的基本問題，即在數據圖中搜索同構于查詢圖的所有匹配子圖。

隨著信息技術的飛速發展，上述領域的數據爆炸式地增長且動態變化，大量信息中用戶往往只對若干匹配結果感興趣，同時希望通過增加限制條件而減少信息過載的負面影響，因此將Top-K查詢引入子圖查詢中。現有的Top-K子圖查詢方法多集中在中小規模靜態圖上，由于查詢效率、存儲開銷等原因無法直接應用于大規模動態圖；支持動態圖子圖查詢的方法中，多數采用累積定時方式對圖及索引進行更新，這將導致更新間隔內的查詢結果因圖的動態變化而存在一定誤差；同時實際應用中存在一類具有重要意義的查詢，以DBLP作者合作關系網為例，查詢作者間合作密切(利用邊權值大小表示)的具有特定結構的實力強勁的K個團隊，然而現有方法鮮有支持此類用戶個性化限定的興趣子圖查詢。

鑒于上述問題，本文利用標簽圖節點、邊獨有的特征特性，提出了一種動態Top-K興趣子圖近似查詢方法(Dynamic Top-KInteresting Subgraph Query，DISQtop-K)。本文主要工作如下：

1)提出一種圖拓撲結構特性(Graph Topology Structure Feature， GTSF)索引，該索引由節點拓撲結構特性(Node Topology Feature Index， NTF)索引和邊特性(Edge Feature， EF)索引構成。利用NTF索引可根據節點度、鄰接點等信息過濾無效節點，以獲得相對較小的候選節點集；利用EF索引可根據邊的類型標簽及權值快速過濾不滿足權值限制的無效邊，進而獲得相對較小的候選邊集。

2)提出基于GTSF索引的多因素候選集過濾策略，利用加權邊、節點度以及鄰接點頻率等特征限制對查詢圖候選集進一步剪枝，以避免匹配驗證階段的冗余計算。

3)提出Top-K興趣子圖匹配驗證方法，該方法考慮到圖的動態變化可能對匹配結果產生影響，將匹配驗證過程分為初始匹配和動態修正兩個階段，初始階段在候選集上按照匹配順序進行逐一匹配以獲得初始結果集；動態修正階段，利用圖動態變化對初始結果集進行動態修正，盡可能保證查詢結果的實時、準確。

4)基于真實數據集和模擬數據集，在存儲空間及索引創建時間、查詢效率等方面進行了大量實驗，驗證了本文方法的有效性。

1　相關工作

目前子圖查詢方法多采用過濾-驗證的方式，根據過濾方式的不同可分為三類：無索引結構、頻繁子圖索引和可達性索引過濾。

無索引結構方法將直接進行匹配驗證。Ullmann算法[3]是一種基于狀態空間搜索的子圖同構檢測方法，主要通過細化過程來消除樹搜索過程中的后繼節點個數，從而達到剪枝的目的，以提高確定同構的效率。由于其使用的是遞歸的窮舉方法，因此在小規模圖上效率較高。VF2算法[4]對Ullmann進行了優化，通過使用一組可行性規則對搜索空間進行剪枝，增加了查詢節點匹配順序，但在大規模圖上的查詢效率極低。STwig算法[5]同樣不使用圖形索引，而是利用并行技術解決子圖查詢，然而連接操作將產生大量無用中間結果，以致空間復雜度和時間復雜度相對較高。TurboISO[6]提議合并查詢圖中的相似節點(具有相同標簽并位于相同區域的頂點)，并將查詢圖轉化成一棵生成樹，通過路徑過濾法過濾掉不可行的候選節點。BoostIso[7]對TurboISO進行了優化，先將數據圖中的相似節點進行合并，然后同樣通過路徑過濾法進一步減少不必要的中間結果。但TurboISO和BoostIso只適用于具有相似節點的查詢圖和數據圖；同時，由于路徑過濾運行時間會隨著數據集的增加呈現指數增長，對于大規模查詢圖和數據圖，TurboISO和BoostIso均無法高效處理子圖查詢問題。文獻[8]提出了一個新框架，通過對查詢圖進行CFL(Core Forest Leaf)分解來消除不相似節點笛卡爾積的冗余問題；同時提出一種輔助數據結構索引CPI(Compact Path Index)，不僅可以用于計算匹配順序，還可以實現對數據圖的剪枝，進而對數據圖中的可能查詢結果進行壓縮編碼。但是，該算法由于沒有動態查詢機制，在大規模動態標簽圖上查詢效率較低。

頻繁子圖索引方法指的是找到頻繁子圖或經常查詢的子圖，并對這些頻繁結構進行索引，避免了匹配過程中過多的連接操作。SUBDUE算法[9]是在單個圖中挖掘頻繁子圖的經典算法；SpiderMine[10]則對其進行優化，旨在從圖中挖掘前K個最大頻繁模式。這兩種子圖查詢方法只適用于具有頻繁子圖結構的數據圖。

可達性索引方法則通過構建索引結構和一些優化策略對候選集進行裁剪，基于回溯的方式逐步列舉解決方案并驗證查詢圖節點所對應的候選集，從而遞歸地形成最終的查詢結果。SPath[11]和GraphQL[12]都是利用每個節點的鄰居進行過濾，使得候選節點數最小化。其中GraphQL利用廣度優先搜索樹的形式，進一步對候選節點進行過濾，從而迭代地進行查找；SPath則通過記錄一些基本的路徑實現對節點的過濾。由于SPath與GraphQL在過濾中記錄了過多信息，造成了較多不必要的內存開銷，同時這兩種方法均沒有涉及等價節點重復枚舉和匹配順序選擇問題。

在實際應用中，人們往往關注興趣度比較高的查詢結果，因此引出更具針對性的Top-K子圖查詢問題。Top-K子圖查詢主要分為兩個部分：一是根據查詢圖在數據圖中找到所有的匹配子圖；二是將所有的匹配子圖根據興趣度排名獲得興趣度最大的K個興趣子圖。目前Top-K子圖查詢主要分為兩種模式：先匹配后排序模式和邊匹配邊排序模式。

先匹配后排序模式，即先獲取所有匹配子圖，然后根據興趣度對所有的匹配子圖排序，從而獲得最優的K個匹配子圖，如RAM算法[13]，通過建立SPath索引結構對候選集進行過濾，然后匹配驗證獲得所有匹配子圖，根據興趣度對所有的匹配子圖排序，從而獲得最優的K個匹配，由于獲取所有匹配結果的過程相對較復雜，因此在大規模圖上的Top-K子圖查詢效率較低。邊匹配邊排序模式則在匹配驗證的過程中過濾掉興趣度明顯較小的匹配子圖，如RWM[14]針對RAM進行改進，采用邊匹配邊排序的模式，提出兩種索引結構對候選集進行剪枝，查詢效率相對提高，然而由于其Top-K匹配的順序隨機，因此將產生大量的冗余計算。

綜上分析可知，目前對于Top-K子圖查詢算法大多存在兩個問題：一是大多數算法僅解決無權查詢圖的匹配問題，沒有考慮用戶的個性化需求，即沒有涉及加權查詢圖的匹配處理；二是在實際應用中，圖會隨著時間推移、實際應用語義的改變而發生拓撲結構的變化，動態圖下的Top-K子圖查詢研究相對較少。

2　動態Top-K興趣子圖近似查詢

2.1　問題描述

2.1.1圖標簽

本文討論的無向加權標簽圖可通過(V,E,L,W)四元組形式表示，其中：V為節點集合；E為邊集合；L為節點標簽集合;L(v)為節點v的標簽值，用以表示節點的某種特征;W則為邊權值集合。

以DBLP作者合作關系網為例，網絡中作者、研究領域關鍵字以及學術會議均抽象為圖中節點，如圖1所示，用標簽A、K、C表示，即利用圖標簽表示節點的不同種類，邊則表示三者之間的關系，邊權值用以表示作者間合作關系以及作者參與會議的程度、關鍵字間相似程度等。

2.1.2興趣子圖

在現實生活中，根據查詢需求的不同，人們往往對具有某種結構的查詢圖感興趣，并且希望通過限定查詢圖中某些節點間的特殊關系而實現更精準的查詢。例如，在由軍人和其擅長的技術組成的軍事網絡中，要組建一個4人團隊完成某項任務，其中要求2人槍法精準，1人擅長英語和計算機，1人僅擅長英語，且槍法精準的2人曾有過多次合作，即可將該查詢問題抽象為查詢具有上述結構且節點間權值具有一定限制的子圖，通常將此類子圖稱為興趣子圖。本文將針對此類興趣子圖查詢問題展開深入研究。

圖1　數據圖GFig. 1　Data graph G

2.1.3動態Top-K近似查詢

興趣子圖查詢將根據用戶查詢需求，從數據圖中搜索與查詢圖結構相同、邊權值滿足某種限制且聯系緊密的所有子圖。在實際應用中，常通過標簽圖中邊權值大小來標識兩個實體的關聯程度，各個實體間的關聯程度則反映整個網絡的緊密程度，本文將用圖的興趣度來表示，其規范化定義如下：

定義1興趣度。若M是查詢圖Q在數據圖G中的一個匹配子圖，則組成M的所有邊的權值之和即為該匹配子圖的興趣度，表示為I(M)。

如圖2所示，P1、P2是查詢圖Q的兩個匹配子圖，它們的興趣度分別為:I((P1)= 2.1，I(P2)= 2.3。

圖2　查詢Q的兩個匹配子圖P1與P2Fig. 2　Two matched subgraph P1 and P2 of query Q

隨著圖數據規模的日益增大，Top-K查詢因可有效解決信息過載帶來的巨大開銷而得到廣泛應用。大規模圖的Top-K興趣子圖查詢，即搜索同構于查詢圖的K個最大興趣度的子圖。實際應用中，網絡常隨時間推移、實際應用語義的改變而發生拓撲結構的變化，即數據圖發生節點或邊的插入、刪除等，如何保證大規模動態圖下Top-K興趣子圖查詢的高效性面臨嚴峻挑戰。研究發現，當前動態圖數據處理常采用定時累積更新取代實時更新，以減少頻繁I/O造成的巨大通信開銷，這將導致更新間隔內的查詢結果存在一定的誤差，然而圖動態變化是一個長期且穩定的過程，一段時間內的變化量遠小于圖數據規模，對子圖查詢結果影響相對較小，因此，本文將針對大規模動態圖中的Top-K興趣子圖近似查詢展開研究。本文方法處理過程主要由索引建立、候選集過濾以及子圖匹配驗證三個階段構成。

2.2　圖拓撲結構特性索引

子圖同構匹配本身是一個NP完全問題，隨著數據圖及查詢規模的擴大，算法的搜索效率會大幅度下降，現有方法多采用過濾-驗證策略，通過提取圖節點信息或某些子結構信息建立具有過濾能力的索引以提高查詢效率。為此本文結合標簽圖的自身特性，利用圖節點及邊信息，提出一種圖拓撲結構特性索引(GTSF索引)，該索引由節點拓撲結構特性索引(NTF索引)和邊特性索引(EF索引)構成。

2.2.1NTF索引

研究發現，標簽圖中節點的度、類型標簽和不同類型鄰接點等屬性具有標志性和可辨別性，因此本文利用該特性提出NTF索引，該索引由兩級結構構成，頂層結構根據節點標簽類型進行索引，底層結構則建立每種標簽類型包含的節點拓撲關系，以達到高效過濾無效節點的目的。

NTF頂層索引項由〈節點標簽類型，所屬類型節點數〉構成，底層索引項則由〈節點編號，節點度，各類型鄰接點個數〉組成，通過廣度優先算法統計各個節點的標簽類型、度、鄰接點類型及個數等拓撲結構特性。由于節點的度越大，它提供的信息量越大，在查詢匹配時就可能更有價值，因此本文將索引項按照節點度進行降序排列。以圖1為例，數據圖G中包含A、K、C三種類型的節點，其NTF索引如圖3所示。其中：id表示節點編號,degree表示節點的度，numA、numK和numC分別表示A、K、C三種類型節點的數量。

圖3　NTF索引Fig. 3　Index of NTF

2.2.2EF索引

由標簽圖特性分析發現，除節點外，邊同樣蘊含大量信息，如邊類型、權值等。為進一步過濾無效結構，本文提出了EF索引，該索引同樣包含兩級索引結構，頂層結構根據邊標簽類型(由兩端節點類型組成)進行索引，底層結構則為每種邊標簽類型包含的邊信息，通過EF索引可以快速獲取各邊的類型標簽及權值。

EF頂層索引項由邊類型構成，底層索引項則由〈邊端點1,邊端點2,權值〉三元組構成。由于Top-K興趣子圖查詢目的是根據查詢圖Q在數據圖G中查詢K個興趣度最高的匹配子圖,而由興趣度定義可知其隨著邊權值的增大而增大，因此為有效過濾不滿足條件的邊，本文將EF索引項按邊權值進行降序排列。仍以圖1為例，數據圖G包含AA、AK、AC、CK和KK五種類型的邊，其EF索引如圖4所示，其中id1、id2表示邊的兩個節點的編號，w表示邊的權值。

圖4　EF索引Fig. 4　Index of EF

2.3　基于GTSF索引的多因素候選集過濾

子圖匹配驗證的效率與構建的索引和候選集的過濾策略密切相關，利用高效的圖索引和過濾策略過濾掉明顯違背查詢需求的元素，獲得相對較小的候選集，可提高子圖匹配驗證的效率。因此，本文利用NTF索引和EF索引，針對節點和邊分別給出候選節點集過濾策略(CNFiltering)和候選邊集過濾策略(CEFiltering)，以實現對節點及邊的剪枝過濾。

2.3.1多因素候選節點集過濾

在大規模動態圖中，用戶常根據查詢需求，通過對某邊權值限制實現個性化查詢。因此查詢圖中節點可區分為特殊節點(帶有權值邊的端點稱為特殊節點)和普通節點，在進行候選節點篩選時，本文從節點類型、度、鄰接點個數、邊權值限制等多因素考慮，提出了CNFiltering策略，如算法1所示。

算法1CNFiltering algorithm。

輸入node topology feature indexTG， edge feature indexEG， node topology feature indexTQ， edge feature indexEQ；

輸出the candidate node setCN。

1)

CN=NULL；

2)

for(traverseeinEQ) do

/*遍歷EF索引，獲取查詢圖Q候選節點集CN*/

3)

if(w(e)!=0)

/*對特殊節點過濾*/

4)

CN←SNF(EG，e，CN)；

5)

CN←DF(TG，e，CN)；

6)

CN←ANLF(TG，e，CN)；

7)

else

/*對普通節點過濾*/

8)

CN←DF(TG，e，CN)；

9)

CN←ANLF(TG，e，CN)；

10)

end for

11)

OutputCN；

1)特殊節點過濾(Special Node Filtering， SNF)。對于特殊節點，其構成的邊必須滿足查詢圖中權值的限制，因此根據加權邊類型，利用EF索引，將不滿足權值限制的邊進行剪枝，以篩選出特殊節點候選集。

2)度過濾(Degree Filtering， DF)。候選集中各節點度不小于查詢節點度，因此利用NTF索引，根據查詢節點類型及度剪枝無效節點。

3)鄰接點標簽頻率過濾(Adjacent Node Label Frequency Filtering， ANLF)。候選節點不僅要滿足度的要求，同時每種類型鄰接點數都不小于對應查詢節點中同類型鄰接點數，為此,利用NTF索引在DF基礎上剪枝不滿足鄰接點各類型出現頻率的節點，從而獲得候選節點集。

以圖2中數據圖及查詢圖為例，Q中僅AC類型的邊(v1,v2)具有權值0.5，因此v1和v2為特殊節點，檢索EF索引，獲得邊權值不小于0.5的AC類型的邊為(10,16):0.8、(7,14):0.7、(15,14):0.6、(8,14):0.6和(7,4):0.5，再對其進行DF過濾和ANLF過濾，獲得v1和v2的候選集分別為{10,15,7,8}和{16,14,4}。對于普通節點僅使用DF過濾和ANLF過濾獲取節點的候選集，最終獲得查詢圖Q的候選節點集CN如圖5所示。

圖5　查詢圖Q的候選節點集CNFig. 5　Candidate node set CN of query graph Q

2.3.2候選邊集過濾

利用CNFiltering策略可有效剪枝去除不滿足要求的節點，獲得相對較少的查詢圖節點候選集。本節在候選節點集基礎上，利用數據圖的EF索引，充分挖掘節點和邊所蘊含的信息，提出候選邊集過濾策略，即CEFiltering，以實現對查詢圖候選集再一次剪枝，獲得更優的用于最終子圖匹配驗證的候選邊集。

1)特殊邊過濾。在查詢圖中，帶有權值的邊為特殊邊，針對每條特殊邊檢索數據圖的EF索引，篩選邊類型相同且權值不小于特殊邊權值的邊作為候選邊；然后判斷候選邊的兩端點是否在相應的候選節點集中，存在為有效邊，反之則無效，進而獲得特殊邊的候選邊集。

2)普通邊過濾。在查詢圖中，無權值的邊為普通邊，對普通邊的過濾僅需根據邊的類型檢索數據圖的EF索引，找到類型相同的邊并且邊的兩個端點應在對應的節點候選集中，從而獲得普通邊的候選集。

仍以圖2為例，查詢圖Q有AA、AC和CK三種類型的邊。其中只有AC類型的邊(v1,v2)帶有權值0.5， 利用EF索引找到AC類型的權值不小于0.5的邊，且滿足邊端點在CN中，因此(v1,v2)邊的候選集為{(10,16):0.8,(7,14):0.7, (15,14):0.6,(8,14):0.6,(7,4):0.5}。Q中CK類型的邊(v2,v4)為普通邊，檢索EF索引，找到CK類型的邊且兩端點在對應v2和v4節點候選集中的邊，獲得(v2,v4)的候選邊集為{(16,13),(4,3), (14,13)}。同理獲得其他普通邊候選集。查詢圖Q的候選邊集CE如圖6所示。

圖6　查詢圖Q的候選邊集CEFig. 6　Candidate edge set CE of query graph Q

2.4　興趣子圖匹配驗證

在進行Top-K興趣子圖匹配驗證時，圖的動態變化可能對匹配結果產生影響，因此為盡量保證查詢結果的準確性，本文將匹配過程分為初始匹配和動態修正兩個階段。

初始匹配驗證將在候選邊集CE之上進行。由于匹配驗證采用逐一邊匹配的方式，因此將最小候選邊集對應邊作為起始匹配邊進行廣度優先遍歷，可有效減少迭代次數，進而減少不必要的計算開銷。在介紹匹配驗證之前，首先介紹Size-c候選匹配及其上界值計算US(Size-c)兩個概念。

定義2Size-c候選匹配。一個Size-c候選匹配表示在子圖匹配中，對查詢圖的c條邊進行實例化的部分增長匹配，其興趣度為實例化邊的權值之和，其中c∈(1,n)，n為查詢圖的邊數。

定義3US(Size-c)。又稱Size-c候選匹配的興趣度上界值，其值為Size-c候選匹配中實例化邊的權值與沒有實例化邊的最大候選邊的權值之和。

初始匹配驗證具體過程如算法2。算法維護一個Top-K堆用于降序存儲興趣度最大的K個匹配結果；維護候選匹配堆CM用于升序存儲子圖匹配驗證過程中已經驗證存入Top-K堆但被之后的匹配結果替換的匹配，以及已經驗證但未存入Top-K堆的匹配。

算法2InitSubMatching algorithm。

輸入edge feature indexEQ， the candidate edge setCE， number of interesting subgraphK；

輸出Top-Kinteresting subgraphF， the candidate matching heapCM。

1)

CM=NULL；F=NULL；

2)

intCP，N=|EQ|，Top-K=K，O[|EQ|]；

3)

O[0] ←First(CE)；

/*確定起始邊*/

4)

O[ ]←traverseEQfromCE；

/*確定邊匹配順序*/

5)

for((u,v)′←traverseCE[O[0]]) do

/*實例化查詢圖Q，獲得初始Top-K堆*/

6)

CP←Size-1((u,v)′)；

7)

if(US(Size-1)

8)

return false；

9)

else

10)

for(c=2,3,…,n) do

11)

(u,v)″←traverseO[c] in |CP|；

12)

if((u,v)″ !=null)

13)

(u,v)″←traverse|CP|；

14)

CP←Size-c()；

15)

else return false；

16)

end for

17)

if(I(Size-n())<=I(Top-K.bottom))

18)

CM←Size-n()；

19)

update(CM)；

20)

return false；

21)

else

22)

CM←Top-K.bottom；

23)

update(CM)；

24)

delete(Top-K.bottom)；

25)

Top-K←Size-n()；

26)

update(Top-K)；

27)

end for

28)

F←Top-K；

29)

OutputF，CM；

針對圖2中的數據圖G和查詢圖Q，Top-K子圖匹配的K為2時的初始匹配過程：首先遍歷候選邊集CE，確定起始邊為(v2,v4)，從邊(v2,v4)開始進行廣度優先遍歷以獲得查詢圖邊的匹配順序為(v2,v4)→(v1,v2)→(v3,v2)→(v1,v3)；按照(v2,v4)邊的匹配順序實例化，先將(v2,v4)實例化為(16,13):0.7，則Size-1候選匹配為(v1,16,v3,13):0.8，接著進行Size-c(c=2,3,…,n，n為查詢圖Q的邊數)，獲得(10,16,1,13):1.9、(10,16,11,13):2.0兩個匹配子圖，將其存入Top-K堆中，繼續實例化獲得其他匹配；當Top-K堆滿時根據興趣度更新Top-K堆，以獲得初始匹配結果，同時將CM堆的子圖作為備用候選子圖。

節點或邊的插入、刪除、更改權值均導致圖的動態變化，而圖的變化可能影響查詢結果，為此本文將利用更新間隔內的圖變化對初始匹配結果進行動態修正，在保證查詢效率的基礎上進一步提高查詢結果的準確性。將更新間隔內的圖變化記錄收集形成待更新記錄集W。對于W內的插入記錄，以插入記錄對應邊為起始邊，按照廣度優先遍歷進行實例化，用得到的匹配子圖更新Top-K堆和備用候選子圖，獲得最終匹配結果(Top-K堆內的子圖)；對于W內的刪除記錄，若在Top-K堆和備用候選子圖中存在相關的節點或邊，則將對應候選子圖刪除，并用修改后的備用候選子圖中興趣度最大的子圖填滿Top-K堆，獲得查詢結果；對于W內的更改權值記錄，若Top-K堆或備用候選子圖中存在相關的節點或邊，則將重新比較變化子圖與其他子圖的興趣度，用前K個更新Top-K堆，作為最終查詢結果。

3　實驗與分析

本章將本文的DISQtop-k方法與目前具有代表性的RAM、RWM算法進行實驗對比，比較并分析不同數據量級的數據集上索引創建時間、索引存儲開銷及子圖查詢效率。

3.1　實驗環境及數據集

本文實驗環境為Intel Pentium CPU G3220@3.00 GHz處理器、4 GB內存，500 GB硬盤，編程語言為Java，開發環境為eclipse 6.5。

實驗分別在DBLP真實數據集及模擬數據集上完成。真實數據集利用NetClus[15]聚類方法將DBLP數據聚類成由作者、關鍵字和會議組成的作者合作關系網。將DBLP數據集(節點數為217 080，邊數為1 022 980)分為3個子集合GR1(包括104個節點，13 774條邊，約1萬個節點規模)、GR2(包括105個節點，392 482條邊，約10萬個節點規模)，GR3(包括217 080個節點，1 022 980條邊，約22萬個節點規模)。模擬數據集G1、G2、G3和G4則通過GT-Graph的圖生成器R-MAT[16]創建，其節點數分別為103、104、105和106，每個圖的邊數為其節點的10倍，每個節點從1到5隨機分配屬性標簽性，每條邊的權值隨機產生[0,1]區間的值。

3.2　實驗分析

3.2.1索引創建時間及存儲開銷

圖7(a)和(b)分別展示了模擬數據集上和真實數據集上不同索引的構建時間對比情況。RAM算法需建立SPath索引，RWM算法需建立Topology、MMW索引。如圖7所示，各索引創建時間均隨圖規模的增大而增長。其中EF索引創建時間遠小于其他索引，這是因為其只需對不同的標簽邊進行排序，無需計算復雜的節點關系等；NTF索引明顯優于Topology+MMW(D=2)和SPath索引，因為NTF索引僅需遍歷一次數據圖即可獲得所有節點及其鄰接點的關系，然而Topology+MMW(D=2)和SPath索引受D的約束，隨著D值的增加，索引構建時間將會呈指數增長。

圖7　不同數據集上的索引構建時間對比Fig. 7　Index building time comparison for different datasets

表1展示了在模擬數據集和真實數據集上不同索引的存儲開銷。各索引的存儲空間均隨圖規模的增大而變大，其中NTF及EF索引所占的內存較少，因為NTF索引僅需要存儲各節點的度及一跳鄰接點信息，而EF索引只記錄邊的權值信息;而SPath、MMW和Topology 則根據D值的不同，需要記錄各節點多跳鄰接點信息，因此隨著D值的增加，索引的存儲空間將呈指數增長。

表1　不同數據集上的索引存儲空間對比　KBTab. 1　Index size comparison for different datasets　KB

表2　不同數據集上的算法查詢時間的比較　sTab. 2　Query time comparison for different datasets　s

3.2.2興趣子圖查詢效率分析

表2展示了在不同規模數據集下查詢時間對比情況。實驗針對無權查詢圖(Q1)和加權查詢圖(Q2)，觀察隨數據圖規模的增大，各種算法的查詢時間變化情況。其中，Q1是圖2(b)中查詢圖Q去除權值后的圖，Q2是圖2(b)中查詢圖Q，RAM和RWM索引中D=2。

從表2可以看出，各種算法的查詢時間隨著數據規模增大而增大。 RAM和RWM算法對于有權查詢圖的查詢，需要首先查詢所有匹配子圖后再進行滿足權值限制子圖的篩選，而DISQtop-k算法則在候選集篩選時已過濾不滿足條件的節點及邊，避免了重復計算，所以運行時間更短、增長較平緩。

3.2.3查詢圖變化對子圖查詢效率的影響

分析可知，查詢圖節點個數以及K值的設定均對子圖查詢時間具有一定的影響，表3展示了在模擬數據集G2和DBLP數據集的子集GR1上，DISQtop-K針對不同規模的查詢圖Q及不同K值設定下查詢時間對比情況。

從表3中可以看出，當查詢圖及K值的增大，查詢時間均隨之增加。當查詢圖Q相同時，不同的K值間的查詢時間波動較小。

表3　不同數據集上的DISQtop-k算法針對不同查詢圖、K值的查詢時間對比Tab. 3　Query time comparison of different query graph and K value by DISQtop-K algorithm for different datasets

4　結語

本文提出一種適用于大規模動態標簽圖中的Top-K興趣子圖查詢方法，即 DISQtop-K方法。該方法首先建立由NTF和EF索引構成的GTSF索引，基于該索引提出了多因素候選集過濾策略，對查詢圖候選集進行有效剪枝；充分考慮圖動態變化下產生的查詢誤差，對候選集進行初始匹配及動態修正以獲得查詢結果。真實數據集及模擬數據集上的實驗結果表明，該方法在大規模動態標簽圖上具有較高的查詢效率，且查詢結果具有一定的實際意義。

參考文獻:

[1]SONMEZ A B, CAN T. Comparison of tissue/disease specific integrated networks using directed graphlet signatures [J]. BMC Bioinformatics, 2017, 18(Suppl. 4): 135.

[2]張海威,解曉芳,段媛媛,等.一種基于自適應結構概要的有向標簽子圖匹配查詢算法[J].計算機學報,2017,40(1):52-71. (ZHANG H W, XIE J F, DUAN Y Y, et al.An algorithm for subgraph matching based on adaptive structural summary of labeled directed graph data[J]. Chinese Journal of Computers, 2017, 40(1): 52-71.)

[3]ULLMANN J R. An algorithm for subgraph isomorphism [J]. Journal of the ACM (JACM), 1976, 23(1): 31-42.

[4]CORDELLA L P, FOGGIA P, SANSONE C, et al. A (sub)graph isomorphism algorithm for matching large graphs [J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2004, 26(10): 1367-1372.

[5]SUN Z, WANG H, WANG H, et al. Efficient subgraph matching on billion node graphs [J]. Proceedings of the VLDB Endowment, 2012, 5(9): 788-799.

[6]HAN W-S, LEE J, LEE J-H. TurboISO: towards ultrafast and robust subgraph isomorphism search in large graph databases [C]// SIGMOD ’13: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2013: 337-348.

[7]REN X, WANG J. Exploiting vertex relationships in speeding up subgraph isomorphism over large graphs [J]. Proceeding of the VLDB Endowment, 2015, 8(5): 617-628.

[8]BI F, CHANG L, LIN X, et al. Efficient subgraph matching by postponing Cartesian products [C]// SIGMOD ’16: Proceedings of the 2016 International Conference on Management of Data. New York: ACM, 2016: 1199-1214.

[9]HOLDER L B, COOK D, DJOKO S. Substructure discovery in the SUBDUE system [C]// AAAIWS’94: Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining. Seattle, WA: IAAA, 1994: 169-180.

[10]ZHU F, QU Q, LO D, et al. Mining Top-Klarge structural patterns in a massive network [J]. Proceedings of the VLDB Endowment, 2011, 4(11): 807-818.

[11]ZHAO P, HAN J. On graph query optimization in large networks [J]. Proceedings of the VLDB Endowment, 2010, 3(1/2): 340-351.

[12]HE H, SINGH A K. Query language and access methods for graph databases [M]// Managing and Mining Graph Data. Boston: Springer, 2010: 125-160.

[13]YAN X, HE B, ZHU F, et al. Top-Kaggregation queries over large networks [C]// ICDE 2010: Proceedings of the 2010 IEEE 26th International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2010: 377-380.

[14]GUPTA M, GAO J, YAN X, et al. Top-Kinteresting subgraph discovery in information networks [C]// ICDE 2014: Proceedings of the 2014 IEEE 30th International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2014: 820-831.

[15]SUN Y, YU Y, HAN J. Ranking-based clustering of heterogeneous information networks with star network schema [C]// KDD ’09: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2009: 797-806.

[16]CHAKRABARTI D, ZHAN Y, FALOUTSOS C. R-MAT: a recursive model for graph mining [C]// SIAM International Conference on Data Mining. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), 2004: 442-446.