Approximation of graph edit distance based on Hausdorff matching |
| |
Authors: | Andreas Fischer Ching Y. Suen Volkmar Frinken Kaspar Riesen Horst Bunke |
| |
Affiliation: | 1. Concordia University, Centre for Pattern Recognition and Machine Intelligence, 1455 de Maisonneuve Blvd West, Montreal, Canada, H3G 1M8;2. Kyushu University, Faculty of Information Science and Electrical Engineering, 744 Motooka, Nishi-ku, Fukuoka 819-0395, Japan;3. University of Applied Sciences and Arts Northwestern Switzerland, Riggenbachstrasse 16, 4600 Olten, Switzerland;4. University of Bern, Institute of Computer Science and Applied Mathematics, Neubrückstrasse 10, 3012 Bern, Switzerland |
| |
Abstract: | 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. |
| |
Keywords: | Graph edit distance Hausdorff distance Approximation algorithms Graph classification Graph embedding Handwriting recognition |
本文献已被 ScienceDirect 等数据库收录! |
|