Pierre Le Bodic
email: pierre.lebodic@lri.fr

Pierre Héroux
email: pierre.heroux@univ-rouen.fr

Sébastien Adam
email: sebastien.adam@univ-rouen.fr

Yves Lecourtier
email: yves.lecourtier@univ-rouen.fr

An Integer Linear Program for Substitution-Tolerant Subgraph Isomorphism and its Use for Symbol Spotting in Technical Drawings

Keywords: Substitution-Tolerant Subgraph Isomorphism, Integer Linear Programming, Symbol Spotting

Introduction

Labeled graphs are data structures able to model complex entities. In a graph-based representation, vertices and their labels describe objects or entity components whereas edges represent the relationships between the components. Due to the intrinsic genericity of structural representations and thanks to the improvement of the computational power of computers, graphs are being increasingly used in a large scope of application domains such as biology, chemistry, computer vision, information retrieval or pattern recognition. As a consequence of the intensive use of graph-based representations, a growing interest is being shown to graph algorithms including graph mining [START_REF] Kuramochi | Finding frequent patterns in a large sparse graph[END_REF][START_REF] Inokuchi | Complete mining of frequent patterns from graphs: Mining graph data[END_REF][START_REF] Barbu | Frequent graph discovery: Application to line drawing document images[END_REF], graph classification [START_REF] Neuhaus | Edit distance-based kernel functions for structural pattern classification[END_REF][START_REF] Raveaux | Learning graph prototypes for shape recognition[END_REF] or clustering [START_REF] Zanghi | Fast online graph clustering via Erdos Renyi mixture[END_REF][START_REF] Qiu | Graph matching and clustering using spectral partitions[END_REF][START_REF] Lozano | Protein classification by matching and clustering surface graphs[END_REF], graph isomorphism [START_REF] Cordella | A (sub)graph isomorphism algorithm for matching large graphs[END_REF][START_REF] Auwatanamongkol | Inexact graph matching using a genetic algorithm for image recognition[END_REF][START_REF] Zampelli | Solving subgraph isomorphism problems with constraint programming[END_REF][START_REF] Solnon | Alldifferent-based filtering for subgraph isomorphism[END_REF].

In the context of pattern recognition, graph-based techniques are generally used to match a graph representing a known entity to a graph resulting from an observation. The general framework of graph matching covers different problems according to the kind of constraints which must be respected or those which can be relaxed. A particular class of matching problem is the substitution-tolerant subgraph isomorphism. A subgraph isomorphism is said to be substitution-tolerant when the mapping does not affect the topology, i.e. each vertex and each edge of the pattern graph has a one-to-one mapping into the target graph, but when editing operations between vertex and edge labels are allowed. A substitution-tolerant mapping is generally needed when no exact mapping between vertex and/or edge labels can be found, but when the mapping can be associated to a cost. For example, this case occurs when vertex and edge labels are numerical values (scalar or vectorial) resulting from a feature extraction step as often in pattern analysis. The cost for the mapping can then be defined as the sum of the distances between label values. A first solution to tackle such problems relies on a discretization or a classification procedure to transform the numerical values into nominal labels. The main drawback of such approaches is their sensitivity to frontier effects of the discretization or misclassification. A subsequent exact matching algorithm would then be unsuccessful. A second solution consists in using exact matching algorithms and to customize the compatibility function for pairing vertices and edges. The main drawback of such approaches is the need to define thresholds for these compatibilities. A last way consists in using a substitution-tolerant matching procedure that overcomes this drawback by integrating the numerical values during the mapping search. In this case, the matching problem turns from a decision one to an optimization one.

In this paper, we propose a new modelling of the substitution-tolerant subgraph isomorphism as an optimization problem modeled by an integer linear program. This original approach is parameter free and solves problems that could not be solved optimally using existing algorithms. This paper is an extended and improved version of [START_REF] Bodic | Symbol detection using region adjacency graphs and integer linear programming[END_REF]. The new contributions concern an extension of the approach for the search for multiple solutions and a strategy that enables the learning of a threshold for this search. Moreover, many new experimental results are proposed on both synthetic and real datasets. They include a comparison with state of the art approaches, in order to show the strong points and the weaknesses of the proposed method.

The paper is organized as follows. Section 2 introduces substitutiontolerant subgraph isomorphism and reviews related approaches from the literature. Section 3 presents Integer Linear Programming as a way to express optimization problems and our formulation of the substitution-tolerant subgraph isomorphism. Section 4 reports many experimental results obtained by the proposed approach on both synthetic and application-dependent datasets. The application concerns the localization of symbols on technical drawings. Finally, section 5 draws a conclusion of the paper and proposes future directions.

Subgraph isomorphism

Definitions and notations

The approach proposed in this paper deals with directed graphs, defined as follows :

Definition 1. A directed attributed multigraph 1 G is a 4-tuple G = (V, E, µ, ξ) where V is the set of vertices of G, E is a multiset of ordered pairs e = (v 1 , v 2 ) with v 1 ∈ V and v 2 ∈ V , i.e. edges of G. µ : V → L V is
a function assigning a label to a vertex, L V being the set of possible labels for vertices. ξ : E → L E is a function assigning a label to an edge, L E being the set of possible labels for edges.

Considering two graphs, one can be interested in finding the instances of the first one (the pattern graph) in the second one (the target graph). In graph theory, this problem is called subgraph isomorphism2 . It relies on the definition of subgraph :

Definition 2. Given a graph G = (V, E, µ, ξ), a subgraph of G is a graph S = (V S , E S , µ S , ξ S ) such that V S ⊆ V , E S ⊆ E, ∀e = (v 1 , v 2 ) ∈ E S , v 1 ∈ V S , v 2 ∈ V S
and µ S and ξ S are the restrictions of µ and ξ to V S and E S , i.e. µ S (v) = µ(v) and ξ S (e) = ξ(e)

