基于增量信息索引的子圖查詢算法

王超琿　黃一夫

(復旦大學計算機科學技術學院智能信息處理重點實驗室　上海 200433)

?

基于增量信息索引的子圖查詢算法

王超琿黃一夫

(復旦大學計算機科學技術學院智能信息處理重點實驗室上海 200433)

當前圖數據庫中的子圖同構查詢算法主要是依賴倒排索引，然而處理那些具有龐大數據的數據庫和復雜的查詢愈發成為挑戰。研究目的是設計一個算法，使用新的索引作為查詢處理的核心，記錄查詢圖的每一個細小改變，并使用一種特殊的數據結構來維護。先是引出一個索引算法，然后逐漸分析整個索引、查詢過程，并利用該算法實現一個系統，最后在不同數據集和查詢上進行實驗。實驗證明了該算法具有良好的時間、空間效率和擴展性。新的索引算法能夠支持更大的查詢圖和更加靈活的查詢。通過實現的系統和其他系統的對比實驗，驗證了算法的有效性。

圖數據庫子圖同構片段子圖查詢索引查詢算法

0　引　言

隨著互聯網步入2.0時代，圖數據庫越來越多地出現在我們的生活中，例如社交網絡、蛋白質網絡、化學結構等，對于它的檢索需求也與日俱增。你可以在Facebook查看你好友或者好友的好友發出的消息；你可以在生物信息數據庫中研究某種DNA、某種氨基酸、某種蛋白質；你可以在化學數據庫中查詢某種化學結構。支撐這些應用的底層存儲數據庫不是普通的數據庫，而是圖數據庫。當你使用這些應用時會有圖數據庫查詢，即使你沒有意識到，這一切都在不知不覺中進行著。

有的圖數據庫本身就是一張大圖[1]，有的圖數據庫中存儲了千千萬萬的小圖。傳統的數據庫只能將一個圖存為一個整體，不能利用其中的結構信息。隨著技術的進步和發展，圖數據庫的實用價值不斷增大，所以使用的比例也不斷加大。

圖數據庫需要檢索技術，本文研究的檢索是子圖同構檢索。進行這樣的檢索有幾個要求：檢索結果需要完全正確，不能漏掉數據庫中應該檢索到的圖，或者檢索出不正確的圖；檢索處理的速度需要足夠快，同時使用的內存要合理。

順序枚舉數據庫里的每個圖，并且查看查詢是不是它的子圖是效率比較低的做法。因為子圖同構查詢是NP完全問題[2]，在整個圖數據庫上進行，花費很大。因此，現在通行的做法是建立索引，之后在查詢時進行兩階段的處理：過濾和驗證。過濾是在圖數據庫中選出部分圖組成候選集集合，過濾掉一些不符合的圖，縮小需要運行子圖同構檢測的數據范圍大小。這時，候選集已經大大減小了，需要運行子圖同構檢測的次數變少了，可以加快查詢的速度。驗證部分運行子圖同構檢測，確定正確的結果。如果過濾步驟能夠顯著地降低候選集的大小，那么這個基于索引的兩階段算法就是有效并且實用的。候選集的大小可以作為不同算法性能直接比較的一個重要指標。

GraphGrep[3]提出了子圖查詢問題，Tree+Δ[4]使用了樹作為索引，gIndex[5]使用了圖作為索引，FG-Index[6]提出了避免過濾階段的方法。傳統的索引是建立頻繁子圖的倒排索引，沒有利用其中的結構信息。本文在構建索引時在子圖之間增加信息，構建的索引是由子圖構成的圖。

本文研究的主要目的是設計一個符合以上要求的支持子圖查詢的算法。

1　基本概念

1.1相關定義

定義2圖G1子圖同構于圖G2(表示為G1?G2)，若存在一個單射函數f:V1→V2，使得?u∈V1都有φ1(u)=φ2(f(u))；?(u,v)∈E1都有(f(u),f(v))∈E2。

定義3一個圖G的正規表示Canon(G)是一個帶標簽的圖，同構于G，且任意同構于G的圖都和G有相同的正規表示，正規表示是唯一的。找尋圖的正規表示的問題叫作圖的正規化。因此，如果有一個圖的正規化的算法，這個算法同樣能夠解決圖的同構問題。對于兩個圖G和H，計算它們的正規表示Canon(G)和Canon(H)，然后檢測兩個正規表示是否相同。如果相同必定同構，如果不同必定不同構[7]。

定義5術語片段用于稱呼圖數據庫或者查詢圖中的一個小的子圖。

1.2問題描述

