Ron A Doney
email: ron.doney@manchester.ac.uk

Stavros Vakeroudis
email: stavros.vakeroudis@ulb.ac.be

Windings of planar stable processes

Keywords: AMS 2010 subject classification: Primary: 60G52, 60G51, 60F05, 60J65; secondary: 60E07, 60B12, 60G18 Stable processes, Lévy processes, Brownian motion, windings, exit time from a cone, Spitzer's Theorem, skew-product representation, Lamperti's relation, Law

whether they are published or not. The documents may come

Windings of planar stable processes

Introduction

In this paper, we study the windings of planar isotropic stable processes. More precisely, having as a starting point a work of Bertoin and Werner [START_REF] Bertoin | Stable windings[END_REF] concerning this subject (following their previous work on windings of planar Brownian motion § [START_REF] Bertoin | Asymptotic windings of planar Brownian motion revisited via the Ornstein-Uhlenbeck process[END_REF]) and motivated by some works of Shi [START_REF] Shi | Windings of Brownian motion and random walks in the plane[END_REF], we attempt to generalize some results obtained recently for the case of planar Brownian motion (see e.g. [START_REF] Vakeroudis | On hitting times of the winding processes of planar Brownian motion and of Ornstein-Uhlenbeck processes, via Bougerol's identity[END_REF][START_REF] Vakeroudis | Nombres de tours de certains processus stochastiques plans et applications à la rotation d'un polymère[END_REF][START_REF] Vakeroudis | Integrability properties and Limit Theorems for the exit time from a cone of planar Brownian motion[END_REF] and the references therein). In particular, we are interested in the behaviour of stable processes for small time, an aspect which has already been investigated e.g. by Doney [START_REF] Doney | Small time behaviour of Lévy processes[END_REF] in terms of Spitzer's condition for stable processes (see e.g. [START_REF] Bertoin | Spitzer's condition for random walks and Lévy Processes[END_REF] and the references therein).

In Section 2, we recall some facts about standard isotropic stable processes of index α ∈ (0, 2) taking values in the complex plane. Then, we follow Bertoin and Werner [START_REF] Bertoin | Stable windings[END_REF] to define the process of its winding number, we generalize the skew-product representation of planar BM (see e.g. [START_REF] Kiu | Semi-stable Markov processes in R n[END_REF][START_REF] Revuz | Continuous Martingales and Brownian Motion[END_REF][START_REF] Chybiryakov | The Lamperti correspondence extended to Lévy processes and semi-stable Markov processes in locally compact groups[END_REF]) and we present two Lemmas for the winding process of isotropic stable Lévy processes obtained in [START_REF] Bertoin | Stable windings[END_REF]. Finally, we mention some properties of the positive and the negative moments of the exit times from a cone of this process.

In Section 3, we use some continuity arguments of the composition function due to Whitt [START_REF] Whitt | Some useful functions for functional limit Theorems[END_REF] and we obtain a new simple proof of the analogue of Spitzer's Theorem for isotropic stable Lévy processes, initially proven by Bertoin and Werner [START_REF] Bertoin | Stable windings[END_REF]. We reformulate and we extend this result in terms of the exit times from a cone. More precisely, Spitzer's asymptotic Theorem says that, if (ϑ t , t ≥ 0) denotes the continuous determination of the argument of a planar BM starting away from the origin, then:

