Sébastien Bougleux

Luc Brun

Vincenzo Carletti

Pasquale Foggia

Benoit Gaüzère

Mario Vento

A Quadratic Assignment Formulation of the Graph Edit Distance

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. a d b c a

Introduction

The definition of efficient similarity or dissimilarity measures between graphs is a key problem in structural pattern recognition [START_REF] Conte | Thirty years of graph matching in Pattern Recognition[END_REF][START_REF] Foggia | Graph matching and learning in pattern recognition on the last ten years[END_REF][START_REF] Vento | A long trip in the charming world of graphs for pattern recognition[END_REF]. This problem is nicely addressed by the graph edit distance, which constitutes one of the most flexible graph dissimilarity measure [START_REF] Tsai | Error-correcting isomorphisms of attributed relational graphs for pattern analysis[END_REF][START_REF] Bunke | Inexact graph matching for structural pattern recognition[END_REF][START_REF] Sanfeliu | A distance measure between attributed relational graphs for pattern recognition[END_REF][START_REF] Bunke | Error correcting graph matching: on the influence of the underlying cost function[END_REF]. Given two graphs G 1 and G 2 , such a distance may be understood as a measure of the minimal amount of distortion required to transform G 1 into G 2 . The graph edit distance is defined from the notion of edit path which corresponds to a sequence of elementary transformations of a graph into another. An edit operation is a transformation performed on the structure of a graph, here restricted to be elementary: node or edge insertion, removal and substitution. This is illustrated in Fig. 1. Edit operations are penalized by a real non-negative cost function c e (.), and the cost of the edit path is defined as the sum of all its elementary operation's costs. An optimal edit path, transforming a graph G 1 = (V 1 , E 1 ) into a graph G 2 = (V 2 , E 2 ), have a minimal cost among all edit paths from G 1 to G 2 . Its cost defines the GED from G 1 to G 2 : GED(G 1 , G 2 ) = min (e1,...,e k )∈P(G1,G2)

k i=1 c e (e i ). (1)
Figure 1: A possible edit path to transform the graph G 1 into the graph G 2 . If we assume that all the edit operation have an unitary cost, the overall cost of the transformation is equal to 5.

where P(G 1 , G 2 ) is the set of all edit paths from G 1 to G 2 , and e i is an edit operation. In this paper, graphs are assumed to be simple and labeled.

Computing the GED is NP-hard, in fact NP-complete, and its approximation is APXhard [START_REF] Lin | Hardness of approximating graph transformation problem[END_REF]. A common approach consists in representing the problem into a state space where the optimal solution can be found using for example the A * algorithm, in exponential time complexity. This is thus restricted to small graphs composed of about 10 nodes. Such a complexity compromises the suitability of the GED in many practical applications where the graphs are usually one order of magnitude bigger. However, most of real world problems do not require the computation of the exact GED, and the use of an approximation is often sufficient. For this reason, the interest of the scientific community has been focused on methods providing efficient approximations of the GED, mainly linear and suboptimal ones.

In [START_REF] Justice | A binary linear programming formulation of the graph edit distance[END_REF], the GED is modeled as a binary linear programming problem for graphs with labeled nodes and unlabeled edges. The relaxation of the initial problem provides a lower bound of the GED which however cannot be readily associated to an edit path. An upper bound is also provided through an approximation of the binary program. The resulting problem corresponds to a square linear sum assignment problem (LSAP), i.e. a weighted bipartite graph matching, such that the nodes of graph G 1 can be removed, substituted to the nodes of graph G 2 , as well as the nodes of G 2 can be inserted. A node assignment incorporating possible removals and insertions is then defined as a bijective mapping, thus representing a set of edit operations on nodes. Each edit operation is penalized by a cost. The cost of an assignment is then defined as the sum of the costs of its corresponding edit operations on nodes. The LSAP consists in selecting an assignment having a minimal cost, which can be computed in polynomial time complexity, for instance with the Hungarian algorithm, see [START_REF] Sierksma | Linear and Integer Programming: Theory and Practice[END_REF][START_REF] Burkard | Assignment Problems[END_REF] for more details on linear programming and LSAP. The resulting optimal node assignment allows to deduce, in a non ambiguous way, the edge operations that define an edit path, mostly not minimal but short. The cost of such a short path defines an approximate GED.

The same line of research has been followed in [START_REF] Riesen | Bipartite graph matching for computing the edit distance of graphs[END_REF][START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF], but such that labels of edges are also taken into account in the assignment through the cost of edit operations on nodes, which is neglected in the upper bound proposed in [START_REF] Justice | A binary linear programming formulation of the graph edit distance[END_REF]. The resulting distance, called the bipartite GED, has received much attention [START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF][START_REF] Fankhauser | Speeding up graph edit distance computation through fast bipartite matching[END_REF][START_REF] Serratosa | Fast computation of Bipartite graph matching[END_REF][START_REF] Gaüzère | Approximate Graph Edit Distance Guided by Bipartite Matching of Bags of Walks[END_REF][START_REF] Riesen | Improving approximate graph edit distance using genetic algorithms[END_REF][START_REF] Riesen | Combining Bipartite Graph Matching and Beam Search for Graph Edit Distance Approximation[END_REF][START_REF] Riesen | Improving bipartite graph edit distance approximation using various search strategies[END_REF][START_REF] Riesen | Estimating graph edit distance using lower and upper bounds of bipartite approximations[END_REF][START_REF] Ferrer | A First Step Towards Exact Graph Edit Distance Using Bipartite Graph Matching[END_REF][START_REF] Carletti | Approximate graph edit distance computation combining bipartite matching and exact neighborhood substructure distance[END_REF]. In order to select a relevant assignment, a bag of patterns is attached to each node, and each possible substitution is penalized by a cost that measures the affinity between the bags, hence taking into account the edge information. Similarly, node removals and insertions are penalized by a cost measuring the importance of the bags.

The definition of the bags of patterns is a key point, as well as the associated measure of affinity. Incident edges have been initially proposed in [START_REF] Riesen | Bipartite graph matching for computing the edit distance of graphs[END_REF][START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF], and the cost between two nodes (or bags) is itself defined as the cost of the linear sum assignment of the patterns within the bags, following the same framework as the one defined for the nodes. The cost of substituting, removing and inserting the patterns depends on the original edit cost function c e . The resulting optimal node assignment allows to deduce, in a non ambiguous way, the edge operations that define an edit path, mostly not minimal but short. The cost of such a short path defines the bipartite GED.

Remark that this approach assumes that an edit path may be deduced from a sequence of edit operations applied on nodes only. As we will see in this paper, this is possible because there is an equivalence relation between assignments and edit paths. Intuitively, this is due to the strong relationship that exists between GED and morphism between graphs. Under special conditions on the cost of edit operations, computing the GED is equivalent to compute a maximum common subgraph of two graphs [START_REF] Bunke | On a relation between graph edit distance and maximum common subgraph[END_REF][START_REF] Bunke | Error correcting graph matching: on the influence of the underlying cost function[END_REF]. More generally, any mapping between the nodes of two graphs induces an edit path which substitutes all mapped nodes together with all their incident edges, and inserts or removes the non-mapped nodes/edges. Conversely, given an edit path between two graphs, such that each node and each edge is substituted only once, one can define a mapping between the substituted nodes and edges of both graphs.

While the bipartite GED provides a good approximation of the GED, it overestimates it. As shown by several works, this overestimation can only be marginally reduced, for instance by considering more global information than the one supported by incident edges [START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF][START_REF] Gaüzère | Approximate Graph Edit Distance Guided by Bipartite Matching of Bags of Walks[END_REF][START_REF] Carletti | Approximate graph edit distance computation combining bipartite matching and exact neighborhood substructure distance[END_REF], or by modifying the resulting edit path by genetic algorithms [START_REF] Riesen | Improving approximate graph edit distance using genetic algorithms[END_REF], see [START_REF] Riesen | Improving bipartite graph edit distance approximation using various search strategies[END_REF] for more details. Although these methods provide an interesting compromise between time complexity and approximation quality, they are inherently limited to compute linear approximations of the GED.

To fully describe the GED, both node and edge assignments should be considered simultaneously. Indeed, operations on edges can only be deduced from operations performed on their two incident nodes. For instance, an edge can be substituted to another one only if its incident nodes are substituted. This pairwise constraint on nodes is closely related to the one involved in graph matching. It is known that graph matching problems, and more generally problems that incorporate pairwise constraints, can be cast as a quadratic assignment problem (QAP) [START_REF] Koopmans | Assignment Problems and the Location of Economic Activities[END_REF][START_REF] Lawler | The quadratic assignment problem[END_REF][START_REF] Lawler | Combinatorial Optimization: Networks and Matroids[END_REF][START_REF] Loiola | A survey for the quadratic assignment problem[END_REF][START_REF] Burkard | Assignment Problems[END_REF]. QAPs are NP-hard and so different relaxation algorithms have been proposed to find an approximate solution, such as Integer Projected Fixed Point (IPFP) [START_REF] Leordeanu | An integer projected fixed point method for graph matching and map inference[END_REF], or Graduated NonConvexity and Concavity Procedure [START_REF] Liu | GNCCP -Graduated Nonconvexity and concavity procedure[END_REF]. Even if computing the GED is generally not equivalent to solving a graph matching problem, it should also be formalized as a QAP. To the best of our knowledge, this aspect has only been considered through the definition of fuzzy paths by [START_REF] Neuhaus | A quadratic programming approach to the graph edit distance problem[END_REF]. Thus, the strong relationships between the GED and the QAP have not yet been analyzed.

In this paper, we extend the LSAP with insertions and removals [START_REF] Riesen | Bipartite graph matching for computing the edit distance of graphs[END_REF][START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF] to a quadratic one. First, preliminary results concerning edit paths are established (Section 2), allowing to formalize the relation between the LSAP (Section 3) or the QAP (Section 4), and such paths. In particular, we show that the GED is a QAP when graphs are simple. Then, we propose an improved IPFP algorithm adapted to the minimization of quadratic functionals to approximate the GED (Section 5). The approach, validated through experiments in Section 6, generally provides a more accurate approximation of the exact GED than the bipartite GED, with a computational cost still affordable for graphs of non trivial sizes.

Preliminaries

This section introduces some basics about graphs, graph edit distance and edit paths. We futher introduce different familly of edit paths and show that one of this familly is in direct correspondence with a familly of mapping functions between the set of nodes of two graphs.

Graph Basics

Definition 1 (Unlabeled graph) An unlabeled graph G is defined by the couple G = (V, E) where V is the set of nodes and E ⊆ V × V is the set of edges. Each edge is an orded couple of nodes (i, j) with i, j ∈ V . The direction of an edge is implicitly given by the order of its nodes, i.e. the direction of (i, j) is from i to j.

Definition 2 (Nodes Adjacency) Given a graph G = (V, E) and two nodes i, j ∈ V . i and j are said to be adjacent iff ∃(i, j) ∈ E. Definition 3 (Unlabeled simple graph) An unlabeled graph is said to be simple iff:

1. It exists at most one edge between any pair of nodes, 2. The graph does not contain self loops ((i, i) ∈ E, ∀i ∈ V ) Definition 4 (Labeled simple graph) Let L be a finite alphabet of node and edge labels. A labeled simple graph is a tuple G = (V, E, µ, ν) where

• the couple (V, E) defines an unlabeled simple graph,

• µ : V → L is a node labeling function, • ν : E → L is an edge labeling function.
The unlabeled graph associated to a given labeled graph G = (V, E, µ, ν) is defined by the couple (V, E).

In the following we will only consider simple graphs that we will simply denote by unlabeled (resp. labeled) graphs. The term graph will denote indifferently a labeled or an unlabeled graph.

Definition 5 (Undirected graph)

• A simple graph G = (V, E) is said to be undirected iff ∀(i, j) ∈ E ∃(j, i) ∈ E. • A labeled simple graph G = (V, E, µ, ν) is said to be undirected iff ∀(i, j) ∈ E ∃(j, i) ∈ E ∧ ν(i, j) = ν(j, i).
Definition 6 (Bipartite graph) A graph G, labeled or not, is said to be bipartite iff

∃V 1 , V 2 ⊆ V : ∀(i, j) ∈ E, (i ∈ V 1 ∧ j ∈ V 2 ) ∨ (i ∈ V 2 ∧ j ∈ V 1 ).
Definition 7 (Subgraph)

