Guillaume Papa

Clémençon Stéphan

Ltci

Aurélien Bellet
email: aurelien.bellet@inria.fr

On Graph Reconstruction via Empirical Risk Minimization: Fast Learning Rates and Scalability

. Strikingly, these fast rates are universal, in contrast to similar results known for other statistical learning problems (e.g., classification, density level set estimation, ranking, clustering) which require strong assumptions on the distribution of the data. Motivated by applications to large graphs, our second contribution deals with the computational complexity of graph reconstruction. Specifically, we investigate to which extent the learning rates can be preserved when replacing the empirical reconstruction risk by a computationally cheaper Monte-Carlo version, obtained by sampling with replacement B n 2 pairs of nodes. Finally, we illustrate our theoretical results by numerical experiments on synthetic and real graphs.

Introduction

Although statistical learning theory mainly focuses on establishing universal rate bounds (i.e., which hold for any distribution of the data) for the accuracy of a decision rule based on training observations, refined concentration inequalities have recently helped understanding conditions on the data distribution under which learning paradigms such as Empirical Risk Minimization (ERM) lead to faster rates. In binary classification, i.e., the problem of learning to predict a random binary label Y ∈ {-1, +1} from on an input random variable X based on independent copies (X 1 , Y 1 ), . . . , (X n , Y n ) of the pair (X, Y ), rates faster than 1/ √ n are achieved when little mass in the vicinity of 1/2 is assigned by the distribution of the random variable η(X) = P{Y = +1 | X}. This condition and its generalizations are referred to as the Mammen-Tsybakov noise conditions (see [START_REF] Mammen | Smooth discrimination analysis[END_REF][START_REF] Tsybakov | Optimal aggregation of classifiers in statistical learning[END_REF][START_REF] Massart | Risk bounds for statistical learning[END_REF]. It has been shown that a similar phenomenon occurs for various other statistical learning problems. Indeed, specific conditions under which fast rate results hold have been exhibited for density level set estimation [START_REF] Rigollet | Fast rates for plug-in estimators of density level sets[END_REF], (bipartite) ranking [START_REF] Clémençon | Ranking and Empirical Minimization of U-statistics[END_REF][START_REF] Clémençon | Minimax learning rates for bipartite ranking and plug-in rules[END_REF][START_REF] Agarwal | Surrogate regret bounds for bipartite ranking via strongly proper losses[END_REF], clustering [START_REF] Antos | Individual convergence rates in empirical vector quantizer design[END_REF][START_REF] Clémençon | A statistical view of clustering performance through the theory of U-processes[END_REF] and composite hypothesis testing [START_REF] Clémençon | Overlaying classifiers: a practical approach to optimal scoring[END_REF].

In this paper, we consider the supervised learning problem on graphs referred to as graph reconstruction, rigorously formulated by [START_REF] Biau | Statistical Inference on Graphs[END_REF]. The objective of graph reconstruction is to predict the possible occurrence of connections between a set of objects/individuals known to form the nodes of an undirected graph. Precisely, each node is described by a random vector X which defines 30th Conference on Neural Information Processing Systems (NIPS 2016), Barcelona, Spain. a form of conditional preferential attachment: one predicts whether two nodes are connected based on their features X and X . This statistical learning problem is motivated by a variety of applications such as systems biology (e.g., inferring protein-protein interactions or metabolic networks, see [START_REF] Jansen | A Bayesian networks approach for predicting protein-protein interactions from genomic data[END_REF][START_REF] Kanehisa | Prediction of higher order functional networks from genomic data[END_REF] and social network analysis (e.g., predicting future connections between users, see [START_REF] Liben-Nowell | The link prediction problem for social networks[END_REF]. It has recently been the subject of a good deal of attention in the machine learning literature (see [START_REF] Vert | Supervised graph inference[END_REF][START_REF] Biau | Statistical Inference on Graphs[END_REF][START_REF] Shaw | Learning a Distance Metric from a Network[END_REF], and is also known as supervised link prediction [START_REF] Lichtenwalter | New perspectives and methods in link prediction[END_REF][START_REF] Cukierski | Graph-based features for supervised link prediction[END_REF]. The learning task is formulated as the minimization of a reconstruction risk, whose natural empirical version is the average prediction error over the n(n -1)/2 pairs of nodes in a training graph of size n. Under standard complexity assumptions on the set of candidate prediction rules, excess risk bounds of the order O P (1/ √ n) for the empirical risk minimizers have been established by [START_REF] Biau | Statistical Inference on Graphs[END_REF] based on a representation of the objective functional very similar to the first Hoeffding decomposition for second-order U -statistics (see [START_REF] Hoeffding | A class of statistics with asymptotically normal distribution[END_REF]. However, Biau & Bleakley ignored the computational complexity of finding an empirical risk minimizer, which scales at least as O(n 2 ) since the empirical graph reconstruction risk involves summing up over n(n -1)/2 terms. This makes the approach impractical when dealing with large graphs commonly found in many applications.

Building up on the above work, our contributions to statistical graph reconstruction are two-fold:

Universal fast rates. We prove that a fast rate of order O P (log n/n) is always achieved by empirical reconstruction risk minimizers, in absence of any restrictive condition imposed on the data distribution. This is much faster than the O P (1/ √ n) rate established by [START_REF] Biau | Statistical Inference on Graphs[END_REF]. Our analysis is based on a different decomposition of the excess of reconstruction risk of any decision rule candidate, involving the second Hoeffding representation of a U -statistic approximating it, as well as appropriate maximal/concentration inequalities.

Scaling-up ERM. We investigate the performance of minimizers of computationally cheaper Monte-Carlo estimates of the empirical reconstruction risk, built by averaging over B n 2 pairs of vertices drawn with replacement. The rate bounds we obtain highlight that B plays the role of a tuning parameter to achieve an effective trade-off between statistical accuracy and computational cost. Numerical results based on simulated graphs and real-world networks are presented in order to support these theoretical findings.

The paper is organized as follows. In Section 2, we present the probabilistic setting for graph reconstruction and recall state-of-the-art results. Section 3 provides our fast rate bound analysis, while Section 4 deals with the problem of scaling-up reconstruction risk minimization to large graphs. Numerical experiments are displayed in Section 5, and a few concluding remarks are collected in Section 6. The technical proofs can be found in the Supplementary Material, along with some additional remarks and results.

Background and Preliminaries

We start by describing at length the probabilistic framework we consider for statistical inference on graphs, as introduced by [START_REF] Biau | Statistical Inference on Graphs[END_REF]. We then briefly recall the related theoretical results documented in the literature.

A Probabilistic Setup for Preferential Attachment

In this paper, G = (V, E) is an undirected random graph with a set V = {1, . . . , n} of n ≥ 2 vertices and a set E = {e i,j : 1 ≤ i = j ≤ n} ∈ {0, 1} n(n-1) describing its edges: for all i = j, we have e i,j = e j,i = +1 if the vertices i and j are connected by an edge and e i,j = e j,i = 0 otherwise. We assume that G is a Bernoulli graph, i.e. the random variables e i,j , 1 ≤ i < j ≤ n, are independent labels drawn from a Bernoulli distribution Ber(p) with parameter p = P{e i,j = +1}, the probability that two vertices of G are connected by an edge. The degree of each vertex is thus distributed as a binomial with parameters n and p, which can be classically approximated by a Poisson distribution of parameter λ > 0 in the limit of large n, when np → λ.

Whereas the marginal distribution of the graph G is that of a Bernoulli graph (also sometimes abusively referred to as a random graph), a form of conditional preferential attachment is also specified in the framework considered here. Precisely, we assume that, for all i ∈ V , a continuous r.v.

X i , taking its values in a separable Banach space X , describes some features related to vertex i. The X i 's are i.i.d. with common distribution µ(dx) and, for any i = j, the random pair (X i , X j ) models some information useful for predicting the occurrence of an edge connecting the vertices i and j. Conditioned upon the features (X 1 , . . . , X n ), any binary variables e i,j and e k,l are independent only if {i, j} ∩ {k, l} = ∅. The conditional distribution of e i,j , i = j, is supposed to depend on (X i , X j ) solely, described by the posterior preferential attachment probability: η (X i , X j ) = P {e i,j = +1 | (X i , X j )} .

(1)

For instance, ∀(x 1 , x 2 ) ∈ X 2 , η (x 1 , x 2 ) can be a certain function of a specific distance or similarity measure between x 1 and x 2 , as in the synthetic graphs described in Section 5.

The conditional average degree of the vertex i ∈ V given X i (respectively, given

(X 1 , . . . , X n )) is thus (n -1) x∈X η(X i , x)µ(dx) (respectively, j =i η(X i , X j )).
Observe incidentally that, equipped with these notations, p = (x,x )∈X 2 η(x, x )µ(dx)µ(dx ). Hence, the 3-tuples (X i , X j , e i,j ), 1 ≤ i < j ≤ n, are non-i.i.d. copies of a generic random vector (X 1 , X 2 , e 1,2 ) whose distribution L is given by the tensorial product µ(dx 1 ) ⊗ µ(dx 2 ) ⊗ Ber(η(x 1 , x 2 )), which is fully described by the pair (µ, η). Observe also that the function η is symmetric by construction:

∀(x 1 , x 2 ) ∈ X 2 , η(x 1 , x 2 ) = η(x 2 , x 1 ).
In this framework, the learning problem introduced by [START_REF] Biau | Statistical Inference on Graphs[END_REF], referred to as graph reconstruction, consists in building a symmetric reconstruction rule g : X 2 → {0, 1}, from a training graph G, with nearly minimum reconstruction risk

R(g) = P {g(X 1 , X 2 ) = e 1,2 } , (2)
thus achieving a comparable performance to that of the Bayes rule g

* (x 1 , x 2 ) = I{η(x 1 , x 2 ) > 1/2}, whose risk is given by R * = E[min{η(X 1 , X 2 ), 1 -η(X 1 , X 2 )}] = inf g R(g).
Remark 1 (EXTENDED FRAMEWORK) The results established in this paper can be straightforwardly extended to a more general framework, where L = L (n) may depend on the number n of vertices. This allows to consider a general class of models, accounting for possible accelerating properties exhibited by various non scale-free real networks [START_REF] Mattick | Accelerating networks[END_REF]). An asymptotic study can be then carried out with the additional assumption that, as n → +∞, L (n) converges in distribution to a probability measure L (∞) on X × X × {0, 1}, see [START_REF] Biau | Statistical Inference on Graphs[END_REF]. For simplicity, we restrict our study to the stationary case, i.e. L (n) = L for all n ≥ 2.

Related Results on Empirical Risk Minimization

A paradigmatic approach in statistical learning, referred to as Empirical Risk Minimization (ERM), consists in replacing (2) by its empirical version based on the labeled sample D n = {(X i , X j , e i,j ) :

1 ≤ i < j ≤ n} related to G: 1 R n (g) = 2 n(n -1) 1≤i<j≤n I {g(X i , X j ) = e i,j } .
(3)

An empirical risk minimizer g n is a solution of the optimization problem min g∈G R n (g), where G is a class of reconstruction rules of controlled complexity, hopefully rich enough to yield a small bias inf g∈G R(g) -R * . The performance of g n is measured by its excess risk R( g n ) -inf g∈G R(g), which can be bounded if we can derive probability inequalities for the maximal deviation

sup g∈G | R n (g) -R(g)|. (4)
In the framework of classification, the flagship problem of statistical learning theory, the empirical risk is of the form of an average of i.i.d. r.v.'s, so that results pertaining to empirical process theory can be readily used to obtain bounds for the performance of empirical error minimization. Unfortunately, the empirical risk (3) is a sum of dependent variables. Following in the footsteps of [START_REF] Clémençon | Ranking and Empirical Minimization of U-statistics[END_REF], the work of [START_REF] Biau | Statistical Inference on Graphs[END_REF] circumvents this difficulty by means of a representation of R n (g) as an average of sums of i.i.d. r.v.'s, namely

1 n! σ∈Sn 1 n/2 n 2 i=1 I{g(X σ(i) , X σ(i+ n 2 ) ) = e σ(i),σ(i+ n 2 ) },
where the sum is taken over all permutations of S n , the symmetric group of order n, and u denotes the integer part of any u ∈ R. Very similar to the first Hoeffding decomposition for U -statistics (see [START_REF] Lee | U -statistics: Theory and practice[END_REF], this representation reduces the first order analysis of the concentration properties of (4) to the study of a basic empirical process (see Biau and Bleakley, 2006, Lemma 3.1). [START_REF] Biau | Statistical Inference on Graphs[END_REF] thereby establish rate bounds of the order O P (1/ √ n) for the excess of reconstruction risk of g n under appropriate complexity assumptions (namely, G is of finite VC-dimension). Note incidentally that (3) is a U -statistic only when the variable η(X 1 , X 2 ) is almost-surely constant (see [START_REF] Janson | The asymptotic distributions of generalized U-statistics with applications to random graphs[END_REF], for an asymptotic study of graph reconstruction in this restrictive context).

Remark 2 (ALTERNATIVE LOSS FUNCTIONS) For simplicity, all our results are stated for the case of the 0-1 loss I{g(X i , X j ) = e i,j }, but they straightforwardly extend to more practical alternatives such as the convex surrogate and cost-sensitive variants used in our numerical experiments. See the Supplementary Material for more details.

Empirical Reconstruction is Always Fast!

In this section, we show that the rate bounds established by [START_REF] Biau | Statistical Inference on Graphs[END_REF] can be largely improved without any additional assumptions. Precisely, we prove that fast learning rates of order O P (log n/n) are always attained by the minimizers of the empirical reconstruction risk (3), as revealed by the following theorem.

Theorem 1 (FAST RATES) Let g n be any minimizer of the empirical reconstruction risk (3) over a class G of finite VC-dimension V < +∞. For all δ ∈ (0, 1), we have w.p. at least 1 -δ: ∀n ≥ 2,

R( g n ) -R * ≤ 2 inf g∈G R(g) -R * + C × V log(n/δ) n ,
where C < +∞ is a universal constant.2

Remark 3 (ON THE BIAS TERM) Apart from its remarkable universality, Theorem 1 takes the same form as in the case of empirical minimization of U-statistics (Clémençon et al., 2008, Corollary 6), with the same constant 2 in front of the bias term inf g∈G R(g) -R * . As can be seen from the proof, this constant has no special meaning and can be replaced by any constant strictly larger than 1 at the cost of increasing the constant C. Note that the O P (1/ √ n) rate obtained by [START_REF] Biau | Statistical Inference on Graphs[END_REF] has a factor 1 in front of the bias term. Therefore, Theorem 1 provides a significant improvement unless the bias overly dominates the second term of the bound (i.e., the complexity of G is too small).

Remark 4 (ON COMPLEXITY ASSUMPTIONS) We point out that a similar result can be established under weaker complexity assumptions involving Rademacher averages (refer to the Supplementary Material for more details). As may be seen by carefully examining the proof of Theorem 1, this would require to use the moment inequality for degenerate U -processes stated in (Clémençon et al., 2008, Theorem 11) instead of that proved by [START_REF] Arcones | U-processes indexed by Vapnik-Chervonenkis classes of functions with applications to asymptotics and bootstrap of U-statistics with estimated parameters[END_REF].

In the rest of this section, we outline the main ideas used to obtain this result (the detailed proofs can be found in the Supplementary Material). We rely on some arguments used in the fast rate analysis for empirical minimization of U -statistics [START_REF] Clémençon | Ranking and Empirical Minimization of U-statistics[END_REF], although these results only hold true under restrictive distributional assumptions. Whereas the quantity (3) is not a U -statistic, one may decompose the difference between the excess of reconstruction risk of any candidate rule g ∈ G and its empirical counterpart as the sum of its conditional expectation given the X i 's, which is a U -statistic, plus a residual term. In order to explain the main argument underlying the present analysis, additional notation is required. Set

H g (x 1 , x 2 , e 1,2 ) = I{g(x 1 , x 2 ) = e 1,2 } and q g (x 1 , x 2 , e 1,2 ) = H g (x 1 , x 2 , e 1,2 )-H g * (x 1 , x 2 , e 1,2 ) for any (x 1 , x 2 , e 1,2 ) ∈ X × X × {0, 1}. Denoting by Λ(g) = R(g) -R * = E[q g (X 1 , X 2 , e 1,2 )]
the excess reconstruction risk with respect to the Bayes rule, its empirical estimate is given by

Λ n (g) = R n (g) -R n (g * ) = 2 n(n -1) 1≤i<j≤n q g (X i , X j , e i,j ).
For all g ∈ G, one may write:

Λ n (g) -Λ(g) = U n (g) + W n (g),
(5) where

U n (g) = E [Λ n (g) -Λ(g) | X 1 , . . . , X n ] = 2 n(n -1) 1≤i<j≤n q g (X i , X j ) -Λ(g)
is a U -statistic of degree 2 with symmetric kernel q g (X 1 , X 2 )-Λ(g), where we denote

q g (X 1 , X 2 ) = E[q g (X 1 , X 2 , e 1,2 ) | X 1 , X 2 ], and W n (g) = 2 n(n-1) i<j {q g (X i , X j , e i,j ) -q g (X i , X j )}.
Equipped with this notation, we can now sketch the main steps of the proof of the fast rate bound stated in Theorem 1. As shown in the Supplementary Material, it is based on Eq. ( 5) combined with two intermediary results, each providing a control of one of the terms involved in it. The second order analysis carried out by [START_REF] Clémençon | Ranking and Empirical Minimization of U-statistics[END_REF] shows that the small variance property of U -statistics may yield fast learning rates for empirical risk minimizers when U -statistics are used to estimate the risk, under a certain "low-noise" condition (see Assumption 4 therein). One of our main findings is that this condition is always fulfilled for the specific U -statistic U n (g) involved in the decomposition (5) of the excess of reconstruction risk of any rule candidate g, as shown by the following lemma.

Lemma 2 (VARIANCE CONTROL) For any distribution L and any reconstruction rule g, we have

Var

(E [q g (X 1 , X 2 , e 1,2 ) | X 1 ]) ≤ Λ(g).
The fundamental reason for the universal character of this result lies in the fact that the empirical reconstruction risk is not an average over all pairs (i.e., a U-statistic of order 2) but an average over randomly selected pairs (random selection being ruled by the function η). The resulting smoothness is the key ingredient allowing us to establish the desired property.

Empirical reconstruction risk minimization over a class G being equivalent to minimization of Λ n (g) -Λ(g), the result below, combined with (5), proves that it also boils down to minimizing U n (g) under appropriate conditions on G, so that the fast rate analysis of [START_REF] Clémençon | Ranking and Empirical Minimization of U-statistics[END_REF] can be extended to graph reconstruction.

Lemma 3 (UNIFORM APPROXIMATION) Under the same assumptions as in Theorem 1, for any δ ∈ (0, 1), we have with probability larger than 1 -δ: ∀n ≥ 2,

sup g∈G W n (g) ≤ C × V log(n/δ) n ,
where C < +∞ is a universal constant.

The proof relies on classical symmetrization and randomization tricks combined with the decoupling method, in order to cope with the dependence structure of the variables and apply maximal/concentration inequalities for sums of independent random variables (see De la [START_REF] De La Pena | Decoupling : from dependence to independence[END_REF].

Based on the above results, Theorem 1 can then be derived by relying on the second Hoeffding decomposition (see [START_REF] Hoeffding | A class of statistics with asymptotically normal distribution[END_REF]. This allows us to write U n (g) as a leading term taking the form of a sum of i.i.d r.v.'s with variance 4V ar(E[q g (X 1 , X 2 , e 1,2 ) | X 1 ]), plus a degenerate U -statistic (i.e., a U -statistic of symmetric kernel h(x 1 , x 2 ) such that E[h(x 1 , X 2 )] = 0 for all x 1 ∈ X ). The latter can be shown to be of order O P (1/n) uniformly over the class G by means of concentration results for degenerate U -processes.

We conclude this section by observing that, instead of estimating the reconstruction risk by (3), one could split the training dataset into two halves and consider the unbiased estimate of (2) given by

1 n/2 n/2 i=1 I{g(X i , X i+ n/2 ) = e i,i+ n/2 }. ( 6
)
The analysis of the generalization ability of minimizers of this empirical risk functional is simpler, insofar as only independent r.v.'s are involved in the sum (6). However, this estimate does not share the reduced variance property of (3) and although one could show that rate bounds of the same order as those stated in Theorem 1 may be attained by means of results pertaining to ERM theory for binary classification (see e.g. Section 5 in [START_REF] Boucheron | Moment inequalities for functions of independent random variables[END_REF], this would require a very restrictive assumption on distribution L, namely to suppose that the posterior preferential attachment probability η stays bounded away from 1/2 with probability one (cf [START_REF] Massart | Risk bounds for statistical learning[END_REF]. This is illustrated in the Supplementary Material.

Scaling-up Empirical Risk Minimization

The results of the previous section, as well as those of [START_REF] Biau | Statistical Inference on Graphs[END_REF], characterize the excess risk achieved by minimizers of the empirical reconstruction risk R n (g) but do not consider the computational complexity of finding such minimizers. For large training graphs, the complexity of merely computing R n (g) is prohibitive as the number of terms involved in the summation is O(n 2 ).

In this section, we introduce a sampling-based approach to build approximations of the reconstruction risk with much fewer terms than O(n 2 ), so as to scale-up risk minimization to large graphs.

The strategy we propose, inspired from the notion of incomplete U -statistic (see [START_REF] Lee | U -statistics: Theory and practice[END_REF], is of disarming simplicity: instead of the empirical reconstruction risk (3), we will consider an incomplete approximation obtained by sampling pairs of vertices (and not vertices) with replacement. Formally, we define the incomplete graph reconstruction risk based on B ≥ 1 pairs of vertices as

R B (g) = 1 B (i,j)∈P B I {g(X i , X j ) = e i,j } , (7)
where P B is a set of cardinality B built by sampling with replacement in the set Θ n = {(i, j) : 1 ≤ i < j ≤ n} of all pairs of vertices of the training graph G. For any b ∈ {1, . . . , B} and all (i, j) ∈ Θ n , denote by b (i, j) the variable indicating whether the pair (i, j) has been picked at the b-th draw ( b (i, j) = +1) or not ( b (i, j) = +0). The (multinomial) random vectors b = ( b (i, j)) (i,j)∈Θn are i.i.d. (notice that (i,j)∈Θn b (i, j) = +1 for 1 ≤ b ≤ B) and the incomplete risk can be then rewritten as

R B (g) = 1 B B b=1 (i,j)∈Θn b (i, j) • I {g(X i , X j ) = e i,j } . (8)
Observe that the statistic ( 7) is an unbiased estimate of the true risk (2) and that, given the X i 's, its conditional expectation is equal to (3). Considering ( 7) with B = o(n 2 ) as our empirical risk estimate significantly reduces the computational cost, at the price of a slightly increased variance:

Var R B (g) = Var R n (g) + 1 B Var R 1 (g) -Var R n (g) ,
for any reconstruction rule g. Note in particular that the above variance is in general much smaller than that of the complete reconstruction risk based on a subsample of √ B vertices drawn at random (thus involving O(B) pairs as well). We refer to the Supplementary Material for more details.

We are thus interested in characterizing the performance of solutions g B to the computationally simpler problem min g∈G R B (g). The following theorem shows that, when the class G is of finite VCdimension, the concentration properties of the incomplete reconstruction risk process { R B (g)} g∈G can be deduced from those of the complete version { R n (g)} g∈G .

Theorem 4 (UNIFORM DEVIATIONS) Suppose that the class G is of finite VC-dimension V < +∞. For all δ > 0, n ≥ 1 and B ≥ 1, we have with probability at least 1 -δ:,

sup g∈G | R B (g) -R n (g)| ≤ log 2 + V log ((1 + n(n -1)/2)/δ) 2B .
The finite VC-dimension hypothesis can be relaxed and a bound of the same order can be proved to hold true under weaker complexity assumptions involving Rademacher averages (see Remark 4). Remarkably, with only B = O(n) pairs, the rate in Theorem 4 is of the same order (up to a log factor) as that obtained by [START_REF] Biau | Statistical Inference on Graphs[END_REF] for the maximal deviation sup g∈G | R n (g) -R(g)| related to the complete reconstruction risk R n (g) with O(n 2 ) pairs. From Theorem 4, one can get a learning rate of order O P (1/ √ n) for the minimizer of the incomplete risk involving only O(n) pairs.

Unfortunately, such an analysis does not exploit the relationship between conditional variance and expectation formulated in Lemma 2, and is thus not sufficient to show that reconstruction rules minimizing the incomplete risk ( 7) can achieve learning rates comparable to those stated in Theorem 1.

In contrast, the next theorem provides sharper statistical guarantees. We refer to the Supplementary Material for the proof.

Theorem 5 Let g B be any minimizer of the incomplete reconstruction risk (7) over a class G of finite VC-dimension V < +∞. Then, for all δ ∈ (0, 1), we have with probability at least 1 -δ: ∀n ≥ 2,

R( g B ) -R * ≤ 2 inf g∈G R(g) -R * + CV log(n/δ) × 1 n + 1 √ B ,
where C < +∞ is a universal constant.

This bound reveals that the number B ≥ 1 of pairs of vertices plays the role of a tuning parameter, ruling a trade-off between statistical accuracy (taking B(n) = O(n 2 ) fully preserves the convergence rate) and computational complexity. This will be confirmed numerically in Section 5.

The above results can be extended to other sampling techniques, such as Bernoulli sampling and sampling without replacement. We refer to the Supplementary Material for details.

Numerical Experiments

In this section, we present some numerical experiments on large-scale graph reconstruction to illustrate the practical relevance of the idea of incomplete risk introduced in Section 4. Following a well-established line of work [START_REF] Vert | Supervised graph inference[END_REF][START_REF] Vert | A new pairwise kernel for biological network inference with support vector machines[END_REF][START_REF] Shaw | Learning a Distance Metric from a Network[END_REF], we formulate graph reconstruction as a distance metric learning problem [START_REF] Bellet | Metric Learning[END_REF]: we learn a distance function such that we predict an edge between two nodes if the distance between their features is smaller than some threshold. Assuming X ⊆ R q , let S q + be the cone of symmetric PSD q × q real-valued matrices. The reconstruction rules we consider are parameterized by M ∈ S q + and have the form

g M (x 1 , x 2 ) = I {D M (x 1 , x 2 ) ≤ 1} , where D M (x 1 , x 2 ) = (x 1 -x 2 ) T M (x 1 -x 2
) is a (pseudo) distance equivalent to the Euclidean distance after a linear transformation L ∈ R q×q , with M = L T L. Note that g M (x 1 , x 2 ) can be seen as a linear separator operating on the pairwise representation vec((

x 1 -x 2 )(x 1 -x 2 ) T ) ∈ R q 2 ,
Table 1: Results (averaged over 10 runs) on synthetic graph with n = 1, 000, 000, q = 100, p = 0.05. hence the class of learning rules we consider has VC-dimension bounded by q 2 + 1. We define the reconstruction risk as:

B = 0.01n B = 0.1n B = n B = 5n B = 10n
S n (g M ) = 2 n(n -1) i<j [(2e i,j -1)(D M (X i , X j ) -1)] + ,
where [•] + = max(0, •) is a convex surrogate for the 0-1 loss. In earlier work, ERM has only been applied to graphs with at most a few hundred or thousand nodes due to scalability issues. Thanks to our results, we are able to scale it up to much larger networks by sampling pairs of nodes and solve the resulting simpler optimization problem.

We create a synthetic graph with n nodes as follows. Each node i has features X true i ∈ R q sampled uniformly over [0, 1]. We then add an edge between nodes that are at Euclidean distance smaller than some threshold τ , and introduce some noise by flipping the value of i,j for each pair of nodes (i, j) independently with probability p. We then apply a random linear transformation R ∈ R q×q to each node to generate a "scrambled" version X i = RX true i of the nodes' features. The learning algorithm is only allowed to observe the scrambled features and must find a rule which accurately recovers the graph by solving the ERM problem above. Note that, denoting D ij = R -1 X i -R X j 2 , the posterior preferential attachment probability is given by η (X i , X j ) = (1 -p)

• I{D ij ≤ τ } + p • I{D ij > τ }.
The process is illustrated in Figure 1. Using this procedure, we generate a training graph with n = 1, 000, 000 and q = 100. We set the threshold τ such that there is an edge between about 20% of the node pairs, and set p = 0.05. We also generate a test graph using the same parameters. We then sample uniformly with replacement B pairs of nodes from the training graph to construct our incomplete reconstruction risk. The reconstruction error of the resulting empirical risk minimizer is estimated on 1,000,000 pairs of nodes drawn from the test graph. Table 1 shows the test error (averaged over 10 runs) as well as the training time for several values of B. Consistently with our theoretical findings, B implements a trade-off between statistical accuracy and computational cost. For this dataset, sampling B = 5, 000, 000 pairs (out of 10 12 possible pairs!) is sufficient to find an accurate reconstruction rule. A larger B would result in increased training time for negligible gains in reconstruction error.

Additional results. In the Supplementary Material, we present comparisons to a node sampling scheme and to the "dataset splitting" strategy given by (6), as well as experiments on a real network.

Conclusion

In this paper, we proved that the learning rates for ERM in the graph reconstruction problem are always of order O P (log n/n). We also showed how sampling schemes applied to the population of edges (not nodes) can be used to scale-up such ERM-based predictive methods to very large graphs by means of a detailed rate bound analysis, further supported by empirical results. A first possible extension of this work would naturally consist in considering more general sampling designs, such as Poisson sampling (which generalizes Bernoulli sampling) used in graph sparsification (cf [START_REF] Spielman | Fast Randomized Algorithms for Partitioning, Sparsification, and Solving Linear Systems[END_REF], and investigating the properties of minimizers of Horvitz-Thompson versions of the reconstruction risk (see [START_REF] Horvitz | A generalization of sampling without replacement from a finite universe[END_REF]. Another challenging line of future research is to extend the results of this paper to more complex unconditional graph structures in order to account for properties shared by some real-world graphs (e.g., graphs with a power law degree distribution).

Figure 1 :

 1 Figure1: Illustrative experiment with n = 50, q = 2, τ = 0.27 and p = 0. Figure1(a)shows the training graph, where the position each node is given by its 2D feature vector. Figure1(b)depicts the same graph after applying a random transformation R to the features. On this graph, the Euclidean distance with optimal threshold achieves a reconstruction error of 0.1311. In contrast, the reconstruction rule learned from B = 100 pairs of nodes (out of 1225 possible pairs) successfully inverts R and accurately recovers the original graph (Figure1(c)). Its reconstruction error is 0.008 on the training graph and 0.009 on a held-out graph generated with the same parameters.

A classical Lehmann-Scheffé argument shows that (3) is the estimator of (2) with smallest variance among all unbiased estimators.

Note that, throughout the paper, the constant C is not necessarily the same at each appearance.

Acknowledgments This work was partially supported by the chair "Machine Learning for Big Data" of Télécom ParisTech and by a grant from CPER Nord-Pas de Calais/FEDER DATA Advanced data science and technologies 2015-2020.


Jean-Pierre Allegret
email: allegret@gate.cnrs.fr

Alain Sand Janvier

Alain Sand-Zantman

Modeling the impact of real and financial shocks on Mercosur: the role of the exchange rate regime

Keywords: Business Cycles, OCA, Co-movement, VAR, Unobserved components model, Mercosur. JEL Classification: C32, E32, F42

This paper studies to what extent the diversity of exchange rate regimes within Mercosur exerts an influence on the feasibility of a monetary union in this area. A semi-structural VAR model is built for each country, including a set of international and domestic variables. Based on impulse response functions and forecast error decomposition, we conclude that differences of exchange rate regime explain significantly the divergences of economic dynamics triggered by foreign or domestic shocks. Second, we decompose the structural innovations generated by each country model into unobservable common and idiosyncratic components, using a statespace model. This last exercise, intended to assess the degree of policy coordination between the Mercosur members, did not disclose any common component for the structural innovations generated by the three national models.

Introduction

The Common market of the South (Mercosur) was created in 1991 by the Treaty of Asuncion signed between Argentina, Brazil, Paraguay and Uruguay. At the beginning the formal project was just a free trade agreement. During the 90s, the signatory countries envisaged a more ambitious economic and monetary process of integration. The Mexican (1994), Asian (1997), Russian (1998), Brazilian (1999) and Argentina (2001Argentina ( -2002) ) crises strongly increased the volatility of the macroeconomic variables. In the face of shocks, economies gave priority to national concerns, weakening the economic and institutional links embodied in the Asuncion Treaty.

This evolution raises the question of the feasibility of a regional monetary union between the Mercosur countries3 . The basic Optimal Currency Areas (OCA) literature identifies criteria to determine the appropriate domain -the optimal size-of a currency area. Countries can optimally form a monetary union when they fulfill the following criteria: (i) a high factor mobility; (ii) a high degree of trade; (iii) a strong symmetry of shocks explained by the diversified composition of output and trade; (iv) a high degree of financial integration; and (v) a high degree of similarity in preferences between member countries of the currency area. [START_REF] Eichengreen | Does Mercosur need a single currency ?[END_REF], [START_REF] Levy-Yeyati | EMU a blueprint for Mercosur?[END_REF], [START_REF] Larrain | Regional currencies versus dollarization: options for Asia and the Americas[END_REF], and [START_REF] Eichengreen | The monetary consequences of a free trade area of the Americas[END_REF] used the OCA theory to determine if Central and Latin American countries can choose a monetary union as their exchange rate regime. Their conclusion -using cross-section or panel data (as econometric methodology)-is that Mercosur countries are far from achieving the pre-requisites to constitute an OCA. From this point of view, Latin American countries (LAC) differ from other regions such as East Asia. [START_REF] Alesina | Currency unions[END_REF] analyse currency unions in terms of costs and benefits. They distinguish two benefits: first, trade benefits -where the higher the bilateral trade the higher the gains linked to the reduction of transaction costs after adopting a common currency -and, second, the benefits of commitment (where the irreversibility of the currency union leads to a decrease in inflation). The main cost of a currency union is the loss of independent monetary policy. This cost increases with the importance of asymmetric disturbances across potential members of the union. [START_REF] Alesina | Optimal currency areas[END_REF] have tested this model using annual data of bilateral trade, inflation rates, comovements of prices and output over the period . They show that the US dollar is not a good anchor for Mercosur countries. Co-movements of prices and outputs with the United States are weak. This result is particularly striking for the two main countries of this area: Argentina for which neither the US Dollar nor the Euro are natural anchors and Brazil for which the European currency is a more appropriate anchor.

Contrary to what OCA theory and cost-benefit analysis of a monetary union propose, our approach is exclusively based on the business cycle properties of the Mercosur countries. Our analysis focuses on business cycles synchronization across countries, on the propagation mechanisms of shocks, and on their common and specific components.

Our paper raises several questions linked to the feasibility of a currency union in Mercosur. First, to what extent has the adoption of different exchange rate regimes affected the countries' reactions to disturbances? In other words, is the diversity of exchange rate regimes inside the area an obstacle to macroeconomic policy coordination? Different adjustments to similar external and/or domestic shocks give indications onto the degree of coordination between Mercosur countries. Second, what is the respective share of common and specific components of disturbances in the studied countries? Weak common components imply large exchange rate adjustments decreasing the feasibility of a currency union. They result either from the existence of asymmetric shocks across countries or from the absence of macroeconomic policy coordination. Third, taking into account the strong sensibility of LAC to boom-bust cycles in international capital markets, we try to determine to what extent international financial disturbances influence their business cycles.

A large body of empirical research focusing on the cyclical properties of Mercosur countries has been published. A first strand of literature uses different specifications to decompose cycles in specific and common components. [START_REF] Karras | The prospect of dollarization: are the Americas an optimum currency area?[END_REF] analyses real output fluctuations for Central and Latin American countries and for Canada with annual data over the period 1950-1997. The decomposition reveals that country-specific shocks in the Americas are both large and asynchronous. These countries are not an OCA. Using panel data econometrics, [START_REF] Loayza | Sectorial macroeconomic interdependencies: evidence from Latin America, East Asia and Europe[END_REF] build an error components model to estimate which fraction of annual real value-added growth in a given country can be attributed to country-specific factors -such as factor endowments or economic policies -or to common factors affecting all sectors and countries in a similar fashion, such as a financial crisis. The higher the proportion of variability in output growth rates explained by common factors -that is by country-independent factors-the higher the integration across countries is. For the period 1970-1994, the authors find that country-specific factors are dominant both in the short and long terms. A second strand of literature takes into account a larger macroeconomic framework with VAR or VECM models. [START_REF] Hallwood | An assessment of the case for monetary union or official dollarization in Argentina, Brazil, Chile, Uruguay and Venezuela[END_REF] use a bivariate VAR system in first difference applied to Mercosur countries. With quarterly data on output and price levels spanning the period 1980-2002, they find no common pattern of shocks. The low correlation of shock-disturbances between Mercosur countries and the United States suggests that dollarization of the region is not a good solution. Using a dynamic panel setting with annual data over the period 1983[START_REF] Cunningham | Emerging economy spread indices and financial stability[END_REF][START_REF] Ahmed | Sources of economic fluctuations in Latin America and implications for choice of exchange rate regimes[END_REF] analyzes the fluctuations in the main LAC. Two results are especially important. On one hand, LAC do not have real common shocks with their main trade partners, including the United States. On the other hand, US three month real interest rate shocks explain a significant share of output fluctuations in these countries. A currency union with the United States would increase the monetary and financial effects of real shocks affecting the US economy: as a result, output fluctuations in LAC would increase. [START_REF] Fanelli | Business cycle and macroeconomic policy coordination in MERCOSUR[END_REF] apply a bivariate structural VAR model in first difference -including quarterly date on a GDP and a combined prices index over the period 1980-2003-to identify the cycles and the coordination evidences within Mercosur. They deemed "symmetry" of shocks and try to shed some light on their sources. The authors try also to identify the common and specific components of domestic cycles, a question in focus in our paper. The results show that co-movements of shocks are weak; a similar trend is observed for the common component of disturbances.

Our paper differs from the previous literature on several points. First, our analysis focuses on the period following the creation of Mercosur. Indeed, not only the quality of data for long periods is low in emerging countries, but during the 80s the three economies were very instable, mainly due to the debt crisis and the bouts of hyperinflation: such disturbances make data processing very complex and unstable. So, our study begins in 1991 by taking into account more stabilized economies. Our approach of currency unions being based on business cycle dynamics, we use quarterly data which are only available and comparable since 1990 for the three countries. As a result, the paper uses quarterly frequency for the period 1991-Q1-2006-Q1. Second, we build a semi-structural VAR including more macroeconomic variables than previous studies. In comparison of works which decompose shocks only into their specific and common components, we are able to identify the nature of disturbances hitting these countries. At the opposite of bivariate VAR models, we take into account more diverse shocks such as external and domestic disturbances, but also policy shocks. The convergence of the policy-mix is one of the main pillars of an optimal monetary union, especially in its endogenous dimension. Third, the semi-structural VAR includes the EMBI spreads 4 as an international financial.

There is an abundant literature stressing, on one hand, the influence of external factors on capital inflows into emerging markets [START_REF] Calvo | Capital inflows and real exchange rate appreciation in Latin America, the role of external factors[END_REF]; Fernández-Arias (1995); [START_REF] Bruner | Why are capital flows so much volatile in emerging than in developed countries?[END_REF]), and, on the other hand, the destabilizing influence of these inflows on macroeconomic fluctuations in these countries [START_REF] Calvo | Crises in emerging market economies: a global perspective[END_REF]). In addition, several empirical studies dedicated to the effects of shocks originated from the United States show that financial transmissionvia monetary policy shocks-exerts a stronger influence than real transmission on LAC output variability 5 .

Few papers dedicated to the OCA take into account the EMBI in their analysis. [START_REF] Fanelli | Business cycle and macroeconomic policy coordination in MERCOSUR[END_REF] show that spreads exert a significant and negative influence on the common component of cycles in Mercosur countries. [START_REF] Berg | An evaluation of monetary regime options for Latin America[END_REF] question if LAC are frequently hit by large and common financial shocks. A positive answer could imply that monetary and exchange rate policies should react in a similar way in each country. As a result, a monetary union might be 4 . EMBI measures yield spreads (over 'safe' or 'risk free' assets which bear minimal credit risk) on emerging market countries' debt instruments. The spread is the extra return required to compensate the investor for the additional risks faced when investing in emerging economies rather than in a 'safe asset' (such as a US government bond). EMBI measures the sovereign risk. Spreads increase with the deterioration -effective or expected-of fundamentals in the countries issuing bonds; they also increase in periods of international financial strains. 5 . See [START_REF] Carrera | How does dollarization affect real volatility? A general methodology for Latin America[END_REF] for Argentina over the period [START_REF] Taylor | Income distribution, inflation and growth: lectures on structuralist macroeconomic theory[END_REF][START_REF] Cunningham | Emerging economy spread indices and financial stability[END_REF][START_REF] Canova | Vector autoregressive models: specification, estimation, inference, and forecasting[END_REF] for a sample of central and Latin American countries over the period 1990-2002. appropriate. The authors use a correlation matrix to identify the common components of all domestic spreads 6 . Their main result is that the degree of co-movements of financial variables is not higher among LAC than it is among other emerging markets. Uribe and Ye (2006) build a VAR system based on panel data set with seven emerging countries covering the period 1994-2001 at a quarterly frequency to analyze the respective influence of US interest rates and EMBI shocks on the macroeconomic fluctuations. An important finding is that EMBI shocks exacerbate the US interest rate shocks, implying a strong macroeconomic volatility in the studied emerging countries.

Last but not least, we propose to break down structural innovations of domestic semi-structural VAR into unobservable common and idiosyncratic components using a state-space model [START_REF] Harvey | Forecasting. Structural times series models and the Kalman filter[END_REF].

These models respond to the drawbacks of the previous literature of which the quasi-totality concentrates on the correlation of shocks without disaggregating the shocks in specific common and components constituent in every country. These results are used to check evidence of economic synchronicity, and convergence of macroeconomic policy The remainder of this paper is organized as follows. Section two presents the outcomes of the estimates of a semi-structural VAR model for each economy; it identifies the interdependence between domestic macroeconomic variables and to external ones, and the sources of disturbances. Section three uses a state-space model to estimate to what extent the shocks -and especially macroeconomic policy shocks-have a common component allowing for speculation about coordination between Mercosur countries. Section four concludes.

A semi-structural VAR model for the "Mercosur"

Literature on regional integration and OCAs stresses the identification of common shocks, the degree of similarity in the adjustment process of the candidates and the convergence of policy responses to shocks. This section aims at deepening these points.

In the context of strong links of macroeconomic variables with complex feedback linkages, the Vector autoregression (VAR) approach constitutes a useful tool, allowing to capture the evolution and the interdependences between multiple time series. All the variables are treated symmetrically, including for each variable an equation which explains its evolution based on its own lags and the lags of all the other variables in the model. [START_REF] Sims | Macroeconomics and reality[END_REF] advocates the use of unrestricted VAR models as a theoryfree method to estimate economic relationships: contrary to the structural method based on the choice of a particular model, this procedure embodies alternative theories "nested" in the empirical model 7 . 6 . They first regress each individual country's spread series in the overall EMBI+ spread series, and save the residuals. Second they report the correlation matrix among these country-specific components of the spread series. 7 As indicated in [START_REF] Canova | Vector autoregressive models: specification, estimation, inference, and forecasting[END_REF], the analyst's prior knowledge is used only to decide what variables should enter the reduced form and, in some cases, the time series transformations to be used (log or ratios of variables).

The VMA (vector moving average) representation of the reduced form allows us to express the current and past values of the shocks, to trace out their time path on the variables contained in the VAR system, and to compute the impact multipliers (deduced from the impulse response functions). The forecast error variance decomposition indicates the proportion of the movement in a sequence due to its "own" shocks versus shocks to the other variables8 . Thus, the convergence of evidence revealed by the tests, the impulse response functions, the forecast error variance decomposition and other forecasting properties give us some guidelines to choose between alternative theories. One of the main issues of these experiments comes from the identification of shocks. If the error terms of the VAR reduced form are correlated, there is no simple way to unambiguously identify shocks with specific variables, for the errors will have common components that affect more than one variable. The practitioner will have to attribute the effects of common components to one specific variable… biasing the interpretation of the impulse responses or of the forecast error variance decomposition: in short, the choice of procedure of identification, i.e. the procedure of shocks orthogonalization, must be based on some "a priori" knowledge. The Cholesky ordering is the usual and least theoretical method to orthogonalize shocks (this kind of "half" structural VAR is usually called either recursive VAR or RVAR, or, as in [START_REF] Doan | Rats Version 6, User's Guide, Estima[END_REF], semi-structural VAR or SSVAR): however, the ordering is not really arbitrary, based on theoretical intuition. Another way is to introduce theory in these "a-theoretical" VAR models by the inclusion of theoretical restrictions in the "structural" VARs (SVARs).

We choose a recursive "Semi-Structural" approach for a VAR in difference. The former choice is justified below; the later one -a VAR in difference -is deduced from the Johansen test results, pointing out the lack of empirical support in favor of any cointegrating vector between the selected endogenous variables9 .

Variable selection 10

Our choice of variables is the traditional one for VARs analyzing external shocks, and macroeconomic packages in open economies (Favero (2001), Lütkepohl andKrätzig (2004)). For the external variables, we chose (i) the Industrial Product Index of Industrialized Economies (noted I_IPI), and (ii) the Emerging Economy spread index of J.P. Morgan (EMBI) 11 , a way to account for the main real supply and financial shocks. For the domestic variables (noted for each country "i", I = A, B, U) , we took Industrial Product Index (i_IPI), Consumption Prices Index (i_CPI), the nominal money market interest rate (i_R) 12 and the direct quotation of the nominal foreign exchange rate with the US $ as base currency (i_EN).

We begin by checking -for each country -the stationarity of the interest rates and the EMBI, and of the logarithm of all the other variables. Standard Augmented Dickey Fuller tests are largely perturbed by numerous shocks, periods of high inflation, stabilization programs, and change in monetary, currency, or fiscal regimes. But even after correction of structural breaks (Perron (1989)), all data are I(1), except interest rates and EMBI which are apparently I(0). As explained above, tests of cointegration (Johansen) failed to find any cointegrating vector 13 . Anyway, given the size of our data sample, the robustness test for stationnarity and cointegration are likely to be weak: we therefore followed economic theory to guide our choices.

Amongst the available procedures to identify innovations, we did not chose an SVAR methodology.

First, assuming a long term neutrality of nominal shocks would seem widely arbitrary for a work covering about twelve or so years, even if business cycles are shorter for these countries than for the industrialized ones 14 . So, contrary to numerous similar works, we don't apply the "BQ" decomposition identification procedure based on long run restrictions [START_REF] Blanchard | The dynamic effects of aggregate demand and supply disturbances[END_REF]) 15 . Second, the inspection of the contemporary correlation matrix of the reduced form residuals (see appendix 1) doesn't justify the rejection of a recursive factorization based on a lower triangular matrix in order to identify the short run restriction.

In fine, the following order of Choleski factorization is deduced from our theoretical interpretation of the contemporary correlation matrix of the reduced form residuals of each country model. External variables are considered here as the most exogenous. For the domestic variables, two schemes have been selected, depending on the dominant exchange rate regime for the period of estimation. So, the order of the variables for Argentina from the most to the least exogenous will be: I_IPI, EMBI, A_EN, A_R, A_CPI and A_IPI. On the other hand, for Brazil and Uruguay, we choose the order I_IPI, EMBI, i_CPI, i_R, i_EN and i_IPI (with i=B,U). The assumption of an exogenous EMBI is shared by a majority of economists -in spite of the weight of Mercosur economies in this index -even if domestic indicators (fiscal deficit, monetary instruments, payment deficit…) can have some influence on the EMBI+. In 1999, J.P.Morgan releases a new index, the EMBIG (for "global") embodying more countries (27) and more titles. In this last index, LAC decreased to 61.5%. 12 The domestic interest rate is the money market one: it is not exactly equivalent of the Federal Fund Rate… but it is the only one available for this sample. 13 . All the tests are available upon request to the authors. 14 Look at [START_REF] Allegret | Disentangling business cycles and macroeconomic policy in Mercosur: a VAR and unobserved components model approaches[END_REF]. 15 Leeper and [START_REF] Faust | When do long-run identifying restriction give reliable results?[END_REF] criticize the wide use of long run restrictions to study the sources of business cycles because of the weak reliability of structural inference for finite samples. In particular, "unless strong restrictions are applied, conventional inferences regarding impulse responses will be badly biased in all sample sizes". country specific spreads 16 . As explained, the ordering can be different for domestic variables. The contemporary correlation matrix of the reduced form residuals for Argentina points out the strong correlation of Argentinean interest rates with other domestic variables: we interpret this outcome as the consequence of the Currency Board regime with a passive monetary policy (and an exogenous interest rate with respect to prices and output); obviously, prices had no influence on a strictly pegged exchange rate. So, we consider here the output (or more exactly its proxy, the A_IPI) as the main adjustment variable in such way that in our model, it is the most endogenous.

In Brazil and Uruguay, we consider prices as the most exogenous domestic variable: these countries have a long tradition of price indexation (the succession of stabilization packages managed to break pessimistic forward expectations of the accelerating inflation times; but it could not eliminate completely backward rigidities) 17 . So, the policies of both these economies continue to be mainly driven by price stability targeting, even if the intermediary exchange rate regime allows a soft peg. As for Argentina, the output can be consider as an adjustment variable, i.e. the most endogenous in both country models.

The model

We estimated a VARs model in log difference of the variables (except interest rates and the EMBI) for each country. The number of lags in each model has been selected using the common set of criteria and tests (available on the software Eviews 5 and RATS 6). However, it is well known that conventional VAR estimation frequently leads to an over-parametrization (because of the number of explanatory variables and lags). Moreover, the VARs are subject to strong colinearity amongst the lagged right side variables: so, the significance of parameters and more generally the robustness of tests are relatively limited. In short, over parametrized models have poor forecasting accuracy 18 . So, in the presence of contradictory results (given by the usual criteria), we followed the parsimony principle and accepted one lag for every country case.

For each country "K", the standard (reduced) form of our VAR with constant is the following :

1) for Argentina:

( )

_ ( 1 , 1 ) ( 1 , 6 ) ( , ) _ _ _ ( 6 , 1 ) ( 6 , 6 ) ln_ _ ( ) ln_ _ ( ) ln_ _ ( ) _ ( ) ln_ _ ( ) ln_ _ ( ) I IPI EMBI En i j A A R A CPI A IPI C C C I IPI t I IP C EMBI t C C A En t vec DUM C A R t C A CPI t C C C A IPI t ∆ ∆ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ∆ = + + ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ∆ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ∆ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ _ _ _ _ ( 1) ( 1) ln_ _ ( 1) _ ( 1) ln_ _
( 1) ln_ _ ( 1)

- ⎛ ⎞ ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ - ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ∆ - + ⎜ ⎟ ⎜ ⎟ - ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ∆ - ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ∆ - ⎝ ⎠ ⎝ ⎠
2) for Brazil :

( ) ( ) _ ( 1 , 1 ) ( 1 , 6 ) _ ( , ) _ _ _ ( 6 , 1 ) ( 6 , 6 ) ln_ _ ( ) ( ) ln_ _ ( ) 1 _ ( ) ln_ _ ( ) ln_ _ ( ) I IPI EMBI B En i j B B R B CPI B IPI C C C I IPI t C EMBI t C C B CPI t vec DUM vec t C B R t C B En t C C C B IPI t ∆ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ∆ = × + + + ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ∆ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ _ _ _ _ ln_ _ ( 1) (
∆ - ⎛ ⎞ ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ - ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ∆ - + ⎜ ⎟ ⎜ ⎟ - ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ∆ - ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ∆ - ⎝ ⎠ ⎝ ⎠
3) for Uruguay:

( )

(1,1) (1,6) ( , ) _ _ _ ( 6 , 1 ) ( 6 , 6 ) ln_ _ ( ) ln_ _ ( ) ln_ _ ( ) _ ( ) ln_ _ ( ) ln_ _ ( ) IPI EMBI En i j U A R A CPI A IPI C C C I IPI t I IPI C EMBI t C C U CPI t vec DUM t C U R t C U En t C C C U IPI t ∆ ∆ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ∆ = + + + ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ∆ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ _ _ _ _ ( 1)
( 1)

- ⎛ ⎞ ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ - ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ∆ - + ⎜ ⎟ ⎜ ⎟ - ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ∆ - ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ∆ - ⎝ ⎠ ⎝ ⎠
In order to account for specific country shocks during the period, and for the evidence of a deterministic trend affecting the set of variables-before the Real Plan for Brazil and in the whole period for Uruguay, we added the following dummies:

- One has to keep in mind that our three economies have adopted different exchange rate regimes.

Furthermore, these have later evolved, following independent paths for the period. In short:

-from 1991 to 2001, Argentina was ruled by a currency board (hard peg) and then by an independent regime of floating;

-from 1991 to 1997, Brazil has adopted a crawling band regime (a kind of real exchange rate targeting) more or less "de jure" and more or less narrow, according to the context: in the following lines, we identify this regime as an intermediate exchange rate regime. After the strong currency crisis, in January 1999, Brazil implemented a flexible exchange rate regime combined with inflation targeting.

-From 1991 to 2001, Uruguay adopted an intermediate exchange rate regime based on crawling bands. In June 2002, the authorities decided to implement a floating regime.

Using this framework, we propose now to combine the impulse response functions (tracing out the time paths of the effects of "pure" shocks on the set of variables) and the forecast error variance decomposition (indicating the proportion of the movements in a sequence due to its "own" shocks versus to the other variables). These experiments aim at identifying what kind of shocks, real or nominal, drive economic fluctuations in the three countries. It allows us to make an assessment of the similarities in the reactions of macroeconomic variables to these shocks. By the way, we will get a first outline of the specific -versus common -economic consequences of shocks in terms of "spontaneous" adjustments and moreover in term of policy responses.

The results are presented in Appendix 2 and 3. When there is high correlation between some pairs of the reduced form residuals, the results can depend on the variable ordering in the Choleski factorization. So, we have tested the sensitivity of our results to alternative orders but we did not note significant changes in the conclusions for the more plausible permutations.

Results

Results analyzed hereafter refer to the most significant responses of domestic variables to shocks included in our VAR system.

Responses of domestic variables to an external real shock: the I_IPI shock

In the three countries, domestic industrial production increases after a shock on IPI of industrial countries. Conjuncture in industrial countries exerts an influence on business cycles in Mercosur countries. Variance decompositions (see Appendix 3) show that this influence is especially strong for Argentina: after 6 periods, I_IPI innovations explain between 13 and 16% of the A_IPI variance.

Brazil -as a relatively closed economy-and Uruguay -where the dependence on US conjuncture is more pronounced-do not exhibit such influence of the I_IPI. The responses of domestic interests rates differ according to the exchange rate regime. Thus, in Brazil, the shock on I_IPI induces a strong increase in interest rates during the first two quarters, followed by a smooth adjustment towards the initial equilibrium. On the other hand, Argentinean interest rates decreases after the shock. We interpret this asymmetric response of interest rates in the two main Mercosur countries as a consequence of the exchange rate regimes on inflation expectations. More precisely, the Argentinean currency board gives the economy a stronger nominal anchor. As a result, inflationary pressures in Argentina are less present than in Brazil.

In these two countries, I_IPI innovations explain more than 10% of the domestic interest rates variance. For Argentina, the influence is especially important with a persistence effect: the share explained by I_IPI increases with the number of periods.

Responses of domestic variables to international financial shock

Responses to shocks and variance decompositions allow us to draw some general lessons suggesting that Argentina is especially sensible to the EMBI shock.

Two factors explain the specific vulnerability of Argentina to the pure international financial shock.

On one hand, over the studied period, Argentina has been one of the main borrower in international capital markets. Until the end of the 1990s', Argentina benefited from very favorable conditions to borrow. So, capital inflows increased during this period. After 1999, its spread dramatically increased.

Argentina suffered from a sudden-stop of capital inflows [START_REF] Calvo | Sudden stops, the real exchange rate, and fiscal sustainability: Argentina's lessons[END_REF]) whose main consequence was a drop in domestic output. As a result, in comparison to the two other countries, the Argentinean economy appears especially sensible to EMBI fluctuations. On the other hand, the monetary policy constraints due to the currency board limit the ability of authorities to react in face of EMBI shocks, inducing strong and ample macroeconomic variability. From this point of view, the exchange rate regime exacerbated the sudden-stop problem. While in countries with floating exchange rates the domestic currency tends to depreciate after an increase in the EMBI, in hard peg countries such as Argentina, the impact of the shock is more pronounced on consumption prices and industrial production: prices and production decrease after the EMBI shock.

In the two countries with intermediate regimes, responses of domestic variables and their variance decompositions suggest that prices, production and interest rates are not significantly affected by the international financial shock. Brazilian and Uruguayan exchange rates are influenced by this shock. In the two countries, the domestic money depreciates after the shock. The exchange rate absorbs in part the negative impact of the international financial shock. This explains the weak responses of other domestic variables to this shock. We observe the opposite for Argentina. Thus our results exhibit a clear distinction between countries with soft pegs and countries with hard pegs.

Responses of domestic variables to real domestic shock

In the three countries, domestic IPI shocks do not lead to significant responses of other variables.

Variance decompositions bring out the fact that no other domestic variable has its variance in part explained by IPI innovations. Over the studied period, the industrial production is an adjustment variable. This similarity across our three countries is explained by monetary policy constraints faced by domestic authorities either in the case of a hard peg (Argentina) or in the case of an economic policy based on the fight against inflation (Brazil and Uruguay).

Responses of domestic variables to nominal domestic shocks

We consider a shock on CPI (Consumption Price Index) as a nominal demand one. This shock allows us to discriminate between hard peg and peg countries. In addition, it appears that Brazil and Uruguay -the two economies with soft pegs-react differently to this shock.

Argentina exhibits a rapid adjustment without major fluctuations of other domestic variables. Variance decompositions of domestic variables show that A_CPI innovations explain only its own variance, whatever the considered period. This lack of reaction is a consequence of the effect of the currency board on the inflation anchor.

In countries with soft pegs, inflation expectations are imperfectly anchored. So, in Brazil and Uruguay, shocks on prices induce higher fluctuations than in Argentina. In Brazil, the shock is short lived, less than two quarters, while it is strong and persistent in Uruguay suggesting the existence of nominal rigidities in the later. In both countries, the shock is followed by a recession (a decline in IPI): higher prices go with pessimistic expectations. Interest rate responses are strong in the short term, and the adjustment is slow especially in Uruguay. This path is explained by a weaker credibility of monetary policy. Monetary authorities are constrained to react quickly in order to prevent the development of indexation mechanisms. On nominal exchange rates, we have a significant depreciation over different horizons: a very short term response in Brazil (less than one quarter) and a longer impact for Uruguay (more than four quarters). In both countries price innovations explain a significant share of the exchange rate variance. These links between prices and exchange rates could mean that these two countries had a real exchange rate target in the 1990s'. As a small open economy, this target has been especially important in Uruguay.

Responses of domestic variables to domestic monetary policy shocks

The innovations on nominal interest rate are monetary policy shocks. The adjustments after an interest rates shock differ according to the exchange rate regime: very fast in Argentina (less than one quarter); four quarters (Brazil) or more (Uruguay) for intermediate exchange rate regime countries. Thus the resilience of the monetary policy shock seems higher in this second group of countries. Two opposing interpretations of this different path are conceivable: first, an insufficient credibility of monetary policy in economies with soft pegs; second, a more reactive monetary policy as a result of the less binding exchange rate regime. The analysis of the responses of other domestic variables leads us to consider that the first explanation is the most relevant: even in countries with intermediate regimes, monetary policy reacts little to non-inflationary shocks revealing a "fear of floating" behavior [START_REF] Calvo | Fear of floating[END_REF]).

The responses of consumption prices contrast in the three countries. No price puzzle appears in Argentina and Uruguay: prices decrease after the interest rate shock. On the other hand, not only Brazilian prices increase as a result of the shock, but the return towards equilibrium appears after five quarters. Prices movements can be interpreted as a Cavallo-Patman effect where higher interest rates increase production costs via the financing needs of working capital, leading to inflationary pressures (Taylor (1981)). The variance of B_CPI is strongly explained by interest rate innovations: 31% in period 2; 38-39% after period 6. The increase in the interest rate in Brazil can be interpreted as the result of a credibility loss in a context of fear of inflation. From this point of view, the interest rate is overall an indicator of inflationary pressures neither than a response to them [START_REF] Favero | Why are Brazil's interest rates so high?[END_REF]).

Nominal exchange rates exhibit weak responses in Argentina and Uruguay. On the contrary, the reaction is strong and long-lasting (approximately four quarters) for Brazil. The nominal exchange rate follows a traditional overreaction mechanism: appreciation at the impact, then strong depreciation. We interpret the evolution as an insufficient credibility of the monetary authorities. According to variance decompositions of nominal exchange rates, innovations on interest rate do not explain a significant part of their variance, except in Brazil.

Responses of domestic variables to nominal exchange rate shocks

The response of production in Brazil is weak. This result is consistent with the main characteristics of the Brazilian economy: low openness and dollarization degrees. In addition, exchange rate innovations do not explain the variance of other domestic variables. In Argentina and Uruguay, IPI decreases after the shock, but with a lagged effect in the latter country. Indeed, dollarization in these two economies implies that domestic currency depreciation produces a negative balance sheet effect. The dollarization of external debt in Argentina explains the stronger response of IPI 19 . Exchange rate innovations explain 13% of the A_IPI variance contemporaneously and 10-11% after six periods.

Responses of prices suggest that pass-through effects are either absent (Argentina and Uruguay) or short-lived (Brazil). These results reinforce other studies which stressed the decrease of the exchange rate-domestic prices transmission in LAC since the 1990s' [START_REF] Larrain | Exchange-rate policy in emerging-market economies: the case for floating[END_REF]).

Interest rate responses are weak and insignificant (see variance decompositions) in Brazil and Uruguay. As expected under currency board arrangement, Argentinean interest rates react strongly at the impact of the shock. They increase in the two first quarters.

The main implication of our results from our semi-structural VAR is the following: 19 . Using the classification proposed by Reinhart, Rogoff and Savastano (2003), Argentina and Brazil belong to Type I dollarization -in which domestic and external liability dollarization co-exist-while Uruguay is a dollarized economy of Type II where dollarization is predominantly of a domestic nature. The degree of dollarization is different between these countries: high in Argentina (index 20 on a scale that goes from 0 to 30) and Uruguay ( 21), but moderate in Brazil (7).

Countries with intermediate exchange rate regimes seem more sensitive to nominal shocks while our hard peg country (Argentina) strongly responds to external financial shock (EMBI shock). In other words, the diversity of the exchange rate regimes among Mercosur countries explain the fact that these countries are vulnerable to different shocks and that the domestic dynamics are different after the shocks. Second, our three countries have a similar characteristic: industrial production exerts a weak influence on other variables.

From this point of view, Argentina, Brazil and Uruguay do not constitute an optimal currency area.

Our space-state model will confirm this outcome.

Identification of common and country specific components of structural shocks using a state-space model

The main purpose of structural VAR estimation is to get non-recursive orthogonalization of the error terms for impulse response analysis and variance decompositions of forecast errors. Whatever the identification restrictions (short or long run), and their theoretical (or "a-theoretical") foundations (choice of an "ad-hoc" scheme of identification, or decomposition " à la Blanchard et Quah" contrasting demand and supply shocks on the basis of long run neutrality on the supply side), these experiments don't allow the distinction between common and specific components of fluctuations and shocks. However, this distinction, and overall the weight of common component, are the fundamental criteria of judgment in the choice of economic and monetary integration. Following the OCA theory, a too light weight of common component implies significant adjustment of exchange rates in the case of strong shocks. Such adjustments are difficult to endure in a simple free trade area. Moreover, it becomes impossible in the case of a common monetary zone. In short, any integration process implies symmetry, i.e. a large common component.

In order to assess the share of the common and idiosyncratic components in the variability of the structural shocks (policy shocks included), we propose a breakdown in two unobservable stochastic components using the Kalman filter (Harvey (1989), [START_REF] Kim | State Space Models with regime switching[END_REF]). The same method has been used by [START_REF] Bosco N'goma | Analyse des chocs d'offre et de demande dans la zone CFA: une méthode structurelle d'autorégression vectorielle[END_REF] for members of CFA Zone, by Chamie, Desserres, and Lalonde (1994) for a comparison between Europe and the USA, or by Lalonde and St-Amand (1993) for ALENA. We report here a sum up of the explanations proposed by this set of papers.

Methodology

The state-space models distinguish observed variables (the "signal" or "observation") and unobserved variables ("state" variables). They are composed of two sets of equations:

One or several "signal " (or "measurement") equations relating the observable variables to the unobservable states ;

One or several "state" (or "transition") equations describing how the vector of "states" evolves over time.

In this part, we aim at breaking down shocks affecting jointly the three members of Mercosur -or any pair of them -into two unobservable components: a common component for the three countries -or at least for two of them-and an idiosyncratic component, specific for each country. We note :

the three members by i= A, B and U respectively for Argentina, Brazil and Uruguay ; In our state-space model, the following equations:

( ) ( ) ( ) _ , _ _ _ , _ , _ , _ _ _ , _ , _ _ _ , 1 0 0 0 1 0 0 0 1 C IPI t A j A j A j t A IPI t B j t B j B j B IPI t U j t U j U j U IPI t n n n n α α ε ε α α ε α α ⎡ ⎤ ⎡ ⎤ - ⎛ ⎞ ⎢ ⎥ ⎢ ⎥ ⎜ ⎟ ⎢ ⎥ ⎢ ⎥ = - ⎜ ⎟ ⎢ ⎥ ⎢ ⎥ ⎜ ⎟ ⎢ ⎥ ⎝ ⎠ - ⎢ ⎥ ⎣ ⎦ ⎢ ⎥ ⎣ ⎦
constitute the measurement (or transition) system, with the structural innovations -stemming from the decomposition of our reduced form VAR residuals -as endogenous variables.

To estimate the parameters _ i j α and the series _ , C j t n and _ , i j t n , we need a set of transition equations, specifying the dynamics of the unobservable components. For identification purposes, we assume that common and specific components are uncorrelated. In a large number of software packages -and in particular Eviews 5 and Rats 6, used here -the identifying restrictions assume normalized structural innovations _ , i j t ε , with unit variance. This normalization facilitates the comparison of structural shocks, stemming from our different country VARs estimated separately! We will also assume unit variance for the unobservable components. While determining the stochastic components path through the definition of their distributions, this assumption defines the transition equations. So, we can write as "state" system:

_ , _ , _ , _ , _ , _ , _ , _ , ( ) 0 0 0 0 ( ) 0 0 0 0 ( ) 0 0 0 0 ( ( ) 1
( ) 1
( ) 1
⎤ ⎢ ⎥ ⎢ ⎥ Ω = ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎧ = ⎪ = ⎪ ⎨ = ⎪ ⎪ = ⎩
) Finally, we must choose a reference country shock to which the other shocks will be compared: we will choose Argentina when Argentina is present (and Brazil in the other cases) and start estimation initializing _ 1 i j α = . The Kalman filter algorithm will be used to decompose the structural shock and idiosyncratic and (if they exist) common components.

Results

The main result is that we can never observe any significant common component for the three countries20 ! But for some variables, the estimation showed the presence of common components for pairs of Mercosur countries.

So, in the case of CPI, the inflation path has a weak but significant common component of 9% for In brief, it is difficult to exhibit an unambiguous and significant macroeconomic convergence of the three Mercosur partners, either in terms of weight or in terms of statistical significance. In particular, the exceptional macroeconomic volatility of Uruguay during the period conceals any foreign influence. Argentina and Brazil, which have known a significant trend of trade integration before the Brazilian crisis of 1998-1999, and shared common waves of speculative attacks after the collapse of the Argentinean currency board seem to exhibit symptoms of common shocks.

Argentina and Brazil

But finally, in spite of the evidence of common shocks linked to world conjuncture or to speculative behavior on the international financial market, the policy mix of the Mercosur members remains strongly specific.

Conclusion

Our results converge to indicate that the Mercosur countries are not predisposed to form a monetary union either between them, or with the United States. First, the SSVAR proves the weak coordination of economic policies between these countries. In particular, identical nominal shocks involve different adjustment paths. This low level of synchronization and policy coordination is confirmed by the "state-space" models: the latter displayed the weak common component of the various shocks involved in the experiments. Second, including a typical common international financial shock -here the EMBI -suggests one more time idiosyncratic responses: obviously, the variety of exchange rate regimes and policies in the area during this period did not ease convergence and coordination!

In short, our results stay in line with the whole literature on the Latin American integration process.

Furthermore, it confirms the theoretical analyses relative to the place of exchange rate regimes adjustments in the face of macroeconomic shocks.

It must be stressed that these results stem from SSVAR studies including more variables than the majority of papers published on the subject. However, these analyses must be deepened in some privileged directions. First, accounting for the EMBI allowed us to provide a better assessment of the world financial shocks impact on the feasibility of monetary unions; but domestic consequences of structural breaks -linked to these shocks -continue to be imperfectly grasped: in particular, we did not embody explicitly implications of the "sudden stop" hitting Latin American economies during these times. A hint would be to include some of the more relevant variables allowing to account for these facts: trade balance, current accounts, or international reserves could be used to test the impact of "sudden stop" of capital inflows on trade balance and output. Second, our set of variables did not exhibit any cointegrating vector: it is probably due to the presence of structural breaks. A next step will be to deal with this issue in order to build a VECM (Vector Error Correction Model) able to embody short and long run dynamics, allowing us to focus on respective speeds of adjustment: indeed, very different speeds of adjustment could prejudice any project of monetary integration (except obviously for the endogenous OCA perspective).

Appendix 1 Residuals correlation matrix of reduced forms of SSVAR estimations.

  DUM A for the first semester of 2002 in Argentina, to account for the Currency Board collapse; -DUM B from 1990Q1 to 1994Q2 in Brazil, to account for the period of accelerating inflation, up to the Stabilization Real Plan, -DUM U for the whole year 2002 in Uruguay: after three years of economical and political mayhem from 1999 to 2002, the combination of political uncertainty -with the expectations of the left-wing party success in the national elections -and external shocks -due to Argentinean and Brazilian instability -has heavily affected the Uruguayan variables.

Table 1

 1 Decomposition of inflation innovations for Argentina and BrazilWe can find a common component nearly equivalent in the case of the nominal exchange rate for Argentina and Brazil. Considering the differences in both the exchange rate regimes during the better part of the period, it could seem paradoxical. But it accounts for the common volatility of the years 2001-2002 triggered by the Argentinean crisis and worsened by the political uncertainty in Brazil.

	CPI_MB_AB	Coefficient Std. Error z-Statistic Prob.
	C(1)	0.992180	0.068671	14.44830	0.0000
	C(2)	0.088781	0.036808	2.412014	0.0159

Table 2

 2 Decomposition of innovations for nominal exchange rates in the case of Argentina and Brazil

	En_MB_AB	Coefficient Std. Error z-Statistic Prob.
	C(1)	0.992144	0.042701	23.23442	0.0000
	C(2)	0.088986	0.037234	2.389951	0.0169
	At last, we find also a weak -but significant -common component of 15% for both the main
	economies of Mercosur.

Table 3

 3 Decomposition of innovations for domestic industrial growth rate in the case of

		Argentina and Brazil
	IPI_MB_AB	Coefficient Std. Error z-Statistic Prob.
	C(1)	0.979247	0.049178	19.91226	0.0000
	C(2)	0.145616	0.072461	2.009569	0.0445

Curiously, Uruguay doesn't exhibit these features: but the extent of idiosyncratic domestic volatility during the period displayed by the primary data (see

[START_REF] Allegret | Disentangling business cycles and macroeconomic policy in Mercosur: a VAR and unobserved components model approaches[END_REF]

) probably conceals a large part of the foreign perturbations spillover.

However, the outcomes are slightly different for nominal interest rates: as shown in the following table, Brazil and Uruguay exhibit a small common component (about 8.5%).

Table 4

 4 Decomposition of innovations for domestic interest rate in the case of Brazil and Uruguay

	R_MB_BU	Coefficient Std. Error z-Statistic Prob.
	C(2)	0.993101	0.050234	19.76943	0.0000
	C(3)	0.083350	0.041380	2.014267	0.0440

. For date availability reason, our study covers only three countries : Argentina, Brazil, and Uruguay.

Look at Enders (2004), for a very didactical explanation.

In this case,[START_REF] Allen | Levels, differences, and ECM: principal for improved economic forecasting[END_REF] showed that any alternative solutions -VAR in level, or VECM -would lead to greater forecast errors.

All data are quarterly and proceed from the International Financial Statistics (IMF) except the EMBIs published by the Ministery of Economy and Production of the Republic of Argentina (http://www.mecon.gov.ar/peconomica/basehome/infoeco_ing.html) and the IPI Uruguayan published by the Central Bank of the Republic of Uruguay (http://www.bcu.gub.uy/).

We merged two time series: the EMBI for the period 1991Q1-1997Q4 and the EMBI+ from 1998Q1. As indicated in[START_REF] Cunningham | Emerging economy spread indices and financial stability[END_REF], the main differences between these indices are (i) the number of financial instruments embodied (the EMBI tracks returns and spreads on Brady Bonds and some other restructured sovereign debts, the EMBI+ tracks returns on a wider range of instruments), (ii) the number of countries (11 for the EMBI, 16 for the EMBI+). However, in both the indices the weight of the LAC (Latin American countries) is very important (respectively 83.8% and 70.2%). Amongst the LAC, both Argentina and Brazil weight 47.6% of

Fernández-Arias and Panizza (2001) ; González-Rozada andLevy-Yeyati (2005).

On these points, look atSand-Zantman and Trotignon, 2002, for the Brazil, and[START_REF] Clavijo | Terminios de Intercambio y salario real[END_REF][START_REF] Clavijo | Terminios de Intercambio y salario real[END_REF], for Uruguay.

We excluded a Bayesian approach (BVAR), a way to deal with a great number of parameters (here those of lagged variables), thanks to prior information: in our case, such a bet could have been more arbitrary and hazardous[START_REF] Amisiano | Topics in structural VAR Econometrics[END_REF]).

The foreign variables, the IPI for industrialized countries and either the EMBI, are endogenous in each one of our country models: so we can deduce orthogonal shocks for both these variables. Obviously, looking for a common component in these case doesn't present any theoretical interest. But allowed us to check the efficiency of the Kalman Filter: we found indeed the predicted result of a strong significant common component in every case.