2 log t ϑ t (law) -→ t→∞ C 1 , (1)
where C 1 is a standard Cauchy variable. For other proofs of (1) , see e.g. [Wil74, Dur82,

. Bertoin and Werner state that because an isotropic stable Lévy processes is transient, we expect that it winds more slowly than planar Brownian motion and prove that, with θ now denoting the process of its winding number (appropriately defined, see e.g. Section 2), θ t / √ log t converges in distribution to some centered Gaussian law as t → ∞ (Theorem 1 in Bertoin and Werner [START_REF] Bertoin | Stable windings[END_REF], stated here as Theorem 3.2).

In Section 4, and more precisely in Theorems 4.1 and 4.4, we study the asymptotics of a symmetric Lévy process and of the winding process of isotropic stable Lévy processes for t → 0, respectively, which are the main results of this article. In particular, we show that t -1/α θ t converges in distribution to an α-stable law as t → 0. Using this result, in Proposition 4.5 we obtain the (weak) limit in distribution of the process of the exit times from a cone with narrow amplitude and we further obtain several generalizations. We also study the windings of planar stable processes in ( t, 1 ], for t → 0 and we note that, with obvious notation, Spitzer's law is still valid for θ ( t,1 ] (see Remark 4.7). Section 5 deals with the Law of the Iterated Logarithm LIL for Lévy processes for small times, in the spirit of some well-known (LIL) for Brownian motion for t → ∞ from Bertoin and Werner [START_REF] Bertoin | Asymptotic windings of planar Brownian motion revisited via the Ornstein-Uhlenbeck process[END_REF][START_REF] Bertoin | Compertement asymptotique du nombre de tours effectués par la trajectoire brownienne plane[END_REF] and from Shi [START_REF] Shi | Liminf behaviours of the windings and Lévy's stochastic areas of planar Brownian motion[END_REF][START_REF] Shi | Windings of Brownian motion and random walks in the plane[END_REF], and for stable subordinators with index α ∈ (0, 1) for t → 0 from Fristedt [START_REF] Fristedt | The behavior of increasing stable processes for both small and large times[END_REF][START_REF] Fristedt | Sample function behavior of increasing processes with stationary, independent increments[END_REF] and Khintchine [START_REF] Khintchine | Sur la croissance locale des processus stochastiques homogènes à accroissements indépendants[END_REF] (see also [START_REF] Bertoin | Lévy Processes[END_REF]). Moreover, we prove a LIL for the winding number process of stable processes, for t → 0.

Finally, in Section 6 we discuss the planar Brownian motion case and in Theorem 6.1 we obtain the asymptotic behaviour of the winding process as t → 0. More precisely, the process c -1/2 ϑ ct , t ≥ 0 converges in law to a 1-dimensional Brownian motion as c → 0.

Notation: In the following text, with the symbol "=⇒" we shall denote the weak convergence in distribution on the appropriate space, endowed with the Skorohod topology.

Preliminaries

Following Lamperti [START_REF] Lamperti | Semi-stable Markov processes I[END_REF], a Markov process X with values in R d , d ≥ 2 is called isotropic or O(d)-invariant (O(d) stands for the group of orthogonal transformations on R d ) if its transition satisfies:

P t (φ(x), φ(B)) = P t (x, B), (2)
for any φ ∈ O(d), x ∈ R d and Borel subset B ⊂ R d .
Moreover, X is said to be α-self-similar if, for α > 0,

P λt (x, B) = P t (λ -α x, λ -α B), (3)
for any λ > 0, x ∈ R d and B ⊂ R d .

We focus now our study on the 2-dimensional case (d = 2), where (3) holds, and we denote by (Z t , t ≥ 0) a standard isotropic stable process of index α ∈ (0, 2) taking values in the complex plane and starting from z 0 + i0, z 0 > 0. A scaling argument shows that we may assume z 0 = 1, without loss of generality, since, with obvious notation:

Z (z 0 ) t , t ≥ 0 (law) = z 0 Z (1) (t/z α 0 ) , t ≥ 0 . (4)
Thus, from now on, we shall take z 0 = 1. More precisely, Z has stationary independent increments, its sample path is right continuous and has left limits (cadlag) and, with •, • standing for the Euclidean inner product,

E [exp (i λ, Z t )] = exp (-t|λ| α ), for all t ≥ 0 and λ ∈ C. Z is transient, lim t→∞ |Z t | = ∞ a.
s. and it a.s. never visits single points. We remark that for α = 2, we are in the Brownian motion case.

We are now going to recall some properties of stable processes and Lévy processes (for more details see e.g. [START_REF] Bertoin | Lévy Processes[END_REF] or [START_REF] Kyprianou | Introductory Lectures on Fluctuations of Lévy Processes with Applications[END_REF]). To start with, if Z = (Z t , t ≥ 0) denotes a planar Brownian motion starting from 1 and S = (S(t), t ≥ 0) an independent stable subordinator with index α/2 starting from 0, i.e.:

E [exp (-µS(t))] = exp -tµ α/2 , (5)
for all t ≥ 0 and µ ≥ 0, then the subordinated planar BM (Z 2S(t) , t ≥ 0) is a standard isotropic stable process of index α. The Lévy measure of S is:

α 2Γ(1 -α/2) s -1-α/2 1 {s>0} ds
thus, the Lévy measure ν of Z is:

ν(dx) = α 2Γ(1 -α/2) ∞ 0 s -1-α/2 P (Z 2s -1 ∈ dx) ds = α 8πΓ(1 -α/2) ∞ 0 s -2-α/2 exp -|x| 2 /(4s) ds dx = α 2 -1+α/2 Γ(1 + α/2) πΓ(1 -α/2) |x| -2-α dx . (6)
Contrary to planar Brownian motion, as Z is discontinuous, we cannot define its winding number (recall that, as is well known [START_REF] Itô | Diffusion Processes and their Sample Paths[END_REF], for planar BM, since it starts away from the origin, it does not visit a.s. the point 0 but keeps winding around it infinitely often. In particular, the winding process is well defined, for further details see also e.g. [START_REF] Pitman | Asymptotic Laws of planar Brownian Motion[END_REF]). However, following [START_REF] Bertoin | Stable windings[END_REF], we can consider a path on a finite time interval [0, t] and "fill in" the gaps with line segments in order to obtain the curve of a continuous function f : [0, 1] → C with f (0) = 1. Now, since 0 is polar and Z has no jumps across 0 a.s., we have f (u) = 0 for every u ∈ [0, 1]. Hence, we can define the process of the winding number of Z around 0, which we denote by θ = (θ t , t ≥ 0). It has cadlag paths of absolute length greater than π and, for all t ≥ 0,

exp(iθ t ) = Z t |Z t | . ( 7
)
We also introduce the clock:

H(t) ≡ t 0 ds |Z s | α , (8)
and its inverse:

A(u) ≡ inf{t ≥ 0, H(t) > u} . (9)
Bertoin and Werner following [START_REF] Graversen | α-self-similar Markov Processes[END_REF] obtained these two Lemmas for α ∈ (0, 2) (for the proofs see [START_REF] Bertoin | Asymptotic windings of planar Brownian motion revisited via the Ornstein-Uhlenbeck process[END_REF]):

Lemma 2.1. The time-changed process (θ A(u) , u ≥ 0) is a real-valued symmetric Lévy process. It has no Gaussian component and its Lévy measure has support in [-π, π].

We now denote by dz the Lebesgue measure on C. Then, for every complex number z = 0, φ(z) denotes the determination of its argument valued in (π, π ].

Lemma 2.2. The Lévy measure of θ A(•) is the image of the Lévy measure ν of Z by the mapping z → φ(1 + z). As a consequence, E[(θ A(u) ) 2 ] = uk(α), where

k(α) = α 2 -1+α/2 Γ(1 + α/2) πΓ(1 -α/2) C |z| -2-α |φ(1 + z)| 2 dz . (10)
Using Lemma 2.1, we can obtain the analogue of the skew product representation for planar BM which is the Lamperti correspondence for stable processes. Indeed, following [START_REF] Graversen | α-self-similar Markov Processes[END_REF] and using Lamperti's relation (see e.g. [START_REF] Lamperti | Semi-stable Markov processes I[END_REF][START_REF] Kiu | Semi-stable Markov processes in R n[END_REF][START_REF] Chybiryakov | The Lamperti correspondence extended to Lévy processes and semi-stable Markov processes in locally compact groups[END_REF][START_REF] Caballero | Explicit identities for Lévy processes associated to symmetric stable processes[END_REF] or [START_REF] Revuz | Continuous Martingales and Brownian Motion[END_REF]) and Lemma 2.1, there exist two real-valued Lévy processes (ξ u , u ≥ 0) and (ρ u , u ≥ 0), the first one non-symmetric whereas the second one symmetric, both starting from 0, such that:

log |Z t | + iθ t = (ξ u + iρ u ) u=Ht= t 0 ds |Zs| α . ( 11
)
We remark here that |Z| and

Z A(•) /|Z A(•) | are NOT independent. Indeed, the processes |Z A(•) | and Z A(•) /|Z A(•)
| jump at the same times hence they cannot be independent. Moreover, A(•) depends only upon |Z|, hence |Z| and Z A(•) /|Z A(•) | are not independent. For further discussion on the independence, see e.g. [START_REF] Liao | Isotropic self-similar Markov processes[END_REF], where is shown that an isotropic α-self-similar Markov process has a skew-product structure if and only if its radial and its angular part do not jump at the same time.

We also remark that

H -1 (u) ≡ A(u) ≡ inf{t ≥ 0 : H(t) > u} = u 0 exp{αξ s } ds . (12)
Hence, (11) may be equivalently written as:

|Z t | = exp (ξ(H t )) ⇔ Z A(t) = exp (ξ t ) , (extension of Lamperti's identity) θ t = ρ(H t ) ⇔ θ (A(t)) = ρ(t) . (13)
We also define the random times

T |θ| c ≡ inf{t : |θ t | ≥ c} and T |ρ| c ≡ inf{t : |ρ t | ≥ c}, (c > 0).
Using the "generalized" skew-product representation (11) (or ( 13)), we obtain:

T |θ| c = H -1 u u=T |ρ| c = T |γ| c 0 ds exp(αξ s ) ≡ A T |ρ| c . (14)
Following [START_REF] Vakeroudis | Integrability properties and Limit Theorems for the exit time from a cone of planar Brownian motion[END_REF], for the random times

T θ -d,c ≡ inf{t : θ t / ∈ (-d, c)}, d, c > 0, and T θ c ≡ inf{t : θ t ≥ c}, we have: Remark 2.3. For 0 < c < d, the random times T θ -d,c , T |θ| c
and T θ c satisfy the trivial inequality:

T |θ| c ≤ T θ -d,c ≤ T θ c . (15)
Hence, with p > 0:

E T |θ| c p ≤ E T θ -d,c p ≤ E T θ c p , (16)
and for the negative moments:

E T θ c -p ≤ E T θ -d,c -p ≤ E T |θ| c -p . ( 17
)
Remark 2.4. For further details concerning the finiteness of the positive moments of T |θ| c , see e.g. [START_REF] De Blassie | The first exit time of a two-dimensional symmetric stable process from a wedge[END_REF][START_REF] Banũelos | Symmetric stable processes in cones[END_REF]. Recall also that for the positive moments of the exit time from a cone of planar Brownian motion, Spitzer showed that (with obvious notation) [START_REF] Spitzer | Some Theorems concerning two-dimensional Brownian Motion[END_REF][START_REF] Burkholder | Exit times of Brownian Motion, Harmonic Majorization and Hardy Spaces[END_REF]:

E T |ϑ| c p < ∞ ⇔ p < π 4c , (18)
whereas all the negative moments E T

|ϑ| c -p
are finite [START_REF] Vakeroudis | Integrability properties and Limit Theorems for the exit time from a cone of planar Brownian motion[END_REF].

We denote now by Ψ(u) the exponent of the symmetric Lévy process ρ, hence (Lévy-Khintchine formula) E[e iuρt ] = e -tΨ(u) , with:

Ψ(u) = (-∞,∞) 1 -e iux + iux1 {|x|≤1} µ(dx), u ∈ R, ( 19
)
where µ is a Radon measure on R \ {0} such that:

(-∞,∞) (x 2 ∧ 1)µ(dx) < ∞ .
µ is the Lévy measure of ρ and is symmetric.

Large time asymptotics

Concerning the clock H, we have the almost sure convergence (see Corollary 1 in Bertoin and Werner [START_REF] Bertoin | Stable windings[END_REF]):

H(e u ) u a.s. -→ u→∞ 2 -α Γ(1 -α/2) Γ(1 + α/2) ≡ K(α) = E |Z 1 | -α . (20)
Moreover, we have the following:

Proposition 3.1. The family of processes

H (u) x ≡ H(e ux ) u , x ≥ 0 is tight, as u → ∞.

Proof of Proposition 3.1:

To prove this, we could repeat some arguments of Pitman and Yor [START_REF] Pitman | Further Asymptotic Laws of planar Brownian Motion[END_REF] (see the estimates in their proof of Theorem 6.4), however, we give here a straightforward proof, using the definition of tightness: for every ε, η > 0, there exist δ > 0 and C δ > 0 such that, for every 0 < x < y:

P sup |x-y|≤δ |H(e uy ) -H(e ux )| ≥ uε ≤ η , for u ≥ C δ , (21)
or equivalently:

P 1 u H(e u(x+δ) ) -H(e ux ) ≥ ε ≤ η , for u ≥ C δ . (22)
First, following Bertoin and Werner [START_REF] Bertoin | Stable windings[END_REF], we introduce the "Ornstein-Uhlenbeck type" process:

Zu = exp(-u/α)Z exp(u) , u ≥ 0 , (23)
which is a stationary Markov process under P 0 (see e.g. [START_REF] Breiman | A delicate law of the iterated logarithm for non-decreasing stable processes[END_REF]). We denote by p t (•) the semigroup of Z:

p t (z) = P 0 (Z t ∈ dz)/dz, z ∈ C.
We denote by Z (0) another stable process starting at 0. Then, using the scaling property, given that

Z0 ≡ Z 1 ≡ 1 + Z (0) 1 = x, the semigroup q u (•) of Z is given by: q u (x, ȳ) = p exp(u)-1 e u/α ȳ -x e 2u/α = (e u -1) -2/α e 2u/α p 1 (e u -1) -1/α (e u/α ȳ -x) = (l(u)) 2 p 1 l(u)(ȳ -e -u/α x) , (24)
where l(v) = e v/α (e v -1) -1/α . For every δ > 0 and changing variables s = exp(v), with obvious notation, we have:

E H(e u(x+δ) ) -H(e ux ) = e u(x+δ) e ux E |Z s | -α ds = u(x+δ) ux E Z0 | Zv | -α dv . ( 25
)
We also define ε(v) ≡ l(v)e -v/α = (e v -1) -1/α . From (23), using the stability of Z, we have:

Zv = e -v/α Z exp(v) = e -v/α Z exp(v)-1 + Z 1 (law) = e -v/α (e v -1) 1/α Z (0) 1 + Z 1 = (l(v)) -1 Z (0) 1 + ε(v)Z 1 . (26)
Hence (for simplicity, we use E ≡ E 0 ):

E Z0 | Zv | -α = (l(v)) α E |Z (0) 1 + ε(v) Z0 | -α ≡ (l(v)) α (E 1 + E 2 ) , (27)
where, with δ ′ > 0,

E 1 = E |Z (0) 1 + ε(v) Z0 | -α : |Z (0) 1 + ε(v) Z0 | ≥ δ ′ , E 2 = E |Z (0) 1 + ε(v) Z0 | -α : |Z (0) 1 + ε(v) Z0 | ≤ δ ′ .
We have: l(v) v→∞ -→ 1 and ε(v) v→∞ -→ 0, thus, by Dominated Convergence Theorem:

E 1 v→∞ -→ E |Z (0) 1 | -α : |Z (0) 1 | ≥ δ ′ δ ′ →0 -→ E |Z (0) 1 | -α . ( 28
)
Moreover, changing the variables: w = z + ε(v)x, we have:

E 2 = x,z:|z+ε(v)x|≤δ ′ P ( Z0 ∈ dx) P (Z (0) 1 ∈ dz) |z + ε(v)x| -α = x, w:| w|≤δ ′ P ( Z0 ∈ dx) P (Z (0) 1 ∈ d w) | w| -α .
Remarking now that for stable processes: P (Z (0) 1

∈ dȳ) ≤ C ′ dȳ, where C ′ stands for a positive constant and using w = (w 1 , w 2 ), we have:

E 2 ≤ C ′ x, w:| w|≤δ ′ P ( Z0 ∈ dx) dw 1 dw 2 | w| α = C ′ z:| w|≤δ ′ dw 1 dw 2 | w| α δ ′ →0 -→ 0 . (29)
Thus, from ( 27), ( 28) and (29), invoking again the Dominated Convergence Theorem, we deduce:

lim u→∞ E Z0 | Zv | -α = E |Z (0) 1 | -α , (30)
which is a constant. Hence, for every ε, η > 0, there exist δ > 0 and

C δ > 0 such that (22) is satisfied for u ≥ C δ .
Bertoin and Werner in [START_REF] Bertoin | Stable windings[END_REF] obtained the analogue of Spitzer's asymptotic Theorem [START_REF] Spitzer | Some Theorems concerning two-dimensional Brownian Motion[END_REF] for isotropic stable Lévy processes of index α ∈ (0, 2):

Theorem 3.2. The family of processes

Θ (c) t ≡ c -1/2 θ exp(ct) , t ≥ 0 converges in distribution on D([ 0, ∞ ) , R
) endowed with the Skorohod topology, as c → ∞, to r(α)B t , t ≥ 0 , where (B s , s ≥ 0) is a real valued Brownian motion and

r(α) = α 2 -1-α/2 π C |z| -2-α |φ(1 + z)| 2 dz . (31)
Using some results due to Whitt [START_REF] Whitt | Some useful functions for functional limit Theorems[END_REF], we can obtain a simple proof of this Theorem.

Proof of Theorem 3.2: (new proof) Essentially, an argument of continuity of the composition function (Theorem 3.1 in [START_REF] Whitt | Some useful functions for functional limit Theorems[END_REF]) may replace the martingale argument in the lines of the proof for t → ∞ from Bertoin and Werner. We split the proof in three parts:

i) Concerning the clock H, we have the almost sure convergence (20):

H(e u ) u a.s. -→ u→∞ K(α) = E |Z 1 | -α .
From this result follows the convergence of the finite dimensional distributions of v -1 H(exp(vt)), for v → ∞ and every t > 0. Moreover, from Proposition 3.1, the family of processes

H (u) x ≡ H(e ux ) u , x ≥ 0 is tight as u → ∞.
Hence, from (20) and (21), finally, H (u) (t) ≡ (u -1 H(exp(ut)), t ≥ 0) converges weakly to (tK(α), t ≥ 0) as u → ∞, i.e.:

H(e ut ) u , t ≥ 0

(d) =⇒ u→∞ (tK(α), t ≥ 0), (32)
where the convergence in distribution is viewed on D([ 0, ∞ ) , R) endowed with the Skorohod topology.

ii) Using the skew product representation analogue (11) and Lemma 2.2, we have:

