Sofiane Lagraa

Hamida Seba
email: hamida.seba@univ-lyon1.fr

Riadh Khennoufa

Abir M'baya

Hamamache Kheddouci

A Distance Measure for Large Graphs based on Prime Graphs

Keywords: Graph similarity, Graph decomposition, Quotient graph, Prime graph, Edit distance, Graph probing

Graphs are universal modeling tools. They are used to represent objects and their relationships in almost all domains: they are used to represent DNA, images, videos, social networks, XML documents, etc. When objects are represented by graphs, the problem of their comparison is a problem of comparing graphs. Comparing objects is a key task in our daily life. It is the core of a search engine, the backbone of a mining tool, etc.

Nowadays, comparing objects faces the challenge of the large amount of data that this task must deal with. Moreover, when graphs are used to model these objects, it is known that graph comparison is very complex and computationally hard especially for large graphs.

So, research on simplifying graph comparison gained in interest and several solutions are proposed. In this paper, we explore and evaluate a new solution for the comparison of large graphs. Our approach relies on a compact encoding of graphs called prime graphs. Prime graphs are smaller and simpler than the original ones but they retain the structure and properties of the encoded graphs. We propose to approximate the similarity between two graphs by comparing the corresponding prime graphs. Simulations results show that this approach is effective for large graphs.

Introduction

It is well established that graphs are an effective and major way of representing objects in various domains and applications mainly those related to pattern recognition such as computer vision, data mining, biology, etc. A graph G = (V, E) is a representation tool composed of a set of vertices V and a set of edges E with the cardinalities |V (G)| = n and |E(G)| = m where n is called the order of the graph and m its size. The set of edges E is a subset of V × V such that (u, v) ∈ E means that vertices u and v are connected. Usually, a finite number of labels are associated with vertices and edges. So, in the graph representation, the vertices represent objects and the edges represent relations between these objects. The eventual labels represent objects' properties. When graphs are used to represent objects, the problem of comparing these objects turns into determining the similarity between the corresponding graphs.

Comparing graphs with a low computational cost and a high degree of precision remains a challenging issue despite years of investigations. Nowadays, with the big data challenge this topic is essential more than ever.

Graph comparison approaches are generally classified into two categories: exact approaches and inexact or fault-tolerant approaches. Exact approaches refer to the methods used to find out if two graphs are the same. The common related problems include graph isomorphism, sub-graph isomorphism and the maximum common subgraph [START_REF] Bunke | Recent advances in graph-based pattern recognition with applications in document analysis[END_REF][START_REF] Conte | Thirty Years of Graph Matching in Pattern Recognition[END_REF][START_REF] Mckay | Practical graph isomorphism[END_REF][START_REF] Ullmann | An Algorithm for Subgraph Isomorphism[END_REF]. In these problems we look generally for an exact mapping between the vertices and edges of a query graph and the vertices and edges of a target graph.

Fault-tolerant graph comparison aims generally to compute a distance between the compared graphs. This distance measures how much these graphs are similar and help to deal with noise and distortion that are introduced during the process needed to model objects by graphs. The different stages of image encoding is perhaps the most illustrative example of such noise that graph comparison must deal with. Fault-tolerant graph comparison is also useful for search/rank based applications where a distance between the compared objects is needed. In some applications, graph similarity measures are intended to compute relatively suboptimal distances [START_REF] Conte | Thirty Years of Graph Matching in Pattern Recognition[END_REF] that are compensated by a large reduction of the computational complexity of the comparison process. Several graph similarity measures have been proposed in the literature and several approaches have been used including genetic algorithms [START_REF] Khoo | Multiple relational graphs mapping using genetic algorithms[END_REF][START_REF] Ponnuthurai | Structural pattern recognition using genetic algorithms[END_REF], neural networks [START_REF] Micheli | Neural network for graphs : A contextual constructive approach[END_REF], the theory of probability [START_REF] Christmas | Structural matching in computer vision using probabilistic relaxation[END_REF][START_REF] Myers | Bayesian graph edit distance[END_REF], clustering techniques [START_REF] Carcassoni | Weighted graph-matching using modal clusters[END_REF][START_REF] Sanfeliu | Clustering of attributed graphs and unsupervised synthesis of function-described graphs[END_REF], spectral methods [START_REF] Robles | A riemannian approach to graph embedding[END_REF][START_REF] Umeyama | An eigen decomposition approach to wighted graph mathcing problems[END_REF], decision trees [START_REF] Messmer | Efficient Graph Matching Algorithms for Preprocessed Model Graphs[END_REF][START_REF] Messmer | A decision tree approach to graph and subgraph isomorphism detection[END_REF], etc. We refer the reader to [START_REF] Bunke | Recent Advances in Graph Matching[END_REF][START_REF] Bunke | Recent advances in graph-based pattern recognition with applications in document analysis[END_REF][START_REF] Conte | Thirty Years of Graph Matching in Pattern Recognition[END_REF][START_REF] Gallagher | Matching Structure and Semantics: A Survey on Graph-Based Pattern Matching[END_REF] for more exhaustive surveys. We focus here mainly on similarity measures that try to extend to graphs some of the properties defined in metric spaces. Definition 1. A metric space is an ordered pair (M, d) where M is a set and d is a metric on M , i.e., a function d : M × M -→ R such that for any x, y ∈ M , the following holds:

• d(x, y) ≥ 0 (non-negativity),

• d(x, y) = 0 iff x = y (uniqueness),

• d(x, y) = d(y, x) (symmetry) and • d(x, z) ≤ d(x, y) + d(y, z) (triangle inequality).

Perhaps, the most referenced metric is edit distance which defines the similarity of graphs by the minimum costing sequence of edit operations that convert one graph into the other [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].

An edit operation is either an insertion, a suppression or a re-labeling of a vertex or an edge in the graph. A cost function associates a cost to each edit operation. Figure 1 shows an example of edit operations that are necessary to get the graph G 2 from G 1 with the suppression of two edges and a vertex and the relabeling of two vertices. Graph edit distance is a flexible graph similarity measure which is applicable to various kind of graphs [START_REF] Ambauen | Graph edit distance with node splitting and merging and its application to diatom identification[END_REF][START_REF] Bunke | Inexact graph matching for structural pattern recognition[END_REF][START_REF] Neuhaus | An Error-Tolerant Approximate Matching Algorithm for Attributed Planar Graphs and Its Application to Fingerprint Classification[END_REF][START_REF] Robles | Graph Edit Distance from Spectral Seriation[END_REF][START_REF] Sanfeliu | A distance measure between attributed relational graphs for pattern recognition[END_REF]. It also defines a common theoretical framework that allows comparing different approaches of graph comparison. In fact, Bunke showed in [START_REF] Bunke | On a relation between graph edit distance and maximum common subgraph[END_REF] that under a particular cost function, graph edit distance computation is equivalent to the maximum common subgraph problem. In [START_REF] Bunke | Error correcting graph matching: On the influence of the underlying cost function[END_REF], the same author shows that the graph isomorphism and subgraph isomorphism problems can be reduced to graph edit distance. However, computing graph edit distance suffers from two main drawbacks:

1. A high computational complexity. The problem of computing graph edit distance is NPhard in general [START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF]. The most known method for computing the exact value of graph edit distance is based on A * [START_REF] Hart | A Formal Basis for the Heuristic Determination of Minimum Cost Paths[END_REF] which is a best first search algorithm where the search space is organized as a tree. The root of the tree is the starting point of the algorithm. The internal vertices correspond to partial solutions and leaves represent complete solutions.

2. The difficulty related to defining cost functions [START_REF] Neuhaus | Automatic learning of cost functions for graph edit distance[END_REF].

The first drawback motivated several approximating solutions to compute graph edit distance.

A comprehensive survey on graph edit distance and the approaches proposed to compute it can be found in [START_REF] Gao | A survey of graph edit distance[END_REF]. We focus here on three independent but similar works that approximate the edit distance of two graphs by computing the edit distance between subgraphs of these graphs [START_REF] Raveaux | A graph matching method and a graph matching distance based on subgraph assignments[END_REF][START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF][START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF]. In [START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF], the authors introduce an novel method to compute an upper and lower bounds for the edit distance between two graphs in polynomial time. This method consists to use star representations of graphs and edit distance between stars defined as follows:

Definition 2.

[63] A star structure s is an attributed, single-level, rooted tree which can be represented by a 3-tuple s = (r, L, ℓ), where r is the root vertex, L is the set of leaves and ℓ is a labeling function. Edges exist between r and any vertex in L and no edge exists among vertices in L.

Definition 3. [START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF] Given two star structures s 1 and s 2 , the edit distance between s 1 and s

2 λ(s 1 , s 2 ) = T (r 1 , r 2 ) + d(L 1 , L 2 )
where

T (r 1 , r 2 ) = 0 if ℓ(r 1 ) = ℓ(r 2 ), 1 otherwise. d(L 1 , L 2 ) = ||L 1 | -|L 2 || + M(L 1 , L 2 ) M(L 1 , L 2 ) = max{|Ψ L1 |, |Ψ L2 |} -|Ψ L1 ∩ Ψ L2 | Ψ L is the multiset of vertex labels in L.
The authors define the distance between two multisets of star structures. Subsequently, they define the mapping distance between two graphs based on the distance between their star representations.

Similarly to the work of [START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF], the authors of [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF] define a mapping distance between two graphs based on the distance between their local structures. Each local structure contains a vertex and its incident edges (i.e., a star structure without the leaves). In [START_REF] Raveaux | A graph matching method and a graph matching distance based on subgraph assignments[END_REF], the authors describe a more general framework for this approach where the subgraphs are also stars. In this approach, the authors consider edge labels and the distance between sub-graphs may be different from editdistance. This distance is given by the minimum-weight subgraph matching between the query and target graphs with respect to a cost function.

A relatively resembling distance, that does not use edit operations, is also defined in [START_REF] Jouili | Attributed graph matching using local descriptions[END_REF] where a different representation of the star structure is used. In this similarity measure, the star structure is called node signature and is represented by a vector containing the label of the vertex, its degree, and the set of labels of its incident edges. A distance between two node signatures is also defined and the distance between two graphs is then defined as an assignment problem in the matrix containing the distances between nodes signatures of the two compared graphs.

In [START_REF] Yahiaoui | Coloring based approach for matching unrooted and/or unordered trees[END_REF], the authors present an extension of the similarity measure defined in [START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF] that ensures a better execution time. In this solution, the obtained subgraphs may be stars or bi-stars and are obtained by a graph coloring algorithm. However, this algorithm can be used only for trees.

In [START_REF] Zhao | A Partition-Based Approach to Structure Similarity Search[END_REF], the authors point-out the redundancy and the fixed-size of the substructures used in the aforementioned methods and propose a new approach that use variable-size non-overlapping substructures.

