胡一然，宋中山，孫 翀，鄭 祿

（中南民族大學 計算機科學學院，湖北 武漢 430070）

0 引言

圖模型作為一種重要的數(shù)據(jù)結構，在現(xiàn)實世界中被廣泛應用于如社交網(wǎng)絡、城市道路網(wǎng)絡、生物網(wǎng)絡等眾多領域。子圖搜索是在數(shù)據(jù)圖中找到與查詢圖同構且滿足用戶設定條件的子圖集合[1]。1976年，首個子圖搜索算法被 Ullmann[2]提出；隨后，VF2、Spath、GraphQL、RWM等經(jīng)典算法通過索引和優(yōu)化策略提高搜索效率[3-6]。

然而，上述大多數(shù)算法僅用于無權圖的搜索，且對于大規(guī)模數(shù)據(jù)圖的搜索效率并不理想。目前，大圖上的子圖搜索問題的主要方法主要分為構建索引和并行化[7-9]，如李瑞遠等[10]提出的SMID算法使用動態(tài)簽名樹索引；Sun Z等[11]采用分布式思想進行大圖上的子圖搜索。盡管目前已有的大規(guī)模數(shù)據(jù)圖上子圖搜索算法取得了一定的進展[12-13]，但均基于通用查詢圖模型進行搜索，對于現(xiàn)實生活中一些限定性的常見查詢問題的執(zhí)行效率并不高，甚至無法滿足查詢要求[14-15]。

例如，在進行區(qū)域搜索時，我們希望在城市（被建模為數(shù)據(jù)圖）中找到這樣一個區(qū)域（即結果子圖）：具有酒店、超市、車站和娛樂場所，其中娛樂場所具有滿足其一即可的多個可選項（如，游樂場或電影院）。根據(jù)經(jīng)驗，基礎設施即酒店、超市和車站的距離（被建模為邊的權重）越近，該區(qū)域越受歡迎。圖1展示了一個區(qū)域選擇圖模型，節(jié)點值的說明在表1中給出，其中游樂場D和電影院E為娛樂場所，其余為基礎設施。G表示地圖網(wǎng)絡，邊權表示兩個地點的鄰近度。Q給出用戶希望得到區(qū)域的結構，“*”代表娛樂場所中的任意一種，同時用戶希望酒店和車站的鄰近度不小于 0.2，基礎設施之間的總鄰近度不小于 0.5。G中以頂點{1,5,6,9,10}構成的子圖為滿足用戶要求的子圖，在圖1中以深色頂點標出。

圖1 區(qū)域選擇圖模型Fig.1 Diagram model of area selection

表1 節(jié)點值說明Tab.1 Node value description

針對上述問題，本文提出可變節(jié)點值搜索算法（Node Variable Search Algorithm, NVSA）用來解決具有可變節(jié)點值的查詢圖在大圖上的搜索問題，并通過構建雙索引結構：基于合并點的 CP-Index和Vin-Index來提高算法搜索時間效率。通過真實數(shù)據(jù)集上的實驗表明，本文提出的NVSA算法能更好的滿足用戶的特定查詢結果質量，與經(jīng)典子圖搜索算法相比，具有更高的求解效率。

1 問題描述與形式化

具有可變節(jié)點值的查詢圖搜索問題，本文給出如下相關定義：

定義 1 數(shù)據(jù)圖. 數(shù)據(jù)圖定義為 G = ＜VG, EG,LG, WG＞，其中 VG表示頂點集， EG表示邊集， LG表示頂點的節(jié)點標簽集合， WG表示數(shù)據(jù)圖中邊的權值。頂點與節(jié)點標簽具有唯一映射關系。

定義 2 查詢圖. 查詢圖定義為 Q = ＜VQ, EQ,LQ, WQ＞，其中，VQ表示查詢圖的頂點集合， EQ表示查詢圖的邊集合， LQ表示查詢圖的節(jié)點標簽集合（ LQ?LG），WQ表示查詢圖的邊權。