ρ tu √ u , t ≥ 0 (d) =⇒ u→∞ k(α) B t , t ≥ 0 , (33)
where the convergence in distribution is viewed again on D([ 0, ∞ ) , R) endowed with the Skorohod topology and k(α) is given by (10). This follows from the convergence of the finite dimensional distributions:

ρ u √ u = θ A(u) √ u (d) -→ u→∞ k(α) B 1 , (34)
a condition which is sufficient for the weak convergence (33), since Lévy processes are semimartingales with stationary independent increments; for further details see e.g. [START_REF] Skorohod | Random Processes with Independent Increments[END_REF] or [START_REF] Jacod | Limit theorems for stochastic processes[END_REF] (Corollary 3.6, Chapter VII, p. 415).

iii) Theorem 3.1 in [START_REF] Whitt | Some useful functions for functional limit Theorems[END_REF] states that the composition function on

D([ 0, ∞ ) , R) × D([ 0, ∞ ) , [ 0, ∞ )) is continuous at each (ρ, H) ∈ (C([ 0, ∞ ) , R)×D 0 ([ 0, ∞ ) , [ 0, ∞ ))),
with C denoting the set of continuous functions and D 0 the subset of increasing cadlag functions in D (hence the subset of non-decreasing cadlag functions in D). Hence, from (32) and (33), we have: for every t > 0,

θ exp(ct) √ c = ρ H(exp(ct)) √ c = ρ c(H(e ct )/c) √ c . ( 35
)
The result now follows from the continuity of the composition function together with (35) and the weak convergence of H (c) (•) and c -1/2 ρ c , as c → ∞.

From Theorem 3.2, we can obtain the asymptotic behaviour of the exit times from a cone for isotropic stable processes which generalizes a recent result in [START_REF] Vakeroudis | Integrability properties and Limit Theorems for the exit time from a cone of planar Brownian motion[END_REF]:

Proposition 3.3. For c → ∞, for every x > 0, we have the weak convergence:

1 c log T θ x √ c , x ≥ 0 (d) =⇒ c→∞ τ (1/2) √ 1/r(α) , x ≥ 0 , (36)
where for every y > 0, τ

(1/2) y stands for the 1 2 -stable process defined by: τ

(1/2) y ≡ inf{t : B t = y}.

Proof of Proposition 3.3:

We rely now upon Theorem 3.2, the analogue of Spitzer's Theorem for stable processes by Bertoin and Werner:

Θ (c) t ≡ c -1/2 θ exp(ct) , t ≥ 0 (d) =⇒ c→∞ B r(α)t , t ≥ 0 . (37)
Hence, for every x > 0,

1 c log T θ x √ c = 1 c log inf t : θ t > x √ c t=exp(cs) = 1 c log inf e cs : 1 √ c θ exp(cs) > x = inf s : 1 √ c θ exp(cs) > x c→∞ -→ inf s : B r(α)s > x = inf s : r(α)B s > x ≡ τ (1/2) x/ √ r(α) . (38)
Moreover, from Theorem 7.1 in [START_REF] Whitt | Some useful functions for functional limit Theorems[END_REF], we know that the first passage time function mapping is continuous, thus, we deduce (36).

If we replace c by ac, we can obtain several variants of Proposition 3.3 for the random times T θ -bc,ac , 0 < a, b ≤ ∞, for c → ∞, and a, b > 0 fixed:

Corollary 3.4. The following asymptotic results hold:

1 c log T θ √ ac (law) -→ c→∞ τ (1/2) √ a/r(α) , (39)
1 c log T |θ| √ ac (law) -→ c→∞ τ |B| √ a/r(α) , (40)
1 c log T θ - √ bc, √ ac (law) -→ c→∞ τ B - √ b/r(α), √ a/r(α) , (41)
where for every x, y > 0, τ

|B| x ≡ inf{t : |B t | = x} and τ B -y,x ≡ inf{t : B t / ∈ (-y, x)}.
Proposition 3.5. The following asymptotic result for α ∈ (0, 2), holds: for every b > 0,

P T θ b √ log t > t t→∞ -→ erf b 2r(α) , (42)
where erf(x) ≡ 2 √ π x 0 e -y 2 dy is the error function. Proof of Proposition 3.5: Using the notation of Theorem 3.2, for every b > 0, we have:

P T θ b √ log t > t = P sup u≤t θ u < b log t u=t v = P sup v≤1 (log t) -1/2 θ t v < b t=e c = P sup v≤1 c -1/2 θ exp(cv) < b
Hence, using Theorem 3.2 for t → ∞, we deduce:

P T θ b √ log t > t t→∞ -→ P sup v≤1 r(α)B v < b = P |B 1 | < b r(α) = 2 b/ √ r(α) 0 dw √ 2π e -w 2 /2 ,
and changing the variables w = y √ 2, we obtain (42).

As mentioned in [START_REF] Bertoin | Stable windings[END_REF], because an isotropic stable Lévy process Z is transient, the difference between θ and the winding number around an arbitrary fixed z = 1 is bounded and converges as t → ∞. Hence, with (θ i t , t > 0), 1 ≤ i ≤ n denoting the continuous total angle wound of Z of index α ∈ (0, 2) around z i (z 1 , . . . , z n are n distinct points in the complex plane C) up to time t, we obtain the following concerning the finite dimensional distributions (windings around several points): Proposition 3.6. For isotropic stable Lévy processes of index α ∈ (0, 2), we have:

θ i t √ log t , 1 ≤ i ≤ n (d) =⇒ t→∞ r(α)B i 1 , 1 ≤ i ≤ n , (43)
where (B i s , 1 ≤ i ≤ n, s ≥ 0) is an n-dimensional Brownian motion and r(α) is given by (31).

Small time asymptotics

We turn now our study to the behaviour of θ t for t → 0.

Theorem 4.1. For α ∈ (0, 2), the following convergence in law holds:

t -1/α ρ ts , s ≥ 0 (d) =⇒ t→0 (ζ s , s ≥ 0) , (44)
where (ζ s , s ≥ 0) is a symmetric 1-dimensional α-stable process and the convergence in distribution is considered on D([ 0, ∞ ) , R) endowed with the Skorohod topology.

Proof of Theorem 4.1: From Lemma 2.2, we use the Lévy measure, say π, of θ A(•) (thus the Lévy measure of ρ) and we prove that for t → 0 it converges to the Lévy measure of a 1-dimensional α-stable process. Indeed, with

L ≡ α 2 -1+α/2 Γ(1 + α/2) πΓ(1 -α/2) ,
and z denoting a number in C, using polar coordinates, we have:

φ (1 + z) = C dz 1 + z = 2L π 0 ∞ 0 r dr dϕ (1 + r 2 -2r cos ϕ) 1+α/2 .
We remark that:

1 + r 2 -2r cos ϕ = (r -cos ϕ) 2 + sin 2 ϕ ,
hence, changing the variables (rcos ϕ) 2 = t -1 sin 2 ϕ and denoting by:

B(y; a, b) = y 0 u a-1 (1 -u) b-1 du ,
the incomplete Beta function, for ϕ > 0 (we can repeat the same arguments for ϕ < 0) we have:

π(dϕ) = dϕ 2L ∞ 0 r dr (r -cos ϕ) 2 + sin 2 ϕ 1+α/2 = dϕ 2L 2 2 α + cos ϕ 1 -cos 2 ϕ -1 2 -α 2 1-1 cos 2 ϕ 0 t -1 2 + α 2 (1 + t) -α 2 -1 dt u=-t = dϕ L 2 α + cos ϕ -1 + cos 2 ϕ -1 2 -α 2 1-1 cos 2 ϕ 0 u -1 2 + α 2 (1 -u) -α 2 -1 du = dϕ L 2 α + cos ϕ -1 + cos 2 ϕ -1 2 -α 2 B 1 - 1 cos 2 ϕ ; 1 2 + α 2 , - α 2 ϕ∼0 ∼ Lϕ -1-α dϕ , (45)
which is the Lévy measure of an α-stable process. The result now follows by standard arguments.

Concerning the clock H and its increments, we have:

Theorem 4.2. The following a.s. convergence holds:

H(ux) u , x ≥ 0 a.s. -→ u→0 (x, x ≥ 0) . (46)
Proof of Theorem 4.2: From the definition of the clock H we have:

H(ux) u = 1 u ux 0 ds |Z s | α .
Hence, for every x 0 > 0, we have:

sup x≤x 0 H(ux) -ux u = sup x≤x 0 1 u ux 0 1 |Z s | α -1 ds ≤ 1 u ux 0 0 1 |Z s | α -1 ds s=uw = x 0 0 1 |Z uw | α -1 dw a.s. -→ u→0 0 . (47)
because:

|Z u | α a.s. -→ u→0 1 . (48)
Thus, as (47) is true for every x 0 > 0, we obtain (46).

Remark 4.3. We remark that this behaviour of the clock is different for the case t → ∞, where (32) can be equivalently stated as:

H(ux) log u , x ≥ 0 (d) =⇒ u→∞ 2 -α Γ(1 -α/2) Γ(1 + α/2) x, x ≥ 0 . (49)
Using Theorems 4.1 and 4.2, we obtain:

Theorem 4.4. With α ∈ (0, 2), the family of processes c -1/α θ ct , t ≥ 0 converges in distribution on D([ 0, ∞ ) , R) endowed with the Skorohod topology, as c → 0, to a symmetric 1-dimensional α-stable process (ζ t , t ≥ 0).

