2017, Vol. 38
图集合是一个包含若干个图的集合.图集合相似性搜索指从一个由诸多图集合构成的数据集中查找出与给定查询图集合相似的所有图集合.图集合相似性搜索有重要的实际应用.例如:查询药效相似的药物.药物是一种由多种成分组成的混合物.每种成分由一种化学分子组成.一个化学分子可以表示为一个图.于是, 一种药物可以表示为一个图的集合.因此, 查找药效相似的药物, 也就是搜索相似的图集合.虽然图集合相似性搜索具有重要的实际意义, 但目前在图数据管理领域还没有得到充分的关注.现有图相似性搜索的相关研究主要分为两类:①从一个图数据集中找出所有与给定查询图相似的图[1-6];②从一个大图中找出所有满足条件的子结构[7-8].与图集合的相似性搜索问题不同, 图相似性搜索的查询对象是图而不是图集合, 计算过程中一般采用定义在图数据之间的编辑距离而不是图集合之间的距离.显然, 因为图集合是一种新的数据表示形式, 所以需要一种新的距离定义来表示两个图集合之间的相似性; 此外, 因为数据类型不同、相似性定义不同, 现有的相似性搜索算法[1-11]也不能直接用于解决图集合的相似性搜索问题.
1 图集合距离和问题定义定义1 (图集合) 图集合指一个无向有权简单连通图的集合, 表示为G={g1, g2, …, gn}.
定义2 (二分图最小完美匹配) 定义为满足如下条件的二分图的边集合的一个子集:①任意两条边不相交; ②覆盖了二分图的所有顶点; ③边的权重之和最小.二分图是一种满足如下条件的图, 它的顶点集V可以划分为两个子集X和Y, 它的每条边的两个端点只能分别属于X和Y集合, 不能同时属于X或者Y集合.
定义3 (图集合对的完全二分图表示) 已知两个图集合d1和d2, d1和d2可以构成这样一个完全二分图. d1和d2分别对应二分图的X和Y集合.d1或d2中的每个图对应X或Y中的一个顶点.该完全二分图任意一条边所连接的两个顶点所对应的图之间的编辑距离是该边的权重.该完全二分图称之为d1和d2的完全二分图, 记作CBG (d1, d2).如果d1和d2的基数不相等, 那么在基数较小的图集合中补充虚拟图, 使得两个图集合的基数相等.
定义4 (图集合距离) 图集合d1和d2的距离GSD (d1, d2) 是d1和d2的完全二分图的最小完美匹配.
定义5 (图集合相似性搜索) 已知图集合数据集D和查询图集合q, 图集合相似性搜索的目的是从D中找出所有与q的距离小于或等于一个给定阈值t的图集合R={d|GSD (q, d)≤t, d∈D}.
因为图的编辑距离计算是NP-Hard问题, 所以本文提出的图集合距离计算是很复杂的.为了提高查询效率, 本文提出的算法采用了过滤-求精框架.
2 过滤和求精 2.1 算法框架本文提出一个新的算法 (GSSS) 来解决图集合相似性搜索问题.该算法采用过滤-求精策略, 先对图集合数据集进行过滤, 消除一些一定不是最终结果的 (true negative) 数据, 得到一个包含了所有最终结果的候选结果集.因为该候选结果集中包含了一些非最终 (false positive) 结果, 所以计算候选结果集中每个图集合d与查询图集合q之间的图集合距离.如果该距离不超过给定阈值t, 则d属于结果集; 否则, d不属于结果集.
2.2 过滤为了减少搜索空间, 本文提出了Number filter, Size filter, Complete edge filter和Lower bound filter.下文依次介绍这些过滤器, 并证明它们的正确性.
已知两个图集合d1和d2, |d1|=n, |d2|=m, n≥m, d1和d2构成的完全二分图CBG (d1, d2) 和给定阈值t.
定理1 (Number filter) 如果d1和d2相似, 那么它们的基数之差的绝对值一定要小于或等于t, 即n-m≤t.
证明 根据已知条件和图集合距离定义可知, d1比d2多的n-m个图对它们的图集合距离的贡献至少为n-m, 也就是GSD (d1, d2)≥n-m.显然, 如果GSD (d1, d2)≤t, 则n-m≤t.
定理2 (Size filter) 如果d1和d2相似, 那么d1中的n-m个最小图的大小之和一定小于或等于t.
证明 根据已知条件、图集合距离定义和Number counting bound[1]可知, d1比d2多的n-m个图对它们的图集合距离的贡献的下界是d1中的n-m个最小图的大小之和.同理, 定理2成立.
本文将g∈d1(或d2) 在CBG (d1, d2) 中的最小边距离定义为g对应顶点的所有邻接边的最小的边权, 记作MED (g), 此外, d1和d2的完全边距离定义为d1中所有的图对应顶点的最小边距离之和.记作:CED (d1, d2)=∑(MED (g)), g∈d1.同理d2和d1的完全边距离CED (d2, d1)=∑(MED (g)), g∈d2.
定理3 (Complete edge filter) 如果d1和d2相似, 那么max{CED (d1, d2), CED (d2, d1)}≤t.
证明 根据已知条件、图集合距离定义和完全边距离定义, 不难推导出CED (d1, d2) 和CED (d2, d1) 是d1和d2的图集合距离的下界.因此, 如果d1和d2相似, 那么max{CED (d1, d2), CED (d2, d1)} ≤t.
引理1 假设CBG (d1, d2) 的最小完美匹配的匹配数为PM1.用CBG (d1, d2) 中每条边的权重下界取代真实边权重得到一个新的完全二分图CBG′(d1, d2), 假设CBG′(d1, d2) 最小完美匹配的匹配数为PM2, 则PM2≤PM1.
证明 下面分两种情况进行证明.①假设替换后, 最小完美匹配不变.由于匹配中每条边的权重不变或者变小了, 所以PM2≤PM1.②假设替换后, 最小完美匹配发生改变.换言之, PM2 < PM1.综上所述, PM2≤PM1.
GSSS算法采用如下图编辑距离下界的最大值作为图集合对构成二分图的边的权重下界:Number counting bound[1], Label multiset bound[3]和Compact branch bound[6].
定理4 (Lower bound filter):如果d1和d2相似, 那么PM2≤t.
证明 由引理1, 可知PM2≤PM1.如果d1和d2相似, 那么PM1≤t.因此, PM2≤t.
根据计算代价小优先使用的原则, 按如下次序使用过滤器:Number filter, Size filter, Complete edge filter和Lower bound filter.
2.3 求精求精阶段使用的剪枝策略的基本思想是:在求解完全二分图的最小完美匹配过程中, 如果可以判断最小完美匹配的上界小于或等于给定的阈值, 就提前终止计算, 判定对应的两个图集合一定相似.
目前计算二分图最小完美匹配的最优算法是扩展的KM算法.KM算法是求解二分图的最大完美匹配问题的算法, 进行如下扩展可用于求解二分图最小完美匹配问题:先将边的权重取负数, 接着使用KM算法计算出最大完美匹配, 最后取该最大完美匹配的匹配数的负数, 即所求的最小完美匹配的匹配数.KM算法的流程如下:
1) 设置二分图的顶点标记, 使得如下结论始终成立:边权重始终小于或等于两个邻接点的标记之和.
2) 使用匈牙利算法查找同等子图中的完美匹配.如果找到, 则找到的完美匹配为所求; 否则, 修改顶点标记, 扩展同等子图.
3) 循环1) 和2), 直至找到完美匹配为止.
定理5 已知两个图集合d1和d2, 以及给定的阈值t.在查找同等子图的完美匹配的过程中, 如果当前匹配的边权之和CMS (d1, d2) 大于或等于-t, 那么GSD (d1, d2)≤t.
证明 根据扩展的KM算法, GSD (d1, d2)≤t, 也就是对应的最大完美匹配的匹配数MAXPM≥-t.因此, 证明定理5成立, 即证明如下结论成立:如果CMS (d1, d2) ≥-t, 那么MAXPM≥-t.下面分2种情况讨论:①假设当前匹配是完美匹配, 那么MAXPM=CMS (d1, d2)=-t.②假设当前匹配不是完美匹配, 那么完美匹配将在后继步骤中找到.根据匈牙利算法可知, 后继匹配的边权之和大于当前匹配的边权之和.因此, MAXPM > CMS (d1, d2).根据假设可知, CMS (d1, d2)≥-t.显然, MAXPM > -t.综上所述, 定理5成立.定理5不仅可以帮助GSSS算法在求精阶段快速地找到最终结果, 还可以加快Lower bound filter的计算.
2.4 索引最基本的查询策略是将查询图集合与每个数据图集合依次进行过滤和求精, 从而得到最终查询结果.这种策略的查询效率很低.当数据图集合数量非常多的时候, 低效问题尤为突出.为了提高查询效率, 设计了一个多层倒排索引.下文先介绍与多层倒排索引相关的基本概念, 然后分别讨论该索引的组织结构、存储优化、构造方法、动态维护和查询方法.
本文将图信息单元定义为一个三元组GIU (g)= < graphId, size, branches >.其中, graphId指g的唯一标识, size指g的顶点数和边数之和, branches指g的所有branch结构.一个branch由g中的一个顶点v和v的邻接边组成[6].此外, 一个图集合d的信息单元由该集合的唯一标识和d中所有的图的信息单元组成, 记作GSIU (d).多层倒排索引的键是图集合的基数|d|, 列表中包括的是所有基数为|d|的图集合的信息单元, 如图 1所示.
|
图 1 多层倒排索引示意图 Fig.1 Illustration diagram of multi-layer inverted index |
进一步, 为了减少索引的存储空间, 本文采用了将图的信息单元单独存储的策略.因为不同的图集合可以包含相同的图, 所以不同图集合的信息单元可能包含相同的图信息单元.因此, 构造一个哈希表来专门存储所有图的信息单元.这样就避免索引中多次存储相同的图信息单元, 从而优化了存储空间.为了提高查询效率, 离线建立索引.该索引的构造方法与倒排索引的构造方法相类似.限于篇幅, 不对其构造方法进行详细的介绍.
多层倒排索引可以通过增量式的维护来适应数据集合的动态变化, 从而避免了索引的重新建立.当增加了一个新的数据集合d1, 如果d1中图的信息单元在哈希表中不存在, 则添加进哈希表, 并在倒排索引中添加d1的集合信息单元.当删除一个数据集合d2, 则只需要删除多层倒排索引中d2的集合信息单元即可.类似地, 当数据集合d1中增加 (或减少) 了图g, 则相应地更新d1对应的集合信息单元和哈希表.
GSSS的查询算法如算法1所示.给定一个查询图集合q和一个距离阈值t, 先根据Number filter计算出与q相似的数据图集合d的基数的范围.然后, 与多层倒排索引中的键相匹配, 找到Number filter过滤后的候选结果集1.接着, 对候选结果集1中的每个图集合, 依次使用Size filter, Complete edge filter和Lower bound filter得到候选结果集2.最后, 采用优化过的KM算法验证候选结果集2, 返回最终的查询结果.GSSS算法流程描述如图 2所示.
|
图 2 GSSS算法流程示意图 Fig.2 Flow diagram of GSSS algorithm |
算法1:GSSS查询算法
输入:图集合数据集D, 查询图集合q和距离阈值t.
输出:R={d|GSD (q, d)≤t, d∈D}.
1) 建立D的多层倒排索引;
2) 根据Number filter, q和t, 查询第一步建立的多层倒排索引, 得到候选结果集1;
3) 依次使用Size filter, Complete edge filter和Lower bound filter对候选结果集1进行过滤, 得到候选结果集2;
4) 使用优化的KM算法验证候选结果集2, 返回最终的查询结果.
3 性能评价在真实数据集上比较GSSS, Naive算法和扩展的M算法[6]的在线查询时间, 并研究GSSS算法的索引构造时间和空间.每组进行了3次实验, 取均值作为实验结果.下面分别报告使用的真实数据集、实验配置和实验结果.
NCI化合物数据集:一个分子化合物可以表示成一个图.原子表示为图的顶点, 化学键表示为图的边.ID为1的NCI化合物数据集共包含42490个分子化合物.使用文献[12]实验提出的方法构造了50000个分子组.
本文所有实验均在单台计算机上执行.计算机配置如下所示:Linux操作系统, 2.93GHz CPU, 4GB RAM.
3.1 离线索引构造时间和空间本节测试了多层倒排索引的构造时间和空间.试验结果如图 3和图 4所示.图 3和图 4分别显示:随着数据图集合的增大, 多层倒排索引的构造时间和空间呈线性增长.
|
图 3 多层倒排索引构造时间 Fig.3 Building time of multi-layer inverted index |
|
图 4 多层倒排索引空间 Fig.4 Size of multi-layer inverted index |
本节比较了GSSS算法、Naive算法和扩展的M算法 (M*) 的在线查询时间.结果如表 1所示 (|D|=30K).N, S, C和L分别表示采用Number filer, Size filter, Complete edge filter和Lower bound filter的GSSS算法. N+S+C+L表示采用所有过滤器的GSSS算法.Naive算法、M*算法、N和N+S均未在8h之内完成.当距离阈值等于5, N+S+C+L至少比Naive算法和M*算法快150倍; 当距离阈值等于20, N+S+C+L至少比Naive算法和M*算法快4倍.显然, GSSS算法比Naive算法和M*算法要快.因为GSSS算法采用了多个过滤器, 并且采用了优化的KM算法.同时, GSSS算法采用的过滤器越多, 在线查询时间越少.因为过滤器越多, 过滤掉的非最终结果越多.
|
表 1 采用不同过滤器的在线查询时间 Table 1 Online response time by using different filters |
不同距离阈值对GSSS算法过滤性能的影响 (|D|=30K), 如图 5所示.随着距离阈值的增大, 各组合过滤器的过滤效果变弱.因为随着距离阈值的增大, Number filter, Size filter, Complete edge filter和Lower bound filter的过滤效果均变弱.根据定理1, 被Number filter过滤掉的图集合在距离阈值增大的情况下可能通过Number filter.因此, 随着距离阈值的增大, Number filter的过滤效果变弱.同理, 随着距离阈值的增大, Size filter, Complete edge filter和Lower bound filter的过滤效果也变弱.同时, 对于同一个阈值, 采用更多过滤器的GSSS算法的过滤效果更好.因为对于同一个阈值, 这些过滤器的过滤效果呈递增趋势.
|
图 5 不同阈值的过滤效果 Fig.5 Filtering effect of different distance thresholds |
本文采用一种新的数据类型 (图集合) 来表示对象, 给出一种图集合间的距离定义, 并提出了一个基于过滤-求精策略的GSSS算法来解决图集合相似性搜索问题; 为了提高搜索效率, 提出了一个增量式的多层倒排索引和多个下界剪枝策略, 并优化了KM算法.实际数据集上的大量实验证明了该算法的有效性和高效性.
| [1] | Zheng Z, Tung A K H, Wang J, et al.Comparing stars:on approximating graph edit distance[C]//Proceedings of the VLDB Endowment.Lyon, 2009:25-36. |
| [2] | Wang G R, Wang B, Yang X C, et al. Efficiently indexing large sparse graphs for similarity search[J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(3): 440–451. DOI:10.1109/TKDE.2010.28 |
| [3] | Zhao X, Xiao C, Lin X M, et al.Efficient graph similarity joins with edit distance constraints[C]//Proceedings of the 28th International Conference on Data Engineering.Washington D C, 2012:210-221. |
| [4] | Zhao X, Xiao C, Lin X M, et al.A partition-based approach to structure similarity search[C]//Proceedings of the VLDB Endowment.Hangzhou, 2013, 7(3):169-180. |
| [5] | Pang J, Gu Y, Xu J, et al.Efficient graph similarity join with scalable prefix-filtering using MapReduce[C]//Proceedings of the 15th International Conference on Web-Age Information Management.Macau, 2014:415-418. |
| [6] | Zheng W G, Zou L, Lian X, et al. Efficient graph similarity search over large graph databases[J]. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(4): 964–978. DOI:10.1109/TKDE.2014.2349924 |
| [7] | Li R H, Qin L, Yu X J, et al.Influential community search in large networks[C]// Proceedings of the VLDB Endowment.Hawaii, 2015, 8(5):509-520. |
| [8] | Huang X, Cheng H, Li R H, et al. Top-k structural diversity search in large networks[J]. International Journal on Very Large Data Bases, 2015, 24(3): 319–343. DOI:10.1007/s00778-015-0379-0 |
| [9] | Xu J, Zhang Z J, Anthony K H, et al.Efficient and effective similarity search over probabilistic data based on earth mover's distance[C]//Proceedings of the VLDB Endowment.Singapore, 2010, 3(1):758-769. |
| [10] | Li G L, Deng D, Feng J H. A partition-based method for string similarity joins with edit-distance constraints[J]. ACM Transactions on Database Systems, 2013, 38(2): 721–741. |
| [11] | Yang X C, Wang Y S, Wang B, et al.Local filtering:improving the performance of approximate queries on string collections[C] //Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data.Melbourne, 2015:377-392. |
| [12] | Wu J, Zhu X Q, Zhang C Q, et al. Bag constrained structure pattern mining for multi-graph classification[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(10): 2382–2396. DOI:10.1109/TKDE.2013.2297923 |