Title:
A Quadratic Programming Approach to the Graph Edit Distance Problem
Speaker:
Horst Bunke
Subject:
graph theory
Area:
Mathematics
Type of school:
university
School name:
University of Bern
Country:
United States
Course language:
English
Course media:
Video
Course duration:
Contributor:
pbp
Comments:
A Quadratic Programming Approach to the Graph Edit Distance Problem
author: Horst Bunke , University of Bern
Description
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.