Pierre-Anthony Grenier
email: pierre-anthony.grenier@ensicaen.fr

Luc Brun
email: luc.brun@ensicaen.fr

Didier Villemin
email: didier.villemin@ensicaen.fr

Taking into account interaction between stereocenters in a graph kernel framework

Keywords: Graph kernel, Chemoinformatics, Stereoisomerism

An important field of chemoinformatics consists in the prediction of molecule's properties, and within this field, graph kernels constitute a powerful framework thanks to their ability to combine a natural encoding of molecules by graphs, with classical statistical tools. Unfortunately some molecules encoded by a same graph and differing only by the three dimensional orientation of their atoms in space have different properties. Such molecules are called stereoisomers. These latter properties can not be predicted by usual graph methods. In this report, ordered graphs are introduced in order to represent those molecules. Then the stereoisomerism property of each atom of a molecule is encoded by a local ordered subgraph. Finally a graph of interactions between those local subgraphs is constructed.

Introduction

The prediction of molecule's properties through Quantitative Structure Activity (resp. Property) Relationships are two active research subfields of chemoinformatics named QSAR and QSPR. Methods of those fields are based on the similarity principle: two structurally similar molecules should have similar properties.

One common method to predict chemical properties consists to design a vector of descriptors from a molecule and use statistical machine learning algorithms to predict molecule's properties. Such methods [START_REF] Cherqaoui | Use of a neural network to determine the boiling point of alkanes[END_REF][START_REF] Golbraikh | Qsar modeling using chirality descriptors derived from molecular topology[END_REF], can use structural information, physical properties or biological activities in order to compute vectors of descriptors. However, such an approach requires to either select a random set of predefined descriptors (before a variable selection step) or to use an heuristic definition of appropriate descriptors by a chemical expert. In both cases, the transformation of the graph into a finite vector of features induces a loss of information.

Another approach consists to encode a molecule by a graph, and use it to predict properties. A molecular graph is a labeled simple graph G = (V, E, µ, ν) representing a molecule. The unlabeled graph (V, E) encodes the structure of the molecule, each node v ∈ V encoding an atom and each edge e = (v, w) ∈ E a bond between two atoms. The labelling function µ associates to each vertex v ∈ V a label µ(v) encoding the nature of the atom and the function ν associates to each edge e a type of bond ν(e) (single, double, triple or aromatic). Note that for the rest of this report, we denote the neighborhood of a vertex v ∈ V by N (v):

∀v ∈ V, N (v) = {u ∈ V | (v, u) ∈ E}
Note that v does not belong to N (v).

Several methods based on graph theory use this representation to predict molecular properties. One approach consists to search subgraphs with a large difference of frequencies between a set of positive and a set of negative examples [START_REF] Poezevara | Discovering emerging graph patterns from chemicals[END_REF]. Another approach consists to encode each class of molecules by a graph prototype and to measure the structural similarity between each prototype and an input molecule [START_REF] Brun | Symbolic learning vs. graph kernels: An experimental comparison in a chemical application[END_REF]. However, these methods can not be easily combined with machine learning algorithms. Conversely graph kernel methods can be coupled to machine learning algorithms provided that the kernel is definite positive. Let G be the set of all graphs. A definite positive kernel is a symmetric function k : G × G → R such that: n i=1 n j=1 c i c j k(G i , G j ) ≥ 0 where n > 0, G 1 , . . . , G n ∈ G, c 1 , . . . , c n ∈ R Such a definite positive kernel corresponds to a scalar product between two vectors ψ(G) and ψ(G ) in an Hilbert space induced by the kernel.

A large family of graph kernel methods, associate a bag of patterns to each graph, and define the kernel value from a measure of similarity between those bags [START_REF] Kashima | Marginalized kernels between labeled graphs[END_REF][START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF][START_REF] Gaüzère | Two New Graphs Kernels in Chemoinformatics[END_REF]. In [START_REF] Kashima | Marginalized kernels between labeled graphs[END_REF] a graph kernel is defined as a measure of similarity between sets of walks extracted from each graph. But those walks are linear features and thus have limited expressiveness. An infinite set of tree patterns is used in [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF] to define kernels. However, the similarity between two graphs is based on an implicit enumeration of their common tree patterns which does not allow to readily analyze the influence of a pattern on the prediction. Finally [START_REF] Gaüzère | Two New Graphs Kernels in Chemoinformatics[END_REF] is based on an explicit enumeration of patterns. All subtrees of a labeled graph up to size 6, called treelets are enumerated.

However, some molecules may have a same molecular formula, a same molecular graph but a different relative positioning of their atoms. Such molecules are said to be stereoisomers. Different stereoisomers may be associated to different properties. However, usual graph kernels based on the molecular graph representation are not able to capture any dissimilarity between these molecules encoded by a same graph. From a more local point of view, an atom or two connected atoms are called stereocenters if a permutation of the positions of two atoms belonging to the union of their neighborhoods produces a different stereoisomer.

One example of stereocenter is an asymmetric carbon, which is a carbon atom with four different neighbors. We can represent each of its neighbors on a summit of a tetrahedron. If we permute two of the atoms, we obtain a different spatial configuration and hence an alternative stereoisomer (Figure 1a). Two carbons, connected by a double bond, can also define stereoisomers (Figure 1b). Indeed, on the left side of Figure 1b fluorine (F) and iodine(I) atoms are located on the same side of the double bond while they are located on opposite sides on the stereoisomer represented on the right. In this case both carbon atoms of the double bond correspond to a stereocenter.

According to chemical experts [START_REF] Jacques | Enantiomers, racemates, and resolutions[END_REF], within molecules currently used in chemistry, 98% of stereocenters correspond either to asymmetric carbons (Figure 1a) or to couples of two carbons adjacent through a double bond (Figure 1b). We thus restrict the present report to such cases.

To distinguish those configurations, we introduce the two following subsets of the set of vertices V of a molecular graph:

Definition 1. Potential Asymmetric Carbons

Let us denote V P AC the subset of V containing all vertices encoding atoms of carbon with four neighbors:

V P AC = {v ∈ V | µ(v) = 'C' and |N (v)| = 4}
Since being an atom with four neighbors is a necessary condition to define an asymmetric carbon, the set V P AC contains all vertices which may encode such atoms.

Definition 2. Set of double-bonds connecting carbon atoms

The subset of V containing all atoms of carbon which share a double bond with another carbon is noted V DB :

V DB =    v ∈ V | ∃e(v, w) ∈ E, ν(e) = 2,   |N (v)| = |N (w)| = 3 and µ(v) = µ(w) = 'C'   
An atom of carbon with two double bounds must have a degree equal to two. Hence, each vertex v belonging to V DB is incident to a single double bound and we denote n = (v) the other carbon connected by this double bond. Note that n = (v) ∈ V DB .

Brown et al. [START_REF] Brown | Compound analysis via graph kernels incorporating chirality[END_REF] have proposed to incorporate this information through an extension of the tree-pattern kernel [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF]. In this method, similarity between molecules are deduced from the number of common tree-patterns between two molecules. These patterns take into account the configuration around stereocenters. One drawback of this method is that, patterns which encode stereo information, and patterns which do not, are combined without any weighting in the final kernel value. So for a property only related to stereoisomerism, patterns that do not encode stereo information may be assimilated to noise which deteriorates the prediction. When several stereocenters are close to each other, one pattern may encode all of them. However the size of patterns are limited, so in some cases the influence of a permutation around stereocenters may not be detected by patterns containing them.

Intuitively, stereoisomerism property is related to the fact that permuting two neighbors of a stereocenter produces a different spatial configuration. If those two neighbors have a same label, the influence of the permutation should be searched beyond the direct neighborhood of this stereocenter. Based on this ascertainment, we have proposed in [START_REF] Grenier | A graph kernel incorporating molecule's stereisomerism information[END_REF] to characterized locally a stereocenter by a subgraph, big enough to highlights the influence of each permutation of neighbors of this stereocenter. We then proposed a kernel based on those subgraphs.

One drawback of our previous approach is that each subgraph, and thus each stereocenter, are considered independently.

In the next section we present an encoding of molecules distinguishing stereoisomers, which was introduced in our previous report [START_REF] Grenier | Incorporating stereo information within the graph kernel framework[END_REF]. In Section 3 we present the construction of a subgraph, which allows to characterizes locally a stereocenter, introduced in [START_REF] Grenier | A graph kernel incorporating molecule's stereisomerism information[END_REF]. Then in Section 4 we present a method which take into account interactions between the different subgraphs which characterize stereocenters. Finally, we demonstrate the validity of our kernel through experiments in Section 5.

Encoding of stereoisomers

