Approximation of Graph Edit Distance in Quadratic Time
Loading...
Authors
Author (Corporation)
Publication date
05/2015
Typ of student thesis
Course of study
Collections
Type
04B - Conference paper
Editors
Editor (Corporation)
Supervisor
Parent work
Graph-Based Representations in Pattern Recognition - 10th IAPR-TC-15 International Workshop, GbRPR 2015, Beijing, China, May 13-15, 2015.
Special issue
DOI of the original publication
Link
Series
Lecture Notes in Computer Science
Series number
9069
Volume
Issue / Number
Pages / Duration
Patent number
Publisher / Publishing institution
Place of publication / Event location
Bejing
Edition
Version
Programming language
Assignee
Practice partner / Client
Abstract
The basic idea of a recent graph matching framework is to reduce the problem of graph edit distance (GED) to an instance of a linear sum assignment problem (LSAP). The optimal solution for this simplified GED problem can be computed in cubic time and is eventually used to derive a suboptimal solution for the original GED problem. Yet, for large scale graphs and/or large scale graph sets the cubic time complexity remains a severe handicap of this procedure. Therefore, we propose to use suboptimal algorithms – with quadratic rather than cubic time complexity – for solving the underlying LSAP. In particular, we introduce several greedy assignment algorithms for approximating GED. In an experimental evaluation we show that there is great potential for further speeding up the GED computation. Moreover, we empirically confirm that the distances obtained by this procedure remain sufficiently accurate for graph based pattern classification.
Keywords
Subject (DDC)
Event
Exhibition start date
Exhibition end date
Conference start date
Conference end date
Date of the last check
ISBN
978-3-319-18223-0
ISSN
Language
English
Created during FHNW affiliation
Yes
Strategic action fields FHNW
Publication status
Published
Review
Peer review of the complete publication
Open access category
License
Citation
Riesen, K., Ferrer, M., Fischer, A., & Bunke, H. (2015, May). Approximation of Graph Edit Distance in Quadratic Time. Graph-Based Representations in Pattern Recognition - 10th IAPR-TC-15 International Workshop, GbRPR 2015, Beijing, China, May 13-15, 2015. http://hdl.handle.net/11654/10730