Improving Approximate Graph Edit Distance by Means of a Greedy Swap Strategy
No Thumbnail Available
Authors
Bunke, Horst
Author (Corporation)
Publication date
2014
Typ of student thesis
Course of study
Collections
Type
04B - Conference paper
Editors
Editor (Corporation)
Supervisor
Parent work
Image and Signal Processing. 6th International Conference, ICISP 2014, Cherbourg, France, June 20 -- July 2, 2014, Proceedings
Special issue
DOI of the original publication
Link
Series
Series number
Volume
Issue / Number
Pages / Duration
314-321
Patent number
Publisher / Publishing institution
Place of publication / Event location
Stockholm
Edition
Version
Programming language
Assignee
Practice partner / Client
Abstract
The authors of the present paper previously introduced a fast approximation framework for the graph edit distance problem. The basic idea of this approximation is to build a square cost matrix C = (c ij ), where each entry c ij 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 is established in polynomial time. Yet, this procedure considers the graph structure only in a local way, and thus, an overestimation of the true graph edit distance has to be accepted. The present paper aims at reducing this overestimation by means of an additional greedy search strategy that builds upon the initial assignment. In an experimental evaluation on three real world data sets we empirically verify a substantial gain of distance accuracy while run time is nearly not affected.
Keywords
Subject (DDC)
Event
6th International Conference on Image and Signal Processing (ICISP 2014)
Exhibition start date
Exhibition end date
Conference start date
Conference end date
Date of the last check
ISBN
978-1-4799-5208-3
ISSN
Language
English
Created during FHNW affiliation
Yes
Strategic action fields FHNW
Publication status
Published
Review
Peer review of the complete publication
Open access category
License
Citation
RIESEN, Kaspar und Horst BUNKE, 2014. Improving Approximate Graph Edit Distance by Means of a Greedy Swap Strategy. In: Image and Signal Processing. 6th International Conference, ICISP 2014, Cherbourg, France, June 20 -- July 2, 2014, Proceedings. Stockholm. 2014. S. 314–321. ISBN 978-1-4799-5208-3. Verfügbar unter: http://hdl.handle.net/11654/8225