Structure Learning of Sparse GGMs over Multiple Access Networks
Mostafa Tavassolipour Armin Karamzade Reza Mirzaeifard Seyed Abolfazl Motahari Mohammad-Taghi Manzuri Shalmani

















Structure Learning of Sparse GGMs over Multiple Access  Networks
    Mostafa Tavassolipour,
        Armin Karamzade,
        Reza Mirzaeifard,
        Seyed Abolfazl Motahari,
         and Mohammad-Taghi Manzuri Shalmani
    December 30, 2023
===========================================================================================================================================================




A central machine is interested in estimating the underlying structure of a sparse Gaussian Graphical Model (GGM) from datasets distributed across multiple local machines. The local machines can communicate with the central machine through a wireless multiple access channel. In this paper, we are interested in designing effective strategies where reliable learning is feasible under power and bandwidth limitations. Two approaches are proposed: Signs and Uncoded methods. In Signs method, the local machines quantize their data into binary vectors and an optimal channel coding scheme is used to reliably send the vectors to the central machine where the structure is learned from the received data. In Uncoded method, data symbols are scaled and transmitted through the channel. The central machine uses the received noisy symbols to recover the structure. Theoretical results show that both methods can recover the structure with high probability for large enough sample size. Experimental results indicate the superiority of Signs method over Uncoded method under several circumstances. 





Structure learning, Gaussian graphical model, distributed learning







§ INTRODUCTION
 
In recent years, by the explosion of the volume of training data, distributed machine learning has become more important than ever. Many modern big datasets are distributed over several hosting machines which are connected to each other via some communication links. In such systems, designing distributed learning algorithms which efficiently exploit the available resource demands a careful design where intensive computational workloads and the amount of data communications are taken into account.

This paper is focused on the problem of structure learning in Gaussian Graphical Models (GGMs) in distributed environments. A GGM for a d-dimensional random vector x = (x_1, ⋯, x_d)^T ∈ℝ^d is specified by a graph 𝒢(𝒱, ℰ) where 𝒱={1,⋯, d} is the set of vertices and ℰ⊆𝒱^2 is the set of edges. The model comprises all d-dimensional normal distributions 𝒩(μ, Θ^-1) where Θ is the precision  matrix with Θ_jk≠ 0 iff (j, k) ∈ℰ. It worths mentioning that GGM is indeed a Markov Random Field (MRF). 

In our problem setting, we assume that the data are distributed over multiple local machines so that each one contains a single dimension of the whole dataset. The local machines are connected to a central machine via a wireless medium. The central machine is responsible for inferring the conditional dependencies between the gathered data by the local machines. The system's block diagram is depicted in  <ref>. We also assume that the communication links between the local and the central machine are bandwidth limited implying that transmission of the whole local datasets to the central machine is impossible. Due to this constraint, each local machine transmits some information from its local dataset to the central machine. Then, the central machine estimates the underlying graph structure using received information from the local machines.



In this paper, we consider a wireless multiple access channel between the local machines and the central node. Each local machine is equipped with a single antenna while the central node is equipped with multiple antennas. Hence, the overall channel between the local and central machines is modeled as a single-input multiple-output multiple access channel (SIMO-MAC).

We have proposed two communication schemes for transmitting information from the local machines to the central machine. In the first scheme, we have separate the source coding from the channel coding. In this scheme, we quantize the source samples into single bits and assume that there exists a channel coding such that the bits can be sent through the channel reliably. We refer to this scheme as Signs method in the paper.

In the second scheme, we do not use any source and channel coding. In this scheme, we put the source samples into the channel without any encoding. At the central machine, we directly estimate the underlying graph structure using received data from the channel. We refer to this scheme as Uncoded method.

We have shown through theoretical analysis and experiments that by transmitting only 1 bit per sample; the central machine can reliably recover the underlying graph structure. More precisely, we have shown theoretically that by consuming only 1 bit per sample, under some mild conditions, the central machine can perfectly recover the graph structure with high probability. Moreover, the true signs of the edges weights of the graph are obtained.