定義 3 可變節(jié)點值. 對于圖 M =＜VM, EM,LM, WM＞，其頂點分為兩類：固定節(jié)點值頂點 VF和可選節(jié)點值頂點 VN，即 VM= VF∪ VN，其中VF∩ VN=? 。 對 于 ? vi∈ VF，存 在 唯一 節(jié) 點 標 簽li∈ LM與之對應；對于 ? vj∈ VN，則存在節(jié)點值集合 { lj1,lj2,…}?LM與之對應。將具有上述頂點分類的圖稱為具有可變節(jié)點值的圖。

定義 4 可變節(jié)點值的查詢圖搜索. 數(shù)據(jù)圖頂點均為固定節(jié)點值，僅查詢圖具有可變節(jié)點值的問題稱為可變節(jié)點值的查詢圖搜索問題。即：給定數(shù)據(jù)圖 G = ＜ VG, EG, LG, WG＞，根據(jù)用戶輸入的查詢圖 Q = ＜VQ, EQ, LQ, WQ＞及閾值γF，尋找G中滿足以下條件的子圖G0的集合：

（1）存在唯一雙射函數(shù) f，使得:

均有ww′≥

以圖 1為例，數(shù)據(jù)圖 G規(guī)模為 17，查詢圖 Q規(guī)模為5，兩者均包含5種標簽，其中{A, B, C}為固定值，{D, E}為可選節(jié)點值。G中頂點與節(jié)點標簽存在唯一映射關系，Q 中“*”表示可選節(jié)點值頂點，該頂點標簽為D或為E均可滿足搜索條件， G中滿足Q搜索條件的子圖M如圖2所示。

圖2 滿足搜索條件的子圖Fig.2 Subgraphs with the search criteria

2 雙索引結構

目前大規(guī)模圖上的子圖搜索研究中，多數(shù)使用索引結構加快查詢[16-17]，在同等規(guī)模數(shù)據(jù)圖上，使用索引比無索引的算法在搜索速度上快 2—5個數(shù)量級[18]。本節(jié)將詳述CP-Index和VinCP-Index的構建，并在第3章介紹雙索引結構在算法中的使用。

2.1 CP 索引

本文提出的具有可變節(jié)點值的查詢圖搜索問題對固定節(jié)點值節(jié)點鄰近度有較高要求，因此通過合并相鄰同類節(jié)點以達到壓縮效果，并在此過程中構建 CP索引。索引以鍵值對的形式表示，其中鍵為合并點標號，值為合并點類別、合并點權值、內部點個數(shù)的有序列表。

以圖1中數(shù)據(jù)圖G為例，CP-Index對應的壓縮圖結構如圖3所示，相鄰兩點均為異類合并點。固定節(jié)點值合并點用V標識，可選節(jié)點值合并點用U標識，CP-Index對壓縮圖中的每個頂點構建一個索引。V1區(qū)域包含頂點集合{1,2,4,5,6}，U3區(qū)域包含集合{3}，V7區(qū)域包含集合{7,8}，U9區(qū)域包含集合{9,10,11}，V12區(qū)域包含集合{12,13,14}，V15區(qū)域包含集合{15,16,17}。在實現(xiàn)中可采用 hash結構或樹結構存儲加快查找速度。

圖3 數(shù)據(jù)圖壓縮結構Fig.3 Data graph compression structure

CP索引構建過程如下：

算法1 CP-Index構建算法

輸入：G、節(jié)點值分類

輸出：CP-Index

1. CP-Index ← null

2. 棧 S ← null

3. G中任取一個頂點入棧

4. While(S 非空)：

5. vi← 棧頂元素出棧

6. M ← null

7. vi放入 M

8. 對于vi所有未被訪問過的鄰接點ui:

9. 如果ui和vi不屬于同類點：

10. ui入棧

11. 否則

12. vi← ui并重復 7—12 行

13. 根據(jù)M 更新CP-Index

14. Return CP-Index