Using this definition, the subgraph isomorphism problem between a pattern graph G and a target graph G ′ is defined by : Definition 3.

An injective function f : V → V ′ is a subgraph isomor- phism from a graph G = (V, E, µ, ξ) to a graph G ′ = (V ′ , E ′ , µ ′ , ξ ′ ) if there exists a subgraph S of G ′ such that f is a graph isomorphism from G to S : • ∀v ∈ V, f (v) = v ′ ∈ V ′ , f -1 (v ′ ) = v • for all e = (v 1 , v 2 ) ∈ E, there exists a distinct edge e ′ = (f (v 1 ), f (v 2 )) ∈ E ′
Note that extra edges may exist in G ′ between mapped vertices, i.e. a subgraph does not need to be induced.

In its exact formulation, the subgraph isomorphism must preserve the labelling, i.e. µ(v) = µ ′ (v ′ ) and ξ(e) = ξ ′ (e ′ ). In pattern recognition applications, where vertices and edges are labeled with measures which may be affected by noise, a substitution-tolerant formulation which allows differences between labels of mapped vertices and edges is mandatory. However, these differences are associated to costs and one is interested in finding the mapping corresponding to the minimal global cost, if one exists.

Existing approaches

A very complete and detailed review of the numerous graph matching techniques may be found in [START_REF] Conte | Thirty years of graph matching in pattern recognition[END_REF]. This paper proposes a taxonomy which distinguishes mainly exact and inexact techniques. In the following, we only examine approaches that deal with subgraph isomorphism, also called monomorphism. Exact techniques may be used to solve the substitutiontolerant subgraph isomorphism problem. For that purpose, a compatibility function must compare labels and decide whether each vertex (resp. edge) of the pattern graph may be mapped to each vertex (resp. edge) of the target graph or not. The compatibility function is generally based on a threshold between label differences. Most of the exact techniques rely on a tree based exploration in a search space, in which each state corresponds to a partial mapping. Backtracking, forward checking and procedures maintaining arc consistency are used to reach a state where all vertices and edges of the pattern graph are mapped to the target one. The exact subgraph isomorphism problem can be modeled as a constraint satisfaction problem [START_REF] Larrosa | Constraint satisfaction algorithms for graph pattern matching[END_REF][START_REF] Solnon | Alldifferent-based filtering for subgraph isomorphism[END_REF]. The different techniques proposed in the literature differ from (i) the order in which partial mappings are explored (ii) the filtering caused by the constraint propagation which allows to reduce the search space. In [START_REF] Solnon | Alldifferent-based filtering for subgraph isomorphism[END_REF], Solnon reviews and compares several approaches by examining the strength of the filtering. In this paper, the author proposes the LAD-filtering (locally all different) which is proven to be stronger than other known techniques (especially [START_REF] Ullmann | An algorithm for subgraph isomorphism[END_REF][START_REF] Larrosa | Constraint satisfaction algorithms for graph pattern matching[END_REF] when examining the filtering criterion. Experimental results reported in this paper also shows that the LAD-filtering allows to resolve more instances quicker than VF/VF2.

VF [START_REF] Cordella | Performance evaluation of the VF graph matching algorithm[END_REF] is a solver which performs forward checking propagation of edge and difference constraints. The constraint propagation is limited to vertices that are adjacent to vertices already matched. This implies that the subgraph induced by the matched vertices is connected. VF2 [START_REF] Cordella | A (sub)graph isomorphism algorithm for matching large graphs[END_REF] is an improved version of VF which reduces its spatial complexity and achieve better performance on large graphs. Experimental resultats reported in [START_REF] Cordella | A (sub)graph isomorphism algorithm for matching large graphs[END_REF] illustrate that VF2 clearly outperforms Ullmann's algorithm on the subgraph isomorphism task.

The main drawback of exact techniques for pattern recognition applications is the difficulty to set the thresholds used to decide whether two vertices (resp. edges) can be matched or not, based on their attribute values (regardless structural consideration). If one is interested in a subgraph isomorphism that minimizes the sum of all label differences (or another measure), then this sum must be computed for all matching candidates. In this context, choosing a threshold is puzzling. On the one hand, setting a small threshold reduces the number of matching candidates and speeds up the search, but at the cost of possibly discarding all optimal mappings (see Fig. 1). On the other hand, setting a large threshold results in a costly search among more matching candidates.

In order to overcome this drawback, inexact optimal approaches are guided by the cost of the partial mapping and a heuristic which approx-i (1) j ( 1 imates the future mapping to explore the search space. The branch and bound algorithm allows to prune branches of the tree that lead to unsuccessful solution as in [START_REF] Ghahraman | Graph optimal monomorphism algorithms[END_REF][START_REF] Wong | An algorithm for graph optimal monomorphism[END_REF], whereas the A* algorithm dynamically orders branches to explore as a priority. In this latter case, the computationnal performance highly depends on the quality of approximation of the future matching by the heuristics, but the optimal solution is always reached. One the other hand, the complexity issue is tackled by suboptimal optimization techniques. Among them, relaxation techniques like the one proposed in [START_REF] Wilson | Structural matching by discrete relaxation[END_REF] transform the discrete optimization process in a continuous one which can be solve in polynomial time. Other optimization techniques such as those based on neural networks or genetic algorithms [START_REF] Auwatanamongkol | Inexact graph matching using a genetic algorithm for image recognition[END_REF] have been proposed for graph matching problems. If the polynomial complexity of suboptimal techniques is appealing, they do not guaranty to provide the matching with the minimal global cost.

This paper proposes an integer linear program to solve the problem of substitution-tolerant subgraph isomorphism, which is an inexact approach for monomorphism. In the literature, linear programming has been proposed to model other graph matching problems. For example, the weighted graph matching problem has been successfully tackled by a linear approach by Almohamad and Duffuaa [START_REF] Almohamad | A linear programming approach for the weighted graph matching problem[END_REF]. More recently, Justice and Hero have proposed a binary linear program for the graph edit distance [START_REF] Justice | A binary linear programming formulation of the graph edit distance[END_REF]: two input graphs are first embedded into a clique of size the sum of the graph sizes. Then, an adjacency matrix is shown to encode an isomorphism between an input graph and the clique, while a permutation matrix encodes edit operations. The mathematical formulation then consists in finding a permutation matrix which yields a minimum isomorphism cost.

In the following of this article, we propose an optimization-based approach for solving substitution-tolerant subgraph isomorphism via an Integer Linear Program.

Solving the Subgraph Isomorphism Problem using Integer Linear Programming

The main contribution of this paper is the modelization of the substitutiontolerant subgraph isomorphism problem as an optimization problem. The general technique used to solve this problem is Mathematical Programming (MP) which provides tools to model optimization problems as well as resolution algorithms. More precisely, we provide an Integer Linear Program (ILP), i.e. a MP with linear equations and integer variables [START_REF] Nemhauser | Integer and combinatorial optimization[END_REF][START_REF] Schrijver | Theory of Linear and Integer Programming[END_REF]. (Solving an) ILP is NP-hard, therefore there is no known polynomial-time algorithm to solve general ILP. However, non problem-specific algorithms are continuously designed, improved, and implemented by the ILP community. ILP is known to be one of the most efficient technique for numerous NP-hard optimization problems that appear for instance in production [START_REF] Kellerer | Knapsack Problems[END_REF], logistics [START_REF] Applegate | The Traveling Salesman Problem: A Computational Study[END_REF], or network design [START_REF] Hwang | The Steiner Tree Problem[END_REF]. In the following, we briefly explain how to solve a problem using ILP. Then, we explain how we model the subgraph isomorphism problem. Finally, we disclose the methods used to find multiple close-to-optimal solutions, rather than a single optimal solution.

Integer Linear Programming

Solving a problem using ILP is a two-step process: it first requires a mathematical modelling of the problem as an integer linear program. The model must then be implemented using a solver. The general form of an ILP is as follows:

min x c T x (1a) subject to Ax ≤ b (1b) x ∈ C ⊆ Z n (1c) where c ∈ R n , A ∈ R n * m , b ∈ R m are data of the problem.
A solution is a vector x of n variables. In the case of integer programming, x belongs to a discrete set C ⊆ Z n . C has to be defined according to the modeled problem. A is used to express linear inequality constraints (1b). Hence, a feasible solution for the problem is a vector x such that x ∈ C and constraints (1c) are respected. The objective function c T x is a linear combination of all variables x weighted by the vector c. To find an optimal solution, the objective function (1a) is minimized over the set of feasible solutions.

Testing each vector x for feasibility is exponential in the number of variables. Hence, the second step consists in implementing this model using a solver. Such a tool is a complex set of algorithms that interact to implicitly explore the tree of solutions with the so-called Branch and Bound method. Given an instance, the solver finds an optimal solution if one exists.

Modeling the Subgraph Isomorphism Problem

In the following, for the sake of clarity, the term graph represents a simple directed graph with loops, what means that no more than one edge exists linking a vertex to an other, but the modeling holds for multigraphs. As a consequence, an edge e originating from i and targeting to j and can be denoted ij without any ambiguity.

In order to model the problem as an ILP, we use binary variables, i.e. C = {0, 1} n . As depicted in figure 2, two kinds of variable are defined:

• For each pair of vertices i ∈ V S and k ∈ V G , there is a variable x i,k , such that x i,k = 1 if vertices i and k are matched together, 0 otherwise.

• For each pair of edges ij ∈ E S and kl ∈ E G , there is a variable y ij,kl , such that y ij,kl = 1 if edges ij and kl are matched together, 0 otherwise.

i j k l x i,k = 1
x j,l = 1

y ij,kl = 1 S G Figure 2
: an example of matching. S and G both contain a single edge, respectively ij and kl. The following solution is represented on this figure : x i,k = 1 (resp. x j,l = 1, y ij,kl = 1), i.e. i (resp. j, ij) is matched with k (resp. l, kl). Conversely, since i (resp. j) is not matched with l (resp. k), x i,l = 0 (resp. x j,k = 0).

Given S = (V S , E S ) and G = (V G , E G ), let us assume that a cost function c V : V S × V G → R + as well as a cost function c E : E S × E G → R + are known. Let us consider two vertices i ∈ V S and k ∈ V G . Pairing i and k (i.e.
x i,k = 1) costs c V (i, k), whereas not pairing them (i.e. x i,k = 0) costs 0. The cost can thus be written as the linear expression c V (i, k) * x i,k . Similarly, the cost between two edges ij ∈ E S and kl ∈ E G is c E (ij, kl) * y ij,kl . Let us now write the objective function : the global cost for matching S to a subgraph of G, which is the sum of the costs for matching vertices and edges, should be minimized:

min x,y   i∈V S k∈V G c V (i, k) * x i,k + ij∈E S kl∈E G c E (ij, kl) * y ij,kl   (2a)
Obviously, equation (2a) does not encode the subgraph isomorphism problem. Let us now consider the constraints of the ILP.

• Every vertex of V S must be matched to a unique vertex of V G :

k∈V G x i,k = 1 ∀i ∈ V S (2b)
• Every edge of E S must be matched to a unique edge of E G :

kl∈E G y ij,kl = 1 ∀ij ∈ E S (2c)
• Every vertex of V G must be matched to at most a vertex of E S :

i∈V S x i,k ≤ 1 ∀k ∈ V G (2d)
• If two vertices are matched together, an edge originating the vertex of S must be matched with an edge originating the vertex of G:

kl∈E G y ij,kl = x i,k ∀k ∈ V G , ∀ij ∈ E S (2e)
• If two vertices are matched together, an edge targeting the vertex of S must be matched with an edge targeting the vertex of G:

kl∈E G y ij,kl = x j,l ∀l ∈ V G , ∀ij ∈ E S (2f)
Finally, let us properly write the aforementioned domain constraints of the variables:

x i,k ∈ {0, 1} ∀i ∈ V S , ∀k ∈ V G (2g) y ij,kl ∈ {0, 1} ∀ij ∈ E S , ∀kl ∈ E G (2h)
Equations (2a) to (2h) form the ILP used to solve the Subgraph Isomorphism Problem. It might be the case that the problem is infeasible, if there exists no graph isomorphism between S and any subgraph of G. Otherwise, a solver implementing this model will return the best solution found, i.e. the best subgraph isomorphism.

Finding Multiple Close-to-Optimal Solutions

Depending on the application context, it may be the case that the pattern graph that is searched for has many instances in the target graph. As defined in subsection 3.2, the ILP model is only capable of finding the optimal solution. There is no out-of-the-box free implementation to find multiple closeto-optimal solutions in ILP. There are, however, multiple ways to achieve this [START_REF] Danna | Generating multiple solutions for mixed integer programming problems[END_REF]. In the context of our study, we have chosen to call iteratively the model and to discard the successive optimal solutions after each call. Such a solution is linear in the number of instances. There are multiple ways to discard an optimal solution. The general idea is that a new constraint cutting the current solution is added to the model. Hence, the current optimal solution becomes infeasible for the next run. The solver can be called again and will be able to find another optimal solution. In the sake of our study, the following constraint is added to the formulation :

i∈V S ,k∈V G   j∈V S xj,k   * x i,k = 0
Its purpose is to discard every vertex of G that has been used in the current optimal solution (x ȳ) T . It means that for every vertex k of G, if there exists a vertex j of S matched to k, then x i,k equals 0 for every vertex i of S.

Experiments and results

The evaluation of subgraph isomorphism algorithms is a difficult task since it implies to have at disposal (i) some graph and subgraph datasets and (ii) the position of each pattern graph in the target graphs, i.e. the mapped vertices and edges. For graphs extracted from a real world application, this information is difficult and time consuming to be collected since the mapping has to be defined in relation to the application. As an example, for graphs representing objects in an image, defining the mapping require to consider both graphs and images. This difficulty is increased when error-tolerant isomorphism is involved. In order to overcome this difficulty, most of the papers dealing with subgraph isomorphism propose an evaluation relying on synthetic datasets, such as the well known VF dataset described in [START_REF] Cordella | Performance evaluation of the VF graph matching algorithm[END_REF] or those provided on the IAPR TC-15 website3 . However, to the best of our knowledge, all existing datasets rely on a nominal labeling and we are not aware of publicly available graph dataset with scalar or vectorial numerical attributes.

In this context, we propose in this paper a two step evaluation of the proposed algorithm. In the first step, the evaluation is led on a synthetic graph dataset. Its aim is to validate the functioning of the ILP approach and to quantify the effectiveness of the algorithm w.r.t. the size of graphs. Both exact and inexact graph matchings are considered in this part of the experiments and a performance comparison with VF2 [START_REF] Cordella | A (sub)graph isomorphism algorithm for matching large graphs[END_REF] and LAD [START_REF] Solnon | Alldifferent-based filtering for subgraph isomorphism[END_REF] algorithms is proposed. These algorithms have been chosen because they are known to be very efficient for different graph matching problems (see 2.2 for their description). In the second step, the proposed algorithm is evaluated in a real-world context, on a document analysis problem.

Experiments on synthetic data

In this subsection, we first describe the data before presenting and discussing the obtained results.

Data generation

Two sets of synthetic graphs have been generated to evaluate the exact and the substitution-tolerant subgraph isomorphism. These sets have been generated considering the same procedure. Firslty, a random graph S is generated according the Erdös-Rényi model [START_REF] Erdös | On random graphs[END_REF]. Then, a graph G 0 is created as an exact copy of S. In the case of substitution-tolerant matching, labels of G 0 can be modified by applying a noise model. Finally, G 0 is completed to form a graph G with vertex and edge insertions according the Erdös-Rényi model until a predefined size.

The informations provided during the creation and the modifications of G 0 are recorded and considered as the ground-truth information. G 0 is called the ground-truth solution. Note that in a noiseless model, there might be multiple optimal solutions, and in a noisy model, the ground-truth solution G 0 may not be the optimal solution. This procedure provides a couple of graphs (S, G). The following values of the parameters have been chosen for our experiments :

• Size of G : |V G | = n G ∈ {50, 100, 250, 500} • Size of S : |V S | = n S ∈ {10, 25, 50}
• Probability that an edge connects two vertices : p ∈ {0.01, 0.05, 0.1}

• vertex and edge labels have been randomly chosen in [-100, 100] with a uniform distribution.

Using this parameterization, two test sets have been generated :

• The first set, denoted as T 1 , contains 5 couples (S, G) generated for each combination of (n G , n S , p). In this set, no noise has been applied, so the mapping between S and G is an exact isomorphism.

• The second set, denoted as T 2 aims at evaluating the subgraph isomorphism search in presence of noise. These data have been generated using a Gaussian noise (σ = 5) applied on both vertices and edges before the graph is completed to its final size.

Obtained results

Given the two datasets T 1 and T 2 described above, two experiments have been led. They relate respectively to exact and substitution-tolerant subgraph isomorphisms.

(a) Exact subgraph isomorphism . These first experiments aim at (i) validating the ILP formulation proposed in 3.2 in the case of exact matchings and (ii) comparing the efficiency of the proposed approach w.r.t. reference approaches. In this context, the results obtained using our algorithm have been compared with those obtained with VF2 [START_REF] Cordella | A (sub)graph isomorphism algorithm for matching large graphs[END_REF] and LAD [START_REF] Solnon | Alldifferent-based filtering for subgraph isomorphism[END_REF]. For these experiments, the matching cost functions c v and c e have been defined as the Euclidean distance between the attribute values. For each of the couple (S, G) generated for each combination of (n G , n S , p), as expected, we have observed that the isomorphisms are exactly the same for all the algorithms. As one can see in this table, VF2 and LAD are clearly more efficient than the proposed ILP approach for exact matching problem. Such a result is quite natural since approaches do not rely on the same paradigm. VF and LAD algorithms rely on a decision process, whereas the proposed approach relies on an optimization process. More precisely, exact algorithms can prune the solution tree very early, at a vertex's level, since for a vertex matching, a single label difference means every solution with this matching is infeasi-ble. The algorithm we propose is by nature error-tolerant and accepts label differences, making the solution tree harder to prune. As a consequence, it is natural that it is outperformed by dedicated algorithms.

(b) Substitution-tolerant subgraph isomorphism. These second experiments on the T 2 dataset aim at validating the real contribution of the proposed approach, i.e. the ability of an ILP based approach to tackle problems where a substitution-tolerant isomorphism is required. First of all, one can note that if the procedure used to generate synthetic data guarantees that the mapping between S and G corresponds to an exact or substitution-tolerant subgraph isomorphism, it does however not ensure that this mapping is unique. Indeed, the completion of G until its final size may produce new subgraph isomorphisms, and some of them may have a lower matching cost. It is difficult to keep track of this in the case of data generation for the substitutiontolerant problem. The ground-truth information produced during the generation phase can then be only partial. However, when doing a multiple search as explained in 3.3, it is possible to check that the initial solution is in the list of returned solutions. Such tests have shown that the ground-truth solution is always in this list. Moreover, for the T 2 dataset, it is always the first one. Concerning the processing time, the results presented in table 2, compared with those of table 1 illustrate that more time is needed when an substitution-tolerant mapping is searched for. One reason is that T 1 dataset is such that there is always a feasible solution of cost 0, which is necessarily optimal, since the objective function is a sum of non-negative terms. Once this solution is identified by the Branch and Bound, the search can stop without further tree exploration. For the T 2 dataset, the optimal value is not 0 in general, thus the tree exploration may continue after finding the optimal solution, in order to certify that no better solution exists.

Comparing these results with existing approaches such as those used for exact matching is a difficult task since they have not been designed to tackle such problems. Nevertheless, as explained in 2.2, it is possible to customize them in order to make them applicable. Hence, given two thresholds t v and t e (one for the vertices, and one for the edges), two vertices (resp. edges) are considered as compatible if the distance between their attribute is lower than t v (resp. t e ). For our experiments, we have used an extended version of LAD supplied by the author of [START_REF] Solnon | Alldifferent-based filtering for subgraph isomorphism[END_REF] to evaluate such a strategy 4 experiment, since the label distribution is the same for vertices and edges, we used a unique threshold t = t v = t e . The obtained results are given in table 3. It provides the number of instances that are solved by LAD when submitted the same five queries than in table 2 by varying the value of t in {5, 10, 20} i.e in {σ, 2σ, 4σ}.

As one can see in table 3, many instances (389/540) are not solved using LAD. Two reasons explain these failures: (i) For "small" values of t, few solutions are found by the system, because of the phenomenon explained in 2.2 and illustrated by figure 1. Hence, a threshold of 5 (resp. 10, 20) only solves 9 (resp. 29, 113) of the 180 instances. (ii) For larger values of t, the number of solved instances increase. However, the problem sometimes becomes intractable because of the important number of vertices (and edges) that can be matched. Thus, the system is flooded with feasible solutions. This result has to be correlated to the density of the graphs. Hence, when the graph density increases, more instances are solved: for p = 0.01 (resp. 0.05, 0.1), 14 (resp. 65, 72) instances are solved.

Hence, the choice of the threshold values is crucial since low values can eliminate good mappings, and since large values can lead to an intractable problem. As an illustration, figure 4 shows the number of solutions and the 0.01 50 2/3 4/1 2/0 0/5 0/2 0/0 0/5 0/5 4/0 100 2/2 0/1 0/0 0/5 0/1 0/0 0/5 0/4 0/0 250 0/2 0/0 0/0 0/5 0/1 0/0 0/5 0/4 0/0 500 0/1 0/0 0/0 0/5 0/1 0/0 0/5 0/4 0/0 0.05 50 0/5 5/0 5/0 0/5 0/5 5/0 0/5 0/5 5/0 100 2/3 2/2 4/0 0/5 1/4 5/0 0/5 0/5 5/0 250 1/3 1/2 2/0 0/5 1/4 4/0 0/5 0/5 5/0 500 1/4 2/1 2/0 0/5 0/5 3/0 0/5 0/5 4/1 0.1 50 0/5 2/3 5/0 0/5 0/5 5/0 0/5 0/5 5/0 100 0/5 3/2 5/0 0/5 0/5 5/0 0/5 0/5 5/0 250 0/5 3/2 5/0 0/5 0/5 5/0 0/5 0/5 5/0 500 1/4 4/1 3/0 0/5 1/4 5/0 0/5 0/5 5/0 processing time necessary to find all the solutions according to the threshold values (the same value is considered here for both vertices and edges but as a matter of fact, they can be distinguished). As one can see, the number of compatible graphs as well as the time needed rapidly grows when the threshold increases. One can mention that all the solutions have to be sorted after this search. Moreover, when using an exact approach, there is no absolute guaranty that the optimal solution is among the found instances (as for the example of figure 1). According to us, these results illustrate the important interest to consider subgraph isomorphism as an optimization process, which is driven by the objective function under some constraints. Hence, the proposed approach is not the most efficient for all problems, but it does not need to define a threshold, and it always give the optimal solution. In the next section, we present the second part of our experiments, that concerns an application based on substitution-tolerant subgraph isomorphism for symbol detection.

Symbol detection

Symbol detection is a problem related to document analysis that aims at searching the occurrences of some reference symbols in an input document image. In the literature, this problem is tackled using either pixel based approaches [START_REF] Tabbone | Matching of graphical symbols in line-drawing images using angular signature information[END_REF][START_REF] Adam | Symbol and character recognition: application to engineering drawings[END_REF], symbol signature [START_REF] Dosch | Vectorial signatures for symbol discrimination[END_REF][START_REF] Zhang | A new vectorial signature for quick symbol indexing, filtering and recognition[END_REF] or structural approaches [START_REF] Lladós | Symbol recognition by errortolerant subgraph matching between region adjacency graphs[END_REF][START_REF] Barbu | Using bags of symbols for automatic indexing of graphical document image databases[END_REF][START_REF] Locteau | Symbol spotting using full visibility graph representation[END_REF][START_REF] Qureshi | Spotting symbols in line drawing images using graph representations[END_REF]. In the latter case, the proposed techniques theoretically allow to overcome the segmentation/recognition paradigm, but they require a subgraph isomorphism algorithm to detect the instances of the model graph in the graph describing the whole document. The remaining of this section presents how our approach for subgraph isomorphism has been applied to solve the symbol detection problem. First, the graph database is described. Then, the experimental protocol and the results obtained for multiple experiments are presented.

Graph database

The database used for this experiment is made of Region Adjacency Graphs (RAG) extracted from images of technical documents. In a RAG, vertices are associated to the regions of an image and edges are created between pairs of vertices if the corresponding regions are adjacent. The algorithm used for extracting such RAG's is fully described in [START_REF] Bodic | Symbol detection using region adjacency graphs and integer linear programming[END_REF]. Using this algorithm, vertices are labelled with a feature vector corresponding to a set of Zernike Moments (ZM) [START_REF] Teague | Image analysis via the general theory of moments[END_REF] and edges are labelled with relative scale and relative distance. Once a document image and the symbol to be searched have been described as RAG's, the symbol detection problem turns into a subgraph isomorphism problem. Moreover, this subgraph isomorphism search has to be substitution-tolerant. Indeed, due to noise on images, the labeling may differ between the graph which represents the symbol and its instance in the graph representing the whole document.

The document images used for this evaluation are extracted from the floorplan dataset [START_REF] Delalandre | Generation of synthetic documents for performance evaluation of symbol recognition; spotting systems[END_REF] 5 . This dataset is made of synthetic images representing several symbol arrangements on 10 empty architectural plan templates. Our experiments have been performed using 200 images corresponding to the 20 first images for each template. Figure 5 shows two examples of plans and the corresponding RAG's. Figure 6

Performance criteria

The search of a substitution-tolerant subgraph isomorphism results in a one-to-one mapping between every vertices and edges from the graph representing the symbol and some vertices and edges from the graph representing the whole document. In order to be assessed, the proposed mapping has to • the mapping exactly corresponds to the groundtruth (denoted as =);

• a part of the mapping corresponds to the groundtruth (denoted as ≈);

• the mapping does not correspond to the groundtruth (denoted as =);

• no mapping is proposed. This case occurs when no solution fulfills the constraints of the ILP (denoted as ∅).

When an erroneous mapping is proposed, two cases can be distinguished:

• the symbol appears on the document image (denoted as = |+);

• the symbol has no instance on the document image. (denoted as = |-).

Search of a single occurrence

The task which has been evaluated in our first experiments was to locate the most probable instance of a given symbol in a plan, i.e. the minimum cost subgraph isomorphism. This experiment has been performed on 16 symbols and 200 plans, leading to 3200 subgraph isomorphism "queries". For all these queries, the system has always proposed a feasible solution. The results are reported on table 4. They show that, among the 3200 found instances, 1719 exactly correspond to a symbol and 337 partly correspond to an actual mapping. 755 searches returned in an erroneous result which is explained by the fact that the symbol was not on the document. Finally, only 389 confusions were returned among the 2445 cases where the searched symbol should have been found. Table 4 also reveals that the performance are not equally distributed among the symbol classes. For example, symbols from class E, M or N were quite well located, whereas searches of instances of C, D or G result in numerous confusions. Two explanations can be given for these errors. On one hand, it may be noted that the region adjacency graph representation is not well suited to describe symbols C or D. Indeed, these symbols only contain two non adjacent regions. Thus, the corresponding graphs are composed of two vertices without edge. As a consequence, no topological constraint is used by the subgraph isomorphism, which leads to erroneous mappings. On the other hand, many confusions occur between F and G because the graph for symbol G is a subgraph of the graph for symbol F.

Symbol # = ≈ = |+ = |-∅ A

Search of multiple occurrences

Considering that a symbol can have several instances on the same document image, a second experiment has been dedicated to evaluate the performance of a multiple search. The algorithm was configured so that any vertex mapping in a previous solution is excluded from the search space because a region can be part of at most one symbol. For a search of 50 instances of all symbol models in the 200 plans, a perfect system should find 5609 symbol instances. Among them, the proposed approach returns exactly 3911 mappings (69.7%) and partially 1636 mappings (29.2%). The 62 symbol instances which are not found correspond to cases where two symbols from the same class, made of identical regions (e.g. symbol K composed of four triangles) are closed in the plan so that the mapping is done with regions of both occurrences. In such a case, the second occurrence cannot be found. Considering that a partial matching is sufficient to consider the symbol as detected, the overall recall is thus 99% and the overall recall is 10%. Table 5 details the results per class when 50 occurrences are considered. As one can see in this table, a significant number of false detections are made. This can be explained by the fact that the search of 50 instances has led the system to propose solutions whereas all the actual symbols were already found.

These results highlight a need for some improvements. Indeed, if the recall rate may be considered as satisfactory, the number of false detections has to be drastically reduced. This goal may be achieved by implementing a rejection strategy which is able to filter the search results according to a threshold used to stop the search. Figure 7 illustrates the results that such a strategy can produce on precision-recall curves, when varying the value of the threshold.

Learning of distance threshold

The results presented above show that it is necessary to stop the search using a threshold on the matching cost when considering multiple occurrences, in order to improve the precision of the system. As shown by figure 8, which depicts the ranges of matching costs obtained for each class of symbols for the 3200 queries, the threshold has to be tuned according to the symbol class which is considered. Four our experiments, this threshold has been learned on a subset of 20 floorplans by optimizing the F1-measure which is a tradeoff between recall and precision (see eq 3). The obtained values are highlighted as blue strokes on figure 8

Table 6 presents the rejection threshold for each class and the new values for recall and precision, obtained on 180 floorplans. The diversity of the threshold values justifies the choice to set a class dependent threshold. It might be noted that these values are somehow correlated with the size of the model graph. However the main observation is the performance evolution achieved by the use of this rejection strategy. Indeed, for each symbol class, a significant improvement in precision was obtained at the cost of a slight decrease of the recall. The overall performance of the system reaches a precision of 81% while keeping a high value for the recall (90%).

Conclusion

In this paper, an integer linear formulation has been proposed to solve the problem of substitution-tolerant subgraph isomorphism. This optimization approach enables us to find instances of a query graph into a larger one the attribute of which may differ. Results have been presented for experiments performed on synthetic graph datasets. We also report results obtained on graph-based representations extracted from architectural plans where a subgraph isomorphism corresponds to a symbol instance. For these latter, we have proposed a rejection strategy based on the learning of matching cost thresholds. This strategy improves the precision by greatly reducing false detections while keeping the good recall performance achieved by a multiple search.

The main characteristics of the proposed approach are the following. First, it is very general in the sense that it can be applied to the most general class of graphs. Indeed, it can process directed multigraphs (several edges may exist between edges, even loops). The graph can be labeled on both vertices and edges and there is no restriction considering the type of label, only a distance or a cost function to compare labels of two different vertices or edges are needed. Neither the pattern nor the target graph need to be connected. Second, in contrast to the approach by Messmer and Bunke [START_REF] Messmer | A new algorithm for error-tolerant subgraph isomorphism detection[END_REF], the graph database does not need to be preprocessed. The subgraph isomorphism search can be directly applied to two newly presented graphs. Finally, the approach presented in this paper separates the formulation of problem and the method used to solve it. The error-tolerant subgraph isomorphism is modeled as an optimization problem under constraints. The responsibility to solve this problem can be delegated to any solver able to process an ILP formulation. Such solvers are continuously developed by the combinatorial optimization community.

The work described in this paper can be pursued following several leads. First, concerning the symbol detection problem, the subgraph isomorphism approach could be applied to vector or contour-based structural descriptions of symbols and documents as the ones proposed by [START_REF] Qureshi | Spotting symbols in line drawing images using graph representations[END_REF] or [START_REF] Tabbone | A hybrid approach to detect graphical symbols in documents[END_REF], in order to overcome some of the limits of region-based descriptions. At the same time, in order to manage possible segmentation errors which may result in merged or split vertices, operators establishing distances for one-to-many or many-to-one mappings [START_REF] Sorlin | Applied Graph Theory in Computer Vision and Pattern Recognition[END_REF] should be considered. This remark could even be integrated at the isomorphism level. Indeed, the integer linear programming formulation proposed for substitution-tolerant subgraph isomorphism could be adapted to other mapping problems such as substitution-tolerant induced subgraph isomorphism or isomorphisms allowing topological transformations. Also, the overall running time of the algorithm can be improved by further customizing the ILP solver heuristics. Finally, considering the lack of public ground-truthed dataset to evaluate subgraph isomorphism in presence of graph labeled with numerical values, the ones used in this paper are available on demand and we intend to make them publicly accessible for download.

  Best solution for t = 2 → d = 2

Figure 1 :

 1 Figure 1: Example showing the difficulty of selecting the best threshold t for substitutiontolerant subgraph isomorphism. (a) Definition of S and G. Two structurally isomorphic matchings exist between S and G. (b) Solution found by a customized exact matching procedure if the distance threshold t between vertices is set to 1, which leads to a matching error of d = 4 [(l,c),(k,d),(i,e),(j,f)]. (c) Solution found by a customized exact matching procedure if t is set to 2, which leads to a matching error of d = 2 [(l,d),(k,c),(i,a),(j,b)].

Figure 3

 3 Figure 3 illustrates an output produced by the synthetic data generation in the presence of noise.

  A graph G (c) Ground-truth for the mapping between S and G.

Figure 3 :

 3 Figure 3: Illustration of the generation of synthetic data for the substitution-tolerant subgraph isomorphism search with the following parameters : n S = 3, n G = 6, p = 0.3, labels in [-100,100] and a Gaussian noise (σ = 5). The mapping cost is 24.93

Figure 4 :

 4 Figure 4: Evolution of the number of subgraph isomorphism solutions and the computation time found by VF2 and LAD according to a threshold value for the following parameters values : (n G = 250, n S = 25, p = 0.1)

  represent the 16 symbol models. The whole plan dataset contains 5609 symbol instances, with an average of 28 instances per document image. The graphs corresponding to symbol instances contain 4 vertices and 7 edges on average. As a comparison, the structural representations of the plans contain 121 vertices and 525 edges on average.

Figure 5 :

 5 Figure 5: Examples of plans from the floorplan dataset with the corresponding RAG's

Figure 6 :

 6 Figure 6: Symbol models

Figure 7 :

 7 Figure 7: Precision-recall curves per class for the search of 50 instances

Figure 8 :

 8 Figure 8: Ranges of mapping costs for good detection and errors according to the class of symbol. The stroke line represents the threshold that has been learned.

Table 1 :

 1 Table1gives the time needed to solve the five subgraph isomorphism instances for each configuration. Results obtained on T 1 for the proposed approach, VF2 and LAD. This table gives the sum of the processing time in seconds for the five solved instances.

	p	n G		10	n S = |V S | 25		50
			ILPiso vf2 lad ILPiso vf2 lad ILPiso vf2 lad
		50	0.02	0.03 0.0	0.04	0.02 0.0	0.08	0.02 0.0
	0.01	100 250 0.028 0.02 0.02 0.02 0.02 0.0	0.06 0.1	0.01 0.0 0.02 0.02	0.1 0.28	0.02 0.0 0.02 0.02
		500	0.08	0.06 0.01	0.26	0.05 0.04	0.72	0.06 0.01
		50	0.03	0.02 0.0	0.06	0.02 0.0	0.3	0.02 0.02
	0.05	100 250	0.06 0.15	0.01 0.02 0.03 0.04	0.21 0.85	0.02 0.01 0.04 0.04	0.76 4.24	0.02 0.02 0.05 0.04
		500	0.68	0.14 0.34	2.87	0.14 0.4	14.82 0.13 0.4
		50	0.05	0.02 0.01	0.22	0.02 0.01	1.28	0.02 0.02
	0.1	100 250	0.1 0.42	0.02 0.01 0.06 0.1	0.63 3.64	0.02 0.01 0.01 0.14 15.52 0.06 0.08 3.1 0.01 0.01
		500	1.90	0.24 1.26 15.33 0.22 1.33 42.33 0.24 1.25

Table 2 :

 2 Results obtained on T 2 for the proposed approach. This table gives the sum of the processing time in seconds for the five solved instances.

Table 3 :

 3 Results of LAD on the T 2 dataset for threshold values in {5, 10, 20}. The first number gives the number of solved instances among the 5 queries. The second number gives the number of instances for which LAD did not found any solution. The remaining instances are not solved by LAD.

Table 4 :

 4 Results for the search of the most probable instance of each symbol on the 200 plans of the floorplan dataset. # denotes here the number of plans which contain the symbol

		106 106	0	0	94	0
	B	160	46	76	38	40	0
	C	200	56	72	72	0	0
	D	60	0	11	49	140 0
	E	112 112	0	0	88	0
	F	130 129	1	0	70	0
	G	151	51	21	79	49	0
	H	188	40	128	20	12	0
	I	176 114	0	62	24	0
	J	192 191	1	0	8	0
	K	200 158	25	17	0	0
	L	123 123	0	0	77	0
	M	91	89	2	0	109 0
	N	180 180	0	0	20	0
	O	183 131	0	52	17	0
	P	193 193	0	0	7	0
	Total		1719 337 389	755 0

  .

	Symbol Recall (%) Precision (%)
	A	100	9
	B	99	10
	C	100	9
	D	97	1
	E	100	2
	F	100	14
	G	100	7
	H	100	5
	I	100	5
	J	100	7
	K	88	32
	L	100	12
	M	100	8
	N	100	2
	O	100	6
	P	100	28
	overall	99	10

Table 5 :

 5 Recall and precision for the search of 50 instances

	F1-mesure = 2	Precision × Recall Precision + Recall

Table 6 :

 6 Precision and recall of the symbol spotting system implementing the rejection strategy based on the maximization of the F-measure

		Matching
	Symbol	cost	Recall (%) Precision (%)
		threshold
	A	2.451	93	100
	B	3.875	75	85
	C	0.489	70	49
	D	0.889	95	5
	E	1.165	100	100
	F	2.315	100	100
	G	2.969	76	38
	H	2.710	90	100
	I	0.862	95	38
	J	1.831	96	100
	K	4.435	84	90
	L	3.513	100	98
	M	3.767	100	100
	N	1.144	100	90
	O	0.447	60	100
	P	3.625	100	100
	overall		90	81

In the remaining of the paper, the term graph denotes a directed attributed multigraph.

This kind of mapping is also called monomorphism

http://www.greyc.ensicaen.fr/iapr-tc15

We would like to thank the author for his help concerning our experiments

http://mathieu.delalandre.free.fr/projects/sesyd/