Salim Jouili
email: salim.jouili@loria.fr

Salvatore Tabbone
email: tabbone@loria.fr

Ernest Valveny
email: ernest@cvc.uab.cat

Comparing Graph Similarity Measures for Graphical Recognition ⋆

Keywords: Graph matching, Graph retrieval, Structural representation, Performance evaluation

In this paper we evaluate four graph distance measures. The analysis is performed for document retrieval tasks. For this aim, different kind of documents are used including line drawings (symbols), ancient documents (ornamental letters), shapes and trademark-logos. The experimental results show that the performance of each graph distance measure depends on the kind of data and the graph representation technique.

Introduction

In document retrieval applications, it is necessary to define some description of the document based on a set of features. These descriptions are then used to search and to determine which documents satisfy the query selection criteria. The effectiveness of a document retrieval system ultimately depends on the type of representation used to describe it. In pattern recognition, the document representation can be broadly divided into statistical and structural methods [START_REF] Bunke | Towards bridging the gap between statistical and structural pattern recognition: Two new concepts in graph matching[END_REF]. In the former, the document is represented by a feature vector, and in the latter, a data structure (e.g. graphs or trees) is used to describe objects and their relationships in the document. The classical retrieval systems are often limited to work with a statistical representation due to the need of computing distances between documents (feature vectors) or finding a representative cluster of documents. However, when a numerical feature vector is used to represent the document, all structural information is discarded although the structural representation is more powerful in terms of its representational abilities [START_REF] Bunke | Towards bridging the gap between statistical and structural pattern recognition: Two new concepts in graph matching[END_REF]. In the last decades, many structural approaches have been proposed. These approaches deal, especially, with graph-based representations. Nevertheless, dealing with graphs suffers, on the one hand from the high complexity of the graph matching problem which is a problem of computing distances between graphs, and on the other hand from the robustness to structural noise which is a problem related to the capability to cope with structural variations and differences in the size of the graph. In order to overcome this problem, several approximate graph matching methods have been proposed [START_REF] Jouili | Graph matching using node signatures[END_REF][START_REF] Lopresti | A fast technique for comparing graph representations with applications to performance evaluation[END_REF][START_REF] Papadopoulos | Structure-based similarity search with graph histograms[END_REF][START_REF] Robles-Kelly | Graph edit distance from spectral seriation[END_REF]. In this paper, our attention is focused on the comparison of different graph similarity measures in the context of document retrieval.

Graph similarity measures use different techniques to minimize the complexity and to optimize the robustness to structural noise. Robles-Kelly and al. [START_REF] Robles-Kelly | Graph edit distance from spectral seriation[END_REF] propose a spectral seriation approach to reduce the graph matching to a string edit distance in a probabilistic framework. Jouili and al. [START_REF] Jouili | Graph matching using node signatures[END_REF] simplify the problem to a bipartite graph matching by making use of node signatures. Lopresti and al. [START_REF] Lopresti | A fast technique for comparing graph representations with applications to performance evaluation[END_REF] use a probe technique to reduce the graph matching to distance between vectors. Papadopoulos and al. [START_REF] Papadopoulos | Structure-based similarity search with graph histograms[END_REF] introduce an histogram-based technique.

In this paper, we present an evaluation of these four graph distance measures on four different document data sets. We use the well-known GREC [START_REF] Riesen | Iam graph database repository for graph based pattern recognition and machine learning[END_REF] data base which consists of graphs representing symbols from architectural and electronic drawings. Here the ending points (ie corners, intersections and circles) are represented by nodes which are connected by undirected edges and labeled as lines or arcs. We have also performed a retrieval evaluation on an ornamental letters data set which contains lettrine (graphical object) extracted from digitized ancient document3 . Since one lettrine contains a lot of information (i.e. texture, decorated background, letters), the graphs are extracted from a region-based segmentation [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF] of the lettrine with a user-based parameterization technique. The nodes of the graph are represented by the regions and the edges describe their adjacency relationships. We have also evaluated the graph similarity measures on a shape data set [START_REF] Sharvit | Symmetry-based indexing of image databases[END_REF] in which the graph is extracted by making use of a skeletonizing algorithm and a delaunay triangulation of detected endpoints. Finally, the graph similarity measures are evaluated on a set of trademark-logos in which the graph is extracted by making use of an interest points detector [START_REF] Harris | A combined corner and edge detection[END_REF] and the delaunay triangulation.

