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.