• An unlabeled graph G 1 = (V 1 , E 1 ) is said to be an unlabeled subgraph of G 2 = (V 2 , E 2 ) if V 1 ⊆ V 2 and E 1 ⊆ E 2 ∩ (V 1 × V 1 ). The unlabeled subgraph G 1 is called an unlabeled proper subgraph if V 1 = V 2 or E 1 = E 2 . • If G 1 = (V 1 , E 1 , µ 1 , ν 1 ) and G 2 = (V 2 , E 2 , µ 2 , ν 2 ) are both labeled graphs then G 1 is a (proper) subgraph of G 2 if (V 1 , E 1
) is an unlabeled (proper) subgraph of (V 2 , E 2 ) and if the following additional constraint is fulfilled:

µ 2|V 1 = µ 1 and ν 2|E 1 = ν 1
, where f | denotes the restriction of function f to a particular domain.

• A structural subgraph of a labeled graph G is an unlabeled subgraph of the unlabeled graph associated to G.

Edit operations, paths, and distance

Definition 8 (Elementary edit operations) An elementary edit operation is one of the following operation applied on a graph:

• Node/Edge removal. Such removals are defined as the removal of the considered element from sets V or E.

• Node/Edge insertion. On labeled graphs, a vertex/edge insertion also associates a label to the inserted element.

• Node/Edge substitution if the graph is a labeled one. Such an operation modifies the label of a node or an edge and thus transforms the node or edge labeling functions.

Definition 9 (Cost of an elementary edit operation) Each elementary operation x is associated to a cost encoded by a specific function for each type of operation:

• Node (c vd (x)) and edge removal (c ed (x))

• Node (c vi (x)) and edge (c ei (x)) insertion,

• Node (c vs (x)) and edge (c es (x)) substitution on labeled graphs.

By extension, we will consider that functions c vd and c vi (resp. c ed and c ei ) apply on the set of nodes (resp. the set of edges) of a graph. Hence, the cost c vd (v) denotes the cost of removing node v.

We assume that a substitution transforming one label into the same label has zero cost:

∀l ∈ L, c vs (l → l) = c es (l → l) = 0
where l → l ′ denotes the substitution of label l into l ′ on some edge or node.

Definition 10 (Edit path) An edit path of a graph G is a sequence of elementary operations applied on G, where node removal and edge insertion have to satisfy the following constraints:

1. A node removal implies a first removal of all its incident edges,

2. An edge insertion can be applied only between two existing or already inserted nodes.

3. Edge insertions should not create more than one edge between two vertices nor create self-loops.

An edit path that transforms a graph G 1 into a graph G 2 is an edit path of G 1 whose last graph is G 2 . If G 1 and G 2 are unlabeled we assume that no node nor edge substitutions are performed.

Definition 11 (Cost of an edit path) The cost of an edit path P , denoted γ(P ) is the sum of the costs of its elementary edit operations.

Definition 12 (Edit distance)

The edit distance from a graph G 1 to a graph G 2 is defined as the minimal cost of all edit paths from G 1 to G 2 .

d(G 1 , G 2 ) = min P ∈P(G1,G2) γ(P )
where P(G 1 , G 2 ) is the set of all edit paths transforming G 1 into G 2 . An edit path from G 1 to G 2 with a minimal cost is called an optimal path.

Proposition 1 Given any graph G, and any edit path P of G, the transformation of G by P is still a simple graph.

Proof: Let G = (V, E, µ, ν) and G ′ = (V ′ , E ′ , µ ′ , ν ′ ) denote the initial graph and its transformation by P . Since the insertion of nodes and edges induces the definition of their labels, function µ ′ (resp. ν ′ ) defines a valid labeling function over V ′ (resp. E ′ ).

Let us consider (u, v) ∈ E ′ . Vertices u and v should either be present in V or have been inserted before the insertion of edge (u, v) (Definition 10, condition 2). Moreover, none of these nodes can be removed after the last insertion of edge (u, v) since such a removal would imply the removal of (u, v) (Definition 10, condition 1). Both u and v thus belong to V ′ . Hence E ′ ⊆ V ′ × V ′ . Moreover, according to Definition 10, condition 3 the edge (u, v) can not be inserted if it already exists in G and u = v. It follows that G ′ = (V ′ , E ′ , µ ′ , ν ′ ) is a labeled simple graph according to Definition 4.

Definition 13 (Independent edit path) An independent edit path between two labeled graphs G 1 and G 2 is an edit path such that:

1. No node nor edge is both substituted and removed, 2. No node nor edge is simultaneously substituted and inserted, 3. Any inserted element is never removed, 4. Any node or edge is substituted at most once, Note that an independent edit path is not minimal in the number of operations. Indeed, Definition 13 still allows to replace one substitution by one removal followed by one insertion (but such an operation can be performed only once for each node or edge thanks to condition 3). We however forbid useless operations such as the substitution of one node followed by its removal (condition 1) or the insertion of a node with a wrong label followed by its substitution (condition 2).

In the following we will only consider independent edit paths that we simply call edit paths.

Proposition 2

The elementary operations of an independent edit path between two graphs G 1 and G 2 may be ordered into a sequence of removals, followed by a sequence of substitutions and terminated by a sequence of insertions.

Proof: Let R, S and I denote the sub-sequences of Removals, Substitutions and Insertions of an edit path P , respectively. Since no removal may be performed on a substituted element (condition 1 of Definition 13) and no removal may be performed on an inserted element (condition 3), removals only apply on elements which are neither substituted nor inserted. Such removals operations may thus be grouped at the beginning of the edit path. Now, since an element cannot be substituted after its insertion, substitutions can only apply on the remaining elements after the removal step and can be grouped after the removal operations. The remaining operations only contain insertions.

Let us consider the sequence of elementary operations (R, S, I) the order within sequences R, S and I being deduced from the one of P . Such a sequence may be defined since operations in R apply on elements not in S and I while operations in S do not apply on the same elements than operations in I. Such sets are independent, leading to the definition of independent edit paths. However, we still have to show that the sequence (R, S, I) defines a valid edit path.

1. Since R contains all the removal operations contained in P , if P satisfies condition 1 of Definition 10, so does the sequence R.

2. Let us suppose that an edge insertion is valid in sequence P while it violates Definition 10, condition 2 in sequence (R, S, I). Let us denote by (u, v) such an edge. Edge (u, v) violates condition 2 in sequence (R, S, I) only if either the removal of u or v belongs to R. In such a case the insertion of (u, v) in P should be made before the removal of u or v. But such a removal would imply the removal of all the incident edges of u or v (Definition 10, condition 1) including the newly inserted edge (u, v). Such an operation would violate the independence of P (Definition 13, condition 3).

The sequence (R, S, I) is thus a valid edit path which transforms a graph G 1 into G 2 if P do so. Furthermore, it is readily seen that all the conditions of Definition 13 are satisfied by the sequence (R, S, I) as soon as they are satisfied by P . The sequence (R, S, I) is thus an independent edit path.

Proposition 3 Let P be an edit path between two graphs G 1 and G 2 . Let us further denote by R, S and I the sequence of node and edge Removals, Substitutions and Insertions performed by P , the order in each sequence being deduced from the one of P . Then:

• the graph Ĝ1 obtained from G 1 by applying removal operations R is a subgraph of G 1 ,
• the graph Ĝ2 obtained from G 1 by applying the sequence of operations (R, S) is a subgraph of G 2 ,

• Both Ĝ1 and Ĝ2 correspond to a same common structural subgraph of G 1 and G 2 .

Proof:

1. Since the sequence R is an edit path, Ĝ1 is a graph by Proposition 1. Moreover, since R is only composed of removal operations, we trivially have V1 ⊂ V 1 and Ê1 ⊂ E 1 .

The fact that Ê1 ⊂ E 1 ∩ V1 × V1 is induced by the fact that Ĝ1 is a graph. Moreover, if G 1 is a labeled graph, since removal operations do not modify labels, labels on Ĝ1 are only the restriction of the ones on G 1 to V1 and Ê1 .

2. The graph Ĝ2 is deduced from G 1 by the edit path (R, S), it is thus a graph. Moreover, G 2 is deduced from Ĝ2 by the sequence of insertions I. We thus trivially have: V2 ⊂ V 2 and Ê2 ⊂ E 2 ∩ V2 × V2 . Moreover, since insertion operations do not modify the label of existing elements, the restriction of the label functions of G 2 to V2 and Ê2 corresponds to the label functions of Ĝ2 .

3. Sub graph Ĝ2 is deduced from Ĝ1 by the sequence of substitution operations S. Since substitution operations only modify label functions, the structure of both graphs is the same and there exists a structural isomorphism between both graphs.

One should note that it may exist several structural isomorphisms between Ĝ1 and Ĝ2 . The set of substitutions S fixes one of them, say f such that the image of any element of Ĝ1 by f have the same label than the one defined by the substitution. More precisely, let us suppose that we enlarge the set of substitution S by 0 cost substitutions so that all the nodes and edges of Ĝ1 = ( V1 , Ê1 , µ 1 , ν 1 ) are substituted. In this case, we have:

∀v ∈ V1 , µ 2 (f (v)) = l v ∀e ∈ Ê1 , ν 2 (f (e)) = l e
where l v and l e correspond to the labels defined by the substitutions of v and e and µ 2 and ν 2 define respectively the node and edge labeling functions of G 2 .

Corollary 1 Using the same notations than in Proposition 3, the cost γ(P ) of an edit path is defined by:

γ(P ) = v∈V1\ V1 c vd (v) + e∈E1\ Ê1 c ed (e) + v∈ V1 c vs (v) + e∈ Ê1 c es (e) + v∈V2\ V2 c vi (v) + e∈E2\ Ê2 c ei (e)
Proof: The edit path P and its rewriting in (R, S, I) have the same set of operations and thus a same cost.

From G 1 to Ĝ1 : Operations in R remove nodes in V 1 \ V1 and edges in E 1 \ Ê1 .

From Ĝ1 to Ĝ2 : Substitutions of S apply between the two graphs Ĝ1 and Ĝ2 . Let us consider the set of substitutions S ′ which corresponds to the completion of S by 0 cost substitutions so that all nodes and edges of Ĝ1 are substituted. Both S and S ′ have a same cost. The cost of S ′ is defined as the sum of costs of the substituted nodes and edges of Ĝ1 .

From Ĝ2 to G 2 : Operations in I insert nodes of V 2 \ V2 and edges of E 2 \ Ê2 in order to obtain G 2 from Ĝ2 .

Remark 1 Using the same notations than Proposition 3 if both G 1 and G 2 are undirected we have:

γ(P ) = γ v (P ) + γ e (P )
with

γ v (P ) = i∈V1\ V1 c vd (i) + i∈ V1 c vs (i) + k∈V2\ V2 c vi (k) γ e (P ) = 1 2   (i,j)∈ Ê1
c es ((i, j))

+ (i,j)∈E1\ Ê1 c ed ((i, j)) + (k,l)∈E2\ Ê2 c ei ((k, l))  
Indeed, if both graphs G 1 and G 2 are undirected both (i, j) and (j, i) belong to E 1 while encoding a single edge e. The removal or the substitution of the edge e is thus counted twice in γ e (P ). In the same way (k, l) and (l, k) represent the same edge e of E 2 \ Ê2 which is thus inserted twice in γ e (P ). The factor 1 2 of γ e (P ) removes this double couting of edge operations.

Corollary 2 If all costs do not depend on the node/edge involved in the operations, i.e. edit cost functions c vd , c ed , c vs , c es , c vi , and c ei are constant, the cost of an edit path P is equal to:

γ(P ) = (|V 1 | -| V1 |)c vd + (|E 1 | -| Ê1 |)c ed + V f c vs + E f c es + (|V 2 | -| V2 |)c vi + (|E 2 | -| Ê2 |)c ei
where V f (resp. E f ) denotes the number of nodes (resp. edges) substituted with a non-zero cost.

Moreover, minimizing the cost of such an edit path is equivalent to maximizing the following formula:

M (P ) def. = | V1 |(c vd + c vi ) + | Ê1 |(c ed + c ei ) -V f c vs -E f c es Proof:
We deduce immediately from Corollary 1 the following formula:

γ(P ) = (|V 1 | -| V1 |)c vd + (|E 1 | -| Ê1 |)c ed + V f c vs + E f c es + (|V 2 | -| V2 |)c vi + (|E 2 | -| Ê2 |)c ei
We obtain by grouping constant terms:

γ(P ) = |V 1 |c vd + |E 1 |c ed + |V 2 |c vi + |E 2 |c ei -| V1 |c vd + | Ê1 |c ed + | V2 |c vi + | Ê2 |c ei -V f c vs -E f c es
Since there is a structural isomorphism between Ĝ1 and Ĝ2 , we have V1 = V2 and Ê1 = Ê2 . So:

γ(P ) = |V 1 |c vd + |E 1 |c ed + |V 2 |c vi + |E 2 |c ei -| V1 |(c vd + c vi ) + | Ê1 |(c ed + c ei ) -V f c vs -E f c es
The first part of the above equation being constant, the minimization of γ(P ) is equivalent to the maximization of the last part of the equation. Definition 14 (Restricted edit path) A restricted edit path is an independent edit path in which any node or any edge cannot be removed and then inserted.

The term restricted should be understood as minimal number of operations. The cost of a restricted edit path may not be minimal (among all edit paths) if the cost of a removal operation followed by an insertion is lower than the cost of the associated substitution. However, such a drawback may be easily solved by setting a new substitution cost equal to the minimum between the old substitution cost and the sum of the costs of a removal and an insertion. In this case all non-zero cost substitutions, for nodes and edges, may be equivalently replaced by a removal followed by an insertion.

Proposition 4 If G 1 and G 2 are simple graphs, there is a one-to-one mapping between the set of restricted edit paths between G 1 and G 2 and the set of injective functions from a subset of V 1 to V 2 . We denote by ϕ 0 , the special function from the empty set onto the empty set.

Proof: Let P denote an edit path. If no node substitution occurs, all node of G 1 are first removed and then all nodes of G 2 are inserted. We associate this edit path to ϕ 0 .

If substitutions occur. We associate to P the function previously mentioned which maps each substituted node of V 1 onto the corresponding node of G 2 .

Let ψ denotes this mapping. Let us consider an injective function f = ϕ 0 from a set V1 ⊂ V 1 onto V 2 . We associate to f the sets of node

• removals: c vd (v → ǫ), v ∈ V 1 -V1 , • insertions: c vi (ǫ → v), v ∈ V 2 -f ( V1 )
, and

• substitutions: c vs (v → f (v)), v ∈ V1 .
Moreover, since G 1 and G 2 are simple graphs it exists at most one edge between any pair of nodes. We thus define the following set of edge operations:

• removals: c ed ((i, j) → ǫ) such that i or j does not belong to V1 or (f (i), f (j)) do not belongs to E 2 , • insertions c ei (ǫ → (k, l)) such that k or l does not belong to f ( V1 ) or (f -1 (k), f -1 (l)) do not belongs to E 1 , • substitutions c es ((i, j) → (f (i), f (j))), (i, j) ∈ ( V1 × V1 ) ∩ E 1 and (f (i), f (j))) ∈ E 2 .
Let us denote respectively by R, S and I the set of removals/substitutions/insertions defined both on node and edges. The sequence (R, S, I) defines a valid restricted edit path whose image by ψ is by construction equal to f . The function ψ is thus surjective. Let us consider two different edit paths P = (R, S, I) and P ′ = (R ′ , S ′ , I ′ ). Then:

• If R = R ′ .
If node removals are not equal, ψ(P ) and ψ(P ′ ) are not defined on the same set and are consequently not equal. Otherwize, let us suppose that an edge (i, j) is removed in P and not in P ′ . Let us further suppose that ψ(P )(i) = ψ(P ′ )(i) and ψ(P )(j) = ψ(P ′ )(j). Since (i, j) is not removed in P ′ we have (ψ(P )(i), ψ(P )(j)) = (ψ(P ′ )(i), ψ(P ′ )(j)) ∈ E 2 . The edge (i, j) should thus be first removed and then inserted in P which contradicts the definition of a restricted edit path. Therefore, one of the two following conditions should holds:

1. ψ(P )(i) = ψ(P ′ )(i) or ψ(P )(j) = ψ(P ′ )(j),
2. the set of edge removal operations is the same in P and P ′ .

If the first condition holds ψ(P ) = ψ(P ′ ). If the second condition holds, since R = R ′ , the set of node removals is different in P and P ′ . In this case we get also ψ(P ) = ψ(P ′ ).

• If S = S ′ . Node substitutions are different if they are either defined on different sets or do not correspond to the same node mapping. In both cases, ψ(P ) = ψ(P ′ ). If node substitutions are identical but if S and S ′ differ by the edge substitutions, an edge of G 1 is substituted by P and P ′ to an edge of G 2 with two different labels.

Since an edge may be substituted at most once in an independent edit path, either P or P ′ is not a valid edit path between G 1 and G 2 . Hence S and S ′ differ only if their node substitutions differ, in which case we have ψ(P ) = ψ(P ′ ).

• If I = I ′ (with R = R ′ and S = S ′ ). If a node k ∈ V 2 is inserted by I but not by I ′ ,
this means that k is substituted by S ′ . Hence we contradict S = S ′ . In the same way, if an edge (k, l) ∈ E 2 is inserted by I and not by I ′ , (k, l) is substituted by S ′ but not by S. We again contradict S = S ′ .

Note that the last item of the previous decomposition shows (as a side demonstration) that given the initial and final graphs, a restricted edit path is fully defined by its set of removals and substitutions. Moreover, if the set of removals or substitutions of two restricted edit paths differ, then the associated mapping is different. The function ψ is thus injective and hence bijective.

Proposition 5 Let P be a restricted edit path not associated with ϕ 0 (hence with some substitutions). Let us denote by ϕ : V1 → V 2 the injective function associated to P and let us denote ϕ( V1 ) by V2 . We further introduce the following two sets:

R 12 = {(i, j) ∈ E 1 ∩ ( V1 × V1 ) | (ϕ(i), ϕ(j)) ∈ E 2 } I 21 = {(k, l) ∈ E 2 ∩ ( V2 × V2 ) | (ϕ -1 (k), ϕ -1 (k)) ∈ E 1 }
• The set of substituted/removed/inserted nodes by P are respectively equal to:

V1 , V 1 \ V1 and V 2 \ V2 .
• The set of edges substituted/removed/inserted by P are respectively equal to:

-Substituted: Ê1 = E 1 ∩ ( V1 × V1 ) \ R 12 with Ê2 = ϕ( Ê1 ) = E 2 ∩ ( V2 × V2 ) \ I 21 -Removed: E 1 \ Ê1 = E 1 ∩ ((V 1 \ V1 ) × V 1 ) ∪ (V 1 × (V 1 \ V1 )) ∪ R 12 -Inserted: E 2 \ Ê2 = E 2 ∩ ((V 2 \ V2 ) × V 2 ) ∪ (V 2 × (V 2 \ V2 )) ∪ I 21
Proof: Node substitions/removal/insertions are direct consequences of the proof of Proposition 4 and the bijective mapping between injective functions from a subset V1 ⊂ V 1 onto V 2 and restricted edit paths.

• If (i, j) ∈ Ê1 , {ϕ(i), ϕ(j)} ⊂ V2 and (ϕ(i), ϕ(j)) ∈ E 2 .
Since (i, j) cannot be removed and then inserted it must be substituted. Conversely, if (i, j) ∈ E 1 is substituted, i an j must be substituted ({i, j} ⊂ V1 ). Moreover, the edge (ϕ(i), ϕ(j)) should exists in E 2 . Hence (i, j) ∈ R 12 and (i, j) ∈ Ê1 .

If (k, l) ∈ Ê2 = ϕ( Ê1 ), it exits (i, j) ∈ E 1 such that k = ϕ(i) and l = ϕ(j). Hence (k, l) ∈ I 21 . Since (i, j) ∈ R 12 , (k, l) ∈ E 2 and {k, l} ⊂ V2 . Hence (k, l) ∈ ϕ( Ê1 ) = E 2 ∩ ( V2 × V2 ) \ I 21 . Conversely, if (k, l) ∈ E 2 ∩ ( V2 × V2 ) \ I 21 , it exits (i, j) such that k = ϕ(i) and l = ϕ(j) ({k, l} ∈ V2 ). Since (k, l) ∈ E 2 \ I 21 we have (i, j) ∈ E 1 \ R 12 .
Finally, {k, l} ⊂ V2 implies that {i, j} ⊂ V1 hence (i, j) ∈ Ê1 and (k, l) ∈ Ê2 = ϕ( Ê1 ).

• Any non substited edge of G 1 must be removed. Hence, the set of removed edges is equal to E 1 \ Ê1 . The remaining equation, is deduced by a negation of the conditions defining Ê1 .

• In the same way, any edge of G 2 which is not produced by a substitution of an edge of G 1 must be inserted. Hence, the set of inserted edges is equal to E 2 \ Ê2 . The negation of the condition defining Ê2 provides the remaining equation.

Linear and quadratic assignment problems

Within this report, an assignment corresponds to a bijective mapping ϕ : X →Y between two finite sets X and Y having the same size |X | = |Y| = n. When these sets are reduced to the same set of integers, i.e. X = Y = {1, . . . , n}, the bijection ϕ reduces to the permutation (ϕ(1), . . . , ϕ(n)). Any permutation ϕ can be represented by a n × n permutation matrix X = (x i,j ) i,j=1,...,n with

x i,j = 1 if j = ϕ(i) 0 else (2)
More generally, recall that a permutation matrix is defined as follows.

Definition 15 (Permutation Matrix) A n × n matrix X is a permutation matrix iff it satisfies the following contraints:

                 ∀j = 1, . . . , n, n i=1 x i,j = 1 ∀i = 1, . . . , n, n j=1 x i,j = 1 ∀i, j = 1, . . . , n, x i,j ∈ {0, 1} (3)
These constraints ensure X to be binary and doubly stochastic (sum of rows and sum of columns equal to 1).

The selection of a relevant assignment, among all possible ones from X to Y, depends on the problem. Nevertheless, each assignment is commonly penalized by a cost, and a relevant assignment becomes one having a minimal or a maximal cost. In this report, we consider minimal costs only. The cost of an assignment is usually defined as a sum of elementary costs. An elementary cost may penalize the assignment of an element of X to an element of Y, or the simultaneaous assignment of two elements i and j of X to two elements k and l of Y, respectively. Definition 16 (Linear Sum Assignment Problem (LSAP)) Let C ∈ [0, +∞) n×n be a matrix such that c i,j corresponds to the cost of assigning the element i ∈ X to the element j ∈ Y. The Linear Sum Assignment Problem (LSAP) consists in finding an optimal permutation

φ ∈ argmin n i=1 c i,ϕ(i) | ϕ ∈ S n (4)
where S n is the set of all permutations of {1, . . . , n}. Equivalently, the LSAP consists in finding an optimal n × n permutation matrix

X ∈ argmin    n i=1 n j=1 c i,j x i,j | X satisfies Eq. 3    . (5)
Let c = vec(C) ∈ [0, +∞) n 2 be the vectorization of the cost matrix C, obtained by concatenating its rows. Similarly, let x = vec(X) ∈ {0, 1} n 2 be the vectorization of X. Then, the LSAP consists in finding an optimal vector

x ∈ argmin c T x | Lx = 1 2n , x ∈ {0, 1} n 2 , (6)
where the linear system Lx = 1 is the matrix version of the constraints defined by Eq. 3.

The matrix L ∈ {0, 1} 2n×n 2 represents the node-edge incidence matrix of the complete bipartite graph K n,n with node sets X and Y:

