Improving bipartite graph edit distance approximation using various search strategies

Vorschaubild nicht verfügbar
Autor:innen
Bunke, Horst
Autor:in (Körperschaft)
Publikationsdatum
04/2015
Typ der Arbeit
Studiengang
Sammlung
Institut für Wirtschaftsinformatik
Komplettanzeige
Typ
01A - Beitrag in wissenschaftlicher Zeitschrift
Herausgeber:innen
Herausgeber:in (Körperschaft)
Betreuer:in
Übergeordnetes Werk
Pattern Recognition
Themenheft
DOI der Originalpublikation
URI
http://hdl.handle.net/11654/10166
Link
Reihe / Serie
Reihennummer
Jahrgang / Band
48
Ausgabe / Nummer
4
Seiten / Dauer
Patentnummer
Verlag / Herausgebende Institution
Verlagsort / Veranstaltungsort
Auflage
Version
Programmiersprache
Abtretungsempfänger:in
Praxispartner:in/Auftraggeber:in
Zusammenfassung
Recently the authors of the present paper introduced an approximation framework for the graph edit distance problem. The basic idea of this approximation is to first build a square cost matrix C=(cij)C=(cij), where each entry cij 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. Since this approach considers local – rather than the global – structural properties of the graphs only, the graph edit distance derived from the optimal node assignment generally overestimates the true edit distance. The present paper pursues the idea of applying additional search strategies that build upon the initial assignment in order to reduce this overestimation. To this end, six different search strategies are investigated in this paper. In an exhaustive experimental evaluation on five real world graph data sets we empirically verify a substantial gain of distance accuracy by means of all search methods while run time remains remarkably low. Keywords Bipartite graph matching; Approximate graph edit distance
Schlagwörter
Bipartite graph matching, approximate graph edit distance
Fachgebiet (DDC)
Projekt
Veranstaltung
Startdatum der Ausstellung
Enddatum der Ausstellung
Startdatum der Konferenz
Enddatum der Konferenz
Datum der letzten Prüfung
ISBN
ISSN
0031-3203
1873-5142
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 und Horst BUNKE, 2015. Improving bipartite graph edit distance approximation using various search strategies. Pattern Recognition. April 2015. Bd. 48, Nr. 4. Verfügbar unter: http://hdl.handle.net/11654/10166
Komplettanzeige