The spatial configuration of the neighbors of each atom may be encoded through an ordering of its neighborhood. For example, considering the left part of Figure 1a, and looking at the central carbon from the hydrogen atom (H), the sequence of remaining neighbors of the carbon: Cl, Br and F may be considered as lying on a plane and are encountered clockwise. Thus, this spatial configuration is encoded by the sequence H, Cl, Br, F and the sequence H, Br, Cl, F encodes the second configuration. The configuration around a double bond can also be encoded by ordered sequences. Considering the left part of Figure 1b and assuming a clockwise orientation with the plane embedding provided by this figure, we encounter F and Cl when turning around the carbon at the top of the molecule, and H and O for the carbon at the bottom. Thus this configuration may be encoded by both sequences F, Cl and H, O respectively for the top and bottom carbon atoms. Sequences F, Cl and O, H encode the second configuration.

In order to encode this information in a graph, we have introduced in [START_REF] Grenier | Incorporating stereo information within the graph kernel framework[END_REF] ordered graphs:

Definition 3. Ordered Graphs
An ordered graph G = ( G = (V, E, µ, ν), ord) is a molecular graph G and a function ord which maps each vertex v belonging to a subset V ord of V to an ordered list of its neighbors:

ord V ord → V * v → v 1 . . . v n
where N (v) = {v 1 , . . . , v n } denotes the neighborhood of v.

V ord is defined as V P AC ∪ V DB . The function ord is defined as follows for each vertex v ∈ V ord :

-If v ∈ V P AC :
We set randomly one of its neighbor v 1 at the first position. The three other neighbors of v are ordered such that if we look at v from v 1 , the three remaining neighbors are ordered clockwise. One of the three orders (defined up to circular permutations) fulfilling this condition is chosen randomly (Figure 2a).

-If v ∈ V DB :
Let us consider w = n = (v) and the two neighborhoods N (v) = {w, a, b} and N (w) = {v, c, d}. The order on the neighborhood of v is set as ord(v) = w, a, b and the order on w's neighborhood is set as ord(w) = v, c, d, whereby a, b, c, d are traversed clockwise when turning around the double bond for a given plane embedding (Figure 2b).

The set of ordered graph is denoted OG.

Lemma 1. Let G = ( G = (V, E, µ, ν), ord) and G = ( G = (V , E , µ , ν ), ord ) be two ordered graph such that it exists f in Isom( G, G ).

Then f (V ord ) = V ord Proof. By Definition 1, v ∈ V P AC ⇔ µ(v) = 'C' and |V (v)| = 4. As f is an isomorphism we have µ(v) = 'C' and |V (v)| = 4 ⇔ µ(f (v)) = 'C' and |V (f (v))| = 4.
Then again by Definition 1, v

∈ V P AC ⇔ f (v) ∈ V P AC . By Definition 2, v ∈ V DB ⇔ ∃e(v, w) ∈ E, ν(e) = 2, |V (v)| = |V (w)| = 3, and µ(v) = µ(w) = 'C'. As f is an isomorphism we have ∃e(v, w) ∈ E, ν(e) = 2, |V (v)| = |V (w)| = 3, and µ(v) = µ(w) = 'C' ⇔ ∃e (f (v), f (w)) ∈ E, ν(e ) = 2, |V (f (v))| = |V (f (w))| = 3, and µ(f (v)) = µ(f (w)) = 'C'. Then again by Definition 2, v ∈ V DB ⇔ f (v) ∈ V DB .
By Definition 3, we have

V ord = V P AC ∪ V DB , so v ∈ V ord ⇔ f (v) ∈ V ord . Thus f (V ord ) = V ord .

Definition 4. Isomorphism between Ordered Graphs

Two ordered graphs G and G are isomorphic (G o G ) if there exists an isomorphism f between their respective molecular graphs G and G which respect the order around each vertex:

G o G ⇔ ∃f ∈ Isom( G, G ) s.t. ∀v ∈ V ord with ord(v) = v 1 . . . v n , ord (f (v)) = f (v 1 ) . . . f (v n )
where

N (v) = {v 1 , . . . , v n } denotes the neighborhood of v. Notice that by Lemma 1, if v ∈ V ord then f (v) ∈ V ord , so ord (f (v)) is always defined.
In this case, f is called an ordered isomorphism between G and G , and we denote IsomOrd(G, G ) ⊂ Isom( G, G ) the set of ordered isomorphism between G and G .

As we have to make some arbitrary choice to define an order (Definition 3), a spatial configuration of atoms may be encoded by several equivalent orders. We thus have introduced in [START_REF] Grenier | Incorporating stereo information within the graph kernel framework[END_REF] the notion of re-ordering function, which associates to each vertex of an ordered structured object a permutation on its neighborhood.

Definition 5. Re-ordering functions

A re-ordering function σ on an ordered graph

G = ( G = (V, E, µ, ν), ord), associates to each vertex v ∈ V ord a permutation ϕ v on {1, . . . , |N (v)|}. σ V ord → P v → ϕ v ∈ Π |N (v)|
where Π n is the group of permutations of n elements and P is the union of Π n for all n ∈ N.

Application of a re-ordering function on an ordered graph provides a new ordered structured graph defined as follows: Definition 6. Re-ordered structured objects Let G = ( G = (V, E, µ, ν), ord) denotes an ordered graph, σ(G) = ( G, ord σ ) is defined as the ordered graph obtained after applying the re-ordering function σ on the ordered list of neighbours of each vertex:

∀v ∈ V ord s.t.   ord(v) = v 1 , . . . , v n and σ(v) = ϕ v ,   ord σ (v) = v ϕv(1) , . . . , v ϕv(n)
Re-ordering functions previously defined may apply any re-ordering on a structured object hence removing the notion of order on these objects. In order to obtain a useful notion of re-ordering, we define a set of specific re-ordering functions.

Definition 7. Set of re-ordering functions

The set Σ of re-ordering functions contains all the re-ordering functions σ such that:

-For each v in V P AC , σ(v) is an even permutation:

∀v ∈ V P AC , (σ(v)) = 1.
-For each v in V DB , σ(v) and σ(n = (v)) have the same parity:

∀v ∈ V DB , (σ(v)) = (σ(n = (v)))
where denotes the signature of a permutation.

With this set we can define a notion of equivalent orders, such that two identical molecules will be represented by ordered graphs of equivalent orders.

∃σ ∈ Σ s.t σ(G) o G (1)
In other word, we consider that two ordered graphs are equivalent if, up to a valid re-ordering σ we can establish an ordered graph isomorphism f between them. In that case the ordered isomorphism f is called an equivalent ordered isomorphism through σ between G and G . We denote by IsomEqOrd(G, G ) the set of equivalent ordered isomorphism between G and G :

IsomEqOrd(G, G ) = σ∈Σ IsomOrd(σ(G), G )
As the set defined in Definition 7 is a valid family of re-ordering functions [START_REF] Grenier | Incorporating stereo information within the graph kernel framework[END_REF], the relationships defined in Definition 8 is an equivalence relationship [START_REF] Grenier | Incorporating stereo information within the graph kernel framework[END_REF]. We have thus now a way to encode stereoisomers.

Potentials asymmetric carbons, and double bonds between carbons, are not necessarily stereocenters. For example if the label of vertex Br of Figure 1a is replaced by Cl, both left and right molecules of Figure 1a would be identical. In the same way, if the label of the vertex F in Figure 1b is replaced by Cl, the left and right molecules of this figure would also become identical. For those cases, any permutation in the ordered list of the carbons would lead to an equivalent ordered graph, i.e it exists an equivalent ordered isomorphism between the graph and a permuted graph :

Definition 9. Set of Isomorphism of non-stereocenter Let G = ( G = (V, E, µ, ν), ord) be an ordered graph. Let v ∈ V ord .
We denote by F v G the set of ordered isomorphism f such that :

F v G = (i,j)∈{1,...,|N (v)|} 2 i =j {f | f ∈ IsomEqOrd(G, τ v i,j (G)) with f (v) = v}
where τ v i,j is a re-ordering function equals to the identity on all vertices except v for which it permutes the vertices of index i and j in ord(v).

We define a stereo vertex as a vertex for which any permutation of two of its neighbors produces a non-equivalent ordered graph:

Definition 10. Stereo vertices Let G = ( G = (V, E, µ, ν), ord) be an ordered graph. A vertex v ∈ V ord is called a stereo vertex iff: F v G = ∅ We denotes SV(G) the set of stereo vertices of G. Lemma 2. Let us consider a graph G and one of its automorphism f , f ∈ Isom( G, G). ∀v ∈ V DB s.t f (v) = v, we have f (n = (v)) = n = (v). Proof. Let v ∈ V DB with f (v) = v. By Definition 2 ∃!w ∈ V s.t e = (v, w) ∈ E with ν(e) = 2 and w = n = (v). Since f is an isomorphism (f (v), f (w)) = (v, f (w)) ∈ E with ν((f (v), f (w))) = 2.
By Definition 2, w is the unique neighbor of v incident to an edge with a label 2, so we have f (w) = w.

