基于图连通支配集的子图匹配优化算法

孙云浩 韩 冰 李冠宇 邢维康 李逢雨(大连海事大学信息科学技术学院 辽宁 大连 116026)

0 引 言

模式匹配是一个子图同构问题，给定一个查询图和数据图，模式匹配是指搜索到所有同构于查询图的数据子图[1]。基于节点的子图匹配方法是解决模式匹配问题的一种有效方法，其以节点作为最小匹配单位，利用了SSR(State Space Representation)树模型构建模式匹配的执行过程[2]。其中，状态表示一个由查询图节点和数据图节点组成的节点对。如果查询图节点和数据图节点满足匹配条件(查询图节点出度小于数据图节点出度，查询图节点入度小于数据图节点入度，查询图节点标签与数据图标签相同等)，则将其加入SSR树模型。当匹配成功的节点数量等价于查询图节点数量，则输出一个子图匹配的答案集。

基于节点的子图匹配算法主要通过优化节点匹配可行性规则、匹配的执行序列和搜索空间三方面提高算法的执行时间效率。最早的算法思想是由Ullmann[4]提出，其主要通过比对查询图节点和数据图节点的度的大小来过滤数据图节点。然而，这种过滤手段是粗糙的，其过滤后的候选数据图节点过于庞大。VF2算法[5-6]在缩减候选数据图节点方面贡献突出，其通过添加邻接节点的可行性规则来缩减候选数据图节点的规模。然而，其匹配的执行序列是随机的，忽略了执行序列对时间效率的影响，导致处理大规模数据时，查询时间过高。文献[5]提出了GADDI算法，定义了邻近辨别子结构距离(NDS)，表示两个节点及相邻节点结构中频繁子图的数量，通过约束模式图中节点的NDS距离来过滤备选节点。……