Graph Distance Metric Combining Topological Subgraph and Graph Edit Distance
Tianlong Gu · Journal of Guilin University of Electronic Technology · 2009
Graph matching is the kernel of the graphstructured data searching.To find a good similarity measure is an important aspect in graph matching.There have two improved methods: graph edit distance measure and maximum common subgraph measure.Each of this two methods has its strengths and weaknesses.The graph edit distance method is strong in specific description but weak in structure description,whereas the maximum common subgraph method is strong in structure description and weak in specific description.In this paper,we propose a new similarity measure which combines the maximum common topological subgraph and the graph edit distance.In this new similarity measure,main structure of the graph is first measured according to the topological common subgraph.The graph specific similarity measure is then described in the main structure.This new similarity measure has the advantage of both maximal common subgraph measure and graph edit distance measure.Therefore,it is more efficient and precise for measuring the similarity of graphs.It can be more consistent and comprehensive in areas such as graph similarity searching,image retrieval and object recognition.