Approximation of Graph Edit Distance in Quadratic Time
Autor:innen
Autor:in (Körperschaft)
Publikationsdatum
05/2015
Typ der Arbeit
Studiengang
Typ
04B - Beitrag Konferenzschrift
Herausgeber:innen
Herausgeber:in (Körperschaft)
Betreuer:in
Ãœbergeordnetes Werk
Graph-Based Representations in Pattern Recognition - 10th IAPR-TC-15 International Workshop, GbRPR 2015, Beijing, China, May 13-15, 2015.
Themenheft
DOI der Originalausgabe
Link
Reihe / Serie
Lecture Notes in Computer Science
Jahrgang / Band
9069
Ausgabe / Nummer
Seiten / Dauer
Patentnummer
Verlag / Herausgebende Institution
Verlagsort / Veranstaltungsort
Bejing
Auflage
Version
Programmiersprache
Abtretungsempfänger:in
Praxispartner:in/Auftraggeber:in
Zusammenfassung
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.
Schlagwörter
Fachgebiet (DDC)
Veranstaltung
Startdatum der Ausstellung
Enddatum der Ausstellung
Startdatum der Konferenz
Enddatum der Konferenz
Datum der letzten Prüfung
ISBN
978-3-319-18223-0
ISSN
Sprache
Englisch
Während FHNW Zugehörigkeit erstellt
Ja
Publikationsstatus
Veröffentlicht
Begutachtung
Peer-Review der ganzen Publikation
Open Access-Status
Lizenz
Zitation
RIESEN, Kaspar, Miquel FERRER, Andreas FISCHER und Horst BUNKE, 2015. Approximation of Graph Edit Distance in Quadratic Time. In: Graph-Based Representations in Pattern Recognition - 10th IAPR-TC-15 International Workshop, GbRPR 2015, Beijing, China, May 13-15, 2015. Bejing. Mai 2015. Lecture Notes in Computer Science. ISBN 978-3-319-18223-0. Verfügbar unter: http://hdl.handle.net/11654/10730