Emmanuel Russ
email: russ@u-cergy.fr

H 1 -L 1 boundedness of Riesz transforms on Riemannian manifolds and on graphs

Keywords: AMS Subject Classification (1991): 42B20, 42B30, 58G11 Riesz transforms, heat kernel, Markov kernel, H 1 at, Hörmander integral condition

We prove that the Riesz transforms are bounded from H 1 to L 1 on complete Riemannian manifolds and on graphs with the doubling property and the Poincaré inequality.

Part I Introduction

In [START_REF] Coulhon | Riesz transforms for 1 ≤ p ≤ 2[END_REF], Coulhon and Duong showed that Riesz transforms on manifolds with the doubling property and a ondiagonal upper bound for the heat kernel are L p -bounded for 1 < p ≤ 2. The corresponding discrete result, namely that Riesz transforms are L p -bounded on graphs with the doubling property and a on-diagonal upper bound of the Markov kernel, is shown in [START_REF] Russ | Riesz transforms on graphs for 1 ≤ p ≤ 2[END_REF]. In both cases, the proofs go through the L 1 case. More precisely, it is shown that the Riesz transforms are bounded from L 1 to L 1,∞ , which gives the result by interpolation between L 1 and L 2 .

In the context of those two papers, it is not clear whether the Riesz transforms are bounded from H 1 to L 1 .

Concerning the H 1 -L 1 boundedness, a positive result is that, on manifolds with nonnegative Ricci curvature, the Riesz transforms are H 1 -L 1 bounded. This is shown by Bakry in [START_REF] Bakry | La propriété de sous-harmonicité des diffusions dans les variétés[END_REF] with a probabilistic definition for H 1 , and by Cheng and Luo in [START_REF] Chen | Duality of H 1 and BM O on positively curved manifolds and their characterization[END_REF], who consider the maximal H 1 space, defined by means of the heat kernel. Cheng and Luo strongly use the assumption about the Ricci curvature to get pointwise estimates about the heat kernel and show that the Riesz transforms are Calderon-Zygmund operators. They also prove that H 1 at , H 1 max and H 1 P (the probabilistic space considered by Bakry) coincide. The issue of the H 1 -H 1 boundedness of Riesz transforms has been investigated in IR n . In [START_REF] Stein | Singular integrals and differentiability properties of functions[END_REF], p.232, E. M. Stein proves that the Riesz transforms on IR n are H 1 -H 1 bounded. In [START_REF] Auscher | Square root problem for divergence operators and related topics[END_REF], P. Auscher and P. Tchamitchian show that the Riesz transform associated to an operator of the form -div(A∇) where A : IR n → M n (C) is a uniformly elliptic operator, is H 1 -H 1 bounded (Chapter 4, Proposition 10).

In the present paper, we prove the H 1 -L 1 boundedness in a geometric setting. Namely, we prove that Riesz transforms are H 1 -L 1 bounded on Riemannian manifolds and H 1 -L 1 bounded on graphs satisfying the doubling property and the Poincaré inequality. The result for manifolds encompasses Cheng and Luo's result, since, on complete Riemannian manifolds with non-negative Ricci curvature, the doubling property and the Poincaré inequality hold.

The basic fact used in the proof is the following result. Let (X, d, µ) be a space of homogeneous type, and T be a bounded linear operator on L 2 (X). Assume that there exists a measurable function k(x, y) (a kernel) such that, for any function f with compact support and almost all x outside the support of f , T f (x) = k(x, y)f (y)dµ(y).

If there exist two constants C and δ > 1 such that, for any y, y 0 ∈ X, d(x,y)≥δd(y0,y) |k(x, y) -k(x, y 0 )| dµ(x) ≤ C,

then T is H 1 at -L 1 bounded. The condition (1) is called the Hörmander integral condition. Since the Riesz transforms are L 2 -bounded and are given by a kernel k(x, y), it will be sufficient to show that k satisfies the Hörmander integral condition [START_REF] Auscher | Square root problem for divergence operators and related topics[END_REF]. The main result used to prove that is the Hölder regularity for solutions of the heat equation, which is a consequence of the parabolic Harnack principle, shown by L. Saloff-Coste in [START_REF] Saloff-Coste | Parabolic Harnack inequality for divergence form second order differential operators[END_REF] in the case of manifolds, and by T. Delmotte in [START_REF] Delmotte | Parabolic Harnack inequality and estimates of Markov chains on graphs[END_REF] in the case of graphs. Thus, we get that the Riesz transforms map continuously H 1 into L 1 .

The paper is made up as follows. First, we prove the H 1 -L 1 boundedness of Riesz transforms on complete Riemannian manifolds with the doubling property and the Poincaré inequality, which generalizes Bakry's and Chen and Luo's results.

Then, we give a local version of this result. Finally, we prove the H 1 -L 1 boundedness of Riesz transforms on graphs with the doubling property and the Poincaré inequality. The strategy is similar but the discrete setting creates some additional technical difficulties. I thank P. Auscher, T. Coulhon, X. T. Duong, E. M. Ouhabaz and F. Ricci for useful conversations and advice.

Part II

Preliminaries

Let X be a set equipped with a distance d and a positive measure µ. For x ∈ X and r > 0, denote by B(x, r) the open ball centered at x and of radius r and define V (x, r) = µ(B(x, r)). Assume that each ball has finite measure. Assume also that µ has the doubling property, which means that there exists C > 0 such that, for any x ∈ X and r > 0, V (x, 2r) ≤ CV (x, r).

Such a space is called a space of homogeneous type. An atom a on X is a function a : X → IR supported in a ball B and satisfying:

a(x)dµ(x) = 0, a ∞ ≤ 1 V (B) . (2)
A function f : X → IR is said to belong to H 1 at if there exist a sequence (λ n ) n∈IN ∈ l 1 and a sequence of atoms

(a n ) n∈IN such that f = n λ n a n
where the convergence is to be understood in the

L 1 sense. When f ∈ H 1 at , set f H 1 at = inf n |λ n | ,
the infimum being taken over all such decompositions of f . Let T be a bounded linear operator on L 2 (X). Assume that this operator is given by a kernel k(x, y), which means that there exists a measurable function k on X × X such that, for any function f with compact support and almost every x ∈ X outside the support of f ,

T f (x) = k(x, y)f (y)dµ(y).
One says that k satisfies the integral Hörmander condition if there exists C > 0 and δ > 1 such that, for any y and y 0 ∈ X,

d(x,y)≥δd(y0,y) |k(x, y) -k(x, y 0 )| dµ(x) ≤ C.
Then the following result holds: Theorem 1 Let (X, d, µ) be a space of homogeneous type and T a bounded linear operator on L 2 (X) given by a kernel k satisfying the integral Hörmander condition. Then there exists a constant C > 0 such that, for any atom a on X, T a 1 ≤ C. Hence, T can be extended to a bounded operator from H 1 at (X) to L 1 (X).

For a proof, see [START_REF] Coifman | Extensions of Hardy spaces and their use in analysis[END_REF], p. 599. When f is a function in L 1 loc (X) and B is a ball of X, define

f B = 1 V (B) f (x)dµ(x). Say that f ∈ L 1 loc (X) belongs to BM O(X) if sup B 1 V (B) B |f (x) -f B | dµ(x) < ∞
where the supremum is taken over all the balls B of X, and, if it is the case, set

f BM O = sup B 1 V (B) B |f (x) -f B | dµ(x).
An important property of BM O functions, which will be used later, is the fact that there exists C > 0 such that, for any f ∈ BM O(X) and any ball B of X,

1 V (B) B |f (x) -f B | 2 dµ(x) ≤ C f 2 BM O . (3)
As a consequence, there exists C > 0 such that, for any f ∈ BM O(X), any ball B of X and any integer k ≥ 0,

1 V (2 k B) 2 k B |f (x) -f B | 2 dµ(x) ≤ C(k + 1) 2 f 2 BM O . (4)
Actually, ( 3) is equivalent to the definition of BM O. For a proof of those facts, see, for instance, [START_REF] Coifman | Extensions of Hardy spaces and their use in analysis[END_REF], Theorem B. Once ( 3) is proved, it is easy to deduce (4). Indeed, consider the space 2 k B equipped with the measure

1 V (2 k B) µ and write that f -f B 2 ≤ k-1 i=0 f 2 i+1 B -f 2 i B 2 + f -f 2 k B ≤ Ck f BM O + C f BM O = C(k + 1) f BM O .
In the second line, the first term follows from the very definition of BM O, the second from (3). Thus, (4) is proved. Define V M O as being the closure of C 0 (X) (the space of all continuous functions on X with compact support) in BM O. Then, the following statement is true (see [START_REF] Coifman | Extensions of Hardy spaces and their use in analysis[END_REF], Theorem 4.1, p. 638):

Theorem 2 The dual of V M O is H 1 at . More precisely, if f ∈ H 1 at (X)
, the linear functional given by v → f vdµ, initially defined for v ∈ C 0 (X), has a unique bounded extension to V M O(X), with a norm equivalent to f H 1 at (X) . Moreover, every continuous linear functional on V M O(X) has this form. One can state a local version of Theorem 1. Say that X satisfies the local doubling property if