Proof of Theorem 4.4:

We will use Theorems 4.1 and 4.2. More precisely, we shall rely again upon the continuity of the composition function as studied in Theorem 3.1 in [START_REF] Whitt | Some useful functions for functional limit Theorems[END_REF].

i) First, concerning the clock H, for every t > 0, we have the almost sure convergence (46), which yields the weak convergence (on D([ 0, ∞ ) , R) endowed with the Skorohod topology) of the family of processes H(u) (t) ≡ (u -1 H(ut), t ≥ 0) to (t, t ≥ 0) as u → 0.

ii) We use another result of Whitt [START_REF] Whitt | Some useful functions for functional limit Theorems[END_REF] which states that the composition function on

D([ 0, ∞ ) , R) × D([ 0, ∞ ) , [ 0, ∞ )) is continuous at each (ρ, H) ∈ (D([ 0, ∞ ) , R) × C 0 ([ 0, ∞ ) , [ 0, ∞ ))
), with D denoting the set of cadlag functions and C 0 the subset of strictly-increasing functions in C. Hence, from Theorem 4.1 and (46), using the weak convergence of H(c) (•) and of c -1/α ρ c , as c → 0, we deduce: for every t > 0,

θ ct c 1/α = ρ H(ct) c 1/α = ρ c(H(ct)/c) c 1/α (d) =⇒ c→0 ζ t , (50)
where the convergence in distribution is viewed on D([ 0, ∞ ) , R) endowed with the Skorohod topology.

From the previous results, we deduce the asymptotic behaviour, for c → 0, of the first exit times from a cone for isotropic stable processes of index α ∈ (0, 2) taking values in the complex plane:

Proposition 4.5. For c → 0, we have the weak convergence:

1 c T θ c 1/α x , x ≥ 0 (d) =⇒ c→0 T ζ x x ≥ 0 , (51)
where for every x, T ζ x is the first hitting time defined by: T

ζ x ≡ inf{t : ζ t = x}.
Proof of Proposition 4.5: Using Theorem 4.4, we have:

1 c T θ c 1/α x = 1 c inf t : θ t > c 1/α x t=cs = 1 c inf cs : c -1/α θ cs > x = inf s : c -1/α θ cs > x c→0 -→ inf {s : ζ s > x} ,
which, using again the continuity of the first passage time function mapping (see Theorem 7.1 in [START_REF] Whitt | Some useful functions for functional limit Theorems[END_REF]), yields (51).

Finally, we can obtain several variants of Proposition 4.5 for the random times T θ -bc,ac , 0 < a, b ≤ ∞ fixed, for c → 0: Corollary 4.6. The following asymptotic results hold:

1 c T θ ac 1/α (law) -→ c→0 T ζ a , (52)
1 c T |θ| ac 1/α (law) -→ c→0 T |ζ| a , (53)
1 c T θ -bc 1/α ,ac 1/α (law) -→ c→0 T ζ -b,a , (54)
where, for every x, y > 0, T = t 1/α Z v , yield:

H ( t,1 ] = 1/t 1 t dv |Z tv | α (law) = 1/t 1 dv |Z v | α = H ( 1,1/t ] .
Hence, as before, using Whitt's result [START_REF] Whitt | Some useful functions for functional limit Theorems[END_REF] on the continuity of the composition function on

D([ 0, ∞ ) , R) × D([ 0, ∞ ) , [ 0, ∞ )) at each (ρ, H) ∈ (D([ 0, ∞ ) , R) × C 0 ([ 0, ∞ ) , [ 0, ∞ )))
, we have (with obvious notation):

θ ( t,1 ] = ρ H ( t,1 ] (law) = ρ H ( 1,1/t ] = θ ( 1,1/t ] . (55)
The only difference with respect to the "normal" stable case is that the winding process is considered from 1 and not from 0, but this doesn't provoke any problem. Hence, Bertoin and Werner's Theorem 3.2 is still valid for Z in ( t, 1 ], t → 0: for α ∈ (0, 2):

1 log(1/t) θ ( t,1 ] (law) = 1 log(1/t) θ ( 1,1/t ] (d) =⇒ t→0 r(α)N, (56)
with r(α) defined in (31) and N ∽ N (0, 1).

ii) We note that this study is also valid for a planar Brownian motion starting from 0 in ( t, 1 ] for t → 0 and for planar stable processes or planar Brownian motion starting both from a point different from 0 (in order to have an well-defined winding number) in [0, 1]. In particular, for planar Brownian motion Z with associated winding number ϑ, we obtain that Spitzer's law is still valid for t → 0 (see e.g. [START_REF] Revuz | Continuous Martingales and Brownian Motion[END_REF][START_REF] Gall | Some properties of planar Brownian motion[END_REF]):

2 log(1/t) ϑ ( t,1 ] (law) -→ t→0 C 1 , (57)
where C 1 is a standard Cauchy variable. We also remark that this result could also be obtained from a time inversion argument, that is: with Z ′ denoting another planar Brownian motion starting from 0, with winding number ϑ ′ , by time inversion we have: Z u = uZ ′ 1/u . Changing now the variables u = 1/v, we obtain:

ϑ ( t,1 ] ≡ Im 1 t dZ u Z u = Im 1 t d(uZ ′ 1/u ) uZ ′ 1/u = Im 1 t dZ ′ 1/u Z ′ 1/u = Im 1/t 1 dZ ′ v Z ′ v ≡ ϑ ′ ( 1,1/t ] ,
and we continue as before.

Note that this time inversion argument is NOT valid for planar stable processes.

From (58), we have that,

U(f (t n )) (f (t n )) 2 tn∼0 ∼ (f (t n )) -α .
Hence, when I(f ) < ∞, from Borel-Cantelli Lemma we have that with probability 1, ρ t n-1 ≤ f (t n ) for all n's, except for a finite number of them. Now, from a monotonicity argument for f , if t ∈ [t n , t n-1 ], we have that:

ρ t n-1 ≤ f (t n ) ≤ f (t)
for every t sufficiently small. It follows now that lim t→0 (ρ t /f (t)) ≤ 1 a.s. Finally, we remark that as I(f ) < ∞, we also have that I(εf ) < ∞, for arbitrarily small ε > 0 and follows that ρ t /f (t) → 0 a.s. The proof of the second statement follows from the same kind of arguments. Indeed, using Lemma 2 from Doney and Maller [START_REF] Doney | Stability of the overshoot for Le'vy processes[END_REF] and the fact that ρ is symmetric, there exists a positive constant c 2 such that for every x > 0, t > 0,

P sup 0≤u≤t ρ u ≤ x ≤ c 2 t h(x) . (63)
Hence:

∞ n=1 P ρ t n-1 ≤ f (t n-1 ) ≤ ∞ n=1 P sup 0≤u≤t n-1 ρ u ≤ f (t n-1 ) ≤ ∞ n=1 c 2 t n-1 h(f (t n-1 ))
.

Thus, for I(f ) = ∞ (or equivalently h(f (t n-1 )) = ∞), Borel-Cantelli Lemma yields that for every n, a.s. ρ t n-1 > f (t n-1 ) infinitely often, which finishes the proof.

Remark 5.3. For other kinds of LIL for Lévy processes for small times e.g. of the Chung type, see [START_REF] Aurzada | Small time Chung type LIL for Lévy processes[END_REF] and the references therein.

Theorem 5.4. (LIL for the angular part of planar stable processes for small times) For any non-decreasing function f > 0, lim sup

t→0 θ t f (t) = 0 ; ∞ a.s. ⇔ ∞ 1 (f (t)) -α dt < ∞ ; = ∞ . (64)
Proof of Theorem 5.4:

We use the skew-product representation (13) together with (46), which essentially writes:

t -1 H(t) a.s.
-→ t→0 1. Thus, for every ε, δ > 0, there exists t 0 > 0 such that:

P H(t) t ≤ 1 + ε ≥ 1 -δ, for t ≤ t 0 . (65)
We define now the setting:

K ≡ K(ω) ≡ ω : H(t) t ≤ 1 + ε , thus : K ≡ K(ω) ≡ ω : H(t) t ≥ 1 + ε ,
hence, there exists t 0 > 0 such that: for every t ≤ t 0 , P (K) ≥ 1δ and P (K) ≤ δ .

Hence, choosing δ > 0 small enough, it suffices to restrict our study in the set K and it follows that: Changing now the variables ũ = u(1 + ε), and invoking (62), there exists another positive constant c 3 such that, for every x > 0 and t > 0:

P sup 0≤u≤t θ u > x = P sup
P sup 0≤u≤t θ u > x ≤ P sup 0≤ũ≤t(1+ε) ρ ũ > x ≤ c 3 t(1 + ε) U(x) x 2 . ( 66
)
Mimicking now the proof of Theorem 5.1, we obtain the first statement.

For the second statement, we use the settings:

K ′ ≡ K ′ (ω) ≡ ω : H(t) t ≥ 1 -ε , thus : K ′ ≡ K ′ (ω) ≡ ω : H(t) t ≤ 1 -ε .
Hence, for every ε, δ > 0, there exists t 0 > 0 such that: for every t ≤ t 0 , P (K ′ ) ≥ 1δ and P (K ′ ) ≤ δ .

As before, we choose δ > 0 small enough and we restrict our study in the set K ′ . The proof finishes by repeating the arguments of the proof of Theorem 5.1.

The planar Brownian motion case

Before starting, we remark that the notations used in this Section are independent from the ones used in the text up to now.

In this Section, we state and give a new proof of the analogue of Theorem 4.4 for the planar Brownian motion case, which is equivalent to a result obtained in [START_REF] Vakeroudis | Integrability properties and Limit Theorems for the exit time from a cone of planar Brownian motion[END_REF]. For this purpose, and in order to avoid complexity, we will use the same notation as in the "stable" case. Hence, for a planar BM Z starting from a point different z 0 from 0 (without loss of generality, let z 0 = 1) and with ϑ = (ϑ t , t ≥ 0) denoting now the (well defined -see eg. [START_REF] Itô | Diffusion Processes and their Sample Paths[END_REF]) continuous winding process, we have the skew product representation (see e.g. [START_REF] Revuz | Continuous Martingales and Brownian Motion[END_REF]): -→ t→∞ T 1 ≡ inf{t :

log
β t = 1} , (75)
where the latter follows essentially from the classical Laplace argument:

• p p→∞ -→ • ∞ .
We also remark that, from Remark 4.3, the behaviour of the clock for t → 0 is a.s. the same for Brownian motion and for stable processes, whereas it is different for t → ∞. In particular, for t → ∞, compare (49) to (75).