l i,(j,k) = 1 if (j = i) ∨ (k = i) 0 else (7)
The system Lx = 1, together with the binary constraint on x, selects exactly one edge of K n,n for each element of X ∪ Y. In other terms, these constraints represent a subgraph of K n,n , with node sets X and Y, such that each node has degree one. Indeed, the LSAP is a weighted bipartite graph matching problem. More details on the LSAP can be found in [START_REF] Sierksma | Linear and Integer Programming: Theory and Practice[END_REF][START_REF] Burkard | Assignment Problems[END_REF]. In particular, Eq. 6 is a binary linear programming problem, efficiently solvable in polynomial time complexity, for instance with the Hungarian algorithm [START_REF] Kuhn | The hungarian method for the assignment problem[END_REF][START_REF] Munkres | Algorithms gor the assignment and trasportation problems[END_REF][START_REF] Lawler | Combinatorial Optimization: Networks and Matroids[END_REF] combined with pre-processing steps [START_REF] Jonker | A shortest augmenting path algorithm for dense and sparse linear assignment problems[END_REF]. In our experiments, we have used the O(n 3 ) (time complexity) version of the Hungarian algorithm proposed in [START_REF] Lawler | Combinatorial Optimization: Networks and Matroids[END_REF][START_REF] Burkard | Assignment Problems[END_REF].

Problems that incorporate pairwise constraints, i.e. simultaneously assigning two elements of X to two elements of Y, can be cast as a quadratic assignment problem [START_REF] Koopmans | Assignment Problems and the Location of Economic Activities[END_REF][START_REF] Lawler | The quadratic assignment problem[END_REF][START_REF] Lawler | Combinatorial Optimization: Networks and Matroids[END_REF][START_REF] Loiola | A survey for the quadratic assignment problem[END_REF][START_REF] Burkard | Assignment Problems[END_REF]. This is the case for the graph matching problem, and for the GED as demonstrated in Section 4. In this paper, we consider the general expression of quadratic assignment problems [START_REF] Lawler | The quadratic assignment problem[END_REF].

Definition 17 (Quadratic Assignment Problem (QAP)) Let D ∈ [0, +∞) n 2 ×n 2 be a matrix such that d ik,jl corresponds to the cost of simultaneously assigning the elements i and j of X to the elements k and l of Y, respectively. The quadratic assignment problem (QAP) consists in finding an optimal permutation

φ ∈ argmin    n i=1 n j=1 d iϕ(i),jϕ(j) | ϕ ∈ S n    . (8)
Equivalently, the QAP consists in finding an optimal n × n permutation matrix

X ∈ argmin    n i=1 n k=1 n j=1 n l=1 d ik,jl x i,k x j,l | X satisfies Eq. 3    . Note that i ∈ X is assigned to k ∈ Y, and j ∈ X is assigned to l ∈ Y, simultaneously iff x i,k = x j,l = 1.
The QAP can be rewritten as a quadratic program:

argmin x T Dx | Lx = 1 2n , x ∈ {0, 1} n 2
where x is the vectorization of X, and the right-hand side is the matrix version of the constraints defined by Eq. 3.

The quadratic term is able to incorporate a linear one. Indeed, any simultenous assignment of the same element i ∈ X to the same element k ∈ Y is penalized by the cost d ik,ik , i.e. a diagonal element of D. Since x i,k ∈ {0, 1}, we have d ik,ik x i,k x i,k = d ik,ik x i,k . Then the total contribution of diagonal elements to the quadratic cost is given by

n i=1 n k=1 d ik,ik x i,k = diag(D) T x
where diag denotes the diagonal vector. So, if diag(D) = 0, the quadratic functional incorporates a linear term which decribes the linear sum assignment between the elements of X and Y. When these constraints are also part of the underlying problem, it is sometimes more convenient to rewritte the QAP as

argmin x T Dx + c T x | Lx = 1 2n , x ∈ {0, 1} n 2 (9)
where diag(D) = 0, and c is the cost of assigning each element of X to each element of Y.

As the GED, the QAP is in general NP-hard, and exact algorithms can only be used with sets of small cardinality [START_REF] Burkard | Assignment Problems[END_REF]. Indeed, the cost functional is generally not convex, and methods based on relaxation and linearization are usually considered to find an approximate solution. See Section 5 for more details.

Bipartite Graph Edit Distance

As already mentionned, the GED can be challenging to compute, even on small graphs. In order to deal with such a complexity, several methods approximate the GED by computing an optimal linear sum assignment between the nodes of the two graphs to be compared. This is formalized through the definition of a specific LSAP [START_REF] Riesen | Bipartite graph matching for computing the edit distance of graphs[END_REF][START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF] that takes into account edit operations, as described in this section. In particular, we show in Section 3.1 that there is a one-to-one relation between restricted edit paths and assignment matrices.

Edit operations, assignments and restricted edit paths

Let X and Y be two finite sets, with |X | = n and |Y| = m. Without loss of generality, we assume that X = {1, . . . , n} and Y = {1, . . . , m}. Each element of X can be assigned to an element of Y. Such a mapping represents a possible substitution. Also each element of X can be removed, and each element of Y can be inserted into X . In order to represent insertions, X is augmented by m dummy elements E X = {ǫ 1 , . . . , ǫ m }, such that j ∈ Y can only be inserted into Y by assiging ǫ j to j. Similarly, the set Y is augmented by n dummy elements E Y = {ǫ 1 , . . . , ǫ n }, such that i ∈ X is removed by assigning it to ǫ i . In other terms, it is not possible to assign an element i ∈ X to an element ǫ k ∈ E Y with k = i, and similarly any assignment from ǫ j ∈ E X to k ∈ Y with k = j is forbidden.

Let X ǫ = X ∪ E X and Y ǫ = Y ∪ E Y be the two augmented sets, which thus have the same size n + m. We assume without loss of generality that symbols ǫ i and ǫ j represent integers, i.e. E X = {n + 1, . . . , n + m} and E Y = {m + 1, . . . , m + n}. It is now possible to define assignments that take into account removal, substitution, and insertion of elements.

Definition 18 (ǫ-assignment) An ǫ-assignment from X to Y is a bijective mapping ψ : X ǫ → Y ǫ , here a permutation, such that for each element of X ǫ one of the four following cases occurs:

1. Substitutions: ψ(i) = j with (i, j) ∈ X × Y.

Removals:

ψ(i) = ǫ i with i ∈ X .
3. Insertions: ψ(ǫ j ) = j with j ∈ Y.

4. Finally ψ(ǫ j ) = ǫ i allow to complete the bijective property of ψ, and thus should be ignored. This occurs when i ∈ X and j ∈ Y are both substituted.

Let Ψ ǫ (X , Y) be the set of all ǫ-assignments from X to Y.

In other terms, an ǫ-assignment is a bijection (or permutation) with additional constraints.

The corresponding (n + m) × (m + n) permutation matrix can be decomposed as follows:

X = 1 • • • m ǫ 1 • • • ǫ n               1 X sub X rem . . . n ǫ 1 X ins X ǫ . . . ǫ m (10)
where matrix X sub ∈ {0, 1} n×m encodes node substitutions, X rem ∈ {0, 1} n×n encodes node removals, and X ins ∈ {0, 1} m×m encodes node insertions. Matrix X ǫ ∈ {0, 1} m×n is an auxiliary matrix (case 4 above), it ensures that X is a permutation matrix. Due to the constraints on dummy nodes (cases 2 and 3 above) matrices X rem and X ins always satisfy:

∀(i, j) ∈ {1, . . . , n} 2 , i = j, x rem i,j = 0 ∀(i, j) ∈ {1, . . . , m} 2 , i = j, x ins i,j = 0. The auxiliary matrix X ǫ in Eq. 10 suggests the definition of an equivalence relation between ǫ-assignment matrices.

Definition 20 Two ǫ-assignment matrices X 1 and X 2 , defined by the two sequences of block matrices

(X sub 1 , X rem 1 , X ins 1 , X ǫ 1 ) and (X sub 2 , X rem 2 , X ins 2 , X ǫ 2 ), are equivalent iff (X sub 1 = X sub 2 ) ∧ (X rem 1 = X rem 2 ) ∧ (X ins 1 = X ins 2 )
. The set of ǫ-assignment matrices up to this equivalence relation is denoted by A ∼ n,m . Proposition 6 There is a one-to-one relation between A ∼ n,m and the set of injective functions from a subset of X to Y.

Proof: Recall that X = {1, . . . , n} and Y = {1, . . . , m}. Let X = (X sub , X rem , X ins , X ǫ ) = (Q, R, S, T) denote an ǫ-assignment matrix. If Q = 0 we associate to X the application ϕ 0 from the empty set onto itself (Proposition 4). Otherwise, let us introduce the set:

X = {i ∈ X | ∃j ∈ Y, q i,j = 1}
Since X is a permutation matrix, for any i ∈ X there is exactly one j ∈ Y such that q i,j = 1. We can thus define the mapping:

ϕ X X → Y i → j
Moreover if ϕ X (i 1 ) = ϕ X (i 2 ) then we have q i1,j = q i2,j = 1. Since X is a permutation matrix, such a case is possible only if i 1 = i 2 , and ϕ X is thus injective. We can thus associate to each assignement matrix an injective function ϕ X from a subset of X to Y. We denote by χ this mapping. We have to show that χ is bijective. Consider an injective mapping ϕ from a subset X onto Y. If ϕ = ϕ 0 , we have χ(X) = ϕ 0 with X = (0 n×m , I n×n , I m×m , 0 m×n ). Otherwise, the sub-blocks of X are defined as follows:

q i,j = 1 iff ∃i ∈ X , with ϕ(i) = j, 0 else r i,i = 1 iff i ∈ X \ X 0 else s j,j = 1 iff j ∈ Y \ ϕ[ X ] 0 else
Note that off-diagonal elements of R and S are equal to 0 by definition of ǫ-assignement matrices (Eq. 11). By using the above definition, q i,j = 1 ⇒ r i,i = s j,j = 0. Hence, if T was filled with 0, the line corresponding to ǫ i ∈ Y ǫ (column m + i) and ǫ j ∈ X ǫ (row n + j) would be filled by 0 in X, which would thus not be an ǫ-assignment matrix. Moreover, since ϕ is injective, we have | X | = |ϕ[ X ]|. Hence the set of indices:

A = {(j, i) ∈ {1, . . . , m} × {1, . . . , n} | q i,j = 1}
defines a square submatrix of T, which can be defined as a permutation matrix on A and 0 elsewhere. Now we check that each row and column of X = (Q, R, S, T) contains exactly one value equal to 1.

For the rows:

• If i ∈ X , then ϕ(i) = j, q i,j = 1 and r i,i = 0. Moreover, since ϕ is an application, we have q i,j ′ = 0 for any j ′ ∈ Y \ {j}.

• If i ∈ X \ X , by definition q i,j = 0 for all j ∈ Y and r i,i = 1. There is thus a single 1 in row i.

• For j ∈ Y with s j,j = 1, by definition of S we have j ∈ Y \ ϕ[ X ], and thus ∀i ∈ X , q i,j = 0. Hence there is no i such that (j, i) ∈ A. By definition of T, its row j is filled with 0.

• For j ∈ Y with s j,j = 0, then j ∈ ϕ[X ] and it exists a unique i ∈ X such that q i,j = 1. Hence (j, i) ∈ A. Since T defines a permutation matrix on A, it should exists a unique k satisfying (j, k) ∈ A such that t j,k = 1. This value is unique on the row j of T by definition of T.

Hence for each element of X ǫ , there is a unique 1 on the corresponding row of X.

The proof for columns is similar. So there is a unique 1 value on each row and each column of X. Matrix X is thus a permutation matrix. Moreover, since elements of the blocks R and S are equal to 0 on off-diagonal indices, X is an ǫ-assignement matrix with χ(X) = ϕ, by construction.

The application χ is thus surjective. Let us show that it is also injective. To this end, we consider two non-equivalent assignement matrices X = (Q, R, S, T) and

X ′ = (Q ′ , R ′ , S ′ , T ′ ). • If Q = Q ′ ,
then we may suppose without loss of generality that there exists (i, j) ∈ X × Y such that q i,j = 1 and q ′ i,j = 0. Since q i,j = 1, i ∈ XX , where XX denotes the subset of X on which χ(X) is defined.

-If q ′ i,j ′ = 0 for all j ′ ∈ Y then i ∈ X \ XX ′ . Hence χ(X) and χ(X ′ ) are not defined on the same set and are consequently not equal.

-If it exists j ′ ∈ Y such that q ′ i,j ′ = 1 we have χ(X)(i) = j and χ(X ′ )(i) = j ′ . Applications χ(X) and χ(X ′ ) are consequently not equal.

• If R = R ′ we may suppose that it exists i ∈ X such that r i,i = 1 and r ′ i,i = 0. Hence i ∈ XX and i ∈ XX ′ . Applications χ(X) and χ(X ′ ) are not defined on the same set and are consequently not equal.