Proposition 1. v ∈ V DB is a stereo vertex iff n = (v) is a stereo vertex. Proof. We consider an ordered graph G = ( G = (V, E, µ, ν), ord). Let us consider v ∈ V DB . We denote w = n = (v) ∈ V DB . Let us suppose that v ∈ SV(G). Then F v G = ∅ and so, ∃(i, j) ∈ {1, 2, 3} 2 , with i = j, ∃f ∈ IsomEqOrd(G, τ v i,j (G)) with f (v) = v
, where τ v i,j is a re-ordering function equals to the identity on all vertices except v for which it permutes the vertices of index i and j in ord(v).

As f ∈ IsomEqOrd(G, τ v i,j (G)) ⊂ Isom( G, G), by Lemma 2 we have f (w) = w.
We define σ = τ w i ,j • τ v i,j where (i , j ) ∈ {1, 2, 3} 2 s.t i = j . By Definition 7 and since (σ(v)) = (τ v i,j ) = -1 and (σ(w)) = (τ w i ,j ) = -1, σ is a valid re-ordering function.

By Definition 8, ∃σ ∈ Σ s.t f is an ordered isomorphism between σ (G) and τ v i,j (G). Thus, by [START_REF] Grenier | Incorporating stereo information within the graph kernel framework[END_REF](Lemma 1), f is an ordered isomorphism between σ • σ (G) and σ • τ v i,j (G) = τ w i ,j (G). As the valid family of re-ordering function is a group [START_REF] Grenier | Incorporating stereo information within the graph kernel framework[END_REF]

σ • σ ∈ Σ, and thus f ∈ IsomEqOrd(G, τ w i ,j (G)) with f (w) = w. So F w G = ∅ So v ∈ SV(G) implies that w = n = (v) ∈ SV(G). Since ∀u ∈ V DB , n = (n = (u)) = u, this last statement is equivalent to : n = (u) ∈ SV(G) ⇒ u ∈ SV(G)
The contrapositive of the above implication provides the expected implication. Furthermore, an additional use of the relationship n = (n = (u)) = u provides the expected equivalence relationship.

As Proposition 1 shows, two carbons linked by a double bond are simultaneously stereo vertices or non-stereo vertices. So we have to consider their stereo property together. We thus introduce the following notations :

Definition 11. Set of bounded Stereo vertices

For s ∈ SV(G) we define its set kernel(s) of bounded stereo vertices as :

kernel(s) = {s} if s ∈ V P AC {s, n = (s)} if s ∈ V DB Definition 12.

Star of Stereo vertices

For s ∈ SV(G) we define its set StereoStar(s):

StereoStar(s) = N (s) ∪ {s} if s ∈ V P AC N (s) ∪ N (n = (s)) if s ∈ V DB Definition 13.

Set of neighbours of Stereo vertices

For s ∈ SV(G) we define its set of neighbour StereoStar * (s):