0≤u≤tρ

  H(u) > x = P sup 0≤u≤t ρ H(u) > x ∩ K ≤ P sup 0≤u≤t ρ u(1+ε) > x

  We consider now our stable process Z starting from 0 and we want to investigate its windings in ( t, 1 ] for t → 0. We know that it doesn't visit again the origin but it winds a.s. infinitely often around it, hence, its winding process θ in ( t, 1 ] is well-defined. With obvious notation, concerning now the clock H ( t,1 ] = 1 t du |Z u | -α , the change of variables u = tv and the stability property, i.e.: Z tv

	|ζ| x ≡ inf{t : |ζ t | = x} and T ζ -y,x ≡ inf{t : ζ t / ∈ (-y, x)}. Remark 4.7. (Windings of planar stable processes in ( t, 1 ] for t → 0) i) (law)

  |Z t | + iϑ t ≡ The Bessel clock H plays a key role in many aspects of the study of the winding number Remark 6.3. We highlight the different behaviour of the clock H for t → 0 and for t → ∞ (for the second see e.g.[START_REF] Pitman | The asymptotic joint distribution of windings of planar Brownian motion[END_REF], followed by [PiY86, LGY86, LGY87], a result which is equivalent to Spitzer's Theorem[START_REF] Spitzer | Some Theorems concerning two-dimensional Brownian Motion[END_REF] stated in (1) ), that is:

	H(t) t		a.s. -→ t→0	1 ,				(74)
	4H(t)	(law)
	(log t) 2
	0	t	dZ s Z s	= (β u + iγ u )	u=Ht= t 0	|Zs| 2 ds	,	(67)

where (β u + iγ u , u ≥ 0) is another planar Brownian motion starting from log 1 + i0 = 0.

Acknowledgements

The author S. Vakeroudis is very grateful to Professor M. Yor for the financial support during his stay at the University of Manchester as a Post Doc fellow invited by Professor R.A. Doney.

The Law of the Iterated Logarithm (LIL)

In this Section, we shall use some notation introduced in [START_REF] Doney | Stability of the overshoot for Le'vy processes[END_REF][START_REF] Doney | Stability and Attraction to Normality for Le'vy processes at zero and infinity[END_REF]. Recall (19); then, for all x > 0, because ρ is symmetric, we define: L(x) = 2μ(x) = 2µ(x, +∞), U(x) = 2 x 0 yL(y)dy .

We remark that U plays essentially the role of the truncated variance in the random walk case (see e.g. [START_REF] Doney | Random walks crossing curved boundaries:a functional limit theorem, stability and asymptotic distributions for exit positions[END_REF]). Hence, from (44), for t → 0, we have ( K(α) is a constant depending on α):

Then, we obtain the following Law of the Iterated Logarithm (LIL) for Lévy processes for small times:

Theorem 5.1. (LIL for Lévy processes for small times) For any non-decreasing function f > 0, lim sup

We can reformulate Theorem 5.1 by using the skew-product representation (13) stating: ρ t = θ A(t) , in order to deduce a LIL for the winding process θ A(•) for small times.

Corollary 5.2. For any non-decreasing function f > 0, lim sup

Proof of Theorem 5.1: First, we define:

Then, we consider t n = 2 -n and we note that (Cauchy's test):

Using now Lemma 2 from Doney and Maller [START_REF] Doney | Stability of the overshoot for Le'vy processes[END_REF], because ρ is symmetric, there exists a positive constant c 1 such that for every x > 0, t > 0,

Thus:

process (ϑ t , t ≥ 0) (see e.g. [START_REF] Yor | Loi de l'indice du lacet Brownien et Distribution de Hartman-Watson[END_REF]). We shall also make use of the inverse of H, which is given by:

Rewriting (67) as:

we easily obtain that the two σ-fields σ{|Z t | , t ≥ 0} and σ{β u , u ≥ 0} are identical, whereas (γ u , u ≥ 0) is independent from (|Z t | , t ≥ 0), a fact that is in contrast to what happens in the "stable" case.

Theorem 6.1. The family of processes c -1/2 ϑ ct , t ≥ 0 converges in distribution, as c → 0, to a 1-dimensional Brownian motion (γ t , t ≥ 0).

Proof. We split the proof in two parts:

i) First, repeating the arguments in the proof of Theorem 4.2 with α = 2, we obtain:

which also implies the weak convergence:

ii) Using the skew product representation (69) and the scaling property of BM together with (70), we have that for every s > 0:

which finishes the proof. We remark that for part (ii) of the proof, we could also invoke Whitt's Theorem 3.1 concerning the composition function [START_REF] Whitt | Some useful functions for functional limit Theorems[END_REF], however, the independence in the planar Brownian motion case simplifies the proof.

From Theorem 6.1 now, with T ≡ inf{t : |γ t | = c}, (c > 0), we deduce for the exit time from a cone of planar BM (this result has already been obtained in [START_REF] Vakeroudis | Integrability properties and Limit Theorems for the exit time from a cone of planar Brownian motion[END_REF], where one can also find several variants): Corollary 6.2. The following convergence in law holds:


Benoit Gaüzère
email: benoit.gauzere@ensicaen.fr

Luc Brun
email: luc.brun@ensicaen.fr

Didier Villemin
email: didier.villemin@ensicaen.fr

Myriam Brun
email: myriam.brun@ensicaen.fr

Graph Kernels Based on Relevant Patterns and Cycle Information for Chemoinformatics

Chemoinformatics aim to predict molecule's properties through informational methods. Computer science's research fields concerned with chemoinformatics are machine learning and graph theory. From this point of view, graph kernels provide a nice framework for combining these two fields. We present in this paper two contributions to this research field: a graph kernel based on an optimal linear combination of kernels applied to acyclic patterns and a new kernel on the cyclic system of two graphs. These two extensions are validated on two chemoinformatics datasets.

Introduction

Chemoinformatics aims to predict molecules properties from their structural similarity. Most of existing methods are based on fingerprints defined as collections of descriptors such as the boiling point, logP, molar refractivity, etc. An alternative strategy consists to extract a set of descriptors directly from the molecular graph G = (V, E, µ, ν), where the unlabeled graph (V, E) encodes the structure of the molecule while µ maps each vertex to an atom's label and ν characterizes a type of bond between two atoms (single, double, triple or aromatic). Considering this representation, similarity between molecules can be deduced from the similarity of their molecular graphs. Graph kernels can be understood as symmetric graph similarity measures. Using a semi definite positive kernel, the value k(G, G ′ ) where G and G ′ encode two graphs corresponds to a scalar product between two vectors ψ(G) and ψ(G ′ ) in an Hilbert space. Graph kernels thus provide a natural connection between structural and statistical pattern recognition fields. A large family of kernels is based on a bag of patterns. These methods extract a bag of patterns from the graphs and deduce similarity between graphs from similarity between their bags. Most of existing methods are defined on linear patterns [START_REF] Kashima | Kernels for graphs[END_REF]. Such methods generally have a low complexity but are limited by the lack of expressivity of linear patterns on graphs. In order to use more structural information, some methods are defined on non-linear patterns. For example, treepattern kernel [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF] is based on an implicit enumeration of tree-patterns, ie. trees where a node can appear more than once. Another approach, described in Section 2 and called treelet kernel [START_REF] Gaüzère | Two new graph kernels and applications to chemoinformatics[END_REF], computes an explicit enumeration of a limited set of subtrees.

The above methods don't take into account the cyclic information encoded within molecular graphs. Nonetheless, cycles have an impact on molecules behavior and must be taken into account. Horváth proposed to combine the tree pattern kernel with an intersection kernel defined on a set of simple cycles of a graph. Despite the high complexity of the enumeration of all simple cycles of a graph, this method can be efficiently used when a set of graphs has a low number of cycles. In order to tackle the complexity required by the enumeration of all simple cycles, Horváth proposed in [START_REF] Horváth | Cyclic pattern kernels revisited[END_REF] to use a subset of simple cycles. This set is first initialized using the set of relevant cycles [START_REF] Vismara | Union of all the minimum cycle bases of a graph[END_REF]. Then, additional simple cycles are iteratively enumerated by combining relevant cycles and newly discovered cycles. Horváth showed that a low number of iterations is sufficient to obtain similar results than the ones obtained using all simple cycles. This paper presents two contributions: We propose in Section 3 a treelet kernel based on cyclic information. Unlike existing methods based on cycles, this kernel encodes topological relationships between relevant cycles. Our second contribution (Section 4) allows us to associate a weight to each treelet found in a training set. These weights are incorporated within our treelet kernel and are optimal according to a given regression or classification task on the training set. Finally, Section 5 shows results obtained by these two contributions on different chemoinformatics problems. Treelet kernel [START_REF] Gaüzère | Two new graph kernels and applications to chemoinformatics[END_REF] is a graph kernel defined as a convolution kernel between bags of patterns extracted from graphs. The set of extracted patterns, called treelets, is composed of all labeled trees with a number of nodes lower than or equal to 6 (Figure 1). The first step of our bag construction scheme enumerates the set of tree structures from a graph. This structure identification step uses two different approaches: First, a depth first traversal is performed from each node of the graph in order to enumerate linear patterns. Then, each non linear pattern is enumerated using a neighborhood analysis of n-star nodes. Such nodes correspond to nodes having a degree equal to n.

G 0 G 1 G 3 G 12 G 2 G 5 G 4 G 7 G 8 G 6 G 9 G 10 G 11 G 13
Once this structure identification step is performed, a key encoding the labels of each treelet is computed. This key, based on Morgan numbering, provides a sequence of nodes and edges labels which is unique for two isomorphic treelets. Conversely, we have shown [START_REF] Gaüzère | Two new graph kernels and applications to chemoinformatics[END_REF] that two treelets with a same index (a same structure) and a same key are isomorphic. The concatenation of treelet's index and treelet's key defines a unique code for each treelet which allows us to perform an explicit enumeration of all treelets included within a graph. Based on this enumeration, we define a function f which associates to each graph G a vector f (G), each component of this vector being equal to the number of occurrences of a given treelet t in G:

f (G) = (f t (G)) t∈T (G) with f t (G) = |(t G)| (1)
where T (G) denotes the set of treelets extracted from G and the subgraph isomorphism relationship. Then, similarity between treelet distributions is computed using a sum of subkernels between treelet's frequencies:

K T (G, G ′ ) = t∈T (G)∩T (G ′ ) k(f t (G), f t (G ′ )) (2)
where k(., .) defines any positive definite kernel between real numbers such as the linear kernel, Gaussian kernel or intersection kernel. Note that, unlike tree pattern methods, this method explicit enumerates sub trees by computing the number of occurrences of each pattern. This explicit enumeration allows us to apply a treelet weighting step, as defined in Section 4. 3 Kernel on Relevant Cycles

Relevant Cycle Graph

A simple cycle is defined as a subgraph C = (V ′ , E ′ , µ, ν) of G = (V, E) where each vertex v ∈ V ′ has a degree equal to 2. Each cycle C ⊆ G can be rep- resented as a vector C ∈ {0, 1} |E| where C i equals 1 if
i is an edge of C and is 0 otherwise. The set of vectors encoding the cycles of G defines a vector space where the addition of two cycles C and C ′ corresponds to a XOR bitwise [START_REF] Vismara | Union of all the minimum cycle bases of a graph[END_REF]. The set of relevant cycles, C R , is then defined by the union of all bases of the vector space of minimum length. The length of a base being defined as the sum of lengths of its cycles. This first step allows us to compute a canonical set of cycles with a polynomial complexity according to the number of nodes of the graphs.

Topological relations between relevant cycles can be encoded by the relevant cycle graph [START_REF] Vismara | Reconnaissance et représentation d'éléments structuraux pour la description d'objets complexes. Application à l'élaboration de stratégies de synthèse en chimie organique[END_REF]. This graph is defined as

G C = (C R , E C R , µ C R , ν C R )
where each vertex encodes a relevant cycle and two vertices are connected by an edge if their cycles share at least one vertex of the initial graph (Figure 2). According to [START_REF] Vismara | Reconnaissance et représentation d'éléments structuraux pour la description d'objets complexes. Application à l'élaboration de stratégies de synthèse en chimie organique[END_REF], a labeling function µ C R (v) is defined as the number of edges composing the cycle of v while ν C R (e) is defined as the couple (|v(C 1 )∩v(C 2 )|, (|e(C 1 )∩e(C 2 )|) where v(C R ) and e(C R ) respectively denote the set of vertices and the set of edges of a cycle. These two labeling functions only encode the size of cycles and of their connections. In order to include more information within relevant cyclic graphs, we propose to redefine these two labeling functions as follows:

• µ C R (C): Each cycle C is defined by a sequence of edge and vertex labels encountered during the traversal of C. In order to obtain a sequence invari-ant to cyclic permutations, µ C R (C) is defined as the sequence having the lowest lexicographic order.

• ν C R (e): An edge e in G C encodes a path between two cycles and is described by a sequence of edge and vertex labels. Since such a path may be traversed from its two extremities, we define ν C R (e) as the sequence of lowest lexicographic order.

In order to encode both the similarities between the cycles of two graphs and the relationships between these cycles, we apply our treelet kernel defined in Section 2 on cyclic graphs using our edge and vertex labeling functions. This kernel is thus defined as follows:

K C (G, G ′ ) = t C ∈T (G C )∩T (G ′ C ) k(f G C (t C ), f G ′ C (t C ))
(3) Unlike cyclic pattern kernel (Section 1) based on a comparison of set of simple cycles, this kernel encodes both the similarity between sets of relevant cycles (pattern G 0 in Figure 1) and relationships between these cycles (all remaining treelets in Figure 1). The proposed edge and vertex labels of the cyclic graph allows us to identify all acyclic combinations composed of at most 6 cycles. In addition, Horváth's method requires at most n k operations to perform k iterations on n relevant cycles. On the other hand, our treelet kernel requires at most nd 5 operations, where d denotes the maximal degree of relevant cycle nodes. Our method thus has a linear complexity according to the number of relevant cycles of a graph. Such a kernel may be computed efficiently as soon as the degree of the vertices of G C remains bounded.

Treelet Weighting

As shown in Section 5, the number of different treelets enumerated from the dataset can be huge and some of them may not be related to the property to be predicted. Therefore, considering these treelets in Equations 2 or 3 leads to inaccurate predictions. In order to tackle this drawback, we must weight each treelet according to its relevance for a given property. To this end, we propose to adapt a multiple kernel learning method called SimpleMKL [START_REF] Rakotomamonjy | SimpleMKL[END_REF] to variable selection. SimpleMKL defines an optimal weighting of any linear combination of N kernels according to a prediction task:

K MKL (x, x ′ ) = N i=1 w i * k i (x, x ′ ) ( 4
)
where w i ∈ R + and N i w i = 1. The treelet kernel (Equations ( 2) and ( 3)) is defined as a sum on the intersection of two sets of treelets. Given the set of treelets T computed over a training set, we define the kernel k t (G, G ′ ) specific to each treelet t ∈ T as:

k t G ′ ) = 0 if f t (G) or f t (G ′ ) = 0 k (f t (G), f t (G ′ )) otherwise (5)
Using Equation ( 5), Equations ( 2) and ( 3) may be written as:

K T (G, G ′ ) = t∈T k t (G, G ′ ) (6)
where the sum is performed over the finite set T . Using this definition, the treelet kernel can be adapted to the SimpleMKL formulation as follows:

K W (G, G ′ ) = t∈T w t * k t (G, G ′ ) (7)
where w t denotes the optimal weight defined using the SimpleMKL method. Since SimpleMKL induces a sparsity constraint on the objective function, only relevant treelets will be selected. Non zero weights may be interpreted as treelet influence measures on the property to predict.

Experiments

Regression Problem

Our first experiment evaluates the relevance of our treelet weighting procedure (Section 4) by a regression task on molecule's boiling points using a dataset1 composed of 185 acyclic molecules. Prediction is performed using a 10-fold cross validation. The first line of Table 1 shows results obtained by the random walks kernel [START_REF] Kashima | Kernels for graphs[END_REF]. Due to the limited expressivity of linear patterns, this method doesn't correctly predict the boiling point property. Line 2 shows results obtained by a Gaussian kernel based on graph edit distance [START_REF] Neuhaus | Bridging the gap between graph edit distance and kernel machines[END_REF]. This method obtains a better result than a kernel based on linear patterns. In the same way, tree pattern [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF] and treelet kernels improve the accuracy of prediction models (Table 1, Lines 3 and 4). Finally, the three last lines show results obtained by two treelet selection methods described in [START_REF] Gaüzère | Two new graph kernels and applications to chemoinformatics[END_REF] and our treelet weighting method defined in Section 4. Using this dataset, 138 different treelets have been enumerated. As shown by Line 7, the lowest root mean squared error (RMSE) is obtained using the SimpleMKL algorithm. A major difference between the MKL method and forward selection and backward elimination methods, which may explain this result, is that the SimpleMKL algorithm provides an optimal real weighting on the training set while forward and backward eliminations only a set of selected treelets [START_REF] Gaüzère | Two new graph kernels and applications to chemoinformatics[END_REF]. Treelet kernel on cycle graphs has not been tested on this experiment since the dataset is exclusively composed of acyclic molecules.

Classification Problems

The second experiment is a classification problem taken from the Predictive Toxicity Challenge [START_REF] Toivonen | Statistical evaluation of the predictive toxicology challenge 2000-2001[END_REF] which aims to predict carcinogenicity of chemical compounds applied to female (F) and male (M) rats (R) and mice (M). This experiment is based on ten different datasets, each of them being composed of one trainset and one testset. Table 2 shows the number of correctly classified molecules over the ten testsets for each method and for each class of animal. As shown by Table 2, Lines 1 and 2, Horváth's cycle kernel [START_REF] Horváth | Cyclic pattern kernels revisited[END_REF] obtains better classification accuracy than our treelet kernel, hence showing the importance of cyclic information in this experiment. Our cyclic kernel, taking into account both relevant cycles and their relationships, outperforms the one of Horvárth's (Lines 2 and 3) which does not encode labels between cycles. As shown by Lines 4 and 5, the selection of treelets using the SimpleMKL algorithm allows us to improve the classification accuracy of both our treelet and cyclic kernels. Note that SimpleMKL allows us to reduce the number of treelets from about 3500 to 150, depending on dataset. Finally, a weighted sum of both kernels (Line 6), with both weights set by cross-validation, allows us to slightly improve the individual results of each kernel. This clear separation between cyclic and acyclic information is one reason which may explain the better classification accuracy of our final kernel compared to the one obtained by the Gaussian Edit Distance kernel (Line 7).

Conclusion

We have proposed a new kernel between cyclic systems of molecules. This kernel compares both the relevant cycles of two graphs and the adjacency relationships between these relevant cycles. This kernel may be computed with a linear complexity according to the number of relevant cycles. We also proposed to adapt a multiple kernel learning framework in order to select the most relevant patterns of our kernels for a prediction task. Further works will aim to improve the definition of our graph of relevant cycles in order to take into account more information about cycles within our kernel.

Figure 1 .

 1 Figure 1. Set of treelet's structures

Figure 2 .

 2 Figure 2. A cyclic system and its graph representation. Canonical key µ C R (C 2 ) is equals to C1C1C1O1C1C2C.

Table 1 . Boiling point prediction.

 1

	Method	RMSE ( • C)
	1 Random Walks Kernel	18.72
	2 Gaussian edit distance	10.27
	3 Tree Pattern Kernel	11.02
	4 Treelet Kernel (TK)	8.10
	5 TK + Forward Selection	7.05
	6 TK + Backward Elimination	6.75
	7 TK + MKL	5.24

Table 2 . Classification accuracy on PTC.

 2

	Method	MM FM MR FR
	1 Treelet Kernel (TK)	208 205 209 212
	2 Horváth	209 207 202 228
	3 TK on Cycles (TC)	211 210 203 232
	4 TK + MKL	217 224 223 250
	5 TC + MKL	216 213 212 237
	6 (TK + αTC) + MKL	219 226 226 251
	7 Gaussian Edit Distance 223 212 194 234

This database is available on the IAPR TC15 Web page: http://www.greyc.ensicaen.fr/iapr-tc15/links.html#chemistry


Benoit Gaüzère
email: benoit.gauzere@ensicaen.fr

Luc Brun

Didier Villemin

Graph Kernels: Crossing Information from Different Patterns using Graph Edit Distance

Graph kernels allow to define metrics on graph space and constitute thus an efficient tool to combine advantages of structural and statistical pattern recognition fields. Within the chemoinformatics framework, kernels are usually defined by comparing number of occurences of patterns extracted from two different graphs. Such a graph kernel construction scheme neglects the fact that similar but not identical patterns may lead to close properties. We propose in this paper to overcome this drawback by defining our kernel as a weighted sum of comparisons between all couples of patterns. In addition, we propose an efficient computation of the optimal edit distance on a limited set of finite trees. This extension has been tested on two chemoinformatics problems.

Introduction