算法1前兩行為初始化，行2的棧S依次存儲搜索過程中當前頂點的異類節(jié)點值鄰接點。5—13行遍歷數(shù)據(jù)圖進行合并點操作并更新索引。其中行8判斷當前搜索頂點的鄰接點節(jié)點值。9—10行將異類鄰接點放入棧 S，后續(xù)循環(huán)出棧遍歷其同類鄰接點。11—12行遞歸搜索同類鄰接點。行 13更新索引操作包括：以M中頂點的最小編號標識合并點，確定合并點節(jié)點值類型，計算M內部邊權和，統(tǒng)計M頂點個數(shù)。

2.2 Vin索引

具有可變節(jié)點值的查詢圖搜索問題中固定節(jié)點值頂點鄰近度極大的影響搜索結果，因此Vin索引僅用來描述CP-Index中每個固定節(jié)點值合并點代表的子圖中不同頂點的異類鄰接點信息。索引的鍵用內部頂點編號表示，值存儲其所屬的合并點編號和異類鄰接點編號集合。圖 3中 V1區(qū)域為例，其Vin-Index結構如圖4所示。

圖4 V in-Index結構Fig.4 Th e structure of Vin-Index

Vin-Index實現(xiàn)為倒排索引，索引的鍵用v表示，一個v的索引項由2個有序列表組成，首列表存儲合并點編號，用V表示，次列表存儲異類鄰接點編號集合。子圖搜索過程中，成功匹配固定節(jié)點值合并點區(qū)域后使用該索引進行區(qū)域內頂點集合查詢，隨后對每個頂點的異類鄰接點集合遍歷進行可選節(jié)點值區(qū)域的子圖搜索，無異類鄰接點用0表示。

3 NVSA 算法

本文提出基于雙索引的NVSA算法求解大規(guī)模圖上具有可變節(jié)點值的子圖搜索問題。在進行子圖搜索之前，離線構建 CP-Index和 Vin-Index，兩者結構均與查詢圖無關，在頻繁的子圖搜索操作中僅構建一次。給定查詢圖進行子圖搜索操作時，搜索算法首先根據(jù)查詢圖 Q和用戶閾值 γF對 CP-Index進行剪枝操作，僅保留滿足條件的合并點。隨后，NVSA算法根據(jù)滿足條件的CP-Index對固定節(jié)點值頂點進行匹配，Vin-Index用來加快匹配成功的固定節(jié)點值頂點向可選節(jié)點值頂點的擴展搜索，最后再次利用CP-Index對可選節(jié)點值合并點內部進行子圖搜索。NVSA算法過程如下：

算法2 NVSA算法：

輸入：G，Q, CP-Index、VinCP-Index, 用戶閾值γF

輸出：匹配子圖集合M*，

1. M* ← 空

2. V-Index←Pruning(CP-Index，Q)

3. 選擇在 Q固定節(jié)點值子圖中出現(xiàn)次數(shù)最少的節(jié)點值L

4. 對于V-Index中的每個固定節(jié)點值的合并點表示的G中的子圖F：

5. 首次選取節(jié)點值為L的點vi

6. 對于每個vi：

7. MC← 空

8. Wc← 0

9. 如果|MC| ＜ |Q固定節(jié)點值頂點|：

10. 對于每個鄰接點ui:

11. 如果在Q中有與e(vi,ui)匹配的邊且未被匹配：

12. Wc←Wc+we

13. ui加入 MC;

14. vi←ui，重復 9—14 行

15. 否則

16. 如果 Wc＞ γF：

17. 對于每一個有可選節(jié)點值鄰接點的點vj:

18. While |MC| ＜ |Q|重復10—14行

19. 如果|MC| ==|Q|:

20. MC加入M*

21. Return M*

算法2描述了NVSA算法的大致流程。行1初始化輸出集合為空。行2根據(jù)查詢圖Q和用戶閾值γF對 CP-Index進行剪枝操作，即遍歷 CP-Index判斷索引中每個合并點的權值和內部點個數(shù)，將不滿足γF和Q的索引刪除。行3統(tǒng)計出現(xiàn)次數(shù)最少的節(jié)點值用來選取首次遍歷點，極大減少了候選集規(guī)模和遞歸次數(shù)。4—14行以 CP-Index中每個固定節(jié)點值合并點為起點進行內部子圖搜索。行15判斷合并點的內部規(guī)模是否達到查詢圖的相應區(qū)域規(guī)模。16—18行對完成匹配的固定節(jié)點值頂點擴展到可選節(jié)點值頂點區(qū)域進行匹配。19—20行將滿足具有可變節(jié)點值的子圖搜索條件的子圖放入集合 M*，行21返回結果。