∀R > 0, ∃C R > 0, ∀x ∈ X, ∀r ∈ ]0, R[ , V (x, 2r) ≤ C R V (x, r). (5)
A local atom is a function a : X → IR supported in a ball B of radius ≤ 1 and satisfying [START_REF] Bakry | Etude des transformations de Riesz dans les variétés riemanniennes à courbure de Ricci minorée[END_REF]. A function f belongs to H 1,loc at if f = n λ n a n where (λ n ) n∈IN ∈ l 1 and the a n 's are local atoms. The H 1,loc at norm is defined as previously.

Consider an operator T bounded on L 2 (X). Assume that T is given by a kernel k(x, y). Say that k satisfies the local Hörmander integral condition if there exists a constant C > 0 such that, for any y, y 0 ∈ X with d(y, y 0 ) ≤ 1,

d(x,y)≥2d(y,y0) |k(x, y) -k(x, y 0 )| dµ(x) ≤ C.
Then the following statement is true: Theorem 3 Let (X, d, µ) be a metric space satisfying the local doubling property. Let T be an operator bounded on L 2 (X), given by a kernel k(x, y) satisfying the local integral Hörmander condition. Then, there exists a constant C > 0 such that, for any local atom a, T a 1 ≤ C. Therefore, T may be extended to a bounded operator from H 1,loc at (X) to L 1 (X). The proof is similar to the proof of Theorem 1.

Part III

The case of Riemannian manifolds 1 Statement of the main result

Let M be a complete Riemannian manifold, d the geodesic distance on M and µ the Riemannian measure on M . For x ∈ M and r > 0, denote by B(x, r) the geodesic ball centered at x and of radius r and by V (x, r) its volume.

Say that M satisfies the doubling property if and only if there exists a constant C > 0 such that, for any x ∈ M and any r > 0, V (x, 2r) ≤ CV (x, r).

This property implies that there exist two constants C vol > 0 and D > 0 such that, for any x ∈ M , r > 0 and

θ > 1, V (x, θr) ≤ C vol θ D V (x, r). (7)
Assume also that the Poincaré inequality holds on M , which means that

∀r > 0, ∀x ∈ M, B |f -f B | 2 dµ ≤ Cr 2 2B |∇f | 2 dµ (8)
for all f ∈ C ∞ (2B), where B = B(x, r), 2B = B(x, 2r) and f B is the mean of f over B defined by

f B = 1 V (B) B f.
Denote by ∆ the Laplace-Beltrami operator on M , by p t the heat kernel, i. e. the kernel of e -t∆ and by ∇ the Riemannian gradient. The definitions of an atom and of H 1 at (M ) are those of the previous section (notice that M is a space of homogeneous type). We intend to show the following result:

Theorem 4 Let M be a complete Riemannian manifold satisfying the doubling property and the Poincaré inequality. Then the Riesz transform T = ∇∆ -1 2 is bounded from H 1 at (M ) to L 1 (M ). Before proving that result, we give a few comments about it. One may define the space H 1 max (M ) in the following way. For f ∈ L 1 loc (M ), t > 0 and x ∈ M , define

P t f (x) = p t (x, y)f (y)dµ(y) and f + (x) = sup t |P t f (x)| . Say that f ∈ H 1 max (M ) if f + ∈ L 1 (M )
and, if it is the case, define

f H 1 max = f + 1 .
In [START_REF] Russ | H 1 -BM O duality on Riemannian manifolds[END_REF], the following statement is proved:

Theorem 5 Let M be a complete Riemannian manifold satisfying the doubling property and the Poincaré inequality. Then H 1 at (M ) = H 1 max (M ). Thus, Theorem 4 implies that the Riesz transform is bounded from H 1 max (M ) to L 1 (M ). Recall that, when M has nonnegative Ricci curvature, the assumptions of Theorem 4 hold. In this setting, D. Bakry has shown in [START_REF] Bakry | La propriété de sous-harmonicité des diffusions dans les variétés[END_REF], Proposition 5.3, that the Riesz transforms are bounded from H 1 P (the probabilistic Hardy space) to L 1 . Moreover, in [START_REF] Chen | Duality of H 1 and BM O on positively curved manifolds and their characterization[END_REF], Cheng and Luo prove, again on a manifold with nonnegative Ricci curvature, that they are bounded from H 1 max to L 1 , and that H 1 max = H 1 at = H 1 P . Recall also that a manifold which is roughly isometric to a manifold with non-negative Ricci curvature also satisfies the assumptions of Theorem 4 (see [START_REF] Coulhon | Variétés riemanniennes isométriques à l'infini[END_REF]). Finally, remember that a co-compact covering whose deck transformation group has polynomial growth also satisfies the assumptions of Theorem 4 (see [START_REF] Coulhon | Variétés riemanniennes isométriques à l'infini[END_REF]).

We are going to show Theorem 4. Since the Riesz transform is clearly L 2 -bounded and is given by a kernel k, it is sufficient, in view of Theorem 1, to show that k satisfies the integral Hörmander condition. To that aim, we first show estimates about some kernels which follow from the assumptions about M .

Kernel estimates

In what follows, we denote by p t the heat kernel. Moreover, if y and y 0 are two fixed points in M , define, for all x ∈ M , q t (x) = p t (x, y) -p t (x, y 0 ).

This section is devoted to various bounds on p t and q t . First, recall that, when ( 6) and ( 8) hold, one has the following estimates about p t (see [START_REF] Saloff-Coste | Parabolic Harnack inequality for divergence form second order differential operators[END_REF], Proposition 3.

3):

Lemma 6 There exist c 1 , c 2 , C 1 , C 2 > 0 such that, for all x, y ∈ M and all t > 0,

c 1 V (x, √ t) e -C 1 d 2 (x,y) t ≤ p t (x, y) ≤ C 2 V (x, √ t) e -c 2 d 2 (x,y) t .
As a consequence of the Gaussian upper bound in Lemma 6 and the doubling property ( 6), the following estimate is valid (see [START_REF] Coulhon | Riesz transforms for 1 ≤ p ≤ 2[END_REF], Lemma 2.3 and Lemma 2.4):

Lemma 7 For all γ ∈ ]0, 2c 2 [, there exists C γ > 0 such that, for any y ∈ M and any s > 0,

M |∇ x p s (x, y)| 2 e γ d 2 (x,y) s dµ(x) ≤ C γ V (y, √ s) s -1 .
Lemma 8 There exists β > 0 such that, for all y ∈ M and all s, t > 0, d(x,y)≥t

1 2 |∇ x p s (x, y)| dµ(x) ≤ Ce -β t s s -1 2 .
One also has the following estimate about q t : Lemma 9 There exist C 3 , c 3 > 0 and γ ∈ ]0, 1[ such that, for any t > 0 such that d(y 0 , y) ≤ √ t and any x ∈ M ,

|q t (x)| ≤ C 3 V (x, √ t) d(y, y 0 ) √ t γ exp(- c 3 d 2 (x, y) t ). ( 9
)
Lemma 9 is a straightforward consequence of the Hölderian regularity of solutions of the heat equation. Indeed, one has the following proposition (see [START_REF] Saloff-Coste | Parabolic Harnack inequality for divergence form second order differential operators[END_REF], Proposition 3.2):

Proposition 10 Let δ ∈ ]0, 1[. Then, there exist C > 0 and γ ∈ ]0, 1[ such that, given x ∈ M , s ∈ IR and r > 0, any solution u of ( ∂ ∂t + ∆)u = 0 in Q = s, s + r 2 × B(x, r) satisfies |u(t, x 1 ) -u(t, x 2 )| ≤ C d(x 1 , x 2 ) r γ u ∞,Q , where (t, x i ) ∈ s + δr 2 , s + r 2 × B(x, (1 -δ)r), i = 1, 2.
We apply Proposition 10 with δ = 1 8 . Indeed, assume that d(y 0 , y) ≤ √ t. Then, if r = 4 3 √ t and s = 4 9 t, one sees that d(y 0 , y) < (1 -δ)r and that s + δr 2 < t < s + r 2 . Fix x ∈ M and set u(t, z) = p t (x, z). Proposition 10 shows that

|p t (x, y) -p t (x, y 0 )| ≤ C d(y 0 , y) r γ sup (τ,z)∈Q p τ (x, z) ≤ C d(x, y) √ t γ sup (τ,z)∈Q p τ (x, z)
where

Q = 4 9 t, 20 9 t × B(y, 4 3 √ t). But Lemma 6 gives the following estimate: if (τ, z) ∈ Q, then p τ (x, z) ≤ c2 V (x, √ τ ) exp(-C2d 2 (x,z) τ ). When z ∈ B(y, 4 3 √ t), d(x, y) ≤ d(x, z) + 4 3 √ t, so that, since 2r 2 ≥ τ ≥ r 2 , one has p τ (x, z) ≤ c 2 V (x, √ t) exp(- C 2 d 2 (x, y) t ).
It follows that

|p t (x, y) -p t (x, y 0 )| ≤ C3 V (x, √ t) d(y,y0) √ t γ exp(- c 3 d 2 (x,y) t
).

Lemma 9 is proved. Fix y 0 and y in M . According to the previous lemma, if d(y, y 0 ) ≤ √ t,

|q t (x)| ≤ C 3 V (x, √ t) d(y, y 0 ) √ t γ e -c3 d 2 (x,y) t .
It is easy to deduce the following bound:

Lemma 11 If d(y 0 , y) ≤ √ t, then, for any α < 2c 3 , there exists C α > 0 such that |q t (x)| 2 exp α d 2 (x, y) t dµ(x) ≤ d(y 0 , y) √ t 2γ C α V (y, √ t) .
Indeed, making use of Lemma 9 and of assumption [START_REF] Coulhon | Variétés riemanniennes isométriques à l'infini[END_REF], one gets that

|q t (x)| 2 exp α d 2 (x, y) t dµ(x) ≤ d(y 0 , y) √ t 2γ C 2 3 V 2 (x, √ t) exp( (α -2c 3 )d 2 (x, y) t )dµ(x) ≤ d(y 0 , y) √ t 2γ C V 2 (y, √ t) exp( -c α d 2 (x, y) t )dµ(x) ≤ d(y 0 , y) √ t 2γ C α V (y, √ t) .
The estimate we will need in the following is a weighted L 2 estimate of the gradient of q t , namely:

Lemma 12 If d(y 0 , y) ≤ √ t, then, for any α < 2c 3 , there exists C α > 0 such that |∇ x q t (x)| 2 exp α d 2 (x, y) t dµ(x) ≤ 1 t d(y 0 , y) √ t 2γ C α V (y, √ t) .
In the proof of this Lemma, we follow closely [START_REF] Grigor'yan | Upper bounds of derivatives of the heat kernel on an arbitrary complete manifold[END_REF], p. 370. Let α be as in Lemma 12. Define ξ(x, t) = α d 2 (x, y) t and observe that, for almost every x ∈ M ,

∂ξ ∂t + 1 4α |∇ξ| 2 ≤ 0. ( 10
)
Set

f (t) = |∇ x q t (x)| 2 exp α d 2 (x, y) t dµ(x).
From now on, the variables t and x are not explicitly written. On the one hand, integrating by parts, one gets that f (t) = -qe ξ ∆q -q∇q.∇(e ξ ) and the Cauchy-Schwarz inequality shows that

f (t) ≤ q 2 e ξ 1 2
e ξ (∆q) 2

1 2 + e ξ (∇q.∇ξ) 2 1 2 . ( 11
)
On the other hand, computing the time derivative of f , one gets

f (t) = 2 e ξ ∇( ∂q ∂t ).∇q + ∂ξ ∂t e ξ |∇q| 2 ≤ 2 e ξ ∇(∆q).∇q - 1 4α e ξ |∇q| 2 |∇ξ| 2 = -2 e ξ (∆q) 2 -2 e ξ (∆q)(∇q.∇ξ) - 1 4α e ξ |∇q| 2 |∇ξ| 2 ≤ -2 e ξ (∆q) 2 + 2 e ξ (∆q) 2 1 2 e ξ |∇q| 2 |∇ξ| 2 1 2 - 1 4α e ξ |∇q| 2 |∇ξ| 2 . (12)
The second line follows from [START_REF] Grigor'yan | Upper bounds of derivatives of the heat kernel on an arbitrary complete manifold[END_REF], the third one by integration by parts. Squaring [START_REF] Russ | H 1 -BM O duality on graphs[END_REF], dividing it by c e ξ q 2 where c is a positive number which will be chosen later and adding to (12) leads to

f (t) + c f 2 (t) e ξ q 2 ≤ (-2 + c) e ξ (∆q) 2 + (2 + 2c) e ξ (∆q) 2 1 2 e ξ |∇q| 2 |∇ξ| 2 1 2 + (c - 1 4α ) e ξ |∇q| 2 |∇ξ| 2 . ( 13
) Choose c = 2-4α 1+16α : one obtains f (t) + c f 2 (t) e ξ q 2 ≤ 0. Define φ(t) = d(y, y 0 ) √ t 2γ C α V (y, √ t) ,
and, using Lemma 11, write that

f (t) f 2 (t) ≤ - c φ(t)
.

An integration on [0, t] implies that

f (t) ≤ 1 c t 0 du φ(u) . Since t 0 du φ(u) ≥ C t t 2 ( u d(y 0 , y) 2 ) γ V (y, √ u)du ≥ C t 2 ( t d(y 0 , y) 2 ) γ V (y, t 2
), one finally gets, using the doubling property, that

f (t) ≤ C α t ( d(y 0 , y) 2 t ) γ 1 V (y, √ t) .
Lemma 12 is therefore proved.

As an immediate consequence of this lemma, we get:

Lemma 13 There exists C > 0 and α > 0 such that, if d(y 0 , y) ≤ √ t, then, for any r 0 > 0,

d(x,y)≥r0 |∇ x q t (x)| dµ(x) ≤ C √ t d(y 0 , y) √ t γ e -α r 2 0 t .
Choose α < 2c 3 . Then, using Lemma 12, write that

d(x,y)≥r0 |∇ x q t (x)| dµ(x) ≤ |∇ x q t (x)| 2 exp α d 2 (x, y) t dµ(x) 1 2 d(x,y)≥r0 exp -α d 2 (x, y) t dµ(x) 1 2 ≤ C √ t ( d(y 0 , y) √ t ) γ 1 V (y, √ t) V (y, √ t)e -α 2 r 2 0 t ≤ C √ t ( d(y 0 , y) √ t ) γ e -α 2 r 2 0 t
which proves Lemma 13.

3

H 1 -L 1 boundedness
We prove that the Riesz transform maps continuously H 1 into L 1 . As in [START_REF] Coulhon | Riesz transforms for 1 ≤ p ≤ 2[END_REF], write that

∇∆ -1 2 = +∞ 0 ∇e -t∆ dt √ t .
This integral representation shows that T is given by the following kernel k:

k(x, y) = +∞ 0 ∇ x p t (x, y) dt √ t .
As was explained before, to get Theorem 4, we just have to check that k satisfies the integral Hörmander condition [START_REF] Auscher | Square root problem for divergence operators and related topics[END_REF]. Let y and y 0 be two fixed points in M . Then

d(x,y)≥2d(y0,y) |k(x, y) -k(x, y 0 )| dµ(x) ≤ +∞ 0 d(x,y)≥2d(y0,y) |∇ x [p t (x, y) -p t (x, y 0 )]| dµ(x) dt √ t = d 2 (y,y0) 0 d(x,y)≥2d(y0,y) |∇ x [p t (x, y) -p t (x, y 0 )]| dµ(x) dt √ t + +∞ d 2 (y,y0) d(x,y)≥2d(y0,y) |∇ x [p t (x, y) -p t (x, y 0 )]| dµ(x) dt √ t = I 1 + I 2 . ( 14
)
As for I 1 , write that

I 1 ≤ d 2 (y,y0) 0 d(x,y)≥2d(y0,y) |∇ x p t (x, y)| dµ(x) dt √ t + d 2 (y,y0) 0 d(x,y)≥2d(y0,y) |∇ x p t (x, y 0 )| dµ(x) dt √ t .
Lemma 8 ensures that there exists β such that d(x,y)≥2d(y0,y)

|∇ x p t (x, y)| dµ(x) ≤ Ce -4β d 2 (y 0 ,y) t t -1 2 .
Moreover, if d(x, y) ≥ 2d(y, y 0 ), then d(x, y 0 ) ≥ 1 2 d(y, y 0 ), so that, using Lemma 8 again, d(x,y)≥2d(y0,y)

|∇ x p t (x, y 0 )| dµ(x) ≤ d(x,y0)≥ 1 2 d(y0,y) |∇ x p t (x, y 0 )| dµ(x) ≤ Ce -β d 2 (y 0 ,y) 4t t -1 2 .
Finally, there exists α such that

I 1 ≤ C d 2 (y,y0) 0 e -α d 2 (y 0 ,y) t dt t = C 1 0 e -α t dt t ,
which is finite and does not depend on d(y 0 , y).

We now turn to I 2 . Using Lemma 13 and the fact that d(y, y 0 ) ≤ √ t, one has, for some β > 0,

I 2 = +∞ d 2 (y,y0) d(x,y)≥2d(y0,y) |∇ x q t (x)| dµ(x) dt √ t ≤ C +∞ d 2 (y,y0) d(y, y 0 ) √ t γ e -β d 2 (y,y 0 ) t dt t ≤ C +∞ 1 dt t 1+ γ 2 ,
which is also finite and independent of d(y 0 , y). Thus, k(x, y) satisfies the integral Hörmander condition and the Riesz transform maps continuously H 1 into L 1 . Theorem 4 is proved.

It should be noticed that the exponential term in Lemma 13 is not used to check that I 2 is finite, whereas the exponential term in Lemma 8 is essential to ensure that I 1 is finite.

Part IV

The case of Riemannian manifolds: a local theorem

In this part, we state and prove a result analogous to Theorem 4 with local assumptions about the manifold, instead of global ones.

Statement of the main result

Let M be a complete Riemannian manifold. Say that M satisfies the local doubling property if

∀R > 0, ∃C R > 0, ∀x ∈ M, ∀r ∈ ]0, R[ , V (x, 2r) ≤ C R V (x, r). ( 15
)
Say that M has at most exponential volume growth at infinity when

∃C, c > 0, ∀x ∈ M, ∀r ≤ 1, ∀θ > 1, V (x, θr) ≤ Ce cθ V (x, r). (16)
Finally, say that M satisfies the local Poincaré inequality if

∀R > 0, ∃C R > 0, ∀r ∈ ]0, R[ , ∀x ∈ M, ∀f ∈ C ∞ (B(x, 2r)), B |f -f B | 2 dµ ≤ C R r 2 2B |∇f | 2 dµ (17)
where B = B(x, r), 2B = B(x, 2r). We intend to show the following statement:

Theorem 14 Let M be a Riemannian manifold satisfying the local doubling property [START_REF] Stein | Singular integrals and differentiability properties of functions[END_REF], the local Poincaré inequality (17) and having at most exponential volume growth at infinity (which means (16)). Then there exists a constant C > 0 such that, for any f ∈ H 1,loc at ,

|∇f | 1 ≤ C ∆ 1 2 f H 1,loc at + f H 1,loc at .
It is important to notice the differences between the assumptions of Theorem 4 and Theorem 14. In Theorem 4, the doubling property and the Poincaré inequality are global, whereas they are local in Theorem 14. Since the doubling property is only local, we only consider local atoms, i. e. atoms supported in balls with smal radii. When M has Ricci curvature bounded below, the assumptions of Theorem 14 hold. In [START_REF] Bakry | Etude des transformations de Riesz dans les variétés riemanniennes à courbure de Ricci minorée[END_REF], Bakry shows that, when M has Ricci curvature bounded below, then, for any 1 < p < ∞, there exists C p > 0 such that, for any f ∈ C ∞ (M ) with compact support,

|∇f | p ≤ C p ∆ 1 2 f p + f p .
But this paper does not give any result about the H 1 -L 1 continuity. Note that this result is generalized for 1 < p ≤ 2 by Coulhon and Duong in [START_REF] Coulhon | Riesz transforms for 1 ≤ p ≤ 2[END_REF], Theorem 1.2, when M only has the local doubling property and a on-diagonal upper bound of the heat kernel for small time.

We shall work with the operator T = ∇(∆ + b) -1 2 where b > 0 will be chosen later. This operator, which is called the corrected Riesz transform, is used by Coulhon and Duong for the proof of Theorem 1.2 in [START_REF] Coulhon | Riesz transforms for 1 ≤ p ≤ 2[END_REF]. The local norm in Theorem 14, as well as in Theorem 1.2 in [START_REF] Coulhon | Riesz transforms for 1 ≤ p ≤ 2[END_REF], appears thanks to the parameter b (see [START_REF] Bakry | Etude des transformations de Riesz dans les variétés riemanniennes à courbure de Ricci minorée[END_REF], Lemme 4.2). It is clear that T is L 2 -bounded and is given by a kernel k(x, y). In view of Theorem 3, it is sufficient to prove that k satisfies the local Hörmander integral condition.

Kernel estimates

As before, for any fixed points y 0 , y ∈ M and any t > 0, define q t (x) = p t (x, y) -p t (x, y 0 ). Under the assumptions of Theorem 14, one has estimates about the heat kernel which correspond to those of the previous section. Namely, ( 15) and (17) imply the two following statement:

Lemma 15 There exist c 1 , C 1 , c 2 , C 2 > 0 such that, for all t < 1, all x ∈ M and every x 1 , x 2 ∈ B(x, 1),

c 1 V (x 1 , √ t) e -C1 d 2 (x 1 ,x 2 ) t ≤ p t (x 1 , x 2 ) ≤ C 2 V (x 1 , √ t) e -c2 d 2 (x 1 ,x 2 ) t .
This result is given in [START_REF] Saloff-Coste | Parabolic Harnack inequality for divergence form second order differential operators[END_REF], Proposition 3.3. Similarly to Lemma 9, one has the following result:

Lemma 16 There exist C 3 , c 3 and γ ∈ ]0, 1[ such that, for any t ∈ ]0, 1[ and any x, y, y 0 ∈ M satisfying d(y 0 , y) ≤ √ t,

|q t (x)| ≤ C 3 V (x, √ t) d(y 0 , y) √ t γ e -c3 d 2 (x,y) t .
This result is a consequence of Proposition 10 applied with R = 1.

From the previous estimates, one gets first the following result:

Lemma 17 For any β < 2c 3 , there exists C β > 0 such that, for any s > 0 and any y ∈ M satisfying d(y 0 , y) ≤ √ s,

|q s (x)| 2 e β d 2 (x,y) s dµ(x) ≤ φ(s)
where

φ(s) =            C γ V (y, √ s) d(y 0 , y) √ s 2γ if s ≤ 1, C γ V (y, 1) d(y 0 , y) 2γ if s ≥ 1.
When s ≤ 1, just use the upper bound given by Lemma 16. Then, observe that the map (s, x) -→ q s (x) = p s (x, y) -p s (x, y 0 ) is a solution of ∂ ∂s u + ∆u = 0, which implies that

|q s (x)| 2 e β d 2 (x,y) s dµ(x)
is non-increasing in s. This fact is a consequence of the following integral maximum principle (see [START_REF] Grigor'yan | Integral maximum principle and its applications[END_REF], Theorem 1.1):

Theorem 18 Suppose that u is a solution of ∂ ∂s u + ∆u = 0. Then the function

I(t) = M u 2 (x, t)e ξ(x,t) dµ(x)
is non-increasing, provided that the function ξ(x, t) is locally Lipschitz and satisfies the relation

∂ξ ∂t + 1 2 |∇ξ| 2 ≤ 0.
Therefore, one has the claimed estimate for s ≥ 1.

We are now going to show the following upper bound:

Lemma 19 For any β < c 3 , there exists C β > 0 such that, for any s > 0 satisfying d(y 0 , y) ≤ √ s,

|∇ x q s (x)| 2 e β d 2 (x,y) s dµ(x) ≤ ψ(s)
where

ψ(s) =            C β sV (y, √ s) d(y 0 , y) √ s 2γ if s ≤ 1, C β sV (y, 1) d(y 0 , y) 2γ if s ≥ 1.
Doing the same computations as in the proof of Lemma 12, one gets that, for any s > 0,

|∇ x q s (x)| 2 e β d 2 (x,y) s dµ(x) ≤ C s 0 du φ(u)
.

But, when s ≤ 1, one has Finally, this lemma implies the following:

Lemma 20 There exists β > 0 such that, for any s > 0 satisfying d(y, y 0 ) ≤ √ s,

d(x,y)>r0 |∇ x q s (x)| dµ(x) ≤ χ(s) √ s e -β r 2 0 s ds
where the function χ is defined by

χ(s) =        C d(y 0 , y) √ s γ if s ≤ 1, Cd(y 0 , y) γ e cs if s ≥ 1.
One uses the Cauchy-Schwarz inequality like in the proof of Lemma 13, in conjunction with the assumption (16).

H 1,loc -L 1 boundedness

As said before, following [START_REF] Coulhon | Riesz transforms for 1 ≤ p ≤ 2[END_REF], we consider, for some b > 0, the operator T = ∇(∆ + b) -1 2 and intend to prove that it is H 1,loc at -L 1 bounded. It is given by the kernel

k(x, y) = +∞ 0 e -tb √ t ∇ x p t (x, y)dt.
We want to show that this kernel satisfies the local integral Hörmander condition. Let y and y 0 be two fixed points in M satisfying d(y 0 , y) ≤ 1. Write that

I = d(x,y)≥2d(y,y0) |k(x, y) -k(x, y 0 )| dµ(x) ≤ +∞ 0 e -tb √ t d(x,y)≥2d(y,y0) |∇ x p t (x, y) -∇ x p t (x, y 0 )| dµ(x)dt = d 2 (y,y0) 0 e -tb √ t d(x,y)≥2d(y,y0) |∇ x p t (x, y) -∇ x p t (x, y 0 )| dµ(x)dt + 1 d 2 (y,y0) e -tb √ t d(x,y)≥2d(y,y0) |∇ x p t (x, y) -∇ x p t (x, y 0 )| dµ(x)dt + +∞ 1 e -tb √ t d(x,y)≥2d(y,y0) |∇ x p t (x, y) -∇ x p t (x, y 0 )| dµ(x)dt = I 1 + I 2 + I 3 .
Remember that d(y, y 0 ) ≤ 1. As for I 1 , the triangular inequality shows that

I 1 ≤ C d 2 (y,y0) 0 e -tb √ t d(x,y)≥2d(y,y0) |∇ x p t (x, y)| dµ(x)dt + d 2 (y,y0) 0 e -tb √ t d(x,y)≥2d(y,y0) |∇ x p t (x, y 0 )| dµ(x)dt ≤ C d 2 (y,y0) 0 e -tb √ t dt √ t e -β d 2 (y,y 0 ) t ≤ C d 2 (y,y0) 0 dt t e -β d 2 (y,y 0 ) t = C 1 0 dt t e -β t
which is finite and independent of y and y 0 . Then,

I 2 ≤ C 1 d 2 (y,y0) e -tb √ t dt t e -β d 2 (y,y 0 ) t d(y, y 0 ) √ t γ = C 1 d 2 (y,y 0 ) 1 e -tbd 2 (y,y0) t 1+ γ 2 e -β t dt ≤ +∞ 0 e -β t dt t 1+ γ 2
which is also finite and does not depend on the points y, y 0 . Finally,

I 3 ≤ +∞ 1 e -tb √ t dt √ t d(y 0 , y) γ e -β 4d 2 (y,y 0 ) t e ct ≤ +∞ 1 e -tb t dt
which is finite and independent of y and y 0 . In the last line, one has to choose b larger than 2c and to use the fact that d(y, y 0 ) ≤ 1. Thus, the kernel k satisfies the local Hörmander integral condition, which proves that T is H 1,loc at -L 1 bounded.

Part V The case of graphs 1 Statement of the main result

Let Γ be an infinite connected graph, endowed with its natural metric and a symmetric weight µ xy = µ yx on Γ × Γ. Assume that x and y are neighbours if and only if µ xy = 0. Define, for every x ∈ Γ,

m(x) = y∼x µ xy .
For every real r ≥ 0, the ball B(x, r) is defined as follows:

B(x, r) = {y ∈ Γ; d(y, x) ≤ r} , and, if A is a subset of Γ, its volume is V (A) = x∈A m(x).
When A is a ball B(x, r), V (A) will be denoted by V (x, r).

The graph Γ is said to satisfy the doubling property if there exists a constant C > 0 such that, for every x ∈ Γ and r > 0

V (x, 2r) ≤ CV (x, r). ( 18
)
Note that this property implies that there exist two constants C vol > 0 and D > 0 such that, for any x ∈ Γ, θ > 1 and r > 0,

V (x, θr) ≤ C vol θ D V (x, r). (19)
The graph Γ is said to satisfy the Poincaré inequality if there exists a constant C > 0 such that, for every function f from Γ to IR, every x 0 ∈ Γ and r > 0, one has

x∈B(x0,r) m(x) |f (x) -f B | 2 ≤ Cr 2
x,y∈B(x0,2r)

µ xy |f (x) -f (y)| 2 , (20)
where

f B = 1 V (x 0 , r) x∈B(x0,r) m(x)f (x).
Finally, one says that Γ satisfies ∆(α) for α > 0 if the two following conditions hold:

x ∼ y ⇒ µ xy ≥ αm(x), ∀x ∈ Γ, µ xx ≥ αm(x).
Denote by f p the L p norm of a function f , that is to say

f p = x |f (x)| p m(x) 1 p
.

One may then consider on Γ a discrete-time Markov kernel. Set

p(x, y) = µ xy m(x)
and define the iterated kernel p k as follows:

p 0 (x, y) = δ(x, y), p k (x, y) = z p(x, z)p k-1 (z, y).
The definition of an atom and of the space H 1 at is given in the first section (note that Γ is a space of homogeneous type).

The gradient of a function f is defined by

∇f (x) = y∼x |f (y) -f (x)|
where x ∼ y means that y is a neighbour of x.

Define the linear operator P by P f (

and notice that

P k f (x) = y p k (x, y)f (y).
One easily checks that P is self-adjoint on L 2 (Γ, m(x)). The Riesz transform T is defined as

T = ∇(I -P ) -1 2 ,
where the unbounded linear operator (I -P ) -1 2 is defined by means of spectral theory. We intend to show the following result:

Theorem 21 Let Γ be an infinite graph satisfying the doubling property and the Poincaré inequality. Then, the Riesz transform is bounded from H 1 at (Γ) to L 1 (Γ). One can define the space H 1 max in the following way. If f ∈ L 1 (Γ), set

f + (x) = sup k P k f (x)
and say that f ∈ H 1 max if and only if

f + ∈ L 1 . If it is the case, define f H 1 max = f + 1 .
The following statement is shown in [START_REF] Russ | H 1 -BM O duality on graphs[END_REF]:

Theorem 22 Let Γ be a graph satisfying the doubling property, the Poincaré inequality and the condition ∆(α).

Then H 1 at (Γ) = H 1 max (Γ). Therefore, Theorem 21 shows that the Riesz transform is bounded from H 1 max (Γ) to L 1 (Γ). To prove Theorem 21, since the Riesz transform is L 2 -bounded and is given by a kernel k(x, y), we only have to check that this kernel satisfies the Hörmander integral condition, which requires some estimates about kernels.

Kernel estimates

Fix y 0 and y in Γ. For any k ∈ IN and x ∈ Γ, define

q k (x) = p k (y, x) -p k (y 0 , x) m(x) .
This section is devoted to various bounds about p k and q k . Recall that, when (18) and (20) hold, one has the following estimate about p k :

Theorem 23 Let Γ satisfy the doubling property, the Poincaré inequality and ∆(α) for α > 0. Then, there

exist c 1 , C 1 , c 2 , C 2 > 0 such that d(x, y) ≤ k ⇒ c1m(y) V (x, √ k) e -C 1 d(x,y) 2 k ≤ p k (x, y) ≤ C2m(y) V (x, √ k) e -c 2 d(x,y) 2 k .
This theorem is shown by T. Delmotte in [START_REF] Delmotte | Parabolic Harnack inequality and estimates of Markov chains on graphs[END_REF], Theorem 1.7.

As a consequence of the Gaussian upper bound in Lemma 23 and of the doubling property (18), one gets the following upper bounds (see Lemma 7 and Lemma 2 in [START_REF] Russ | Riesz transforms on graphs for 1 ≤ p ≤ 2[END_REF]):

Lemma 24 For all γ ∈ ]0, c 1 [, there exists C γ > 0 such that y |∇ y p k (y, x)| 2 e γd 2 (x,y) k m(y) ≤ C γ m 2 (x) kV (x, √ k) .
Lemma 25 There exists β > 0 such that, for any

x ∈ Γ, l ∈ IN, k ∈ IN * , y / ∈B(x, √ l) |∇ y p k (y, x)| m(y) ≤ Cm(x)e -βl k k -1 2 .
T. Delmotte also shows that the solutions of m(x)u(n + 1, x) =

n ∈ Z Z ∩ n 0 -R 2 , n 0 , then |u(n, x 1 ) -u(n, x 2 )| ≤ C d(x 1 , x 2 ) R h sup Q |u| .
As a consequence of Theorem 23 and of Proposition 26, one has the following estimate about q k :

Lemma 27 There exists C 3 , c 3 > 0 and h ∈ ]0, 1[ such that, for any k ∈ IN, x, y, y 0 ∈ Γ such that d(y 0 , y) ≤ √ k,

|q k (x)| ≤ C 3 V (x, √ k) d(y, y 0 ) √ k h e -c3 d 2 (y 0 ,x) k .
Assume first that d(y, y 0 ) ≤ 1 2 √ k and that x ∈ Γ. Proposition 26 may be applied to

u(k, z) = p k (z, x), with R ∼ 1 2 √
k and n 0 ∼ 5 4 k. Since y ∈ B(y 0 , R) and k ∈ Z Z ∩ n 0 -R 2 , n 0 , one gets:

|p k (y, x) -p k (y 0 , x)| ≤ C d(y, y 0 ) R h sup Q p l (z, x) where Q = (Z Z ∩ n 0 -2R 2 , n 0 ) × B(y 0 , 2R).
But, thanks to Theorem 23, when n 0 -2R 2 ≤ l ≤ n 0 and z ∈ B(y 0 , 2R),

p l (z, x) ≤ C 2 m(x) V (x, √ l) e -c 2 d 2 (x,z) l ≤ C 2 m(x) V (x, √ n 0 -2R 2 ) e -c 2 d 2 (x,z) n 0 .
One has

- d 2 (x, z) n 0 ≤ - d 2 (x, y 0 ) 2n 0 + d 2 (y 0 , z) n 0 ≤ - d 2 (x, y 0 ) 2n 0 + 4, so that p l (z, x) ≤ C 3 m(x) V (x, √ k) e -c 2 d 2 (y 0 ,x) k .
It follows that Therefore, the following bound holds:

|p k (y, x) -p k (y 0 , x)| ≤ C 4 d(y, y 0 ) √ k h m(x) V (x, √ k) e -c 2 d 2 (y 0 ,x) k . (21)
Lemma 28 If d(y 0 , y) ≤ √ k, then, for any α < 2c 3 , there exists C α > 0 such that

x |q k (x)| 2 exp α d 2 (x, y) k m(x) ≤ d(y 0 , y) √ k 2h C α V (y, √ k) .
The proof is similar to Lemma 11. We intend to show the following estimate, which is the discrete equivalent of Lemma 12 (see also the analogous estimate in [START_REF] Russ | Riesz transforms on graphs for 1 ≤ p ≤ 2[END_REF], Lemma 7):

Lemma 29 For any k ∈ IN * satisfying d(y, y 0 ) ≤ √ k and any γ < c 3 ,

x |∇ x q k (x)| 2 exp γ d 2 (y, x) k m(x) ≤ C γ kV (y, √ k) d(y, y 0 ) √ k 3h 2
.

The main step in the proof of this lemma is the following temporal estimate:

Lemma 30 For any x ∈ Γ, any k ∈ IN * satisfying d(y, y 0 ) ≤ √ k, |q k+1 (x) -q k (x)| ≤ C kV (y, √ k) d(y, y 0 ) √ k h 2 .
To begin the proof, notice that, for any k ∈ IN * , one has

q k+1 = P q k . Indeed, if x ∈ Γ, [P q k ] (x) = z p(x, z)q k (z) = z p(x, z) p k (y, z) -p k (y 0 , z) m(z) = 1 m(x) z p(z, x) [p k (y, z) -p k (y 0 , z)] = 1 m(x)
[p k+1 (y, x) -p k+1 (y 0 , x)] = q k+1 (x).

Let l be an integer satisfying l ∼ k 2 . One has

|q k+1 (x) -q k (x)| = z p l (x, z) [q l+1 (z) -q l (z)] = z p l (x, z) m(z) [q l+1 (z) -q l (z)] m(z) ≤ p l (x, .) m 2 q l+1 -q l 2 . But p l (x, .) m 2 2 = z p l (x, z)p l (x, z) m(z) = z p l (x, z) p l (z, x) m(x) = p k (x, x) m(x) ≤ C V (x, √ k) . Moreover, if m ∼ l 2 , then q l+1 -q l 2 = (I -P )P m q m 2 ≤ (I -P )P m 2→2 q m 2 ≤ C l q m (y, .) 2 . ( 22
)
The last line follows from Lemma 6 in [START_REF] Russ | Riesz transforms on graphs for 1 ≤ p ≤ 2[END_REF], which we recall here:

Lemma 31 One has (I -P ) p k (x,.)

m 2 ≤ C kV 1 2 (x, √ k)
.

Recall that Lemma 31 is a straightforward consequence of the condition ∆(α), which implies that -1 / ∈ Sp(P ).

From the fact that

q m 1 = x |q m (x)| m(x) ≤ x p m (y, x) + x p m (y 0 , x) = 2
and that

q m ∞ = sup x |p m (y, x) -p m (y 0 , x)| m(x) ≤ C V (y, √ m) d(y, y 0 ) √ m h , we may conclude that q m 2 ≤ q m 1 2 1 q m 1 2 ∞ ≤ C V 1 2 (y, √ m) d(y, y 0 ) √ m h 2 .
It follows from ( 22) that

q l+1 -q l 2 ≤ C lV 1 2 (y, √ l) d(y, y 0 ) √ l h 2
and finally that

|q k+1 (x) -q k (x)| ≤ C kV 1 2 (y 0 , √ k)V 1 2 (y, √ k) d(y, y 0 ) √ k h 2 ≤ C V (y, √ k) d(y, y 0 ) √ k h 2 .
In the last line, we use the fact that d(y, y 0 ) ≤ √ k and the doubling property. Thus, Lemma 30 is proved. Let us deduce Lemma 29 from Lemma 30. The following computations are inspired from those which give Lemma 7 in [START_REF] Russ | Riesz transforms on graphs for 1 ≤ p ≤ 2[END_REF]. Write that

x∼z |q k (x) -q k (z)| 2 e γ d 2 (y,x) k m(x) ≤ C d(x,z)≤1 |q k (x) -q k (z)| 2 m(x)p(x, z)e γ d 2 (y,x) n = CI k . (23)
From now on, we will work with I k .

I k = d(x,z)≤1 q k (x) [q k (x) -q k (z)] m(x)p(x, z)e γ d 2 (y,x) k - d(x,z)≤1 q k (z) [q k (x) -q k (z)] m(x)p(x, z)e γ d 2 (y,x) k = d(x,z)≤1 q k (x) [q k (x) -q k (z)] m(x)p(x, z)e γ d 2 (y,x) k + d(x,z)≤1 q k (x) [q k (x) -q k (z)] m(x)p(x, z)e γ d 2 (y,z) k . 20
In the last line, we inverted x and z and we used the reversibility of p with respect to m. Hence, we get that

I k ≤ 2 x∼z q k (x) [q k (x) -q k (z)] m(x)p(x, z)e γ d 2 (y,x) k + x∼z q k (x) [q k (x) -q k (z)] m(x)p(x, z) e γ d 2 (y,z) k -e γ d 2 (y,x) k = 2I (1)
k + I

k .

The previous upper bounds allow to estimate I

k . Indeed, I

= x q k (x)e γ d 2 (y,x) k m(x) z p(x, z) [q k (x) -q k (z)] = x q k (x)e γ d 2 (y,x) k m(x) [q k (x) -q k+1 (x)] (1) k
hence, thanks to Lemma 30, I

≤ C kV (y, √ k) d(y, y 0 ) √ k h 2 x |q k (x)| e γ d 2 (x,y) k m(x) ≤ C kV (y, √ k) d(y, y 0 ) √ k 3h 2 x 1 V (x, √ k) e (γ-c3) d 2 (y,x) k m(x) ≤ C γ kV 2 (y, k) d(y, y 0 ) √ k 3h 2 y e (γ -α) d 2 (x,y) k m(x) ≤ C γ kV (y, √ k) d(y, y 0 ) √ k (1) k
I (2) k ≤ 2γ k d(x,z)≤1 m(x)p(x, z) |q k (x)| |q k (x) -q k (z)| [d(x, y) + 1] e γ k [d(y,x)+1] 2 = 2 γ k d(x,z)≤1 m(x)p(x, z) |q k (x)| |q k (x) -q k (z)| γ k [d(y, x) + 1] 2 e γ k [d(x,y)+1] 2 ≤ 2 γ k d(x,z)≤1 m(x)p(x, z) |q k (x)| |q k (x) -q k (z)| e γ k [d(y,x)+1] 2 ≤ 2 γ k   d(x,z)≤1 m(x)p(x, z) [q k (x)] 2 e γ k [d(y,x)+1] 2   1 2   d(x,z)≤1 m(x)p(x, z) |q k (x) -q k (z)| 2 e γ k [d(y,x)+1] 2   1 2 . But γ k [d(y, x) + 1] 2 = γ k d 2 (y, x) + 2d(y, x) + 1
and, in the sums which define I k , we may assume that d(y, x) ≤ 2k + 1 and that d(y, z) ≤ 2k + 1, otherwise, since d(x, z) ≤ 1, we obtain d(y, x) > 2k + 1 and d(y, z) > 2k + 1. Then, p k (y, x) = p k (y, z) = 0. Moreover, since d(y 0 , y) < κ √ k, one has d(y 0 , x) > k and d(y 0 , z) > k, and p k (y 0 , x) = p k (y 0 , z) = 0. All that implies q k (x) = q k (z) = 0, and the corresponding terms do not appear in the sum which defines I k . 3 H 1 -L 1 boundedness

We want to prove Theorem 21. Like in [START_REF] Russ | Riesz transforms on graphs for 1 ≤ p ≤ 2[END_REF], write that

∇(I -P ) -1 2 = ∞ k=0 a k ∇P k
where the a k 's are defined by which is finite and independent of the points y, y 0 . Thus, the kernel r satisfies the integral Hörmander condition and we have proved that the Riesz transform is H 1 -L 1 bounded. Theorem 21 is proved. Like in the setting of manifolds, notice that the exponential term in Lemma 32 is not really used, but that getting it is easy.

yµ

  xy u(n, y) satisfy a Hölder regularity property (see Proposition 4.1 in [8]): Proposition 26 There exists h > 0 and C > 0 such that, for all x 0 ∈ Γ, n 0 ∈ Z Z and R ∈ IN, if u is a solution of m(x)u(n + 1, x) = y µ xy u(n, y) on Q = (Z Z ∩ n 0 -2R 2 , n 0 ) × B(x 0 , 2R), x 1 , x 2 ∈ B(x 0 , R) and

Finally, if 2 √ 2 √

 22 d(y, y 0 ) ≤ √ k, consider a point y 1 such that d(y, y 1 ) ≤ 1 k and d(y 1 , y 2 ) ≤ 1 k, and apply (21) to |p k (y, x) -p k (y 1 , x)| and to |p k (y 1 , x) -p k (y 0 , x)|. Lemma 27 is shown.

2 . 2 .

 22 Note that, in this computation, it is possible to choose γ ∈ ]γ, c 3 [ because γ < c 3 .As for I 2 , if we denote by f the map defined byf (x) = e γ k x 2we may write, according to the mean-value theorem, that|f (b) -f (a)| ≤ 2γ k |b -a| (sup a, b)e γ k (sup a,b) Applying this inequality with a = d(y, x), b = d(y, z) when d(x, z) ≤ 1, so that |d(y, x) -d(y, z)| ≤ 1, we get, if we notice that sup(a, b) ≤ a + 1, that

4 V

 4 get the right estimate for I k , hence Lemma 29 by (23). Thanks to Lemma 29, we can finally show the following Lemma: Lemma 32 There exist C > 0 and α > 0 such that, for any x, y 0 , y ∈ Γ, any k ∈ IN * satisfying d(y 0 , y) < κ √ k and any l ∈ IN * , d(x,y)≥l|∇ x q k (x)| m(x) just have to write that, if α < c3 2 , x∼z,d(y,x)≥l |q k (x) -q k (z)| m(x) ≤   x∼z,d(y,x)≥l |q k (x) -q k (z)| 2 e 2α d 2 (y,x) (y, √ k)e -αl 2 2kwhich is Lemma 32 (one may apply Lemma 29 because 2α ∈ ]0, c 3 [).

( 1 -= S 1 + S 2 . 1 √κ 2 a k e -α d 2 1 √ 2

 11212212 x) -1 2 = ∞ k=0 a k x k .Thus, T is given by the kernelr(x, y) = ∞ k=0 a k ∇p k (x, y) m(y)(24)and we are going to prove that this kernel satisfies the integral Hörmander condition. Let y and y 0 be two fixed points in Γ. One hasd(x,y)≥2d(y0,y) |r(x, y) -r(x, y 0 )| m(x) ≤ ∞ k=0 a k d(x,y)≥2d(y0,y) ∇ x p k (x, y) m(y) -∇ x p k (x, y 0 ) y)≥2d(y0,y) ∇ x p k (x, y) m(y) -∇ x p k (x, y 0 ) m(y 0 ) m(x)One estimates S 1 in the same way as I 1 in (14), by means of the triangle inequality and Lemma 25 instead of Lemma 8. Also using the fact that a k ∼ and independent of the points y and y 0 . The treatment of S 2 is completely similar to the one of I 2 in[START_REF] Saloff-Coste | Parabolic Harnack inequality for divergence form second order differential operators[END_REF]. Just use Lemma 32, applied withq k (x) = p k (x, y) m(y) -p k (x, y 0 ) m(y 0 ) ,instead of Lemma 13. Using the fact that a k ∼ πk again, one finds that S


Cazabet Remy
email: remy.cazabet@gmail.com

Baccour Rym

Latapy Matthieu

Tracking bitcoin users activity using community detection on a network of weak signals

Bitcoin is a cryptocurrency attracting a lot of interest both from the general public and researchers. There is an ongoing debate on the question of users' anonymity: while the Bitcoin protocol has been designed to ensure that the activity of individual users could not be tracked, some methods have been proposed to partially bypass this limitation. In this article, we show how the Bitcoin transaction network can be studied using complex networks analysis techniques, and in particular how community detection can be efficiently used to re-identify multiple addresses belonging to a same user.

Introduction

Bitcoin is a cryptocurrency, a digital currency using a technology called blockchain to maintain a public distributed ledger. Bitcoin is decentralized, i.e. there is no central authority. Instead, any peer can consult the distributed ledger at any time to check the amount of b itcoin controlled by each address, which is in fact a public key.

The bitcoin protocol therefore has to solve a difficult problem: on the one hand, one should not be able to track individual users' activity, while, on the other hand, all transactions must be public. This problem is partially solved by the possibility for users to use as many addresses as they want. As a consequence, a same user can use a different address each time he receives a payment, and observers cannot, in theory, associate these different addresses to the single user that control them.

In practice, however, previous works have shown that it is possible, using some simple heuristics, to re-identify several addresses belonging to the same user.

In this article, we show how community detection, a well-known network analysis technique, can be used to improve on these simple heuristics to better re-identify users.

In section 2, we introduce key elements of the Bitcoin transaction system, necessary to understand how re-identification is made possible. In section 3, we present existing heuristics for user re-identification, while section 4 introduces our method based on community detection. In section 5, we propose a framework to empirically assess the quality of re-identification heuristics, and compare the proposed method to existing ones.

Bitcoin transaction definition

To explain how re-identification techniques are made possible, it is first necessary to explain some key elements on how the Bitcoin cryptocurrency works. In this article, we will not describe all details of the blockchain and Bitcoin protocol, but only relevant information for the task of user re-identification. For more details on the protocol, one can refer to [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF][START_REF] Garay | The bitcoin backbone protocol: Analysis and applications[END_REF][START_REF] Kosba | Hawk: The blockchain model of cryptography and privacy-preserving smart contracts[END_REF].

Bitcoin users can exchange amounts through transactions, recorded in a public ledger, the blockchain. These transactions are characterized by:

• m outputs, each associated with:

-A bitcoin amount -A public key (address)

• n inputs, each corresponding to the output of a previous transaction (thus indirectly to its bitcoin amount and public key) • A time stamp, which is an approximate value (due to the distributed nature of the blockchain, the timestamp is not exact, and in some cases, a transaction can take as input the output of a transaction with a later timestamp.

The sum of the inputs of a transaction is equal to the sum of the outputs plus an optional transaction fee.

Each address, which is in fact a public key, is associated with a private key. Both of them have been generated by the same user, and, while the public key is publicly shared, the pivate key is kept secret. To spend the bitcoins received at an address, its owner must "unlock" it by using its private key, as defined by the encryption protocol.

At this point, it is necessary to point out some important consequences of this mechanism:

• The balance of a user u at time t is the sum of all transaction outputs that can be unlocked by a private key owned by u, and that have not yet been unlocked (i.e. spent) at time t. • If two transactions T 0 and T 1 have the same address d among their outputs, with respective associated amounts a 1 and a 2 , these amounts are not merged or associated in any manner, i.e. there is no entity corresponding to the address d that controls, or contains, a 2 + a 1 bitcoins. Instead, these two outputs are uniquely identified respectively as output m 0 of transaction T 0 and output m 1 of transaction T 1 , and each of these outputs can independently be used as input of a new transaction. Their only common trait is that they can be unlocked using the same private key, therefore by the same user. • There is no partial spending: if a user who controls an output o 1 corresponding to x bitcoins use it as input of a transaction to send y bitcoins to another user, with y < x, then the user must send back xy bitcoins to an address that he/she controls. • Users need to create multiple-input transactions each time they need to pay an amount superior to the value of each individual output they control.

Existing re-identification heuristics

Several works have tackled the problem of users re-identification. In this section, we will describe heuristics based on transactions present in the public ledger. Some other methods exist, using IP-addresses collected in real time while transactions occur [START_REF] Biryukov | Deanonymisation of clients in bitcoin p2p network[END_REF] or global activity patterns for very active users [START_REF] Monaco | Identifying bitcoin users by transaction behavior[END_REF]. One can refer to [START_REF] Lischke | Analyzing the bitcoin network: The first four years[END_REF] for a recent survey on such methods. Methods based on the public ledger are the most common ones. They have the advantage of being based on data easily accessible to anyone.

Heuristic based on transaction inputs only

A first heuristic for re-identification has been introduced in [START_REF] Reid | An analysis of anonymity in the bitcoin system[END_REF]: because all private keys corresponding to addresses must be used conjointly to sign a transaction, it can be safely assumed that all addresses in the input of a transaction belong to the same user. The introduction of the multisig protocol in 2013 does not dramatically change this observation: it allows an output to be controlled by several users (all users must use their private key to sign), but does not allow to use conjointly outputs that were initially detained privately by different users. Furthermore, these conjointly detained addresses are identified differently from normal ones, and are scarcely used (as of 2017).

This heuristic can be defined as:

Heuristic H 1 All addresses used as input of the same transaction belong to the same controlling entity, called a User.

A simple network algorithm can be used to discover these users efficiently:

1. Create a network with nodes representing addresses 2. For each set of n addresses used conjointly as input of a transaction, add n -1 edges to create a path between them 3. Discover connected components of this network.

Connected components of this network correspond to sets of addresses belonging to a same user.

Despite the simplicity of this heuristic, it gives good results in practice, because users often have to use conjointly different addresses in order to perform transactions. Some users also tend to reuse the same addresses multiple times, either because they are not aware of the tracking possibility it allows, or because it is more convenient for them. For instance, the organization Wikileaks has an official address to which anyone can donate, therefore this address is used every time someone makes a donation to this organization. It is therefore possible to track how much money this organization receives through donations to this public address.

There is debate on the efficacy of this heuristic. Interested readers can refer to [START_REF] Harrigan | The unreasonable effectiveness of address clustering[END_REF] for a discussion on why this method gives good results in most cases.

Heuristics based on inputs and outputs of transactions

H1 can only associate addresses because they simultaneously appear in the input of a transaction. Another property of bitcoin is that, because users cannot do partial spending, they have to send back to themselves the difference between the sum of inputs and the amount to pay. To improve the user discovery process, one needs to associate input addresses with one -or several-output addresses that belong to the same user, called change address, or shadow address. Several authors have proposed heuristics to discover which output address might be a change address.

Existing heuristics are searching for so-called one-time change address. Indeed, it is a common practice to receive the change on a newly generated address, that is never to be reused.

Androulaki et al. [START_REF] Androulaki | Evaluating user privacy in bitcoin[END_REF] proposed the following heuristic to discover one-time change addresses: Heuristic H 2 If there are exactly two output-addresses a1 and a2, that one of them (a1) appears for the first time and that the other (a2) has appeared before, then a1 is considered to be the change address. This heuristic has also been used in [START_REF] Spagnuolo | Bitiodine: Extracting intelligence from the bitcoin network[END_REF].

Meiklejohn et al. [START_REF] Meiklejohn | A fistful of bitcoins: characterizing payments among men with no names[END_REF] propose a variation of this heuristic, not limited to transactions with exactly 2 outputs:

Heuristic H 3 An address is considered a one-time change address if it satisfies the following properties:

• The transaction is not a coin generation • The address is not among the input addresses (address reuse) • It is the only output address appearing for the first time

In their article, by using known addresses of several users as a reference, the authors are able to identify incorrectly grouped addresses, and propose a list of ad hoc restrictions to consider an address as a one-time change address, that involves checking if the address is not reused later, or reused only by some special services such as gambling games, that send their payout to the change address of the payment they received. The authors point out that these restrictions are only based on empirical observations, and cannot be generalized for future transactions.

A simple adaptation of the network algorithm described for H1 can be used for H2 and H3: a network is created as for H1, and an edge is added between each identified one-time change address and one of the corresponding input addresses. Connected components of this graph correspond to set of addresses controlled by the same user.

We can observe that there is a hierarchical relation between H1 and H2, H3: each user of H2, H3 corresponds exactly to one or several users in H1.

A more in-depth description of these approaches and their applications can be found in [START_REF] Lischke | Analyzing the bitcoin network: The first four years[END_REF].

Proposed Heuristic for user re-identification

In this section, we propose to use community detection, a popular complex network analysis tool, to discover addresses belonging to a same user. The method is built on top of H1 method, using its result as input.

The main idea is to create an identity hint network, in which edges between nodes represent hints that the corresponding set of addresses might belong to a same user. Because community detection searches for dense subgraphs, sets of nodes with multiple hints of belonging to a same user will be grouped together by the algorithm. Thus this solution exploits weak signals to re-identify users.

We propose to create the identity hint network using the following process:

Heuristic H 4 - 1.
A first level of aggregation is created by applying H1. Sets of addresses belonging to a same user are used as nodes of the hint network 2. For each transaction in the dataset, considering users found by H1 instead of individual addresses, an edge is added (if not already present) between the (necessarily unique) sender and each recipient if:

• there are less than 10 users in the ouput of the transaction (recipients)

• all recipients are different from the sender, i.e there is no already known change address

On this network, a community detection algorithm is applied. Communities correspond to unique users.

In our experiments, we used a popular hierarchical community detection algorithm, the Louvain algorithm [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF], that yields several solutions at different levels of aggregation.

For a given level, we consider that a community corresponds to a user, and that this user controls all addresses associated with nodes in the cluster. As with H2 and H3, users found by H4 can be associated with one or more users of H1, i.e. there is a hierarchical relation between them.

Evaluation of user discovery heuristics

To the best of our knowledge, the quality of user re-identification heuristics has never been assessed empirically. In this section, we propose a method to do so, using tools from community detection and clustering.

Let's assume that we have at our disposal a ground truth defined as a set of n labeled addresses a GT = {a 1 , a 2 , . . . , a n }, with a L the label of address a, corresponding to the user that controls it.

By using a heuristic on a transaction dataset, we discover sets of addresses identified as belonging to a same user. We assign a same label to all addresses of the same set, thus obtaining a set of m labeled addresses, a H . By filtering out all addresses of a H not present in a GT , we obtain a set of addresses with two sets of labelling, the ground truth and a computed one. These labelling can be considered as clusters or network communities, and their similarity can be computed using, for instance, the NMI, chance adjusted NMI (aNMI) or Precision, Recall and F 1 -score, which all give a different view on the tested clustering.

NMI and aNMI

The Normalized Mutual Information is frequently used to assess the correspondence between clustering or community partitions. It comes from information theory, and corresponds to the mutual information between the two compared partitions normalized between 0 -no similarity-and 1 -identical partitions. Several variants of the normalization can be used; in this article, we use the following definition:

NMI = I(U,V )

H(U)H(V )

With I(U,V ) the mutual information between partitions U and V , and H(U) the entropy (or quantity of information) of partition U. For more details on NMI, please refer to [START_REF] Vinh | Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance[END_REF][START_REF] Lancichinetti | Detecting the overlapping and hierarchical community structure in complex networks[END_REF]. Despite being often used in community detection evaluation, NMI suffers from known limitations, in particular that random partitions have expected values higher than 0, that can even be relatively high in some cases. A commonly used variant is the adjusted for chance NMI, called aNMI, which conserves the normalization but correct for the effect of chance. Please refer to [START_REF] Vinh | Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance[END_REF] for more information on aNMI.

Precision, recall and F 1 score

Precision and Recall are typically used to assess the quality of classification tasks. They can also be used to evaluate the quality of clustering: Precision corresponds to how often elements are correctly grouped together, while Recall evaluate how often elements belonging to a same cluster are labeled as such in the tested partition.

More formally, for each pair of addresses, we check if they are TP,FP or FN:

• TP (True Positive): two addresses with the same label are in the same cluster • FP (False Positive): two addresses with different labels are in a same cluster • FN (False Negative): two addresses with the same label are in different clusters Then Precision and Recall are defined as usual:

Precision = T P T P + FP , Recall = T P T P + FN
The F 1 score is the harmonic mean of Precision and Recall, and summarize the quality of a clustering in a single value.

Test dataset

In order to compare heuristics empirically, we need a labeled dataset of users and their known addresses. In the article [START_REF] Meiklejohn | A fistful of bitcoins: characterizing payments among men with no names[END_REF], the authors have collected such a dataset by engaging in interactions with many bitcoin entities. In total, they engaged in 344 transactions with a variety of services, classified in 6 categories: Mining, Wallets, Exchanges, Vendors, Gambling and Miscellaneous. Please refer to the original article for more information on how the data was collected. After removing some particular cases, such as addresses of uncertain owners, or addresses controlled by the authors of the article, we were left with 776 addresses belonging to 90 different users. The user with the most known addresses, wallet service instawallet, controls 151 of them, while we know only one address for 33 users.

This dataset, due to its manual collection, is of relatively limited size, but still allows us to test our method and observe broad differences between heuristics. In future works, it will be necessary to collect larger labeled datasets for robuster results.

For the bitcoin transaction dataset, we limited ourselves to the one used by the authors of the ground truth dataset [START_REF] Meiklejohn | A fistful of bitcoins: characterizing payments among men with no names[END_REF]. It is composed of 16,086,073 transactions and 12,056,684 distinct addresses.

Results

We computed NMI, aNMI, Precision, Recall and F 1 -score for H1, H3 and all hierarchical levels of our proposed method H4. Results can be found in Tab. 1 As expected, Precision score for the H1 Heuristic is very high, which means that when two addresses are grouped together, they nearly always belong to the same user. By manually investigating the error, we found that addresses mistakingly grouped together belonged to two companies, one being in fact a branch of the other. More surprisingly, the Recall score is already relatively high for this heuristic.

By adopting H3, which creates larger clusters, the Recall score rises. However, this gain is made at the cost of an important decrease in Precision, thus resulting in lower overall scores (F 1 , NMI and aNMI)

We can observe that, as expected, our method reach higher Recall than the H1 method, at the cost of a lower Precision. However, compared to H3, the loss in precision is lower. In particular, partitions of the highest level (H4-l3,H4-l4) obtain higher scores than H3 on all tested metrics (Pareto dominance). H4-l1 and H4-l2, solutions of lower hierarchical levels, obtain highest aNMI score than the reference H1 metric.

Visual representation of re-identification

To better understand the differences between different heuristics, we propose to use a visual representation. We propose to use alluvial diagrams to compare re-identification algorithms results. In this visualization, each represented clustering is represented on a vertical axis; each address is represented by a horizontal, going from the cluster it belongs to in one clustering to the cluster it belongs to in the other clustering. A layout algorithm minimizes line crossings; horizontal lines with two common endpoints are grouped into a larger line, whose width corresponds to the sum of widths of addresses it represents.

To limit the visual complexity, we restrain the representation to one type of labeled users, which correspond to wallet services. Results for other types of users leads to the same kinds of observations. Fig. 1 represents the correspondence between clusters in the ground truth and H1. We can observe that users controlling large sets of addresses tend to be well discovered (large horizontal lines for instawallet, easywallet, paytunia, flexcoin). We can also observe that there is no cluster in H1 with addresses belonging to different users in the ground truth.

Fig. 2 represents the correspondence between clusters of addresses between the ground truth, H1 and H3. We can observe in H3 the presence of a large cluster (0) gathering addresses from different users in the ground truth. We can observe one occurrence (cluster 24620 in H3) of a cluster in H3 rightfully grouping together distinct clusters from H1.

Fig. 3 represents the matching between clusters of addresses in the ground truth, H1 and H4-l2. We can observe that some entities in the ground truth (flexcoin, instawallet, parts of coinbase and easywallet), are erronously merged in H4-l2, but less than with H3, as shown in Fig. 2. On the contrary, we observe several cases where different clusters in H1 are correctly merged by H4-l2 into clusters very close to those of the ground truth (for paytunia, easywallet and coinbase, in particular)

We can therefore conclude that the proposed method offer a better solution than the H3 method, and even provide a relevant alternative to the widespread H1 solution.

Advantages of the proposed method

On top of yielding a relevant user discovery solution, the community detection approach has several advantages:

• Because it allows to extract several hierarchical levels, one can choose, depending on the application, to increase Recall at the cost of Precision, or said differently, to discover more addresses for known users, at the risk of mistakingly merging different users. • Because the solution is not based on a set of rules, but on weak signals, it is more difficult for users to develop countermeasures to escape re-identification of their addresses • The proposed solution is a generic framework that can be adapted in countless ways to be improved: one could create a different hint network, using weighted edges based on rules decided by experts, or based on machine learning. One could also use other community detection algorithms. Finally, one could also take into account the dynamic of transactions, through temporal networks [START_REF] Holme | Temporal networks[END_REF] and dynamic community detection [START_REF] Cazabet | Dynamic community detection[END_REF].

Conclusion

In this article, we have shown how community detection could be used to improve re-identification of users in bitcoins. We think that this article has two main contributions: on the one hand, it provides a framework for empirical testing and comparison of re-identification algorithms. The dataset used as ground truth is limited in size and representativeness, and further work is needed to produce more ambitious ground truth datasets in order to validate algorithms on a large scale.

On the other hand, we have shown how using complex networks analysis tools such as community detection could improve existing techniques, based on set of rules. In particular, contrary to set of rules techniques, they cannot be easily bypassed by users when publicly released.

Fig. 1

 1 Fig.1Alluvial diagram representing the matching between clusters of addresses in the ground truth and H1. Each horizontal line corresponds to an address. A thick line corresponds to the aggregation of a set of addresses with common left and right belongings. We can observe that some entities (e.g instawallet) are already quite well identified by this heuristic, for the given test set. Nevertheless, for most entities, their addresses are divided into several clusters in H1.

Fig. 2

 2 Fig.2Alluvial diagram representing the matching between clusters of addresses in the ground truth, H3 and H1. We can observe the apparition of a large cluster (named 0) that merge together many addresses corresponding in fact to different entities (Paytunia, easywallet, flexcoin, instawallet, etc.).

Fig. 3

 3 Fig.3Alluvial diagram representing the matching between clusters of addresses in the ground truth, H3 and H1. We can observe the apparition of a large cluster (named 0) that merge together many addresses corresponding in fact to different entities (Paytunia, easywallet, flexcoin, instawallet, etc.).

Table 1

 1 Empirical comparison of User re-identification algorithms. H4-l1 to H4-l4 correspond to the increasing hierarchical levels of the community detection based method (H4). Highest values in bold, lowest ones in italic.

	Heur. Precision Recall F 1 NMI aNMI
	H1	0.98	0.77 0.86 0.89 0.65
	H3	0.09	0.83 0.16 0.47 0.15
	H4-l1 0.75	0.79 0.77 0.86 0.66
	H4-l2 0.50	0.87 0.63 0.81 0.67
	H4-l3 0.27	0.90 0.42 0.70 0.47
	H4-l4 0.25	0.91 0.39 0.67 0.43

Acknowledgements We want to thank the authors of [11], and in particular Sarah Meiklejohn, for kindly sharing with us their dataset, result of their remarkable work. This work is funded in part by the European Commission H2020 FETPROACT 2016-2017 program under grant 732942 (ODYCCEUS), by the ANR (French National Agency of Research) under grants ANR-15-CE38-0001 (AlgoDiv) and ANR-13-CORD-0017-01 (CODDDE), by the French program PIA -Usages, services et contenus innovants" under grant O18062-44430 (RE-QUEST), and by the Ile-de-France program FUI21 under grant 16010629 (iTRAC).