• If S = S ′ , let us consider j ∈ Y such that s j,j = 1 and s ′ j,j = 0. We have j ∈ χ(X)[ XX ] and j ∈ χ(X ′ )[ XX ′ ]. Applications χ(X) and χ(X ′ ) have different set of mappings and are consequently not equal.

Note that we do need to consider matrix T since this matrix is not implied in the equivalence relationship. In all cases application χ maps two non-equivalent ǫ-assignement matrices to different injective functions. The application χ is thus injective.

Application χ being both surjective and injective, it is bijective.

So, ǫ-assignment matrices on X ǫ and Y ǫ , and injective functions defined on a subset of X onto Y, are in one-to-one correspondence.

It is now possible to link ǫ-assignments to edit paths. Consider two simple graphs G 1 and G 2 , with node sets V 1 and V 2 respectively. An ǫ-assignment from V 1 to V 2 can be defined by constructing the sets V ǫ 1 and V ǫ 2 . According to the above proposition, there is a one-to-one correspondence between ǫ-assignment matrices on V ǫ 1 and V ǫ 2 , and injective functions defined on a subset of V 1 onto V 2 . By using Proposition 4, we can connect such a mapping to a restricted edit path between G 1 and G 2 (Definition 10). Up to the equivalence relation (Definition 20), there is thus a one-to-one correspondence between ǫ-assignment matrices and restricted edit paths.

This shows that restricted edit paths can be deduced from ǫ-assignments.

LSAP for ǫ-assignments

Let X = {1, . . . , n} and Y = {1, . . . , m} be two sets. These two sets are augmented by dummy elements as described in the previous section, i.e. X ǫ = X ∪ E X and Y ǫ = Y ∪ E Y . An ǫ-assignment from X to Y, i.e. a bijective mapping from X ǫ onto Y ǫ , represents a set of edit operations.

The selection of a relevant ǫ-assignment is realized through the design of a pairwise cost function adapted to edit operations. To this, each possible mapping of an element i ∈ X ǫ to an element j ∈ Y ǫ is penalized by a non-negative cost c i,j . All costs can be encoded by a (n + m) × (m + n) matrix (having the same structure as ǫ-assignment matrices) [START_REF] Riesen | Bipartite graph matching for computing the edit distance of graphs[END_REF][START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF]

C = 1 • • • m ǫ 1 • • • ǫ n               1 C sub C rem . . . n ǫ 1 C ins 0 m,n . . . ǫ m (12)
where the matrix C sub ∈ [0, +∞) n×m encodes substitution costs, C rem ∈ [0, +∞) n×n encodes removal costs, and C ins ∈ [0, +∞) m×m encodes insertion costs. According to cases 2 and 3 in Definition 18, off-diagonal values of C rem and C ins are typically set to a large value such that max{c i,ψ(i) | ∀i ∈ X ǫ , ∀ψ ∈ Ψ ǫ (X , Y)} ≪ ω < +∞, in order to avoid forbidden mappings. According to case 4 in Definition 18, the mapping of any ǫ i to an ǫ j should not induce any cost, so the last block of C is set to the null matrix 0 m,n . The cost of an ǫ-assignment ψ can then be measured by the sum (see Definition 18 for the decomposition)

n+m i=1 c i,ψ(i) = i∈ X c i,ψ(i) substitutions + i∈X \ X c i,ǫi removals + j∈Y-ψ[ X ] c ǫj ,j insertions . ( 13
)
where X = {i ∈ X | ∃j ∈ Y, ψ(i) = j}. An optimal ǫ-assignment is then defined as one having a minimal cost (several optimal ǫ-assignment may exist) among all ǫ-assignments:

ψ ∈ argmin n+m i=1 c i,ψ(i) | ψ ∈ Ψ ǫ (X , Y) (14)
which is a LSAP (Section 2.3). It can thus be rewritten as a binary programming problem (Eq. 6)

x

∈ argmin c T x | x ∈ vec[A ∼ n,m ] , (15)
where x = vec(X) ∈ {0, 1} (n+m) 2 is the vectorization of the ǫ-assignment matrix X associated with ψ (Eq. 10), c = vec(C) ∈ [0, +∞) (n+m) 2 is the vectorization of the cost matrix C, and vec[A ∼ n,m ] ⊂ {0, 1} (n+m) 2 is the set of all vectorized ǫ-assignment matrices. Note that, using equation 13, two equivalent ǫ-assignment matrices have a same cost.

The optimal solution of the LSAP defined by Eq. 15 can be computed by any algorithm that solves LSAPs, such as Hungarian-type algorithms. Note that mappings in Ψ ǫ , or matrices in A n,m , are much more constrained than bijective mappings or permutation matrices. These constraints, i.e. forbidden assignments, are satisfied in [START_REF] Riesen | Bipartite graph matching for computing the edit distance of graphs[END_REF][START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF] through the large ω values in the cost matrix. This is a classical trick used in LSAPs to avoid some specific assignments of elements [START_REF] Burkard | Assignment Problems[END_REF]. While these assignments are avoided, the corresponding large ω values are still treated by the algorithms. A better way to take into account the additionnal constraints would be to modify the algorithms such that forbidden assignments are not treated at all. This is the choice we made in our experimentations. This improves the time complexity.

Bipartite GED

It is now possible to define a framework to approximate the GED, based on ǫ-assignments and the corresponding LSAP [START_REF] Riesen | Bipartite graph matching for computing the edit distance of graphs[END_REF][START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF][START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF][START_REF] Gaüzère | Approximate Graph Edit Distance Guided by Bipartite Matching of Bags of Walks[END_REF][START_REF] Riesen | Improving bipartite graph edit distance approximation using various search strategies[END_REF]. Within this framework, a resulting approximate GED is called a bipartite GED.

Let G 1 and G 2 be two graphs, with node sets V 1 and V 2 respectively. The computation of a bipartite GED from G 1 to G 2 is performed in four main steps detailed below.

Step 1 -construction of the bags of patterns. For each node of each graph a bag of patterns is constructed. This bag represents a part of the graph connected to a specific node by some structured subgraphs, such as incident edges [START_REF] Riesen | Bipartite graph matching for computing the edit distance of graphs[END_REF][START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF], subtrees [START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF] or walks [START_REF] Gaüzère | Approximate Graph Edit Distance Guided by Bipartite Matching of Bags of Walks[END_REF]. A set of bags of patterns is then obtained for each graph. Let B 1 and B 2 be the ones associated to G 1 and to G 2 respectively. We have thus

|B 1 | = |V 1 | and |B 2 | = |V 2 |.
The idea is then to find an optimal ǫ-assignment from B 1 to B 2 , according to a given pairwise cost matrix.

Step 2 -construction of the cost matrix. Each possible mapping of a bag b i ∈ B 1 to a bag b j ∈ B 2 is penalized by a cost measuring the affinity between the two bags. This cost is initially defined as the cost of editing b i such that it is transformed into b j , i.e. the cost of an optimal ǫ-assignment of the elements of the two bags [START_REF] Riesen | Bipartite graph matching for computing the edit distance of graphs[END_REF][START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF][START_REF] Gaüzère | Approximate Graph Edit Distance Guided by Bipartite Matching of Bags of Walks[END_REF][START_REF] Riesen | Improving bipartite graph edit distance approximation using various search strategies[END_REF]. Also the bags of B 1 can be removed, and the bags of B 2 can be inserted into B 1 , which is penalized by a cost measuring the relevance of the bag. In order to approximate the GED, all theses costs depend on the original edit cost functions defined in Section 2.2. They are encoded by a cost matrix C (Eq. 12). Note that in this step |V 1 | × |V 2 | LSAP are solved for computing the costs of assigning bags of B 1 to bags of B 2 .

Step 3 -construction of an ǫ-assignment between the nodes. Given the cost matrix C computed in the previous step, an optimal ǫ-assignment from B 1 to B 2 is then computed by solving again a LSAP. The computed optimal assignment hence provides an optimal mapping ψ ∈

Ψ ǫ (V 1 , V 2 ).
Step 4 -construction of a restricted edit path. The ǫ-assignment ψ can be interpreted as a partial edit path between the graphs G 1 and G 2 . Indeed, it is only composed of edit operations involving nodes. Therefore this partial edit path has to be completed with edit operations applied on edges. This set of edit operations is directly induced by the set of edit operations operating on nodes, defined by the mapping computed in the previous step. The substitution, removal or insertion of any edge depends thus on the edit operations performed on its incident nodes. The cost of the complete edit path is finally defined by the sum of edit operations on nodes and edges. This cost only corresponds to an approximation of the GED between G 1 and G 2 since the mapping computed during Step 3 may not be optimal. Therefore, this cost corresponds to an overestimation of the exact GED, known as bipartite GED.

The definition of the cost matrix C in Step 2 is a keypoint of the framework. The initial approach proposed in [START_REF] Riesen | Bipartite graph matching for computing the edit distance of graphs[END_REF][START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF] defines bag of patterns as the corresponding node itself and its direct neighborhood, i.e. the set of incident edges and adjacent nodes. The cost of assigning a bag b i ∈ B 1 to a bag b j ∈ B 2 is then defined as the substitution cost of the associated node i ∈ V 1 and j ∈ V 2 , plus the cost associated to an optimal ǫ-assignment between the two sets composed of their incident edges and their adjacent nodes. Using such bags of patterns can be discriminant enough, in which case the bipartite GED provides a good approximation of the GED. But this approach lacks of accuracy in some cases, in particular when the direct neighbourhood of the nodes is homogeneous in the graph. When considering such graphs, the cost associated to each pair of bags do not differ sufficiently, and the optimal ǫ-assignment depends more on the traversal of the nodes by the LSAP solver than on the graph's structure.

In order to improve the accuracy of the bipartite GED, the information attached to each node needs to be more global, for instance by considering bags of walks up to a length k [START_REF] Gaüzère | Approximate Graph Edit Distance Guided by Bipartite Matching of Bags of Walks[END_REF], instead of the direct neighbourhood. This approach follows the same scheme as the one used in [START_REF] Riesen | Bipartite graph matching for computing the edit distance of graphs[END_REF][START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF], except that patterns associated to a node are defined as walks of length k starting at this node. Considering bags of such patterns allow to extend the amount of information associated to the nodes, which leads to a better approximation of the GED. However, the use of bags of walks induces some drawbacks. First, the set of computed walks suffers from the tottering phenomenon which leads to consider irrelevant patterns, especially when considering high values of k. These irrelevant patterns affect the cost of the ǫ-assignment, and thus the quality of the approximation of the GED. In addition, the mapping cost between two bags of walks can only be approximated, which induces another loss of accuracy.

These drawbacks can be avoided by using bags of subgraphs rather than bags of walks, such as all subgraphs centered on a given node and up to a radius k [START_REF] Carletti | Approximate graph edit distance computation combining bipartite matching and exact neighborhood substructure distance[END_REF]. The cost associated to the mapping of two bags of such patterns is defined as the edit distance between the two k-subgraphs centered on the respective nodes. Despite the fact that we can control the size of these subgraphs thanks to the parameter k, this approach requires significantly more computational time than the previous ones. However, the use of accurate sub-structures allows to obtain a better approximation of the GED.

GED as a Quadratic Assignment Problem

The bipartite GED is a good candidate approximation of the GED, but it is based on the construction of a restricted edit path which generally does not have a minimal cost. Costs on edges can only be deduced from operations performed on their two incident nodes. This cannot be taken into account by the approach based on the LSAP, which considers information about edges separately in each node. To fully describe the GED, the model must take into account simultaneous node and edge assignments. This can be formalized as a quadratic assignment problem [START_REF] Riesen | Bipartite graph matching for computing the edit distance of graphs[END_REF][START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF]. In this section, we propose to extend the linear model to a quadratic one based on ǫ-assignments, and we show that this model corresponds to the cost of a restricted edit path.

Simultaneous node assignment and quadratic cost

Let G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ) be two graphs, and let ψ ∈ Ψ(V ǫ 1 , V ǫ 2 ) be an ǫassignment (Definition 18). When a pair (i, j) ∈ V ǫ 1 × V ǫ 1 is assigned by ψ to a pair (ψ(i), ψ(j)) ∈ V ǫ 2 × V ǫ 2 , one of the following cases occurs: 1. Edge substitution: (ψ(i), ψ(j)) ∈ E 2 with (i, j) ∈ E 1 .