The paper is organized as follows. In Section <ref>, we provide a brief review on structure learning of GGMs. Section <ref> describes the detail of our modeling for the source and the communication channel. In sections <ref> and <ref>, we describe Signs and Uncoded methods, respectively. Section <ref> provides experimental results to compare and evaluate the proposed methods. Finally, Section <ref> concludes the paper.






§ RELATED WORK
 
The problem of structure learning of GGMs from data samples has applications in many fields including biology and social networks. For example, it has been used for gene regulatory networks reconstruction  in <cit.> and  analysis of users relationships in social networks in <cit.>.  There are many studies addressing this problem from various perspectives <cit.>. 

The  Chow-Liu algorithm obtains the maximum likelihood estimate of the structure if the underlying graph is a tree <cit.>. Although this algorithm is applicable for discrete random variables, it  can be used for tree structured GGMs in a similar manner <cit.>. Tavassolipour et al. <cit.> proposed a distributed version of the Chow-Liu algorithm and proved it can recover the underlying tree structure with high probability. Tan et al. in <cit.> and <cit.> provided an analysis of the error exponent of the Chow-Liu algorithm on tree-structured GGMs.


GGMs have the property that the neighbors of each variable can be obtained by solving a linear regression problem for the corresponding variable on other variables. This approach is referred to as neighborhood selection in the literature. For the sparse structures, there are some methods which penalize the linear regression problem with ℓ_1 of the coefficient vector <cit.>. 

Among the proposed methods for sparse structure estimation of GGMs, the ℓ_1-regularized maximum likelihood approaches are more popular <cit.>. This class of model is analyzed in several articles (see <cit.> and refs therein). For instance, Ravikumar et al. <cit.> analyzed the performance of the ℓ_1-regularized maximum likelihood estimator (MLE) under high dimensional scaling. They showed that with probability converging to one, the estimated structure correctly specifies the zero pattern of the true precision matrix. A similar study is conducted by <cit.> which analyzed the consistency of the ℓ_1-regularized MLE in the Frobenius norm.

Besides the lasso typed estimators, thresholding based estimators are proposed  for sparse recovering of the precision matrix <cit.>. For example, Sojoudi <cit.> proposed a simple thresholding method and showed, under certain conditions, the resulting structure is identical to the structure obtained by the lasso.

In the distributed setting, there are several studies which address the problem of covariance/precision matrix estimation <cit.>. Arroyo and Hou <cit.> studied the problem of sparse precision matrix estimation in the situation where the samples are distributed among several machines. Their work differs from our setting in the sense that we assume the data are split across dimensions whereas they split the data across samples. Meng et al. <cit.> addressed estimation of the precision matrix in a distributed manner where the zero pattern of the precision matrix is known in advanced.



§ PROBLEM FORMULATION
 
We are given n i.i.d. random vectors drawn from a d-dimensional zero mean normal distribution 𝒩( 0, Q_x) with (Q_x)_jj = 1. The focus of this paper is the problem of estimating the zero pattern of the sparse precision matrix Θ_x = Q_x^-1 in a situation where the data is stored in d separate local machines such that each machine possesses one dimension of the sample vectors.



Denoting the whole gathered data by { x^(1), ⋯,  x^(n)}, the jth machine captures the j-th dimension of the sample vectors. We denote the j-th dimension of the i-th sample by x_j^(i), i.e. x^(i) = [x^(i)_1, ⋯, x^(i)_d]^T. Hence, the local data at the j-th local machine is {x_j^(1), ⋯, x_j^(n)}.




The probability density function of the normal distribution is given by

    f( x; Θ) = 1/√( (2πΘ^-1))exp{-1/2 x^T Θ x }.

The negative log-likelihood of n i.i.d. samples is given by

    g(Θ) = tr(Θ S_x) - log(Θ),

where  S_x = 1/n∑_i=1^nx^(i)( x^(i))^T is reffered to as sample covariance matrix. One of the well known methods for estimating the sparse precision matrix is to solve an ℓ_1-regularized maximum likelihood function stated as

    Θ= min_Θ≻ 0{g(Θ) + λ_n ‖Θ‖_1, off} ,

where ‖Θ‖_1, off := ∑_j ≠ k|Θ_jk|, and λ_n is a user defined regularization parameter. There is an efficient algorithm known as glasso <cit.> for solving the above log-determinant program.

