A First Step Towards Exact Graph Edit Distance Using Bipartite Graph Matching
Loading...
Authors
Author (Corporation)
Publication date
2015
Typ of student thesis
Course of study
Collections
Type
04B - Conference paper
Editors
Liu, Cheng-Lin
Luo, Bin
Kropatsch, Walter G.
Cheng, Yian
Editor (Corporation)
Supervisor
Parent work
Graph-Based Representations in Pattern Recognition - 10th IAPR-TC-15 International Workshop, GbRPR 2015, Beijing, China, May 13-15, 2015.
Special issue
DOI of the original publication
Link
Series
Lecture Notes in Computer Science
Series number
9069
Volume
Issue / Number
Pages / Duration
77-86
Patent number
Publisher / Publishing institution
Springer
Place of publication / Event location
Hamburg
Edition
Version
Programming language
Assignee
Practice partner / Client
Abstract
In recent years, a powerful approximation framework for graph edit distance computation has been introduced. This particular approximation is based on an optimal assignment of local graph structures which can be established in polynomial time. However, as this approach considers the local structural properties of the graphs only, it yields sub-optimal solutions that overestimate the true edit distance in general. Recently, several attempts for reducing this overestimation have been made. The present paper is a starting point towards the study of sophisticated heuristics that can be integrated in these reduction strategies. These heuristics aim at further improving the overall distance quality while keeping the low computation time of the approximation framework. We propose an iterative version of one of the existing improvement strategies. An experimental evaluation clearly shows that there is large space for further substantial reductions of the overestimation in the existing approximation Framework.
Keywords
Subject (DDC)
Event
Exhibition start date
Exhibition end date
Conference start date
Conference end date
Date of the last check
ISBN
978-3-319-18223-0
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
Ferrer, M., Serratosa, F., & Riesen, K. (2015). A First Step Towards Exact Graph Edit Distance Using Bipartite Graph Matching. In C.-L. Liu, B. Luo, W. G. Kropatsch, & Y. Cheng (Eds.), Graph-Based Representations in Pattern Recognition - 10th IAPR-TC-15 International Workshop, GbRPR 2015, Beijing, China, May 13-15, 2015. (pp. 77–86). Springer. http://hdl.handle.net/11654/8237