The performance evaluation is performed using the Precision-Recall curves. Through this evaluation, we will examine the robustness of each graph similarity distance and this will allow us to investigate the applicability of each measure to the problem of retrieval for different kinds of documents.

Graph-based representations

Region-Based approaches have been one of the most important research issues in content-based image retrieval. Representing images at the region level cap-tures not only the local variations of regions but also their spatial organizations. Graph-based representations are widely used in region-based segmentation. To incorporate both region attributes and adjacent relationship an image is usually represented as an attributed graph. Classical image representations such as colors histograms, texture descriptors, or shape descriptions do not take into account the regions localization in the document.

Graph-based representations are used in many applications, for instance, to represent circuit diagrams [START_REF] Bunke | Attributed of programmed graph grammars and their application to schematic diagram interpretation[END_REF], for shape recognition [START_REF] Di Ruberto | Recognition of shapes by morphological attributed relational graphs[END_REF], image matching [START_REF] Li | Region correspondence for image retrieval using graphtheoretic approach and maximum likelihood estimation[END_REF][START_REF] Baeza-Yates | An image similarity measure based on graph matching[END_REF], or old document analysis [START_REF] Karray | An ancient graphic documents indexing method based on spatial similarity[END_REF]. Other works on graph-based representation [START_REF] Ambauen | Graph edit distance with node splitting and merging, and its application to diatom identification[END_REF][START_REF] Barrow | Relational descriptions in picture processing[END_REF][START_REF] Pan | Gcap: Graph-based automatic image captioning[END_REF][START_REF] Ounis | Modeling, indexing and retrieving images using conceptual graphs[END_REF], use different methods to incorporate features of the document image. The methods vary according to the characteristics of the data and the aims of the representation (i.e. matching or retrieval). Bunke [START_REF] Bunke | Attributed of programmed graph grammars and their application to schematic diagram interpretation[END_REF] illustrates an example of converting a circuit diagram to a graph by representing the lines in the circuit diagram; each graph node represents a line endpoint, corner or intersection point, and node attributes record the image coordinates (x,y) of this feature. In [START_REF] Karray | An ancient graphic documents indexing method based on spatial similarity[END_REF] the authors manipulate initial letters from old documents. They proceed by segmenting the initial letter into different information layers to obtain "Information layers of homogeneous zones". Then, each homogeneous zone of the initial letter is converted to a node of graph with two attributes: size and shape descriptions, and each edge contains two attributes: angle and distance. Baeza-Yates and al. [START_REF] Baeza-Yates | An image similarity measure based on graph matching[END_REF] also represent images as attributed graphs and adopt the graph edit distance to calculate the image distance. In another way using graphs in image analysis, Pan and al. [START_REF] Pan | Gcap: Graph-based automatic image captioning[END_REF] introduce a graph-based automatic image annotation. The authors propose a graph-based method to assign automatically keywords to an image. The main idea of this work is to represent all the images, as well as their attributes (caption words and regions) as nodes and link them according to their known association into a graph. For the task of image annotation, they use a "3-layer" graph, with one layer for image nodes, one layer for annotation term nodes, and one layer for the image regions.

In this section, we have seen that graphs can be widely used as a data structure-model in the pattern recognition domain. Moreover, most of the previous graph-based representations aim to measure some similarity between objects for recognition or retrieval tasks. This leads to the development of several similarity measures for graphs.

Graph matching measures

