基于回溯模式总结的鲁棒近似子图查询算法

古险峰，程艳艳，杨立英

(1.郑州工业应用技术学院 信息工程学院，河南 郑州 451100； 2.吉林大学 应用技术学院，吉林 长春 130022)

0 引 言

图数据在网页链接结构、社会关系和金融交易等各种信息分析中发挥着重要作用。近似子图查询[1]是一种典型的图数据操作，即在数据图中对一个查询图的同构嵌入进行枚举。图数据库上的流行查询语言有SPARQL、Cypher等[2]。此外，在恶意软件检测[3]、复杂网络分析[4]等数据分析中，子图匹配也是必不可少的组件。由于子图匹配是NP困难问题，其较高计算成本限制了实用价值。

近似子图查询的研究主要针对两类问题而设定。

第一类问题是针对一个查询图枚举同构子图。如Antonino等[5]利用数据图和查询图生成树之间的近似同构，利用启发式算法过滤候选顶点。也有很多方法[6,7]通过图结构分析来缩小回溯法的搜索空间。但这类方法一般不能在搜索树中进行剪枝操作。Xu等[8]提出一种基于卡方统计的改进型近似子图匹配方法。但该方法不能有效处理具有相同局部结构且频繁出现的复杂图。

第二类问题是“一对多”：取一个查询图和很多个小数据图，找到包含该查询图的数据图。大部分研究着眼于如何总结数据图，对路径和频繁子图[9]进行捕捉。如Guan等[10]提出资源描述框架(resource description framework，RDF)的三元组模式，提高了面向RDF图的子图查询效率。Chen等[11]提出一种基于马尔科夫链蒙特卡罗框架的子图学习方法，该方法的优点是可以减少离散值的影响。

目前很多方法的性能取决于给定图的结构，在稳定性和精确度方面有待提高，因此，提出的子图查询算法没有在回溯之前进行结构分析，而是在回溯过程中执行剪枝。当部分嵌入导致搜索失败时，可以提取并记录下不能导向同构嵌入的模式，本文主要创新之处是：①利用回溯提供的信息降低了对图结构的敏感性，由此大幅减少搜索失败的数量；②仅对无用的部分嵌入进行剪枝，从而对所有的同构嵌入完成精确枚举。

1 问题定义

本文针对带顶点标签的非定向图G=(VG,EG,∑,l)。其中VG为顶点集合，EG⊆VG×VG为边集合，∑为标签集，l表示将一个顶点映射到其标签的函数。在子图查询中，G称为数据图。查询图Q=(VQ,EQ,∑,l)，其中，顶点编号为u1,u2,…,un。

(1)标签约束： ∀ui∈VQ，l(ui)=l(M[ui])；

(2)边约束： ∀(ui,u′i)∈EQ， (M[ui],M[u′i])∈EG；

(3)注入约束： ∀ui,u′i∈VQ，ui≠u′i⟹M[ui]≠M[u′i]。

定义2 子图匹配：给定查询图Q和数据图G，则子图匹配问题为枚举Q在G中的所有子图同构嵌入。

子图匹配要求对所有嵌入进行枚举，但这经常是无法实现的，因为嵌入数量可能会产生海量组合。因此在实践中，当发现的嵌入数量达到指定阈值时即会停止枚举[12]。本文使用的重要符号见表1。

2 提出的算法

2.1 基本框架思想

所提方法的核心思想是从回溯过程中出现的搜索失败模式中进行学习，以避免重复相同的失败，其基本框架如图1所示。当部分嵌入中包含的顶点映射违反了定义1中3个约束的任何一个约束时，会发生搜索失败。只要部分嵌入中包含一个会造成搜索失败的映射，那么无论其它映射如何改变，其都会导致搜索失败，基于这一点，所提方法会在每次遇到搜索失败时提取出违反约束的模式(即映射集合)。在后续搜索中对与提取出的模式相匹配的部分嵌入进行剪枝。因此，所提方法通过避免搜索失败提升了近似子图查询的性能。

表1 使用的符号及说明

2.2 死端模式剪枝

“死端”是指回溯搜索中永远得不到完整嵌入的路径。具体定义如下：

定义3 死端模式：设D为一个部分嵌入。若不存在能够满足D⊆M的完整嵌入M，则D是死端模式(或简单称为死端)。当且仅当D为死端时，判定Dead(D)为真。

(1)

图2给出了一个本文方法中的死端剪枝示例，在回溯过程的搜索树中，当部分嵌入导致搜索失败时，提取并记录下不能导向同构嵌入的顶点映射模式。在后续的搜索中，进行失败模式匹配，这样就可以显著减少搜索失败的数量。

2.3 死端模式管理

本文将死端模式记录在集合D中，并对与D中的死端模式相匹配的部分嵌入进行剪枝。但由于存在空间和时间限制，该机制并不能直接实施。从空间角度，死端模式的数量最多可增加至候选顶点(即 |C[u1]| |C[u2]|…|C[un]|) 所有可能的组合数，该大小可能会超出存储容量限制[14]。从时间角度，为进行剪枝操作，需要检查部分嵌入中是否包含D中的死端模式。若在D上执行线性搜索，并进行逐元素内容检验，则会产生不可接受的过大开销。为使本文的剪枝具有可行性，提出了以下两种对死端模式的管理方式。

2.3.1 固定散列表中的死端模式

2.3.2 数值表示的死端模式

(2)

(3)

Φ[μ]=∅

(4)

整个匹配检查可在O(1)时间内完成，因为访问Δ和比较嵌入ID的时间复杂度为O(1)，所以死端剪枝的开销较低。

