Learning Heuristics to Reduce the Overestimation of Bipartite Graph Edit Distance Approximation
Vorschaubild nicht verfügbar
Autor:innen
Autor:in (Körperschaft)
Publikationsdatum
2015
Typ der Arbeit
Studiengang
Typ
04 - Beitrag Sammelband oder Konferenzschrift
Herausgeber:innen
Perner, Petra
Herausgeber:in (Körperschaft)
Betreuer:in
Übergeordnetes Werk
Machine Learning and Data Mining in Pattern Recognition - 11th International Conference, MLDM 2015, Hamburg, Germany, July 20-21, 2015
Themenheft
DOI der Originalpublikation
Link
Reihe / Serie
Lecture Notes in Computer Science
Reihennummer
9166
Jahrgang / Band
Ausgabe / Nummer
Seiten / Dauer
17-31
Patentnummer
Verlag / Herausgebende Institution
Springer
Verlagsort / Veranstaltungsort
Hamburg
Auflage
Version
Programmiersprache
Abtretungsempfänger:in
Praxispartner:in/Auftraggeber:in
Zusammenfassung
In data mining systems, which operate on complex data with structural relationships, graphs are often used to represent the basic objects under study. Yet, the high representational power of graphs is also accompanied by an increased complexity of the associated algorithms. Exact graph similarity or distance, for instance, can be computed in exponential time only. Recently, an algorithmic framework that allows graph dissimilarity computation in cubic time with respect to the number of nodes has been presented. This fast computation is at the expense, however, of generally overestimating the true distance. The present paper introduces six different post-processing algorithms that can be integrated in this suboptimal graph distance framework. These novel extensions aim at improving the overall distance quality while keeping the low computation time of the approximation. An experimental evaluation clearly shows that the proposed heuristics substantially reduce the overestimation in the existing approximation framework while the computation time remains remarkably low.
Schlagwörter
Fachgebiet (DDC)
Veranstaltung
Startdatum der Ausstellung
Enddatum der Ausstellung
Startdatum der Konferenz
20.07.2015
Enddatum der Konferenz
21.07.2015
Datum der letzten Prüfung
ISBN
978-3-319-21023-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
FERRER, Miguel, Francesco SERRATOSA und Kaspar RIESEN, 2015. Learning Heuristics to Reduce the Overestimation of Bipartite Graph Edit Distance Approximation. In: Petra PERNER (Hrsg.), Machine Learning and Data Mining in Pattern Recognition - 11th International Conference, MLDM 2015, Hamburg, Germany, July 20-21, 2015. Hamburg: Springer. 2015. S. 17–31. Lecture Notes in Computer Science, 9166. ISBN 978-3-319-21023-0. Verfügbar unter: http://hdl.handle.net/11654/10151