Title:
A Quadratic Programming Approach to the Graph Edit Distance Problem
Speaker:
Horst Bunke
Subject:
Algorithms and Data Structures. Graph Theory.
Area:
Computer Science
Type of school:
Online video lectures
School name:
VideoLectures.Net
Country:
other
Course language:
English
Course media:
Video
Course duration:
Contributor:
Lennert Sloth
Comments:
In this paper we propose a quadratic programming approach to computing the edit distance of graphs. Whereas the standard edit distance is defined with respect to a minimum-cost edit path between graphs, we introduce the notion of fuzzy edit paths between graphs and provide a quadratic programming formulation for the minimization of fuzzy edit costs. Experiments on real-world graph data demonstrate that our proposed method is able to outperform the standard edit distance method in terms of recognition accuracy on two out of three data sets.