To overcome the second drawback and avoid the definition of edit costs, similarity measures that do not use edit operations are also proposed. In [START_REF] Bunke | A graph distance metric based on the maximal common subgraph[END_REF], the authors propose a graph distance measure that is based on the maximal common subgraph of two graphs and prove that it is a metric, i.e., the measure satisfies the four properties of a usual metric namely: non-negativity, uniqueness, symmetry and triangle inequality. However, computing the maximal common subgraph of two graphs has a high computational complexity [START_REF] Bunke | A graph distance metric based on the maximal common subgraph[END_REF]. For this reason, Raymond et al. [START_REF] Raymond | RASCAL: Calculation of Graph Similarity using Maximum Common Edge Subgraphs[END_REF] propose a modified version of the measure defined in [START_REF] Bunke | A graph distance metric based on the maximal common subgraph[END_REF] where an initial screening process determines whether it is possible for the measure of similarity between the two graphs to exceed a minimum threshold for which it is acceptable to compute the maximum common subgraph. This screening process is based on computing graph invariants. Graph invariants have been efficiently used to solve the graph comparison problem in general and the graph isomorphism problem in particular. They are used for example in Nauty [START_REF] Mckay | Practical graph isomorphism[END_REF] which is one of the most efficient algorithm for graph and subgraph isomorphism testing. A vertex invariant, for example, is a number i(v) assigned to a vertex v such that if there is an isomorphism that maps

v to v ′ then i(v) = i(v ′ ).
Examples of invariants are the degree of a vertex, the number of cliques of size k that contain the vertex, the number of vertices at a given distance from the vertex, etc. Graph invariants are also the basis of graph probing [START_REF] Daniel | Comparing Semi-Structured Documents via Graph Probing[END_REF] where a distance between two graphs is defined as the norm of their probes. Each graph probe is a vector of graph invariants.

In [START_REF] Wallis | Graph distances using graph union[END_REF], the distance metric based on the maximum common subgraph defined in [START_REF] Bunke | A graph distance metric based on the maximal common subgraph[END_REF] is extended by a proposal to define the problem size with the union of the two compared graphs rather than the larger of the two graphs used in [START_REF] Bunke | A graph distance metric based on the maximal common subgraph[END_REF].

In [START_REF] Xiao | Structurebased graph distance measures of high degree of precision[END_REF], the authors show that we can evaluate graph distance with a high degree of precision by considering complex graph sub-structures in the distance. In fact, in some applications such as analysis of protein interaction graphs, some sub-structures of these graphs represent certain functional modules of cells or organisms. Hence, comparing these graphs in terms of substructure information is biologically meaningful [START_REF] Xiao | Structurebased graph distance measures of high degree of precision[END_REF]. The authors defined a new metric based on the concept of Structure Abundance Vector. Each element of a Structure Abundance Vector of a graph G contains the size of an occurrence of a predefined sub-structure in G. The Structure Abundance Vector is a generalization of the concept of graph invariants.

More recently, kernel based similarity measures are also proposed [START_REF] Borgwardt | Shortest-path kernels on graphs[END_REF][START_REF] Bunke | Recent advances in graph-based pattern recognition with applications in document analysis[END_REF][START_REF] Gartner | On graph kernels: Hardness results and efficient alternatives[END_REF][START_REF] Haussler | Convolution kernels on discrete structures[END_REF][START_REF] Neuhaus | A convolution edit kernel for error-tolerant graph matching[END_REF][START_REF] Neuhaus | A Random Walk Kernel Derived from Graph Edit Distance[END_REF]. The main idea is also to define similarity of graphs based on the similarity of substructures of these graphs.

In this work, we investigate a novel approach for comparing graphs. We propose a new distance measure to approximate the similarity between graphs. The key idea of our approach is simplifying the processing of large graphs by using a compact encoding of the graphs obtained by modular decomposition. Modular decomposition is a way of representing graphs that allows to encapsulate the contents of the graph into simpler graphs that are prime graphs. This means that they can not be further compacted by the use of modular decomposition. An earlier work that uses modular decomposition to compare graphs is described in [START_REF] Abbas | A Module-based Approach for Structural Matching of Process Models[END_REF]. However the approach does not use prime graphs. It focuses mainly on re-defining the concept of module or meaningful substructure in the context of business process graphs. In the next section of this paper, we present the definition of modular decomposition and prime graphs. We also present the basic notations used throughout the paper. In Section 3, we define the prime graph based distance and describe how to compute it. Then, in Section 4, we analyze the proposed approach and show that this distance is a pseudo-metric. Section 5 investigates the application of this distance by performing comprehensive experimental studies over various datasets. Section 6 brings our remarks concluding the paper.

Preliminaries

In this section, we present the main concepts we use to define our similarity measure: quotient graphs, prime graphs and modular decomposition. We will use the notations summarized in Table 1 in the remaining of the paper. undirected unlabeled graph with V its vertex set and E its edge set

G = (V, E, f ) undirected vertex labeled graph, f is a labeling function V (G) vertex set of the graph G E(G) edge set of the graph G G the complement of the graph G deg(v) degree of vertex v ∆(G) the greatest vertex degree in graph G G[X]
the subgraph of G induced by the set of vertices X P(G) prime graph of G T 1 L1-norm of vector T .

Modular Decomposition and Quotient Graphs

Graph decomposition refers generally to a kind of graph representations that aim to highlight regular or meaningful structures within the graph such as cycles, cliques, etc. Graph decompositions give a readable view of the structure of a graph and it can help to solve efficiently complex problems on graphs. Modular decomposition is one of the most known graph decompositions [START_REF] Habib | A survey of the algorithmic aspects of modular decomposition[END_REF]. It was introduced by Gallai [START_REF] Gallai | Transitiv orientierbare graphen[END_REF] to solve optimization problems. It was also used to recognize some graph classes [START_REF] Möhring | Algorithmic aspect of the substitution decomposition in optimization over relation, set system and boolean function[END_REF][START_REF] Möhring | Algorithmic aspects of comparability graphs and interval graphs[END_REF][START_REF] Spinrad | Efficient Graph Representation[END_REF]. For a survey of applications of modular decomposition see [START_REF] Dahlhaus | Efficient and practical modular decomposition[END_REF][START_REF] Gallai | Transitiv orientierbare graphen[END_REF][START_REF] Möhring | Algorithmic aspect of the substitution decomposition in optimization over relation, set system and boolean function[END_REF]. Modular decomposition generates a representation of a graph that highlights groups of vertices that have the same neighbors outside the group. These subsets of vertices are called modules.

Definition 4. A module of a graph G = (V, E) is a set M ⊆ V of
vertices where all vertices in M have the same neighbors in V M .

The empty set, the singletons, and the vertex set V (G) satisfy the definition of a module, they are called trivial modules. A graph that has only trivial modules is called a prime graph. We distinguish two kind of modules [START_REF] Dahlhaus | Efficient and practical modular decomposition[END_REF][START_REF] Möhring | Algorithmic aspect of the substitution decomposition in optimization over relation, set system and boolean function[END_REF]:

• Weak module: A module is weak if its overlaps another module. A module M 1 overlaps another module M 2 if M 1 ∩ M 2 = ∅, M 1 M 2 = ∅ and M 2 M 1 = ∅.
• Strong module: A module is strong if it does not overlap any other module. A strong module can however contain other strong modules. A strong module that is not contained by any other module is a maximal strong module.

The graph of Figure 2 contains only strong modules as all its modules do not overlap.

Two strong modules M 1 and M 2 are either adjacent or non adjacent [START_REF] Möhring | Algorithmic aspect of the substitution decomposition in optimization over relation, set system and boolean function[END_REF]. M 1 and M 2 are adjacent if every vertex of M 1 is adjacent to every vertex of M 2 and nonadjacent if no vertex of M 1 is adjacent to any vertex of M 2 [START_REF] Möhring | Algorithmic aspect of the substitution decomposition in optimization over relation, set system and boolean function[END_REF].

In Figure 2, modules {c, b} and {l, m} are nonadjacent while modules {c, b} and {d, e, f, g} are adjacent.

We consider the partition P of the vertex set V of a graph G = (V, E) where the elements of the partition are maximal strong modules. The relations of adjacency between the elements of the partition P, i.e., strong modules, constitute a new graph, the quotient graph G/P, whose vertices are the elements of the partition P. If P is a nontrivial modular partition, i.e. P = V and P = {{x}, x ∈ V }, then G/P is a compact representation of all the edges that have endpoints in different partition classes of P [START_REF] Möhring | Algorithmic aspect of the substitution decomposition in optimization over relation, set system and boolean function[END_REF]. For each partition class X in P, the subgraph G[X] induced by X is called a factor and gives a representation of all edges with both endpoints in X. Therefore, the edges of G can be reconstructed given only the quotient graph G/P and its factors [START_REF] Möhring | Algorithmic aspect of the substitution decomposition in optimization over relation, set system and boolean function[END_REF]. The term prime graph comes from the fact that a prime graph has only trivial quotients and factors [START_REF] Dahlhaus | Efficient and practical modular decomposition[END_REF].

The modular decomposition is a unique decomposition of the vertices of a graph into nested strong modules [START_REF] Dahlhaus | Efficient and practical modular decomposition[END_REF]. A strong module M of G can take one of the following types:

• Prime: Both, G[M ] and G[M ] are connected. • Series: All strong modules contained by M are adjacent to each other in G[M ]. G[M ] is not connected. • Parallel: All strong modules contained by M are non-adjacent to each other in G[M ]. G[M ] is not connected.
So, strong modules allow a compact encoding of a graph by replacing each module by a unique vertex. The quotient graph that results from recursively compacting all the strong modules is a prime graph. We will denotes such graph by P(G) for a given graph G. (d,e,f,g) h P(S(i,j),k) P(l,m) (f) We consider the graph that corresponds to the final quotient graph obtained by compacting all the strong modules1 and we call this graph the prime graph. Each vertex of this graph is a maximum strong module which may contain other nested strong modules.

Modular decomposition has been extensively studied by many authors [START_REF] Dahlhaus | Efficient and practical modular decomposition[END_REF][START_REF] Gallai | Transitiv orientierbare graphen[END_REF][START_REF] Habib | A survey of the algorithmic aspects of modular decomposition[END_REF][START_REF] Möhring | Algorithmic aspect of the substitution decomposition in optimization over relation, set system and boolean function[END_REF][START_REF] Quaddoura | Classical graphs decomposition and their totally 2010 decomposable graphs[END_REF]. Several algorithms that compute the modular decomposition of a graph are proposed in the literature [START_REF] Habib | A simple linear-time modular decomposition algorithm for graphs[END_REF]. All existing algorithms aim to reduce the time complexity and find the simplest way to obtain the modular decomposition of a graph. The first polynomial algorithm is due to Cowan et al. [START_REF] Cowan | Graph decomposition for undirected graphs[END_REF] and runs in O(n 4 ), where n is the number of vertices in the graph. Habib and Maurer [START_REF] Habib | On the x-joint decomposition for undirected graphs[END_REF] proposed an O(n 3 ) algorithm. Then, Muller and Spinard [START_REF] Muller | Incremental modular decomposition[END_REF] proposed an incremental O(n 2 ) algorithm. Independently, Mc-Connell and Spinard [START_REF] Mcconnelle | Linear time modular decomposition and efficient transitive orientation of comparability graphs[END_REF], Cournier and Habib [START_REF] Cournier | A new linear algorithm for modular decomposition[END_REF] and Dahlhaus et al. [START_REF] Dahlhaus | Efficient and practical modular decomposition[END_REF] succeeded to obtain a linear algorithm in O(n + m) time, where n is the number of vertices in the graph and m the number of edges. Finally, Habib et al. [START_REF] Capelle | Graph decompositions and factorizing permutations[END_REF][START_REF] Habib | A simple linear-time modular decomposition algorithm for graphs[END_REF] developed a simpler linear time algorithm in O(n + m) . We refer the reader to [START_REF] Habib | A survey of the algorithmic aspects of modular decomposition[END_REF][START_REF] Quaddoura | Classical graphs decomposition and their totally 2010 decomposable graphs[END_REF] for a more detailed survey on modular decomposition algorithms and their algorithmic techniques. All existing algorithms focus on computing the modular decomposition tree of a graph. This tree represents how modules are nested in all the graph. So, we adapted the algorithm of [START_REF] Capelle | Graph decompositions and factorizing permutations[END_REF][START_REF] Habib | A simple linear-time modular decomposition algorithm for graphs[END_REF] to extract the final quotient graph. This modification consists mainly in:

