Improving Graph Edit Distance Approximation by Centrality Measures
No Thumbnail Available
Authors
Bunke, Horst
Author (Corporation)
Publication date
28.08.2014
Typ of student thesis
Course of study
Collections
Type
04B - Conference paper
Editors
Editor (Corporation)
Supervisor
Parent work
22nd International Conference on Pattern Recognition
Special issue
DOI of the original publication
Link
Series
Series number
Volume
Issue / Number
Pages / Duration
3910-3914
Patent number
Publisher / Publishing institution
Place of publication / Event location
Stockholm
Edition
Version
Programming language
Assignee
Practice partner / Client
Abstract
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.
Keywords
Subject (DDC)
330 - Wirtschaft
005 - Computer Programmierung, Programme und Daten
005 - Computer Programmierung, Programme und Daten
Event
22nd International Conference on Pattern Recognition, ICPR 2014
Exhibition start date
Exhibition end date
Conference start date
24.08.2014
Conference end date
28.08.2014
Date of the last check
ISBN
978-1-4799-5208-3
ISSN
Language
English
Created during FHNW affiliation
Unknown
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 Graph Edit Distance Approximation by Centrality Measures. In: 22nd International Conference on Pattern Recognition. Stockholm. 28 August 2014. S. 3910–3914. ISBN 978-1-4799-5208-3. Verfügbar unter: http://hdl.handle.net/11654/9007