大規(guī)模標(biāo)簽圖中的動(dòng)態(tài)Top-K興趣子圖查詢

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

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

0　引言

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

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

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

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

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

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

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

1　相關(guān)工作

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

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

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

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

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

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

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

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

2.1　問(wèn)題描述

2.1.1圖標(biāo)簽

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

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

2.1.2興趣子圖

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

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

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

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

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

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

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

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

2.2　圖拓?fù)浣Y(jié)構(gòu)特性索引

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

2.2.1NTF索引

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

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

圖3　NTF索引Fig. 3　Index of NTF

2.2.2EF索引

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

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

圖4　EF索引Fig. 4　Index of EF

2.3　基于GTSF索引的多因素候選集過(guò)濾

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

2.3.1多因素候選節(jié)點(diǎn)集過(guò)濾

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

3)

if(w(e)!=0)

/*對(duì)特殊節(jié)點(diǎn)過(guò)濾*/

4)

CN←SNF(EG，e，CN)；

5)

CN←DF(TG，e，CN)；

6)

CN←ANLF(TG，e，CN)；

7)

else

/*對(duì)普通節(jié)點(diǎn)過(guò)濾*/

8)

CN←DF(TG，e，CN)；

9)

CN←ANLF(TG，e，CN)；

10)

end for

11)

OutputCN；

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

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

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

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

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

2.3.2候選邊集過(guò)濾

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

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

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

仍以圖2為例，查詢圖Q有AA、AC和CK三種類(lèi)型的邊。其中只有AC類(lèi)型的邊(v1,v2)帶有權(quán)值0.5， 利用EF索引找到AC類(lèi)型的權(quán)值不小于0.5的邊，且滿足邊端點(diǎn)在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類(lèi)型的邊(v2,v4)為普通邊，檢索EF索引，找到CK類(lèi)型的邊且兩端點(diǎn)在對(duì)應(yīng)v2和v4節(jié)點(diǎn)候選集中的邊，獲得(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　興趣子圖匹配驗(yàn)證

在進(jìn)行Top-K興趣子圖匹配驗(yàn)證時(shí)，圖的動(dòng)態(tài)變化可能對(duì)匹配結(jié)果產(chǎn)生影響，因此為盡量保證查詢結(jié)果的準(zhǔn)確性，本文將匹配過(guò)程分為初始匹配和動(dòng)態(tài)修正兩個(gè)階段。

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

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

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

初始匹配驗(yàn)證具體過(guò)程如算法2。算法維護(hù)一個(gè)Top-K堆用于降序存儲(chǔ)興趣度最大的K個(gè)匹配結(jié)果；維護(hù)候選匹配堆CM用于升序存儲(chǔ)子圖匹配驗(yàn)證過(guò)程中已經(jīng)驗(yàn)證存入Top-K堆但被之后的匹配結(jié)果替換的匹配，以及已經(jīng)驗(yàn)證但未存入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

/*實(shí)例化查詢圖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；

針對(duì)圖2中的數(shù)據(jù)圖G和查詢圖Q，Top-K子圖匹配的K為2時(shí)的初始匹配過(guò)程：首先遍歷候選邊集CE，確定起始邊為(v2,v4)，從邊(v2,v4)開(kāi)始進(jìn)行廣度優(yōu)先遍歷以獲得查詢圖邊的匹配順序?yàn)?v2,v4)→(v1,v2)→(v3,v2)→(v1,v3)；按照(v2,v4)邊的匹配順序?qū)嵗葘?v2,v4)實(shí)例化為(16,13):0.7，則Size-1候選匹配為(v1,16,v3,13):0.8，接著進(jìn)行Size-c(c=2,3,…,n，n為查詢圖Q的邊數(shù))，獲得(10,16,1,13):1.9、(10,16,11,13):2.0兩個(gè)匹配子圖，將其存入Top-K堆中，繼續(xù)實(shí)例化獲得其他匹配；當(dāng)Top-K堆滿時(shí)根據(jù)興趣度更新Top-K堆，以獲得初始匹配結(jié)果，同時(shí)將CM堆的子圖作為備用候選子圖。

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

3　實(shí)驗(yàn)與分析

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

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

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

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

3.2　實(shí)驗(yàn)分析

3.2.1索引創(chuàng)建時(shí)間及存儲(chǔ)開(kāi)銷(xiāo)

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

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

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

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

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

3.2.2興趣子圖查詢效率分析

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

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

3.2.3查詢圖變化對(duì)子圖查詢效率的影響

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

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

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

4　結(jié)語(yǔ)

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

參考文獻(xiàn):

[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].計(jì)算機(jī)學(xué)報(bào),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.