本文研究的圖數據庫，是由許多的小圖組成的。每個小圖的規模都不大(點數、邊數<200)，但是小圖的數目非常多(10×103～200×103)。給定圖數據庫D={G1,G2,…,Gn}，查詢圖Q。子圖查詢問題是找出所有的Gi，使得Q?Gi。

2　算　法

傳統的索引是建立頻繁子圖的倒排索引，沒有利用其中的結構信息。并且傳統的索引沒有考慮到索引本身和查詢之間的聯系。本文在構建索引時在子圖之間增加信息，構建的索引是由子圖構成的圖。這是為了查詢時使用的特性而特別優化的。

圖1是整體系統的結構，包含有索引構建器、查詢處理機和驗證器。索引構建器能夠輸入圖數據庫并且為其構建索引。查詢處理器用于處理查詢，輸入查詢后對查詢進行分析，在讀取索引的同時維護一個數據結構保存圖的特征信息。這些信息是同時和查詢圖和索引相關聯的，從這個數據結構中可以提取候選集，傳遞給驗證器。驗證器用于驗證候選集，輸出查詢結果。

圖1　系統結構圖

2.1增量信息索引

本文提出的增量信息索引結構本身是一個分層的有向無環圖，圖2是從本文使用的索引所進行的可視化展示中截取的。

圖2　增量信息索引結構圖

定義9若有圖數據庫D和其上的頻繁片段集合F，可以構建增量信息索引I={I1,I2,…,In}。索引中的每一項Ii都對應一個片段，由標識符、正規編碼、類型、大小、轉移信息、父親和支持圖集合組成。

這里我們只將頻繁片段和顯著非頻繁片段放入增量信息索引中，這樣做的原因是所有片段的種類是非常多的，不可能全部放入索引中。已知使用頻繁片段是一種能大幅度降低片段數量的方法，可以通過調節最小支持度閾值α來控制數量，并且過濾效果很好。本文使用一種已有的圖數據庫挖掘算法gSpan生成頻繁片段[9]。

片段的轉移信息是一個數組，表示片段上所有可以進行的操作和操作的結果。操作就是給片段增加一條邊，因為增加完邊后片段仍舊是連通的，所以操作有兩種：

(1) 增加邊的同時增加一個新的結點，新的邊將新的結點連接到片段中一個已有的結點上，我們記這種操作為Nx(y)。其中x為已有結點的編號，y為新結點的標簽。如N0(C)表示將一個標簽為C的新結點連接到已有的0號結點上。

(2) 在已有的兩個沒有邊連接的結點之間連接一條邊，我們記這種操作為Cx-y。其中x、y分別為已有兩個結點的編號，且x

定義10操作的結果叫作轉移(trans)，形如 (id,newIds)。若這個操作是對片段a做的，得到片段a′，a′的正規表示為b，那么id為b的標識符，newIds表示的是a′到b的同構映射函數f。

2.2增量信息索引的構建

首先，將所有頻繁片段連同它們的信息(包括它們的支持圖集合)放入增量信息索引中。然后依次枚舉所有的頻繁片段，并對其嘗試前文所提到的兩種操作：增加邊的同時增加一個新的結點，在已有的兩個沒有邊連接的結點之間連接一條邊。若操作的結果從片段f得到新圖newGraph和轉移newIds，片段f在索引中對應的項為If。根據newGraph的性質進行以下操作：

1) 若newGraph是頻繁片段，對應索引中的項InewGraph，我們記錄三元組(op,InewGraph.id,newIds)到索引中If項的信息中。

3) 若newGraph是顯著非頻繁片段，對應索引中的項InewGraph，我們記錄三元組(op,InewGraph.id,newIds)到索引中If項的信息中。

4) 若newGraph是非顯著非頻繁片段，我們不做任何事。

最后檢查所有的DIF，若其支持圖集合為空，則其支持圖集合的候選集C可由它所有父節點支持圖集合的交集得到。在C上運行驗證器可以得到其支持圖集合。

2.3簡單紡錘形圖

在文獻[10]中，作者提出了紡錘形圖的概念。本文在此基礎上提出了簡單紡錘形圖，作為查詢圖的特性信息。簡單紡錘形圖改變了圖中每個結點所代表的意義和包含的信息，不過還是繼承了其紡錘形的特征和思想。文獻[10]中使用多個紡錘形圖，本文只使用一個簡單紡錘形圖；原有紡錘形圖每個結點都是原有查詢中的一個片段，本文只是索引項的標識符；原有紡錘形圖中結點的總個數一定是查詢圖所有連通子圖的個數，本文簡單紡錘形圖中結點數量的增長較為平緩。因此本文縮減了操作簡單紡錘形圖的時間，使得添加邊、刪除邊的操作更加高效。