In <cit.>, it is stated that the Hessian matrix of  (<ref>) is given by

    Γ = ∇_Θ^2 g(Θ) |_Θ = Θ_x = Θ_x^-1⊗Θ_x^-1.

where ⊗ is the Kronecker matrix product. The entry Γ_(j,k),(l,m) corresponds to the second derivative ∂^2 g/∂Θ_jk∂Θ_lm, evaluated at Θ = Θ_x and Γ_(j,k),(l,m) = cov{x_j x_k, x_l x_m}.

We define the set of non-zero entries in the true precision matrix Θ_x as

    S(Θ_x) = {(j,k) ∈𝒱^2 | (Θ_x)_jk≠ 0 }.

Recall that 𝒱 = {1, ⋯, d}. Note that S(Θ_x) includes the diagonal entries. Let S^c(Θ_x) be the complement set of S(Θ_x) which includes all pairs (j,k) where  (Θ_x)_jk = 0. For any two subsets T and T' of V × V, the notation Γ_TT' denotes a |T|× |T'| sub-matrix of Γ with rows and columns indexed by T and T', respectively.

We adopt the incoherence condition used by Ravikumar et al. <cit.> to obtain error bounds on consistency of the solutions. We define max-row-sum norm of a d by d matrix X as

    X_∞ = max_i = 1,⋯,d∑_j = 1^d| X_ij|.


 
	(Incoherence Condition <cit.>) 

	There exists some α∈ (0, 1] such that
	
    Γ_S^c S (Γ_SS)^-1_∞≤ (1-α).


An implication of the above condition is that the non-edge pairs cannot have strong influence on the edges. 

 
	(Covariance Control <cit.>) 

	There exist constants κ_Σ,  κ_Γ < ∞ such that
	
    Q_x_∞   ≤κ_Σ, 
    Γ_SS^-1_∞   ≤κ_Γ.


The above assumptions imply that the covariance elements along any row of Q_x and Γ_SS^-1 have bounded ℓ_1 norms.

Having no access to the original data,  the central machine finds the solution of the optimization problem (<ref>) using received data from the local machines. The likelihood function g(Θ) in (<ref>) depends on the samples via the sample covariance matrix S_x. Thus, obtaining an appropriate approximate of the sample covariance matrix at the central machine would result in a good estimate of the underlying structure. 








 §.§ Channel Model
 
There is a wireless channel between the local machines and the central node. In this paper, we assume that the channel can be modeled as a single-input multiple-output Gaussian multiple access channel (SIMO-GMAC) with additive white noise. The number of antennas at the receiver is assumed to be m. All transmitters have equal transmit power which is denoted by p. This implies, for all j, the following constraint on the transmit symbols should be satisfied:

    1/n∑_i=1^n|s_j^(i)|^2 ≤ p,

where s_j^(i)'s are the channel inputs at the local machine j.
Denoting the transmit symbols by vector s, the channel output is modeled by 

    y =  H  s +  z,

where H∈𝒞^m× d is assumed to be an invertible complex matrix. In the fading environments, the channel gains are drawn from independent circularly symmetric complex Gaussian distribution. The additive noise z is an independent circularly symmetric Gaussian vector with covaraience matrix  σ_z^2 I_d. 




























                        



§ SIGNS METHOD
 
We assume that each local machine applies a sign function on its local dataset to obtain binary data. More precisely, given samples {x_j^(1), ⋯, x_j^(n)} at local machine j, it obtains the signs dataset {x̂_j^(1), ⋯, x̂_j^(n)} where x̂_j = sign(x_j). Then, it transmits the binary data to the central machine with the rate of 1 bit per sample using a channel encoder and decoder.

Denoting the bit rate of the channel at local machine j by R_j, the achievable bit rates for all machines are characterized by <cit.>

    ∑_k∈ S R_k ≤(p/σ_z^2 H^H_S H_S + I_|S|),     ∀  S ⊆{1, ⋯, d},

