Learning Heuristics to Reduce the Overestimation of Bipartite Graph Edit Distance Approximation
Loading...
Authors
Author (Corporation)
Publication date
2015
Typ of student thesis
Course of study
Collections
Type
04B - Conference paper
Editors
Perner, Petra
Editor (Corporation)
Supervisor
Parent work
Machine Learning and Data Mining in Pattern Recognition - 11th International Conference, MLDM 2015, Hamburg, Germany, July 20-21, 2015
Special issue
DOI of the original publication
Link
Series
Lecture Notes in Computer Science
Series number
9166
Volume
Issue / Number
Pages / Duration
17-31
Patent number
Publisher / Publishing institution
Springer
Place of publication / Event location
Hamburg
Edition
Version
Programming language
Assignee
Practice partner / Client
Abstract
In data mining systems, which operate on complex data with structural relationships, graphs are often used to represent the basic objects under study. Yet, the high representational power of graphs is also accompanied by an increased complexity of the associated algorithms. Exact graph similarity or distance, for instance, can be computed in exponential time only. Recently, an algorithmic framework that allows graph dissimilarity computation in cubic time with respect to the number of nodes has been presented. This fast computation is at the expense, however, of generally overestimating the true distance. The present paper introduces six different post-processing algorithms that can be integrated in this suboptimal graph distance framework. These novel extensions aim at improving the overall distance quality while keeping the low computation time of the approximation. An experimental evaluation clearly shows that the proposed heuristics substantially reduce the overestimation in the existing approximation framework while the computation time remains remarkably low.
Keywords
Subject (DDC)
Event
Exhibition start date
Exhibition end date
Conference start date
20.07.2015
Conference end date
21.07.2015
Date of the last check
ISBN
978-3-319-21023-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). Learning Heuristics to Reduce the Overestimation of Bipartite Graph Edit Distance Approximation. In P. Perner (Ed.), Machine Learning and Data Mining in Pattern Recognition - 11th International Conference, MLDM 2015, Hamburg, Germany, July 20-21, 2015 (pp. 17–31). Springer. http://hdl.handle.net/11654/10151