An important step in structural pattern recognition is the representation of documents by a graph data structure. This structural representation should provide a description of the characteristics of the images efficiently for the task under consideration (e.g. retrieval). The retrieval problem can then be addressed in the corresponding graph space without addressing the original images. The process of comparing graphs is generally referred as graph matching. Generally, given two graphs G 1 =(V 1 ,E 1 ) and G 2 =(V 2 ,E 2 ), the graph matching methods are divided into two broad categories: the first one contains exact matching methods called graph isomorphism that requires to find a one-to-one mapping f :

V 1 → V 2 such that (u,v ) ∈ E 1 if (f(u),f(v)) ∈ E 2 with |V 1 |=|V 2 |.
The second category contains inexact matching methods, where a strict correspondence among the nodes or the edges of the two graphs can not be found. Therefore, in these cases no isomorphism can be expected between both graphs, and the graph matching does not consist in finding the exact matching but the best matching between them. To perform such a structural matching, various formalisms have been proposed, using error-tolerant methods based on continuous optimization [START_REF] Neuhaus | Edit distance-based kernel functions for structural pattern classification[END_REF], quadratic programming, and spectral decomposition of graph matrices [START_REF] Robles-Kelly | Graph edit distance from spectral seriation[END_REF]. Other methods try to characterize the properties of graphs using a vector-based representation in order to profit from the existing vector measures [START_REF] Lopresti | A fast technique for comparing graph representations with applications to performance evaluation[END_REF][START_REF] Jouili | Graph matching using node signatures[END_REF][START_REF] Papadopoulos | Structure-based similarity search with graph histograms[END_REF]. Most of the inexact graph matching measures are based on some sort of edit operations. The basic idea is to define the similarity of graphs based on the effort needed to make the graphs identical. This is an extension of the well known string edit distance [START_REF] Levenshtein | Binary codes capable of correcting deletions, insertions, and reversals[END_REF] to the graph edit distance (GED) [START_REF] Sanfeliu | A distance measure between attributed relational graphs for pattern recognition[END_REF]. For a review of graph similarity measures we refer the readers to [START_REF] Conte | Thirty years of graph matching in pattern recognition[END_REF][START_REF] Bunke | Recent developments in graph matching[END_REF].

The matching methods selected for our evaluation belong to different formalisms. The spectral technique proposed by the Robles-Kelly's method [START_REF] Robles-Kelly | Graph edit distance from spectral seriation[END_REF] has proven to obtain good performance results. The graph matching based on node signature [START_REF] Jouili | Graph matching using node signatures[END_REF] uses a local decomposition of graphs and an assignment method to carry out an optimum node-to-node correspondence. Papadopoulos and al. [START_REF] Papadopoulos | Structure-based similarity search with graph histograms[END_REF] provide a histogram-based representation for graphs to compute the edit distance between graphs as a sequence of three different primitive operations. Finally, using the new concept of probe, Lopresti [START_REF] Lopresti | A fast technique for comparing graph representations with applications to performance evaluation[END_REF] introduces the graph probing which is characterized by its rapidity.

Graph edit distance from spectral seriation

Robles-Kelly and al. [START_REF] Robles-Kelly | Graph edit distance from spectral seriation[END_REF] use a spectral method to represent graphs by strings, and then the similarity of graphs is measured according to the edit distance of strings in a probabilistic framework. The graph edit distance is the cost of the shortest edit path in an edit lattice for transforming the data graph into the model. The rows and columns of edit lattice are indexed by two strings Y={y 1 ,y 2 ,,y |VD| } for data graph G D =(V D ,E D ) and X={x 1 ,x 2 ,,x |VM | } for the model graph G M =(V M ,E M ), with null symbol ε, and V D and E D being the point set and the edge set of the data graph. The problem of computing the edit distance is posed as that of finding the least expensive path

