Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Self-organizing maps for learning the edit costs in graph matching.

Michel Neuhaus1, Horst Bunke

  • 1Department of Computer Science, University of Bern, CH-3012 Bern, Switzerland. mneuhaus@iam.unibe.ch

IEEE Transactions on Systems, Man, and Cybernetics. Part B, Cybernetics : a Publication of the IEEE Systems, Man, and Cybernetics Society
|June 24, 2005
PubMed
Summary

This study introduces a novel method for automatically learning graph edit distance costs using self-organizing maps. This approach enhances graph similarity for classification tasks by adapting edit costs based on graph class.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Approximate Graph Edit Distance in Quadratic Time.

IEEE/ACM transactions on computational biology and bioinformatics·2015
Same author

A novel word spotting method based on recurrent neural networks.

IEEE transactions on pattern analysis and machine intelligence·2011
Same author

Novel kernels for error-tolerant graph classification.

Spatial vision·2009
Same author

Graph classification by means of Lipschitz embedding.

IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society·2009
Same author

A novel connectionist system for unconstrained handwriting recognition.

IEEE transactions on pattern analysis and machine intelligence·2009
Same author

Offline recognition of unconstrained handwritten texts using HMMs and statistical language models.

IEEE transactions on pattern analysis and machine intelligence·2008

Area of Science:

  • Computer Science
  • Machine Learning
  • Graph Theory

Background:

  • Graph matching and edit distance are crucial for comparing graph structures.
  • Automatic inference of edit operation costs remains a significant challenge in graph analysis.
  • Existing methods often require manual cost function definition, limiting scalability.

Purpose of the Study:

  • To develop an automated method for learning graph edit distance cost functions for numerically labeled graphs.
  • To adapt edit costs to improve discrimination between graphs of different classes.
  • To leverage self-organization principles for efficient cost function learning.

Main Methods:

  • Utilized self-organizing maps (SOMs) to model the distance-measuring spaces for node and edge labels.

Related Experiment Videos

  • Implemented a self-organization-based learning process to adapt edit costs.
  • Applied the learning procedure to datasets of line drawing graphs and diatom graphs.

    • Main Results:

    • The proposed SOM-based system effectively learns graph edit distance cost functions from sample data.
    • The learning process successfully increased intra-class graph similarity and decreased inter-class similarity.
    • Demonstrated the system's applicability and performance on two distinct real-world graph datasets.

    Conclusions:

    • Automated learning of graph edit distance costs is feasible and beneficial for graph classification.
    • Self-organizing maps provide a robust framework for adapting edit costs in a data-driven manner.
    • The developed method offers a significant advancement for applications requiring accurate graph comparison and analysis.