  Computing efficiently a robust measure of similarity or dissimilarity between
graphs is a major challenge in Pattern Recognition. The Graph Edit Distance
(GED) is a flexible measure of dissimilarity between graphs which arises in
error-tolerant graph matching. It is defined from an optimal sequence of edit
operations (edit path) transforming one graph into an other. Unfortunately, the
exact computation of this measure is NP-hard. In the last decade, several
approaches have been proposed to approximate the GED in polynomial time, mainly
by solving linear programming problems. Among them, the bipartite GED has
received much attention. It is deduced from a linear sum assignment of the
nodes of the two graphs, which can be efficiently computed by Hungarian-type
algorithms. However, edit operations on nodes and edges are not handled
simultaneously, which limits the accuracy of the approximation. To overcome
this limitation, we propose to extend the linear assignment model to a
quadratic one, for directed or undirected graphs having labelized nodes and
edges. This is realized through the definition of a family of edit paths
induced by assignments between nodes. We formally show that the GED, restricted
to the paths in this family, is equivalent to a quadratic assignment problem.
Since this problem is NP-hard, we propose to compute an approximate solution by
an adaptation of the Integer Projected Fixed Point method. Experiments show
that the proposed approach is generally able to reach a more accurate
approximation of the optimal GED than the bipartite GED, with a computational
cost that is still affordable for graphs of non trivial sizes.
