Zur Kurzanzeige

dc.contributor.authorRiesen, Kaspar
dc.contributor.authorFischer, Andreas
dc.contributor.authorBunke, Horst
dc.contributor.editorEl Gayar, Neamat
dc.contributor.editorSchwenker, Friedhelm
dc.contributor.editorSuen, Cheng
dc.date.accessioned2015-10-05T06:29:42Z
dc.date.available2015-10-05T06:29:42Z
dc.date.issued2014
dc.identifier.isbn978-3-319-11655-6
dc.identifier.urihttp://hdl.handle.net/11654/8221
dc.description.abstractGraph edit distance (GED) is a powerful and flexible graph dissimilarity model. Yet, exact computation of GED is an instance of a quadratic assignment problem and can thus be solved in exponential time complexity only. A previously introduced approximation framework reduces the computation of GED to an instance of a linear sum assignment problem. Major benefit of this reduction is that an optimal assignment of nodes (including local structures) can be computed in polynomial time. Given this assignment an approximate value of GED can be immediately derived. Yet, the primary optimization process of this approximation framework is able to consider local edge structures only, and thus, the observed speed up is at the expense of approximative, rather than exact, distance values. In order to improve the overall approximation quality, the present paper combines the original approximation framework with a fast tree search procedure. More precisely, we regard the assignment from the original approximation as a starting point for a subsequent beam search. In an experimental evaluation on three real world data sets a substantial gain of assignment accuracy can be observed while the run time remains remarkable low.
dc.language.isoen
dc.publisherSpringer
dc.relation.ispartofArtificial Neural Networks in Pattern Recognition - 6th IAPR TC 3 International Workshop, ANNPR 2014, Montreal, QC, Canada, October 6-8, 2014, Proceedings
dc.relation.ispartofseriesLecture Notes in Computer Science 877, ISBN 978-3-319-11655-6;
dc.accessRightsAnonymous
dc.subject.ddc300 - Sozialwissenschaftende
dc.titleCombining Bipartite Graph Matching and Beam Search for Graph Edit Distance Approximation
dc.type04 - Beitrag Sammelband oder Konferenzschrift
dc.spatialHamburg
dc.audienceScience
fhnw.publicationStatePublished
fhnw.ReviewTypeAnonymous ex ante peer review of a complete publication
fhnw.InventedHereYes
fhnw.PublishedSwitzerlandNo
fhnw.pagination117-128
fhnw.IsStudentsWorkno


Dateien zu dieser Ressource

DateienGrösseFormatAnzeige

Zu diesem Eintrag gibt es keine Dateien.

Der Eintrag erscheint in:

Zur Kurzanzeige