Chemoinformatics aims to predict molecule's properties from their structural similarity. Most of existing methods are based on fingerprints defined as collections of descriptors such as boiling point, logP, molar refractivity, etc. An alternative strategy consists to extract a set of descriptors directly from the molecular graph G = (V, E, µ, ν), where the unlabeled graph (V, E) encodes the structure of the molecule while µ maps each vertex to an atom's label and ν characterizes a type of bond between two atoms (single, double, triple or aromatic). Considering this representation, similarity between molecules can be deduced from the similarity of their molecular graphs.

Graph kernels can be understood as symmetric graph similarity measures. Using a semi definite positive kernel, the value k(G, G ′ ), where G and G ′ encode two graphs, corresponds to a scalar product between two vectors ψ(G) and ψ(G ′ ) in an Hilbert space. Graph kernels provide thus a natural connection between structural and statistical pattern recognition fields. A large family of kernels is based on bags of patterns. These methods extract a bag of patterns from each graph and deduce graph's similarity from bag's similarity by comparing the number of occurrences of each pattern within both graphs. Most of existing methods are defined on linear patterns [START_REF] Kashima | Kernels for graphs[END_REF]. Such methods have generally a low complexity but are limited by the lack of expressivity of linear patterns on graphs. In order to use more structural information, some methods are based on non linear patterns, such as the tree-pattern kernel [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF]. This last method is

G 0 G 1 G 3 G 12 G 2 G 5 G 4 G 7 G 8 G 6 G 9 G 10 G 11 G 13
Fig. 1. Set of sub structures enumerated from the graphs.

based on an implicit enumeration of tree patterns, ie. trees where a node can appear more than once. Another approach, called treelet kernel [START_REF] Gaüzère | Two new graph kernels and applications to chemoinformatics[END_REF], computes an explicit enumeration of a limited set of subtrees. Treelet kernel is a graph kernel defined as a kernel between two sets of patterns extracted from both graphs to be compared. The set of extracted patterns, called treelets and denoted T , is composed of all labeled trees with a number of nodes lower than or equals to 6 (Figure 1). Based on the enumeration of this set of substructures, each graph G is associated to a vector f (G). Each component of this vector f t (G) is equals to the number of occurrences of a given treelet t in G:

f (G) = (f t (G)) t∈T (G) with f t (G) = |(t G)| (1)
where T (G) denotes the set of treelets extracted from G and the sub graph isomorphism relationship. Using this vector representation, similarity between treelet distributions is computed using a sum of sub kernels between treelet's frequencies:

K T (G, G ′ ) = t∈T (G)∩T (G ′ ) k(f t (G), f t (G ′ )) (2)
where k(., .) defines any positive definite kernel between real numbers such as linear kernel, Gaussian kernel or intersection kernel. Unfortunately, similarity of occurrences is only computed between isomorphic patterns and not between similar patterns. From a mathematical point of view, computing similarities only between isomorphic patterns relies to consider that each axis encoding a pattern is orthogonal with all other axis. This assumption is dubious since large patterns are composed by smaller ones, hence encoding partially the same information. Moreover, from a chemical point of view, two sub structures may have a similar influence on a chemical property if they slightly differ, hence showing the interest of crossing information collected from differents treelets. In order to capture this similarity, we propose to extend treelet kernel by adding comparisons of non isomorphic treelets. In Section 2, we propose to weight the influence of any pair of treelets by their edit distance. In Section 2.1, we propose an efficient way to compute an exact edit distance between treelets. Then, in Section 3, this treelet kernel extension is tested and discussed on an experimental comparison involving two chemoinformatics problems.

Haussler's convolution kernels [START_REF] Haussler | Convolution kernels on discrete structures[END_REF] are defined on objects x ∈ X which can be associated to a decomposition into finite sets X x . Considering a sub kernel k : 2) can be reformulated as a convolution kernel:

X x ×X x → R, Haussler's convolution kernel K : X ×X → R is defined as follows: K(x, y) = (x ′ ,y ′ )∈Xx×Xy k(x ′ , y ′ ) (3) By considering a decomposition X G = {(t, f t (G))|t G} of each graph and a tensor product (k ⊗ k ′ ) of two kernels k ′ : T × T → R and k : R × R → R, treelet kernel (Equation
K(G, G ′ ) = (t,ft(G))∈X G (t ′ ,f t ′ (G ′ ))∈X G ′ (k ′ ⊗ k)(t, f t (G), t ′ , f t ′ (G ′ )) K(G, G ′ ) = (t,ft(G))∈X G (t ′ ,f t ′ (G ′ ))∈X G ′ k ′ (t, t ′ )k(f t (G), f t ′ (G ′ )) (4)
where

k(f t (G), f t ′ (G ′ )) is defined as in Equation 2 and k ′ (t, t ′ ) = 1 ⇐⇒ t ≃ t ′ , 0 otherwise. Note that k ′ (t, t ′ ) is equal to 1 only if treelet t in T (G) is isomorphic to t ′
and thus belongs simultaneously to T (G) and T (G ′ ) (Equation 2). Such a definition of k ′ (t, t ′ ) restricts comparison of occurrences to isomorphic treelets.

In order to relax this restriction and based on the assumption that similar structures should have a similar chemical activity, we propose to define k ′ (t, t ′ ) in Equation 4as a measure of similarity between t and t ′ . This similarity measure is based on the graph edit distance defined as the sequence of operations transforming G into G ′ with a minimal cost [START_REF] Neuhaus | Bridging the gap between graph edit distance and kernel machines[END_REF]. Such a sequence, called an edit path, may include vertex or edge addition, removal and relabeling. Given a cost function c(.) associated to each operation, the cost of a sequence of operations is defined as the sum of each elementary operation's costs. A high edit distance indicates a low similarity between two graphs while a small one indicates a strong similarity. Unfortunately, trivial kernels defined on graph edit distance are not always semi definite positive and thus does not define valid kernels. In order to define semi definite positive kernels, we apply a regularization scheme as defined by [START_REF] Gaüzère | Two new graph kernels and applications to chemoinformatics[END_REF][START_REF] Neuhaus | Bridging the gap between graph edit distance and kernel machines[END_REF]. According to [START_REF] Neuhaus | Bridging the gap between graph edit distance and kernel machines[END_REF], the computational cost of the exact edit distance grows exponentially with the size of graphs. To overcome this problem, Fankhauser and al. [START_REF] Fankhauser | Speeding up graph edit distance computation through fast bipartite matching[END_REF] propose a method to compute an approximate edit distance in O(n 3 ) where n is equals to the number of nodes and to the maximal degree of both graphs. Such an edit distance computation provides an efficient way to compute an approximate edit distance between graphs at the cost of a lower precision.

Exact Treelet Edit Distance

Exact edit distance is hard to compute when considering the whole set of possible graphs. Given a finite set of n structures B = {(V 1 , E 1 ), . . . , (V n , E n )}, we thus restrict our study to sets of graphs D such that for any G = (V, E, µ, ν) ∈ D we have (V, E) ∈ B. We show in the remaining of this section that within this framework, exact edit distance may be computed within a reasonable computational time using ad hoc methods. In order to present such methods, let us introduce some common definitions. A graph

G ′ = (V ′ , E ′ , µ ′ , ν ′ ) is a structural sub graph of G = (V, E, µ, ν), denoted G ′ s G, iff V ′ ⊆ V and E ′ ⊆ E ∩ (V ′ × V ′ ). In addition, if µ ′ |V ′ = µ and ν ′ |E ′ = ν, f | denoting the restriction of function f to a particular domain, then G ′ is a sub graph of G, denoted G ′ G. A graph G = (V, E, µ, ν) is structurally isomorphic to a graph G ′ = (V ′ , E ′ , µ ′ , ν ′ ), denoted G ≃ s G ′ iff there exists a bijective function f : V → V ′ such that (u, v) ∈ E ⇔ (f (u), f (v)) ∈ E ′ . If µ ′ • f = µ and ν ′ • f = ν, then G is isomorphic to G ′ , denoted G ≃ G ′ . If G = G ′ then f is called an automorphism. If f is only injective then it exists a sub graph isomorphism between G and G ′ . A graph Ĝ is a maximal common sub graph of G 1 and G 2 if it is a sub graph of G 1
and G 2 and if it is not a sub graph of any other common sub graph of G 1 and G 2 . A graph Ĝ is called a maximum common sub graph of G 1 and G 2 if it is a common sub graph of G 1 and G 2 with a maximal number of nodes.The notions of maximal structural sub graph and maximum structural sub graph are defined the same way using the notion of structural sub graph.

Under mild assumptions [START_REF] Brun | Relationships between graph edit distance and maximal common unlabeled subgraph[END_REF], the sequence of edit operations encoding an edit path can be ordered into a sequence of deletions, substitutions and additions as illustrated in Figure 2(a). The first sequence transforms the initial graph G 1 into one of its sub graphs Ĝ1 by deleting a set of nodes corresponding to V 1 -V1 and a set of edges corresponding to E 1 -Ê1 . The second sequence represents the set of substitutions transforming Ĝ1 into Ĝ2 . This set of substitutions defines a one to one matching between V1 and V2 on the one hand and between Ê1 and Ê2 on the other. Substitutions matching two elements having a same label are denoted as identical substitutions. Finally, the last sequence corresponds to the addition of a set of nodes and edges in order to transform Ĝ2 into G 2 . Note that the set of operations transforming Ĝ1 into Ĝ2 is only composed of substitutions which do not modify the structure of graphs. Therefore, Ĝ1 and Ĝ2 have a same structure and correspond to two structurally isomorphic sub graphs of G 1 and G 2 . We define costs on edit operations as non negative constant functions for edges (c e * ) and vertex (c v * ) deletions (c * d ), insertions (c * i ) or substitutions (c * s ). In addition, the cost associated to an identical substitution is equals to 0 since such an operation does not modify the graph. Using the representation described in Figure 2(a) and cost functions previously defined, the cost of any edit path is equals to: [START_REF] Haussler | Convolution kernels on discrete structures[END_REF] with V f , resp. E f , denoting the number of non identical substitutions on nodes, resp. edges, required to transform Ĝ1 into Ĝ2 . Bunke have shown that under some slightly different conditions on edge operations, constraining the costs to c vd + c vi < c vs and c es < c vs induces that Ĝ1 ≃ Ĝ2 correspond to a maximum common sub graph of G 1 and G 2 [START_REF] Bunke | Error correcting graph matching: On the influence of the underlying cost function[END_REF]. However, maximum common sub graph of two graphs depends both on structure and labels. This last point does not allow us to use efficiently our assumption that the number of different structures of any set of graphs is bounded and known a priori. We propose to study if different conditions between costs can lead to a possible efficient algorithm to compute an exact edit distance. Proof. [START_REF] Brun | Relationships between graph edit distance and maximal common unlabeled subgraph[END_REF] Considering two graphs G 1 and G 2 , this first proposition ensures that sequences of structural operations transform G 1 and G 2 into one of their maximal common structural sub graphs. Since maximal common structural sub graph does not depend on labeling information, the set of maximal common structural sub graphs may be pre computed between any pair of structure belonging to B. However, this number may be large hence forbidding an efficient pre computation of the exact edit distance. By restricting conditions on costs, we obtain a relationship leading to a reduced set of sub structures: Proposition 2. Let us suppose that c ed = c ei = 0 and c es ≤ c vs . Given two graphs G 1 and G 2 , let us further denotes by δ v the number of vertices of their maximum common structural sub graphs and by δ e the maximal number of edges of all maximum common structural sub graphs. Then if c vd +cvi cvs ≥ δ v + δ e , Ĝ1 is a maximum common structural sub graph of G 1 and G 2 .

