Improving Hausdorff Edit Distance Using Structural Node Context

Loading...
Thumbnail Image
Authors
Fischer, Andreas
Uchida, Seiichi
Frinken, Volkmar
Bunke, Horst
Author (Corporation)
Publication date
2015
Typ of student thesis
Course of study
Type
04B - Conference paper
Editors
Liu, Cheng-Lin
Luo, Bin
Kropatsch, Walter G.
Cheng, Jian
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
Patent number
Publisher / Publishing institution
Springer
Place of publication / Event location
Hamburg
Edition
Version
Programming language
Assignee
Practice partner / Client
Abstract
In order to cope with the exponential time complexity of graph edit distance, several polynomial-time approximation algorithms have been proposed in recent years. The Hausdorff edit distance is a quadratic-time matching procedure for labeled graphs which reduces the edit distance to a correspondence problem between local substructures. In its original formulation, nodes and their adjacent edges have been considered as local substructures. In this paper, we integrate a more general structural node context into the matching procedure based on hierarchical subgraphs. In an experimental evaluation on diverse graph data sets, we demonstrate that the proposed generalization of Hausdorff edit distance can significantly improve the accuracy of graph classification while maintaining low computational complexity.
Keywords
Subject (DDC)
Project
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
German
Created during FHNW affiliation
Yes
Strategic action fields FHNW
Publication status
Published
Review
Peer review of the complete publication
Open access category
License
Citation
Fischer, A., Uchida, S., Frinken, V., Riesen, K., & Bunke, H. (2015). Improving Hausdorff Edit Distance Using Structural Node Context. In C.-L. Liu, B. Luo, W. G. Kropatsch, & J. Cheng (eds.), Graph-Based Representations in Pattern Recognition - 10th IAPR-TC-15 International Workshop, GbRPR 2015, Beijing, China, May 13-15, 2015. Springer. http://hdl.handle.net/11654/8238