Γ * = γ 1 , γ 2 , ..., γ k , , γ L from (y 1 ,x 1 ) to (y |VD | ,x |VM | ) through the edit lattice based on the Levenshtein distance. Each state γ k ∈ (V D ∪ ε) × (V M ∪ ε) of the edit path is a Cartesian pair.
Then cost functions are defined for elementary matches, according to the cost edit path Γ * (i.e., graph edit distance) computed using the following equation:

d(X, Y ) = C(Γ * ) = γ k ∈Γ η(γ k → γ k+1 ) (1)
where

η(γ k → γ k+1 ) = -(lnP (γ k |φ * X (x i ), φ * Y (y j ))+lnP (γ k+1 |φ * X (x i+1 ), φ * Y (y j+1 ))+ lnR k,k+1 ), and the edge compatibility coefficient R k,k+1 is R k,k+1 = P (γ k |γ k+1 ) P (γ k )P (γ k+1 ) =                        ρ M ρ D if γ k → γ k+1 is a diagonal transition on the edit lattice ρ M if γ k → γ k+1 is a vertical transition on the edit lattice ρ D if γ k → γ k+1 is a horizontal transition on the edit lattice 1 if y j = ε or x i = ε and y j+1 = ε or x i+1 = ε P (γ k |φ * X (x i ), φ * Y (y j )) =        1 √ 2πσ exp{-1 2σ 2 (φ * X (x i ) -φ * Y (y j )) 2 } if y j = ε and x i = ε α if y j = ε and x i = ε
where ρ M and ρ D are respectively the edge densities of the graphs G M and G D (ρ M = |VM | 2 EM ) and φ * X and φ * Y are, respectively, the leading eigenvectors of the adjacency matrices for the graph G M and G D . In the remainder, we denote this graph matching technique by GEDSS.

Graph matching based on node signatures

Jouili and al. [START_REF] Jouili | Graph matching using node signatures[END_REF] propose a new algorithm for matching and computing the distance between graphs. This approach is based on node signatures notion. In order to construct a signature for a node in an attributed graph, all available information into the graph and related to this node is used. The collection of these informations should be refined into an adequate structure which can provides distances between different node signatures. In this perspective, the node signature is defined as a set composed by four subsets which represent the node attribute, the node degree and the attributes of its adjacent edges and the degrees of the nodes on which these edges are connected. Given a graph G=(V,E,α,β), the node signature of n i ∈ V is defined as follows:

γ(n i ) = α i , θ(n i ), {θ(n j )} ∀ij∈E , {β ij } ∀ij∈E
where α i the attribute of the node n i .

θ(n i ) the degree of n i .

-{θ(n j )} ∀ij∈E the degrees set of the nodes adjacent to n i .

-{β ij } ∀ij∈E the attributes set of the incident edges to n i .

Then, to compute a distance between node signatures, the Heterogeneous Euclidean Overlap Metric (HEOM) is used. The HEOM uses the overlap metric for symbolic attributes and the normalized Euclidean distance for numeric attributes. Next the similarities between the graphs is computed: firstly, a definition of the distance between two sets of node signatures is given. Subsequently, a matching distance between two graphs is defined based on the node signatures sets. Let S γ be a collection of local descriptions, the set of node signatures S γ of a graph g=(V,E,α,β) is defined as :

S γ ( g ) = γ(n i ) | ∀n i ∈ V
Let A=(V a ,E a ) and B=(V b ,E b ) be two graphs. And assume that φ : S γ (A) → S γ (B) is a function. The distance d between A and B is given by ϕ which is the distance between S γ (A) and S γ (B)

d(A, B) = ϕ(S γ (A), S γ (B)) = min φ γ(ni)∈Sγ (A) d nd (γ(n i ), φ(γ(n i )))
The calculation of the function ϕ(S γ (A), S γ (B)) is equivalent to solve an assignment problem, which is one of the fundamental combinatorial optimization problems. It consists of finding a maximum weight matching in a weighted bipartite graph. This assignment problem can be solved by the Hungarian method. The permutation matrix P, obtained by applying the Hungarian method to the cost matrix, defines the optimum matching between two given graphs. In the remainder, we denote this graph matching technique by GMNS.

