Towards a Quadratic Time Approximation of Graph Edit Distance.
Place: Large Lecture Room
Affiliation: Research Group on Computer Vision and Artificial Intelligence IAM, University of Bern. Switzerland
Graph edit distance is a powerful and flexible method for error-tolerant graph matching. Yet oftern it can only be calculated for small graphs due to its exponential time complexity. In this paper we propose a quadratic time approximation of graph edit distance based on the Hausdorff distance. 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. Overall, the proposed Hausforff edit distance shows a promising potential in terms of flexibility, efficiency, and accuracy.
SHARE ON
