Maximum Likelihood Estimation of Sparse Networks with Missing Observations
Solenne Gaucher Olga Klopp








































thmTheorem
prpProposition
lemLemma
corCorollary
defiDefinition
remarkRemark


    𝒜ℬ𝒞𝒟ℰℱ𝒢ℋℐ𝒥𝒦ℒℳ𝒩𝒪𝒫𝒬ℛ𝒮𝒯𝒰𝒱𝒲𝒳𝒴𝒵
            ABCDEFGHIJKLMNOPQRSTUVWXYZ
            𝐚𝐛𝐜𝐝𝐞𝐟𝐠𝐡𝐢𝐣𝐤𝐥𝐦𝐧𝐨𝐩𝐪𝐫𝐬𝐭𝐮𝐯𝐰𝐱𝐲𝐳
            Θ
            𝔸𝔹ℂ𝔻𝔼𝔽𝔾ℍ𝕀𝕁𝕂𝕃𝕄ℕ𝕆ℙℚℝ𝕊𝕋𝕍𝕎𝕏𝕐ℤ
            Θ
            
            #1#2#1#22mu#1#2 iid∼Bin
            bUnif sto≤ sto≥
            ε ⇒  ⇔ WW_n^*
            n^(2)N^(2)k^(2)k_(2)R cst L̃k_ mink_ maxd1]Solenne Gaucher solenne.gaucher@ensae.fr2,1]Olga Klopp kloppolga@math.cnrs.fr[1]CREST, ENSAE[2]ESSEC Business SchoolMaximum Likelihood Estimation of Sparse Networks with Missing Observations
                [
                
            ==========================================================================
            
            
            Estimating the matrix of connections probabilities is one of the key questions when studying sparse networks. In this work, we consider networks generated under the sparse graphon model and the inhomogeneous random graph model with  missing observations. Using the Stochastic Block Model as a parametric proxy, we bound the risk of the maximum likelihood estimator of network connections probabilities, and show that it is minimax optimal. Moreover, we show that our estimator can be efficiently approximated using tractable variational methods, and thus used in practice.
            
            
            § INTRODUCTION
            
            
            In the past two decades, networks have attracted considerable attention, as many scientific fields are concerned by the advances made in the understanding of these complex systems. In social sciences <cit.> as in physics <cit.> and biology <cit.>, networks are used to represent a great variety of systems of interactions between social agents, particles, proteins or neurons. These networks are often modeled as an observation drawn from a random graph. 
            
            Missing observations is a common problem when studying real life networks. In social sciences, data coming from sample surveys are likely to be incomplete, especially, when dealing with large or hard-to-find populations. While biologists often use graphs to model interactions between proteins, experimental discovery of these interactions can require substantial time and investment from the scientific community <cit.>. In many cases, collecting complete information on relations between actors can be difficult, expensive and time-consuming <cit.>. On the other hand, the emergence of detailed data sets coming, for example, from social networks or genome sequencing has fostered new challenges, as their large size makes using the full data computationally unattractive. This has lead scientists to consider only sub-samples of the available data <cit.>. However, incomplete observation of the network structure may considerably affect the accuracy of inference methods <cit.>.
            
            Our work focuses on the study of the inhomogeneous random graph model with missing observations. In this setting, the problem of estimating the matrix of connections probabilities is of primary interest. Minimax optimal convergence rates for this problem have been shown to be attained by the least square estimator under full observation of the network for dense graphs in <cit.> and for sparse graphs in <cit.>. In <cit.>, the authors extended these results to the setting in which observations about the presence or absence of an edge are missing independently at random with the same probability p.  However their estimator requires the knowledge of p, and cannot be extended to non-uniform sampling schemes. Unfortunately, least square estimation is too costly to be used in practice. Many other approaches have been proposed, for example, spectral clustering <cit.>, modularity maximization <cit.>, belief propagation <cit.>, neighborhood smoothing <cit.>, convex relaxation of k-means clustering <cit.> and of likelihood maximization <cit.>, and universal singular value thresholding <cit.>. It was conjectured the existence of possible computational gap when no polynomial time algorithm can achieve minimax optimal rate of convergence. The present work shows that this is not the case.
            
            In this work, we consider the maximum likelihood estimator. This estimator is also NP-hard but its computationally efficient approximations (under some additional conditions) have been proposed in the literature (see, e.g., <cit.> for a detailed review of these methods). For example, the authors of <cit.> suggest to use pseudo-likelihood methods, as it leads to computationally tractable estimators. Alternatively, in <cit.> a tractable variational approximation of the maximum likelihood estimator is proposed. This methods has been applied successfully to study biological networks, political blogsphere networks and seeds exchange networks <cit.>. The authors of <cit.> show asymptotic normality of the maximum likelihood estimate and of its variational approximation for sparse graphs generated by stochastic block models when the connections probabilities of the different communities are well separated. In <cit.>, these results are extended to the case of missing observations. These methods suffer from a lack of theoretical guarantees when the model is misspecified or non-identifiable. On the other hand, to the best of our knowledge, no non-asymptotic bound has been established for the risk of the maximum likelihood estimator. In this work, we close this gap and show that the maximum likelihood estimator is minimax optimal in a number of scenarii, and adaptative to non-uniform missing data schemes. Moreover we show that it can be efficiently approximated using tractable variational methods.
            
            Our results find a natural application in predicting the existence of non-observed edges, a commonly encountered problem called link prediction<cit.>. Interaction networks are often incomplete, as detecting interactions can require significant experimental effort. Instead of exhaustively testing for every connection, one might be interested in deducing the pairs of agents which are most likely to interact based on the relations already recorded and on available covariates. If these estimations are precise enough, testing for these interactions would enable scientists to establish the network topology while substantially reducing the costs <cit.>. In this context, estimating the probabilities of connections through likelihood maximization enables to accordingly rank unobserved pairs of nodes. Link prediction also finds applications in recommender systems for social networks. The missing observation scheme studied in this work is motivated by the above examples, and generalizes the model described in <cit.>.
            
            
            
             §.§ Inhomogeneous random graph model
            
             We consider an undirected, unweighted graph with n nodes indexed from 1 to n. Its connectivity can be encoded by its adjacency matrix, defined as follows:  set  a n × n symmetric matrix such that for any i<j, _ij = 1 if there exists an edge between node i and node j, _ij = 0 otherwise. In our model, we consider that there is no edge linking a node to itself, so _ii=0 for any i. We assume that the variables ( _ij)_1 ≤ i<j ≤ n are independent Bernoulli random variables of parameter ^*_ij, where ^* is a n × n symmetric matrix with zero diagonal entries. This matrix ^* corresponds to the matrix of probabilities of observing an edge between nodes i and j. This model is known as the inhomogeneous random graph model:
             
                ∀ 1 ≤ i < j ≤ n,  _ij|^*_ijind.∼Bernoulli(^*_ij).
            
            In the present paper we consider the following problem: from a single partial observation of the graph, that is, given a sample of entries of the adjacency matrix , we want to estimate the matrix of connections probabilities ^*. 
            
            
            The problem of estimating ^* when some entries of the adjacency matrix are not observed is closely related to the 1-bit matrix completion problem. The matrix completion problem <cit.> aims at recovering a matrix which is only partially observed. More precisely, we observe a random sample of its entries, which may be corrupted by some noise, and we wish to infer the rest of the matrix. In 1-bit matrix completion, first introduced in <cit.>, the entries (i,j) of the observed matrix can only take two values {0,1} with probabilities given respectively by f(_ij) and 1-f(_ij). Here, the matrix  corresponds to the real quantity of interest that one would like to infer, and the function f can be seen as the cumulative distribution function of the noise. A typical assumption in this setting is that the matrix  is low-rank. In <cit.>, the authors show that for 1-bit matrix completion the restricted penalized maximum likelihood estimator is minimax optimal up to a log factor. The methods used in our proofs are, to some extend, inspired by the methods developed for the framework of matrix completion. However, the problem we have in hand is in many aspects different from the 1-bit matrix completion problem. The structure of the connections probabilities matrix ^* and the sparsity of the network allow for faster rates of convergence, and the technics of proof required to match the minimax optimal convergence rate are more involved.
            
            Our approach for estimating the matrix of connections probabilities is based on the celebrated Regularity Lemma by Szemerédi <cit.>, which implies that any graph can be well approximated by a stochastic block model (SBM). We refer to <cit.> for a more detailed presentation of this result. In the SBM, each node i is associated with a community z^*(i), where z^*: [n] → [k] is called the index function. This index function can either be treated as a parameter to estimate (this model is sometimes called the conditional stochastic block model), or as a latent variable. In this case, the indexes follow a multinomial distribution: ∀ i, z^*(i) i.i.d∼ℳ(1; α^*) where ∀ l ∈ [k], α_l is the probability that node i belongs to the community l. Given this index function, the probability that there exists an edge between nodes i and j depends only on the communities of i and j. For example, when considering citations networks, where two articles are linked if one is cited by the other, it amounts to saying that the probability that two articles are linked only depends on their topic. Similarly, if one considers students of a school in a social network, it is a reasonable assumption to say that the probability that two students are linked only depends on their cohorts. This implies that the matrix of connections probabilities ^* can be factorized as follows: ^*_ij = ^*_z^*(i) z^*(j), with ^* a k × k symmetric matrix such that ^*_ab is the probability that there exists an edge between a given member of the community a and a given member of the community b, so we have that the conditional SBM can be written as:
             
                ∃^*∈[0,1]^k × k_ sym,    ∃ z^*: [n] → [k]
                 ∀ 1 ≤ i < j ≤ n,  _ij|^*, z^*    ind.∼Bernoulli(^*_z^*(i)z^*(j)), _ii = 0.
            
            While considering the SBM, the problem of estimating the matrix of connections probabilities reduces to estimating the label function z^* and the matrix of probabilities of connections between communities ^*.
            
            In the past decade, the stochastic block model has known a growing interest from the statistical community and an important part of the work has focused on the problem of community recovery (i.e., the recovery of the vector of communities populations α^*, or of the label function z^* in the conditional model). Theoretical guarantees for this problem were established  under quite strong assumptions on the matrix of probabilities of connections between communities, ^*, see, for example, <cit.>.
            
            Note that our results hold without assuming the existence of the true community structure, that is, without assuming that the matrix ^* is block constant. With this in mind, we will focus on estimating the distribution giving rise to the adjacency matrix, i.e., on estimating ^*, rather than on estimating the label function or the populations of the communities. One important question in this setting is how to choose the number of communities for our estimator, as more communities implies a smaller bias and a greater variance. Optimizing this trade-off requires, first, establishing a non-asymptotic bound on the risk of our estimator for a number of communities that may depend on the number of nodes, and, in a second time, bounding the bias of an oracle block constant estimator.
            
               
            Our work focuses on relevant in applications setting of partial observations of the network. We consider the following missing value setting. Let ∈{0,1}^n × n_sym denote the sampling matrix given by _ij = 1 if we observe _ij and _ij = 0 otherwise. We assume that the sampling matrix  is random and, conditionally on ^*, independent from the adjacency matrix . For any 1≤ i<j≤ n, its entries _ij are mutually independent. Finally, we denote by ∈ [0,1]^n × n_sym the unknown matrix of sampling probabilities such that _ijind.∼Bernoulli(_ij). This sampling scheme includes for instance node-based sampling schemes such as the exo-centered design described in <cit.>, where we observe _ij if i or j belongs to the set of sampled nodes. It also covers random dyad sampling schemes (described, e.g., in <cit.>). In this case, the probability of observing the entry _ij is allowed to depend on the communities of i and j. 
            
            
            
             §.§ Graphon model
            
            While studying exchangeable random graphs, important questions such as how to compare two graphs with different numbers of nodes or how to study graphs with an increasing number of nodes call for a more general, non-parametric model. One of such models that has attracted a lot of attention recently is the graphon model <cit.>. In this model, the connections probabilities ^*_ij are the following random variables  
            
                _ij^* = W^*(ζ_i, ζ_j)
            
            where ζ_1, ..., ζ_n are unobserved (latent) independent random variables sampled uniformly in [0,1]. The graph is then sampled according to the inhomogeneous random graph model (<ref>). The function W^*: [0,1]^2 → [0,1] is measurable, symmetric and is called a graphon. Graphs encountered in practice are usually sparse: the expected number of edges grows as ρ_n n^2 where ρ_n is a decreasing sequence of sparsity inducing parameters. The dense graphon model can be modified in order to account for this sparsity:
            
                _ij^* = ρ_nW^*(ζ_i, ζ_j).
            
            Since the law of the graph is invariant under any change of labelling of its nodes, different graphons can give rise to the same distribution on the space of graphs of size n. More precisely, let W be a graphon and τ: [0,1] → [0,1] be a measure-preserving function. We write W_τ(x,y ) = W(τ(x),τ(y)) and say that two graphons U and V are weakly isomorphic if there exists measure-preserving maps τ , ϕ such that U_τ = W_ϕ almost everywhere. It is established in Section 10, <cit.> that two graphons define the same probability measure on graphs if and only if they are weakly isomorphic. 
            
            In the present paper we also consider the setting when the matrix of connections probabilities is generated following the sparse graphon model (<ref>). We deal with two classes of graphon functions previously studied in the literature, step-function graphons and smooth graphons, under the scenario  of partial observations of the network.
            
            
            
             §.§ Outline of the paper
            
              
            The present paper is devoted to the theoretical study of the maximum likelihood estimator in sparse network models with missing observations. First, we provide an oracle bound for the risk of the maximum likelihood estimator of the matrix of connections probabilities from a partial observation of the adjacency matrix . Our results hold under fairly general assumptions on the missing observations scheme and we show that the maximum likelihood estimator matches the minimax optimal rates of convergence in a variety of scenarii, while being fully adaptative to the missing data scheme. Second, we provide a parameter-free version of our estimator which, in particular, does not require the knowledge of the sparsity parameter ρ_n. We also bound the Kullback-Leibler divergence between the true matrix of connections probabilities and its block constant approximation, and derive an optimal choice for the number of communities defining the maximum likelihood estimator. We show that the maximum likelihood estimator can be approximated using tractable variational methods, and we provide a bound on the risk of the variational estimator.
            
            This manuscript is organized as follows. In Section <ref>, we introduce the maximum likelihood estimator for the matrix of connections probabilities ^* from partial observation of the adjacency matrix . Then,   Theorem <ref> in Section <ref> provides a non-asymptotic oracle bound on the risk of this estimator. As a consequence, we  show that our estimator is minimax optimal in a number of scenarii and derive the corresponding bound for estimating ^* in the case of full observation of the adjacency matrix . Our estimation method requires bounds on the entries of ^*. In Section <ref>, we first  propose a  method to choose these bounds under fairly general assumptions and, in Section <ref>, we specify it to the case of sparse graphon model (<ref>). We show that the resulting adaptative estimator is minimax optimal up to a log factor. In Section <ref>, Theorem <ref>, we provide the choice for the number of communities that achieves the best trade off between the variability of our estimate and the fit of the oracle model. Finally, in Section <ref>, we show that the maximum likelihood estimator can be consistently approximated using a tractable variational estimator.
            
            
            
             
             
            
             §.§ Notations
            
             
             We provide here a summary of the notations used throughout this paper.work.
            
            
              *  For any positive integer d, we denote by [d] the set {1,...,d}.
            
              *  For any set 𝒮, we denote by |𝒮| its cardinality.
            
              *  For any matrix , we denote by _ij its entry on row i and column j. If ∈ [0,1]^n × n and  is symmetric, we write ∈ [0,1]^n × n_ sym.
            
              *  Let (q,q')=qlog (q/q' )+(1-q)log (1-q/1-q') denote the Kullback-Leibler divergence of a Bernoulli distribution with parameter q from a Bernoulli distribution with parameter q'. For any three symmetric matrices with zero diagonal entries ,  , ∈ [0,1]^n × n_sym we set
            
                _(,) =i<j∑_ij(_ij,_ij)  and  (,)=i<j∑(_ij,_ij).
            
              *  For any three symmetric matrices with zero diagonal entries ,  , ∈ℝ^n × n_sym, let ⟨|⟩ = i<j∑_ij_ij, ⟨|⟩_ = i<j∑_ij_ij_ij, ‖‖_2 = √(⟨|⟩),  ‖‖_2, = √(⟨|⟩_), and ‖‖_∞ = i,jmax|_ij|. With these notations, ‖‖_2, = √(𝔼[‖‖_2,^2]) corresponds to the L_2-norm of the matrix  with respect to the sampling probabilities .
            
            
              *  We denote by 𝒵_n,k  the label functions z: [n] → [k]. For any z ∈𝒵_n,k, we denote by 𝒯_z the set of block constant matrices corresponding to the label z: 
            
            𝒯_z ≜{: ∀ i ∈ [n], _ii = 0  & ∃∈ [0,1]^k × k, ∀ 1 ≤ i<j≤ n, _ij = _ji = _z(i) z(j)}.
              *  To ease notations, for ∈𝒯_z and (a, b)∈ [k]^2, we sometimes denote by  _z^-1(a) z^-1(b) any entry _ij such that (i,j) ∈ (z^-1(a), z^-1(b)) and i ≠ j. We write _k = z ∈_n,k∪_z.
            
            
              *  We denote by C and C' positive constants that can vary from line to line. These are absolute constants unless otherwise mentioned. For any two positive sequences (a_n)_n ∈ℕ, (b_n)_n ∈ℕ, we write a_n = ω(b_n) if a_n/b_n →∞.
            
              *  We denote respectively by 𝔼^ and ℙ^ the expectation and the probability conditionally on the random variable , and respectively by 𝔼 and ℙ the expectation and the probability over all random variables.
            
            
            § CONVERGENCE RATE FOR THE MAXIMUM LIKELIHOOD ESTIMATOR
            
            
             §.§ Maximum likelihood estimator under missing observations
            
            
             
             We start by introducing the conditional log-likelihood for the model (<ref>). Conditionally on the probability matrix ^*, the entries (_ij)_1 ≤ i<j≤ n of the adjacency matrix  are independent Bernoulli variables with parameters (^*_ij)_1 ≤ i<j≤ n. Therefore, for any ∈ [0,1]^n× n, the conditional log-likelihood of the parameter matrix  with respect to the observed entries of the adjacency matrix  is given by
              
                _(;)   =∑_i<j_ij (_ijlog(_ij)+(1-_ij)log(1-_ij)).
            
            For any z∈_n,k and ∈ [0,1]^k× k_, the matrix of connections probabilities corresponding to the block model (z,) is given by _ij = _z(i)z(j) for 1≤ i < j ≤ n and _ii =0 for i ∈ [n]. With these notations, the conditional log-likelihood of a block model (z,)  with respect to the observed entries of the adjacency matrix  is  
             
                _(;z,)   =∑_1 ≤ i<j≤ n_ij(_ijlog(_z(i)z(j))+(1-_ij)log(1-_z(i)z(j)))
                   =∑_1 ≤ a≤ b ≤ k∑ _i ≠ ji∈ z^-1(a), j∈ z^-1(b)_ij(_ijlog(_ab)+(1-_ij)log(1-_ab))
                   =∑_a≤ blog(_ab)∑ _i ≠ ji∈ z^-1(a), j∈ z^-1(b)_ij_ij+∑_a≤ blog(1-_ab)∑ _i ≠ ji∈ z^-1(a), j∈ z^-1(b)_ij(1-_ij).
            
            The maximum likelihood estimator for the stochastic block model is 
              
                (,z)∈∈ [0,1]^k× k_ sym, z∈_n,k_ (;z,).
            
                The block constant maximum likelihood estimator  of ^* is defined as _ij=_z(i)z(j) for any i<j. Note that maximizing the log-likelihood is equivalent to minimizing  a sum of Bernoulli Kullback-Leibler divergences. Indeed, an easy calculation leads
            
                (,z)∈∈ [0,1]^k× k_ sym, z∈_n,k_ (;z,)=∈ [0,1]^k× k_sym, z∈_n,k∑_i<j_ij(_ij,_z(i)z(j)) .
            
             Moreover, for any fixed assignment z∈_n,k and any sampling matrix , the log-likelihood with regards to the observed entries of  will be maximized by taking 
             
                _ab= ^z_ab≜∑ _i ≠ ji∈ z^-1(a),j∈ z^-1(b)_ij_ij/∑ _i ≠ ji∈ z^-1(a),j∈ z^-1(b) _ij.
            
            Note that for any label function z, maximizing the likelihood or minimizing the least square criterion defined as _(; z, ) = i<j∑_ij(_ij - _z(i),z(j))^2 with regards to  yields the same estimator. However, the label functions selected by the two criterions can be different, as is shown in figure <ref>.
            
            
            
            In the rest of this work, we will denote by  the oracle probability matrix, i.e., the best approximation to ^* in the sense of the weighted Kullback Leibler divergence: 
            
                _i<j = ^*_z^*(i) z^*(j), _ii=0 
                   (^*,z^*)∈∈ [0,1]^k× k_ sym, z∈_n,k∑_i<j_(^*_ij,_z(i)z(j)) .
            
            
             §.§ Upper bound on the risk of the restricted maximum likelihood estimator
            
              In this section, we establish an upper bound on the risk of the maximum likelihood estimator and show that it matches the minimax convergence rate obtained in <cit.>.  We will measure the risk of our estimator in -weighted Frobenius norm. To bound the risk of the maximum likelihood estimator, we assume that there exists sequences ρ_n and γ_n such that ∀ i<j, 
                0 < γ_n ≤^*_ij≤ρ_n < 1.
            
              Note that for sparse graphs, ρ_n corresponds to the sparsity inducing sequence in equation (<ref>).
              
              The assumption (<ref>) is systematic in the literature studying the maximum likelihood estimator for the stochastic block model, as it guarantees that the loss associated to the maximum likelihood estimator is Lipschitz. See, for example, <cit.> and  <cit.>, where the authors assume that the adjacency matrix is generated by an homogeneous stochastic block model for which the matrix ^*/ρ_n has entries bounded away from 0. In our model, this corresponds to imposing that ρ_n = O(γ_n), i.e., that all entries of the matrix of connections probabilities ^* are of the same order of magnitude. Our assumptions are more general than the one developped in these articles, as they also cover the case γ_n = o(ρ_n). 
              
              In <cit.>, the authors consider the dense SBM and assume that the entries of ^* belong to {0}∪ [ζ, 1-ζ] ∪{1} for some ζ >0. They prove the consistency of the maximum likelihood estimator constrained to a restricted subset of the parameters. However, the definition of this subset implies knowing the set Ω_0 = { (i,j) : ^*_ij∈{0,1}} prior to estimating the matrix of connections probabilities. Note that, if we assume that Ω_0 is known and that ^* belong to {0}∪ [ζ, 1-ζ] ∪{1}, we can set _ij = 0 for any (i,j) ∈Ω_0 and estimate the remaining entries (which are bounded away from 0 and 1) with our procedure.
              
              On the other hand, cases where the entries of ^* are of different order of magnitude are common in the literature in the case of planted partition models and assortative and disassortative SBM. In the planted partition model, the matrix of connections probabilities between communities is given by ^* = (p-q) I_k + q 1_k 1_k^T, where p>q,  I_k is the identity matrix and 1_k 1_k^T the matrix whose entries are all equal to 1. This amounts to saying that the probability that two nodes are connected only depends on whether they belong to the same community or not. This model can be relaxed to give rise to the assortative model, where the within group probabilities of connection ^*_aa are larger than the between group probabilities of connection ^*_bc : there exists p,q ∈ [0,1] such that for any a≠ b, one has ^*_ab≤ q < p ≤^*_aa. The disassortative model corresponds to the case where between communities connections are more likely than within community connections: one has for any a ≠ b, ^*_aa≤ q < p ≤^*_ab. The last two models are closely related. Indeed, if  is drawn from an assortative SBM, 1_n 1_n^T - I_n - corresponds to a realization of a disassortative SBM.
              
              In the planted partition model, maximizing the likelihood is equivalent to finding a partition maximizing the within group connectivity, i.e., maximizing ∑_i<j_ij_ij where _ij = 1{z(i) = z(j)}. Convex relaxations of the constraints on  have been studied in the literature <cit.>, and theoretical guarantees for these algorithms for the problem of communities recovery have been established under assumptions on the gap p-q. In these models, communities are characterized by higher (respectively lower) connectivity, and the assumption that q ≪ p actually makes the recovery problem easier. By contrast, the definition of a community in the SBM as a set of nodes with the same stochastic behaviour is far more general. It covers settings not suitably described by assortative or disassortative models, as, e.g., graphs with leaders and followers such as  the well known example of Zachary's  Karate Club (see, e.g., <cit.>). In these models, leaders  are seldomly linked one to another, but are highly connected to their own set of followers. On the other hand, followers rarely connect  one to another or to more than one leader. By comparison, our results hold without any assumption on the assortativity or the disassortativity of the model.
            
            In a first time, we assume that we know γ_n and ρ_n. We will discuss how to estimate these values in Section
               <ref>. Let   be the block constant estimator based on the maximization of the likelihood among block constant matrices with entries in [γ_n, ρ_n]:
            
                _i<j = _z(i) z(j), _ii=0
                   (,z) ∈∈ [γ_n,ρ_n]^k× k_ sym, z∈_n,k∑_i<j_ij (_ij,_z(i)z(j)).
            
            Here we assume that k is fixed and that it can depend on the number of
            nodes n. k can be chosen using a network cross-validation
            method <cit.> or, when the graphon is a step function, it can be chosen using a sequential goodness-of-fit testing procedure <cit.> or a
            likelihood-based model selection method <cit.>. When graphon is Hölder-continuous, we provide a choice of k to optimize the usual trade-off between bias and variance of our estimator in Section <ref>.
            Note that the maximum likelihood estimator does not require the knowledge of the matrix of sampling probabilities . On the other hand, this matrix, which characterizes the difficulty induced by missing observations, appears when bounding the error of this estimator. In Theorem <ref>, we provide a general bound on the ‖·‖_2,-norm of the error, while in Corollaries <ref> and <ref> we derive specific bounds on its ‖·‖_2-norm under further assumptions on the matrix .
            
            Assume that  is drawn according to (<ref>), and that ρ_n = ω(n^-1). Then, there exists absolute constants C,C'>0 such that with probability at least 1 - 9exp(-Cρ_nnlog(k))
                ‖^*-‖^2_2,≤ C' ρ_n  (𝒦_(^*, ) + ρ_n^2/(1 - ρ_n )^2 γ_n^2(k^2 + nlog(k) ) ).
            
             Note that we are not interested in regimes for which ρ_n = O(n^-1), as Theorem <ref> implies that in this setting the constant estimator with all entries equal to the average node degree attains the minimax rate.
            
             This bound is stated as a function of the of weighted Kullback-Leibler divergence 𝒦_ and of the oracle matrix  defined in (<ref>). Note that it implies the weaker bound 
                ‖^*-‖^2_2,≤ C' ρ_n  (𝒦(^*, ^f) + ρ_n^2/(1 - ρ_n )^2 γ_n^2(k^2 + nlog(k) ) )
             where ^f is the oracle matrix for the full Kullback-Leibler divergence 𝒦. Indeed, one has 𝒦_(^*, ) ≤𝒦_(^*, ^f) ≤𝒦(^*, ^f).
            
            In the case where all entries are observed, that is _ij = 1 for any i<j, the rate attained by the maximum likelihood estimator is given by the following corollary.
            
            Assume that  is drawn according to (<ref>), that ∀ 1 ≤ i < j ≤ n,  _ij =1 and that ρ_n = ω(n^-1). Then, there exists positive constants C,C'>0 such that with probability at least 1 - 9exp(-Cρ_n nlog(k))
                ‖^*-‖^2_2≤ C' ρ_n  (𝒦(^*, ) + ρ_n^2/(1 - ρ_n )^2 γ_n^2(k^2 + nlog(k) ) ).
            
            If we assume that the probability of observing any entry of the adjacency matrix is bounded away from 0, Theorem <ref> can be adapted to provide a bound on the risk of our estimator under the Frobenius norm. Indeed, if 1≤ i<j≤ nmin{_ij}≥ p, then ‖^*-‖^2_2≤1/p‖^*-‖^2_2, and we get the following result.
            
            Assume that  is drawn according to (<ref>), that 1≤ i<j≤ nmin{_ij}≥ p and that ρ_n = ω(n^-1). Then, there exists absolute constants C,C'>0 such that with probability at least 1 - 9exp(-Cρ_n (k^2 + nlog(k) ))
                ‖^*-‖^2_2≤ C' ρ_n/p (𝒦_(^*, ) + ρ_n^2/((1 - ρ_n )^2 γ_n^2)(k^2 + nlog(k) ) ).
            
            
            
             Previously, the problem of estimation of connections probabilities matrix ^* from partial observations of the network was studied, in particular, by Gao et al.  <cit.>. In this paper, the authors assume  that any entry of the adjacency matrix  is observed independently from the others with the same probability p,  which is assumed to be known. They establish the following lower bound on the risk of any estimator for the stochastic block model.
              
            Assume that  is drawn according to (<ref>), and that each edge is observed independently from the others with probability p. There exists universal constants C,C'>0 such that 
            
                inf ^* ∈_k, ‖^* ‖_∞≤ρ_nsupℙ[‖^* - ‖_2^2  ≥ C (ρ_n(nlog(k) + k^2)/pρ_n^2n^2 )] > C'.
             The authors of <cit.> study the following weighted least square estimator :
            
                ∈‖‖_2^2 - 2/pi<j∑_ij_ij_ij
            
            where p is the probability of observing any entry of the adjacency matrix. They prove that this estimator is minimax optimal in the uniform sampling setting. However, this estimator cannot handle more realistic, non-uniform sampling schemes. Our estimator, on the other hand, works in the non-uniform sampling setting, is adaptative to the sampling design, and does not require information on the probability of observing the entries of the adjacency matrix .  In the particular case when _ij∼Bernoulli(p) and ρ_n = O(γ_n), Corollary <ref> and the lower bound in Theorem <ref> ensures that the maximum likelihood estimator is minimax optimal. We underline that although the lower bound  has been established in <cit.> for ∈_k, ‖‖_∞≤ρ_n, its proof can be adapted to provide a lower bound on the convergence rate for a smaller set of parameters {∈_k,  ‖‖_∞≤ρ_n,  i<jmin{_ij}≥γ_n }. Indeed, the “non parametric" as well as the “clustering" components of the rate are established using matrices with entries close to ρ_n/2.
            
            
            
            
             §.§ Choice of γ_n under general assumptions
            
            In this section, we deal with the setting when condition i<jmin ^*_ij > γ_n is violated. In what follows we consider the sparse case, that is ρ_n → 0, so γ_n ≤ 1 - ρ_n for n large enough. As discussed in <cit.>, we can easily estimate ρ_n (see also Section <ref>). On the other hand, when some entries of the matrix of connections probabilities ^* can be 0 or arbitrarily close to 0, choosing the best sequence γ_n comes down to a trade-off between errors caused by estimating entries smaller than γ_n by γ_n, and the bound obtained in Theorem <ref>. We first consider the case when there exists a sequence γ_n such that number of small entries n_s = ∑_i<j1{_ij < γ_n} is small enough. Then, we have the following result:
            
            Assume that  is drawn according to (<ref>), that ρ_n = ω(n^-1) and that n_s ≤k^2  (nlog(k))/ρ_n. Then, there exists absolute constants C,C'>0 such that with probability at least 1 - 9exp(-Cρ_n ( k^2 + nlog(k) ))
                ‖^*-‖^2_2,≤ C' ρ_n  (𝒦_(^*, ) + ρ_n^2/γ_n^2(k^2 + nlog(k) ) ).
            
            To see it, we define
            
                _ij^s = ^s_z^*(i) z^*(j), ^s_ii=0 
                   ^s_ab = ^*_abγ_n
            
             where ^* is given by (<ref>). Note that ^s and  are defined on the same set, and thus 𝒦_(, ) ≤𝒦_(, ^s). Adapting the proof of Theorem <ref> gives 
            
                ‖^*-‖^2_2,   ≤    C' ρ_n  (𝒦_(^*, ^s) + ρ_n^2/γ_n^2(k^2 + nlog(k) ) )
                   ≤    C' ρ_n  (𝒦_(^*, ) + 𝒦_(^*, ^s) - 𝒦_(^*,) + ρ_n^2/γ_n^2(k^2 + nlog(k) ) )
                   ≤    C' ρ_n  (𝒦_(^*, ) + 2γ_n n_s + ρ_n^2/γ_n^2(k^2 + nlog(k) ) )
            
            where (<ref>) follows from Lemma <ref>. Note that, if there exists a sequence γ_n such that ρ_n = O(γ_n) and n_s ≤ k^2  (nlog(k))/ρ_n, the upper bound on the risk obtained in (<ref>) matches the bound of Theorem <ref> and is minimax optimal. 
            
            Without any assumption on the number of small entries of the matrix of connections probabilities, we choose γ_n = γ(ρ_n) ≜ n^-2/3ρ_n^2/3(k^2 + nlog(k) )^1/3 and obtain the following bound. 
            
            Assume that  is drawn according to (<ref>), and that ρ_n = ω(n^-1). Let 
            
                _i<j = _z(i) z(j), _ii=0
                   (,z) ∈∈ [γ(ρ_n),ρ_n]^k× k_ sym, z∈_n,k∑_i<j_ij(_ij,_z(i)z(j)).
            
            There exists absolute constants C,C'>0 such that with probability at least 1 - 9exp(-Cρ_n ( k^2 + nlog(k) ))
                ‖^*-‖^2_2,≤ C' ρ_n  (𝒦_(^*, ) + ρ_n^2/3 n^4/3(k^2 + nlog(k) )^1/3 ).
             If k is not too large, the rate of convergence is essentially multiplied by (nρ_n)^2/3.
            
            
            
             §.§ Choice of γ_n for sparse positive graphons
            
             In Theorem <ref> we have established an oracle bound for the maximum likelihood estimator with entries belonging to [γ_n, ρ_n]. Defining our estimator requires us to estimate the values of these two sparsity parameters, which are usually unknown. When the matrix of connections probabilities ^* is generated according to the sparse graphon model (<ref>) where W^* is bounded away from 0, these bounds will be of the same order of magnitude and decrease as the expected node degree. Under this assumption, we can use d, the average number of edges, to estimate γ_n and ρ_n. Indeed, it is easy to see that, with probability close to 1, d is close to d = ρ_n01∫01∫W^*(x,y)dx dy, the expected node degree.  Note that if the graphon W^* is Hölder continuous or is a step function, assuming that W^*>0 is enough to ensure that there exists a constant C_inf>0 such that W^* ≥ C_inf. 
             
             To simplify the exposition, we will assume that we observe all the entries of . Our results can be extended to the missing observations scheme described in Section <ref> under the assumption that the entries of the sampling probability matrix  are bounded away from 0. Let Ω be a subset of {(i,j) ∈ [n]^2, i<j} of size n sampled independently of , and let 
            
                d = 1/n∑_(i,j) ∈Ω_ij
                   ρ_n = (log(n))^1/5d ,  γ_n = (log(n))^-1/5d.
            
            We use ρ_n and γ_n to build the restricted maximum likelihood estimator of the matrix of connections probabilities based on the   the observations of _ij with {(i,j) ∈ [n]^2, i<j}\Ω: 
            
                _i<j = _z(i) z(j), _ii=0
                   (,z) ∈∈ [γ_n, ρ_n]^k× k_ sym, z∈_n,k∑_(i,j) ∉Ω(_ij,_z(i)z(j)).
            
            We prove the following upper bound on the risk of this adaptive estimator:
            
            Assume that  is drawn according to the sparse graphon model and that C_inf≜(x,y) ∈ [0,1]^2inf W^*(x,y)>0, ρ_n = o(log(n)^-1/5) and ρ_n = ω(n^-1). Then, there exists positive constants N, C, C' depending only on C_inf, such that, for n ≥ N, with probability at least 1 - 7exp( - C n ρ_n ), we have
            
                ‖^*-‖^2_2≤ C' ρ_n log(n)  (𝒦(^*, ) + (k^2 + nlog(k)) ).
            
             
            In the sparse graphon model, if the graphon W^* is bounded away from 0 and n^-1≪ρ_n ≪log(n)^-1/5, our adaptive estimator is optimal in the minimax sense up to a log factor. This setting includes the sparse stochastic block model considered for example in <cit.>: in this model, the matrix of probabilities of connection between communities ^* is such that ^* = ρ_n ^0, for some fixed matrix ^0 with entries in (0,1] (in this case, the graphon function W^* is a step function bounded away from 0). More generally, Theorem <ref> covers the case of ^* = ρ_n ^0, and ^0 is a fixed matrix with entries in (0, 1].
            
            When we can not assume that the graphon W^* is bounded away from 0, we can  use the same trade-off as in (<ref>) and choose γ_n = γ(ρ_n). Then, with high probability, we obtain  the following bound on the risk of the adaptative estimator: 
            
                ‖^*-‖^2_2≤ C' ρ_n log(n) (𝒦(^*, ) + (log(n)^1/5ρ_n)^2/3 n^4/3(k^2/n^2 + nlog(k) )^1/3).
            
            
             §.§ Smooth graphons
            
            
            We have established a non-asymptotic bound on the risk of the maximum likelihood estimator depending on the Kullback-Leibler divergence between ^* and its oracle approximation by a block constant matrix corresponding to a SBM with k communities. 
            While studying the graphon model (<ref>), two classes of graphons are of particular interest: step function graphons and Hölder continuous graphons <cit.>. A graphon W is called a step function if there exists a partition S_1 ∪ ... ∪ S_k of [0,1] into measurable sets such that the graphon W is constant on any product set S_a × S_b.  For step function graphons, the model corresponds to the stochastic block model described in (<ref>): in this case, the oracle matrix  is equal to the matrix of connections probabilities ^*. Next, we bound the Kullback-Leibler divergence between ^* and its oracle approximation by a block constant matrix for Hölder continuous graphons. We also provide the optimal choice for the number of communities k for our estimator. 
            
            We  consider graphons that are weakly isomorphic to a smooth function. More precisely, for any α >0 and M>0, let _α(M) be the class of Hölder functions, defined as follows:
            
                _α(M) = {W    :    [0,1]^2 → [0,1], ∀ (x,y), (x',y') ∈ [0,1]^2, 
                      | W(x',y') - _⌊α⌋((x,y), (x'-x, y'-y)) |≤ M(| x-x' |^α - ⌊α⌋ + | y-y' |^α - ⌊α⌋)  }
            
            where _⌊α⌋((x,y), · ) is the Taylor polynomial of W of degree ⌊α⌋ at point (x,y). In particular, if W ∈_α(M), ∀ (x,y), (x',y') ∈ [0,1]^2, 
            
            
                | W(x',y') - W(x,y)|≤ M(| x-x' |^α 1 + | y-y' |^α 1).
            
            When the graphon is Hölder continuous, the following proposition provides an upper bound on the Kullback-Leibler divergence between ^* and .
            
            Consider the sparse graphon model (<ref>) with W^* ∈_α(M) where α, M>0 and we assume that C_inf≜(x,y) ∈ [0,1]^2inf W^*(x,y)>0, ρ_n≤ 1 - C_inf and ρ_n = ω(n^-1). Then, almost surely, there exists a k-block constant matrix ^bc such that
            
                (^*, ^bc) ≤4n^2ρ_nM^2/C_inf(1-ρ_n)(1/k)^2(α 1).
            
            Proposition <ref> enables us to bound the bias of estimating ^* by an oracle SBM with k communities. On the other hand, the bound given in Theorem <ref> can be considered as the variance term of a block constant estimator with k blocks. To optimize the trade-off between these two terms, we choose k as follows 
            
                k = ⌈ n^1/1+ (α 1)ρ_n^1/2+ 2(α 1)⌉
            
            and obtain the following result:
            
            Consider the sparse graphon model (<ref>) with W^* ∈_α(M) where α, M>0 and we assume that C_inf≜(x,y) ∈ [0,1]^2inf W^*(x,y)>0, ρ_n≤ 1 - C_inf and that ρ_n = ω(n^-1). Then,
            there exists constants C, C'>0, depending only on M, α and C_inf, such that, the restricted maximum likelihood estimator defined by (<ref>) constructed with k defined by (<ref>) satisfies
            
                ‖_ij^* - _ij‖_2^2 ≤ Cρ_n(n^2/1 + (α 1)ρ_n^1/1 + (α 1)  + nlog(ρ_n n) )
            
            with probability larger than 1- 9exp(-C'ρ_n n log(ρ_nn)).
            The bound  obtained in Theorem <ref> matches the minimax optimal rate established in
            <cit.>  and proves that the maximum likelihood estimator is optimal for estimating the matrix of connections probabilities in graphon model for graphons W^* in the Hölder class.
            
            
            
            § VARIATIONAL APPROXIMATION TO THE MAXIMUM LIKELIHOOD ESTIMATOR
            
            
            Due to the existence of local minima in the likelihood function and the subsequent necessary optimisation over the set of k^n labels, the maximum likelihood estimator defined in Equation (<ref>) cannot be computed in polynomial time. A tractable variational approximation to this estimator has been introduced in <cit.> to study dense and fully-observed stochastic block models. It has been extended to sparse stochastic block models in <cit.>. More recently, the authors of <cit.> used variational methods to approximate the maximum likelihood estimator in networks with missing observations. This method estimates the matrix ^* of probabilities of connections between communities, and the proportions of the different communities, and can be used to estimate the community label function z^* and the matrix ^* of probabilities of connections between nodes.
            
            Note that variational approximations to the maximum likelihood estimator have been introduced in a model closely related to the conditional stochastic block model described in Equation (<ref>). In this model, the labels are assumed to be latent random variables drawn according to the following distribution
                ∀ 1≤ i ≤ n, z(i) ∼ℳ(α^*)
            where α^* = (α^*_1, ..., α^*_k), and α^*_an is the expected size of community a. Conditionally on z = z^*, the edges are then drawn according to the conditional stochastic block model described in Equation (<ref>). Note that the stochastic block model with random labels is a special case of the graphon model described in Equation (<ref>), in which the graphon W^* is a step function.
            
            The likelihood of the observed adjacency matrix under a stochastic block model with random labels with parameters (α, ) is given by 
                𝔩_(; α, )    =   z ∈_n,k∑(i ≤ n∏α_z(i)) exp(_(;z,) ).
            The Expectation-Maximization (EM) algorithm cannot be used to maximise 𝔩_, as it would require to evaluate the expectation of the label function z for given parameters (α, ) by summing over k^n possible labels. To circumvent this problem, variational methods approximate the posterior distribution of z given the observed entries ⊙ of the adjacency matrix , denoted ℙ(·|⊙, α, ), by a simpler distribution chosen so that the expectation step of the EM procedure becomes tractable. More precisely, the posterior distribution ℙ(·|⊙, α, ) is approximated by a multinomial distribution denoted ℙ_τ, such that ℙ_τ(z) = ∏_1≤ i ≤ n m(z|τ^i), where m( ·|τ^i) is the density of the multinomial distribution with parameter τ^i = (τ^i_1, ..., τ^i_K), and τ = (τ^1, ..., τ^n). Then, the variational estimator is defined as
            
                (α^VAR, ^VAR, τ^VAR)    =   (α, ) ∈𝒬, τ∈𝒯𝒥_(; τ, α, )
                for    𝒥_(; τ, α, )     =   log(𝔩_(; α, )) - KL(ℙ_τ(·)||ℙ(·|⊙, α, ) )
            
            where 𝒬 and 𝒯 are the respective parameter spaces for the parameters (α,) and τ, and KL denotes the Kullback-Leibler divergence between two distribution. Note that exp(𝒥_(; τ, α, )) provides a lower bound on 𝔩_(; α, ), as KL(ℙ_τ(·)||ℙ(·|⊙, α, ) ) ≥ 0 for any parameter (α, ). The variational estimator is obtained using the EM algorithm derived in <cit.>, which alternates between the following two steps :
            
              *  Estimation Step : for given parameters (α, ), the variational parameter τ maximizing 𝒥_(; τ, α, ) is given by the following fixed point equation :  
                
                τ^i_a =  c_i α_a ∏_j≠ i : _ij = 1∏_b ≤ k(_ab^_ij(1-_ab)^1-_ij)^τ_b^j   where c_i is a normalising constant;
            
              *  Maximisation Step : for a given parameter τ, the parameters (α, ) maximizing 𝒥_(; τ, α, ) are given by  
                
                α_a = ∑_i τ^i_a/n   ,    _ab = ∑_i ≠ j_ijτ^i_aτ^j_b _ij/∑_i ≠ j_ijτ^i_aτ^j_b.
            
            This algorithm is implemented in the package https://cran.r-project.org/web/packages/missSBM/index.html. Since the EM algorithm is not guaranteed to converge to a global maximum, a clever initialization of the parameter τ using a clustering step is performed.
            
            Theoretical properties of the variational estimator have been first studied in <cit.> for the dense stochastic block model, in <cit.> for the sparse stochastic block model, and more recently in <cit.> for a dense stochastic block model with observations missing uniformly at random. These results establish that maximizing max_τ∈𝒯𝒥_(; τ, α, ) is equivalent to maximizing 𝔩_(; α, ). They also establish that the estimator obtained by maximizing 𝔩_(; α, ) converges to the true parameters (α^*, ^*), and conclude that (α^VAR, ^VAR) also converges to (α^*, ^*). 
            
            We build on this approximation and use the following estimator for the label function z^*:
            
                .
                         ∀ i ≤ n,  z^VAR(i) ≜_a≤ k(τ^VAR)^i_a
            
            Next, we compare the asymptotic behavior of z^VAR with that of the profile maximum likelihood estimator of the label function z, defined as
            
                (,z) ∈∈𝒬, z∈_n,k∑_i<j_ij (_ij,_z(i)z(j))
            
            where we use the convention that ∈𝒬 if there exists α such that (α, ) ∈𝒬. 
            
            In Proposition <ref>, we establish the asymptotic equivalence of z^VAR and of z in the case of sparse stochastic block model with full observations. To prove it, we will assume that the proportions of different communities are held constant, while the probabilities of connections between communities may decreases at rate ρ_n. That is, the parameters (α^*,^*) verify
            
            
              * α^* = α^0 for some fixed α^0 such that α^0_a >0 for any a∈{1,...,k}
              * ^* = ρ_n ^0 for some fixed ^0 ∈ (0,1)^k × k such that ka,b = 1∑α^0_aα^0_b^0_ab = 1
            The normalisation constraint ka,b = 1∑α^0_aα^0_b^0_ab = 1 ensure the identifiability of the parameters (^0, ρ_n) (see <cit.>). In the following, we denote by 𝒬 the set of parameters (α, ) verifying Assumptions <ref> and <ref>. Note that the stochastic block model is identifiable up to a simultaneous permutation of communities and of rows and columns of the parameters ^*. For any two label functions z, z', we write z ∼ z' if there exists a permutation σ of {1, ..., k} such that (z(σ(a)))_a≤ k = (z(a))_a≤ k. 
            Assume that (z^*,) is generated from a stochastic block model with parameters (α^*, ^*) ∈𝒬 such that ^0 has no identical columns and the sparsity inducing sequence ρ_n satisfies ρ_n≫log(n)/n.
            Then, under Assumptions <ref> and <ref>, ℙ(z^VAR∼z) → 1 when n →∞.
            
            
            The proof of Proposition <ref> relies on results established in <cit.> and <cit.>, and is given in Section <ref>. These results have been extended in <cit.> to the case of dense stochastic block model with incomplete observation of the network, where entries of the adjacency matrix are observed uniformly at random. Building on their results, Proposition <ref> can be extended to the case of missing observations.
            
            Once we have estimated the community labels, we can derive an estimator of the matrix of connection probabilities. For all (a,b) ∈{1,..,k}, define 
            
                n_ab(z^VAR)  = {[        | (z^VAR) ^-1(a)|×|( z^VAR)^-1(b)|                                     a ≠ b; | (z^VAR) ^-1(a)|×(| (z^VAR)^-1(a)| - 1 )                                           ].
            
            and 
            
                ^ML-VAR_ab≜i∈ (z^VAR)^-1(a),j∈ (z^VAR) ^-1(b)∑_ij/n_ab(z^VAR).
            
            Proposition <ref> implies that with large probability, there exists a permutation σ of {1, ..., k} such that (z^VAR(σ(a)))_a ≤ k = (z(a))_a ≤ k. When this hold, (^ML-VAR_σ(a), σ(b))_a,b≤ k = (_a,b)_a,b≤ k, and the risk bounds obtained in Theorem <ref> for the estimator  hold for the tractable estimator  ^VAR, defined as
            
                ^VAR_i≠ j  =   ^ML-VAR_z^VAR(i), z^VAR(j),  ^VAR_ii = 0.
            
            Assume that (z^*,) is generated from a stochastic block model with parameters (α^*, ^*) ∈𝒬 such that ^0 has no identical columns and the sparsity inducing sequence ρ_n satisfies ρ_n≫log(n)/n. Then, under Assumptions <ref> and <ref>, there exists a constant C_^0>0 depending on ^0 such that 
            
                ℙ(‖^* - ^VAR‖_2^2 ≤  C_^0ρ_n(k^2 + nlog(k)) ) → 1
            when n →∞.
            
            
            § CONCLUSION
            
            
            We have studied the problem of estimating the matrix of connections probabilities for the inhomogeneous random graph model and the graphon model with missing link. We have established a non-asymptotic bound on the risk of the maximum likelihood estimator. In particular, we have shown that, if the entries of the probability matrix decrease at the same rate, our estimator achieves the minimax convergence rate. This result is adaptative to the unknown sampling scheme. Moreover, we show that our estimator can be efficiently approximated using variational methods, and thus used in practice.
            
            
            
            
            § ACKNOWLEDGMENTS
            
            
            The work of O. Klopp was conducted as part of the project Labex MME-DII (ANR11-LBX-0023-01).
            The authors want to thank Catherine Matias and Nicolas Verzelen for 
            extremely valuable suggestions and discussions.
            
             The authors declare that there is no conflict of interest.
            
            
            
             
            
            § PROOFS
            
             
              The proof of Theorem <ref> requires bounding the domain of definition of our estimator away from 0 and 1 in order to ensure that the loss function associated with the maximum likelihood estimator is Lipschitz. The Lipschitz constant here is equal to  1/(1 - ρ_n ) γ_n. We balance this term by ρ_n by taking advantage of the sparsity of the graph, which implies, in particular, the low variance of . For ease of notations, we will assume that 1 - ρ_n≥γ_n. This is the case when the graph is sparse, and our results still hold in the dense case if we replace γ_n by γ_n  (1 - ρ_n) in our bounds.
             
             
            
             §.§ Proof of Theorem <ref>
            
             In previous works on sparse network estimation, the authors used the definition of the least square estimator to bound the norm of the error of this estimator by the scalar product between this error and a noise term. The main difficulty in their proofs consists in bounding this scalar product. Unfortunately, the definition of the maximum likelihood estimator does not yield such a bound, and these technics cannot be used to control its error. Instead, we make use of more refined peeling arguments, in order to take advantage of the Lipschitz continuity of the loss.
             
             Let ϵ_n = C ρ_n^2/γ_n^2( nlog(k) + k^2 ) for some absolute constant C defined as the maximum of the absolute constants appearing in Lemma <ref>, Lemma <ref> and Lemma <ref>, and let ϵ^0 ≜ρ_nϵ_n. We start by considering the following two cases:
            
            Case 1: ‖-‖^2_2,≤ 2 ϵ^0. Then the statement of Theorem <ref> follows from Lemma <ref>:
            
                ‖^*-‖^2_2,≤ 2‖-‖^2_2, + 2‖^*-‖^2_2,≤ 4ρ_n ϵ_n + 16 ρ_n 𝒦_(^*, ).
            Case 2: ‖-‖^2_2, > 2ϵ^0. Then  belongs to the set
            
                𝒮_ = {∈z ∈𝒵_n,k∪𝒯_z: ‖-‖^2_2,≥ 2 ϵ^0, ‖‖_∞≤ρ_n, i<jmin{_ij}≥γ_n . }
            
             The following lemma helps us bound the error in ‖·‖_-norm by the error in ‖·‖_-norm. Its proof departs from previous technics used to study network with missing observations. It allows for non-uniform sampling design, and is one of the main technical contribution of this work.
            
            There exists and absolute constant C>0 such that for all ∈𝒮_ simultaneously we have
            
                |‖ - ‖_2, ^2 - ‖ - ‖_2, ^2 |≤1/2‖ - ‖_2, ^2
            
            with probability greater than 1 - 2exp(-Cn log(k)).
            
            Lemma <ref> implies that with large probability,  belongs to the set 𝒮_ defined as 
            
                𝒮_ = {∈z ∈𝒵_n,k∪𝒯_z: ‖-‖^2_2,≥ϵ^0, ‖‖_∞≤ρ_n, i<jmin{_ij}≥γ_n }.
            
            To bound ‖-‖^2_2, when ∈𝒮_∩𝒮_, we introduce the following notation. For , ' ∈ (0,1)^n × n_sym and , ∈ [0,1]^n × n_sym we set Δ^_(, ') = 𝒦_(, )-𝒦_(, '). Using Lemma <ref> we get
            
                ‖^*-‖^2_2,    ≤    8ρ_n𝒦_(^*, )
                   ≤    8ρ_n 𝒦_(^*, ) + 8ρ_n Δ^^*_(, ).
            
            On the other hand, the definition of  implies that Δ^_(, ) ≤ 0 so 
            
                ‖^*-‖^2_2,    ≤    8ρ_n 𝒦_(^*, ) + 8ρ_n Δ^^*_(, ) - 8ρ_n Δ^_(, ) 
                   ≤    8ρ_n ( 𝒦_(^*, ) + ( Δ^^*_(, ) - Δ^^*_(, ) )+ ( Δ^^*_(, ) - Δ^_(, )) )  .
            
            To bound the terms involved in equation (<ref>), we control ∈𝒮_sup|Δ^^*_(, ) - Δ^^*_(, ) | using the concentration of  around its expectation , 
            and we control 
            ∈𝒮_sup|Δ^^*_(, ) - Δ^_(, ) | conditionally on  using the concentration of  around its expectation ^*.
            
            
            There exists absolute constants C, C'>0 such that for all ∈𝒮_ simultaneously we have
            
                |Δ^^*_(, ) - Δ^^*_(, ) |≤1/2×32ρ_n‖ - ‖_2, ^2 + Cρ_n^2/γ_n^2(nlog(k) + k^2 )
            
            with probability greater than 1 - 2exp(-C'ρ_n nlog(k)).
            
            There exists absolute constants C,C'>0 such that conditionally on , for any ∈𝒮_ simultaneously we have
            
                |Δ^^*_(, ) - Δ^_(, ) |≤1/4× 32 ρ_n‖ - ‖_2, ^2 + Cρ_n^2/γ_n^2(nlog(k) + k^2 )
            
            with probability greater than 1 - 5exp(-C' ρ_n nlog(k)).
            
            Combining Lemma <ref>, Lemma <ref>, Lemma <ref> and (<ref>) yields that there exists two absolute constants C,C'>0 such that with probability greater than 1 - 9exp(-C'ρ_n n log(k))
                ‖^*-‖^2_2,   ≤    8ρ_n𝒦_(^*, )+ 8 ρ_n×1/2× 32 ρ_n‖- ‖_2, ^2 + 8ρ_n×1/4× 32 ρ_n‖- ‖_2, ^2
                      + Cρ_n ρ_n^2/γ_n ^2(nlog(k) + k^2)
                   ≤    8ρ_n𝒦_(^*, )+ 1/8‖- ‖_2, ^2 + 1/16×3/2‖- ‖_2, ^2 + Cρ_n ρ_n^2/γ_n^2(nlog(k) + k^2)
                   ≤    8ρ_n𝒦_(^*, )+ 1/2‖^* - ‖_2, ^2 + 1/2‖^* - ‖_2, ^2 + Cρ_n ρ_n^2/γ_n^2(nlog(k) + k^2).
            
            Lemma <ref> and (<ref>) imply that there exists two absolute constants C, C'>0 such that with probability larger than 1 - 9exp(-C'ρ_n n log(k)),
            
                1/2‖^*-‖^2_2,   ≤    8ρ_n𝒦_(^*, )+ 1/2× 8ρ_n𝒦_(^*, ) + Cρ_n ρ_n^2/γ_n^2(nlog(k) + k^2).
            
             This completes the proof of Theorem <ref>.
            
            
            
             §.§ Proof of Lemma <ref>
            
            
             To prove Lemma <ref>, we show that the probability of the following “bad" event is small:
            
                ℰ≜{∃∈𝒮_: |‖ - ‖_2, ^2 - ‖ - ‖_2, ^2 | > 1/2‖ - ‖_2, ^2}.
            
            We use a standard peeling argument (see, e.g., <cit.>): we slice 𝒮_ in different sets, on which we control ‖ - ‖_2,^2. Recall that ϵ_n ≜ Cρ_n^2/γ_n^2(nlog(k) + k^2 ) where the absolute constant C is larger than the constant appearing in Lemma <ref>, and that ϵ^0 ≜ρ_nϵ_n. For l ∈ℕ^*, we set 
            
                𝒮_l,≜{∈𝒮_:  2^l-1(2ϵ^0) ≤‖ - ‖_2,^2 ≤ 2^l(2ϵ^0)}.
            
            If the event ℰ holds, there exists l ∈ℕ^* such that ∈𝒮_l, and 
            
                |‖ - ‖_2, ^2 - ‖ - ‖_2, ^2 | > 1/2‖ - ‖_2, ^2.
            
            Note that 𝔼[‖ - ‖_2, ^2] =‖ - ‖_2, ^2. The events that we need to control are the following:
            
                ℰ_l≜{∃∈𝒮_l,: |‖ - ‖_2, ^2 - 𝔼[‖ - ‖_2, ^2]| > 2^l-1(2ϵ^0)/2}.
            
            If ℰ holds for some ∈𝒮_, there exists l ∈ℕ^* such that ∈𝒮_l,, thus there exists l ∈ℕ^* such that ℰ_l holds, i.e., ℰ⊂l ∈ℕ^*∪ℰ_l,. For T>0, let 𝒮_(T) be defined as follows:
            
                𝒮_(T) = {∈z ∈𝒵_n,k∪𝒯_z :  ‖‖_∞≤ρ_n, i<jmin{_ij}≥γ_n, ‖ - ‖_2,^2 ≤ T }.
            
            We see that 𝒮_l,⊂𝒮_(2^l ϵ^0), so we only need to control the probability of the events
            
                ℰ(T) = {∃∈𝒮_(T): |‖ - ‖_2, ^2 - 𝔼[‖ - ‖_2, ^2]| > T/4}.
             
            The following lemma helps us bound the probability of the events ℰ(T).
            
             For T>ϵ^0, let Z_T=∈𝒮_(T)sup|‖ - ‖_2, ^2 - ‖ - ‖_2, ^2 |. There exists an absolute constant C>0 such that
             
                ℙ( Z_T≥T/4)≤exp(-CT/ρ_n).
            
             To prove Lemma <ref>, we first show that Z_T concentrates around its expectation and then bound this term. 
            
            Let Z_T be defined as in <ref>. Then
             
                ℙ(Z_T> 2𝔼[Z_T] + T/16) ≤exp(-T/64ρ_n).
            
            Let Z_T be as in Lemma <ref>, then there exists an absolute constant C>0 such that 
            
                𝔼[Z_T] ≤T/16 + Cρ_n ρ_n^2/γ_n^2(nlog(k) + k^2 ).
            
             Putting together Lemma <ref> and Lemma <ref>, we get that there exists an absolute constant C>0 such that 
            
                ℙ( Z_T≥3T/16+ C/8ρ_n ρ_n^2/γ_n^2(nlog(k) + k^2 )) ≤exp(-T/64ρ_n).
            
            Our choice of ϵ_0 allows us to conclude that for T ≥ 2ϵ_0, C/8ρ_n ρ_n^2/γ_n^2(nlog(k) + k^2 ) ≤T/16 and
            
                ℙ( Z_T≥T/4) ≤exp(-T/64 ρ_n).
            
            For this choice of ϵ_0,
             
                ℙ (ℰ )   ≤l=1∞Σℙ (ℰ(2^l(2 ϵ^0)) )
                   ≤l=1∞Σexp(-2Cϵ^0 2^l/ρ_n )
                   ≤l=1∞Σexp(-2Cllog(2)ϵ^0/ρ_n )
                   ≤exp(-2Clog(2)ϵ^0/ρ_n )/1-exp(-2Clog(2)ϵ^0/ρ_n ) = 1/exp(-2Clog(2)ϵ^0/ρ_n ) - 1≤ 2 exp(-C nlog(k) )
             
             for n large enough. This completes the proof of Lemma <ref>.
             
            
            
              §.§.§ Proof of Lemma <ref>
            
            
            To control the deviation of Z_T from its expectation, we apply the following theorem from Bousquet, as stated in <cit.>, Theorem 3.3.16.
            
            Let X_i, i ∈ℕ be independent 𝒮-valued random variables, and let  be a countable class of functions f = (f_1,..., f_n): 𝒮→ [-1,1]^n such that 𝔼[f_i(X_i)] = 0 for any f ∈ and i ∈ [n]. Set
            Z = f ∈sup|1 ≤ i ≤ n∑ f_i(X_i) | and v = f ∈sup1≤ i ≤ n∑𝔼[f_i(X_i)^2]. Then, for any x>0,
            
                ℙ(Z > 𝔼[Z] + x/3 + √(2x(2𝔼[Z] + v))) ≤exp(-x).
            
            We apply Theorem <ref> to the random variable 
            
                Z_T   =   ∈𝒮_(T)sup|‖ - ‖_2, ^2 - ‖ - ‖_2, ^2 |
                   =   ∈𝒮_(T)sup|∑_1 ≤ i < j ≤ n(_ij - _ij)( _ij - _ij)^2 |
                   =   ρ_n ∈𝒮_(T)sup|∑_1 ≤ i < j ≤ n f^_ij(_ij) |
            
            where we set f^_ij(_ij) ≜(_ij - _ij)(_ij - _ij)^2/ρ_n. The set of functions {f^_ij, ∈𝒮_(T) } is separable and we can apply Theorem <ref> (see, e.g., <cit.>, Section 2.1). Note that for any 1≤ i < j ≤ n, 𝔼[f^_ij(_ij)] = 0, | f^_ij(_ij)|≤ 1, 𝔼[(_ij - _ij)^2 ] ≤_ij and |_ij - _ij|≤ρ_n so 
            
                ∈𝒮_(T)sup1≤ i<j ≤ n∑𝔼[f^_ij(X_ij)^2]    ≤   1/ρ_n^2∈𝒮_(T)sup1≤ i<j ≤ n∑_ij(_ij - _ij)^4
                   ≤   ∈𝒮_(T)sup1≤ i<j ≤ n∑_ij(_ij - _ij)^2
                   ≤    T.
            
            Theorem <ref> implies that 
            
                ℙ(Z_T/ρ_n > 1/ρ_n𝔼[Z_T] + x/3 + √(2x(2/ρ_n𝔼[Z_T] + T))) ≤exp(-x) 
                ℙ(Z_T> 𝔼[Z_T] + ρ_n x/3 + √(2xρ_n (2𝔼[Z_T] + ρ_nT))) ≤exp(-x)
                ℙ(Z_T> 𝔼[Z_T] + ρ_n x/3 + 2ρ_nx + 𝔼[Z_T] + ρ_n√(2xT)) ≤exp(-x)
            
            where we have used √(a+b)≤√(a) + √(b) and 2√(ab)≤ a + b. Setting x = T/64ρ_n and noticing that ρ_n ≤ 1 leads to 
            
                ℙ(Z_T> 2𝔼[Z_T] + T/16) ≤exp(-T/64ρ_n).
            
            
              §.§.§ Proof of Lemma <ref>
            
            
            Once we have bounded Z_T by its expectation, we bound 𝔼[ Z_T ]. To do so, we use a symetrization argument and Talagrand's contraction principle (see, e.g., <cit.> for a proof).
            
            Let {_i}_1 ≤ i ≤ n be independent random variables, {_i}_1 ≤ i ≤ n be a Rademacher sequence, and 𝒜 be a subset of ℝ^n, then
            
                𝔼[∈𝒜sup|∑_1≤ i≤ n (_i - 𝔼[_i])_i|]    ≤ 2 𝔼[ ∈𝒜sup|∑_1≤ i≤ n_i _i _i|].
            
             Let {ϕ_i}_1≤ i ≤ n: ℝ→ℝ be 1-Lipshitz functions vanishing at 0, 𝒜 be a compact subset of ℝ^n and {_i}_1≤ i ≤ n be a Rademacher sequence, then
            
                𝔼[∈𝒜sup|1 ≤ i ≤ n∑_iϕ_i(_i)|] ≤  2𝔼[∈𝒜sup|1 ≤ i ≤ n∑_i_i|] .
            
             Recall that
            
                𝔼[Z_T]    =   𝔼[∈𝒮_(T)sup|∑_1 ≤ i < j ≤ n(_ij - _ij)( _ij - _ij)^2 |].
            
            Let (_ij)_1 ≤ i<j≤ n be a Rademacher sequence. Lemma  <ref> implies
            
                𝔼[Z_T]    ≤    2 𝔼[∈𝒮_(T)sup|∑_1 ≤ i < j ≤ n_ij_ij( _ij - _ij)^2 |].
            
            For any 1 ≤ i < j ≤ n, let ϕ_ij: x →x^2/2ρ_n. Note that on [-ρ_n, ρ_n], ϕ_ij is a 1-Lipschitz and vanishes at 0. Applying Lemma <ref>, we get that
            
                𝔼[Z_T]    ≤    4ρ_n 𝔼[∈𝒮_(T)sup|∑_1 ≤ i < j ≤ n_ijϕ_ij(_ij( _ij - _ij) ) |]
                   ≤    8ρ_n 𝔼[∈𝒮_(T)sup|∑_1 ≤ i < j ≤ n_ij_ij( _ij - _ij) |].
            
            We bound the term in  using the following lemma.
            
            Let ∈{, } and let  be a random matrix such that almost surely, ‖‖_∞≤ 1 and that conditionally on , for any 1≤ i < j ≤ n the coefficients _ij are independent and centered. Assume that there exists α>0 such that for any ∈ℝ^n × n_sym, i<j∑𝔼^[_ij^2_ij^2] ≤α‖‖_2,^2. There exists an absolute constant C such that
            
                𝔼^[∈𝒮_(T)sup|∑_1 ≤ i < j ≤ n_ij( _ij - _ij) |] ≤γ_nα T/32× 64^2ρ_n^2 + Cρ_n^2/γ_n(nlog(k) + k^2).
            
            Note that for any 1 ≤ i < j ≤ n, 𝔼[_ij^2] ≤_ij, so for any ∈ℝ^n × n_sym, i<j∑𝔼[_ij^2_ij^2_ij^2] ≤‖‖_2,^2. We apply Lemma <ref> with =, α = 1 and for any 1 ≤ i <j ≤ n, _ij = _ij_ij and combine it with (<ref>) to get that for some absolute constant C
                𝔼[Z_T]    ≤   Tγ_n× 8 ρ_n/32× 64^2 ρ_n^2 + Cρ_n ρ_n^2/γ_n^2(nlog(k) + k^2 )
                   ≤   T/4×64 + Cρ_n ρ_n^2/γ_n (nlog(k) + k^2 ).
            
            This concludes the proof of Lemma <ref>.
            
            
            
              §.§.§ Proof of Lemma <ref>
            
            
            To get an upper bound on 𝔼^[∈𝒮_(T)sup|∑_1 ≤ i < j ≤ n_ij( _ij - _ij) |], we use Bernstein's inequality, which we state here for the reader's convenience: 
            
            Let X_1, ..., X_n be independent centered random variables. Assume that for any i ∈ [n],  | X_i|≤ M almost surely, then
            
                ℙ(|∑_1 ≤ i ≤ nX_i |≥√(2t∑_1 ≤ i ≤ n𝔼[X_i^2]) + 2M/3t) ≤ 2e^-t.
            
            Recall that for ∈{, }, 
                𝒮_(T) = {∈z ∈𝒵_n,k∪𝒯_z :  ‖‖_∞≤ρ_n, i<jmin{_ij}≥γ_n, ‖ - ‖_2,^2 ≤ T }
             and let 𝒮_z(T) ≜𝒯_z ∩𝒮_(T) be the set of matrices in 𝒮_(T) that are block constant for the label z. Let ^z be the projection of  onto 𝒯_z for the -weighted Frobenius norm:
            
                ^z ≜∈𝒯_z ‖ - ‖_2,.
             
            Note that if 𝒮_z(T) ≠∅, then ^z ∈𝒮_z(T). If 𝒮_z(T) = ∅, we set ∈𝒮_z(T)sup|⟨|^z- ⟩| = 0.
            We decompose the error in two terms. 
            
                𝔼^[∈𝒮_(T)sup|∑_1 ≤ i < j ≤ n_ij( _ij - _ij) |]    ≤𝔼^[ z∈𝒵_n,k, 𝒮_z(T) ≠∅sup|⟨| - ^z⟩|]
                     +  𝔼^[ z∈𝒵_n,ksup∈𝒮_z(T)sup|⟨|^z- ⟩|]
                   ≤  (I) + (II).
            
            The term (I) denotes 𝔼^[ z∈𝒵_n,k, 𝒮_z(T) ≠∅sup|⟨| - ^z⟩|] and corresponds to the error induced by an error on the label. The term (II) denotes 𝔼^[ z∈𝒵_n,ksup∈𝒮_z(T)sup|⟨|^z- ⟩|] and corresponds to the error induced by a Bernoulli noise.
            
            Control of (I): To control the first term of (<ref>), recall that for any z ∈𝒵_n,k such that 𝒮_z(T) ≠∅, ^z ∈𝒮_z(T) and by hypothesis,  i<j∑𝔼^[_ij^2(_ij - ^z_ij)^2] ≤α‖- ^z ‖_2,^2 ≤α T. Furthermore, ‖‖_∞≤ 1 so |_ij(_ij - ^z_ij)|≤ρ_n. Since |𝒵_n,k|≤ nlog(k), the union bound and Bernstein's inequality imply
            
                ℙ^(z∈𝒵_n,k, 𝒮_z(T) ≠∅sup|⟨|- ^z⟩|≥√(2α T(t + nlog(k))) + 2ρ_n/3(t + nlog(k)))    ≤    2e^-t
                ℙ^(z∈𝒵_n,k, 𝒮_z(T) ≠∅sup|⟨|- ^z⟩|≥γ_nα T/64^3ρ_n^2 + (2ρ_n/3 + 64^3ρ_n^2/γ_n)(t + nlog(k)))    ≤    2e^-t.
            
            Integrating the last inequality and using ρ_n/γ_n≥ 1, we get that for some absolute constant C
                (I) ≤αγ_n T/64^3ρ_n^2 + C ρ_n^2/γ_n nlog(k).
            Control of (II): The control of the second term of (<ref>) is more involved. We adapt the argument developped in <cit.> and consider only z ∈_n,k such that 𝒮_z(T) ≠∅. By property of the projection, we have for any ∈𝒮_z(T), ‖ - ^z‖_2,^2 ≤‖ - ‖_2,^2 ≤ T. Thus ( ^z- ) ∈𝒜_z(T), where 
                𝒜_z(T) ≜{∈𝒯_z: ‖‖_∞≤ρ_n, ‖‖_2,^2 ≤ T },
             so ∈𝒮_z(T)sup|⟨|^z- ⟩|≤∈𝒜_z(T)sup|⟨|⟩|. Let ^z ∈𝒜_z(T) be such that 
            
                |⟨|^z⟩|≜∈𝒜_z(T)sup|⟨|⟩|.
            
            Note that →|⟨|⟩| is continous and reaches its supremum on 𝒜_z(T). Indeed, either for any 1≤ i<j≤ n, _ij >0 so ‖·‖_ is a norm and 𝒜_z(T) is compact, or we can find a subspace 𝒱 of ℝ^(n-1)(n-2)/2 of dimension |{ 1 ≤ i < j ≤ n: _ij >0 }| such that for any ∈ℝ^(n-1)(n-2)/2, ⟨|⟩ = ⟨|𝒫_𝒱() ⟩ where 𝒫_𝒱 denotes the projection onto 𝒱, and 𝒜_z(T) ∩𝒱 is compact.
            
            To control |⟨|^z⟩|, we build a finite set with small cardinality that approximates ^z well both in the weighted Frobenius norm and in the supremum norm. More precisely, our goal is to construct a finite set 𝒞_z(T) containing a matrix  such that 2(^z - ) ∈𝒜_z(T). To apply Bernstein's inequality, we also need to be able to control the suppremum norm on this set. Our first step will be to construct such a set. 
            
            We denote by ℬ_r the ball centered at 0 and of radius r for the weighted Frobenius norm ‖·‖_2,. Let 𝒞_z be a minimal √(T)/2-net for the weighted Frobenius norm on ℬ_√(T)∩𝒯_z.  Note that 𝒜_z ⊂ℬ_√(T)∩𝒯_z, so there exists ∈𝒞_z(T) such that ‖ - ^z ‖_2, ≤√(T)/2. Since our choice of net does not allow us to directly bound ‖- ^z ‖_∞, we extend this net using the following argument. For any ∈𝒞_z and any matrix ∈{-1,0,1}^k × k, let ^∈ℝ^n× n be such that ^_ii = 0 and for any i<j, 
            
                ^_ij = (_ij)(|_ij|ρ_n )( 1 - |_z(i) z(j)|) + _z(i) z(j)ρ_n/2.
            
            Recall that ‖^z ‖_∞≤ρ_n so for any ∈𝒞_z(T) we have |(_ij)(|_ij|ρ_n ) - ^z_ij|≤|_ij - ^z_ij|. This implies that ‖^0- ^z ‖_2,≤‖- ^z ‖_2, .
            
            Now, let 𝒞_z(T)= {^: ∈𝒞_z(T), ∈{-1,0,1}^k × k_sym} and = ∈{-1,0,1}^k × k‖^ - ^z ‖_∞. By definition, for any (a,b) ∈ k × k,  minimises |^_z^-1(a) z^-1(b) - ^z_z^-1(a) z^-1(b)|, so it is also a minimizer of ‖^ - ^z ‖_2, = a,b ∈ [k]∑((i,j) ∈ z^-1(a) × z^-1(b), i ≠ j∑_ij) |^_z^-1(a) z^-1(b) - ^z_z^-1(a) z^-1(b)|^2. Therefore 
                ‖^- ^z ‖_2,≤‖^0- ^z ‖_2,≤‖- ^z ‖_2,≤√(T)/2.
             
            Furthermore ‖^- ^z ‖_∞≤‖^^*- ^z ‖_∞, where ^*_ab = (^z_z^-1(a)z^-1(b)). By construction, 
                ‖^^*- ^z ‖_∞ = sup_i<j|^z_ij - (^z_ij) ρ_n/2| = sup_i<j||^z_ij| - ρ_n/2|≤ρ_n/2.
             Hence, 2(^z - ^) ∈𝒜_z(T). Thus, we have shown that
            
                2 |⟨|^z - ^⟩|   ≤   ∈𝒜_z(T)sup|⟨|⟩|≜|⟨|^z⟩|
                
                2|⟨|^z ⟩| - 2|⟨|^⟩|   ≤   |⟨|^z⟩|
                |⟨|^z ⟩|   ≤    2|⟨|^⟩| .
            
            This and (<ref>) allows us to conclude that 
            
                z∈𝒵_n,ksup∈𝒮_z(T)sup|⟨|^z - ⟩|≤ 2 z∈𝒵_n,ksup∈𝒞_z(T)sup|⟨|⟩|.
            
            To bound the right hand side of (<ref>), we recall that by hypothesis for any ∈𝒞_z(T),  i<j∑𝔼^[_ij^2_ij^2] ≤α‖‖_2,^2 and note that ‖‖_∞≤ρ_n and ‖‖_2,≤√(T). We use Bernstein's inequality and the union bound to obtain
            
                ℙ(z∈𝒵_n,ksup∈𝒞_z(T)sup|⟨|⟩|≥√(2α Tt) + 2/3t)    ≤    2e^-t + nlog(k) + ∈𝒞_z(T)suplog(|𝒞_z(T) |).
            
            By construction of 𝒞_z(T), we have |𝒞_z(T)| = |𝒞_z(T)|× 3^k^2. The following classical result on the covering number of a ball will help us bound |𝒞_z(T)| (see, e.g., Lemma 5.2 in <cit.>).
            
            Let ℬ_r the ball of a subspace of ℝ^n of dimension d centered at 0 and of radius r for the euclidean norm, and 𝒩(ℬ_r,ϵ) its ϵ-covering number, that is the minimal cardinality of a set 𝒞 such that for any ∈ℬ_r, there exists ∈𝒞 such that ‖ - ‖≤ϵ. Then 
            
                𝒩(ℬ_r,ϵ) ≤(3r/ϵ)^d.
            
            Extending the proof Lemma <ref> to a weighed euclidean norm is straightforward. Putting Lemma <ref> into equation (<ref>) and noting that 𝒯_z spans a subspace of ℝ^(n-1)(n-2)/2 of dimension k(k-1)/2, we get that for some absolute constant C
                ℙ(z∈𝒵_n,ksup∈𝒞_z(T)sup|⟨|⟩|≥√(2α T( t + nlog(k) + k^2log(C))) + 2ρ_n/3(t + nlog(k) + k^2log(C)))    ≤   2e^-t
                ℙ(z∈𝒵_n,ksup∈𝒞_z(T)sup|⟨|⟩|≥αγ_n T/2 × 64^3ρ_n^2 + (2ρ_n/3 + 2× 64^2ρ_n^2/γ_n)(t + nlog(k) + k^2log(C))) ≤ 2e^-t.
            
             We integrate and find for some absolute constant C>0
                𝔼[
                z∈𝒵_n,ksup∈𝒮_z(T)sup|⟨|^z- ⟩|]  ≤αγ_n T/64^3ρ_n^2  + Cρ_n^2/γ_n(nlog(k) + k^2).
            
            Combining the bounds (<ref>) and (<ref>) yields the desired result.
            
            
            
             §.§ Proof of Lemma <ref>
            
             The proof of Lemma <ref> closely follows that of Lemma <ref> and we only sketch it. Recall that ϵ_n ≜ Cρ_n^2/γ_n^2(nlog(k) + k^2 ) where the absolute constant C is larger than the constant appearing in Lemma <ref>, and that ϵ^0 ≜ρ_nϵ_n. We show that the probability of the following “bad" event is small:
            
                ℰ≜{∃∈𝒮_:|Δ^^*_(, ) - Δ^^*_(, ) | > 1/2×32ρ_n‖ - ‖_2, ^2 + ϵ_n }.
            
            Again, we slice 𝒮_ in different sets 𝒮_l, defined as
            𝒮_l,≜{∈𝒮_:  32^l-1(2ϵ^0) ≤‖ - ‖_2,^2 ≤ 32^l(2ϵ^0)}
            on which we control the events ℰ_l≜{∃∈𝒮_l,:|Δ^^*_(, ) - Δ^^*_(, ) | > 32^l-1× 2ϵ^0/4× 32ρ_n + ϵ_n }.
            To do this, we set 𝒮_(T) ≜{∈𝒮_: ‖ - ‖_2,^2 ≤ T} and we control the probability of the events
            
                ℰ(T) = {∃∈𝒮_(T): |Δ^^*_(, ) - Δ^^*_(, ) | > T/64^2ρ_n +ϵ_n }.
             
            The following lemma helps us bound the probability of the events ℰ(T).
            
             Let Z_T=∈𝒮_(T)sup|Δ^^*_(, ) - Δ^^*_(, ) |. There exists two absolute constants C, C' >0 such that
             
                ℙ( Z_T≥T/64^2ρ_n +  Cρ_n^2/γ_n^2(nlog(k) + k^2 )) ≤exp(-C'Tγ_n^2/ρ_n^2).
            
             To prove Lemma <ref>, we first show that Z_T concentrates around its expectation and then bound this term. 
            
            Let Z_T be defined as in Lemma <ref>. Then there exists an absolute constant C>0 such that 
            
                ℙ(Z_T> 2𝔼[Z_T] + T/2× 64^2ρ_n) ≤exp(-CTγ_n^2/ρ_n^2).
            
            Let Z_T be as in Lemma <ref>, then there exists an absolute constant C>0 such that 
            
                𝔼[Z_T] ≤T/4× 64^2ρ_n + Cρ_n^2/γ_n^2(nlog(k) + k^2 ).
            
            Putting together Lemma <ref> and Lemma <ref>, we get that there exists two absolute constants C,C'>0 such that
             
                ℙ( Z_T≥T/64^2ρ_n+ Cρ_n^2/γ_n^2(nlog(k) + k^2)) ≤exp(-C'Tγ_n^2/ρ_n^2).
            
            This concludes the proof of Lemma <ref>.
             
             
            Lemma <ref> and the arguments developped to prove Lemma <ref> help us conclude the proof of Lemma <ref>.
             
            
            
              §.§.§ Proof of Lemma <ref>
            
            
            Recall that by definition of Z_T,
            
                Z_T   =   ∈𝒮_(T)sup|∑_1≤ i<j ≤ n(_ij - _ij) ( ^*_ijlog(_ij/_ij) + (1 - ^*_ij) log(1 - _ij/1 - _ij) )|
                   =   1/γ_n∈𝒮_(T)sup|∑_1 ≤ i < j ≤ n f^_ij(_ij) |
            
            where we set f^_ij(_ij) ≜γ_n(_ij - _ij) ( _ij^* log(_ij/_ij) + (1 - _ij^*) log(1 - _ij/1 - _ij) ). Assuming that γ_n ≤ 1 - ρ_n, x →log(x) and x →log(1-x) are 1/γ_n - Lipshitz on [γ_n, ρ_n] so 
            
                |_ij^* log(_ij/_ij) + (1 - _ij^*) log(1 - _ij/1 - _ij) |≤^* |_ij - _ij|/γ_n + (1 - ^*) |_ij - _ij|/γ_n≤|_ij - _ij|/γ_n
            
            which implies that for any 1≤ i < j ≤ n, | f^_ij(_ij)|≤ 1. Moreover for any 1≤ i < j ≤ n, 𝔼[f^_ij(_ij)] = 0 and 𝔼[(_ij - _ij)^2 ] ≤_ij, hence
            
                ∈𝒮_(T)sup1≤ i<j ≤ n∑𝔼[f^_ij(X_ij)^2]    ≤   γ_n^2∈𝒮_(T)sup1≤ i ≤ n∑_ij( _ij^* log(_ij/_ij) + (1 - _ij^*) log(1 - _ij/1 - _ij) )^2
                   ≤   γ_n^2 ∈𝒮_(T)sup1≤ i ≤ n∑_ij1/γ_n^2( _ij - _ij)^2
                   ≤    T.
            
            Then, Theorem <ref> implies
            
                ℙ(γ_n Z_T > γ_n𝔼[ Z_T] + x/3 + √(2x(2γ_n𝔼[ Z_T] + T))) ≤exp(-x) 
                ℙ( Z_T> 𝔼[ Z_T] +  x/3γ_n +  4x/γ_n + 𝔼[ Z_T] + 2x× 4 × 64^2ρ_n/γ_n^2 + T/4 × 64^2ρ_n) ≤exp(-x)
                ℙ( Z_T> 2 𝔼[ Z_T] +  9× 64^2 xρ_n/γ_n^2 + T/4 × 64^2ρ_n) ≤exp(-x)
            
            where we have used √(a+b)≤√(a) + √(b), √(ab)≤ a + b and ρ_n/γ_n≥ 1. Setting x = Tγ_n^2/9× 64^2 × 4 × 64^2 ρ_n^2 yields the desired result.
            
            
            
              §.§.§ Proof of Lemma <ref>
            
            
            In Lemma <ref>, we bound
            
                𝔼[ Z_T]    =   𝔼[ ∈𝒮_(T)sup|∑_1≤ i<j ≤ n(_ij - _ij) ( _ij^* log(_ij/_ij) + (1 - ^*) log(1 - _ij/1 - _ij) )|].
            
            Let (_ij)_1 ≤ i<j≤ n be a Rademacher sequence. We apply Lemma  <ref> and get
            
                𝔼[  Z_T]    ≤    2 𝔼[ ∈𝒮_(T)sup|∑_1≤ i<j ≤ n_ij_ij( _ij^* log(_ij/_ij) + (1 - _ij^*) log(1 - _ij/1 - _ij) )|].
            
            For any 1 ≤ i < j ≤ n, let ϕ_ij: x →γ_n/2ρ_n_ij(^*_ijlog(_ij - x/_ij) + (1 - ^*_ij) log(1 + x - _ij/1 - _ij) ). Note that on [_ij - ρ_n, _ij - γ_n], ϕ_ij is 1-Lipschitz and vanishes at 0. Then we apply Lemma <ref> and compute 
            
                𝔼[  Z_T]    ≤   4ρ_n/γ_n𝔼[∈𝒮_(T)sup|∑_1 ≤ i < j ≤ n_ijϕ_ij( _ij( _ij - _ij) )|]
                   ≤   8ρ_n/γ_n𝔼[∈𝒮_(T)sup|∑_1 ≤ i < j ≤ n_ij_ij( _ij - _ij) |].
            
            Now, applying Lemma <ref> with α = 1 and = allows us to conclude that there exists an absolute constant C>0 such that 
                𝔼[ Z_T] ≤T/8× 64^2ρ_n + Cρ_n^3/γ_n^2(nlog(n) + k^2) ≤T/8× 64^2ρ_n + Cρ_n^2/γ_n^2(nlog(n) + k^2).
            
            
             §.§ Proof of Lemma <ref>
            
             
             The proof of Lemma <ref> closely follows that of Lemma <ref>, and we only sketch it. Recall that ϵ_n ≜ Cρ_n^2/γ_n^2(nlog(k) + k^2 ) where the absolute constant C is larger than the constant appearing in Lemma <ref>, and that ϵ^0 ≜ρ_nϵ_n. We show that conditionally on , the probability of the following “bad" event is small and does not depend on :
            
                ℰ_≜{∃∈𝒮_: |Δ^^*_(, ) - Δ^_(, ) | > 1/2× 64 ρ_n‖ - ‖_2,^2 + ϵ_n}.
            
            We slice 𝒮_ in the following sets 𝒮_l,≜{∈𝒮_:  64^l-1ϵ^0 ≤‖ - ‖_2,^2 ≤ 64^lϵ^0} and control the probability of the events 
            ℰ_l,≜{∃∈𝒮_l,: |Δ^^*_(, ) - Δ^_(, ) | > 64^lϵ^0 /2× 64^2ρ_n + ϵ_n }.
            To do this, we control the probability of the events
            ℰ_(T) = {∃∈𝒮_(T): |Δ^^*_(, ) - Δ^_(, ) | > T/2×64^2ρ_n +ϵ_n }
            where 𝒮_(T) = {∈𝒮_:  ‖ - ‖_2,^2 ≤ T }.
             Let Z_T,=∈𝒮_(T)sup|Δ^^*_(, ) - Δ^_(, ) |. There exists two absolute constants C, C' >0 such that
            ℙ^( Z_T,≥T/2×64^2ρ_n + Cρ_n^2/γ_n^2(nlog(k) + k^2 )) ≤ 4exp(-C'γ_n^2 T/ρ_n^2).
             To prove Lemma <ref>, we first show that Z_T, concentrates around its expectation and then bound this term. 
            
            Let Z_T, be as in Lemma <ref>, then there exists two absolute constants C, C'>0 such that 
            
                ℙ^( | Z_T, - 𝔼^ (Z_T,) | > Cρ_n/γ_n^2 + T/4 × 64^2ρ_n)≤ 4 exp(-C'Tγ_n^2/ρ_n^2).
            
            Let Z_T, be as in Lemma <ref>, then there exists an absolute constant C>0 such that 
            
                𝔼^[Z_T,] ≤T/4 × 64^2 ρ_n + Cρ_n^2/γ_n^2(nlog(k) + k^2 ).
            
             Putting together Lemma <ref> and Lemma <ref>, we get that 
             
                ℙ^( Z_T,≥T/2×64^2ρ_n + Cρ_n^2/γ_n^2(nlog(k) +1/ρ_n +k^2 )) ≤ 4exp(-C'γ_n^2 T/ρ_n^2).
            
             If nρ_n →∞, for n large enough n > 1/ρ_n. This yields the desired result.
             
             We combine Lemma <ref> and the arguments developed in Lemma <ref>, and note that ℙ^(_) does not depend on  to conclude the proof of Lemma <ref>.
             
             
            
              §.§.§ Proof of Lemma <ref>
            
             
             In this Section, we prove the Lemma <ref> that helps us bound | Z_T, - 𝔼^ (Z_T,) | with hight probability. To prove that Z_T, concentrates around its mean, we use the following version of Talagrand's Theorem for Lipschitz convex functions (for a proof, see Theorem 3.3 of <cit.>).
            
            Suppose that f: [-1, 1]^N→ℝ is a convex Lipschitz function with Lipschitz constant L. Let R_1,..., R_N be independent random variables taking value in [-1,1]. Let Z:= f(R_1,...,R_N). Then for any t ≥ 0,
            
                ℙ( | Z - 𝔼 (Z) | > 16L + t )≤ 4 e^(-t^2/2L^2) .
             
            Recall that 
            
                Z_T,    =∈𝒮_(T)sup|Δ^^*_(, ) - Δ^_(, ) |
                    = ∈𝒮_(T)sup|∑_1≤ i<j ≤ n(_ij_ij-_ij_ij^*) ( log (_ij/_ij ) - log (1-_ij/1-_ij )) |.
            
            Note that Z_T, = f() where f() is defined for ∈ [-1,1]^(n-1)(n-2)/2 by 
            
                f:    →∈𝒮_(T)sup|∑_1≤ i<j ≤ n_ij(_ij-_ij^*) ( log (_ij/_ij ) - log (1-_ij/1-_ij )) |.
            
             It is easy to see that f is indeed convex. Our next step is to show that f is Lipschitz. Let , ∈ [-1,1]^(n-1)(n-2)/2,
            
                | f() - f() |   =   |∈𝒮_(T)sup|∑_1≤ i<j ≤ n_ij(_ij-_ij^*) ( log (_ij/_ij ) - log (1-_ij/1-_ij )) |
                       - ∈𝒮_(T)sup|∑_1≤ i<j ≤ n_ij(_ij-_ij^*) ( log (_ij/_ij ) - log (1-_ij/1-_ij )) ||
                   ≤   ∈𝒮_(T)sup||∑_1≤ i<j ≤ n_ij(_ij-_ij^*) ( log (_ij/_ij ) - log (1-_ij/1-_ij )) |
                       - |∑_1≤ i<j ≤ n_ij(_ij-_ij^*) ( log (_ij/_ij ) - log (1-_ij/1-_ij )) ||
                   ≤   ∈𝒮_(T)sup|∑_1≤ i<j ≤ n_ij(_ij-_ij) ( log (_ij/_ij ) - log (1-_ij/1-_ij )) |
                   ≤   ∈𝒮_(T)sup{∑_1≤ i<j ≤ n_ij| (_ij-_ij) log (_ij/_ij) | + _ij| (_ij-_ij) log (1-_ij/1-_ij)|}
                   ≤   ∈𝒮_(T)sup‖ - ‖_2( ∑_1≤ i<j ≤ n_ij(log (_ij/_ij) )^2 + _ij(log (1-_ij/1-_ij))^2)^1/2
            
            where we have used that ∈{0,1}^n× n. Thus f is Lipschitz with Lipschitz constant 
                ∈𝒮_(T)sup( ∑_1≤ i<j ≤ n_ij(log (_ij/_ij) )^2 + _ij(log (1-_ij/1-_ij))^2)^1/2.
            
            As stated before, assuming that γ_n ≤ 1-ρ_n, x →log(x) and x →log(1-x) are Lipschitz functions on [γ_n, ρ_n] with Lipschitz constant γ_n^-1. Thus f is Lipschitz with Lipschitz constant
            
                ∈𝒮_(T)sup( ∑_1≤ i<j ≤ n_ij(|_ij - _ij|/γ_n)^2 + _ij(|_ij - _ij|/γ_n)^2)^1/2.
            
            This implies
            
                | f() - f() |   ≤   ‖ - ‖_2 ∈𝒮_(T)sup√(2)‖- ‖_2, /γ_n≤‖ - ‖_2 √(2T)/γ_n.
            
            We have shown that f has a Lipschitz constant L = √(2T)/γ_n. Applying Theorem <ref> for t = T/8 × 64^2 ρ_n, we get
            
                ℙ^( | Z_T, - 𝔼 (Z_T, ) | > 16√(2 T)/γ_n + T/8 × 64^2ρ_n)≤ 4 exp(-Tγ_n^2/8^2 × 2 × 64^4 ρ_n^2).
            
            Using for β >0, 2√(ab)≤β a^2 + b^2/β  yields
            
                ℙ^( | Z_T,  - 𝔼 (Z_T, ) | > 8^2 × 64^2 × 16 ρ_n/γ_n^2 + T/8 × 64^2ρ_n+ T/8 × 64^2ρ_n)≤ 4 exp(-Tγ_n^2/4 × 4^2 × 32^4 ρ_n^2).
            
             
             This concludes the proof of Lemma <ref>.
            
            
            
             §.§ Proof of Lemma <ref>
            
             Once we have shown that Z_T, concentrates around its mean, we bound 𝔼[ Z_T, ]. To do so, we follow the steps of Lemma <ref>.
              Let _1≤ i<j ≤ n a Rademacher sequence. Applying Lemma <ref>, we get
              
                𝔼^[Z_T,]    = 𝔼^[ ∈𝒮_(T)sup|∑_1≤ i<j ≤ n_ij(_ij-𝔼[_ij] ) ( log (_ij/_ij ) - log (1-_ij/1-_ij )) |] 
                   ≤ 2 𝔼^[ ∈𝒮_(T)sup|∑_1≤ i<j ≤ n_ij_ij_ij( log (_ij/_ij ) - log (1-_ij/1-_ij )) |] .
            
            For any 1 ≤ i < j ≤ n, let ϕ_ij: x →1/2γ_n_ij_ij( log(_ij - x/_ij) - log(1 + x - _ij/1 - _ij) ). Note that ϕ_ij is 1-Lipschitz and vanishes at 0 on the interval [_ij - ρ_n, _ij - γ_n]. Indeed,
            
                ϕ_i(x)'    =   1/2γ_n_ij_ij( -1/_ij - x - 1/1 + x - _ij)
                   ≤   _ij_ij.
            
             By definition of the functions ϕ_ij, 
                𝔼^[Z_T,] ≤4/γ_n𝔼^[ ∈ S_(T)sup|i<j∑_ijϕ_ij(_ij_ij(_ij- _ij))  |].
             We apply Lemma <ref> to get
             
                𝔼^[ Z_T,] ≤8/γ_n𝔼^[ ∈ S_(T)sup|i<j∑_ij_ij_ij(_ij- _ij))  |].
            
            Next, we apply Lemma <ref> with =, _ij = _ij_ij_ij and α = ρ_n. Note that ‖‖_∞≤ 1 and that for any matrix , i<j∑𝔼^[_ij^2_ij^2_ij^2] ≤ρ_n‖‖_2,^2. Combining Lemma <ref> and (<ref>) yields 
            
                𝔼^[ Z_T,]   ≤8/γ_n×(Tγ_n/32× 64^2ρ_n + Cρ_n^2/γ_n(nlog(k) + k^2)).
            
            This concludes the proof of Lemma <ref>.
             
            
            
             §.§ Proof of Theorem <ref>
            
            
            Our proof relies on two steps: first, we show that with high probability, d is close to its expected value, which belongs to [γ_n, ρ_n]. More precisely, let γ_n = C_inf/2ρ_nlog(n)^-1/5 and ρ_n = ( 1 + C_inf/2)ρ_nlog(n)^1/5. We prove that with high probability, γ_n≤γ_n≤γ_n and ρ_n ≤ρ_n≤ρ_n. Then this implies that the oracle matrix  belongs to the set of definition of our estimator and its likelihood is greater than that of . Then both  and  belong to the set [γ_n, ρ_n]^n × n and we adapt the proof of Theorem <ref> to get the desired result.
            
            Let = {γ_n∈[ γ_n, γ_n], ρ_n∈[ρ_n, ρ_n] }. There exists a positive constant C and an integer N, both depending only on C_inf, such that ∀ n ≥ N, ℙ() ≥ 1 - exp(-Cnρ_n).
            
            Note that ‖ - ^*‖_∞≤ 1 almost surely, and that for any 1 ≤ i < j ≤ n, (_ij - ^*_ij) is centered and has a variance smaller than ρ_n. Applying Bernstein's inequality <ref>  yields
            
                ℙ( |∑_(i,j) ∈Ω(_ij - ^*_ij)|≥√(2tnρ_n) + 3t/2)    ≤    2e^-t, ∀ t>0.
            
            Choosing t = ρ_nn C with C>0 sucht that √(2C) + 3C/2≤C_inf/2 yields 
            
                ℙ( |d - ∑_(i,j) ∈Ω^*_ij/n|≥C_inf/2ρ_n)    ≤    2e^-Cnρ_n.
            
            Note that  in the sparse graphon model (<ref>), when 0 < C_inf≜(x,y) ∈ [0,1]^2infW^*(x,y), we see that γ_n = C_infρ_n and ∑_(i,j) ∈Ω^*_ij/n∈[γ_n, ρ_n ] = [C_infρ_n, ρ_n ]. So, with probability greater than 1 - 2e^-Cnρ_n, A∈[C_infρ_n/2, (1 +C_inf/2) ρ_n]. Let N be such that log(N)^-1/5≤C_inf/1 + C_inf/2 and log(N)^1/5≥ 2C_inf^-1. For any n ≥ N, with probability greater than 1 - 2e^-Cnρ_n, γ_n∈[ γ_n, γ_n] and ρ_n∈[ρ_n, ρ_n].
            
            
            To prove Theorem <ref>, we work conditionally on the event . Note that in the model (<ref>), the law of the remaining entries (A_i,j)_(i,j) ∉Ω is independent of . Since on  both  and ^* belong to the set [ γ_n, ρ_n], we have
            
            
                ‖ - ^* ‖_2^2    =   ∑_(i,j) ∈Ω(_ij - ^*_ij)^2 + ∑_(i,j) ∉Ω(_ij - ^*_ij)^2 
                   ≤     nρ_n^2+ ∑_(i,j) ∉Ω(_ij - ^*_ij)^2.
            
            
              We adapt the proof of Theorem <ref> to bound the second term. Let ϵ_n≜ C ( ρ_n/γ_n)^2 (nlog(k) + k^2 ) where C is the same absolute constant as in Theorem <ref>, and let ϵ^0 ≜ρ_n ϵ_n. We start by considering the following two cases:
            
            
            Case 1: ∑_(i,j) ∉Ω(_ij - _ij)^2 ≤ϵ^0. Then, the statement of Theorem <ref> follows from (<ref>) and Lemma <ref>:
            
                ∑_(i,j) ∉Ω(_ij - ^*_ij)^2    ≤    2∑_(i,j) ∉Ω(_ij - _ij)^2  + 2∑_(i,j) ∉Ω(_ij - ^*_ij)^2
                   ≤    2ρ_nϵ_n + 16 ρ_n𝒦(^*, )
                   ≤    Clog(n)ρ_n( 𝒦(^*, )+nlog(k) + k^2).
            Case 2: ∑_(i,j) ∉Ω(_ij - _ij)^2 > ϵ^0. Then  belongs to the set 
                𝒮 = {∈z ∈𝒵_n,k∪𝒯_z: ∑_(i,j) ∉Ω(_ij - _ij)^2 > ϵ^0, ‖‖_∞≤ρ_n, i<jmin{_ij}≥γ_n}.
            
            
            As before, Lemma <ref> implies
            
                ∑_(i,j) ∉Ω(_ij - ^*_ij)^2    ≤    8ρ_n∑_(i,j) ∉Ω𝒦(^*_ij, _ij)
                   ≤    8ρ_n𝒦(^*, )+8ρ_n∑_(i,j) ∉Ω (𝒦(^*_ij, _ij)-𝒦(^*_ij, _ij) ).
            
            On the event ,  belongs to the set of matrices on which the maximum likelihood estimator is defined, thus the definition of  implies ∑_(i,j) ∉Ω (𝒦(_ij, _ij)-𝒦(_ij, _ij)) ≤ 0 and
            
                ∑_(i,j) ∉Ω(_ij - ^*_ij)^2 ≤ 8ρ_n𝒦(^*, )+8ρ_n∑_(i,j) ∉Ω (𝒦(^*_ij, _ij)- 𝒦(_ij, _ij) - ( 𝒦(^*_ij, _ij) - 𝒦(_ij, _ij))  ).
            
            
            The proof of the following lemma follows the lines of the proof of Lemma <ref>, and we do not present it.
            
            
             There exists a constant C>0 depending only on C_inf such that for any ∈𝒮 simultaneously we have 
            
                |∑_(i,j) ∉Ω (𝒦(^*_ij, _ij)- 𝒦(_ij, _ij) - ( 𝒦(^*_ij, _ij) - 𝒦(_ij, _ij))  )|≤1/32ρ_n∑_(i,j) ∉Ω(_ij - _ij)^2+ϵ_n
            
             with probability at least 1-5exp(-Cρ_n(nlog(k) + k^2 )).
             
             
             This implies that on the event , with large probability, 
            
                ∑_(i,j) ∉Ω(_ij - ^*_ij)^2    ≤    8ρ_n𝒦(^*, )+ 1/4∑_(i,j) ∉Ω(_ij - _ij)^2+ 8ϵ_nρ_n
                   ≤     8ρ_n𝒦(^*, )+ 1/2∑_(i,j) ∉Ω(_ij - ^*_ij)^2 + 1/2∑_(i,j) ∉Ω(^*_ij - _ij)^2 +8ϵ_nρ_n
                1/2∑_(i,j) ∉Ω(_ij - ^*_ij)^2    ≤   ( 8 ρ_n + 4 ρ_n)𝒦(^*, ) + 8 ϵ_nρ_n.
            
            Using (<ref>) and (<ref>), we have shown that for n≥ N and some constants C, C'>0 depending only on C_inf, with probability at least 1-5exp(-Cρ_n(nlog(k) + k^2 )) - 2exp(-Cnρ_n),
            
            
                ‖ - ^* ‖_2^2 ≤  C(ρ_n^2n + ρ_n𝒦(^*, )+ ρ_nϵ_n).
            
            
            We conclude the proof of Theorem <ref> by noticing that nρ_n^2 ≤ρ_nϵ_n and using that ρ_n = Clog(n)^1/5ρ_n.
            
            
            
            
             §.§ Proof of Proposition <ref>
            
            
            By definition, 
            
                (^*, ^bc)    =   ∑_i<j(^*_ijlog(^*_ij/^bc_ij) + (1 - ^*_ij)log(1 - ^*_ij/1 - ^bc_ij))
                   ≤   ∑_i<j(^*_ij^*_ij - ^bc_ij/^bc_ij + (1 - ^*_ij)^bc_ij - ^*_ij/1 - ^bc_ij)
                   =   ∑_i<j(^bc_ij - ^*_ij)^2/(1 - ^bc_ij)^bc_ij
            
            where the second line follows from the fact that for any x > 0, log(x) ≤ x-1. Since for any 1 ≤ i < j ≤ n,  ^bc_ij and ^*_ij belong to [C_infρ_n, ρ_n], this yields
            
                (^*, ^bc)    ≤   ∑_i<j(^bc_ij - ^*_ij)^2/(1 - ρ_n)C_infρ_n.
            
            Now, recall that ^*_ij = ρ_n W (ζ_i, ζ_j) and define z^*: [n] → [k] by z^*(i) = 1≤ a ≤ k∑ a 1{ζ_i ∈[a-1/k, a/k) } for any i ∈ [n]. Moreover, define ^bc_ij = ρ_n W (z^*(i)/k, z^*(j)/k). Note that by definition of z^*, for any i, |ζ_i - z^*(i)/k|≤1/k. Thus
            
                (^*, ^bc)    ≤   ρ_n/C_inf(1-ρ_n)∑_i<j( W(ζ_i, ζ_j ) - W (z^*(i)/k, z^*(j)/k) )^2
                   ≤   4ρ_nM^2/C_inf(1-ρ_n)∑_i<j(1/k)^2(α 1)
            
            where the last equation follows from (<ref>).
            
             
            
            
             §.§ Technical lemmas
            
             For any , ' ∈ℝ^n× n and ∈ [0,1]^n× n_sym, 
             
                ‖-'‖^2_2,≤ 8 (‖‖_∞∨‖'‖_∞ ) 𝒦_(, ').
            
             By definition of Bernoulli Kullback-Leibler divergence for any 0<q,q'<1 we have that
             
                (q,q')   =qlog (q/q' )+(1-q)log (1-q/1-q' )≥ (√(q)-√(q') )^2+ (√(1-q)-√(1-q') )^2
                   ≥1/2 [ (√(q)-√( q') )- (√(1-q)-√(1-q') ) ]^2.
            
             Using Taylor's Theorem for some η between q and q' we get
              
                (q,q')   ≥1/2 [1/2√(η) (q-q' )+1/2√(1-η) (q-q' ) ]^2=  (q-q' )^2/8 [1/√(η)+1/√(1-η) ]^2
                   =  (q-q' )^2/8 [1/η+1/1-η ]=  (q-q' )^2/81/η(1-η)≥(q-q')^2/8(q∨  q').
            
               Now Lemma <ref> follows from  (<ref>) and 
               
                𝒦_(, ')=∑_i<j_ij (_ij, _ij').
            
             Let ^s and n_s be defined as in (<ref>), and assume that γ_n ≤1/2, then
             
                𝒦_(^*, ^s) - 𝒦_(^*, ) ≤ 2γ_n n_s.
            
                𝒦_(^*, ^s) - 𝒦_(^*_ij, _ij)    =   i<j∑_ij(  ^*_ijlog(_ij/^s_ij) + (1-^*_ij) log(1-_ij/1-^s_ij)) 
                   =   i<j∑_ij1{_ij < γ_n }( ^*_ijlog(_ij/γ_n) + (1-^*_ij) log(1-_ij/1-γ_n))
                   ≤   i<j∑_ij1{_ij < γ_n } (1-^*_ij) log(1 + γ_n-_ij/1-γ_n)
                   ≤   i<j∑_ij1{_ij < γ_n }γ_n-_ij/1-γ_n≤i<j∑_ij1{_ij < γ_n } 2γ_n ≤ 2n_sγ_n.
            
            
             §.§ Proof of Proposition <ref>
            
            
            In the case of fully observed network, we alleviate notations and write 
            
                (;z,)    =   i ≠ j∑_ijlog(_z(i), z(j)) + (1-_ij)log(1 -_z(i), z(j)) ,
                𝔩(; α, )    =   z ∈𝒵_n,k∑(i∏α_z(i))exp(( ;z,)),
                and 𝒥(; τ, α, )    =   log(𝔩(; α, )) - KL (ℙ_τ(·) ||ℙ(·|, α, ) ).
            
            
            For any z ∈𝒵_n,k and (α, ) ∈𝒬, we denote
            
                𝔩'(, z ; α, ) = (i ≤ n∏α_z(i))exp((;z,) )
             the likelihood of the parameters (α, ) and the label function z. Then, the likelihood of the stochastic block model with parameters (α, ) is given by 𝔩(; α, ) = z ∈𝒵_n,k∑𝔩'(, z ; α, ).  Note that the likelihood functions 𝔩(; α, ) and 𝔩'(, z ; α, ) provide lower and upper bounds on the variational objective function 𝒥(; τ, α, ) : for any parameter (α, ) and any label function z ∈_n,k,
            
                𝔩'(, z ; α, ) ≤sup_τ∈exp(𝒥(; τ, α, )) ≤𝔩(; α, ).
            
            
            
            To prove Proposition <ref>, we first show that ℙ(·|,  α^Var, ^Var), i.e. the posterior distribution of z at the variational estimator (α^Var, ^Var), concentrates around δ_z', the dirac distribution at the label function 
            z' = _z : z∼ z^*𝔩'(, z; α^VAR,  ^VAR) :
            
            
                ℙ(z' |, α^Var, ^Var) = 1 - o_p(1).
            
            Then, we show that it implies the concentration of the estimator z^Var :
            
                ℙ(z^Var = z' |) = 1 - o_p(1).
            
            Together (<ref>) and (<ref>) imply ℙ(z^Var∼ z^* |) = 1 - o_p(1). Since the random variable ℙ(z^Var∼ z^* |) is bounded, Equation (<ref>) also implies that it converges to 1 in expectation. Finally, we show that with probability going to one, the maximum likelihood estimator of the label function is equal to the true label function (up to permutation):
            
                ℙ(z∼ z^*) = 1 - o_p(1)
            
            which concludes the proof of Proposition  <ref>.
            
            Proof of Equation (<ref>) The proof of Equation (<ref>) relies on results proven in <cit.>, which we recall for the sake of completeness. For any two parameters (α, ) and  (α', ') in 𝒬, we say that (α', ') ∈𝒮_α, if there exists a permutation σ of {1, ..., k} such that for any (a,b) ∈{1, ..., k}^2, '_σ(a), σ(b) = _a,b and α'_σ(a) = α_a.
            
            
            Let (z^*, A) be generated from a stochastic block model with parameters (α^*,^*) ∈𝒬 such that ^0 has no identical columns and ρ_n ≫log(n)/n. Then, for any (α, ) ∈𝒬,
            
                𝔩(; α, )/𝔩(; α^*, ^*) = (α', ') ∈𝒮_α, max𝔩'(, z^* ; α', ')/𝔩'(, z^* ; α^*, ^*)(1 + ϵ_n((α', '), k)) +ϵ_n((α', '), k)
            
            where sup_(α, ) ∈ϵ_n((α, ), k) = o_p(1).
            
            Let (z^*, A) be generated from a stochastic block model with parameters (α^*,^*) ∈𝒬 such that ^0 has no identical columns and ρ_n ≫log(n)/n. Then,
            
                𝔩'(, z^*; α^*, ^*)/𝔩(; α^*, ^*) = 1 + o_p(1).
             Recall that z' = _z : z∼ z^*𝔩'(, z^*; α^VAR,  ^VAR). By definition of 𝔩 and 𝔩', 
            
                z ≠ z'∑𝔩'(, z; α^VAR, ^VAR)   =   𝔩(; α^VAR, ^VAR) -  𝔩'(, z'; α^VAR, ^VAR).
            
            Thus
            
                z ≠ z'∑𝔩'(, z; α^VAR, ^VAR)/𝔩'(, z^*; α^*, ^*)   =   𝔩(; α^*, ^*)/𝔩'(, z^*; α^*, ^*)×𝔩(; α^VAR, ^VAR)/𝔩(; α^*, ^*) -  𝔩'(, z'; α^VAR, ^VAR)/𝔩'(, z^*; α^*, ^*).
            
            Using Lemma <ref>, we have that 
            
                𝔩(; α^*, ^*)/𝔩'(, z^*; α^*, ^*) = 1 + o_p(1).
            
            Moreover, we note that 
            
                max_(α', ') ∈𝒮_α^VAR,^VAR𝔩'(, z^* ; α', ')     =    max_z ∼ z^*𝔩'(, z ; α^VAR,^VAR) 
                    =    𝔩'(, z' ; α^VAR,^VAR)
            
            by the definition of z'. Then, applying Theorem <ref>, we get that 
            
                𝔩(; α^VAR, ^VAR)/𝔩(; α^*, ^*) = 𝔩'(, z' ; α^VAR, ^VAR)/𝔩'(, z^* ; α^*, ^*)(1 + o_p(1)) + o_p(1).
            
            Combining Equations (<ref>), (<ref>) and (<ref>), we obtain that 
            
                z ≠ z'∑𝔩'(, z; α^VAR, ^VAR)/𝔩'(, z^*; α^*, ^*)   =   𝔩'(, z' ; α^VAR, ^VAR)/𝔩'(, z^* ; α^*, ^*) o_p(1) + o_p(1).
            
            Thus, 
            
                z ≠ z'∑𝔩'(, z; α^VAR, ^VAR) = max{𝔩'(, z^*; α^*, ^*), 𝔩'(, z' ; α^VAR, ^VAR)} o_p(1).
            
            On the one hand, using Equation (<ref>) and the definition of (τ^VAR, α^VAR, ^VAR), we find that 
            
                𝔩'(, z^* ; α^*, ^*)   ≤   sup_τ∈exp(𝒥(;τ,  α^*, ^*))
                   ≤   exp(𝒥(; τ^VAR, α^VAR, ^VAR)) 
                   ≤   𝔩(;  α^VAR, ^VAR).
            
            Also, by the definition of 𝔩 and 𝔩', we have that 𝔩'(, z' ; α^VAR, ^VAR)≤𝔩(;  α^VAR, ^VAR). Thus, Equation (<ref>) implies
            
                z ≠ z'∑𝔩'(, z; α^VAR, ^VAR) =  𝔩(;  α^VAR, ^VAR)o_p(1).
            
            Now, we can conclude the proof of Equation (<ref>) by noticing that
            
                ℙ(z' |, α^Var, ^Var)    =   𝔩'(, z'; α^VAR, ^VAR)/𝔩(; α^VAR, ^VAR)
                   =     1 - z ≠ z'∑𝔩'(, z; α^VAR, ^VAR)/𝔩(; α^VAR, ^VAR)
            
            and using Equation (<ref>).
            
            Proof of Equation (<ref>)
            By the definition of 𝒥(; τ, α, ), we have that
            
                KL(ℙ_τ^VAR(·)||ℙ(·|, α^VAR, ^VAR) ) = log(𝔩(; α^VAR, ^VAR) )- 𝒥(; τ^VAR, α^VAR, ^VAR).
            
            Equation (<ref>) implies that 𝒥(; τ^VAR, α^VAR, ^VAR) ≥log(𝔩(, z' ; α^VAR, ^VAR)), so
            
                KL(ℙ_τ^VAR(·)||ℙ(·|, α^VAR, ^VAR) ) ≤log(𝔩(; α^VAR, ^VAR) ) - log(𝔩(, z' ; α^VAR, ^VAR)).
            
            Note that Equation (<ref>) implies
            
                log(𝔩(; α^VAR, ^VAR) ) - log(𝔩(, z' ; α^VAR, ^VAR)) = o_p(1).
            
            Now, using Pinsker's inequality, we see that 
            
                |ℙ_τ^VAR(z') - ℙ(z' |, α^VAR, ^VAR) | = o_p(1).
            
            We use Equation (<ref>) and the definition of z^(VAR) to conclude the proof of Equation (<ref>).
            
            Proof of Equation (<ref>)
            
            Equation (<ref>) is proven in <cit.>. In this work, the authors define the profile likelihood modularity 𝒬_LM(A,z) of a label function z ∈_n,k as
            
                𝒬_LM(A,z) = 1/2a,b∑n_ab(_ab/n_ablog(_ab/n_ab) + (1 - _ab/n_ab)log(1-_ab/n_ab)).
            
            for _ab = i ∈ z^-1(a), j ∈ z^-1(b)∑_ij and 
                n_ab  = {[        | z^-1(a)|×| z^-1(b)|                        a ≠ b; | z^-1(a)|×(| z^-1(a)| - 1 )                              ].
             For ẑ^LM = _z∈_n,k𝒬_LM(A,z), the authors of <cit.> prove that under the assumptions of Proposition <ref>, with probability going to 1, ẑ^LM∼ z^*. Since maximizing 𝒬(A,z) is equivalent to maximizing max_ℒ(; , z), this implies that z∼ z^* with probability going to 1.
            
            
            
             §.§ Proof of Proposition <ref>
            
            
            To prove Proposition <ref>, we show that the maximum likelihood estimator studied in Proposition <ref> is equal to the restricted maximum estimator studied in Corollary <ref>. Proposition <ref> then follows from Corollary <ref>. 
            
            Define c_min = min_a,b^0_a,b and c_max = max_a,b^0_a,b. Corollary <ref> implies that for some absolute constant C>0, 
            
                ℙ(‖^* - ^r‖_2^2 ≤  C(c_max/c_min)^2ρ_n(k^2 + nlog(k)) ) → 1,
            
            where the restricted maximum likelihood estimator ^r is defined as
            
                ^r_i<j = ^r_z^r(i) z^r(j), ^r_ii=0
                   (^r,z^r) ∈∈ [c_minρ_n /2, 2c_maxρ_n]^k× k_ sym, z∈_n,k∑_i≠ j(_ij,_z(i)z(j)).
            
            One the other hand, Proposition <ref> implies that with probability going to one, the variational estimator of the probabilities of connections ^VAR is equal to the maximum likelihood estimator  given by 
            
                _i<j = _z(i) z(j), _ii=0
                 for    (, z) ∈∈, z∈_n,k∑_i≠ j(_ij,_z(i)z(j)).
            
            Thus, it is enough to show that = ^r with large probability to prove Proposition <ref>. To do so, we show that with large probability, (z) ∈ [c_minρ_n/2, 2c_maxρ_n]^k× k]. We define
            
                n_ab(z)  = {[        | z^-1(a)|×| z^-1(b)|                        a ≠ b; | z^-1(a)|×(| z^-1(a)| - 1 )                              ].
            
            for z ∈_n,k, and (z) = ((z)_ab) such that (z)_ab = (i ∈ z^-1(a), j ∈ z^-1(b)∑_ij)/n_ab(z). With these notations, we note that = (z).
            
            Recall that |(z^*) ^-1(a)| is a sum of n independent Bernoulli random variables with mean α^0_a. Using Bernstein's inequality <ref>, we find that for any a, 
            
                ℙ(nα^0_a - |(z^*) ^-1(a)|≥ 0.5n α^0_a) ≤ 2e^-nα^0_a/16.
            
            Thus, 
            
                ℙ(min_a|(z^*) ^-1(a)|≤ 0.5n min_aα^0_a) ≤ 2ke^-nmin_aα^0_a/16.
            
            Therefore, the event Ω = {min_a,b n_a,b(z^*) ≥ n^2 min_a (α^0_a)^2/5 } holds with probability going to 1. 
            
            Now, we show that on the event Ω, with large probability, (z^*) ∈ [c_minρ_n /2, 2c_maxρ_n]^k× k. Recall that for any a,b, conditionally on z^*, n_ab(z^*)(z^*)_ab is a sum of n_ab(z^*) independent Bernoulli random variables with mean ρ_n ^0_ab. Then, Bernstein's inequality <ref> implies that for any t>0
                ℙ(| n_ab(z^*)(z^*)_ab  - n_ab(z^*)ρ_n^0_ab|≥√(2tn_ab(z^*)ρ_n^0_ab) + 2t/3) ≤ 2e^-t.
            
            Choosing t = n_ab(z^*)ρ_n^0_ab/16 yields
            
                ℙ(| n_ab(z^*)(z^*)_ab  - n_ab(z^*)ρ_n^0_ab|≥ 0.5n_ab(z^*)ρ_n^0_ab) ≤ 2e^-n_ab(z^*)ρ_n^0_ab/16.
            
            On the event Ω, this implies that 
            
                ℙ(| n_ab(z^*)(z^*)_ab  - n_ab(z^*)ρ_n^0_ab|≥ 0.5n_ab(z^*)ρ_n^0_ab) ≤ 2e^-n^2ρ_n^0_ab(min_aα_a^0)^2/80.
            
            A union bound yields
            
                ℙ((z^*) ∉ [c_minρ_n /2, 2c_maxρ_n]^k× k) ≤ 2k^2e^-n^2ρ_nmin_a,b^0_ab(min_aα_a^0)^2/80
            
            on the event Ω. Since ℙ(Ω) → 1 and n^2ρ_n → +∞, this shows that 
                ℙ((z^*) ∈ [c_minρ_n /2, 2c_maxρ_n]^k× k) → 1.
            
            Now, Equation (<ref>) shows that with probability going to 1, z∼ z^*. Thus, Q(z) ∈ [c_minρ_n /2, 2c_maxρ_n]^k× k with probability going to one, and the maximum likelihood estimator of the probabilities of connections between nodes coincides with the restricted maximum likelihood estimator. This concludes the proof of Proposition <ref>.
            
            
            apalike
