Research On Graph Similarity Matching Algorithm

As a general data model,graphs can represent the relationships between various complex entities in the real world,and are widely used in many fields such as pattern recognition,image processing,and social networking.The essence of graph matching is to calculate the similarity of two graph structures.Existing methods usually use the filter validation mechanism to calculate the similarity of graph structures.In the filtering stage,the existing algorithm has poor quality of the partition structure;in the verification stage,the existing algorithm has the problem that the lower bound of the A* algorithm is not tightly estimated.We study the method of graph matching.First of all,in order to improve the quality of the structure of the filtering stage,we improve the method of partition quality by the method of probability estimation,and obtain a better partition structure by adjusting it.At the same time,after the partition filtering,the unmatched data map is excluded again by retrieving the unmatched partitions,and a candidates that may meet the edit distance constraint is obtained.Second,in the A*-based verification phase,whether the choice of the cost function is appropriate affects the efficiency of verification.For the problem that the lower bound estimation is not tight,a more compact lower bound estimation algorithm is given.This ensures that some partial mappings that do not meet the conditions during the verification process can be discovered as soon as possible and not necessarily kept until the end of the verification..At the same time,extending the matching partition gives the basic map of the verification and speeds up the verification process.Finally,based on the AIDS dataset experiments,the paper analyzes and compares the filtering effect,verification time,and scalability to verify the superiority of the proposed algorithm.