• Finding the adjacency relationships between the maximum strong modules

• Keeping track of the vertex labels because the modular decomposition algorithm doesn't deal with labels.

Graph Distance Measure based on the Prime Graph

Given two labeled graphs G 1 and G 2 and their respective prime graphs P(G 1 ) and P(G 2 ), we aim to take a decision on the similarity between G 1 and G 2 by comparing their prime graphs.

There are at least two advantages for such approach. First, similarity is computed on simpler graphs which reduces considerably the number of comparisons for large graphs. Second, the detection of particular structures within the graph, i.e., the modules, may enhance the accuracy of the comparison mainly for classification problems. We first obtain the prime graph by using a modular decomposition algorithm then we use graph probing and star comparison to compute a distance between these graphs. So, computing the similarity between two graphs G 1 and G 2 is mapped to computing the similarity between their corresponding prime graphs P(G 1 ) and P(G 2 ).

We consider simple labeled graphs which do not contain self-loops, multi-edges and edge labels. An undirected attributed graph, denoted by G can be represented by a 3-tuple stars of strong modules. After that, we will define the mapping distance between two prime graphs based on their star representations. Finally, we will define the mapping distance between two graphs based on the distance between their prime graphs.

G = (V, E, f ) where V is a finite set of vertices, E ⊆ V × V is a set of vertex
As pointed-out in the previous section, we focus on maximum strong modules that ensure the uniqueness of the prime graph. The structure inside a maximum strong module is encoded by the type of the module and also the types of inner strong modules that are contained in it.

The type of a module is represented by a vertex labeled S (for a series module), P (for a parallel module) and Pr for (for a prime module). So, to describe a module, we use a label-oriented representation based on a probe vector. This means that we mainly represent vertices rather than edges because the structure inside the modules, i.e. the adjacency relationships, is already encoded in the labels S, P and P r which characterize the modules.

Definition 5 (module probe vector ). Let M be a module in the graph G and let A = {l S , l P , l P r } {l 0 , l 1 , l 2 , . . . , l α } denote an ordered finite set of vertex labels of P(G). M can be described with a numerical vector of non negative integers V M = (a S , a P , a P r , a 0 , a 1 , a 2 , . . . , a α ) such that M contains exactly a S series modules , a P parallel modules , a P r prime modules and a i vertices labeled l i .

Figure 4 shows an example of a probe vector for one of the modules of our graph example (i.e., graph of Figure 2). We compute the distance between two probe vectors as follows:

Definition 6 (probe vector distance). Given two probe vectors V 1 and V 2 , the distance between V 1 and V 2 is given by:

γ(V 1 , V 2 ) = max( V 1 1 , V 2 1 ) -V1+V2 1-V1-V2 1 2 γ(V 1 , V 2 )
computes the number of edit operations needed to transform V 1 into V 2 by the addition and the suppression of labels or by modifying labels (i.e, relabeling). It is equivalent to

M(L 1 , L 2 ) in Definition 3.
According to this notation, a module structure which is encoded in the type of the module, can be defined as follows:

Definition 7 (module structure). A Module structure T M can be represented by a 4-tuple T M = (r, f, A, V M ) where r is the type of the module, A is the set of labels, f a labeling function and V M the probe vector of the module.

Then, we define the distance between two module structures as follows: Definition 8 (module distance). Given two module structures T M1 = (r 1 , f 1 , A, V M1 ) and T M2 = (r 2 , f 2 , A, V M2 ) then the distance between T M1 and T M2 is:

d(T M1 , T M2 ) = ω(r 1 , r 2 ) + γ(V M1 , V M2 ).
where

ω(r 1 , r 2 ) = 0 if r 1 = r 2 , 1 otherwise. γ(V M1 , V M2
) is given by Definition 6.

Every vertex v i in a prime graph P(G) has a corresponding star of modules S P(G) i defined as S P(G) i = (r Si , L Si , f i ) where r Si is the module at the root of the star S P(G) i , L Si is the set of modules of the leaves of the star and f i is a labeling function. For a prime graph containing k vertices, we have k stars of modules. Accordingly, a prime graph P(G) can be mapped to a multiset of stars of modules denoted SM (P(G)). The distance between two stars of modules is defined as follows:

Definition 9 (star of modules distance). Given two stars of modules S 1 = (r S1 , L S1 , f 1 ) and S 2 = (r S2 , L S2 , f 2 ) then the distance between S 1 and S 2 is:

d SM (S 1 , S 2 ) = d(r S1 , r S2 ) + ψ(L S1 , L S2 ) + |∆(S 1 ) -∆(S 2 )|.
where ψ(L S1 , L S2 ) = γ(V S1 , V S2 ) with V Si a probe vector associated to L Si and given by:

V Si = V Mt Mt∈LS i . d(r S1 ,
P r_Dist(G 1 , G 2 ) = min h Si∈SM(P(G1)),h(Si)∈SM(P(G2)) d SM (S i , h(S i )).
where h :

SM (P(G 1 )) → SM (P(G 2 )) is a bijection. d SM (S i , h(S i )) is calculated with Definition 9.
Computing this distance is then equivalent to solve the assignment problem in the square matrix max

(|P(G 1 )|, |P(G 2 )|) × max(|P(G 1 )|, |P(G 2 )|)
in which each element represents the distance between the i th star in SM (P(G 1 )) and j th star in SM (P(G 2 )). To do so, we use the Hungarian algorithm [START_REF] Kuhn | The Hungarian method for the assignment problem[END_REF] to obtain the minimum cost in O(n 3 ) time. Note that, in the case where |P(G 1 )| = |P(G 2 )|, the square matrix is obtained by adding empty stars.

Complexity Analysis and Discussion

In the remaining sections, we will denote by Ex_Dist the distance obtained by the exact graph edit distance computation based on the A * algorithm [START_REF] Hart | A Formal Basis for the Heuristic Determination of Minimum Cost Paths[END_REF] and by St_Dist the distance obtained by the approximate graph distance algorithm based on star assignment [START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF]. The proposed distance, denoted P r_Dist is mainly compared to Ex_Dist and St_Dist.

The proposed approach involves three steps:

1. Building the prime graph: this needs O(n + m) time where n is the number of vertices in the graph and m is the number of its edges. We use the modular decomposition algorithm described in [START_REF] Capelle | Graph decompositions and factorizing permutations[END_REF][START_REF] Habib | A simple linear-time modular decomposition algorithm for graphs[END_REF] and modified to extract the adjacency relationships between the maximal strong modules from the tree generated by the algorithm.

2. Computing the distance between each pair of stars in the obtained prime graphs: we need therefore O(k 3 ) time steps where k is the number of vertices in the largest prime graph, i.e., the number of maximal strong modules in the largest prime graph.

3. Solve the assignment problem by using the Hungarian algorithm [START_REF] Kuhn | The Hungarian method for the assignment problem[END_REF] to obtain the minimum cost in O(k 3 ) time.

So, our algorithm runs in polynomial time and has a complexity of

O(k 3 + n + m)
where k is the number of vertices in the largest prime graph. In the worst case k = n which means that the graph is not decomposable. In this case the algorithm is equivalent to the algorithm of [START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF] as stated by the following Lemma.

Lemma 1. Let G 1 and G 2 be undirected attributed graphs. If G 1 and G 2 are not decomposable then

P r_Dist(G 1 , G 2 ) = St_Dist(G 1 , G 2 ).
Proof. If G 1 and G 2 are not decomposable, we have G 1 = P(G 1 ) and G 2 = P(G 2 ). So, it suffices to show that for two stars S 1 and S 2 of G 1 and G 2 respectively, we have :

d SM (S 1 , S 2 ) = λ(S 1 , S 2 ).
λ is given by Definition 3.

d SM (S 1 , S 2 ) = d(r S1 , r S2 ) + ψ(L S1 , L S2 ) + |∆(S 1 ) -∆(S 2 )|.
As there are no modules, r S1 = r 1 and r S2 = r 2 with r 1 and r 2 the vertices at the roots of S 1 and S 2 respectively. So,

d(r S1 , r S2 ) = ω(r 1 , r 2 ) = T (r 1 , r 2 ). ψ(L S1 , L S2 ) = γ(V S1 , V S2
) where V S1 gives the number of occurrences of each label in the leaves of S 1 and V S2 gives the number of occurrences of each label in the leaves of S 2 . So,

V S1 1 = |L 1 |, V S2 1 = |L 2 | and max{ V S1 1 , V S2 1 } - VS 1 +VS 2 1 -VS 1 -VS 2 1 2
has the same result as

M(L 1 , L 2 ). Consequently, d SM (S 1 , S 2 ) = λ(S 1 , S 2 ).
Hence, when the two graphs are not decomposable P r_Dist behaves similarly to St_Dist when compared to Ex_Dist. The comparison between St_Dist and Ex_Dist is given by:

Theorem 1. [63] St_Dist(G 1 , G 2 ) ≤ max{4, max{∆(G 1 ), ∆(G 2 )} + 1}Ex_Dist(G 1 , G 2 )
When at least one of the two graphs is decomposable, we have the following relation between P r_Dist, St_Dist and Ex_Dist: Theorem 2. For any graphs G 1 and G 2 , the following properties hold:

1. P r_Dist(G 1 , G 2 ) ≥ St_Dist(G 1 , G 2 ) ≥ Ex_Dist(G 1 , G 2 ) 2. P r_Dist(G 1 , G 2 ) ≤ (5 + 3 max{∆(G 1 ), ∆(G 2 )})Ex_Dist(G 1 , G 2 )
Proof. We follow the same reasoning as in [START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF]. Let P = (p 1 , p 2 , • • • , p k ) be a set of edit operations transforming G 1 to G 2 in Ex_Dist. This means that there is a sequence of graphs

G 1 = h 0 → h 1 → • • • → h k = G 2
, where h i-1 → h i indicates that h i is obtained by applying edit operation p i on h i-1 for 1 ≤ i ≤ k. Assume there are k 1 edge insertion/deletion operations, k 2 vertex insertion/deletion operations and k 3 vertex relabeling operations in P with k 1 + k 2 + k 3 = k. In the following, we will analyze each kind of edit operations in detail.

• Vertex Insertion/Deletion: In the case of vertex insertion, since the newly inserted vertex v i has no edges, P r_Dist(h m , h m+1 ) = St_Dist(h m , h m+1 ) = 1. The same result is obtained in case of deleting one isolated vertex.

• Edge Insertion/Deletion: For St_Dist, inserting an edge between two vertices v i and v j in the graph h m affects the two stars rooted at v i and v j respectively. For both stars, a new vertex and a new edge are inserted. So, St_Dist induces 4 edit operations [START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF].

For P r_Dist, inserting an edge between two vertices v i and v j in the graph h m may induce one of the following modifications of the stars and module structures:

-Modifying two simple stars (i.e., no module is affected): this case is similar to St_Dist and induces 4 edit operations.

-Creating a new module or splitting up an existing module (see Figure 5): assume there is a vertex v t in h m such that when inserting an edge between v i and v j , v i obtains the same neighboring hood as vertex v t . The two vertices v i and v t form a new module M in P(h m+1 ). Each star in P(h m ) that has v i and v t in its leaves has now M as a leaf in P(h m+1 ). This means that the number of labels in the leaves of each star increases by 1 (i.e, the label that corresponds to the type of the module) but the degree of the star decreases by 1. The star rooted at v j has 2 new labels in its leafs (v i and the type of the module, i.e., 2 operations). Also, the star routed at v i and the star rooted at v t are replaced by one star rooted at M that has 3 labels in the root. This is equivalent to add 2 labels to the star rooted at v t (i.e., 2 operations) and to suppress the star rooted at v i (i.e., 1 + 2 deg(v i )). So P r_Dist induces 2 + 2 + 1 + 3 deg(v i ) edit operations. The same reasoning can be applied when the inserted edge splits up an existing module. -Modifying an existing module (see Figure 6): Let M be a module in P(h m ) such that when inserting an edge between v i and v j , v i obtains the same neighboring hood as a vertex v t of M . Vertex v i joins the module M . In this case, the star rooted at M has an additional label in the root. The stars that have v i as a leaf (so have also M as a leaf) decrease their degree by 1 (i.e., deg(v i ) edit operations) and we have one star in less, the star rooted at v i ((i.e., 1 + 2 deg(v i )). This gives P r_Dist(h m , h m+1 ) =

1 + 1 deg(v i ) + 1 + 2 deg(v i ). So, P r_Dist(h m , h m+1 ) = 2 + 3 deg(v i ) in this case.
The same reasoning can be applied when the inserted edge retrieves a vertex from an existing module. Note that, in the case of modification of an existing module, we have deg(v i ) > 0. So, in both cases we have P r_Dist(h m , h m+1 ) ≥ St_Dist(h m , h m+1 ).

• Vertex Relabeling: Assume a vertex v i 's label is changed from ℓ 1 to ℓ 2 . In this case, the star containing v i in its root and also all the stars containing v i in their leaves are affected.

Therefore, for one vertex relabeling, we have P r_Dist(h m , h m+1 ) = St_Dist(h m , h m+1 ) and both of them induce 1 + deg(v i )) edit operations.

Consequently, we have the following inequalities:

• P r_Dist(G 1 , G 2 ) ≥ St_Dist(G 1 , G 2 ) ≥ Ex_Dist(G 1 , G 2 ), and
• P r_Dist(G 1 , G 2 ) ≤ max(4, 5 + 2 deg(v i ), 2 + 3 deg(v i ))k 1 + k 2 + (1 + deg(v i ))k 3 ≤ (5 + 3 max{∆(G 1 ), ∆(G 2 )}) k 1 + k 2 + (max{∆(G 1 ), ∆(G 2 )} + 1) k 3 ≤ (5 + 3 max{∆(G 1 ), ∆(G 2 )}) (k1 + k2 + k3) ≤ (5 + 3 max{∆(G 1 ), ∆(G 2 )})Ex_Dist(G 1 , G 2 )
Theorem 3. For any graphs G 1 , G 2 and G 3 , the following properties hold:

1. P r_Dist(G 1 , G 2 ) ≥ 0 2. P r_Dist(G 1 , G 2 ) = P r_Dist(G 2 , G 1 ) 3. P r_Dist(G 1 , G 2 ) ≤ P r_Dist(G 1 , G 3 ) + P r_Dist(G 2 , G 3 )
Proof. Properties 1 and 2 follow directly from the uniqueness of the prime graphs obtained by the relations of adjacency between maximum strong modules and from Definitions 5-10. We focus here on the proof of the triangle inequality. The distance between two graphs is the minimum cost between stars given by the assignment algorithm. This algorithm preserves the triangle inequality, so we have to prove the triangle inequality between stars. Let S 1 , S 2 and S 3 three stars of modules from P(G 1 ), P(G 2 ) and P(G 3 ) respectively, we need to show that:

d SM (S 1 , S 2 ) ≤ d SM (S 1 , S 3 ) + d SM (S 3 , S 2 )
with d SM (S i , S j ) = d(r Si , r Sj ) + ψ(L Si , L Sj ) + |∆(S i ) -∆(S j )| according to Definition 9. In this equation, d(r Si , r Sj ) is equal to 0 or 1, |∆(S i ) -∆(S j )| is the difference of degrees of the two stars and ψ(L Si , L Sj ) is the number of edit operations that are needed to obtain the leaves of S i from the leaves of S j and vice versa. As, we consider vector of probes to represent the leaves, we consider only edit operations on labels. Property 3 in Theorem 3 is equivalent to the following inequality: (2) which can be simplified to:

d(r S1 , r S2 ) + ψ(L S1 , L S2 ) + |∆(S 1 ) -∆(S 2 )| ≤ d(r S1 , r S3 ) + ψ(L S1 , L S3 ) + |∆(S 1 ) -∆(S 3 )|+ d(r S3 , r S2 ) + ψ(L S3 , L S2 ) + |∆(S 3 ) -∆(S 2 )| (
r 12 + a 12 ≤ r 13 + r 32 + a 13 + a 32 + 2(m 33 + m 12 ) (3)
We consider six cases according to the degrees of the stars:

• Case 1: ∆(S 1 ) ≥ ∆(S 2 ) ≥ ∆(S 3 ). Here, we have a 13 ≥ a 13 ≥ 0 and a 13 ≥ a 23 ≥ 0. Then, according to the value of r 12 , we have:

r 12 = 0, here Equation 3 holds whatever is in the value of its right part.

r 12 = 1, this means that r 13 = 1 or r 23 = 1 and consequently Equation 3 holds.

• Case 2: ∆(S 1 ) ≥ ∆(S 3 ) ≥ ∆(S 2 ). Here, a 12 , a 13 and a 23 can be computed by:

a 12 = m 11 + m 13 -m 22 -m 23 a 13 = m 11 + m 12 -m 33 -m 23 a 23 = m 33 + m 23 -m 22 -m 12
Equation 3 is simplified to: r 12 ≤ r 13 + r 32 + 2(m 33 + m 12 ) which holds true.

The remaining four cases

∆(S 2 ) ≥ ∆(S 1 ) ≥ ∆(S 3 ), ∆(S 2 ) ≥ ∆(S 3 ) ≥ ∆(S 1 ), ∆(S 3 ) ≥ ∆(S 1 ) ≥ ∆(S 2 ) and ∆(S 3 ) ≥ ∆(S 2 ) ≥ ∆(S 1
) can be shown similarly.

Note that the prime graph based distance does not respect the uniqueness property and two non isomorphic graphs G 1 and G 2 may verify P r_Dist(G 1 , G 2 ) = 0. So, the Prime graph based distance for labeled undirected graphs is a pseudo-metric.

Evaluation

In this section, we evaluate how much our approach approximates the similarity between two graphs and to which extent it can be used for pattern recognition and classification tasks. We also evaluate its execution time performance. For modular decomposition, we use the algorithm proposed in [START_REF] Capelle | Graph decompositions and factorizing permutations[END_REF][START_REF] Habib | A simple linear-time modular decomposition algorithm for graphs[END_REF] which is linear time. It generates the modular decomposition of a graph of n vertices and m edges in O(n + m) time. All experiments were conducted on a 2.80 GHz Intel(R) Core(T M ) i7 -2640M 64 bits laptop with 8 GB main memory running on Windows 7. All programs were implemented in C ++ . For comparison, we use two reference distances. The optimal A * based algorithm of exact graph edit distance computation [START_REF] Hart | A Formal Basis for the Heuristic Determination of Minimum Cost Paths[END_REF] described in Section 1 and the approximate graph edit distance algorithm proposed in [START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF] and also described in Section 1.

Datasets

We investigate the precision of our graph distance over several real datasets from the IAM graph database repository2 for graph-based pattern recognition and machine learning [START_REF] Riesen | IAM Graph Database Repository for Graph Based Pattern Recognition and Machine Learning[END_REF] and the RI database of biochemical data3 [START_REF] Bonnici | A subgraph isomorphism algorithm and its application to biochemical data[END_REF]. In Table 2 a summary of these graph data. Besides the size of each dataset, its maximum number of vertices and edges and its average number of vertices and edges, we also give the average and maximum reduction rates of the dataset. Given a graph G and its prime graph P(G), the reduction rate RR of G is given by: RR

(G) = |V (G)|-|V (P(G))| |V (G)| • 100%.
It compares the number of vertices in P(G) in respect to G. 1. The AIDS database (IAM database): The AIDS dataset consists of graphs representing molecular compounds. This dataset consists of two classes (active, inactive), which represent molecules with activity against HIV or not. Graphs are constructed from the AIDS Antiviral Screen Database of Active Compounds [START_REF] Riesen | IAM Graph Database Repository for Graph Based Pattern Recognition and Machine Learning[END_REF]. The molecules are converted into graphs by representing atoms as vertices and the covalent bonds as edges [START_REF] Riesen | IAM Graph Database Repository for Graph Based Pattern Recognition and Machine Learning[END_REF]. Vertices are labeled with the number of the corresponding chemical symbol and edges 4 by the valence of the linkage. The resulting graphs are small and sparse. We use a training set and a validation set of size 250 each, and a test set of size 1500. Thus, there are 2000 elements totally (1600 inactive elements and 400 active elements).

2. The Protein database(IAM database): The protein dataset consists of graphs representing proteins originally used in [START_REF] Borgwardt | Protein function prediction via graph kernels[END_REF]. The proteins database consists of six classes, which represent proteins out of the six enzyme commission top level hierarchy (EC classes). The proteins are converted into graphs [START_REF] Riesen | IAM Graph Database Repository for Graph Based Pattern Recognition and Machine Learning[END_REF] by representing the secondary structure elements of a protein with vertices and edges of an attributed graph. Vertices are labeled with their amino acid sequence (e.g. TFKEVVRLT). Every vertex is connected with an edge to its three nearest neighbors in space. Edges are labeled with their type and the distance they represent in angstroms. There are 600 proteins totally, 100 per class. We use a training, validation and test sets of equal size (200).

3. The Mutagenicity database (IAM database): Mutagenicity is a kind of chemical compounds. The molecules were converted into graphs [START_REF] Riesen | IAM Graph Database Repository for Graph Based Pattern Recognition and Machine Learning[END_REF] by representing atoms as vertices and the covalent bonds as edges. Vertices are labeled with the number of the corresponding chemical symbol and edges by the valence of the linkage. The mutagenicity dataset is divided into two classes mutagen and nonmutagen. The dataset contains 4337 elements totally (2401 mutagen elements and 1936 nonmutagen elements). We use a training set, a validation set and a test set of equal size 300.

GREC database (IAM database):

The GREC dataset consists of graphs representing symbols from architectural and electronic drawings. Graphs are extracted from images by tracing the lines from end to end and detecting intersections as well as corners [START_REF] Riesen | IAM Graph Database Repository for Graph Based Pattern Recognition and Machine Learning[END_REF]. Ending points, corners, intersections and circles are represented by vertices and labeled with a two-dimensional attribute giving their position. The vertices are connected by undirected edges which are labeled as "line" or "arc". An additional attribute specifies the angle with respect to the horizontal direction or the diameter in case of arcs [START_REF] Riesen | IAM Graph Database Repository for Graph Based Pattern Recognition and Machine Learning[END_REF]. The obtained graphs are uniformly distributed over 22 classes. The resulting set is split into a training and a validation set of size 286 each, and a test set of size 528.

Letter database (IAM database):

This graph dataset contains graphs that represent distorted letter drawings [START_REF] Riesen | IAM Graph Database Repository for Graph Based Pattern Recognition and Machine Learning[END_REF]. Only the 15 capital letters of the Roman alphabet that consist of straight lines (A, E, F, H, I, K, L, M, N, T, V, W, X, Y, Z) are considered. For each class, a prototype line drawing is manually constructed. These prototype drawings are then converted into prototype graphs by representing lines by undirected edges and ending points of lines by nodes. Each node is labeled with a two-dimensional attribute giving its position relative to a reference coordinate system [START_REF] Riesen | IAM Graph Database Repository for Graph Based Pattern Recognition and Machine Learning[END_REF]. Edges are unlabeled. The graphs are uniformly distributed over the 15 classes. Distortions are applied on the prototype graphs with three different levels of strength, viz. low, medium and high. Hence, this dataset contains 3 subsets: HIGH, MED and LOW with 2250 graphs in each set.

6. The PPI database (RI database): This dataset contains graphs describing the known and predicted protein interactions. The graphs describe the following organisms: Mus musculus, Saccaromyces cerevisiae, Caenorhabditis elegans, Drosophila melanogaster, Takifugu rubipres, Danio rerio, Xenopus tropicalis, Bos taurus,Rattus norvegicus, and Homo sapiens. They are large graphs. The original version of the dataset have unique vertex labels (protein IDs) [START_REF] Szklarczyk | The string database in 2011: functional interaction networks of proteins, globally integrated and scored[END_REF]. We use the RI version which was randomly relabeled with 2048 labels. Labels are assigned using a uniform distribution [START_REF] Bonnici | A subgraph isomorphism algorithm and its application to biochemical data[END_REF].

7. The PDBS database (RI Database): This dataset contains 30 graphs with data from DNA, RNA, and proteins having up to 33067 vertices. The dataset mostly contains very large graphs [START_REF] Bonnici | A subgraph isomorphism algorithm and its application to biochemical data[END_REF].

Results and Discussion

Comparison with the Exact Graph Edit Distance Algorithm

We first conducted experiments to compare our algorithm to the exact graph edit distance computation based on the A * algorithm [START_REF] Hart | A Formal Basis for the Heuristic Determination of Minimum Cost Paths[END_REF], denoted by Ex_Dist. We also compared our algorithm to the approximate graph edit distance computation algorithm based on subgraph assignment [START_REF] Jouili | Attributed graph matching using local descriptions[END_REF][START_REF] Raveaux | A graph matching method and a graph matching distance based on subgraph assignments[END_REF][START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF][START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF]. We implemented the solution of [START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF] denoted here by St_Dist mainly because it does not use edge labels and consequently can be easily compared to the proposed solution. We consider two metrics: runtime and also how the proposed distance behaves with respect to the exact edit distance computation. For both metrics, we used the AIDS datasets and considered only small graphs to avoid the time complexity related to the exact computation of the graph edit distance. From the 2000 graphs of the AIDS dataset, we randomly selected 10 graphs each of which contains 10 vertices to form a target graph database. We also constructed 7 query groups: Q 8 ,...,Q 14 each of which contains 10 graphs. All the graphs of the same query group Q i have the same number of vertices. The number of vertices in each graph of a query group Q i is i. This means that the number of vertices of the query graphs varies from 8 to 14. Ex_Dist. We can also see that P r_Dist achieves a little bit better than St_Dist.

Then, we focused on how P r_Dist behaves compared to the exact edit distance Ex_Dist and to its approximation given by St_Dist.

Scalability over Large Graphs

We evaluated the scalability of our approach in terms of the order of the graphs, i.e., the number of vertices of the graphs. For this, we used two datasets: PDBS and PPI. Both datasets contain large graphs with a significant difference in the reduction rate : 63.28% for PDBS and 3.41% for PPI. For each dataset, we used all the the graphs that have a number of vertices lower than 12000 as the graph database and we varied the size of the graph query. Figure 9 shows the runtime for calculating P r_Dist and St_Dist between each query graph and the graph database for the two datasets. The X-axis shows the number of vertices contained in the query graph and the Y -axis the average runtime, in log scale, obtained over the target database. From this figure we can see that P r_Dist faster than St_Dist in the two datasets and that this difference of performance is proportional to the compression rate. This is mainly due to the reduction but also to the fact that St_Dist uses a time consuming algorithm to compute intersections between multisets. This is avoided by P r_Dist which is based on probes. We can also see that the runtime performance of P r_Dist is more important with the PDBS dataset than with the PPI dataset this is due to the difference of reduction rate between the two datasets.

It is also worth noting that memory requirement is also important for large graphs. For the PDBS dataset where some graphs exceed 33000 vertices St_Dist generates an Out of memory exception with graphs larger than 12000 vertices while P r_Dist processes all the graphs. In fact, with an average reduction rate of 63.28%, the largest graph of the PDBS dataset, i.e. 33067 vertices, has a prime graph of at most 12142 vertices. We note also that the two algorithms use the same data structures for graphs and use the same implementation of the Hungarian algorithm and that the Out of memory exception generated by St_Dist is due to the Hungarian part of the implementation.

Figure 10 shows the computed distance for P r_Dist and St_Dist between each query graph and the graph database for the two datasets. The X-axis shows the number of vertices contained in the query graph (in log scale for PDBS dataset) and the Y -axis the average distance obtained over the target database. From this figure we can see that P r_Dist is an upper bound for St_Dist. For the PPI dataset that has a small reduction rate the two distances are similar. This confirm the result stated by Lemma 1.

Classification

We use the N N classifier to evaluate the quality of the proposed distance and we compared it with St_Dist. Table 3 reports the average classification results obtained for each dataset over the three subsets: Test, train and valid. From these results, we can see that P r_Dist obtains a better classification for the AIDS, GREC and Letter databases and not for Mutagenecity and Protein databases. It seems that more the dataset is reducible more P r_Dist is accurate. This is clearly illustrated in Figure 11. In this figure, the X-axis shows the average reduction rate of the datasets and the Y -axis the average classification obtained over the dataset. Figure 11(a) shows clearly that the classification obtained by P r_Dist increases with the average reduction rate. It also shows that beyond 27% of reduction P r_Dist achieves better than St_Dist. To explain these results, we also investigated the impact of the distribution of the reduction over the dataset. In fact, we remarked that when there is a large difference between the reduction rates of the compared graphs, the computed distance tend to be biased by the important number of empty stars needed by the assignment computation. In fact, even if the initial graphs have the same number of vertices, their prime graphs may have very different number of vertices.

So, the distribution of the reduction over the dataset is to be considered to explain in which cases P r_Dist behaves better than St_Dist and in which cases it does not. We considered the difference between the maximum reduction rate and the average reduction rate as a measure of how homogenous is the reduction over a dataset and we plot the results obtained for classification in function of this difference. shows that beyond a difference of reduction of 52%, P r_Dist looses in accuracy.

Over all these results, we can conclude that P r_Dist takes advantage from detecting particular structures in the compared graphs and enhance the accuracy of the classification. However, when the compared graphs are not homogenously reduced, the detection of these particular substructures is not benefic for the distance and P r_Dist looses in accuracy.

Conclusion

In this paper, we introduced an approximate approach for the similarity measure of large graphs which is based on prime graphs. The key idea of the proposed method is to perform the comparison on simpler graphs without losing the structural information of original graphs in order to enhance the time complexity. We provide an experimental evaluation over small and large graphs. The obtained results show that our approach has an interesting runtime performance and has a good scalability in terms of the number of vertices in the compared graphs. Classification results over several real datasets show that the accuracy of the approach is acceptable. Moreover, we also showed that the proposed similarity takes advantage from detecting particular structures in the compared graphs and enhance the accuracy of the classification. However, this result is obtained when the compared graphs are decomposable, hence the need of thresholding the compression of the compared graphs. According to the experiments, this threshold, given by the average reduction rate, can be fixed to 27%. We also remark that the homogeneity of the reduction over the dataset is an important factor to consider when using this method for classification purposes.

As future work, several extensions and enhancements are possible. A non exhaustive list is:

• Use prime graphs or strong modules to compute footprints that may be used for indexing in large graph databases.

• Use other methods to compare prime graphs. To compute our similarity measure, we coupled the prime graphs with a subdivision into stars and we used probe vectors. However, it may be interesting to investigate other ways to use prime graphs to compute a similarity between graphs. Tree edit distance may provide better performance. Indeed, each vertex of the prime graph is a maximum strong module which may contains other nested strong modules. So, it can be represented by a tree. Internal vertices of the tree gives the type of the modules nested in the maximum strong module and the leaves are the trivial modules, i.e. the vertices of the original graph. Figure 12 illustrates the representation of the strong modules within the final quotient graph of our graph example (graph used in Figures 2 and3). • Consider a parallel version of the algorithm to enhance the processing of very large graphs.

• Extend the approach to directed graphs. Note that a modular decomposition algorithm for directed graphs is proposed in [START_REF] Cowan | Graph decomposition for undirected graphs[END_REF][START_REF] Mcconnell | Linear-time modular decomposition of directed graphs[END_REF].

• Extend the approach to edge-labeled graphs. A solution is directly obtained by using a second probe vector for the edge labels of each maximum strong module.

Figure 1 :

 1 Figure 1: Example of edit operations.

Figure 2

 2 Figure 2 illustrates an example of a graph and its modules.

Figure 2 :

 2 Figure 2: A graph and its modules.

Figure 3

 3 details in several steps how we get the final prime graph by compacting recursively the strong modules of the graph of Figure2.

Figure 3 :

 3 Figure 3: The quotient graph obtained by compacting the strong modules of the graph G. S: series module. P : parallel module. P r: prime module.

Figure 4 :

 4 Figure 4: Example of Probe Vector of a module.

  r S2 ) is calculated with Definition 8. Definition 10 (graph distance). Given two prime graphs P(G 1 ) and P(G 2 ) of two graphs G 1 and G 2 with their multisets of star decompositions SM (P(G 1 )) = {S 1 , S 2 , . . . , S |V (P(G1))| } and SM (P(G 2 )) = {S ′ 1 , S ′ 2 , . . . , S |V (P(G2)| } respectively, then the distance between G 1 and G 2 is:

Figure 5 :

 5 Figure 5: Edge insertion inducing a module creation.

Figure 6 :

 6 Figure 6: Edge insertion inducing a module modification.

1 ) 1 Figure 7 :

 117 Figure 7: Overlapping between labels of L S1 , L S2 and L S3

Figure 8

 8 Figure 8 (a) shows the average runtime performance of the three distances. The X-axis shows the number of vertices contained in the query graph and the Y -axis the average runtime, in log scale, obtained over the query group of the corresponding graph size when compared to the target graph database. This figure shows clearly that St_Dist and P r_Dist are faster than

Figure 8 Figure 8 :

 88 Figure 8: Comparison with Ex_Dist

  of vertices in the Query Graph Pr_Dist St_Dist (a) PDBS dataset: RR = 63.28%. of vertices in the Query Graph Pr_Dist St_Dist (b) PPI dataset: RR = 3.41%.

Figure 9 :

 9 Figure 9: Scalability over Large Graphs: Runtime Performance

Figure 10 :

 10 Figure 10: Scalability over Large Graphs: Computed Distance

  Figure 11 (b) reports the obtained results. In this figure, the X-axis shows the difference between the maximum and the average reduction rates of the datasets and the Y -axis the average classification obtained over the dataset. It appears from Figure11(b) that more the reduction is homogenous over the dataset more P r_Dist is accurate. Figure11(b) also

Figure 11 :

 11 Figure 11: Impact of the reduction rate on Classification.

Figure 12 :

 12 Figure 12: Tree representation of the maximal strong modules within the quotient graph.

Table 1 :

 1 Notation

	Symbol	Description
	G(V, E)

  Equation 1 is equivalent to: r 12 +m 11 +m 22 +m 13 +m 23 +a 12 ≤ r 13 +m 11 +m 33 +m 12 +m 23 +a 13 +r 32 +m 22 +m 33 +m 13 +m 12 +a 32

Table 2 :

 2 Graph Dataset Characteristics tr: size of the training set. va: size of the validation set. te: size of the test set. #classes: number of classes. avg|V |: average number of vertices. avg|E|: average number of edges. max|V |: maximum number of vertices. max|E|: maximum number of edges. avgRR(%) : average reduction rate of the dataset and maxRR(%) its maximum reduction rate.

	Dataset	size(tr,va,te)	#classes	avg|V |	avg|E|	max|V |	max|E|	avgRR(%)	maxRR(%)
	AIDS	250,250,1500	2	15.69	16.19	95	103	53.219	94.199
	Mutagenecity	1500,500,2337	2	30.32	30.78	417	112	20.833	97.559
	GREC	286,286,528	22	11.51	11.93	24	29	32.267	91.669
	P rotein	200,200,200	6	32.63	62.14	126	149	16.860	95.349
	Letter	6750	15	4.67	3.61	9	9	27.52	75
	P P I	10	-	7828.9	107134.8	12578	332458	3.41	6.07
	P DBS	30	-	7448.2	5628.9	33067	30773	63.28	88.52

Table 3 :

 3 Classification

	Dataset	St_Dist	P r_Dist
	AIDS	98.67	100
	Mutagenecity	76	65
	GREC	84	88.67
	P rotein	48.33	43.33
	Letter	78.67	80.67

Note that, for some graphs, we can compact entirely the graph into a single node. In this case, we stop the compacting process one step before the entire compacting of the graph to avoid obtaining a trivial module.

www.iam.unibe.ch/fki/databases/iam-graph-database

http://ferrolab.dmi.unict.it/ri/ri.html#description

Note that we have not used edge labels for all the datasets.

Acknowledgements

The authors would like to thank the anonymous reviewers for their valuable comments on earlier drafts of this paper.


Boyd Michailovsky

Pronominally marked noun determiners in Limbu

Introduction

As in other Kiranti languages, nouns in Limbu are typically modified either by demonstratives, by pronominal prefixes, by other nouns (bearing the genitive suffix, but with a pronominal prefix on the head noun), or by propositions, participles, place-names, time-adverbs, etc., marked by the Limbu "nominalizing" suffix -pa. In a few cases, however, Limbu shows a different construction, in which the modifier bears a pronominal prefix, the 3d singular "posessive" prefix ku-. This type of determination is reflected in a common type of color-term derivative, e.g. kubhuːtla 'pale'. The same prefix is found in a number of other words which typically function as modifiers or as predicate adjectives, like kusɔŋ 'new'. In compounds, a noun may take the place of the pronominal ku-, e.g. mikphuːtla ["eye-pale"] 'European'. Similar phenomena are reported from other East Kiranti languages. 1

Modifier-Noun constructions

I begin with a review of nominal modifiers in Limbu. Nominals may carry the definite suffix -ɛn or the plural suffix -haˀ.

Demonstrative: DEM.-N (no marking)

(1) kha nɛse-'n (untimely209) 2 that earring-DEF 'that earring'

Genitive: (N-GEN)-PRON-N (head-and dependent-marking)

The "possessed" head is marked by a pronominal prefix belonging to the paradigm a-'1st person', kɛ-'2d person', ku-'3d person'. The genitive suffix on the dependent noun is -rɛ/-lɛ. Limbu independent pronouns do not take the genitive marker. The dependent-marker here is the "nominalizer" -pa, which in some contexts has a marked feminine -ma (cf. pa 'father', ma 'mother'). The function of -pa as a morphological element -the use which concerns us here -is to mark certain elements as nominal modifiers. Like other modifiers, these may serve as nominals in the absence of a head (see below). 3 A time-adverb as modifier:

( [START_REF]Compare the independent noun laŋ 'leg', kulaŋ 'his leg'. (This rule is apparently not observed in the standard Panchthar dialect, cf. kuleˑtla in ex. 15 and in A, and kulaŋ[END_REF] asen-ba khɔdakmi-rɛ (dance125) before-NOM elder-ERG 'old-timers' A subject-relativization using the active participle: [START_REF]A). The Academy dictionary also lists two compounds in which kuis retained: kubhiŋluŋ 'sapphire' ["blue-stone"] (A), kuhɛˀluŋ 'ruby' ["red-stone[END_REF] kha kɛ-si-ba mɔna-n (untimely270) that ACT-die-NOM man-DEF 'the dead man' English adjectives are most often translated by Limbu "stative" verbs (whose aspectual character is more complex than their name suggests). Morphologically, these have an unprefixed participial form in place of the active participle of ( 6):

(7) yɔm-ba sara thik (trade143) big-NOM boar one 'a big wild boar' Any modifier, in the absence of an expressed head, can serve as a nominal; in other words, Limbu is a language in which 'big' may mean 'big one'. [START_REF]I have applied Ebert's etymology for 'new' to Limbu kusɔŋ in (19) above[END_REF] a-mba a-mma-rɛ-'tmu (mariage39)

1-father 1-mother-GEN-LOC 'to/at my parents' [place]' [START_REF]Athpare 'money' is simply 'red[END_REF] kha kɛ-si-b'-ɛn (untimely123)

that ACT-die-NOM-DEF 'the dead man'

Color-words

Color-words form a closed class in Limbu, with particular formal properties (cf. van Driem's "bound colour morphs" 1987:23-25). The following are found in the Mewa Khola dialect: [START_REF] Bernot | [END_REF] There are a number of derived color-forms, some of them marked by the nominalizing suffix -pa mentioned above. The morpheme -taŋ 'like' is used to form color adjectives of the form [COLOR]-taŋba, e.g. maktaŋba 'black', phɔdaŋba 'white'. Special suffixes -kɔŋgɔŋba, -kɔkkɔkpa and -yɔˀyɔˀba are used to derive color adjectives expressing degrees of "[COLOR]ish", e.g. makkɔŋgɔŋba 'dark', phiŋgɔkkɔkpa 'blueish', makyɔˀyɔˀba 'blackish' (A).

But the most common and the most characteristic color-form has the prefix kuand the otherwise unknown suffix -ra/-la, for example, kuhɛtla 'red', kubhɔra 'white': kuhɛtla liŋ 'reddish thatch-grass'

The prefix kuis clearly the 3d person clitic pronoun, although here it does not commute with the other clitic pronouns (a-'1st person', kɛ-'2d person'). That is, if I am black, I am kumakla and not *a-makla. Note also that kumarks the dependent modifier (i.e. the color) and not, as in the genitive construction, the head. 4 Like other modifiers, the color-term can function as head: kuhɛtla (thik) 'a red one', kuhɛtla-'n 'the red one'. This is the construction that interests us here -or at least its lexicalized trace. Before discussing it further, I will present a few other lexical and morphological uses of ku-. 5

Other pronominalized modifiers

Three other words have the prefix kuand the suffix -la, although they do not share other color-derivatives: kulɔːpla 'cylindrical' (A) (cf. lɔːppɛt '[manner of] lying stretched out'), kugɔpla 'round' (A) (cf. kɔpma 'to surround, to reach around'), kusɛŋla 'dried' (A) (cf. sɛŋma 'to dry in the air').

A small group of adjectives has the prefix kuand the suffix -wɛt (~ wa in Tembe): kuhiŋwɛt 'alive' (cf. hiŋma 'to live'), kughɔŋwɛt 'unripe (of fruits)', kumaŋwɛt 'uncooked', kusiwɛt 'dead' (cf. sima 'to die'). ( 18 22), kudɔŋba is derived from the verb tɔŋma 'to agree '. In (20), kusiktaŋba is related to the postposition kusik 'like, in the manner of', which generally has an adverbial sense. In both cases there is an extra argument, the comparandum, which could justify the pronominal ku-; note, however, that this argument is not in the genitive case.

Modifier-compounds

In compounds, these modifiers generally appear without the kuprefix, which can thus be seen as commuting with a compounded noun. There are two types of compounds: the first type occurs with color-words of the type kuhɛtla 'red', in which the pronominal element kumay originally have indexed the head of a modifying construction. In compounds, what is logically a head-noun replaces the pronoun: structurally "meat-fresh" vs "its-fresh (meat)". Note that the usual modifier-head order of Limbu syntax is reversed:

(23)

saretla

'fresh meat' (cf. sa 'flesh') ŋaghɛkya

'dried fish' (cf. ŋa 'fish') maːkkiretla 'green/unripe maize' (cf. maːkki 'maize') thɛgek.hɛtla 'police (an Assam police force wearing red headgear)' (cf. thɛgek 'head') mikphuˑtla

(1) 'cataract', (2) 'European' ["pale-eye"] (cf. mik 'eye')

The second type also occurs with color words, and with 'new'. The pronominal prefix is again lost, but the usual order of determination is preserved: "black-earth" vs "its-black earth". (The identity of the compounded element is not always clear.) 'new man, stranger' (A) (mi is a formative suffix in a number of nouns referring to persons) This is the order of modifier-head compounds generally in Limbu, with modifiers like cukpa 'small' which never take ku-, e.g. cukphɛ '(kind of) small knife' (A) (cf. phɛdza 'Nepalese knife').

Relational nouns and compounds

The great majority of kuentries in the Academy dictionary are nouns, of which only a few will be cited here. Most have a relational sense, implying a relation to a whole, a source, a material, a complement, etc. In other words, to the extent that these words only appear with the pronominal prefix, they constitute a class of obligatorily possessed nouns. 7 Grammatically, the prefix marks the head of a genitive expression, not a modifier as with color-words.

(25) kubhɛrɛk 'half' kube 'edge' kurum 'middle' kumulla (A) 'piece (esp. of meat)' kubuŋ (A) 'base' kummaːmaˀ (A) 'female (of a species)' kusaːp (A) 'root' kusigɛk (A) 'broken grain' Many deverbal derivatives fall into this category, distinguished from the source verbs by the pronominal prefix. The prefixed form is either the present stem or the infinitive (suffix -ma). Note that the prefix kudoes not occur in the finite verbal paradigm (see appendix). ( 26 tɛpma 'to cover'. kuyaŋ 'storage place, place to stay' yaŋma (A) 'to put inside' kuyuŋ 'handle (of a knife, etc.)' yuŋma 'to set, to fix' kueːp 'suppression' (A) epma 'to suppress' kugeːŋ 'length' (A)

keŋma 'be long' kughɛːk 'piece' (A), 'odd member of a pair' khɛːkma 'to have a nick, a missing tooth'

Relational nouns also enter into compounds. As in the case of modifier-compounds (above), a noun takes the place of the pronominal ku-. However, the semantic structure is different, because the noun that replaces the pronominal is logically a modifier and not the head: 'tree('s)-base' vs 'its-base'.

(

) 27
kuduːppa 'large intestine (A)' hiduːt, hiduːppa 'id.' (hi 'excrement') kumulla (A) piece (esp. of meat) sɛmulla 'piece of meat' (A) (? sa 'flesh') phaksamulla 'a piece of pork' (phaksa 'pork') kubuŋ (A) 'base' siŋbuŋ 'tree trunk' (A) (siŋ 'tree, wood') kusaːp (A) 'root' siŋsaːp 'tree-root' (A) kusigɛk (A) 'broken grain' yaˀsigɛk, yaˀsigeːk (A) 'broken grain' (yaˀ 'grain, rice') kuyuŋ 'handle' phɛyuŋ (A) 'knife-handle' (phɛdza 'Nepalese knife')

When the relational noun is itself the modifier, it comes first in the compound, e.g. in puŋsammaŋ 'chief among hunting deities' (A) (cf. sammaŋ 'deity'), lumsoːkma 'middle finger' (A) (cf.

soːkma 'to point'). Where it is a quantifier, it can apparently come either before or after what is quantified, like NP quantifiers: phrɛːŋdɔk ["half-pause"] 'semicolon' (A), tɔŋbhrɛːŋ ["year-half"] 'semester' (A).

East Kiranti parallels

The phenomena described above find an echo in Ebert's description of the closely-related language Athpare (1991:93-94) (Comments in square brackets are mine.): Some adjectives [marked by the (singular) nominalizer -na] alternate with forms that have a prefix /u-/ [u-~ o-, identical with the 3d person possessive prefix] and suffixes -pa ~ -ba or -wat. The following adjectives are attested only with /u-/, although they have the ending -na (rather than -pa or -wat) or no suffix at all. ucaphenna ugly, bad [cf. Limbu kudza phɛn ("its-eating bad")] ocetnuna beautiful, nice [cf. nu-'become good'] ohop u-pha-ba ~ u-pha-wa money (<?) 9 Finally, from Bickel's sketch of another East Kiranti language, Belhare (2003:563):

One adjective, uchoũat 'new', is attributed without further marking (uchoũat khim or khim uchoũat 'a/the new house') and appears to go back to a possessive construction meaning 'its-newness'. Such constructions are found with a few other concepts: e.g. ŋatlabu u-soŋ

[banana 3POSS-ripe] 'the/a ripe banana'.

The post-nominal position of the adjective is not necessarily significant, since Belhare is described as head-final with a "post-phrase adjunct position". But if pronominally-marked adjectives are more frequent in this position than other attributes, it might be taken to reflect the headedness of the hypothesized "house its-newness". [START_REF] Bernot | L'épithète en birman: contribution à l'étude des langues sans catégorie adjectivale[END_REF] describes Burmese as a language without a specifically adjectival category, in which demonstratives, possessors, and relatives precede the head. Modifiers which would normally be translated by French or English adjectives are generally drawn from the category of "stative verbs", which can serve as predicates, be followed by modal particles, etc. (I omit consideration of Pali loans, used in the literary language.) These usually follow the noun. 10 A few of them -essentially limited to color-words in the spoken language, although exceptional examples with 'new' and 'warm' are also cited -are marked by the prefix ˀə-. Thus: lu `ci [`ji] 'adult ["man big"]' `paŋ ˀəni 'the red flower ["flower PFX-red"]'

Burmese

The prefix in question also serves regularly to form deverbal nouns, as well as being found on a certain number of other nouns. Finally, it is lost in compounds, unless it is in first position.

Thus, as in Limbu, we have a nominalizing prefix which marks color-terms in their function as noun-modifiers. This is an interesting typological convergence, but perhaps no more than that. The Burmese prefix is not pronominal, at least not synchronically. The prefixed color-term, like other stative-verb modifiers in Burmese, usually follows the noun.

Conclusion

Pronominally-marked modifiers constitute a small, closed class in Limbu, consisting essentially of color terms and the word 'new' -among the usual suspects in closed classes of adjectives (Dixon 1994) -as well as 'living', 'dead', and a few others.

They are characterized by the presence of the pronominal prefix ku-. The structure of the modifier, "its-[quality]", reflects grammaticalization of the notion that the quality is "possessed" by the noun. Syntactically, however, it seems clear that in an expression like kubhɔra phuŋ 'white flower', 'flower' is the head, since head-final order is general in Limbu syntax. The pronominal morphology is frozen and unproductive.

The identification of the prefix as the 3d person possessive pronoun is reinforced by the existence of compounds in which the pronoun commutes with a noun. A pronominal form like kuretla 'green, unripe' can be seen as representing any of the possible compounds saretla 'meat+fresh', maːkkiretla 'maize+green/unripe', etc. Even in compounds where the internal order corresponds to the usual syntactic modifier-head order (e.g. phɔdiŋ'rek 'white-thorn [Solanum khasianum]'), the prefix is almost always dropped (cf. note 6).

We might consider the prefixed adjectives like kuretla as simply grammaticalized pronominalizations derived from saretla, etc., but we would still have to explain the anomalous order of the latter, which falls out naturally from the "its-[quality]" grammaticalization path. Compounds with the more usual stative-verb-type modifiers -'big' and 'little', for example -have only modifier-head order.

Pronominally marked modifiers are reported from two other East Kiranti languages, Athpare and Belhare. They have not been reported elsewhere in the Kiranti group.

  empty [cf. Limbu hopma 'not be, not exist'] umaŋ raw [cf. Limbu kumaŋwɛt] Ebert remarks (93n44): The origin of the prefix /u-/ is obscure. It could be a frozen 3rd person possessive prefix, or the form u--ba/-wa could be an old U[ndergoer]/S[ubject] participle. Cf. also o-mok-pa broth (<mok-ma 'boil') o-yaŋ-wat broken rice (<yaŋ-ma 'beat')o-choŋ-wat new (<choŋ-ma 'sell')8

appear in a number of constructions and characteristic derivations. They occur as predicates with the copulas lɔˀma 'to be like, to sound like, to make like...' and cokma 'to do, to behave':

		hɛt hiːk let mak 'black, dark' 'red' 'yellow', 'green' (Tembe, Phedap) 'raw, unripe, green, light "grue"' ɔm 'yellow' phiŋ 'blue, dark "grue"' phɔ 'white' phuːt 'gray, pale'
	Color-words (11) mak lɔˀ black COP go-SUB pekk-ɛllɛ	bela time	(elope43)
		'when it becomes dark'
	(12)	maːkki let maize green COP lɔˀ
		'the maize is green (unripe)'
		These predicates can serve as modifiers, using the regular relative construction :
	(13)	ɔm yellow ACT-COP-NOM kɛ-lɔˀ-ba	phuŋ flower
		'yellow flower'

)

  kusiwɛt siŋbuŋ 'dead tree' (A) kumaŋwa sa 'raw meat' (Tembe dialect) Further examples include the word 'new', which has the prefix kuwith no suffix: kusɔŋ him 'new house' (cf. sɔŋma 'to sell') kughɛkya sa 'dried meat' (cf. khɛkma 'to be dry').

	In (
	(19)
	Two pronominalized words express comparisons:
	(20)	thi-n beer-DEF water cwaːt	kusiktaŋba cog-u like make-3O.pa
		'he made the beer like water [i.e. weak]'
	(21)	a-mbhɔŋa-si-rɛ 1-uncle-COLL.GEN like kusiktaŋba ... cələn ... custom not.exist hop	(dance251)
		'there is no custom like that of my uncles' generation'
	(22)	jəmmə kudɔŋba pɔt all same COP	(dance62)
		'all [of our body-parts] are the same'

APPENDIX: Syntactic use of kuwith verbs

The prefix kudoes not occur as a prefix in the finite verbal conjugation, but it occurs with non-finite verb forms in two constructions. First, it appears with a reduplicated gerund, forming a kind of propositional nominalization or headless relative with an extentive sense. The original referent of the pronominal is perhaps an implied head (i.e. the amount in (a), the duration in (b), the speech in (c)).

(28) ku-ghambekk-ɛllɛ ku-dhɔn-dhɔn lɔt Second, kuappears with the present stem and the suffix -sɛ in the purpose construction, van Driem's "supine" (1987:212), where it indexes definite 3d person personal objects (only), commuting with a-'1st person' and kɛ-'2d person'.


INTRODUCTION

Like many filled rubber-like materials, as well as soft biological tissues and other biomaterials, filled silicones exhibit highly non-linear mechanical behavior. This non-linearity is commonly characterized by large strain levels under static conditions, a non-linear stress-strain response and strain rate dependence. Finally, under cyclic loading conditions, hysteresis and stress-softening behaviors are observed on both filled and unfilled elastomers. For the last half century all these cyclic phenomena were evidenced and modeled to support the most widely engineering applications. However, their microscopic mechanisms (breaking of weak chains, breaking of links, desabsorption of chains, etc.) explanation remains non-unanimous.

Hysteresis is rather related to the dissipative nature of material, i.e., related with viscoelasticity [START_REF] Bergstrom | Large strain timedependent behaviour of filled elastomers[END_REF] and viscoplasticity [START_REF] Miehe | Superimposed finite elastic-viscoelastic-plastoelastic stress response with damage in filled rubbery polymers. Experiments, modelling and algorithmic implementation[END_REF] behaviors. It is characterized as the difference between loading and unloading paths during a stabilized cycle. On the other hand the stresssoftening phenomenon, also called the Mullins effect (see [START_REF] Mullins | Softening of rubber by deformation[END_REF]), can be described as a softer behavior of the second loading after a first loading. It can be idealized as an instantaneous and irreversible softening of the stress-strain curve, due to rearrangements in the microstructure of the material that occurs whenever the load increases beyond its prior all-time maximum stretch value. At times when the load is less than a prior Experimental observation of induced anisotropy of the Mullins effect in particle-reinforced silicone rubber G. Machado, G. Chagnon & D. Favier Université de Grenoble/CNRS, Laboratoire 3S-R, Grenoble, France ABSTRACT: This study is concerned with the experimental observation of anisotropy induced by the Mullins effect in a particle-reinforced silicone rubber. Like many filled rubber-like materials, filled silicone exhibits highly nonlinear mechanical behavior. This nonlinearity is characterized by large strain levels under static conditions, a non-linear stress-strain response and strain rate dependence. However, experimental data concerning the influence of tensile loading cycles in one direction on the stress-softening in other tension directions is quite scarce. In this scope several tension cyclic tests were carried, using a filled silicone rubber material, in order to evidence the anisotropy of the stress-softening phenomenon. The results lead to the conclusion that tensile cycles in one direction practically do not cause the Mullins effect in tension in the perpendicular direction. Nevertheless, the level of influence of the Mullins effect developed in one tension direction on tension behavior for intermediate directions could be measured with respect the different angles in plane. Thus, the anisotropy of the Mullins effect becomes clearly evident. maximum, nonlinear elastic behavior prevails. One time the previous maximum stretch is reached the loading path turns up and follows the primary curve again up to a new maximum.

Through the years, the Mullins effect has experimentally been observed in different deformation states and numerous models have been proposed, but experimental data concerning the influence of loading cycles in one direction on the stresssoftening in other directions are quite scarce. [START_REF] Mullins | Effect of stretching on the properties of rubber[END_REF] has alluded that the degree of softening was not the same in all directions for natural rubber samples cut both along and perpendicular to the direction of the previous preconditioning stretch; and thus some anisotropic stress-strain properties were developed. This evidence, for example, can be found in a homogeneous plane-strain compression experiment by Pawelski (2001) and in a simple shear experiment performed by Muhr (1999) where simple shear loadings in different directions produce different responses. Other experimental results can be seen in Laraba (2003) using a carbon-black filled natural rubber, Diani (2006) for the commercial elastomer filled black (EPDM) and [START_REF] Itskov | Experimental observation of the deformation induced anisotropy of the Mullins effect in rubber[END_REF] for carbon-black filled acrylate rubber (ACM). All these experimental results point out the strain-induced anisotropy in orthogonal directions due to some in-plane preconditioning test procedure.

Within that context, the aims of this work are to characterize and understand the mechanical behavior of a filled silicone. The objective is to focus on the strain-induced anisotropy by studying the influence of loading direction on the Mullins effect.

EXPERIMENTAL SETUP

Preparation of the silicone specimens

The samples used in the experiments were made of a filled silicone rubber called Rhodorsil ® RTV3428 supplied as two liquid components: the uncured silicone and the curing agent. The final material is produced by a polyaddition, curing at room temperature. The liquid mixture is injected in a mold to obtain a sheet with constant thickness.

Specimens used for each of the experiments were made using the same protocol of elaboration, in order to obtain specimens with reproducible mechanical properties, as follow: (i) mixing the components with a 10/1 mass ratio, (ii) putting the mixture under vacuum for 20 minutes in order to eliminate undesirable entrapped air bubbles, (iii) sheet molding injection, (iv) putting mold inside an oven 70ºC for 4 hours in order to accelerate the curing process and assure a sufficient crosslinking density; (v) sheet demolding after 1 hour exposed at ambient temperature.

Finally, the external surface of the molded plate was coated with a stochastic silicone paint pattern. Made of small speckles, the pattern is necessary for the digital image correlation (DIC) field measurement. Note that the quality of the coated pattern (size, density and gray contrast level) is a critical point to obtain an accurate strain field measurement.

Testing procedures

All the quasi-static experiments were conducted on a MTS 4M universal testing machine with an Entran ELPM-T2 ± 250 N load cell. The images were recorded at 0.5 Hz with a Jai TM-4200GE CCD camera using a reduced scan of 2048 × 1000 pixels. Figure 1 presents the experimental setup. Simple tensile tests were performed on rectangular samples having an initial gauge length l o = 40 mm, width w o = 13 mm and a thickness e o = 2 mm. Since the experiment was not intended to fail the specimen, there was no need to use a dumbbell shaped specimen commonly used to prevent specimen failure nearby the clamps. But knowing that the effects of clamps create an indeterminate state of stress and strain in the region surrounding the clamps, due to the process of gripping, the initial gauge length was adopted as being less than the real physical size of the samples. Figure 2 presents the tensile test specimen together with the grid used by the DIC software to estimate strain fields in the gauge region. For all tests, homogeneity of strain fields in the gauge region has been verified and elongations are averaged values.

Strain field measurement

The DIC technique like a non-contact method is often used to characterize rubber-like materials, see for example Meunier (2008) and [START_REF] Sasso | Characterization of hyperelastic rubber-like materials by biaxial and uniaxial stretching tests based on optical methods[END_REF]. At each testing time step, one image of the sample deformation was recorded using a CCD camera. The DIC technique allows surface reconstruction of the deformed samples and determination of the full-field surface displacements. For the in-plane displacement an accuracy of 10 -2 pixels or better can be reached. For point-to-point strain, the accuracy value lies around 10 -4 . The DIC method is preferred because there is no change in sample stiffness resulting from the presence of an attached sensor (classical extensiometry) and for being insensitive to ambient vibrations and rigid body motions (speckle pattern interferometry). Moreover the method is able to deal with high strain levels, what is a very desirable feature given the high strain level experienced by the tested material. Also the DIC allows demonstrating and measuring a heterogeneous deformation field. See [START_REF] Sutton | Digital Image Correlation for Shape and Deformation Measurements[END_REF] for further explanation about digital image correlation method.

RESULTS

Simple tensile strain state

During the test, using an elongation rate of λ′ = 1.60 × 10 -2 s -1 , the nominal stress tensor P (First Piola-Kirchhoff stress tensor) is assumed to be homogeneous within the gauge region as well as the deformation gradient tensor F.

Since the actual thickness is not measured, the material is assumed to be incompressible, i.e., det(F) = 1 for convenience. In the central zone, the deformation gradient, considering that the direction 1 is the tensile loading one, is given by

F e E e E e E = ⊗ ( )+ ⊗ ⊗ ( ) - λ λ 1 1 2 1 2 2 3 3 / + (1)
and the nominal stress tensor P = ⊗ ( )

P 11 e E 1 1
(2)

where (E 1 , E 2 , E 3 ) and (e 1 , e 2 , e 3 ) are the orthonormal basis used for the initial and current configurations, respectively. In a second time, a tensile specimen has been subjected to a load/unload sequence at different elongation rates λ′ = 25 × 10 -4 s -1 to λ′ = 125 × 10 -2 s -1 in order to verify the rate-dependence influence. No noticeable difference between stress-strain responses was observed at the considered strain rate range. Consequently the RTV3428 behavior can be assumed indepen dent of the rate of deformation for the observed ranges.

A cyclic tensile loading test was realized, the results are presented in Figure 3. Different phenomena are highlighted, first a large Mullins effect appears by comparing the two first loadings at each strain level, but with very little residual elongation. Moreover, a little hysteresis (difference between second and subsequent loadings and unloadings) is observed.

Directional influence

In order to study the anisotropy induced by the Mullins effect, two identical large specimens l o = 100 mm, width w o = 70 mm and e o = 2 mm of thickness were submitted to one cycle of stretch, at λ = 2.45 in uniaxial tension along a principal direction referred to 0º. Then, a set of smaller specimens was cut from each of these preconditioned large samples along four different directions 0º (first loading direction), 30º, 45º and 90º (orthogonal direction). An illustration is presented in Figure 4. All the cut specimens have been submitted to the same initial strain state (this has been verified thanks to the DIC measures). Figure 5 presents the second loading and unloading curves for the different cut specimens.

It clearly appears that all these second loading curves come back on the first loading curve at the same maximum elongation. Moreover, the subsequent unloading curves are almost independent of the history. The main difference is the shape of the second loading curve, the amount of stress-softening can be relied to the angle between the two loading directions.

As represented by [START_REF] Shariff | An anisotropic model of the Mullins effect[END_REF] and Diani (2006b), Figure 6 shows the stress ratio between the first virgin load curve and the set of sub-samples orientated at 0º, 30º, 45º and 90º directions. The curves highlight that there is no proportionality between the different curves, moreover there is no easy link between the second loading curves.

Figure 7 presents the evolution of the loss energy by Mullins effect according to the loading angle. where a o = 0.460, a 1 = 0.440, a 2 = 0.093 and ω = 2.0.

It appears that the function evolves from a maximum of stress-softening, when the two loadings are in the same direction and a minimum, close to zero, when the directions are orthogonal. That means that, at least, two parameters are necessary to describe the Mullins effect: the maximum stretch criteria and the angle between the first and second loading.

CONCLUSION

In the present work we have conducted an experimental campaign to build evidence showing that the Mullins effect in filled silicone rubbers is, in general, non-isotropic. The reproducibility and accuracy of measurements were evaluated through several successive tests. Results have shown that our protocol to manufacture the silicone specimens without any pre-existent anisotropy and our experimental methodology work well and provide a precise experimental characterization of softening phenomena. Using the DIC method as a non-contact full-field optical measurement, a large strain level was achieved. The results have shown that tensile cycles in one direction hardly cause any softening in the perpendicular direction. In addition, the results with respect to the influence of Mullins effect in the intermediate directions provide valuable information for testing and calibrating numerical models.

Finally, the anisotropy of the Mullins effect becomes clearly evident and should be taken into account in the constitutive modeling of filled elastomers.

Figure 1 .

 1 Figure 1. Testing machine with tensile test specimen, load cell and CCD camera.

Figure 2 .

 2 Figure 2. Uniaxial test specimen dimensions and the homogeneous gauge zone.

Figure 3 .

 3 Figure 3. Cyclic loading-unloading tensile test with increasing maximum stress: 0.2, 0.4. 0.6 and 0.8 MPa at λ′ = 1.60 × 10 -2 s -1 .

Figure 5 .

 5 Figure 5. Anisotropy induced by Mullins effect of a filled silicone RTV3428, superposed uniaxial stress-strain responses (load-unload).

Figure 6 .

 6 Figure6. Stress ratio between the first virgin load curve and the set of sub-samples, for sub-samples orientated at 0º, 30º, 45º and 90º (perpendicular) directions.

Figure 7 .

 7 Figure 7. Ratio of energy loss according to the difference of angle loading.

Figure 4 .

 4 Figure 4. The large preconditioned sample and the different observed orientations.

ACKNOWLEDGEMENTS

We would like to thank the French ANR for supporting this work through the project RAAMO ("Robot Anguille Autonome pour Milieux Opaques").