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

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

0　引言

圖因獨有的結(jié)構(gòu)化特征而廣泛用于描述生物技術(shù)[1]、軍事管理等領(lǐng)域的復(fù)雜網(wǎng)絡(luò)關(guān)系，而網(wǎng)絡(luò)中數(shù)據(jù)類型的多樣化則可通過具有節(jié)點特征標(biāo)識能力的標(biāo)簽圖表示。子圖查詢[2]是圖數(shù)據(jù)處理的基本問題，即在數(shù)據(jù)圖中搜索同構(gòu)于查詢圖的所有匹配子圖。

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

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

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

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

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

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

1　相關(guān)工作

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

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

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

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

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

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

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

2　動態(tài)Top-K興趣子圖近似查詢

2.1　問題描述

2.1.1圖標(biāo)簽

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

以DBLP作者合作關(guān)系網(wǎng)為例，網(wǎng)絡(luò)中作者、研究領(lǐng)域關(guān)鍵字以及學(xué)術(shù)會議均抽象為圖中節(jié)點，如圖1所示，用標(biāo)簽A、K、C表示，即利用圖標(biāo)簽表示節(jié)點的不同種類，邊則表示三者之間的關(guān)系，邊權(quán)值用以表示作者間合作關(guān)系以及作者參與會議的程度、關(guān)鍵字間相似程度等。

2.1.2興趣子圖

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

圖1　數(shù)據(jù)圖GFig. 1　Data graph G

2.1.3動態(tài)Top-K近似查詢

興趣子圖查詢將根據(jù)用戶查詢需求，從數(shù)據(jù)圖中搜索與查詢圖結(jié)構(gòu)相同、邊權(quán)值滿足某種限制且聯(lián)系緊密的所有子圖。在實際應(yīng)用中，常通過標(biāo)簽圖中邊權(quán)值大小來標(biāo)識兩個實體的關(guān)聯(lián)程度，各個實體間的關(guān)聯(lián)程度則反映整個網(wǎng)絡(luò)的緊密程度，本文將用圖的興趣度來表示，其規(guī)范化定義如下：

定義1興趣度。若M是查詢圖Q在數(shù)據(jù)圖G中的一個匹配子圖，則組成M的所有邊的權(quán)值之和即為該匹配子圖的興趣度，表示為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

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

2.2　圖拓撲結(jié)構(gòu)特性索引

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

2.2.1NTF索引

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

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

圖3　NTF索引Fig. 3　Index of NTF

2.2.2EF索引

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

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

圖4　EF索引Fig. 4　Index of EF

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

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

2.3.1多因素候選節(jié)點集過濾

在大規(guī)模動態(tài)圖中，用戶常根據(jù)查詢需求，通過對某邊權(quán)值限制實現(xiàn)個性化查詢。因此查詢圖中節(jié)點可區(qū)分為特殊節(jié)點(帶有權(quán)值邊的端點稱為特殊節(jié)點)和普通節(jié)點，在進行候選節(jié)點篩選時，本文從節(jié)點類型、度、鄰接點個數(shù)、邊權(quán)值限制等多因素考慮，提出了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候選節(jié)點集CN*/

3)

if(w(e)!=0)

/*對特殊節(jié)點過濾*/

4)

CN←SNF(EG，e，CN)；

5)

CN←DF(TG，e，CN)；

6)

CN←ANLF(TG，e，CN)；

7)

else

/*對普通節(jié)點過濾*/

8)

CN←DF(TG，e，CN)；

9)

CN←ANLF(TG，e，CN)；

10)

end for

11)

OutputCN；

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

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

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

以圖2中數(shù)據(jù)圖及查詢圖為例，Q中僅AC類型的邊(v1,v2)具有權(quán)值0.5，因此v1和v2為特殊節(jié)點，檢索EF索引，獲得邊權(quán)值不小于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}。對于普通節(jié)點僅使用DF過濾和ANLF過濾獲取節(jié)點的候選集，最終獲得查詢圖Q的候選節(jié)點集CN如圖5所示。

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

2.3.2候選邊集過濾

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

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

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

仍以圖2為例，查詢圖Q有AA、AC和CK三種類型的邊。其中只有AC類型的邊(v1,v2)帶有權(quán)值0.5， 利用EF索引找到AC類型的權(quán)值不小于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類型的邊且兩端點在對應(yīng)v2和v4節(jié)點候選集中的邊，獲得(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興趣子圖匹配驗證時，圖的動態(tài)變化可能對匹配結(jié)果產(chǎn)生影響，因此為盡量保證查詢結(jié)果的準(zhǔn)確性，本文將匹配過程分為初始匹配和動態(tài)修正兩個階段。

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

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

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

初始匹配驗證具體過程如算法2。算法維護一個Top-K堆用于降序存儲興趣度最大的K個匹配結(jié)果；維護候選匹配堆CM用于升序存儲子圖匹配驗證過程中已經(jīng)驗證存入Top-K堆但被之后的匹配結(jié)果替換的匹配，以及已經(jīng)驗證但未存入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中的數(shù)據(jù)圖G和查詢圖Q，Top-K子圖匹配的K為2時的初始匹配過程：首先遍歷候選邊集CE，確定起始邊為(v2,v4)，從邊(v2,v4)開始進行廣度優(yōu)先遍歷以獲得查詢圖邊的匹配順序為(v2,v4)→(v1,v2)→(v3,v2)→(v1,v3)；按照(v2,v4)邊的匹配順序?qū)嵗?，先?v2,v4)實例化為(16,13):0.7，則Size-1候選匹配為(v1,16,v3,13):0.8，接著進行Size-c(c=2,3,…,n，n為查詢圖Q的邊數(shù))，獲得(10,16,1,13):1.9、(10,16,11,13):2.0兩個匹配子圖，將其存入Top-K堆中，繼續(xù)實例化獲得其他匹配；當(dāng)Top-K堆滿時根據(jù)興趣度更新Top-K堆，以獲得初始匹配結(jié)果，同時將CM堆的子圖作為備用候選子圖。

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

3　實驗與分析

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

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

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

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

3.2　實驗分析

3.2.1索引創(chuàng)建時間及存儲開銷

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

圖7　不同數(shù)據(jù)集上的索引構(gòu)建時間對比Fig. 7　Index building time comparison for different datasets

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

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

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

3.2.2興趣子圖查詢效率分析

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

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

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

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

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

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

4　結(jié)語

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

參考文獻:

[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]張海威,解曉芳,段媛媛,等.一種基于自適應(yīng)結(jié)構(gòu)概要的有向標(biāo)簽子圖匹配查詢算法[J].計算機學(xué)報,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.