An HMM-based cost function free algorithm for graph edit distance

In this paper, we propose a cost function free algorithm to address the issue of computing graph edit distance (GED), in view of most GED algorithms rely heavily on cost functions which are difficult to be defined reasonably in a general method. This new method compares the difference of graph structures which are characterized by node distribution of graphs. Hidden Markov model (HMM) is employed to describe the distribution of nodes in each graph, and then the dissimilarity of graphs can be measured by the distance of these HMMs. As well known, Kullback-Leibler distance (KLD) is suitable for computing distance between two probability models and it is approximated by a fast algorithm to calculate the distance between HMMs efficiently. It can be demonstrated that the proposed GED algorithm can characterize the graph structure variety effectively. In addition, image classification and clustering based on this distance measurement are effective for both rigid and non-rigid objects.