Computing the Graph Edit Distance Using Dominant Sets

We present a new approach to compute the graph edit distance between two attributed graphs which is based on a formal connection between the graph edit distance problem and that of finding a dominant set in an auxiliary edge-weighted 'association' graph. Experiments performed on various data sets show that with the proposed approach we are able to improve on state-of-the-art algorithms. © 2012 ICPR Org Committee