基于分区过滤-增量验证的图编辑相似查询

Graph Edit Similarity Query Based on Partitioned Filtering-Incremental Verification

图编辑相似查询问题是指从图集G中查询出所有与查询图q的图编辑距离(Graph Edit Distance,GED)在给定阈值τ内的数据图.由于GED计算是NP-Hard问题,现有的研究多采用过滤-验证框架进行查询,对未能过滤掉的图采用A*-GED算法验证.本文提出了分区过滤-增量验证框架PFIV来处理图相似查询问题,在增强过滤效果的同时,还能加快验证速度.首先,在过滤阶段提出了2种分区策略,用来加快分区速度.(1)映射顶点顺序策略:在分区过程中,基于图的特征信息和结构信息提出分区时顶点的映射顺序,尽快过滤掉不相似的图,减少计算量;(2)分区结束条件策略:在分区过程中,设置分区结束条件,加快不相似图的过滤速度.其次,在验证阶段提出了增量验证策略,利用过滤阶段保留的映射结果,设计状态空间树,进行增量验证,加快验证阶段的计算.最后,通过大量实验验证了PFIV能够高效地处理图编辑相似查询问题,对比原有算法,查询效率提高8%~17%,并证明了所提出策略的有效性.

The Graph Edit Similarity Query problem refers to querying all data graphs from the graph set G that have Graph Edit Distance(GED)within a given thresholdτfrom the query graph q.Since GED computation is an NP-Hard problem,most existing studies use a filtering-verification framework for querying,and the A*-GED algorithm is used to verify the graphs that fail to be filtered out.In this paper,we propose the Partitioned Filtering-Incremental Verification(PFIV)framework to deal with the graph similarity query problem,which enhances the filtering effect and speeds up the verification speed.First,two partitioning strategies are proposed in the filtering stage to speed up the partitioning.(1)Mapping vertex order strategy:during the partitioning process,the mapping order of vertices during partitioning is proposed based on the feature information and structure information of the graph to filter out dissimilar graphs as soon as possible and reduce the computation;(2)Partitioning end condition strategy:during the partitioning process,the partitioning end condition is set to speed up the filtering of dissimilar graphs.Secondly,an incremental verification strategy is proposed in the validation stage,using the mapping results retained in the filtering stage to design the state space tree for incremental verification and speed up the computation in the validation stage.Finally,it is verified through a large number of experiments that PFIV can efficiently handle the graph edit similar query problem,and the query efficiency is improved by 8%~17%compared with the original algorithm,and the effectiveness of the proposed strategy is demonstrated.