Approximate graph edit distance in quadratic time
Loading...
Author (Corporation)
Publication date
2020
Typ of student thesis
Course of study
Collections
Type
01A - Journal article
Editors
Editor (Corporation)
Supervisor
Parent work
IEEE/ACM Transactions on Computational Biology and Bioinformatics
Special issue
DOI of the original publication
Link
Series
Series number
Volume
17
Issue / Number
2
Pages / Duration
483-494
Patent number
Publisher / Publishing institution
IEEE
Place of publication / Event location
New York
Edition
Version
Programming language
Assignee
Practice partner / Client
Abstract
Graph edit distance is one of the most flexible and general graph matching models available. The major drawback of graph edit distance, however, is its computational complexity that restricts its applicability to graphs of rather small size. Recently, the authors of the present paper introduced a general approximation framework for the graph edit distance problem. The basic idea of this specific algorithm is to first compute an optimal assignment of independent local graph structures (including substitutions, deletions, and insertions of nodes and edges). This optimal assignment is complete and consistent with respect to the involved nodes of both graphs and can thus be used to instantly derive an admissible (yet suboptimal) solution for the original graph edit distance problem in Ο(n³) time. For large scale graphs or graph sets, however, the cubic time complexity may still be too high. Therefore, we propose to use suboptimal algorithms with quadratic rather than cubic time for solving the basic assignment problem. In particular, the present paper introduces five different greedy assignment algorithms in the context of graph edit distance approximation. In an experimental evaluation, we show that these methods have great potential for further speeding up the computation of graph edit distance while the approximated distances remain sufficiently accurate for graph based pattern classification.
Keywords
Subject (DDC)
Event
Exhibition start date
Exhibition end date
Conference start date
Conference end date
Date of the last check
ISBN
ISSN
1545-5963
1557-9964
1557-9964
Language
English
Created during FHNW affiliation
Yes
Strategic action fields FHNW
Publication status
Published
Review
Peer review of the complete publication
Open access category
Closed
License
Citation
Riesen, K., Ferrer, M., & Bunke, H. (2020). Approximate graph edit distance in quadratic time. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 17(2), 483–494. https://doi.org/10.1109/TCBB.2015.2478463