Improved quadratic time approximation of graph edit distance by combining Hausdorff matching and greedy assignment

Fischer, Andreas (Department of Informatics, University of Fribourg, Fribourg, Switzerland ; School of Engineering and Architecture (HEIA-FR), HES-SO // University of Applied Sciences Western Switzerland) ; Riesen, Kaspar (Institute for Information Systems, University of Applied Sciences and Arts Northwestern Switzerland, Olten, Switzerland ; Institute of Computer Science and Applied Mathematics, University of Bern, Bern, Switzerland) ; Bunke, Horst (Institute of Computer Science and Applied Mathematics, University of Bern, Bern, Switzerland)

Approximation of graph edit distance in polynomial time enables us to compare large, arbitrarily labeled graphs for structural pattern recognition. In a recent approximation framework, bipartite graph matching (BP) has been proposed to reduce the problem of edit distance to a cubic-time linear sum assignment problem (LSAP) between local substructures. Following the same line of research, first attempts towards quadratic-time approximation have been made recently, including a lower bound based on Hausdorff matching (Hausdorff Edit Distance) and an upper bound based on greedy assignment (Greedy Edit Distance). In this paper, we compare the two approaches and derive a novel upper bound (BP2) which combines advantages of both. In an experimental evaluation on the IAM graph database repository, we demonstrate that the proposed quadratic-time methods perform equally well or, quite surprisingly, in some cases even better than the cubic-time method.


Keywords:
Article Type:
scientifique
Faculty:
Ingénierie et Architecture
School:
HEIA-FR
Institute:
iCoSys - Institut des systèmes complexes
Date:
2017-02
Pagination:
8 p.
Published in:
Pattern Recognition Letters
Numeration (vol. no.):
2017, vol. 87, no. 1, pp. 55-62
DOI:
ISSN:
0167-8655
Appears in Collection:

Note: The status of this file is: restricted


 Record created 2020-10-13, last modified 2020-10-27

Fulltext:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)