StereoStar * (s) = N (s) if s ∈ V P AC N (s) ∪ N (n = (s) -{s, n = (s)} if s ∈ V DB Note that StereoStar * (s) = StereoStar(s) -kernel(s).

From a global to a local characterization of stereo information

Definition 10 is based on the whole graph G to test if a vertex v is a stereo vertex. However, given a stereo vertex s, one can observe that on some configurations, the removal of some vertices far from s should not change its stereo property.

In order to obtain a more local characterization of a stereo vertex, we should thus determine a vertex induced subgraph H of G, including s, big enough to characterize the stereo property of s, but sufficiently small to encode only the relevant information characterizing the stereo vertex s. Such a subgraph is called a minimal stereo subgraph of s.

Definition 14. Subgraph characterizing a Stereo vertex

Let G = ( G = (V, E, µ, ν), ord) be an ordered graph. Let S be a subgraph of G. We say that the stereo property of s ∈ SV(G) is captured by S if:

-StereoStar(s) ⊂ S. -F s S = ∅.
Remark 1. With the same argument than for the proof of Proposition 1, we can show that if the stereo property of s ∈ SV(G) is captured by S and s ∈ V DB then the stereo property of n = (s) is captured by S. Thus a couple of carbons linked by a double bond only needs one subgraph to characterizes both of them.

Definition 15. Set of vertices inducing isomorphism

Let G = ( G = (V, E, µ, ν), ord) be an ordered graph. Let s be a stereo vertex. Let H be a subgraph of G that do not capture the stereo property of s and such that StereoStar(s) ⊂ H.

By Definition 14, F s H is not empty. Let f ∈ F s H . We define E H f as the set of vertices inducing the isomorphism f in H:

E H f = {v ∈ V (H) | ∃p = (v 0 , . . . , v q ) ∈ H with v 0 ∈ kernel(s) and v q = v s.t. f (v 1 ) = v 1 } (2)
where (v 0 , . . . , v q ) denotes a path in H (Hence v 0 = v 1 ).

Proposition 2. For H and f defined as in Definition 15, E H f is not empty.

Proof. Let G = ( G = (V, E, µ, ν), ord) be an ordered graph. Let s be a stereo vertex. Let H be a subgraph of G that do not capture the stereo property of s and such that StereoStar(s) ⊂ H. Let us consider f ∈ F s H . By definition of equivalent ordered isomorphism, it exists σ ∈ Σ such that f is an ordered isomorphism between H and σ τ s i,j (H) .

-If s ∈ V P AC : By definition of ordered isomorphisms, and since f (s) = s, we have:

∀l ∈ {1, . . . , |N (s)|}, f (v l ) = v σ(s)•τ s i,j (l) .
with ord(s) = v 1 , . . . , v n . As σ(s) is an even permutation, σ(s) • τ s i,j is an odd one. Hence it exists l in {1, . . . , |N (s)|} such that l = σ(s) • τ s i,j (l). Thus f (v l ) = v l , and

E H f is not empty as it contain at least v l . -If s ∈ V DB :
Let us consider w = n = (s). Since f ∈ IsomEqOrd(H, τ s i,j (H)) ⊂ Isom( H, H), by Lemma 2 we have f (w) = w. We denote by N (s) = {s 1 , s 2 , w} the neighbourhood of s and N (w) = {w 1 , w 2 , s} the neighbourhood of w. Let us suppose that f (w 1 ) = w 1 . As f (s) = s, we have f (w 2 ) = w 2 and since f is an ordered isomorphism between H and σ τ s i,j (H) we have σ(w) = Id where Id is the identity permutation. Thus (σ(s)) = (σ(w)) = 1 and σ(s) • τ s i,j is odd. Hence f defines an odd permutation on the ordered neighbour of s and f (w) = w, thus by definition of ordered isomorphisms, we have f (s 1 ) = s 2 = s 1 . Thus we have either f (w 1 ) = w 1 or f (s 1 ) = s 1 , so E H f is not empty as it contains at least w 1 or s 1 .

Definition 16. Minimal stereo subgraph

Let G = ( G = (V, E, µ, ν), ord) be an ordered graph. Let s ∈ SV(G). We consider a sequence (H k s ) k∈N of vertex induced subgraphs of G defined such that:

-V (H 0 s ) = StereoStar(s) -V (H k+1 s ) = V (H k s ) ∪ f ∈F H k s N (E H k s f ).
We define S s as:

S s = lim k→+∞ H k s
The vertex induced subgraph S s is called the minimal stereo subraph of s. We say that s is the stereo vertex of S s (if s ∈ V DB , the stereo vertex of S s is arbitrarily chosen between s and n = (s) as they have a same role). We denote H(G) the set of minimal stereo subraphs of G. Figure 3

∈ N V (H k+1 s ) = V (H k s ) ∪ f ∈F H k s N (E H k s f ). Thus (H k s ) k∈N is an increasing sequence.
As (H k s ) k∈N is upper bounded and increasing, (H k s ) k∈N converges.

Remark 2. (H k s ) k∈N is a sequence of vertex induced subgraphs of G, so it is a discrete sequence, and thus the limit is reached: ∃n ∈ N s.t ∀k > n, H k s = S s . Proposition 4. For any k ∈ N such that V (H k s ) = V (S s ), the stereo property of s is not captured by

H k s . Proof. We consider k ∈ N such that V (H k s ) = V (S s ). As H k+1 s is only constructed from H k s (V (H k+1 s ) = V (H k s ) ∪ f ∈F H k s N (E H k s f )),
and

V (H k s ) = V (S s ), we have V (H k s ) = V (H k+1 s ). Thus f ∈F H k s N (E k f ) = ∅. So it exists at least one f ∈ F H k s such that E k f = ∅
and thus F H k s = ∅. Then by Definition 14 and 9 the stereo property of s is not captured by H k s .

Lemma 3. Let G = ( G = (V, E, µ, ν), ord) be an ordered graph. Let s be a stereo vertex. Let H be a connected vertex induced subgraph of G that do not capture the stereo property of s and such that StereoStar(s) ⊂ H. Let f ∈ F s H . We denotes cc 1 . . . cc n the set of connected components obtained by removing kernel(s) from H.

We define the sets of indices :

-I = {i | cc i ∩ E H f = ∅}. -J = {j | cc j ∩ E H f = ∅}.
We denote cc I = i∈I cc i and cc J = j∈J cc j .

Then we have :

cc I ⊂ E H f . ( 3
) ∀j ∈ J , cc j ∩ StereoStar * (s) = ∅ and ∀v ∈ cc j ∩ StereoStar * (s) we have f (v) = v. ( 4
)
Proof. We first show that:

cc I ⊂ E H f .
Let i ∈ I. By definition of I we have cc i ∩ E H f = ∅. We denote u one vertex such that u ∈ cc i and u ∈ E H f . By definition of E H f , it exists a path p u = (u 1 , . . . , u q ) ∈ H with u q = u, u 1 ∈ StereoStar * (s) and f (u 1 ) = u 1 . As cc i is a connected component of H -kernel(s), we have that p u ∈ cc i and so

u 1 ∈ cc i . As cc i is a connected component ∀v ∈ cc i , ∃p = (u 1 , v 1 , . . . , v) ∈ cc i . So v ∈ E H f and cc i ⊂ E H f .
We now show that:

∀j ∈ J , cc j ∩ StereoStar * (s) = ∅ and ∀v ∈ cc j ∩ StereoStar * (s) we have f (v) = v.
H is connected, thus for each u ∈ H, ∃p = (u 0 , . . . , u q ) ∈ H with u q = u and u 0 ∈ kernel(s). So ∀u ∈ cc j , ∃p = (u 1 , . . . , u q ) ∈ cc j with u q = u and u 1 ∈ StereoStar * (s). Hence u 1 ∈ cc j and cc

j ∩ StereoStar * (s) = ∅ Let us consider v ∈ cc j ∩ StereoStar * (s), if we suppose that f (v) = v then v ∈ E H f and thus cc j ∩ E H f = ∅ is false. So ∀v ∈ cc j s.t v ∈ StereoStar * (s) we have f (v) = v.
Remark 3. By definition of cc I and cc J we have :

-V (H) = cc I ∪ cc J ∪ kernel(s) -V = V (G -H) ∪ cc I ∪ cc J ∪ kernel(s) Lemma 4.
With the same hypothesis and notations than in Lemma 3 we have:

f (cc I ) = cc I Proof. Let v ∈ cc i with i ∈ I.
Thus ∃p = (v 1 , . . . , v q ) ∈ H with v q = v, v 1 ∈ StereoStar * (s) and f (v 1 ) = v 1 . So the sequence (f (v 1 ), . . . , f (v q )) is also a path of H.

We denote ṽ1 = f (v 1 ).

As

v 1 ∈ StereoStar * (s), ṽ1 ∈ StereoStar * (s). As f (v 1 ) = v 1 and f is bijec- tive, f ( ṽ1 ) = f (f (v 1 )) = f (v 1 ) = ṽ1 .
In conclusion we have ∃p = ( ṽ1 , . . . , f (v q )) ∈ H with v q = v, ṽ1 ∈ StereoStar * (s) and f ( ṽ1 ) = ṽ1 , so f (v) ∈ cc i with i ∈ I.

So f (cc

I ) ⊂ cc I . As f is bijective we have |f (cc I )| = |cc I |. So f (cc I ) = cc I .
Lemma 5. Using the same hypothesis and notations than in Lemma 3, ∀f ∈ F s H we have

N (E H f ) ⊂ V (H). Proof. Let us supposed N (E H f ) ⊂ V (H).
To obtain a contradiction we will construct an equivalent ordered isomorphism between G and τ s i,j (G). To prove that the function we will construct is an ordered isomorphism between G and τ s i,j (G) we will need some properties about the cc i and cc j defined previously which are consequences of our assumption

N (E H f ) ⊂ V (H).
We need to prove that we have :

∀v ∈ V (G-H), ∀p = (v 0 , . . . , v q ) with v 0 = v, v q ∈ H and kernel(s)∩p = ∅, we have v q ∈ cc J . (5)
Let us suppose that ∃v ∈ V (G -H), ∃p = (v 0 , . . . , v q ) with v 0 = v, v q ∈ H and kernel(s) ∩ p = ∅ such that v q ∈ cc i with i ∈ I.

Let us denote v r ∈ p with r ∈ {0, . . . , q -1} one vertex such that v r ∈ V (H) and v r+1 ∈ cc i . Such a vertex exists as v 0 ∈ V (H) and v q ∈ cc i .

As v r+1 ∈ cc i , v r+1 ∈ E H f by (3) of Lemma 3. Thus v r ∈ N (E H f ) and v r ∈ V (H). As we have supposed N (E H f ) ⊂ V (H) we have a contradiction, so v q ∈ cc J .

Equation ( 5) and Remark 3 implies that:

∀v ∈ V (G -H), N (v) ⊂ V (G -H) ∪ cc J (6) ∀v ∈ cc J , N (v) ⊂ V (G -H) ∪ cc J ∪ kernel(s) (7) ∀v ∈ cc I , N (v) ⊂ cc I ∪ kernel(s) (8)
Let us now define a function g such that:

∀v ∈ V, g(v) =    f (v) if v ∈ cc I v if v ∈ cc J ∪ V (G -H) v = f (v) if v ∈ kernel(s)
We want to prove that g ∈ IsomEqOrd(G, τ s i,j (G)).

First, we have to prove that g is bijective.

By Lemma 4 we have f (cc I ) = cc I so g(cc I ) = cc I . We have g cc I = f is bijective, g G-cc I = Id is bijective and g(cc I ) = cc I , so g is bijective.

We now prove that g ∈ Isom( G, G) = Isom( G, τ s i,j (G)). Let e = (u, v) ∈ E:

-If u ∈ cc I .
We have g(u) = f (u) and v ∈ cc I or v ∈ kernel(s) by ( 8). In both cases we have

g(v) = f (v). As f ∈ IsomEqOrd(H, τ s i,j (H)), (g(u), g(v)) = (f (u), f (v)) ∈ E. -If u ∈ cc J or u ∈ V (G -H).
We have g(u) = u and v ∈ V (G -H), v ∈ cc J or v ∈ kernel(s) by ( 6) and [START_REF] Gaüzère | Two New Graphs Kernels in Chemoinformatics[END_REF]. In each case we have

g(v) = v. Thus (g(u), g(v)) = (u, v) ∈ E. -If u ∈ kernel(s).
We have

g(u) = f (u) and v ∈ StereoStar * (s) or v ∈ kernel(s). If v ∈ cc I , then f (v) = g(v). However if v ∈ cc J , then g(v) = v. But by (4) of Lemma 3 we have v = f (v), so g(v) = v = f (v). Finally if v ∈ kernel(s), g(v) = v = f (v). So, in each case we have g(v) = f (v). As f ∈ IsomEqOrd(H, τ s i,j (H)), (g(u), g(v)) = (f (u), f (v)) ∈ E.
In each case we have either (g(u),

g(v)) = (f (u), f (v)) or (g(u), g(v)) = (u, v), thus : e = (u, v) ∈ E ⇒ e = (g(u), g(v)) ∈ E, ν(e) = ν(e ), µ(g(u)) = µ(u) and µ(g(v)) = µ(v). (9)
We define g such that:

g V × V → V × V (u, v) → (g(u), g(v))
As g is bijective, g is bijective.

By [START_REF] Grenier | Incorporating stereo information within the graph kernel framework[END_REF] we have g(E) ⊂ E, and as g is bijective we have g

(E) = E. So ∀(u, v) ∈ V × V , such that g(u, v) = (g(u), g(v)
) ∈ E we have (u, v) ∈ E. With [START_REF] Grenier | Incorporating stereo information within the graph kernel framework[END_REF] we can conclude that : 10) By ( 9) and [START_REF] Grenier | Incorporating molecules stereisomerism within the machine learning framework[END_REF]