Graph probing approach

Lopresti and al. [START_REF] Lopresti | A fast technique for comparing graph representations with applications to performance evaluation[END_REF] introduce the paradigm of graph probing. This technique consist on using a probe into the graphs to determine some particular information. The measure of similarity between two graphs is an L1 norm distance of the two corresponding vectors. For the construction of vectors, Lopresti present three classes of construction each one led by a question, Class 0: "How many vertices with degree n are present in graph G = (V,E)? ", Class 1: "How many vertices with in-degree m and out-degree n are present in G? ", Class2 : "How many vertices labeled as att are present in G? ". The use of such class depends on the type of graph.

Therefore, for each graph, a representative vector is computed and the corresponding graph distance. Concretely, let G = (V,E) be an undirected graph, the vector associated to G is: PR(G)≡(n 0 ,n 1 ,n 2 , ...) where

n i =|{ v in V | deg(v )=i}|.
So the distance between two graphs is L 1 (PR1,PR2). In the remainder, we denote the graph probing technique by GP.

Graph histogram approach

Papadopoulos and al. [START_REF] Papadopoulos | Structure-based similarity search with graph histograms[END_REF] present a similarity measure for graphs, which is based on the concept of edit operations. They propose three different primitive operations, which are vertex insertion, vertex deletion and vertex update. While vertex insertions or deletions have a trivial meaning, the update operation is needed to insert or delete edges incident to a vertex. Additionally they introduce the degree sequence of a graph, i.e. the non-increasing sequence of the degrees of vertices in a graph. The similarity distance between two graphs is defined as the minimum number of primitive operations which are required so that the two graphs have the same degree sequence. To calculate the similarity measure, the sorted graph histogram is introduced, which is a histogram of the degrees of the vertices in a graph. Papadopoulos and al. show also that the L 1 -distance between two sorted graph histograms defines their similarity distance. Additionally it is proven that the similarity distance satisfies the metric properties. In some cases, the sorted degree histograms of the graphs in a database are of different dimensionality if not all graphs are of the same order. To allow the use of index structures for vector spaces, the authors introduce a histogram folding technique to achieve a constant dimensionality of the histograms for all graphs. In the remainder, we denote this method by GH.

Table 1 provides a description of the selected graph similarity measures. In this table, we show the capability of each graph similarity measure to deal with labeled or unlabeled graphs and it provides a node-to-node matching.

Handle unlabeled graphs

Explicit node-tonode matching Robles-Kelly [START_REF] Robles-Kelly | Graph edit distance from spectral seriation[END_REF] no yes no Jouili [START_REF] Jouili | Graph matching using node signatures[END_REF] yes yes yes Lopresti [START_REF] Lopresti | A fast technique for comparing graph representations with applications to performance evaluation[END_REF] yes yes no Papadopoulos [START_REF] Papadopoulos | Structure-based similarity search with graph histograms[END_REF] no yes no

Experimental results

In this section, we provide a performance comparison of the graph similarity measures described above. In addition, even if the statistical/structural approaches comparison is not the aim of this paper, we also use the generic Fourier descriptor (GFD) well known for its good performance [START_REF] Zhang | Shape-based image retrieval using generic fourier descriptor[END_REF] to show the general behavior of structural approaches vs a statistical one. In GFD, feature vectors are created from images by extracting information in the frequency domain. This statistical descriptor is invariant to rotation and scaling. In our experiments, we use the Euclidean distance to compute the distance between images represented by GFD feature vectors. Four graphic databases have been used to perform the comparison study. The precision/recall curves are used to measure retrieval performances. The leave-one-out protocol is used to provide precision/recall curves.

Data sets

