New binary linear programming formulation to compute the graph edit distance

In this paper, a new binary linear programming formulation for computing the exact Graph Edit Distance (GED) between two graphs is proposed. A fundamental strength of the formulations lies in their genericity since the GED can be computed between directed or undirected fully attributed graphs. Moreover, a continuous relaxation of the domain constraints in the formulation provides an efficient lower bound approximation of the GED. A complete experimental study that compares the proposed formulations with six state-of-the-art algorithms is provided. By considering both the accuracy of the proposed solution and the efficiency of the algorithms as performance criteria, the results show that none of the compared methods dominate the others in the Pareto sense. In general, our formulation converges faster to optimality while being able to scale up to match the largest graphs in our experiments. The relaxed formulation leads to an accurate approach that is 12% more accurate than the best approximate method of our benchmark.