e = (g(u), g(v)) ∈ E ⇒ e = (u, v) ∈ E, ν(e) = ν(e ), µ(g(u)) = µ(u) and µ(g(v)) = µ(v). (
we have g ∈ Isom( G, G) = Isom( G, τ s i,j (G)).
We finally have to prove that ∃σ ∈ Σ such that g ∈ IsomOrd(σ(G),

τ s i,j (G)). f ∈ IsomEqOrd(H, τ s i,j (H)) so by Definition 8 ∃σ ∈ Σ, σ(H) o τ s i,j (H).
We denote σ the re-ordering function such that:

∀v ∈ V ord , σ (v) = σ(v) if v ∈ cc I ∪ kernel(s) Id n if v ∈ cc J ∪ V (G -H)
where Id n is the identity permutation of n elements and n is the degree of v.

Let v ∈ V P AC . If v ∈ kernel(s)∪cc I then σ (v) = σ(v). σ ∈ Σ so by Definition 7 σ(v) is even. If v ∈ V (G -H) ∪ cc J then σ (v) = Id n . The identity is even, so ∀v ∈ V P AC , σ (v) is even. Let v ∈ V DB .
-

By Definition 11 v ∈ kernel(s) iff n = (v) ∈ kernel(s). So, if v ∈ kernel(s), then σ (v) = σ(v) and σ (n = (v)) = σ(n = (v)).
σ ∈ Σ so by Definition 7 σ(v) and σ(n = (v)) have a same parity.

-If v ∈ cc I then by (8) n = (v) ∈ cc I ∪ kernel(s). As n = (v) ∈ kernel(s) iff v ∈ kernel(s) (Definition 11) and v ∈ cc I , n = (v) ∈ kernel(s) and so n = (v) ∈ cc I . Thus σ (v) = σ(v) and σ (n = (v)) = σ(n = (v)).
σ ∈ Σ so by Definition 7 σ(v) and σ(n = (v)) have a same parity. 6) and [START_REF] Gaüzère | Two New Graphs Kernels in Chemoinformatics[END_REF]