4 實驗

實驗采用的硬件環(huán)境為：Intel（R）Core i5-2400（主頻 3.10 GHz），RAM 為 4 GB；編譯環(huán)境為MyEclipse, Java語言。實驗選用2個真實數(shù)據(jù)集：DBLP數(shù)據(jù)集和Friendster數(shù)據(jù)集。DBLP是計算機領域的文獻數(shù)據(jù)庫，包含70多萬點（作者）和700多萬條邊（作者間合作關系），頂點屬性表示作者研究領域；Friendster是斯坦福大學公開的在線游戲網(wǎng)站的數(shù)據(jù)集，包含6500萬個點和18億條邊。為證明AOSA算法穩(wěn)定性，本文在實驗前對2個數(shù)據(jù)集進行預處理：各選取70萬規(guī)模的頂點，頂點屬性集合均包含 5種固定屬性值標簽和 5中可選屬性值標簽。

本文將AOSA算法與經(jīng)典算法Spath和RWM進行索引構建效率和子圖搜索效率兩方面的對比分析，實驗過程中對經(jīng)過預處理的兩個數(shù)據(jù)集均進行等規(guī)模抽取數(shù)據(jù)以測試算法穩(wěn)定性。實驗結果與分析如下：

圖5 索引構建時間Fig.5 Index construction time

不同規(guī)模下三種算法的索引構建時間如圖5所示，其中Spath和RWM算法索引的跳數(shù)d設置為3。由圖可知，本文構建的兩個索引在構建效率上較兩個經(jīng)典算法有較大提高， Vin-Index比CP-Index構建效率稍低，因為Vin-Index在遍歷過程中，存在一個可選屬性值頂點同時連接多個固定屬性值頂點的情況，該可選屬性值點被存儲多次減慢了索引構建速度。

圖6展示了不同規(guī)模下三種算法的運行時間。Spath和RWM算法無法直接解決不定屬性子圖搜索問題，因此根據(jù)查詢圖列舉所有組合方式，并進行多次子圖搜索。由圖可知，AOSA算法在子圖搜索時間上比兩個經(jīng)典算法均更快，尤其在不定屬性標簽種類越多的情況下AOSA算法的優(yōu)勢越明顯。

圖6 算法時間Fig.6 Algorithm time

5 結束語

本文針對查詢圖中存在具有可變節(jié)點值的子圖搜索問題提出NVSA算法，并通過構建兩個索引：CP-Index和Vin-Index加快在大規(guī)模圖上的子圖搜索速度。CP-Index通過合并點方式進行構建，構建時間上較經(jīng)典算法有明顯優(yōu)勢。同時NVSA算法加入剪枝策略，在真實數(shù)據(jù)集上的實驗證明，NVSA算法在解決具有可變節(jié)點值的子圖搜索問題上具有高效性。后續(xù)希望通過分布式的方式，進一步提高大圖上具有可變節(jié)點值的子圖搜索問題的求解效率。

[1] 郭衍奎, 胡俊, 徐晨光, 等. 一種基于極大連通子圖的相關度屬性選擇算法[J]. 軟件, 2014, 35(5): 69-72.GUO Y K, et al. An Algorithm of Correlation Attribute Selection Based on Maximal Connected Subgraphs[J].computer engineering & Software, 2014, 35(5): 69-72.

[2] Ullmann J R. An Algorithm for Subgraph Isomorphism[J].Journal of the ACM, 1976, 23(1): 31-42.