where  H_S is the sub-matrix of H that includes the rows and columns indexed by S, H^H is the Hermitian of H, I_|S| is the |S|×|S| identity matrix, and (·) is the logarithm function in base 2. Throughout this section, we assume that R_j ≥ 1, for all j = 1, ⋯, d. Therefore, there exists a channel encoding to transmit 1 bit per sample at each local machine.



At the central machine, our goal is to solve the optimization problem (<ref>) on the received binary data from all local machines. In order to obtain a solution that is close to the solution obtained by the original data, we seek a suitable  approximation for the sample covariance matrix S_x in (<ref>). Thus, our goal is to estimate the sample covariance matrix as accurate as possible using the received signs data. In this section, we propose an estimator for the sample covariance matrix and theoretically show its error decreases exponentially by the sample size n.

Let x_j and x_k be jointly normal with zero means, unit variances and correlation coefficient ρ_jk. If x̂_j and x̂_k be the corresponding sign variables, then the joint probability mass function (pmf) of x̂_j and x̂_k is given by <cit.>

    [ x̂_j \x̂_k         -1         +1;         -1     β_jk/2 (1-β_jk)/2;         +1 (1-β_jk)/2     β_jk/2 ]

where β_jk∈ [0, 1] and given by

    β_jk = 1/2 + arcsin(ρ_jk)/π.

The equation (<ref>) can be rewritten as

    ρ_jk = sin(π(β_jk - 1/2)) = -cos(πβ_jk).

Thus, by proposing an estimator for β_jk, using (<ref>) we can obtain an estimator for ρ_jk. The following estimator for β_jk is optimal in the sense that it is unbiased and has minimum variance (UMVE) <cit.>,

    β̂_jk = 1/n∑_i=1^n𝕀(x̂^(i)_j x̂^(i)_k = 1),
 
where 𝕀(.) is the indicator function. β̂_jk is indeed a binomial random variable with success probability of β_jk. By substituting  β̂_jk in (<ref>), we use

    ρ̂_jk = -cos(πβ̂_jk),

as an estimator for ρ_jk. Although ρ̂_jk is indeed biased, it is a consistent estimator for ρ_jk. Following lemma gives an error bound on this estimator.

 
	Let x_j and x_k be two jointly normal variables with zero means, unit variances and correlation coefficient ρ_jk. Then, for the estimator (<ref>), we have
	
    (|ρ̂_jk - ρ_jk|≥δ) ≤ 2 exp(-2/π^2nδ^2),

	where δ≥ 0.



	Since the function cos(·) is a 1-Lipschitz function, i.e. |cos(x) - cos(y) |≤| x - y |, we have
	
    (|ρ̂_jk - ρ_jk|≥δ)    = (| -cos(πβ̂_jk) + cos(πβ_jk) |≥δ) 
       ≤(π|β̂_jk - β_jk|≥δ) 
       = (|β̂_jk - β_jk|≥δ/π).

	Since β̂_jk is sum of n independent Bernoulli random variables, applying the Hoeffding inequality yields
	
    (|β̂_jk - β_jk|≥δ/π)    ≤ 2exp(-2/π^2nδ^2),

	which completes the proof.

Lemma <ref> shows that the error of proposed estimator ρ̂_jk is controlled by the number of samples exponentially. Using this estimator, we can obtain an estimator for the sample covariance matrix as follows

    S_x = - cos(π/2 B),
 
where B_jk = β̂_jk, and cos(.) function is applied on the input matrix element wise, i.e. (S_x)_ij = -cos(π2β_ij).
By substituting the above sample covariance matrix into (<ref>), we can solve the regularized maximum likelihood problem. 

Note that the sample covariance matrix S_x defined in (<ref>) is not necessarily positive semi-definite. But, it does not affect the convexity and uniqueness solution of (<ref>). Ravikumar et al. <cit.> proved that the problem (<ref>) is convex and has a unique solution for any sample covariance matrix with strictly positive diagonal elements which holds for S_x in (<ref>).




By incorporating Lemma <ref> and the theorems 1 and 2 in <cit.>, we can conclude that the precision matrix obtained by solving (<ref>) with the sample covariance matrix S_x in (<ref>), recovers the true structure with high probability. Moreover, the proposed method correctly recovers the signs of the edges with high probability.