γ(P ) = |V 1 -V1 |c vd +|E 1 -Ê1 |c ed +V f c vs +E f c es +|V 2 -V2 |c vi +|E 2 -Ê2 |c ei
Proof. [START_REF] Brun | Relationships between graph edit distance and maximal common unlabeled subgraph[END_REF] of 183 acyclic molecules and prediction is performed using a 10-fold cross validation. The first line of Table 1 shows results obtained by random walks kernel [START_REF] Kashima | Kernels for graphs[END_REF].

Due to the limited expressivity of linear patterns, this method does not permit to predict correctly molecule's boiling points. Line 2 shows results obtained by a Gaussian kernel applied on graph edit distance [START_REF] Neuhaus | Bridging the gap between graph edit distance and kernel machines[END_REF]. This last method based on global similarity of graphs obtains a better result than kernel based on linear patterns. In the same way, tree pattern [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF] and treelet kernels (Table 1, Lines 3 and 4) improve the accuracy of prediction model based on linear patterns by including information encoded by non linear patterns. Then, Line 5 shows results obtained by combining treelet kernel with a variable selection step [START_REF] Gaüzère | Two new graph kernels and applications to chemoinformatics[END_REF] which leads to a better prediction accuracy (Table 1, Line 5) on this dataset, at the price of an high computation time. Lines 6 and 7 show results obtained using our inter treelet kernel. First, inter treelet kernel obtains a better prediction accuracy than using treelet kernel restricted to the comparison of similar treelets, hence showing the relevance of including pairs of non isomorphic treelets within kernel computation. Second, we can note that the use of an exact edit distance provides a slightly more accurate weighting than using an approximate edit distance (Table 1, Lines 6 and 7).

Our second experiment is defined as a classification problem on the monoamine oxidase (MAO) dataset which is composed of 68 molecules divided into two classes: 38 molecules inhibit the monoamine oxidase (antidepressant drugs) and 30 do not. Classification accuracy is measured for each method using a leave one out procedure with a two-class SVM. This classification scheme is made for each of the 68 molecules of the dataset. In this experiment, best results are obtained 2, Line 2). In addition, the better accuracy obtained by methods crossing information from differents patterns (Table 2, Lines 5 and 6) shows the relevance of the proposed extension. As highlighted on our first experiment, difference between the two methods may be explained by the better accuracy provided by the exact edit distance.

Conclusion

In this article, we have presented an extension of the Treelet Kernel which consists in crossing information encoded by non isomorphic treelets according to their structural similarities. In addition, we have defined a new relation between edit distance and maximum common structural sub graphs which leads to an efficient computation of edit distance between treelets. The relevance of this extension has been validated by obtaining a better prediction accuracy than original Treelet Kernel on two chemoinformatics problems. One major perspective of this work is to define the weighting of non isomorphic treelet pairs using their relevance according to a property to predict and no more by an a priori similarity measure such as edit distance.

  (a) Different steps describing an edit path. (b) Possible edit paths passing through maximum common structural sub graphs { Ĝ1 1 , . . . , Ĝn 1 } and { Ĝ1 2 , . . . , Ĝn 2 }. Dashed lines correspond to structural operations, other to substitutions.

Fig. 2 .

 2 Fig. 2. General edit path scheme and edit paths passing through maximum common structural sub graphs.

Proposition 1 .

 1 Given two graphs G 1 , G 2 , let us denote by δ v the number of vertices of their maximum structural common sub graph and by δ e , the maximal number of edges, of their structural common sub graphs. If c vd +cvi cvs ≥ δ v + ces cvs δ e and c ed +cei ces ≥ δ e + cvs ces δ v , then Ĝ1 is a maximal common structural sub graph of G 1 and G 2 .

Table 1 .

 1 Boiling point prediction.

	Method	RMSE ( • C)
	1 Random Walks Kernel	18.72
	2 Gaussian edit distance	10.27
	3 Tree Pattern Kernel	11.02
	4 Treelet Kernel	8.10
	5 Treelet Kernel with backward selection	6.75
	6 Inter Treelet Kernel with approximate edit distance	6.09
	7 Inter Treelet Kernel with exact edit distance	5.89

Table 2 .

 2 Classification accuracy on the monoamine oxidase (MAO) dataset. Tree Pattern Kernel (Table2, Line 3). Methods based on non linear patterns (Table2, Lines 3 to 6) outperform methods based on linear patterns (Table2, Line 1) and graph edit distance (Table

	Method	Classification Accuracy
	1 Random Walks Kernel	82% (56/68)
	2 Gaussian edit distance	90% (61/68)
	3 Tree Pattern Kernel	96% (65/68)
	4 Treelet Kernel	91% (62/68)
	5 Inter Treelet Kernel with approximate edit distance	93% (63/68)
	6 Inter Treelet Kernel with exact edit distance	94% (64/68)

Proposition 2 states that under some hypothesis on the costs c * d , c * i and c * s any optimal edit path between two graphs G 1 and G 2 should pass through one of their maximum common structural sub graphs. Let us consider two graphs G 1 and G 2 and without loss of generality let us suppose that these two graphs share only one maximum common structural sub graph Ĝ = ( V , Ê). Let us denote as { Ĝ0 1 , . . . , Ĝi 1 , . . . , Ĝn1 1 } and { Ĝ0 2 , . . . , Ĝi 2 , . . . , Ĝn2 2 } the sets of sub graphs of G 1 and G 2 structurally isomorphic to G (Figure 2(b)). By Proposition 2, any optimal edit path P between G 1 and G 2 should pass through one G i 1 and G j 2 . The cost associated to P can be decomposed into two parts: a structural cost γ struc (P ), corresponding to insertion and deletion operations, and a substitution cost γ label (P ), corresponding to the label substitutions required to transform Ĝi

Following Equation 5, we have:

For any i ∈ {1, . . . , n 1 }, since Ĝi

Similarly, the same holds for G 2 and Ĝj 2 for any j ∈ {1, . . . , n 2 }. Structural cost corresponding to edit path P is thus equals to:

Computing substitution cost γ label (P ) (Equation 7) relies on computing the number of non identical node substitutions V f and edge substitutions E f transforming Ĝi 1 into Ĝj 2 . Let Φ( Ĝ) denotes the set of structural automorphisms of Ĝ. Given both sub graphs Ĝi 1 and Ĝj 2 , each automorphism φ ∈ Φ( Ĝ) induces a mapping of Ĝi 1 onto Ĝj 2 and thus a substitution of the label of each vertex v (resp. edge e) of G i 1 onto the label of φ(v) (resp. φ(e)) in Ĝj 2 . More precisely, let us denote by P i,j,φ the edit path associated to the triplet ( Ĝi 1 , Ĝj 2 , φ). the number of non identical substitutions V f and E f induced by P i,j,φ is equals to:

Substitution cost of edit path P i,j,φ is thus equals to γ label (P i,j,φ ) = V f (P i,j,φ )c ns + E f (P i,j,φ )c es . Let us denotes by P opt the edit path minimizing the substitution cost:

P opt = P i0,j0,φ0 with (i 0 , j 0 , φ 0 ) = argmin (i,j,φ)∈{1,...,n1}×{1,...,n2}×Φ( Ĝ)

γ label (P i,j,φ ) (11) Since γ struct (P i,j,φ ) is the same for any (i, j, φ) ∈ {1, . . . , n 1 }×{1, . . . , n 2 }×Φ( Ĝ) (Equation 9), P opt is an edit path having a minimal cost. Therefore, under our assumptions, the edit path associated to the edit distance is the one which passes through the pair of maximum common structural sub graphs and which minimizes the number of substitutions (Equation 11). This exact edit distance computation algorithm can be applied to treelets since the set of treelets is composed of 14 different structures. In addition, by restricting the set of edit paths to the ones which preserve the connectedness of intermediate graphs [START_REF] Brun | Relationships between graph edit distance and maximal common unlabeled subgraph[END_REF], we can obtain a lower bound on the ratio between substitutions and insertion/deletion costs. Proposition 3. Considering edit paths preserving connectedness and given two trees

then Ĝ1 is a maximum common structural sub tree of T 1 and T 2 .

Proof. [START_REF] Brun | Relationships between graph edit distance and maximal common unlabeled subgraph[END_REF] When computing tree edit distance on the set of treelets, δ v is bounded by 6 and if we define costs as symmetric, i.e. c vd = c vi and c ed = c ei , bounds on costs lead to: c vd > 3c vs and c ed > 2.5c es . Since the set of treelets represents all trees having a size lower than or equals to 6, the maximum common structural sub tree of two treelets T 1 and T 2 is a treelet. The set of possible sub graphs and automorphisms for any pair of treelets can be easily pre computed since we have to consider only 14 patterns. Therefore, computing exact edit distance between two treelets consists in comparing at most max i,j∈{0,...,13} (n i * n j * |Φ ij |) label sequences where Φ ij denotes the set of automorphisms of the maximum common structural subtree T of treelets T i and T j and n i , n j the numbers of sub trees of T i and T j isomorphic to T . The value of this product on the set of treelets is bounded by 120, hence inducing a constant time complexity for the computation of the exact tree edit distance. Note that, without our restriction to a set of specific tree structures, the complexity of the edit distance calculation between labeled unordered unrooted trees is NP-Complete [START_REF] Zhang | On the editing distance between unordered labeled trees[END_REF]. In addition, given a trainset D, our kernel is defined as the 0-extension of the kernel defined by matrix e -d(ti,tj ) (i,j)∈{1,...,n} 2 , where n is the number of different treelets extracted from D. Note that this regularisation has to be performed only once since this kernel only operates on treelets and not directly on graphs.

Experiments

Our first experiment evaluates our inter treelet kernel on a regression problem which consists in predicting molecule's boiling points 3 . This dataset is composed


Pierre Degond

published or not. The documents may come

Diffusion driven by collision with the boundary