author = {Vincenzo Carletti and Benoit Gaüzère and Luc Brun and Mario Vento}, title = {Approximate Graph Edit Distance Computation Combining Bipartite Matching and Exact Neighborhood Substructure Distance}, booktitle = {Proceedings of the 10 th IAPR-TC15 Workshop on Graph-based Representations (GbR) in Pattern Recognition}, year = 2015, editor = {Cheng-Lin Liu and Bin Luo and Kropatsch, Walter G. and Jian Cheng}, volume = 9069, series = {LNCS}, pages = {188-197}, month = {May}, address = {Bejing, China}, organization = {IAPR TC15}, url ={draft version (PDF) :=https://brunl01.users.greyc.fr/ARTICLES/gbr2015Carletti.pdf, HAL:= https://hal.archives-ouvertes.fr/hal-01389626}, publisher = {Springer International Publishing}, note = {aceptance rate:67.9% }, theme= "pattern,ged", abstract={Graph edit distance corresponds to a flexible graph dissimilarity measure. Unfortunately, its computation requires an exponential complexity according to the number of nodes of both graphs being compared. Some heuristics based on bipartite assignment algorithms have been proposed in order to approximate the graph edit distance. However, these heuristics lack of accuracy since they are based either on small patterns providing a too local information or walks whose tottering induce some bias in the edit distance calculus. In this work, we propose to extend previous heuristics by considering both less local and more accurate patterns defined as subgraphs defined around each node.}