Approximate graph edit distance in quadratic time
Vorschaubild nicht verfügbar
Autor:innen
Autor:in (Körperschaft)
Publikationsdatum
2020
Typ der Arbeit
Studiengang
Typ
01A - Beitrag in wissenschaftlicher Zeitschrift
Herausgeber:innen
Herausgeber:in (Körperschaft)
Betreuer:in
Übergeordnetes Werk
IEEE/ACM Transactions on Computational Biology and Bioinformatics
Themenheft
DOI der Originalpublikation
Link
Reihe / Serie
Reihennummer
Jahrgang / Band
17
Ausgabe / Nummer
2
Seiten / Dauer
483-494
Patentnummer
Verlag / Herausgebende Institution
IEEE
Verlagsort / Veranstaltungsort
New York
Auflage
Version
Programmiersprache
Abtretungsempfänger:in
Praxispartner:in/Auftraggeber:in
Zusammenfassung
Graph edit distance is one of the most flexible and general graph matching models available. The major drawback of graph edit distance, however, is its computational complexity that restricts its applicability to graphs of rather small size. Recently, the authors of the present paper introduced a general approximation framework for the graph edit distance problem. The basic idea of this specific algorithm is to first compute an optimal assignment of independent local graph structures (including substitutions, deletions, and insertions of nodes and edges). This optimal assignment is complete and consistent with respect to the involved nodes of both graphs and can thus be used to instantly derive an admissible (yet suboptimal) solution for the original graph edit distance problem in Ο(n³) time. For large scale graphs or graph sets, however, the cubic time complexity may still be too high. Therefore, we propose to use suboptimal algorithms with quadratic rather than cubic time for solving the basic assignment problem. In particular, the present paper introduces five different greedy assignment algorithms in the context of graph edit distance approximation. In an experimental evaluation, we show that these methods have great potential for further speeding up the computation of graph edit distance while the approximated distances remain sufficiently accurate for graph based pattern classification.
Schlagwörter
Fachgebiet (DDC)
330 - Wirtschaft
Veranstaltung
Startdatum der Ausstellung
Enddatum der Ausstellung
Startdatum der Konferenz
Enddatum der Konferenz
Datum der letzten Prüfung
ISBN
ISSN
1545-5963
1557-9964
1557-9964
Sprache
Englisch
Während FHNW Zugehörigkeit erstellt
Ja
Publikationsstatus
Veröffentlicht
Begutachtung
Peer-Review der ganzen Publikation
Open Access-Status
Closed
Lizenz
Zitation
RIESEN, Kaspar, Miquel FERRER und Horst BUNKE, 2020. Approximate graph edit distance in quadratic time. IEEE/ACM Transactions on Computational Biology and Bioinformatics. 2020. Bd. 17, Nr. 2, S. 483–494. DOI 10.1109/TCBB.2015.2478463. Verfügbar unter: https://irf.fhnw.ch/handle/11654/42709