2. Edge removal: (ψ(i), ψ(j)) ∈ E 2 with (i, j) ∈ E 1 .

Edge insertion: (ψ

(i), ψ(j)) ∈ E 2 with (i, j) ∈ E 1 .
4. Finally (ψ(i), ψ(j)) ∈ E 2 with (i, j) ∈ E 1 allows to complete the bijection property.

Each possible simultaneous mapping of nodes i, j ∈ V ǫ 1 onto respectively nodes k and l in V ǫ 2 , is penalized by a non-negative cost d ik,jl which depends on the underlying edit operation described by one of the cases above. The overall edge's cost associated to a simultaneous node assignment is then measured by:

d(ψ) = n+m i=1 n+m j=1 d iψ(i),jψ(j) , (16)
where cost values are defined as follows.

Recall that all mappings from a node of V ǫ 1 to a node of V ǫ 2 are not allowed. Indeed (Section 3.1), i → ǫ j with i ∈ V 1 and j = i, and reciprocally ǫ k → l with l ∈ V 2 and k = l are forbidden. Then, a simultaneous node mapping involving at least one of these two cases is also forbidden. We denote by → a forbidden mapping. As in Section 3.2, the cost is set to a (large) value ω in this case.

For any other simultaneous node mapping (i → k, j → l), with i, j ∈ V ǫ 1 and k, l ∈ V ǫ 2 , its cost depends on the presence or the absence of edges (i, j) ∈ E 1 and (k, l) ∈ E 2 :

• If (i, j) ∈ E 1 and (k, l) ∈ E 2 then d ik,jl is the cost of the edge assignment (i, j) → (k, l), i.e. edge substitution.

• If (i, j) ∈ E 1 and (k, l) ∈ E 2 then d ik,jl is the cost of removing the edge (i, j).

• If (i, j) ∈ E 1 and (k, l) ∈ E 2 then d ik,jl is the cost of inserting the edge (k, l).

• Else, the simultaneous mapping must not influence the overall cost and so its cost is always set to 0.

By using the edit cost functions defined in Section 2.2, the cost of an allowed simultaneous node mapping is then defined by

c e (i → k, j → l) = c es ((i, j) → (k, l)) δ (i,j)∈E1 δ (k,l)∈E2 + c ed (i, j) δ (i,j)∈E1 (1 -δ (k,l)∈E2 ) + c ei (k, l) (1 -δ (i,j)∈E1 )δ (k,l)∈E2 (17)
where δ e ∈ E = 1 if e ∈ E and 0 else, (i, j) → ǫ denotes edge removal and ǫ → (k, l) denotes edge insertion. Since graphs do not have self-loops, we have

d ik,ik = 0 for all i ∈ V ǫ 1 and k ∈ V ǫ 2 .
Remark also that the symmetry of c e (i → k, j → l) depends on the one of edit operations and the one of directed edges when the two graphs are directed.

Finally, the cost of a simultaneous node mapping is given by

d ik,jl = ω if (i → k) ∨ (j l) c e (i → k, j → l) else (18) Let x ∈ vec[A ∼ n,m ] ⊂ {0, 1} (n+m
) 2 be the vectorization of the ǫ-assignment matrix associated to ψ. All costs can be represented by a (n + m) 2 × (n + m) 2 matrix D = (d ik,jl ) i,k,j,l such that d ik,jl x ik x jl = d iψ(i),jψ(j) if x ik = x jl = 1, and 0 else. So each row and each column of D, and x, have the same organization of pairwise indices, and then the total cost of the simultaneous node assignment can be written in quadratic form as:

d(ψ) = n+m i=1 m+n k=1 n+m j=1 m+n l=1 d ik,jl x ik x jl = x T Dx,
The cost matrix D can be decomposed as follows into blocks:

D =           D 1,1 • • • D 1,n D 1,ǫ1 • • • D 1,ǫm . . . . . . . . . . . . . . . . . . D n,1 • • • D n,n D n,ǫ1 • • • D n,ǫm D ǫ1,1 • • • D ǫ1,n D ǫ1,ǫ1 • • • D ǫ1,ǫm . . . . . . . . . . . . . . . . . . D ǫm,1 • • • D ǫm,n D ǫm,ǫ1 • • • D ǫm,ǫm           (19)
where each block D i,j ∈ [0, +∞) (m+n)×(m+n) defines the cost of assigning i and j of V ǫ 1 to respectively k and l for all k, l ∈ V ǫ 2 , i.e. [D i,j ] k,l = d ik,jl . Remark that blocks D i,j are organized in four main blocks corresponding to the nature of nodes i and j (dummy nodes or not). Each block D i,j is itself decomposed into four blocks as follows:

D i,j = j1 • • • jm jǫ 1 • • • jǫ n               i1 D i,j 1,1 D i,j 1,2 . . . im iǫ 1 D i,j 2,1 D i,j 2,2 . . . iǫ n (20)
where

D i,j 1,1 ∈ [0, +∞) m×m , D i,j 1,2 ∈ [0, +∞) m×n , D i,j 2,1 ∈ [0, +∞) n×m and D i,j 2,2 ∈ [0, +∞) n×n .
The different values taken by the elements of D, depending on the values of the indices, are reported in Table 1.

case block nodes in V ǫ 2 d (i,j),(k,l) 1 D i,j 1,1 k, l c es ((i, j) → (k, l))δ (i,j)∈E1 δ (k,l)∈E2 + c ed (i, j)δ (i,j)∈E1 (1 -δ (k,l)∈E2 ) + c ei (k, l)(1 -δ (i,j)∈E1 )δ (k,l)∈E2 2 D i,j 1,2 k, ǫ j c ed (i, j)δ (i,j)∈E1 else ω 3 D i,j 2,1 ǫ i , l c ed (i, j)δ (i,j)∈E1 else ω 4 D i,j 2,2 ǫ i , ǫ j c ed (i, j)δ (i,j)∈E1 else ω 5 D i,ǫ l 1,1 k, l c ei (k, l)δ (k,l)∈E2 else ω 6 D i,ǫ l 1,2 k, ǫ 0 7 D i,ǫ l 2,1 ǫ i , l 0 else ω 8 D i,ǫ l 2,2 ǫ i , ǫ 0 else ω 9 D ǫ k ,j 1,1 k, l c ei (k, l) δ (k,l)∈E2 else ω 10 D ǫ k ,j 1,2 k, ǫ j 0 else ω 11 D ǫ k ,j 2,1 ǫ, l 0 12 D ǫ k ,j 2,2 ǫ, ǫ j 0 else ω 13 D ǫ k ,ǫ l 1,1 k, l c ei (k, l) δ (k,l)∈E2 else ω 14 D ǫ k ,ǫ l 1,2 k, ǫ 0 else ω 15 D ǫ k ,ǫ l 2,1 ǫ, l 0 else ω 16 D ǫ k ,ǫ l 2,2 ǫ, ǫ 0
Table 1: Elements of matrix D according to the configuration of its indices. We consider that i, j

∈ V 1 , k, l ∈ V 2 , ǫ k , ǫ l ∈ E 1 , and ǫ i , ǫ j ∈ E 2 .
Epsilon values without indices mean any ǫ-value.

Proposition 7 If both G 1 and G 2 are undirected, then:

∀(i, k, j, l) ∈ V ǫ 1 × V ǫ 2 × V ǫ 1 × V ǫ 2 , d ik,jl = d jl,ik . Proof: If both G 1 and G 2 are undirected, then δ (i,j)∈E1 = δ (j,i)∈E1 , δ (k,l)∈E2 = δ (l,k)∈E2
and :

   c es ((i, j) → (k, l)) = c es ((j, i) → (l, k)) c ed (i, j) = c ed (j, i) c ei (k, l) = c ei (l, k)
Hence if none of i, j, k or l are equal to ǫ, the first line of Table 1 remains unchanged. Moreover, if ǫ ∈ {i, j, k, l}, then permuting indices (i, k) and (j, l) leads to the following permutations of the lines of Table 1 (after the appropriate renaming of variables):

