关键词:
图编辑相似
映射
分区过滤
增量验证
摘要:
近些年来,图数据模型在化学、计算机视觉等领域的重要性越来越明显,许多问题都可以转换为图相似查询问题,比如新型药物研发、模式识别、软件漏洞识别等。图相似查询成为近些年研究热点之一,现有的图相似查询大多以图编辑距离(Graph Edit Distance,GED)作为相似衡量标准,称为图编辑相似查询。即给定查询图和图数据集,计算查询图与图数据集中每一个数据图之间的编辑距离,当图编辑距离小于给定阈值时,则认为查询图与数据图相似,最后返回所有判定为相似的数据图。由于图编辑距离的计算是NP-Hard问题,现有的研究多采用过滤-验证方法。在过滤阶段,计算图编辑距离下界,过滤掉部分一定不相似的数据图。对于未能在过滤阶段过滤掉的数据图,在验证阶段,计算查询图与数据图的编辑距离,判定是否相似。但是,现有的算法没有充分考虑到图的特征信息和结构信息,导致查询效率低下。并且,没有充分利用过滤阶段产生的结果,导致验证阶段和过滤阶段分离,仍需要耗费大量时间进行验证。本文针对图编辑相似查询问题进行了详细地分析和探究,提出分区过滤-增量验证算法(Partitioning Filter-Incremental Verification,PFIV),在增强过滤效果的同时加快验证速度。主要内容可以概括为如下几部分:(1)针对过滤阶段,本文提出分区过滤算法(Partitioning Filter,Par Fil)。基于分区的思想,将查询图划分为多个不重叠的分区,逐步计算过滤下界。同时提出桥标签集的概念,提高过滤下界,增强过滤效果。并且基于图的特征信息和结构信息,提出三种分区策略,用来加快过滤速度。(2)针对验证阶段,本文提出增量验证算法(Incremental Verification,Inc Ver)。对未能过滤掉的数据图,利用过滤阶段保留的部分映射结果,确定验证阶段映射顶点顺序和匹配顶点顺序,增量地建立查询图和数据图的状态空间树,更快判断出不相似的数据图。并且考虑桥标签集贡献的编辑错误,提高状态空间树中每个结点的状态编辑距离,加快验证速度。(3)设计对比实验,在三个真实数据集上,对比本文所提出的算法PFIV和目前先进的图编辑相似查询算法的查询时间,查询时间提升了8%~17%,证明了算法PFIV能够有效解决图编辑相似查询问题。