定義11簡單紡錘形圖(SimpleSPIG)是一個圖，結點i帶有數據{id,edgeSets}。i.id是增量信息索引中索引項的標識符。若兩個簡單紡錘形圖中的結點各自對應的索引項在增量信息索引中有邊連接，那么在簡單紡錘形圖中這兩個結點也有邊連接。i.edgeSets是邊集的集合且不為空。

圖3展示了簡單紡錘形圖的結構。當用戶插入了一條邊后，簡單紡錘形圖只會增加結點和結點中的邊集。當用戶刪除邊后，簡單紡錘形圖中的結點和結點中的邊集只會減少。我們需要實現增加邊和刪除邊的算法。

圖3　簡單紡錘形圖

2.4增加查詢邊算法

每次加入新的邊時，會更新簡單紡錘形圖。用廣度優先搜索從小到大找出所有包含種子邊的查詢圖的連通子圖。廣度優先搜索所使用的隊列里存儲的是用于表示片段的三元組(查詢結點標識符數組,邊集,索引項的標識符)。其中查詢結點標識符數組和邊集可以定位片段在查詢圖中的位置，索引項的標識符可以定位片段在索引中的位置。

每次從隊列中取出一個三元組后，我們嘗試所有給它加邊的方法，加上新的邊得到新的邊集。若還沒有被處理過，使用加邊操作在索引信息中查找。若能找到對應的轉移，利用查詢結點標識符數組和轉移中的newIds構建新的查詢結點標識符數組，并且將新的三元組加入到隊列中去。并且，同時將標識符添加到簡單紡錘形圖中，這里添加時需要使用父親信息。這是因為若有父親已經存在在簡單紡錘形圖中，我們需要連一條到父親的邊。然后將邊集加入到簡單紡錘形圖結點的邊集中。

等到隊列全部處理完成的時候，算法也就終止了，此時更新也完成了。

2.5刪除查詢邊算法

刪除一條邊的算法只需要對簡單紡錘形圖進行更新就可以了，不需要使用到索引的信息。其主要的思想是移除所有簡單紡錘形圖中包含有需要刪除邊的邊集，若移除后簡單紡錘形圖中結點的邊集集合為空，說明此結點的限制不必再應用于這個查詢，可以移除這個結點了。更新完成后就可以得到所需的新的簡單紡錘形圖。

2.6得到查詢結果

這里需要根據簡單紡錘形圖的層數分兩種情況：

1) 若層數存在和查詢大小相同的這一層，簡單紡錘形圖形成一個完整的紡錘形，那么說明查詢本身就在索引中出現過。可以直接使用索引的支持圖集合作為查詢的結果，不需要再做驗證。

2) 否則，還需要再次通過驗證器驗證才能作為查詢的結果。先從簡單紡錘形圖中所有葉子結點中取出它們的支持圖集合，并把這些集合的交集作為查詢結果的候選集，驗證完后作為查詢結果。只取所有的葉子結點是因為，若一個結點不是葉子結點，那么它一定有一個后代并且這個后代的支持圖集合是它的支持圖集合的子集，所以沒有必要再和非葉子結點的支持圖集合做交集操作。

3　實驗結果與分析

本文所實現的程序稱為Inc-Info，將與之前的算法Prague進行比較，并進行性能測試。實驗是在一臺IntelCorei7-4700MQ處理器、12GB內存、運行Windows8.1x64操作系統的計算機上進行的。實驗環境上安裝有Java1.8和Graphviz2.38。

實驗的數據集是AIDS抗病毒數據集，是一個真實的數據集，總共包含有43 000個化學結構。取頻率閾值α為0.1，并運行gSpan生成頻繁片段。

圖4顯示了在AIDS數據集上建立索引，得到片段數與索引大小、片段大小的關系。頻繁片段的總數為2847，構建時間為70分鐘，總索引大小為139.3MB，其中支持圖集合占138.5MB，數據庫文件占用磁盤總空間237MB。實驗表明，片段個數會隨著片段大小的增長而增多，但是達到一個最大值后反而會下降，最后歸零，說明此算法片段數是可控的。在最后得到的增量信息索引中，支持圖集合占據了絕大部分空間，說明本算法表示索引結構部分的信息是十分高效的。

圖4　索引大小分布圖

本文手工構建了18個查詢圖，作為測試樣例。在Inc-Info和Prague上輸入測試Q1-Q18，得到查詢用時，見圖5、圖6所示。其中Q7-Q12、Q15-Q18的圖比較大，Prague無法處理，因此沒有結果。可以發現Inc-Info的查詢用時較小。