More precisely, the event ℳ(Θ_x; Θ_x) indicates that Θ_x and Θ_x do agree on the zero entries and for the nonzero entries they have the same sign.   
Theorems <ref> and <ref> state that the event ℳ(Θ_x, Θ_x) occurs with high probability. Before stating the theorems we should define some properties of the underlying GGM. We denote the maximum degree of the underlying graph structure by Δ. The minimum absolute value of the edges weighs in the precision matrix is denoted by θ_min which is

    θ_min = min_(i,j) ∈ E(Θ_x)|(Θ_x)_ij|.










 
Consider a normal distribution satisfying the incoherence Assumption <ref> and <ref> with parameter α∈ (0, 1]. Let Θ_x be the  solution of the log-determinant program (<ref>) with sample covariance S_x in (<ref>) and regularization parameter λ_n = (8π/α) √(1/2nln2/ϵ) for some 0 < ϵ≤ d^-2. Then,


  * If the sample size is lower bounded as




    n > C_sign^2 Δ^2 (1+8/α)^2 ln2/ϵ,

where

    C_sign = 3√(2)πmax{κ_Σκ_Γ,κ_Σ^3κ_Γ^2},

then with probability at least 1-d^2 ϵ, the edge set specified by Θ_x is a subset of the true edge set.


  * If the sample size satisfies the lower bound
 
    n > T^2_sign(1+8/α)^2 ln2/ϵ,

    where 
    
    T_sign = √(2)πmax{κ_Γθ_min^-1, 3 Δ max{κ_Σκ_Γ,κ_Σ^3κ_Γ^2}},

	then,
	
    (ℳ(Θ_x; Θ_x)) ≥ 1-d^2ϵ.
 






	Note that the proposed sign method is applicable for any channel with capacity greater than or equal to 1 bit.




§ UNCODED METHOD
 
In this section, we assume that each local machine puts its local data into the channel without any source or channel coding. The central machine estimates the underlying graph structure using received data from the channel. At the central machine, no source or channel decoding is used. It infers the structure directly from the output samples of the channel. 



As described in Section <ref>, we consider a SIMO-GMAC. Each local machine can transmit two consequent samples by each channel use. More precisely, denoting the channel input symbol by s =  s_R + j  s_I, each local machine can put two consequent samples as real and imaginary parts of the input symbol. Therefore, at the central machine, n/2 vectors are received that each one is 2d-dimensional.

In this way, the  equation (<ref>) can be decomposed as

    y = (H_R + j H_I) ( s_R + j  s_I) + ( z_R + j  z_I),

where j^2 = -1. Hence, it can be rewritten in a block-matrix form as

    [ y_R; y_I ]
    = 
    [  H_R -H_I;  H_I  H_R ][ s_R; s_I ]
    +
    [ z_R; z_I ],

where H_R, H_I are d × d real matrices, and all the real and imaginary part vectors are d-dimensional. In this way, two source samples can be transmitted per channel use: a sample is put into the real part and the other is put into the imaginary part. In particular, s_R + j s_I = √(p/2)( x_R+j x_I), where x_R and x_I are two independent samples from the source. In this way, the transmit power constraints are satisfied.  

The central machine estimates the conditional dependencies of the vectors x using the received vectors y.


























 §.§ Approximating the Sample Covariance

Defining matrix H = √(p2)[  H_R -H_I;  H_I  H_R ], x̃ = [ x_R; x_I ], and ỹ = [ y_R; y_I ]. When transmitting samples through the channel, if we put two independent samples as real and imaginary parts of the vector x̃, then the covariance matrix of x̃ is

    Q_x̃ = 
    [ Q_x   0;   0 Q_x ].

On the other hand, according to equation (<ref>), we have

    Q_x̃ = H^-1 Q_ỹH^-T - σ_z^2 H^-1H^-T,

where Q_x̃ and Q_ỹ is the covariance matrix of x̃ and ỹ, respectively. By substituting the sample covariance matrix of ỹ into the above expression, we obtain an approximation for the sample covariance matrix of x̃, as

    S_x̃ = H^-1 S_ỹH^-T - σ_z^2 H^-1H^-T.

 
