Research On Optimizations For Graph Edit Distance

Graph similarity search is one of the most important graph operations.Graph edit distance(GED)is a fundanmental method to measure the similarity between graphs.Given a query graph and a target graph,graph edit distance is the minimum length of an edit path between them.Graph edit distance computation is an NP-Hard problem,therefore it requires huge time and space consumption.Existing methods suffers from several drawbacks,for example,redundant computation.These drawbacks lead to low efficiency in GED computation.To address the above drawbacks,this paper proposes efficient graph edit distance techniques.Firstly,the computation of extending vertex mappings is improved.The information of vertex mappings with the same level is computed in advance of the A* search procedure to avoid redundant computation,which reduces time comsumption.Secondly,several techniques are adopted to accelerate the search of the vertex mapping.A novel symmetry-breaking technique is proposed to prune equivalent redundant vertex mappings,which reduces both time and space consumption.An upperbound-based technique is prorposed which prunes vertex mappings with edit cost lowerbounds larger than the upperbound computed in advance of the search procedure to avoid unnecessary space consumption.A novel heuristic which extends deeper vertex mappings with the same edit cost lowerbound is proposed to improve the search performance of the A* algorithm,which reduces both time and space comsuption.Finally,the experiments based on 2 real graph datasets are carried out.According to the computation time and numbers of all mappings,the efficiency of the proposed methods is verified.The experiment results show that the proposed techniques improve both time and space performance.