Improving bipartite graph matching by assessing the assignment confidence

Due to the ability of graphs to represent properties of entities and binary relations at the same time, a growing interest in this representation formalism can be observed in various fields of pattern recognition. The availability of a distance measure is a basic requirement for pattern recognition. For graphs, graph edit distance is still one of the most popular distance measures. In the present paper we substantially improve the distance accuracy of a recent framework for the approximation of graph edit distance. The basic idea of our novel approach is to manipulate the initial assignment returned by the approximation algorithm such that the individual assignments are ordered according to their individual confidence. Next, the individual assignments are post processed in this specific order. In an experimental evaluation we show that the order of the assignments plays a crucial role for the resulting distance accuracy. Moreover, we empirically verify that our novel generalization is able to generate approximations which are very near to the exact edit distance (in contrast with the original framework).