Improving Graph Edit Distance Approximation by Centrality Measures
Lade...
Autor:innen
Bunke, Horst
Autor:in (Körperschaft)
Publikationsdatum
28.08.2014
Typ der Arbeit
Studiengang
Typ
04B - Beitrag Konferenzschrift
Herausgeber:innen
Herausgeber:in (Körperschaft)
Betreuer:in
Übergeordnetes Werk
22nd International Conference on Pattern Recognition
Themenheft
DOI der Originalpublikation
Link
Reihe / Serie
Reihennummer
Jahrgang / Band
Ausgabe / Nummer
Seiten / Dauer
3910-3914
Patentnummer
Verlag / Herausgebende Institution
Verlagsort / Veranstaltungsort
Stockholm
Auflage
Version
Programmiersprache
Abtretungsempfänger:in
Praxispartner:in/Auftraggeber:in
Zusammenfassung
In recent years the authors of the present paper introduced a powerful approximation fra or the graph edit distance problem. The basic idea of this approximation is to build a square cost matrix C = (cj), where each entry reflects the cost of a node substitution, deletion or insertion plus the matching cost arising from the local edge structure. Based on C an optimal assignment of the nodes and their local structure can be established in polynomial time (using, for instance, the Hungarian algorithm). Since this approach considers the local -- rather than the global -- structural properties of the graphs only, the obtained graph edit distance value is suboptimal in the sense of overestimating the true edit distance in general. The present paper pursues the idea of including topological information in the node labels in order to increase the amount of structural information available during the initial assignment process. In an experimental evaluation on three real world data sets a reduction of the overestimation can be observed while the run time is only moderately increased compared to our original framework.
Schlagwörter
Veranstaltung
22nd International Conference on Pattern Recognition, ICPR 2014
Startdatum der Ausstellung
Enddatum der Ausstellung
Startdatum der Konferenz
24.08.2014
Enddatum der Konferenz
28.08.2014
Datum der letzten Prüfung
ISBN
978-1-4799-5208-3
ISSN
Sprache
Englisch
Während FHNW Zugehörigkeit erstellt
Unbekannt
Zukunftsfelder FHNW
Publikationsstatus
Veröffentlicht
Begutachtung
Peer-Review der ganzen Publikation
Open Access-Status
Lizenz
Zitation
Riesen, K., & Bunke, H. (2014). Improving Graph Edit Distance Approximation by Centrality Measures. 22nd International Conference on Pattern Recognition, 3910–3914. https://doi.org/10.1109/ICPR.2014.670