Given n i.i.d. samples of the vector ỹ. Then, for the sample covariance matrix S_x̃ in (<ref>) we have

    (| (S_x̃)_jk - (Q_x̃)_jk|≥δ) ≤ 4exp(-nδ^2/c),

where

    c = 3200 (1 + σ_z^2 / λ^2_min(H))^2,

and λ_min(H) is the minimum eigenvalue of H.


	We define the random variable w as follows
	
    w = H^-1 y =  x + H^-1 z.

	It is clear that w ∼𝒩( 0, Q_w), where Q_w=Q_x + σ_z^2 H^-1H^-T. Denoting w = [w_1, ⋯, w_p]^T, w_j/√((Q_w)_jj) is a standard normal variable which is sub-Gaussian with parameter 1. Thus, according to Lemma 1 in <cit.>, we have
	
    (| (S_w)_jk - (Q_w)_jk|≥δ) ≤exp{-nδ^2/3200 max_i (Q_w)_ii^2},

	where S_w = H^-1S_y H^-T is the sample covariance over w^(i) = H^-1 y^(i) samples. On the other hand, we have 
	
    (|(S_x̃ - Q_x̃)_jk|≥δ)    = (|( H^-1(S_ỹ - Q_ỹ)H^-T)_jk|≥δ) 
       =(|(S_w - Q_w)_jk|≥δ) 
       ≤exp{-nδ^2/3200 max_i (Q_w)_ii^2}

	By finding an upper bound on  max_i (Q_w)_ii^2, we can obtain an upper bound on the above probability. 
	
    max_i(Q_w)_ii   = max_i(Q_x + σ_z^2H^-1H^-T)_ii
       ≤max_i(|Q_x|+|σ_z^2H^-1H^-T|)_ii
       ≤max_i(Q_x)_ii+max_j(σ_z^2H^-1H^-T)_jj.

	By decomposing H^-1H^-T as UΛ^2 U^T, we have
	
    max_i(σ_z^2H^-1H^-T)_ii   = max_i (σ_z^2 UΛ^2 U^T)_ii
       ≤max_i (σ_z^2 λ_max^2(H^-1) U U^T)_ii
       =  σ_z^2/λ_min^2(H).

	By combining the above bound and (<ref>), and substituting into (<ref>) we obtain the claimed bound in the lemma.


Next, we define the approximate sample covariance matrix of x as

    Ŝ_x = 1/2([ I_d 0_d ]
    S_x̃[ I_d; 0_d ]
    +
    [ 0_d I_d ]
    S_x̃[ 0_d; I_d ]),

where 0_d is a d× d zero matrix.

	For Ŝ_x defined in (<ref>), we have
	
    (| (S_x)_jk - (Q_x)_jk|≥δ) ≤ 8exp(-nδ^2/2c).
 


From (<ref>), it is clear that 
    (Ŝ_x)_jk = 1/2((S_x̃)_jk + (S_x̃)_(d+j)(d+k)).
 Thus, we have

    (| (Ŝ_x)_jk - (Q_x)_jk|≥δ) 
         = (| (S_x̃)_jk + (S_x̃)_(d+j)(d+k) - 2(Q_x̃)_jk|≥ 2δ) 
         ≤(| (S_x̃)_jk - (Q_x̃)_jk| + | (S_x̃)_(d+j)(d+k) - (Q_x̃)_jk|≥ 2δ) 
         ≤(| (S_x̃)_jk - (Q_x̃)_jk|≥δ) + 
             (| (S_x̃)_(d+j)(d+k) - (Q_x̃)_jk|≥δ) 
         ≤ 8exp(-nδ^2/2c),

where the last inequality is obtained by the error bound of Lemma <ref> for the sample size n/2.





































Note that the matrix S_x in (<ref>) is not necessarily positive semi-definite. But this does not affect the convexity of the optimization problem (<ref>).


