Estimating Graph Edit Distance Using Lower and Upper Bounds of Bipartite Approximations
No Thumbnail Available
Authors
Author (Corporation)
Publication date
02.03.2015
Typ of student thesis
Course of study
Collections
Type
01A - Journal article
Editors
Editor (Corporation)
Supervisor
Parent work
International Journal of Pattern Recognition and Artificial Intelligence
Special issue
DOI of the original publication
Link
Series
Series number
Volume
29
Issue / Number
2
Pages / Duration
1-27
Patent number
Publisher / Publishing institution
World Scientific
Place of publication / Event location
Edition
Version
Programming language
Assignee
Practice partner / Client
Abstract
The concept of graph edit distance (GED) is still one of the most flexible and powerful graph matching approaches available. Yet, exact computation of GED can 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, this approach considers local — rather than the global — structural properties of the graphs only, and thus GED derived from the optimal node assignment generally overestimates the true edit distance. Recently, it has been shown how the existing approximation framework can be exploited to additionally derive a lower bound of the exact edit distance without any additional computations. In this paper we make use of regression analysis in order to predict the exact GED using these two bounds. In an experimental evaluation on diverse graph data sets we empirically verify the gain of distance accuracy of the estimated GEDs compared to both bounds.
Keywords
graph edit distance, bipartite graph matching, predicting exact graph edit distance
Subject (DDC)
Event
Exhibition start date
Exhibition end date
Conference start date
Conference end date
Date of the last check
ISBN
ISSN
0218-0014
1793-6381
1793-6381
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, Andreas FISCHER und Horst BUNKE, 2015. Estimating Graph Edit Distance Using Lower and Upper Bounds of Bipartite Approximations. International Journal of Pattern Recognition and Artificial Intelligence. 2 März 2015. Bd. 29, Nr. 2, S. 1–27. Verfügbar unter: http://hdl.handle.net/11654/10147