Towards a Quadratic Time Approximation of Graph Edit Distance.

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.  

Website: www.iam.unibe.ch/fki/staff/prof.-dr.-horst-bunke