By substituting S_x from (<ref>) into the (<ref>), we can solve the ℓ_1 regularized maximum likelihood problem and obtain a sparse solution for the precision matrix Θ_x. Similar to Theorem <ref>, we can guarantee that Uncoded method can correctly recover the underlying graph structure with high probability.

 
Consider a normal distribution satisfying the incoherence Assumption <ref> and <ref> with parameter α∈ (0, 1]. Let Θ_x be the  solution of the log-determinant program (<ref>) with sample covariance S_x in (<ref>) and regularization parameter λ_n = (8π/α) √(1/2nln2/ϵ) for some 0 < ϵ≤ d^-2.


  * If the sample size is lower bounded as




    n > C_uncoded^2 Δ^2(1+8/α)^2 ln8/ϵ,

where

    C_uncoded = 6 √(2c) max{κ_Σκ_Γ,κ_Σ^3κ_Γ^2}.

then with probability at least 1-d^2 ϵ, the edge set specified by Θ_x is a subset of the true edge set.


  * If the sample size satisfies the lower bound
 
    n > T^2_uncoded(1+8/α)^2 ln8/ϵ,

    where 
    
    T_uncoded = 2√(2c)max{κ_Γθ_min^-1, 3 Δ max{κ_Σκ_Γ,κ_Σ^3κ_Γ^2}}

	then,
	
    (ℳ(Θ_x; Θ_x)) ≥ 1-d^2ϵ.
 






Since the  channel has real and imaginary parts, 2 samples can be transmitted by each channel access (i.e. each local machine can transmit n samples by n/2 channel uses). Therefore, if the sample generation rate at the source is less than or equal to twice of the channel's rate, the machines can transmit all samples without any sample loss.


	
	
	
	
	
	
	
	
	
	
	 

	


§ EXPERIMENTS
 
