Improving bipartite graph edit distance approximation using various search strategies
Loading...
Authors
Bunke, Horst
Author (Corporation)
Publication date
04.2015
Typ of student thesis
Course of study
Collections
Type
01A - Journal article
Editors
Editor (Corporation)
Supervisor
Parent work
Pattern Recognition
Special issue
DOI of the original publication
Link
Series
Series number
Volume
48
Issue / Number
4
Pages / Duration
Patent number
Publisher / Publishing institution
Place of publication / Event location
Edition
Version
Programming language
Assignee
Practice partner / Client
Abstract
Recently the authors of the present paper introduced an approximation framework for the graph edit distance problem. The basic idea of this approximation is to first build a square cost matrix C=(cij)C=(cij), where each entry cij 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. Since this approach considers local – rather than the global – structural properties of the graphs only, the graph edit distance derived from the optimal node assignment generally overestimates the true edit distance. The present paper pursues the idea of applying additional search strategies that build upon the initial assignment in order to reduce this overestimation. To this end, six different search strategies are investigated in this paper. In an exhaustive experimental evaluation on five real world graph data sets we empirically verify a substantial gain of distance accuracy by means of all search methods while run time remains remarkably low.
Keywords
Bipartite graph matching;
Approximate graph edit distance
Keywords
Bipartite graph matching, approximate 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
0031-3203
1873-5142
1873-5142
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, K., & Bunke, H. (2015). Improving bipartite graph edit distance approximation using various search strategies. Pattern Recognition, 48(4). http://hdl.handle.net/11654/10166