圖5　Q1-Q9測試用時

圖6　Q10-Q18測試用時

表1是在Inc-Info和Prague上輸入Q1后，刪除一條邊所獲得的操作用時。Prague不支持刪除邊5-邊7的操作，因為Prague不能留下不連通的查詢圖，這點上Inc-Info較為靈活。而且可以看到Inc-Info較Prague在時間效率上有優勢。

表1　刪除邊測試結果

4　結　語

本文提出了能夠快速轉移的新索引結構、一種新的查詢時數據結構簡單紡錘形圖，組成一種新的相似度查詢過濾算法。這種新算法可以支持更大的查詢圖，并有更高的查詢性能。通過實驗，將本文系統和現有系統進行比較，證明了本文提供的算法在實踐上也具有良好的表現。未來可能的研究方向將關注如何縮小增量信息索引的大小，加快索引構建速度。

[1]SunZ,WangHZ,WangHX,etal.Efficientsubgraphmatchingonbillionnodegraphs[J].ProceedingsoftheVLDBEndowment,2012,5(9):788-799.

[2]GareyMR,JohnsonDS.Computersandintractability:aguidetothetheoryofNP-completeness[M].USA:W.H.FreemanandCompany,1979.

[3]GiugnoR,ShashaD.GraphGrep:afastanduniversalmethodforqueryinggraphs[C]//Proceedingsofthe16thInternationalConferenceonPatternRecognition,Quebec,Canada,2002,2:112-115.

[4]ZhaoPX,YuJX,YuPS.Graphindexing:tree+delta>=graph[C]//Proceedingsofthe33rdInternationalConferenceonVeryLargeDataBases,2007:938-949.

[5]YanXF,YuPS,HanJW.Graphindexing:afrequentstructure-basedapproach[C]//Proceedingsofthe2004ACMSIGMODInternationalConferenceonManagementofData,2004:335-346.

[6]ChengJ,KeYP,NgW,etal.FG-Index:towardsverification-freequeryprocessingongraphdatabases[C]//Proceedingsofthe2007ACMSIGMODInternationalConferenceonManagementofData,2007:857-872.

[7]Canonicalform[EB/OL].Wikipedia[2015-03-20].http://en.wikipedia.org/wiki/Canonical_form.

[8]JinC,BhowmickSS,XiaoXK,etal.GBLENDER:towardsblendingvisualqueryformulationandqueryprocessingingraphdatabases[C]//Proceedingsofthe2010ACMSIGMODInternationalConferenceonManagementofData,2010:111-122.

[9]YanXF,HanJW.gSpan:graph-basedsubstructurepatternmining[C]//Proceedingsofthe2002IEEEInternationalConferenceonDataMining,2002:721-724.

[10]JinCJ,BhowmickSS,ChoiB,etal.Prague:towardsblendingpracticalvisualsubgraphqueryformulationandqueryprocessing[C]//Proceedingsofthe2012IEEE28thInternationalConferenceonDataEngineering,2012:222-233.

ASUBGRAPHQUERYALGORITHMBASEDONINCREMENTALINFORMATIONINDEX

WangChaohuiHuangYifu

(KeyLabofIntelligentInformationProcessing,SchoolofComputerScience,FudanUniversity,Shanghai200433,China)

Currentlysubgraphisomorphicqueryalgorithmsingraphdatabasemainlydependoninvertedindex.However,theprocessingofthosegraphdatabaseswithhugedataandthecomplicatedqueriesincreasinglybecomesachallenge.Thepurposeofourresearchistodesignanalgorithm,weusedanewindexasthecoreofqueryprocessing,recordedeverytinychangeinquerygraph,andmaintaineditwithaspecialdatastructure.Firstweintroducedanindexalgorithm,andthengraduallyanalysedthewholeprocessofindexandquery,andusedthealgorithmtohaveimplementedasystem,finallywecarriedouttheexperimentsondifferentdatasetsandqueries.Thisalgorithmhasbeenprovedwithgoodtimeandspaceproductivityandscalability.Thenewindexalgorithmisabletosupportgreaterquerygraphandmoreflexiblequery.Throughtheimplementedcomparativeexperimentsbetweenthissystemandothersystems,weverifiedtheefficiencyofthisalgorithm.

GraphdatabaseSubgraphisomorphismFragmentSubgraphqueryIndexQueryalgorithm

2015-05-18。王超琿，碩士生，主研領域：數據庫。黃一夫，碩士生。

TP

ADOI:10.3969/j.issn.1000-386x.2016.10.009