NVSA：一种具有可变节点值的查询图搜索算法

胡一然，宋中山，孙 翀，郑 禄

（中南民族大学 计算机科学学院，湖北 武汉 430070）

0 引言

图模型作为一种重要的数据结构，在现实世界中被广泛应用于如社交网络、城市道路网络、生物网络等众多领域。子图搜索是在数据图中找到与查询图同构且满足用户设定条件的子图集合[1]。1976年，首个子图搜索算法被 Ullmann[2]提出；随后，VF2、Spath、GraphQL、RWM等经典算法通过索引和优化策略提高搜索效率[3-6]。

然而，上述大多数算法仅用于无权图的搜索，且对于大规模数据图的搜索效率并不理想。目前，大图上的子图搜索问题的主要方法主要分为构建索引和并行化[7-9]，如李瑞远等[10]提出的SMID算法使用动态签名树索引；Sun Z等[11]采用分布式思想进行大图上的子图搜索。尽管目前已有的大规模数据图上子图搜索算法取得了一定的进展[12-13]，但均基于通用查询图模型进行搜索，对于现实生活中一些限定性的常见查询问题的执行效率并不高，甚至无法满足查询要求[14-15]。

例如，在进行区域搜索时，我们希望在城市（被建模为数据图）中找到这样一个区域（即结果子图）：具有酒店、超市、车站和娱乐场所，其中娱乐场所具有满足其一即可的多个可选项（如，游乐场或电影院）。根据经验，基础设施即酒店、超市和车站的距离（被建模为边的权重）越近，该区域越受欢迎。图1展示了一个区域选择图模型，节点值的说明在表1中给出，其中游乐场D和电影院E为娱乐场所，其余为基础设施。G表示地图网络，边权表示两个地点的邻近度。Q给出用户希望得到区域的结构，“*”代表娱乐场所中的任意一种，同时用户希望酒店和车站的邻近度不小于 0.2，基础设施之间的总邻近度不小于 0.5。G中以顶点{1,5,6,9,10}构成的子图为满足用户要求的子图，在图1中以深色顶点标出。

图1 区域选择图模型Fig.1 Diagram model of area selection

表1 节点值说明Tab.1 Node value description

针对上述问题，本文提出可变节点值搜索算法（Node Variable Search Algorithm, NVSA）用来解决具有可变节点值的查询图在大图上的搜索问题，并通过构建双索引结构：基于合并点的 CP-Index和Vin-Index来提高算法搜索时间效率。通过真实数据集上的实验表明，本文提出的NVSA算法能更好的满足用户的特定查询结果质量，与经典子图搜索算法相比，具有更高的求解效率。

1 问题描述与形式化

具有可变节点值的查询图搜索问题，本文给出如下相关定义：

定义 1 数据图. 数据图定义为 G = ＜VG, EG,LG, WG＞，其中 VG表示顶点集， EG表示边集， LG表示顶点的节点标签集合， WG表示数据图中边的权值。顶点与节点标签具有唯一映射关系。

定义 2 查询图. 查询图定义为 Q = ＜VQ, EQ,LQ, WQ＞，其中，VQ表示查询图的顶点集合， EQ表示查询图的边集合， LQ表示查询图的节点标签集合（ LQ⊆LG），WQ表示查询图的边权。

定义 3 可变节点值. 对于图 M =＜VM, EM,LM, WM＞，其顶点分为两类：固定节点值顶点 VF和可选节点值顶点 VN，即 VM= VF∪ VN，其中VF∩ VN=Ø 。 对 于 ∀ vi∈ VF，存 在 唯一 节 点 标 签li∈ LM与之对应；对于 ∀ vj∈ VN，则存在节点值集合 { lj1,lj2,…}⊆LM与之对应。将具有上述顶点分类的图称为具有可变节点值的图。

定义 4 可变节点值的查询图搜索. 数据图顶点均为固定节点值，仅查询图具有可变节点值的问题称为可变节点值的查询图搜索问题。即：给定数据图 G = ＜ VG, EG, LG, WG＞，根据用户输入的查询图 Q = ＜VQ, EQ, LQ, WQ＞及阈值γF，寻找G中满足以下条件的子图G0的集合：

