Research On The Solving Technology Of Graph Edit Distance

Graph is a powerful data model,which is widely available for real-world fields for instance,pattern recognition,natural language processing,and assembly sequence planning.The essence of graph matching is to calculate the similarity of two graph structures.Among many graph matching methods,the graph edit distance(GED)method is an efficient graph matching method,which measures the accuracy of matching by measuring the difference between two graphs.The graph edit distance is mainly divided into the precise graph edit distance and the approximate graph edit distance.The precise graph edit distance can calculate the optimal match between the two graphs,but the search space is too large,the time complexity is high,and it is greatly affected by noise.The edit distance of the approximate graph can be solved in polynomial time,but the accuracy is insufficient and the storage space is large,which causes the graph size to increase,and the solution cannot be effectively solved.Due to the lack of precision,the approximate graph edit distance algorithm is not suitable for applications with high matching accuracy requirements.For this reason,this article focuses on the exact graph edit distance algorithm.The specific content is as follows:(1)The DF?GED algorithm is an improved method of the A* algorithm.The upper bound is obtained through the BP algorithm,and the depth-first and upper and lower bound pruning strategies are adopted to accelerate the calculation of the graph editing distance.By analyzing the DF?GED algorithm,it is found that the upper bound algorithm has the problem of large storage space,and the time can still be improved.When the same upper bound is obtained,the FBP algorithm is faster than the BP algorithm,but the condition of using the FBP algorithm is that the cost value definition needs to meet the constraints.For this reason,a new upper bound algorithm is proposed based on the FBP algorithm.By introducing parameters to adjust the relationship between the cost values,the versatility of the FBP algorithm can be improved,and the new upper bound algorithm can reduce the calculation time and storage space.(2)Constraint Satisfaction Problem(CSP)is an important method to deal with large-scale solving problems in artificial intelligence.It is a technology that can effectively solve combinatorial search problems and provides an effective idea for solving graph matching problems.As an extended model of CSP,WCSP attaches a weight to each constraint on the basis of classic CSP.This weight is used as an evaluation criterion for judging the pros and cons of the solution to the problem,which can well portray the cost of editing and editing operations..To this end,a weighted constraint satisfaction(WCSP)model of graph edit distance is proposed.The vertex set of the source graph is used as a variable set,and the vertex set of the target graph is used as a value range.Null values ??are introduced to indicate insertion and deletion operations.Each variable assignment can be regarded as a vertex matching situation,and the specific editing can be described by establishing constraints.Operation,the editing cost generated in the matching process is used as the weighted value,and the GED is described as a WCSP model.(3)Combining the maximum constraint criterion and the depth-first branch and bound method,the WCSP?GED algorithm is proposed to solve the constraints of the weighted constraint satisfaction model of the graph edit distance.The branch and bound method can effectively reduce the search space,reorder the model variables through the maximum constraint criterion,and quickly update the boundary.The experimental results show that under the real data set,the solution scale and speed of this algorithm are better than A*GED algorithm and DF?GED algorithm.