[3] Cordella L P, Foggia P, Sansone C, et al. A Subgraph Isomorphism Algorithm for Matching Large Graphs[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2004,26(10); 1367-1372.

[4] Zhao P, Han J. On Graph Query Optimization in Large Networks[J]. PVLDB, 2010, 3(1): 340-351.

[5] He H, Singh A K. Query Language and Access Methods for Graph Databases[M]. Managing and Mining Graph Data,2010.

[6] Gupta M, Gao J, Yan X, et al. Top-K Interesting Subgraph Discovery in Information Networks[J]. ICDE 2014: 820-831.

[7] 郭騰. 基于Spark的子圖匹配算法研究與實現(xiàn)[D]. 北京交通大學, 2017.GUO T. Research and Implementation of Subgraph Matching Algorithm Based on Spark[D]. Beijing Jiaotong University,2017.

[8] 戴昕. 高效子圖匹配算法研究[D]. 北京交通大學, 2016.Dai X. Research on High Efficiency Subgraph Matching Algorithm[D]. Beijing Jiaotong University, 2016.

[9] 黃云, 洪佳明, 覃遵躍. 基于雙索引的近似子圖匹配[J].計算機應用, 2012, 32(07): 1994-1997.HUANG Y, HONG J M, QIN Z Y. Approximate Subgraph Matching Based on Double Indexing[J]. Journal of Computer Applications, 2012, 32(07): 1994-1997.

[10] 李瑞遠, 洪亮. 一種基于包含度的子圖匹配方法[J/OL].軟件學報, : 1-19(2017-03-31). http: //kns.cnki.net/kcms/detail/11.2560.TP.20170331.2154.004.html. DOI: 10. 13328/j.cnki.jos.005268..LI R Y, HONG L. A Subgraph Matching Method Based on Inclusion Degree[J/OL]. Journal of Software, : 1-19(2017-03-31). http: //kns.cnki.net/kcms/detail/11.2560.TP. 20170331.2154.004.html. DOI: 10.13328/j.cnki.jos.005268..

[11] Sun Z, Wang H, Shao B, et al. Efficient Subgraph Matching on Billion Node Graph[J]. PVLDB, 2012, 5(9): 788-799.

[12] 張海威, 解曉芳, 段媛媛等. 一種基于自適應結構概要的有向標簽圖子圖匹配查詢算法[J]. 計算機學報, 2017,40(01): 52-71.ZHANG H W, XIE X F, DUAN Y Y, et al. A Directed Label Graph Matching Query Algorithm Based on Adaptive Structure[J]. Chinese Journal of Computers, 2017, 40(01):52-71.

[13] 楊艷, 紀安娜, 金虎. 大規(guī)模數(shù)據(jù)圖上的個性化子圖匹配算法[J]. 計算機研究與發(fā)展, 2015, 52(S1): 48-55.YANG Y, JI A N, JIN H. Personalized subgraph matching algorithm on large scale data[J]. Journal of Computer Research and Development, 2015, 52(S1): 48-55.

[14] 吳金全. 有向圖的強連通分量及應用[J]. 軟件, 2014, 35(3):72-75.WU J Q. Strongly Connected Components and Applications of Directed Graphs[J]. computer engineering & Software,2014, 35(3): 72-75.

[15] 陳新泉. 基于超圖模型的關聯(lián)度計算[J]. 軟件, 2014, 35(5):62-68.CHEN X Q. Correlation Degree Calculation Based on Hypergraph Model[J]. computer engineering & Software, 2014,35(5): 62-68.

[16] 駱吉洲, 李建中. 一種索引結構的壓縮存儲及其查詢處理技術[J]. 計算機工程與應用, 2007(08): 149-153.

[17] 于戈, 谷峪, 鮑玉斌等. 云計算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術[J]. 計算機學報, 2011, 34(10): 1753-1767.YU G, GU Y, BAO Y B, et al. Large Scale Data Processing Technology in Cloud Computing Environment[J]. Chinese Journal of Computers, 2011, 34(10): 1753-1767.

[18] 于靜, 劉燕兵, 張宇等. 大規(guī)模圖數(shù)據(jù)匹配技術綜述[J].計算機研究與發(fā)展, 2015, 52(02): 391-409.YU J, LIU Y B, ZHANG Y, et al. Review of Large Scale Graph Data Matching Technology[J]. Journal of Computer Research and Development, 2015, 52(02): 391-409.