-Finally if v ∈ V (G -H) ∪ cc J then by (
n = (v) ∈ V (G -H) ∪ cc J ∪ kernel(s). As n = (v) ∈ kernel(s) iff v ∈ kernel(s) (Definition 11) and v ∈ V (G -H) ∪ cc J , n = (v) ∈ kernel(s) and so n = (v) ∈ V (G -H) ∪ cc J . So σ (v) = Id n and σ (n = (v)) = Id n have a same parity.
Using Definition 7, we deduce from the previous considerations that σ ∈ Σ.

Let us now show that g ∈ IsomOrd(σ (G), τ s i,j (G)). We denote by ord the order in τ s i,j (G). We stress here that ∀v ∈ V ord -{s}, ord

(v) = ord(v). Let v ∈ V ord with ord σ (v) = v 1 , . . . , v n : -If v ∈ cc I .
We have g(v) = f (v). We know that σ(H)

o τ s i,j (H) and v ∈ H, so ord (g(v)) = ord (f (v)) = f (v 1 ), . . . , f (v n ).
By [START_REF] Golbraikh | Qsar modeling using chirality descriptors derived from molecular topology[END_REF] we know that ∀k ∈ {1, . . . , n} we have v k ∈ cc I or v k ∈ kernel(s). In both cases we have f

(v k ) = g(v k ) and thus ord (g(v)) = g(v 1 ), . . . , g(v n ). -If v ∈ cc J or v ∈ V (G -H).
We have

g(v) = v. So ord (g(v)) = ord (v). As v ∈ V ord -{s}, ord (v) = ord(v), and thus ord (g(v)) = ord(v). As σ (v) = Id n , we have ord(v) = ord σ (v) = v 1 , . . . , v n . So ord (g(v)) = v 1 , . . . , v n .
By [START_REF] Gaüzère | Two New Graphs Kernels in Chemoinformatics[END_REF] and ( 8) we know that ∀k ∈ {1, . . . , n} we have

v k ∈ V (G -H), v k ∈ cc J or v k ∈ kernel(s). So v k = g(v k ) and thus ord (g(v)) = g(v 1 ), . . . , g(v n ). -If v ∈ kernel(s).
We have

g(v) = f (v). We know that σ(H) o τ s i,j (H) and v ∈ H, so ord (g(v)) = ord (f (v)) = f (v 1 ), . . . , f (v n ). Let k ∈ {1, . . . , n}. If v k ∈ cc I , then f (v k ) = g(v k ). However if v k ∈ cc J , then g(v k ) = v k . But by (4) we have v k = f (v k ), so g(v k ) = v k = f (v k ). Thus ord (g(v)) = g(v 1 ), . . . , g(v n )
In each case we have ord (g(v)) = g(v 1 ), . . . , g(v n ), so σ (G) o τ s i,j (G). Thus g ∈ IsomEqOrd(G, τ s i,j (G)) and g(s) = s. This is not possible since

s ∈ SV(G), thus N (E H f ) ⊂ V (H).
Theorem 1. The stereo property of s is captured by S s .

Proof. We denote n ∈ N an integer such that H n s = S s (Remark 2). The sequence is initialized by V (H 0 s ) = StereoStar(s). As the sequence is increasing we have V (H 0 s ) ⊂ V (H n s ), so the first condition of Definition 14 is true.

We thus have to prove that F s

H n s = ∅. Let us suppose that ∃(i, j) ∈ {1, . . . , |N (s)|} 2 with i = j, ∃f ∈ IsomEqOrd(H n s , τ s i,j (H n s )) with f (s) = s. Thus by Lemma 5 we have N (E H n s f ) ⊂ V (H n s ). So V (H n+1 s ) = V (H n s ) ∪ f ∈F H k s N (E H k s f ) = V (H n s ).
This is in contradiction with the fact that H n s = S s = lim k→+∞ H k s , so the stereo property of s is captured by H n s = S s .

Thus for each stereo vertex we can construct its minimal stereo subgraph to characterize it. We consider two stereo vertices as similar if they have a same minimal stereo subgraphs, and to test it efficiently, we transform our minimal stereo subgraphs S into codes c S thanks to the method described in [START_REF] Wipke | Stereochemically unique naming algorithm[END_REF].

Interactions between stereo vertices

In the previous section we have defined a way to construct an oriented subgraph which characterizes a stereocenter. We may use the set of subgraphs, associated to each stereocenter of a molecule, to compare molecules. However two stereocenter may not have the same influence on a property if they are close from each other or far from each other in a molecule. In the same way, two same minimal stereo subgraph may not have a same influence on a property if they have different surroundings. We now propose to construct some new graphs, based on the set of minimal stereo subgraphs, to encode more information about those subgraphs.

Graphs of interaction

To represent the interactions between stereo vertices we define different functions of interactions, which encode different degrees of information about the interactions between stereo vertices:

Definition 17. Functions of interactions

Let G = (G m = (V, E, µ, ν), ord) an ordered graph and H(G) its set of minimal stereo subgraphs.

Functions of interactions are defined according to a sequence of conditions (c 0 , . . . , c n ). These conditions are increasingly constraining: ∀i ∈ {1, . . . , n -1} c i+1 ⇒ c i and c 0 = ¬c 1 Let H 1 and H 2 be two minimal stereo subgraphs, such that s 1 is the stereo vertex of H 1 and s 2 is the stereo vertex of H 2 . The value F (H 1 , H 2 ) is obtained by taking the maximum index j of conditions c j which represents the strongest interaction between H 1 and H 2 :

F (H 1 , H 2 ) = max{j ∈ {0, . . . , n} | c j }
We consider 4 sequences of conditions defining 4 functions of interactions F i :

-F 1 is defined by using

       c 1 : H 1 H 2 = ∅ c 2 : kernel(s 1 ) ⊂ H 2 c 3 : StereoStar(s 1 ) ⊂ H 2 c 4 : H 1 ⊂ H 2 -F 2 is defined by using    c 1 : H 1 H 2 = ∅ c 2 : StereoStar(s 1 ) ⊂ H 2 c 3 : H 1 ⊂ H 2 -F 3 is defined by using    c 1 : kernel(s 1 ) ⊂ H 2 c 2 : StereoStar(s 1 ) ⊂ H 2 c 3 : H 1 ⊂ H 2 -F 4 is defined by using c 1 : StereoStar(s 1 ) ⊂ H 2 c 2 : H 1 ⊂ H 2
Note that the F i is not symmetric.

We define thanks to those functions, 4 graphs of interactions G i where each vertex v ∈ V i represent a minimal stereo subgraph and each edge encode the interaction between two minimal stereo subgraphs.

Definition 18. Directed Graph of interactions

A directed graph of interactions

G i = (V i , A i , µ i , ν i ) is a graph constructed from an ordered graph G = (G m = (V, E, µ, ν), ord) such that : -∀u ∈ V i , ∃!H(u) ∈ H(G). -∀u ∈ V i , µ i (u) = c H(u)
, where c H is the code defined in [START_REF] Wipke | Stereochemically unique naming algorithm[END_REF] (Section 3).

-∃a = (u 1 , u 2 ) ∈ A i ⇐⇒ F i (H(u 1 ), H(u 2 )) = 0. -∀a = (u 1 , u 2 ) ∈ A i , ν i (a) = F i (H(u 1 ), H(u 2 ).
where F i is one of the function defined in Definition 17.

As very few nodes have the same label in the directed graph of interactions, the direction of edges does not provide a lot of information. We thus define undirected graphs of interactions, which encode not a lot less infromation than directed graphs of interactions, but which is simpler.

Definition 19. Graph of interactions

A graph of interactions G i = (V i , E i , µ i , ν i ) is a graph constructed from an ordered graph G = (G m = (V, E, µ, ν), ord) such that :

-∀u ∈ V i , ∃!H(u) ∈ H(G). -∀u ∈ V i , µ i (u) = c H(u)
, where c H is the code defined in [START_REF] Wipke | Stereochemically unique naming algorithm[END_REF] (Section 3).

-∃e = (u 1 , u 2 ) ∈ E i ⇐⇒ F i (H(u 1 ), H(u 2 )) = 0 or F i (H(u 2 ), H(u 1 )) = 0. -∀e = (u 1 , u 2 ) ∈ E i , ν i (e) = min(F i (H(u 1 ), H(u 2 )), F i (H(u 2 ), H(u 1 ))) max(F i (H(u 1 ), H(u 2 )), F i (H(u 2 ), H(u 1 ))).
where denotes the concatenation and F i is one of the function defined in Definition 17.

Figure 4 show all graphs of interactions we can construct from an ordered graph by taking the four different functions of interactions.

The first graph G 1 is constructed by taking 4 different types of interaction. However we may suppose that some of those type of interaction are less relevant than the other.

Indeed, a vertex s 1 is a stereo vertex because of the relative positioning of its neighbour. So we may suppose that, if a stereo vertex is present in a stereo subgraph (kernel(s 1 ) ⊂ H 2 ), but not its neighbourhood (StereoStar(s 1 ) ⊂ H 2 ), the stereo vertex may have a similar influence in H 2 than a non-stereo vertex. G 2 is thus constructed without taking kernel(s 1 ) ⊂ H 2 as a type of interaction.

We also may suppose that an intersection between two minimal stereo subgraphs may not be a sufficiently relevant information. Thus the graph G 3 is constructed with 3 different type of interaction, by considering that two stereo vertex are related if we have at least kernel(s 1 ) ⊂ H 2 or kernel(s 2 ) ⊂ H 1 .

Finally G 4 is constructed by taking the two previous assumptions together.

As graphs of interaction are graphs without order, we may apply any graph kernel (for the experiment in Section 5 we apply the treelet kernel [START_REF] Gaüzère | Two New Graphs Kernels in Chemoinformatics[END_REF]) to measure their similarity.

Experiments

We have tested our method on two datasets. For both of them we use the same protocol, a nested cross-validation, to choose the parameter and estimate the performance. The outer cross-validation is a leave-one-out procedure, used to compute an error for each molecule of the dataset. For each fold, we use another leave-one-out procedure on the remaining molecules, to compute a validation error. We use standard SVM method [START_REF] Cortes | Support-vector networks[END_REF][START_REF] Drucker | Support vector regression machines[END_REF] for classification and regression of molecules. Our first experiment is based on a dataset composed of all the stereoisomers of the perindoprilate [START_REF] Castillo-Garit | Atombased stochastic and non-stochastic 3d-chiral bilinear indices and their applications to central chirality codification[END_REF]. As this molecule has 5 stereocenters, the dataset is composed of 2 5 = 32 molecules. In this dataset, we try to predict if a molecule inhibit the angiotensin-converting enzyme (ACE). Basic statisistics about the graphs of interactions G i = (V i , E i , µ i , ν i ) deduced from this dataset is displayed in Table 2a. For this first experiment we have not included results of method which do not include stereoisomerism information [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF][START_REF] Gaüzère | Two New Graphs Kernels in Chemoinformatics[END_REF]. Indeed all molecules of the dataset are stereoisomers of each other, so those methods cannot differentiate any molecule of this dataset and are consequently unable to predict the considered property. Moreover, information not related to stereoisomerism included in kernel [START_REF] Brown | Compound analysis via graph kernels incorporating chirality[END_REF] consists of the same patterns for all molecules. This leads to add a constant shift to all values of the kernel and hence does not deteriorate the prediction for this dataset. In this dataset two stereocenters have a same minimal stereo subgraph, but different surrounding. The stereo kernel [START_REF] Grenier | A graph kernel incorporating molecule's stereisomerism information[END_REF] and one of the graph of interactions (G 4 ), can not differentiate those two stereocenters, which have different influence on the property, this explains why other method ( [START_REF] Brown | Compound analysis via graph kernels incorporating chirality[END_REF][START_REF] Grenier | Incorporating molecules stereisomerism within the machine learning framework[END_REF] and the three other graphs of interactions) obtain a better accuracy. However, for our graphs of interactions, treelet of size one have a negative effect on the classification, this explains why we do not obtain better results than [START_REF] Brown | Compound analysis via graph kernels incorporating chirality[END_REF][START_REF] Grenier | Incorporating molecules stereisomerism within the machine learning framework[END_REF]. By using a multiple kernel learning algorithm [START_REF] Varma | More generality in efficient multiple kernel learning[END_REF], we can learn a weight for each treelet, that allow us to discard treelet of size 1 and to obtain the best results with the first and second graph of interactions. The third graph of interactions have very few edges and a low degree (Table 2a) which explains why the treelet kernel with multiple kernel learning obtains poor results with this graph.

The second dataset is a dataset of synthetic vitamin D derivatives, used in [START_REF] Brown | Compound analysis via graph kernels incorporating chirality[END_REF]. This dataset is composed of 69 molecules, with an average of 9 stereocenters per molecule. This dataset is associated to a regression problem, which consists in predicting the biological activities of each molecules. As for the previous dataset, statistics about the graphs of interactions deduced from this dataset can be found in Table 2b.

Table 3: Prediction of the biological activity of synthetic vitamin D derivatives.

Method RMSE 1 -Tree patterns Kernel [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF] 0.251 2 -Treelet Kernel [START_REF] Gaüzère | Two New Graphs Kernels in Chemoinformatics[END_REF] 0.271 3 -Brown [START_REF] Brown | Compound analysis via graph kernels incorporating chirality[END_REF] 0.184 4 -Stereo Kernel [START_REF] Grenier | A graph kernel incorporating molecule's stereisomerism information[END_REF] 0.194 5 -Stereo + Extended subgraphs [START_REF] Grenier | Incorporating molecules stereisomerism within the machine learning framework[END_REF] 0.180 6 -Graph of interaction 1 0.177 7 -Graph of interaction 2 0.177 8 -Graph of interaction 3 0.169 9 -Graph of interaction 4 0.172

Methods which do not encode stereoisomerism information [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF][START_REF] Gaüzère | Two New Graphs Kernels in Chemoinformatics[END_REF] obtain poor results as we can see in Table 3 (lines 1-2). The adaptation of the tree pattern kernel to stereoisomerism [START_REF] Brown | Compound analysis via graph kernels incorporating chirality[END_REF] and our previous kernels [START_REF] Grenier | A graph kernel incorporating molecule's stereisomerism information[END_REF][START_REF] Grenier | Incorporating molecules stereisomerism within the machine learning framework[END_REF] (lines 3-5) improves the results over the two previous methods hence showing the insight of adding stereoisomerism information. Taking into account relationships between minimal stereo subgraphs (lines 6-9) allows us to obtain better results than our previous method [START_REF] Grenier | Incorporating molecules stereisomerism within the machine learning framework[END_REF].

Conclusion

The study and the definition of new stereoisomers constitutes an important subfield of chemistry and thus a major challenge in chemoinformatics. Indeed, stereoisomers of some common drugs may be considered as violent poisons. For example, a molecule called thalidomide was sold in the late fifties as an anti nausea for pregnant women. However, it turns out that one of the stereoisomer of this molecule could cause fetal malformation. Up to now, only few methods have proposed pattern recognition methods taking explicitly into account stereoisomerism.

We have presented previously a graph kernel based on an explicit enumeration of all the stereo subgraphs of a molecule. Each stereo subgraph is associated to a stereo vertex and encodes the part of the graph which provides the stereo property to this vertex. In this report we have proposed an extension of this previous methods which consists in construct a new graph, where each nodes represent a stereo subgraph and each edge encode the interaction between stereo subgraphs. This graph allows us to take into account relationships between stereo subgraphs. The relevance of this approach is demonstrated by our experiments on two datasets.

  (a) Two different spatial configurations of the neighbors of a carbon (b) Two different spatial configurations of two carbons linked by a double bond.

Fig. 1 :

 1 Fig. 1: Two types of stereocenters.

Fig. 2 :

 2 Fig.2: Example of elements of V P AC and of V DB with their ordered list (top) and the ordered lists obtained using two permutations σ and σ

Fig. 4 :

 4 Fig. 4: One ordered graph and its different graph of interactions, obtained by taking different function of interactions.

  shows one exemple of minimal stereo subraph.

	Fig. 3: An asymmetric carbon and its associated sequence (H k C ) k∈N . Its minimal stereo subgraph is S C = H 3 C .
	Proof. As (H k s ) k∈N is a sequence of vertex induced subgraphs of G, we know that ∀k ∈ N H k s G. The sequence is thus upper bounded.
	Proposition 3. The sequence (H k s ) k∈N converges.

By Definition 16, we have ∀k

Table 1 :

 1 Averages values of numbers of vertices (|V |), edges (|E|), different labels(|L V |,|L E |), and mean degree (d) of graph of interactions.

	|V | |E| |LV | |LE| d	|V | |E| |LV | |LE| d
	Graph 1 5 7 4.5 3 2.8	Graph 1 8.55 17.4 8.38 5.71 4.07
	Graph 2 5 7 4.5 3 2.8	Graph 2 8.55 17.4 8.38 3.71 4.07
	Graph 3 5 2 4.5 2 0.8	Graph 3 8.55 11.3 8.38 4.71 2.62
	Graph 4 5 1 4.5 1 0.4	Graph 4 8.55 6.14 8.38 2.71 1.43
	(a) ACE dataset	(b) Vitamin dataset

Table 2 :

 2 Classification of the ACE inhibitory activity of perindopirilates stereoisomers

	Method	Accuracy
	Brown [1]	96.875
	Stereo Kernel [11]	87.5
	Stereo + Extended subgraphs [10] 96.875
	Graph of interaction 1	93.75
	Graph of interaction 2	93.75
	Graph of interaction 3	93.75
	Graph of interaction 4	84.375
	Graph of interaction 1 with MKL	100
	Graph of interaction 2 with MKL	100
	Graph of interaction 3 with MKL	87.5
	Graph of interaction 4 with MKL 90.625

Pierre-Anthony Grenier † , Luc Brun † , and Didier Villemin ‡

Acknowledgements

This work was in part made using the computing resources funded under the CPER.


Marco Congedo

Alexandre Barachant

A Special Form of SPD Covariance Matrix for Interpretation and Visualization of Data Manipulated with Riemannian Geometry

Keywords:

DEFINITION OF DATA MATRICES

In many engineering applications we observe a number of realizations in the form of generic data matrices

X i ∈ ℜ R×C , ( 1
)
where i is the index of the realization, R is the number of rows, indexed by r ∈ {1, . . . R} and C is the number of columns, indexed by c ∈ {1, . . .C}. For example, X i may be a black and white image of R × C pixels. Besides images, in this work we employ the example of data describing the realizations of R random variables of which C samples are recorded, yielding again an R ×C data matrix

X i =   x 1i . . . x Ri   ∈ ℜ R×C (2)
where x ri ∈ ℜ C is the r th row of the data matrix, that is, the i th realization of the r th random variable. We treat throughout the paper the real case, however the case of complex data is analogous. In general with real-life data we have R = C. In our first example (images) both the row and columns refer to a spatial dimension. Our second example concerns brain electrical event-related potentials. In this case we adopt the convention that the rows of X i hold the potential recorded at electrodes placed on the scalp (spatial dimension) and the columns hold temporal samples (temporal dimension). As we will see, the form of covariance matrix we propose embeds both spatial covariance structures in the first example and both the spatial and temporal covariance structure in the second example. More in general, for any data matrix X i the special form of covariance matrix we propose embeds both the row and column covariance structure, whatever they represent.

STANDARD COVARIANCE MATRICES

Let 1 (N) the N-dimensional vector filled with one everywhere and I (N) the N × N identity matrix. Given realization X i there exist two possible sample covariance matrices, namely, the "row-covariance"

C (R) = 1 C X i H (C) H (C) X T i ∈ ℜ R×R , (3)
and the "column-covariance"

C (C) = 1 R X T i H (R) H (R) X i ∈ ℜ C×C , (4)
where

H (N) = I (N) - 1 N 1 (N) 1 T (N) (5)
is named the centering matrix ( [START_REF] Searle | Matrix Algebra Useful for Statistics[END_REF], p. 66-68 and p. 349-352). The centering matrix H (N) has N -1 equal eigenvalues and one null eigenvalue corresponding to eigenvector 1 (N) . It has also the following properties:

H = H T = H 2 ; H1 = H11 T = 11 T H = 0 (6)
As the name suggests, the centering matrix centers the signal around zero, that is, the centered signal has zero mean, i.e., it holds

1 C H (R) X i 1 (C) = 0 and 1 R H (C) X i 1 (R) = 0 (7)
One may also double-center the data [START_REF] Pascual-Marqui | A measure of association between vectors based on "similarity covariance[END_REF] such as

X i ← H (R) X i H (C) , (8)
after which the two conditions X i 1 (C) = 0 and X T i 1 (R) = 0 hold simultaneously. Notice that for the sequel data centering is not a necessary step and we may process as well the raw X i as they are recorded. The important point here is that if we shuffle the columns of X i the row-covariance matrix (3) does not change. In the same way, if we shuffle the rows of X i the column-covariance matrix (4) does not change; thus, neither covariance matrix taken alone may define exhaustively and uniquely the data matrix X i . However, if we consider them simultaneously we can do so up to second order statistics. For instance, the definition is exhaustive if the data follows a multivariate Gaussian distribution.

THE SPECIAL FORM OF COVARIANCE MATRIX

Given realization X i ∈ ℜ R×C consider first the following data expansion:

Y i = X i αI (R) αI (C) X T i ∈ ℜ T ×T , (9)
where T = R+C. Now, consider its associated Gram matrix (covariance structure) scaled by 1/2α such as

C i = 1 2α Y i Y T i = 1 2α X i X T i + α 2 I (R) X i X T i 1 2α X T i X i + α 2 I (C) ∈ ℜ T ×T , α > 0 (10)
This matrix holds on the diagonal blocks a regularized and differently scaled version of the covariance structures (3) and ( 4) and on the off-diagonal block the original data matrix itself and its transpose (in the original scaling thanks to the division of the whole matrix by 2α). Since it holds both covariance structures, this matrix defines exhaustively X i up to second-order statistics; now any shuffling of columns or rows would result in a different X i , therefore we have created a bijection between C i and X i such that to any X i it corresponds one and only one C i . Matrix C i is symmetric by construction, but not necessarily positive definite. However, there exists a real κ > 0 such that C i is positive definite for any α ≥ κ. The larger is α, the stronger the regularization enforced on the covariance structures, thus in general we may want to choose α as small as possible provided that the resulting matrices C i are positive definite. The selected value of α depends on the dynamic range of the original data. Once we have obtained symmetric positive-definite (SDP) matrices C i we can manipulate them according to our purpose in the Riemannian manifold of SPD matrices. Now we are able to appreciate the effect of these manipulations also in the original space of the data. That is to say, any manipulation of C i on the Riemannian manifold will enforce a unique corresponding manipulation on its block X i , allowing the interpretation of our manipulations in the original space of the data matrix X i .

ILLUSTRATIONS

We illustrate the effect of working with the special form of SPD matrix (10) with two examples.

Example 1

The first example illustrates the manipulation of color and black and white (B&W) images. A B&W image can be represented by a matrix X i ∈ ℜ R×C of R ×C pixels that can take integer value 0 (black) to ρ (white), where ρ depends on the resolution of the image (255 in our example). A color image can be represented by a triplet of images of the same kind holding each the value of red (R), green (G) and blue (B), which combination defines the color image. In order not to distort the images we do not center them and we use (10) with α = ρ , which ensures positive-definitiveness of matrices(10). As an example of manipulation in the Riemannian manifold of SPD matrices we show how images move along geodesics in this manifold. Given SPD matrices C 1 and C 2 in the Riemannian manifold of SPD matrices we move on the geodesic connecting them by [START_REF] Bhatia | Riemannian geometry and matrix geometric mean[END_REF].

C (C 1 →C 2 ,β ) = C 1/2 1 C -1/2 1 C 2 C -1/2 1 β C 1/2 1 , β ∈ [0 : 1] (11)
For instance, with β = 0 we are at point C 1 . With β = 1 we are at C 2 . With β = 0.5 we reach the geometric mean of C 1 and C 2 . Suppose we have a color image at low (spatial) resolution and the same image in black and white at high resolution. Suppose our goal is to generate a color image with high resolution (HR) starting only from the color image at low resolution (LR) and the B&W image at HR. This problem is known in the literature as pansharpening and arises in satellite imaging. Satellites have several cameras, of which one camera integrates over a wide light wavelength spectrum, achieving HR but no color information, and several cameras integrate over a narrow-band light wavelength spectrum, returning color information at LR. We use a very simple idea: we decompose the LR color image in its red (R), green (G) and blue (B) component and compute the special form of covariance (10) for the three LR R,G,B images as well as for the B&W HR image. Then we move along the geodesic the three R,G,B matrices all toward the direction of the B&W matrix, as per (11) with a step size close enough to 1 (0.95 in this example). Finally, we assign to each pixel the saturation of the LR color image. Figure 1 shows the result of these manipulations. Figure 2 shows the special form of the covariance matrix (10) for the HR B&W image (top-left), the red component of the LR image (top-right), the green component of the LR image (bottom-left) and the blue component of the LR image. In these images the diagonal blocks are the row and column covariance structures, while the off-diagonal blocks are the image itself and its transpose, as per construction of (10). Note that since the original picture is mainly red, the red LR special form of covariance matrix has more detailed covariance structures as compared to the green and blue components, but still much less detailed covariance structure as compared to the HR B&W image. We see that moving the special form of covariance matrix of the R,G,B components along the geodesic toward the HR B&W image amounts to progressively matching the covariance structures of the three R,G,B components with the covariance structures of the B&W image, i.e., in this case, it amounts to increasing the spatial resolution loosing progressively color information; by construction of (10) such matching is reflected in the image itself (top-right off-diagonal block).

Example 2

The second example estimates for the first time the "geometric mean" of event-related potentials (ERP). ERP data were gathered using the Brain Invaders brain-computer interface [START_REF] Congedo | Brain Invaders": a prototype of an open-source P300-based video game working with the OpenViBE platform[END_REF]. X i in this case holds the brain electrical signal recorded for a short time period (one second in this example) starting at time "zero" corresponding to an external stimulation sent to the brain (a visual stimulation in this case) and it is named a "trial". Each row x ri ∈ ℜ C of X i as per (2) is the electric potential difference recorded at the r th electrode with respect to a cephalic reference. These potential changes are stereotypical in a given experimental condition and are time-and phase-locked to the stimulus, i.e., they have similar form and amplitude in different trials. However, an inter-trial variability is present. Moreover, potential changes are very small in amplitude (a few µV ) as compared to the spontaneous electroencephalography in the background (tens of µV ), hence the signal-to-noise variance ratio (SNR) for a single trial is -20dB or smaller, that is to say, the ERP is invisible on raw data. To increase the SNR the ERPs are usually averaged (sample-by-sample arithmetic mean) in order to enhance the stereotypical response, while spontaneous activity and artifacts, being not time-and -phase locked to the stimulus and oscillating around zero, cancel out across trials in the summation. In this example the spatial structure of a trial depends on what areas of the brain contribute to the signal and on the electrode placement on the scalp, whereas the temporal structure depends on the timing of their activity. The data has been presented in [START_REF] Congedo | Riemann Geometry: an Universal BCI Classification Framework (Ch. VIII)[END_REF], to which the reader is referred for details on data acquisition and experimental procedures. We present data obtained on one subject for which 58 ERPs were recorded. 16 electrodes (R = 16) were used. As only preprocessing, data was band-pass filtered in the frequency region 1-20Hz and down-sampled at 128 samples per second (C = 128). Each trial holds one second of data post-stimulus, therefore our data matrices X i have dimension 16 × 128.

In order to compute the "geometric mean" of ERPs we use (10) with double-centering (8) as PSD characterization of the trials. Before double-centering the data and applying (10) (with α = 1), in this example we reduce the dimension of the data by "reducing" each trial X i such as

X i ← U T X i V, (12)
where U ∈ ℜ R×P and V ∈ ℜ C×Q are taken, respectively, as the first P = Q = 8 left and right singular vectors of the arithmetic mean of target trials X i . That is, if U T WV is the singular value decomposition of the average ERP, the columns of U and V span an orthogonal basis of the signal subspace for the spatial (U) and temporal (V) covariance of the average ERP. Once data dimension have been reduced by (12) matrices C i (10) have dimension 16 × 16 only. As algorithm for computing the geometric mean of trials (10) we use the well-known gradient descent algorithm that can be found, for instance, in [START_REF] Congedo | Riemann Geometry: an Universal BCI Classification Framework (Ch. VIII)[END_REF]. The geometric mean is known to be more robust to outliers as compared to the arithmetic mean. In order to verify this feature on ERPs, on one trial only (out of 58 available) we added -500 µV (an aberrant voltage value) to samples 5 to 15 of the first electrode. This simulates a strong square-wave transient artifact. See caption of Fig. 3 for the results. Note that the filtered arithmetic mean is very similar to the arithmetic mean obtained on the raw data. This merely states that the generation of the ERP involves no more than eight active dipoles (row, spatial components) acting on no more than eight temporal windows (column, temporal components). This is well-known in the ERP literature. Processing the data without the simulated outlier the arithmetic mean (AM) and the geometric mean (GM) are similar, but not identical; in both cases we can observe three major peaks of the global field power (see pointing arrows in Fig. 3): a positive deflection at 280 ms, a negative deflection at 450 ms and a positive deflection at 650 ms. For the GM a forth positive deflection at 580 ms is better visible. Also, the first two GFP peaks are sharper and better separated for the GM mean.

CONCLUSIONS

We have presented a special form of covariance matrix that can be computed starting from any generic data matrix. Such special covariance matrix de facto allows the manipulation of generic data matrices using the tools of Riemannian geometry in the SPD manifold. Furthermore, this special form of covariance matrix is unique for each data matrix (for a given α), thus may be used, for instance, to classify directly any kind of data matrix using Riemannian methods as shown for example in [START_REF] Barachant | Multi-Class Brain Computer Interface Classification by Riemannian Geometry[END_REF] and in [START_REF] Congedo | Riemann Geometry: an Universal BCI Classification Framework (Ch. VIII)[END_REF]. In summary, the presented special form of covariance matrix has two interesting properties:

1. it allows the visualization of manipulations on the Riemannian manifold of SPD matrices in the original space of the data that have generated the SDP matrices. 2. It allows an exhaustive and unique characterization of a data matrix by describing both the covariance structure of its rows and of its columns.

The only practical limitation of the method is that each data matrix X i analyzed must be of the same size. Our first example (satellite images) has illustrated how any data matrix can be moved along geodesics toward any other data matrix. This may be very useful in some applications, however the method used in the example is not meant to represent a competitive option for pansharpening. In the second example we have estimated the "geometric mean" of 58 ERPs. This is the first time the concept of geometric mean on the SPD manifold is translated to ERP data. The example demonstrates that the geometric mean may be robust to outliers, thence such estimation deserves further investigation in the field of neuroscience. The choice of parameter α is not trivial. It should be high enough so that the C i matrices are positive and well enough conditioned. On the other hand, increasing α amounts to move the points C i on the manifold all toward the point αI. Such region of the SPD manifold (the hyper plane of SPD diagonal matrices) is the least curved therein -in fact, this hyper plane is log-Euclidean, see [START_REF] Congedo | Riemann Geometry: an Universal BCI Classification Framework (Ch. VIII)[END_REF] -. Thus, increasing α will not only progressively reduce the radius of the ball containing the points C i , but also as α increases we expect to observe less and less difference in between the geometric and arithmetic mean of the data matrix blocks X i embedded in these points. This suggests that several "mean ERP" may be estimated varying α within a suitable range leaving to the investigator the choice of the most suitable mean. Further research will elucidate the implications on the choice of α we have touched on.

FIGURE 1 .

 1 FIGURE 1. Simulation of satellite images of a car parking. From left to right and top to bottom: a) a color low-resolution image, b) its B&W high resolution version, c) its color high-resolution version (here used as a benchmark, but it cannot be generated by the satellite) and d) the color image we have reconstructed using a) and b) only.