(2, 3)(4)(5, 9)(6, 11)(7, 10)(8, 12)(13)(14, 15)(

One can check that in each case d ik,jl = d jl,ik .

Remark 2 If the rows of matrix D correspond to (i, k) and the columns to (j, l), then under the hypothesis of Proposition 7, D is symmetric and we get D T = D.

To fully represent edit operations we also need to consider the ones performed on nodes. This can be measured by the linear sum c T x defined in Section 3.2, where c = vec(C) ∈ [0, +∞) (n+m) 2 represents the cost of edit operations on nodes (Eq. 12):

c sub i,k = c vs (i → k) c rem i,k = c vd (i) if k = i ω else c ins i,k = c vi (k) if i = k ω else (21)
4.2 QAP for ǫ-assignments, restricted edit paths and GED

According to the following result, summing the quadratic and the linear costs defined above leads to the cost of a restricted edit path.

Proposition 8 Let ∆ = D if both G 1 and G 2 are undirected and ∆ = D + D T else. Note that using Proposition 7, ∆ is symmetric. Any non-infinite value of 1 2 x T ∆x + c T x corresponds to the cost of a minimal edit path. Conversely the cost of any minimal edit path may be written as 1 2 x T ∆x + c T x with the appropriate x. Proof: If 1 2 x T ∆x + c T x is not infinite, x corresponds to a matrix of assignment (Definition 10). Hence by propositions 6 and 4, there is a unique restricted edit path P such that P and x correspond to the same injective function ϕ from a subset V1 of V 1 onto V 2 . The edit path P substitutes each node v, belonging to V1 onto ϕ(v), removes all nodes belonging to V 1 \ V1 and insert all nodes belonging to V 2 \ ϕ[ V1 ] (Proposition 6).

Consider the notations of the proof of Proposition 6, i.e. the matrix X = (Q, R, S, T) defining x. The three first blocks are defined as: q i,ϕ(i) = 1 for any i ∈ V1 , r i,i = 1 for any i ∈ V 1 \ V1 and s j,j = 1 for any j ∈ V 2 \ ϕ[ V1 ]. These blocks are filled with 0 outside these indices (Proposition 4).

Let us decompose the cost γ(P ) of P into a cost γ v (P ) related to operations on nodes and a cost γ e (P ) related on operation on edges:

γ(P ) = γ v (P ) + γ e (P )
We have according to corollary 1:

γ v (P ) = v∈V1\ V1 c vd (v) + v∈ V1 c vs (v) + v∈V2\ V2 c vi (v)
On the other hand, let us denote by C sub , C rem and C ins the blocks corresponding to (Q, R, S) in the cost matrix C defining c (Section 3.2). The term c T x is equal to:

c T x = n i=1 m j=1 c sub i,j q i,j + n i=1 n j=1 c rem i,j r i,j + m i=1 m j=1 c ins i,j s i,j = i∈ V1 c sub i,ϕ(i) + i∈V1\ V1 c rem i,i + j∈V2\ϕ[ V1] c ins j,j = i∈ V1 c vs (i → ϕ(i)) + i∈V1\ V1 c vd (i) + j∈V2\ϕ[ V1] c vi (j)
The first line takes into account that the block corresponding to T in matrix C is equal to 0. Thus, this block does not play any role in the computation of c T x. The last line is due to the definition of the remaining blocks of C (equation 21).

We have thus γ v (P ) = c T x. Let us show that γ e (P ) = 1 2 x T ∆x. We have:

x T D jl = i,k d ik,jl x ik = n i=1 m k=1 d ik,jl q i,k + n i=1 m k=1 d ik,jl r i,k + m k=1 n i=1 d ik,jl s i,k = n i=1 m k=1 d ik,jl q i,k + n i=1 d iǫ,jl r i,i + m k=1 d ǫk,jl s k,k = i∈ V1 d iϕ(i),jl + i∈V1\ V1 d iǫ,jl + k∈V2\ V2 d ǫk,jl
where V2 = ϕ[ V1 ] (Proposition 5). In the same way we have:

x T Dx = j,l x T D jl x jl = j∈ V1
x T D jϕ(j) + j∈V1\ V1

x T D jǫ + l∈V2\ V2

x T D ǫl

We have:

j∈ V1 x T D jϕ(j) = j∈ V1   i∈ V1 d iϕ(i),jϕ(j) + i∈V1\ V1 d iǫ,jϕ(j) + k∈V2\ V2 d ǫk,jϕ(j)   = (i,j)∈ V 2 1 d iϕ(i),jϕ(j) + (i,j)∈E1∩(V1\ V1)× V1 c ed (i, j) + (k,l)∈E2∩(V2\ V2)× V2 c ei (k, l) j∈V1\ V1 x T D jǫ = j∈V1\ V1   i∈ V1 d iϕ(i),jǫ + i∈V1\ V1 d iǫ,jǫ + k∈V2\ V2 d ǫk,jǫ   = (i,j)∈E1∩V1×(V1\ V1) c ed (i, j) l∈V2\ V2 x T D ǫl = l∈V2\ V2   i∈ V1 d iϕ(i),ǫl + i∈V1\ V1 d iǫ,ǫl + k∈V2\ V2 d ǫk,ǫl   = (k,l)∈E2∩V2×(V2\ V2) c ei (k, l)
where all substitutions of d ij,kl by the corresponding removal or insertion costs are deduced from Table 1. Moreover, we have, using the notations of Proposition 5:

{(i, j) ∈ V1 2 | δ (i,j)∈E1 = δ (ϕ(i),ϕ(j))∈E2 = 1} = Ê1 {(i, j) ∈ V1 2 | δ (i,j)∈E1 = 1, δ (ϕ(i),ϕ(j))∈E2 = 0} = R 12 {(k, l) ∈ V2 2 | δ (ϕ -1 (k),ϕ -1 (l))∈E1 = 0, δ (k,l)∈E2 = 1} = I 21
Hence:

j∈ V1 i∈ V1 d iϕ(i),jϕ(j) = (i,j)∈ Ê1 c es ((i, j) → (ϕ(i), ϕ(j)))+ (i,j)∈R12 c ed (i, j)+ (k,l)∈I21 c ei (k, l)
Moreover we have:

(V 1 \ V1 ) × V1 ∪ V 1 × (V 1 \ V1 ) = (V 1 \ V1 ) × V 1 ∪ V 1 × (V 1 \ V1 ) Indeed: (V 1 \ V1 ) × V 1 ∪ V 1 × (V 1 \ V1 ) = (V 1 \ V1 ) × V1 ∪ (V 1 \ V1 ) × (V 1 \ V1 ) ∪ V 1 × (V 1 \ V1 ) = (V 1 \ V1 ) × V1 ∪ V 1 × (V 1 \ V1 )
Hence by grouping appropriate terms we get:

x T Dx = (i,j)∈ Ê1
c es ((i, j) → (ϕ(i), ϕ(j)))

+ (i,j)∈E1∩((V1\ V1)×V1∪V1×(V1\ V1))∪R12 c ed (i, j) + (k,l)∈E2∩((V2\ V2)×V2∪V2×(V2\ V2))∪I21 c ei (k, l)
Using Proposition 5 we finally get:

x T Dx = (i,j)∈ Ê1
c es ((i, j) → (ϕ(i), ϕ(j)))

+ (i,j)∈E1\ Ê1 c ed (i, j) + (k,l)∈E2\ Ê2 c ei (k, l)
Using Corollary 1 if both G 1 and G 2 are directed we get γ e (P ) = x T Dx. However in this case:

1 2 x T ∆x = 1 2 x T D + D T x = 1 2 x T Dx + x T D T x = 1 2 x T Dx + x T Dx = x T Dx
Hence γ e (P ) = 1 2 x T ∆x. Using Remark 1 we get γ e (P ) = 1 2 x T Dx = 1 2 x T ∆x if both G 1 and G 2 are undirected. Thus γ(P ) = 1 2 x T ∆x + c T x with ∆ = D if both G 1 and G 2 are undirected and ∆ = D + D T else.

Hence, the determination of a restricted edit path with a minimal cost is equivalent to searching for an optimal ǫ-assignment

x ∈ argmin 1 2 x T ∆x + c T x | x ∈ vec[A ∼ n,m ] (22)
In other terms, for the class of graphs under consideration, i.e. simple graphs, we have

GED(G 1 , G 2 ) = min 1 2 x T ∆x + c T x | x ∈ vec[A ∼ n,m ] (23)
This is a QAP, see [START_REF] Lawler | The quadratic assignment problem[END_REF][START_REF] Burkard | Assignment Problems[END_REF] for more details on QAPs. In particular, QAPs are NP-hard and exact algorithms can solve QAPs of small size only. So, many heuristics able to find suboptimal solutions in short computing time have been explored.

Remark 3 Note that the functional involved in the QAP defined by Eq. 22 can be rewritten as a general quadratic term:

1 2 x T ∆x + c T x = 1 2 x T ∆x + x T diag(c)x = x T 1 2 ∆ + diag(c) x (24)
where diag(c) is the diagonal matrix with c as diagonal. So the GED can be equivalently defined by

GED(G 1 , G 2 ) = min x T ∆x | x ∈ vec[A ∼ n,m ] (25)
where ∆ = 1 2 ∆ + diag(c) represents the cost of both node and edge edit operations. As graphs are simple, they have no self-loops and then the diagonal elements of ∆ are all equal to 0. So the diagonal of ∆ is always equal to c.

Solving QAPs with the Integer Projected Fixed Point Algorithm

We propose to compute an approximate GED by finding a solution of the QAP defined by Eq. 22, and rewritten here as the following binary quadratic programming problem:

argmin S(x)

def. = 1 2 x T ∆x + c T x | Ax = 1 n , x ∈ {0, 1} n (26)
where Ax = 1 n , with x ∈ {0, 1} n and A ∈ {0, 1} n×n , is the matrix version of the bijectivity constraints given by Eq. 3, see [START_REF] Burkard | Assignment Problems[END_REF][START_REF] Sierksma | Linear and Integer Programming: Theory and Practice[END_REF] for more details. Also, we suppose that c ∈ [0, +∞) n , and ∆ ∈ [0, +∞) n×n is assumed to be symmetric. Note that Eq. 22 is equivalent to Eq. 26, with additional constraints on x (Eq. 11) imposed by ω values in the expression of ∆ (Eq. 18 and Proposition 8) and c (Eq. 21). QAPs are generally NP-hard, which depends on the structure of the cost matrix ∆ = 1 2 ∆ + diag(c) (see previous section), and so most algorithms find approximate local or global optimal solutions by relaxing the bijectivity constraints on the solution, which leads to find a continuous solution instead of a discrete one:

argmin {S(x) | Ax 1, x ∈ [0, +∞) n } . ( 27
)
While this relaxed problem is also NP-hard, several polynomial-time algorithms have been designed to converge close to a local or global solution in a short computing time. The ones based on linearization of the cost function S are known to be particularly efficient. They transform the relaxed problem into a sequence of convex problems, such that a given initial solution is improved iteratively by decreasing the cost function up to a fixed point.

Then, the final continuous solution is binarized and used as a solution of the QAP. But as shown experimentally in [START_REF] Leordeanu | An integer projected fixed point method for graph matching and map inference[END_REF] in the context of graph matching, the continuous optimum is not necessarily close to the global discrete optimum. To try to overcome this problem, it seems to be more efficient to try to find a discrete solution as close as possible to a continuous one, at each iteration, as done by Sof-Assign [START_REF] Gold | Clustering with a domain-specific distance measure[END_REF][START_REF] Gold | A graduated assignment algorithm for graph matching[END_REF][START_REF] Gold | Softmax to softassign: Neural network algorithms for combinatorial optimization[END_REF] or Integer Projected Fixed Point (IPFP) [START_REF] Leordeanu | An integer projected fixed point method for graph matching and map inference[END_REF].

We present here an adaptation of the IPFP algorithm, originally proposed for maximization of a quadratic term [START_REF] Leordeanu | An integer projected fixed point method for graph matching and map inference[END_REF], to minimization. We also improve the computational complexity of several steps of the algorithm.

Given an initial continuous (or discrete) candidate solution x 0 , The idea of [START_REF] Leordeanu | An integer projected fixed point method for graph matching and map inference[END_REF] is to iteratively improve (here reduce) the corresponding quadratic cost in two steps at each iteration:

1. Compute a discrete linear approximation b k+1 of the quadratic cost S around the current solution x k by solving a LSAP. The iteration of these steps converges to an optimum of the relaxed problem, which is either continuous or discrete but generally not the global one. This last point depends on the initialization. The whole process is detailed in Algorithm 5.

At each iteration, in the first step, the cost S is linearly approximated. The differential of S in x k in the direction h is given by:

DS(x k ) • h = x T k ∆h + c T h (since ∆ is symmetric).
Hence the first-order Taylor expansion of S around the current solution x k is given by:

S(b) ≈ S(x k ) + x T k ∆ + c T (b -x k ) ≈ S(x k ) + R(b) -R(x k ) ( 28
)
where R(x) = (x T k ∆ + c T )x and b ≥ 0. Keeping x k fixed, S(x k ) and R(x k ) are constant, and so the minimization of S(b) is approximatively equivalent to the minimization of R(b):

b k+1 ∈ argmin x T k ∆ + c T b | Ab = 1, b ≥ 0 n . (29)
This is a linear programming problem with totally unimodular constraint matrix A and the right-hand side vector of the linear system Ab = 1 is integer valued. So, by standard tools in linear programming, there is an integer optimal solution, here binary and equal to the solution of the LSAP [START_REF] Sierksma | Linear and Integer Programming: Theory and Practice[END_REF][START_REF] Burkard | Assignment Problems[END_REF]

b k+1 ∈ argmin x T k ∆ + c T b | Ab = 1, b ∈ {0, 1} n×n . ( 30
) Algorithm 1 IPFPmin(x 0 , c, ∆, k max ) 1: k ← 0, L ← c T x 0 , S k ← 1 2 x T 0 ∆x 0 + L 2: repeat 3:
// Projection of the cost by solving a LSAP

4: b k+1 ← argmin{(x T k ∆ + c T )b | b ∈ A ∼ n,m } 5:
// Minimize the quadratic cost along the direction b k+1 6:

L ′ ← c T b k+1 7: S b k+1 ← 1 2 b T k+1 ∆b k+1 + L ′ 8: α ← R(b k+1 ) -2S k + L 9: β ← S b k+1 + S k -R(b k+1 ) -L 10: t 0 ← -α/(2β) 11: if (β ≤ 0) ∨ (t 0 ≥ 1) then 12: x k+1 ← b k+1 S k+1 ← S b k+1 , L ← L ′ 13:
else 14:

x k+1 ← x k + t 0 (b k+1 -x k ) 15: S k+1 ← S k -α 2 /(4β) 16: L ← c T x k+1 17: end if 18: k ← k + 1 19: until (x k+1 = x k ) ∨ (k ≥ k max ) 20: if x k+1 = b k+1 then return (x k+1 , S k+1 ) 21: x k+1 ← argmin{x T k+1 b | b ∈ A ∼ n,m } 22: return (x k+1 , S k+1 )
In our experiments, this problem is solved by the O(n 3 ) version of the Hungarian algorithm [START_REF] Lawler | Combinatorial Optimization: Networks and Matroids[END_REF][START_REF] Burkard | Assignment Problems[END_REF], modified such that forbidden assignments represented by ω values in ∆ and c are not treated. The resulting assignment b k+1 determines a direction of largest possible decrease of S in the first-order approximation. Let us additionally note that the first order approximation of S(b) is lower than S(x k ) since R(b k+1 ) ≤ R(x k ). However we cannot yet conclude since this is only an approximation.

The second step of each iteration of Algorithm 5 consists in minimizing the quadratic function S in the continuous domain along the direction given by b k+1 . This can be done analytically. Let x t = x k + t(b k+1 -x k ), with t ∈ [0, 1], be a parameterization of the segment between x k and b k+1 . The evolution of S on this segment is provided by: The main advantage of the above expression for the calculation of α, and not used in the original algorithm [START_REF] Leordeanu | An integer projected fixed point method for graph matching and map inference[END_REF], is that R(b k+1 ) is already computed by the LSAP algorithm that computes b k+1 . Moreover S(x k ) and c T x k may be stored from the previous iteration of the algorithm. Note that since α = R(b k+1 ) -R(x k ) we have α ≤ 0. For β, the improvement is a bit more tedious. We have indeed to compute S(b k+1 ). Hence the gain is not obvious compared to the direct computation of (b k+1 -x k ) T ∆(b k+1 -x k ) as done in the original algorithm [START_REF] Leordeanu | An integer projected fixed point method for graph matching and map inference[END_REF]. Note however that S(b k+1 ) will also be used in a following step, so computations are factorized. The problem is thus transformed into finding the optimal value

S(x t ) = S(x k + t(b k+1 -x k )) = 1 2 [x k + t(b k+1 -x k )] T ∆[x k + t(b k+1 -x k )] + c T [x k + t(b k+1 -x k )] = 1 2 x T k ∆x k + c T x k + tx T k ∆(b k+1 -x k ) + 1 2 t 2 (b k+1 -x k ) T ∆(b k+1 -x k ) + tc T (b k+1 -x k ) = S(x k ) + t[x T k ∆(b k+1 -x k ) + c T (b k+1 -x k )] + 1 2 t 2 (b k+1 -x k ) T ∆(b k+1 -x k ) = S(x k ) + tR(b k+1 -x k ) + 1 2 t 2 (b k+1 -x k ) T ∆(b k+1 -x k ) = S(x k ) + αt + βt 2 where α = R(b k+1 -x k ) = R(b k+1 ) -R(x k ) ≤ 0 = R(b k+1 ) -x T k ∆x k -c T x k = R(b k+1 ) -2( 1 2 x T k ∆x k + c T x k ) + c T x k = R(b k+1 ) -2S(x k ) + c T x k β = 1 2 (b k+1 -x k ) T ∆(b k+1 -x k ) = 1 2 b T k+1 ∆b k+1 -x T k ∆b k+1 + 1 2 x T k ∆x k = 1 2 b T k+1 ∆b k+1 + c T b k+1 -R(b k+1 ) + 1 2 x T k ∆x k = S(b k+1 ) + S(x k ) -R(b k+1 ) -c T x k 1 1 S(xt 0 ) t S(x t ) (a) β ≥ 0, t 0 ≤ 1 1 1 t S(x t ) (b) β ≥ 0, t 0 ≥ 1 1 1 t S(x t ) (c) β < 0
t 0 = argmin S(x t ) = S(x k ) + αt + βt 2 | t ∈ [0, 1] . (31)
The derivative of S(x t ) cancels at t 0 = -α/(2β). Then as shown in Fig. 2, we have:

• If β > 0 -If t 0 ≤ 1, S(x t0
) is the minimum of S(x t ), in particular it is lower than S(x k ) and S(b k+1 ). Moreover:

S(x t0 ) = S(x k ) - α 2 2β + α 2 4β = S(x k ) - α 2 4β
-If t 0 ≥ 1, then S ′ (x t ) < 0 ∀t ∈ [0, 1], and the minimal value of S(x t ) is S(x 1 ) = S(b k+1 ).

• If β ≤ 0, since α ≤ 0, S(x t ) decreases between t = 0 and t = 1. Its minimal value is thus S(x 1 ) = S(b k+1 ).

So, if either β < 0 or β > 0, but t 0 ≥ 1, the minima of S(x t ) within the range t ∈ [0, 1] is obtained for t 0 = 1, i.e. x t0 = b k+1 (lines [START_REF] Gold | Clustering with a domain-specific distance measure[END_REF][START_REF] Gold | A graduated assignment algorithm for graph matching[END_REF]. Note that in this case the new solution is discrete. In the remaining case (lines 13-16), S(x t ) passes by a minimal value lower than S(x k ) and S(b k+1 ). In both cases x t0 is taken as the solution x k+1 for the next iteration. Hence, as in the original algorithm [START_REF] Leordeanu | An integer projected fixed point method for graph matching and map inference[END_REF], S(x k ) decreases at each iteration, and since ∆ and c are positive, S is bounded bellow 0 and the algorithm converges. The whole process is iterated until a fixed point is reached, in which case x k+1 is ensured to be a minimum of the relaxed problem defined by Eq. 27. When a minimum of the original problem defined by Eq. 26 is requested as for the GED, the discrete vector closest to the minimum of the relaxed problem is selected. Note that the method [START_REF] Justice | A binary linear programming formulation of the graph edit distance[END_REF] does not guarantee the solution to be binary. The minimum of the relaxed problem is not guaranteed to be global. This depends on the initial vector x 0 , which influences both the value of the resulting cost and the number of iterations required to reach the convergence. For the approximation of the GED, we have tested several initializations based on the LSAP, as described in the following section. We have observed that the exact GED is often obtained, meaning that the optimal solution of the original problem can be reached by the algorithm.

Experiments

In this section, we present some experimentation results to show the effectiveness of our quadratic assignment approach with respect to the ones based on LSAPs. To this purpose, we compare our approach to three methods based on the LSAP and one method to compute the exact graph edit distance based on A * algorithm. The latter method is used as a baseline to measure the error induced by approximations. However, A * is restricted to very simple graphs and it wasn't possible to compute exact graph edit distances for two over the four used datasets. The three LSAP methods, i.e. bipartite GEDs, are the ones proposed in [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF][START_REF] Gaüzère | Approximate Graph Edit Distance Guided by Bipartite Matching of Bags of Walks[END_REF][START_REF] Carletti | Approximate graph edit distance computation combining bipartite matching and exact neighborhood substructure distance[END_REF]. They differ on the definition of the cost between elements, as already discussed.

The experiments have been performed on four chemoinformatics datasets1 (see Table 2 for their characteristics) plus one synthetic dataset to test larger graphs. The variety of these datasets allows to see the behavior of different approaches on four kind of graphs: acyclic labeled (Acyclic), acyclic not labeled (Alkane), cyclic labeled (MAO), cyclic not labeled (PAH). Finally, the synthetic dataset is composed of graphs having same characteristics as the ones in MAO dataset but extended up to 100 nodes (details bellow).

Table 3 shows the results of our experiments on the four GREYC's datasets. Note that, in order to avoid some bias, these results have been computed using random permutations of the adjacency matrices before computing graph edit distances. Moreover, all experiments have been computed on the same machine, hence providing comparable computational times. In order to show the relevancy of our proposal, we compute the average edit distance (d), the average approximation error (e) with respect to the exact graph edit distance and the average computational time (t) required to get the graph edit distance for a pair of graphs. For these three measures, lower values correspond to better results. Indeed, since approximation approaches overestimate graph edit distance, a lower average edit distance can be considered as better than an higher one. Due to the computational complexity required by A* algorithm, the exact graph edit distance has not been computed on PAH and MAO datasets which are composed of larger graphs than the ones in Acyclic and Alkane datasets.

IPFP approach allows to drastically improve the accuracy of the approximation with respect to LSAP approaches while keeping a reasonable computational time. This observation can be made on the four datasets, hence showing the consistency of this QAP approach.

Results shown in Table 3 also highlight the importance of the initialization step. Since the functional of QAP formulation is not convex, different initializations can lead to different local minima. Obviously, initializations close to the global minimum have an higher probability to reach it than initializations far from it. This behavior is observed in the results where better approximations are obtained by using the approach giving the best approximation considering LSAP framework. Moreover, less iterations are required to reach convergence since the algorithm is initialized close to the minima. This phenomenon explains the low differences of computational time between the different approaches. Note that we didn't test the method presented in [START_REF] Carletti | Approximate graph edit distance computation combining bipartite matching and exact neighborhood substructure distance[END_REF] due to its high computational time. In conclusion, these results show that the QAP approach is a relevant approach to approximate graph edit distance and outperforms methods based on LSAP formulation while keeping an interesting computational time with respect to the one required to compute an exact graph edit distance.

Figure 3 shows how our IPFP approach scales with the size of graphs. This results have been computed on a synthetic dataset having same node's and edge's labels distribution and same ratio between the number of edges and the number of nodes as MAO dataset but generalized to different graph sizes. For a given number of nodes, a synthetic dataset is composed of 100 pairs of source and target graphs. Each target graph has been generated by removing one node and substituting another one from the associated source graph. The overall edit distance between source and target graphs is then defined by the cost associated to this two node operations together with the induced edit operations on edges. The graph edit distance between each pair of graphs is around 10. Given this protocol, we generated a synthetic dataset composed of 100 couples of graphs for different graph's sizes, hence obtaining 10 datasets from 10 to 100 nodes.

In Figure 3, the dashed green line corresponds to the computational time required to compute an approximation of the graph edit distance, the plain blue line to the average approximation error and the dotted red line corresponds to the percentage of pairs for which the exact graph edit distance is computed using IPFP. The x axis corresponds to the size of the graphs. The y axis on the left of Figure 3 represents simultaneously the mean execution times and the average error using a same scaling. Hence, for example, 0.5 should be read as 0.5 seconds on the dashed green line and as an average error of 0.5 on the plain blue curve. The y axis on the right corresponds to the percentage of exact graph edit distances computed by our algorithm and should be used for the analysis of the dotted red curve. As we can see, the accuracy of the approximation using IPFP is stable for all tested sizes. The average error for each dataset remains about 5 to 10 % of the exact graph edit distance which corresponds to a good approximation. Moreover, the percentage of perfect approximation shows that we are able to compute the exact graph edit distance for 75% to 91% pairs of graphs. From a computational point of view, the curve seems to describe a polynomial function with respect to the size of graphs. Considering a bounded number of iterations, this observation is conform with the cubic complexity associated to the algorithm used to resolve LSAP problems, which is used in each iteration of the IPFP algorithm.

Conclusion

We have in this paper characterized the solutions of some LSAP and QAP as edit paths belonging to a certain family. This characterization has allowed us to solve the graph edit distance problem through a QAP with a clear definition of the family of edit paths implied in the minimization process.

The proposed algorithm used to solve the QAP usually provides a permutation matrix, and hence a value which can be directly interpreted as an approximation of the GED. If the final matrix is only stochastic, we simply project it on the set of permutation matrices in order to obtain the desired value.

Our experiments show that the proposed algorithm usually find values quite close from the optimal solutions within computational times which allow to apply it on graphs of non trivial sizes. These experiments also show the importance of the initialization step since a good initialization both improves the final result and reduces the number of iterations.

Our further works should investigate different directions: the initialization step, the removal within our algorithm of the different instances of ǫ values and finally the definition of alternative QAP solvers. Such improvements should allow in a near future to compute efficiently close approximations of the graph edit distance on graphs composed of a thousand of nodes.

( 11 )

 11 Definition 19 (ǫ-assignment matrix) A (n + m) × (m + n) matrix satisfying equations 3, 10 and 11 is called an ǫ-assignment matrix. The set of all (n + m) × (m + n) ǫ-assignment matrices is denoted by A n,m .

2 .

 2 Compute the next candidate solution x k+1 by solving the relaxed problem, reduced to compute the extremum of S between x k and b k+1 included.

Figure 2 :

 2 Figure 2: Illustration of the 3 cases relating β and t 0 .

Figure 3 :

 3 Figure 3: Analysis of complexity on a synthetic dataset.

Table 2 :

 2 Characteristics of the four GREYC's chemistry datasets.

	Dataset Number of graphs Avg Size Avg Degree
	Alkane	150	8.9	1.8
	Acyclic	183	8.2	1.8
	M AO	68	18.4	2.1
	P AH	94	20.7	2.4

Table 3 :

 3 Accuracy and complexity scores. d is the average edit distance, e the average error and t the average computational time.

	Algorithm	d	Alkane e t	d	Acyclic e t	d	MAO t	d	PAH t
	A *	15		1.29	17		6.02
	[26]	35	18	≃ 10 -3 35	18	≃ 10 -3 105	≃ 10 -3 138	≃ 10 -3
	[10]	33	18	≃ 10 -3 31	14	≃ 10 -2 49	≃ 10 -2 120	≃ 10 -2
	[5]	26	11	2.27	28	9	0.73	44	6.16	129	2.01
	IP F P Random init 22.6 7.1 0.007	23.4 6.1 0.006	65.2 0.031	63	0.04
	IP F P init [26]	22.4 7.0 0.007	22.6 5.3 0.006	59	0.031	62.2 0.04
	IP F P Init [10]	20.5 5	0.006	20.7 3.4 0.005	33.6 0.016	52.5 0.037

Available at https://brunl01.users.greyc.fr/CHEMISTRY/