2.4 子图匹配算法

输入：查询Q，数据图G；

输出：G中Q的所有嵌入；

(3)ifk=|VQ|then

(5)return∅

(6)C′←以边约束定义的候选

(7)if存在ui满足C′[ui]=∅then

(9)else

(10) Γ*←∅

(11)foreachv∈C′[uk1]do

(15) Γ*←Γ*∪Δ[uk+1,v]

(16)else

(18) Γ←Γ*

(21)returnΓ

(22)return∅

3 实验与分析

实验平台是Intel酷睿i3双核2.40 GHz，RAM为4.0 GB，操作系统是Ubauntn 12.04，编译环境是gcc/c++。对比两种不同算法，综合比较了精确度和查询效率，同时分析了不同顶点查询数目的影响。

3.1 数据集

实验采用两种不同的数据集：酵母细胞数据、数字书目索引和图书馆项目(digital bibliography & library project，DBLP)，其中，酵母细胞数据集[15](http://www.imcb.osaka-u.ac.jp/nakai/psort.html)中包含3112个顶点、12 519条边和71个顶点标签。DBLP[16](www.informatik.uni-trier.de/ley/db/)是参考文献数据集，包含数据库挖掘、信息检索等。作者用节点表示，标签表示研究方向，边表示作者间的关系。共有标签数3752，节点数797 787，边数1 301 298。

实验中，每种算法均处理一个包含10 000条查询的查询集。查询集在查询图中的顶点数量各有不同。若算法无法在12 h内完成查询集的处理，则考虑该处理是未能完成的任务(mission not finished，MNF)，在得到1000个嵌入后就停止枚举操作。

3.2 精确度比较

实验所用的度量是平均准确度(P)，召回率(R)，以及F1测度(F1)，F1测度是P与R的调和平均值，F1测度越高表示综合水平越高。对于查询图考虑两种情形，一种是无噪声的；另一种查询图是由目标图子集加一部分结构噪声构成。比较了文献[8]的卡方统计法和文献[5]提出的启发式算法，在酵母数据集和DBLP数据集上的评价结果见表2和表3。

表2 酵母数据集上的精确度结果/%

表3 DBLP数据集上的精确度结果/%

由表2和表3可知，无噪声和有结构噪声的两种情形，本文算法均表现出较高的平均准确度、召回率和F1测度，在酵母数据集上的平均F1测度达90.98%，在DBLP数据集上的平均F1测度达89.14%。此外，本文算法对有结构噪声的敏感性很弱，即，无噪声和有结构噪声的结果差异很小，说明鲁棒性较好。这主要是因为本文利用回溯提供的信息，降低了对图结构的敏感性。卡方统计法也具有相似特征，这是因为少量的结构噪声不能影响卡方值的计算。但启发式算法表现出更大的波动，这可能与启发式算法在搜索顶点解时，结构噪声影响了初始解，导致后续求解过程的偏差。

3.3 查询处理时间比较

本小节比较不同算法的处理时间，以评估死端剪枝的性能收益。其结果如图3所示。当酵母数据集上和DBLP数据集上的查询顶点数分别达到40个和14个时，所有算法均为MNF。总之，所提算法在几乎所有查询大小和数据集上均取得了较优性能，对于大型查询更是如此。例如，对于酵母数据集上的26～36个顶点的查询，卡方统计法[8]和启发式算法[5]处于MNF状态，而本文算法的每个查询时间较低，因此性能更好。这是因为卡方统计法和启发式算法的有效性很大程度上取决于给定图的结构。该问题在较大查询数中更加明显，这是因为较大查询包含更多的候选顶点组合数，卡方统计法和启发式算法需要搜索的组合数更多。与之相比，本文算法通过死端剪枝，避免了不必要的搜索。由此降低了对图结构的敏感性。这也验证了所提算法能够降低处理时间，且对大型查询同样有效。

3.4 顶点查询数的影响

为进一步分析所提算法的性能，实验分析了不同顶点查询数，算法中SEARCH函数的递归调用次数，比较本文算法与其它算法的(即不包含本文子图匹配算法的第(14)行和第(15)行)调用次数。最终的结果如图4所示，其中，酵母数据集上设置了20个以内的顶点查询，DBLP数据集上设置了9个以内的顶点查询。不同算法处理过程中的递归调用次数如图4所示，可以看出，对于较小查询，剪枝数量很少，但随着查询大小的增加，剪枝数量也会增加。例如，对于酵母数据集上的18个顶点的查询，启发式算法约递归6.6×1010次，卡方统计法的递归次数也有1.1×108次，而本文算法则仅递归约2.3×107次。这是因为较大的查询会涉及到更多的搜索失败。随着查询图中顶点和边的数量增加，单射性约束和边约束的违反次数也会增加。本文算法通过降低由这些原因引起的搜索失败，显著提高了性能。同时，本文算法对于较小查询也表现出较好性能。这是因为与死端模式的高效管理相比，死端剪枝的开销是非常小的。

4 结束语

子图匹配是一个NP困难问题，其计算成本非常高。为此，本文提出了一种子图匹配算法，在回溯过程中利用会导致搜索失败的部分嵌入来生成死端模式，并在回溯的后续过程中，对与死端模式相匹配的部分嵌入进行剪枝。实验结果表明，所提算法优于其它同类方法。未来，本文将探讨该算法是否可以推广到其它应用领域，比如生物蛋白网络的全局查询对比、RDF动态数据平台的图查询问题等。