FIGURE 2 .

 2 FIGURE 2. Color-coded (white=0, black=max) images of the special form of covariance matrix (10) computed from the high resolution B&W image (top-left), the red component of the low resolution color image (top-right), the green component of the low resolution color image (bottom-left) and the blue component of the low resolution color image (bottom-right).

FIGURE 3 . 1 -

 31 FIGURE 3. 1-sec average ERP estimations for one subject recorded at 16 electrodes. For consistency with neurological convention, a positive voltage deflection is plotted downward. The voltage scale of each plot is arbitrary but consistent within each plot. The shaded grey area is the global field power (GFP), that is, the total energy (sum of the squared potential across electrodes) at each sample. The GFP is scaled arbitrarily in each plot. The first three plots are, from left to right, the arithmetic mean of the raw ERPs X i , the arithmetic mean of the ERPs after filtering of the trials as per (12) (given by X i ← U T X i V) and the geometric mean of the trials obtained as the top-right off-diagonal block of the geometric mean of trials represented by (10), ri-expanded in the original dimension by X i ← UX i V T . The next three plots are the same three mean estimations obtained with the outlier, which is well visible at the beginning of the trace of the first electrode only in the arithmetic means.

ACKNOWLEDGMENTS

This work has been partly supported by the European Project ERC-2012-AdG-320684-CHESS