Julien Lerouge

Julien Lerouge

Senior Data Scientist @ QuickSign
  • Deep learning
  • Image processing
  • Document analysis & understanding (classification, OCR, NLP)


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.