Julien Lerouge

Julien Lerouge

R&D engineer @ Mitek Systems Paris
  • Machine learning
  • Image processing
  • Document analysis
  • Text recognition

Publication

Exact Graph Edit Distance Computation Using a Binary Linear Program

1Normandie Université, LITIS EA 4108, University of Rouen, 76801, Saint-Etienne du Rouvray, France
2LI Tours, Avenue Jean Portalis, Tours, France

Abstract :

This paper presents a binary linear program which computes the exact graph edit distance between two richly attributed graphs (i.e. with attributes on both vertices and edges). Without solving graph edit distance for large graphs, the proposed program enables to process richer and larger graphs than existing approaches based on mathematical programming and the A∗ algorithm. Experiments are led on 7 standard graph datasets and the proposed approach is compared with two state-of-the-art algorithms.