The graph retrieval tasks considered in this paper includes the retrieval of line drawings (symbols), ancient documents (ornamental letters), the set of trademark-logos and LEMS shape database. Figure 1 represents samples for each database used. Table 2 provides a description of the characteristics of the used graph data sets. Each graph data set is described by the maximum number and the average of nodes and edges (max nodes/edges and φ nodes/edges). Let us recall that all the graphs used in this paper are weighted graphs. That is, there is no labels attached to the nodes, but each edge is weighted by a unique numeric label.

Results analysis

The results of our experiments for these four databases with the four graph matching measures are presented in figure 2.

From the precision-recall curves, we can remark that the performance of the graph matching methods depend on the databases and more particularly the description we put in the graph. For the GREC database, the matching measures (GP, GH and GMNS) that use simple structural modification perform similarly and better than the GEDSS method which use a string representation for graphs. We realize that for graphs with low edge and node densities (as the case of the GREC database) the string-based representation is not discriminant. In addition, the GMNS method provides a performance peak for low recall values, and it joins the performance of the GP and GH methods for high recall values. The discrimination of the node signatures provides a good robustness for this kind of database.

From the results provided on the Lettrine database, we see that all the distance measures provide similar results with a little less performance for the GP technique. This may be explained by the fact that the different methods produce a quite similar response to the structural errors between the graphs used to represent the ornamental letters. In the other way, one can conclude that this kind of graph representation (region adjacency graph) of the ornamental letter is more or less robust to different graph matching methods.

In the case of the shape database, the performance of the graph probing fails clearly in comparison with other distance measures. It seems that the probe of the node degree is not a good discriminating feature for this database which presents important structural errors between graphs in different classes. Further, the GEDSS method which has shown previously good results for similar databases (see [START_REF] Robles-Kelly | Graph edit distance from spectral seriation[END_REF]), provides the better retrieval results. For the logo database, all the distance measures provide similar behaviors. Here, the graph probing keeps the leader position among the other distances. In addition, the provided results of all the distance measures are particularly better in comparison with the other databases. This may be due to the suitable graph representation used for this database. We can think that the graph representation approaches used for other databases is not necessary the most suitable. In addition, different distance measures provide quite similar results for a given graph representation as the case of the Ornamental letters database. From all these results, we can remark that the GP and GEDSS methods are more sensitive to the representation we put in the graph.

In addition, the GFD descriptor outperforms the results of all the graph similarity measures for the Shape database. However, for the Ornamental letters and the Logo databases in which the structural information is more important we remark that the structural approaches provide better results.

Conclusion and perspectives

In this paper we have compared the performance of four graph matching methods for graph retrieval with different kind of document databases. The evaluation is performed using Precision rate against Recall rate. Our experimental results show that the performance of each graph distance measure depends on the databases and the approaches are also more and less robust to the variability of the representation. That is to say, a given graph distance can provide a good performance for one database and poor performance for an other database. Moreover, for a good graph representation we can remark that the performances of different graph matching methods are quite similar. In future works we want to study the behavior of these methods against the representation we put in the graph and the type of database.

Fig. 1 .

 1 Fig. 1. Samples from: (a) GREC database, (b) Ornamental letters database, (c) Shape database, (d) Logo database

Fig. 2 .

 2 Fig. 2. Precision-Recall curves on: (a) GREC database, (b) Ornamental letters database, (c) Logo database, (d) Shape database

Table 1 .

 1 A summarization of the selected graph similarity measures

	Handle	labeled
	graphs

Table 2 .

 2 Description of the four graph data sets

		max nodes max edges φ nodes φ edges
	GREC	24	29	11.54	11.6
	Ornamental Letter	178	4314	97.6	1779.6
	Shape	73	2592	29.1	471.8
	Logo	292	802	102.5	264.9

Provided by the CESR -University of Tours on the context of the ANR Navidomass project http://l3iexp.univ-lr.fr/navidomass/

Provided by the CESR -University of Tours on the context of the ANR Navidomass project http://l3iexp.univ-lr.fr/navidomass/

⋆ This work is partially supported by the French National Research Agency project NAVIDOMASS referenced under ANR-06-MCDA-012 and Lorraine region.