Approximation of graph edit distance based on Hausdorff matching

• Quadratic time approximation of graph edit distance based on Hausdorff matching.
• Error-tolerant graph matching method without constraints on node and edge labels.
• Experimental evaluation for classification of graphs representing letter drawings, fingerprints, and molecules.
• Experimental evaluation for hidden Markov model recognition of vector space embedded graphs representing handwriting.
• Promising potential in terms of flexibility, efficiency, and accuracy.

Graph edit distance is a powerful and flexible method for error-tolerant graph matching. Yet it can only be calculated for small graphs in practice due to its exponential time complexity when considering unconstrained graphs. In this paper we propose a quadratic time approximation of graph edit distance based on Hausdorff matching. In a series of experiments we analyze the performance of the proposed Hausdorff edit distance in the context of graph classification and compare it with a cubic time algorithm based on the assignment problem. Investigated applications include nearest neighbor classification of graphs representing letter drawings, fingerprints, and molecular compounds as well as hidden Markov model classification of vector space embedded graphs representing handwriting. In many cases, a substantial speedup is achieved with only a minor loss in accuracy or, in one case, even with a gain in accuracy. Overall, the proposed Hausdorff edit distance shows a promising potential in terms of flexibility, efficiency, and accuracy.