（1）存在唯一双射函数 f，使得:

均有ww′≥

以图 1为例，数据图 G规模为 17，查询图 Q规模为5，两者均包含5种标签，其中{A, B, C}为固定值，{D, E}为可选节点值。G中顶点与节点标签存在唯一映射关系，Q 中“*”表示可选节点值顶点，该顶点标签为D或为E均可满足搜索条件， G中满足Q搜索条件的子图M如图2所示。

图2 满足搜索条件的子图Fig.2 Subgraphs with the search criteria

2 双索引结构

目前大规模图上的子图搜索研究中，多数使用索引结构加快查询[16-17]，在同等规模数据图上，使用索引比无索引的算法在搜索速度上快 2—5个数量级[18]。本节将详述CP-Index和VinCP-Index的构建，并在第3章介绍双索引结构在算法中的使用。

2.1 CP 索引

本文提出的具有可变节点值的查询图搜索问题对固定节点值节点邻近度有较高要求，因此通过合并相邻同类节点以达到压缩效果，并在此过程中构建 CP索引。索引以键值对的形式表示，其中键为合并点标号，值为合并点类别、合并点权值、内部点个数的有序列表。

以图1中数据图G为例，CP-Index对应的压缩图结构如图3所示，相邻两点均为异类合并点。固定节点值合并点用V标识，可选节点值合并点用U标识，CP-Index对压缩图中的每个顶点构建一个索引。V1区域包含顶点集合{1,2,4,5,6}，U3区域包含集合{3}，V7区域包含集合{7,8}，U9区域包含集合{9,10,11}，V12区域包含集合{12,13,14}，V15区域包含集合{15,16,17}。在实现中可采用 hash结构或树结构存储加快查找速度。

图3 数据图压缩结构Fig.3 Data graph compression structure

CP索引构建过程如下：

算法1 CP-Index构建算法

输入：G、节点值分类

输出：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. 根据M 更新CP-Index

14. Return CP-Index

算法1前两行为初始化，行2的栈S依次存储搜索过程中当前顶点的异类节点值邻接点。5—13行遍历数据图进行合并点操作并更新索引。其中行8判断当前搜索顶点的邻接点节点值。9—10行将异类邻接点放入栈 S，后续循环出栈遍历其同类邻接点。11—12行递归搜索同类邻接点。行 13更新索引操作包括：以M中顶点的最小编号标识合并点，确定合并点节点值类型，计算M内部边权和，统计M顶点个数。

2.2 Vin索引

具有可变节点值的查询图搜索问题中固定节点值顶点邻近度极大的影响搜索结果，因此Vin索引仅用来描述CP-Index中每个固定节点值合并点代表的子图中不同顶点的异类邻接点信息。索引的键用内部顶点编号表示，值存储其所属的合并点编号和异类邻接点编号集合。图 3中 V1区域为例，其Vin-Index结构如图4所示。

图4 V in-Index结构Fig.4 Th e structure of Vin-Index

Vin-Index实现为倒排索引，索引的键用v表示，一个v的索引项由2个有序列表组成，首列表存储合并点编号，用V表示，次列表存储异类邻接点编号集合。子图搜索过程中，成功匹配固定节点值合并点区域后使用该索引进行区域内顶点集合查询，随后对每个顶点的异类邻接点集合遍历进行可选节点值区域的子图搜索，无异类邻接点用0表示。

3 NVSA 算法

本文提出基于双索引的NVSA算法求解大规模图上具有可变节点值的子图搜索问题。在进行子图搜索之前，离线构建 CP-Index和 Vin-Index，两者结构均与查询图无关，在频繁的子图搜索操作中仅构建一次。给定查询图进行子图搜索操作时，搜索算法首先根据查询图 Q和用户阈值 γF对 CP-Index进行剪枝操作，仅保留满足条件的合并点。随后，NVSA算法根据满足条件的CP-Index对固定节点值顶点进行匹配，Vin-Index用来加快匹配成功的固定节点值顶点向可选节点值顶点的扩展搜索，最后再次利用CP-Index对可选节点值合并点内部进行子图搜索。NVSA算法过程如下：

算法2 NVSA算法：

输入：G，Q, CP-Index、VinCP-Index, 用户阈值γF