In this section, the performance of our proposed methods is evaluated by performing several experiments. In our simulations[The source code is available at <https://github.com/ArminKaramzade/distributed-sparse-GGM>.], the glasso package <cit.> is used to solve ℓ_1-regularized MLE of the precision matrix. This package is based on the block coordinate descent algorithm proposed by <cit.>.

In our experiments, a sparse random precision matrix is generated as follows. First, we generate a random sparse graph with a fixed probability of the edge presence, say 0.1, and also set its maximum node degree to Δ = 5. Then, we choose edge weights uniformly in [-1, 1] for the symmetric precision matrix Θ. Next, we make it positive definite matrix by adding a scaled identity matrix. Finally, we normalize the precision matrix to set the variances to 1. Also, we ensure that the generated matrix satisfies Assumption <ref>.

We employ the True Positive and False Positive Rates (TPR and FPR, respectively) as our performance measures. TPR is defined as the percentage of the predicted edges (non-zero off-diagonal entries in the precision matrix) that correctly detected. Similarly, FPR is the percentage of the predicted non-edges (zero entries in the precision matrix) that incorrectly detected.


We have experimentally observed
that λ_n^*signs≈ 4λ_n^*original and λ_n^*uncoded≈2/3λ_n^*original, where λ_n^*signs, λ_n^*uncoded, and λ_n^*original are the best regularization parameter for the signs, uncoded, and original data, respectively. 

In order to have a fair comparison between Signs and Uncoded methods, we have used identical parameters for the channel. More precisely, we assume H=I which ensures all the local machines have identical bit rates. We set the bit rate of each local machine, i.e. R_j, to 2 bits. Thus, in the proposed methods, each local machine can transmit n bits by n/2 channel uses. According to (<ref>), in order to achieve the bit-rate of 2, the signal to noise ratio (SNR) should set to 3 (i.e. p/σ^2_z=3).

In  the first experiment, we evaluate the performance of our methods with respect to the dimension d.  <ref> shows TPR and FPR as a function of d for sample sizes n=1000 and 10,000. In this experiment, the error curves are averaged over 20 different random graphs and for each graph the TPR and FPR are averaged over 10 different random samples. As can be seen from  <ref>, Signs method outperforms Uncoded method. However, all three methods have approximately the same FPR. 

 <ref> reflects the performance of the methods as a function of the sample size n for d=50 and d=100. As can be seen, by increasing the sample size n, the performance of all methods increases. In this experiment again Signs method outperforms the uncoded scheme.




 


	
In  <ref>, the probability of perfect structure recovery for a star-shaped graph is depicted. In this experiment, the underlying star graph consists of d=70 nodes. The precision matrix is generated as the inverse of a covariance matrix with (Q_x)_ij=1/4 for all (i, j) ∈ℰ which satisfies Assumption <ref>. The probability of perfect recovery is estimated by running the proposed methods 100 times and counting the number of times that the structure is recovered exactly. As can be seen from the figure, all methods recover the structure exactly for large enough sample sizes as claimed by theorems <ref> and <ref>. 
		

	
In  <ref>, we measure the TPR of Uncoded method for different values of the SNR. The experiment is performed on a random graph with d=40 nodes with maximum degree of Δ=5 and n=10,000. In this experiment, we have generated the channel matrix H with entries drawn from i.i.d. standard normal samples. The TPR curve is averaged over 100 different channel matrices. As can be seen from  <ref>, for SNR greater than 5, the performance of Uncoded method is very close to the TPR of the original data.

The FPR curve is not plotted, since the error values were negligible even for small SNR.




		

		


§ CONCLUSION
 
In this paper, we have studied the sparse structure learning of GGMs where the data are distributed across multiple local machines. Two methods are proposed to send information from the local machines to the central machine, namely, Signs and Uncoded methods. We have analytically and experimentally shown that the central machine can recover the underlying graph if large enough sample sizes are transmitted to the central machine. 

Our experiments show that, under the same conditions, Signs method outperforms the uncoded scheme. Both methods have small FPR which is close to the FPR obtained by the original data.



§ ACKNOWLEDGMENT

We thank Amir Najafi and Amir-Hossein Saberi for their valuable comments that greatly improved the manuscript.




IEEEtran



[
    < g r a p h i c s >
]Mostafa Tavassolipour
	received the B.Sc. degree from Shahed University, Tehran, Iran, in 2009, and the M.Sc. degree from Computer Engineering department of Sharif University of Technology (SUT), Tehran, Iran, in 2011. Currently, He is a Ph.D. student of Artificial Intelligence program at Computer Engineering Department of Sharif University of Technology. His research interests include machine learning, image processing, information theory, content based video analysis, and bioinformatics.

[
    < g r a p h i c s >
]Armin Karamzade is M. Sc. student of Artificial Intelligence at the Sharif University of Technology, Tehran, Iran. He received his B. Sc. degree in Computer Engineering from Iran University of Science and Technology, Tehran, Iran, in 2017. His research interests include mostly machine learning, optimization, and statistic.
	

[
    < g r a p h i c s >
]Reza Mirzaeifard received the B.Sc. degree of computer engineering from Shahid Beheshti University, Tehran, Iran, in 2017. Currently, He is M.Sc. student of Artificial Intelligence program at Computer Engineering Department of Sharif University of Technology. His research interests include machine learning, information theory, tensor decomposition, bioinformatics.
	

[
    < g r a p h i c s >
]Seyed Abolfazl Motahari
	is an assistant professor at Computer Engineering Department of Sharif University of Technology (SUT). He received his B.Sc. degree from the Iran University of Science and Technology (IUST), Tehran, in 1999, the M.Sc. degree from Sharif University of Technology, Tehran, in 2001, and the Ph.D. degree from University of Waterloo, Waterloo, Canada, in 2009, all in electrical engineering. From October 2009 to September 2010, he was a Postdoctoral Fellow with the University of Waterloo, Waterloo. From September 2010 to July 2013, he was a Postdoctoral Fellow with the Department of Electrical Engineering and Computer Sciences, University of California at Berkeley. His research interests include multiuser information theory and Bioinformatics. He received several awards including Natural Science and Engineering Research Council of Canada (NSERC) Post-Doctoral Fellowship.

[
    < g r a p h i c s >
]Mohammad-Taghi Manzuri Shalmani
	received the B.Sc. and M.Sc.
	in electrical engineering from Sharif University of
	Technology (SUT), Iran, in 1984 and 1988, respectively.
	He received the Ph.D. degree in electrical and
	computer engineering from the Vienna University
	of Technology, Austria, in 1995. Currently, he is an
	associate professor in the Computer Engineering
	Department, Sharif University of Technology,
	Tehran, Iran. His main research interests include
	digital signal processing, stochastic modeling, and
	Multi-resolution signal processing.


















