Improving Hausdorff edit distance using structural node context

Andreas Fischer, Seiichi Uchida, Volkmar Frinken, Kaspar Riesen, Horst Bunke

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationGraph-Based Representations in Pattern Recognition - 10th IAPR-TC-15 InternationalWorkshop, GbRPR 2015, Proceedings
EditorsBin Luo, Walter G. Kropatsch, Cheng-Lin Liu, Jian Cheng
PublisherSpringer Verlag
Number of pages10
ISBN (Electronic)9783319182230
Publication statusPublished - 2015
Event10th IAPR-TC-15 International Workshop on Graph-Based Representations in Pattern Recognition, GbRPR 2015 - Beijing, China
Duration: May 13 2015May 15 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other10th IAPR-TC-15 International Workshop on Graph-Based Representations in Pattern Recognition, GbRPR 2015

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Improving Hausdorff edit distance using structural node context'. Together they form a unique fingerprint.

Cite this