输出：匹配子图集合M*，

1. M* ← 空

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

3. 选择在 Q固定节点值子图中出现次数最少的节点值L

4. 对于V-Index中的每个固定节点值的合并点表示的G中的子图F：

5. 首次选取节点值为L的点vi

6. 对于每个vi：

7. MC← 空

8. Wc← 0

9. 如果|MC| ＜ |Q固定节点值顶点|：

10. 对于每个邻接点ui:

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

12. Wc←Wc+we

13. ui加入 MC;

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

15. 否则

16. 如果 Wc＞ γF：

17. 对于每一个有可选节点值邻接点的点vj:

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

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

20. MC加入M*

21. Return M*

算法2描述了NVSA算法的大致流程。行1初始化输出集合为空。行2根据查询图Q和用户阈值γF对 CP-Index进行剪枝操作，即遍历 CP-Index判断索引中每个合并点的权值和内部点个数，将不满足γF和Q的索引删除。行3统计出现次数最少的节点值用来选取首次遍历点，极大减少了候选集规模和递归次数。4—14行以 CP-Index中每个固定节点值合并点为起点进行内部子图搜索。行15判断合并点的内部规模是否达到查询图的相应区域规模。16—18行对完成匹配的固定节点值顶点扩展到可选节点值顶点区域进行匹配。19—20行将满足具有可变节点值的子图搜索条件的子图放入集合 M*，行21返回结果。

4 实验

实验采用的硬件环境为：Intel（R）Core i5-2400（主频 3.10 GHz），RAM 为 4 GB；编译环境为MyEclipse, Java语言。实验选用2个真实数据集：DBLP数据集和Friendster数据集。DBLP是计算机领域的文献数据库，包含70多万点（作者）和700多万条边（作者间合作关系），顶点属性表示作者研究领域；Friendster是斯坦福大学公开的在线游戏网站的数据集，包含6500万个点和18亿条边。为证明AOSA算法稳定性，本文在实验前对2个数据集进行预处理：各选取70万规模的顶点，顶点属性集合均包含 5种固定属性值标签和 5中可选属性值标签。

本文将AOSA算法与经典算法Spath和RWM进行索引构建效率和子图搜索效率两方面的对比分析，实验过程中对经过预处理的两个数据集均进行等规模抽取数据以测试算法稳定性。实验结果与分析如下：

图5 索引构建时间Fig.5 Index construction time

不同规模下三种算法的索引构建时间如图5所示，其中Spath和RWM算法索引的跳数d设置为3。由图可知，本文构建的两个索引在构建效率上较两个经典算法有较大提高， Vin-Index比CP-Index构建效率稍低，因为Vin-Index在遍历过程中，存在一个可选属性值顶点同时连接多个固定属性值顶点的情况，该可选属性值点被存储多次减慢了索引构建速度。

图6展示了不同规模下三种算法的运行时间。Spath和RWM算法无法直接解决不定属性子图搜索问题，因此根据查询图列举所有组合方式，并进行多次子图搜索。由图可知，AOSA算法在子图搜索时间上比两个经典算法均更快，尤其在不定属性标签种类越多的情况下AOSA算法的优势越明显。

图6 算法时间Fig.6 Algorithm time

5 结束语

本文针对查询图中存在具有可变节点值的子图搜索问题提出NVSA算法，并通过构建两个索引：CP-Index和Vin-Index加快在大规模图上的子图搜索速度。CP-Index通过合并点方式进行构建，构建时间上较经典算法有明显优势。同时NVSA算法加入剪枝策略，在真实数据集上的实验证明，NVSA算法在解决具有可变节点值的子图搜索问题上具有高效性。后续希望通过分布式的方式，进一步提高大图上具有可变节点值的子图搜索问题的求解效率。

[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的子图匹配算法研究与实现[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] 杨艳, 纪安娜, 金虎. 大规模数据图上的个性化子图匹配算法[J]. 计算机研究与发展, 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] 陈新泉. 基于超图模型的关联度计算[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] 于戈, 谷峪, 鲍玉斌等. 云计算环境下的大规模图数据处理技术[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] 于静, 刘燕兵, 张宇等. 大规模图数据匹配技术综述[J].计算机研究与发展, 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.