Optimality of variational inference for stochasticblock model with missing links
Authors: Solenne Gaucher
Olga Klopp
Venue: NeurIPS 2021 Poster (2021)
Keywords: Network models
link prediction
variational methods
maximum likelihood

Abstract: Variational methods are extremely popular in the analysis of network data. Statistical guarantees obtained for these methods typically provide asymptotic normality for the problem of estimation of global model parameters under the stochastic block model. In the present work, we consider the case of networks with missing links that is important in application and show that the variational approximation to the maximum likelihood estimator converges at the minimax rate. This provides the first minimax optimal and tractable estimator for the problem of parameter estimation for the stochastic block model with missing links. We complement our results with numerical studies of simulated and real networks, which confirm the advantages of this estimator over current methods.

Optimality of variational inference for stochastic block model with missing links
Solenne Gaucher
Département de Mathématiques d' d'Orsay, Université Paris-Saclay, Orsay, France solenne, gaucher@math wrpptahh..uuu..... u-psud.f7
Olga Klopp ESSEC Business School, Cergy, France CREST, ENSAE, Palaiseau, France kloppolga@math.
ctt.gaaammtac..nr....... c
Abstract
Variational methods are extremely popular in the analysis of network data. Statisti- cal guarantees obtained for these methods typically provide asymptotic normality for the problem of estimation of global model parameters under the stochastic block model. In the present work, we consider the case of networks with missing links that is important in application and show that the variational approximation the maximum likelihood estimator converges at the minimax rate. This provides the first minimax optimal and tractable estimator for the problem of parameter estimation for the stochastic block model with missing links. We complement our results with numerical studies of simulated and real networks, which confirm the advantages this estimator over current methods.
1
Introduction
The analysis of network data poses both computational and theoretical challenges. Most results obtained in the literature concentrate on the stochastic block model (SBM) which is known to be good proxy for more general models, such as the inhomogeneous random graph model, [35]. Recently, variational methods ([28, 49]) have attracted considerable attention as they offer computationally tractable algorithms often combined with theoretical guarantees. Theoretical results that one can find for such variational methods provide asymptotic normality rates for parameter estimates of stochastic block data. For example, consistency has been shown for profile likelihood maximization [8] and variational approximation the maximum likelihood estimator [13], [7]. These results have been extended to the case of dynamic stochastic block model [34] and sampled data [48]. These work focus parameter estimation,
in [44] and [53], who establish the minimax optimality of variational methods in a large class models (which does however not include the stochastic block model). Variational inference has also been successfully applied the problem of community detection, see, e.g., [3, 54, 26, 45). In particular, the authors of [54] show that an iterative Batch Coordinate Ascent Variational Inference algorithm designed for the two-parann coopparameters, assortative stochastic block model achieves statistical optimality for community detection problem. Note that this algorithm cannot be extended to the more general stochastic block model considered here.
In parallel with this line of work, the problem statistical estimation of model parameters, in particular, the question of minimax optimal convergence rates, has been actively studied in the statistical community. In the case of dense graphs, a pioneering paper [17] shows that, for the problem of estimating the matrix of connection probabilities, the least square estimator is minimax optimal and [18] provides optimal rate for Bayes estimation. For the more challenging case of
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

sparse graphs, the minimax optimal rates have been first obtained in [29] building on the restricted least square estimator. In [16], the authors consider the least square estimator in the setting when observations about the presence or absence of an edge are missing independently at random with the same probability p. Unfortunately, least square estimation is too computationally expensive to he used in practice. Many other approaches have been proposed, for example, spectral clustering [39, 22, 46), modularity maximization [42, 8]. belief propagation [14], neighbourhood smoothing [55], convex relaxation of k-means clustering [20] and of likelihood maximization [4], and universal singular value thresholding [11, 30, 51J. These approaches are computationally tractable but show sub-optimal statistical performances. So the question of possible computational gap when no polynomial time algorithm can achieve minimax optimal rate of convergence has been raised.
The present work goes in these two directions. We study the statistical properties of the mean field variational Bayes method and show that it achieves the optimal statistical accuracy. In particular, these results close the open question on the possible existence of a computational gap for the problem of global parameter estimation. We built our analysis on the approach developed in [13], [7] and [48]
using the closeness of maximum likelihood and maximum variational likelihood and on the results that show the minimax optimality of the maximum likelihood estimator [19].
In the present paper, we deal with settings where the network is not fully observed, a common problem when studying real life networks. In many applications the network has missing data as detecting interactions can require significant experimental effort, see, [32, 52, 24, 21]. For example, in biology graphs are used model interactions between proteins. Discovery of these interactions can be costly and cone-consuming [9]. On the other hand, the size of some networks from social media or genome sequeneing may be so large that only subsamples of the data are considered [6]. has been observed that incomplete observation of the network structure may considerably affect the accuracy of inference methods [31] and missing data must be taken into account while analyzing networks data. A popular approach consists in considering the edges with uncertain status non-existing. In the present paper, we use a different framework by considering such edges as missing and introducing separated data missing mechanism. A natural application of our method is link prediction [36, 56), the task of predicting whether two nodes in a network are connected. Our approach allows to deduce the pairs of nodes that are most likely to interact based the known interactions in the network. Behind inference of the networks structure, our algorithms can be used to predict the links that may appear in the future if we consider networks evolving over the time. For example, in a social network, two users that are not yet connected but are likely to be connected can be recommended as promising friends.
1.1 Contribution and outline
The paper is organized as follows. After summarizing notations, introduce our model and the maximum likelihood estimator for the stochastic block model with missing observations in Section 2. In Section 3, we introduce the mean field variational Bayes method and present a new estimator which combines the labels obtained using the variational method and the empirical mean for estimation of connection probabilities. In Section 3.2, we show that our estimator is minimax optimal for dense stochastic block models with missing observations as well as for sparse stochastic block models. Finally, in Section 4 we provide an extensive numerical study both on synthetic and real-life data which shows clear advantages of our estimator over current methods.
1.2 Notations
We provide here a summary of the notations used throughout the paper. For all d E N., we denote by [d] the set (1,...,.4 d). For 2: [k] -> [n] and all (a, b) E [d] x [d]. we abuse notations and denote I (a. b) {(t.j) =(1) = a. a()) = b, + j}. For any two label functions 2, we write 2 z' if there exists permutation o of {1,..., k) such that (z(o(a)))ast
(z(a))a<k- For any set S, we denote by [S] its cardinality. For any matrix A. we denote by A.j its entry on row and column j. If A E [0, 1|xx and A is symmetric, we write A E [0, 1|axn. We denote by A @ B the Hadamard product of two matrices A and B. The Frobenius norm of a matrix is denoted -AA12=VE.,
by |||||2 = VE., A.y. 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 (ax)neN) (bp) NeN- write on = (bb)) if a, bn,, + 00.
2

---

2 Maximum likelihood estimation in the stochastic block model with missing links
2.1 Network model and missing data scheme
In the simplest situation, a network can be represented as undirected, unweighted graph with ni nodes indexed from 1 to n. Then, the network can be encoded by its adjacency matrix A = (At)) The adjacency matrix is n n symmetric matrix such that for any < j. A.j 1 if there exists an edge between node i and node j. A. = 0 otherwise. We consider that there is no edge linking node to itself, so A = 0 for any A common approach in network data analysis is to assume that the observations are random variables drawn from a probability distribution over the space of adjacency matrices. More precisely, for < j the variables A.j are assumed to be independent Bernoulli random variables of parameter Or where O
iSi<iinn is n. X n symmetric matrix with zero diagonal entries. The matrix O corresponds to the matrix of probabilities of observing an edge between nodes and j. This model known as the inhomogeneous random graph model:
S <iiijsnn A., B ind. Bernoulli (ei,)
(1)
Our focus is on the problem of estimation of the generative matrix O" which determines the overall structure of the network. This question is of particular interest for the task of link prediction.
Many of real-life networks are characterized by block structure. Loosely speaking, the block structure means that the nodes of the network are partitioned into groups called blocks, and that the distribution of the connections between nodes depends on the blocks which the nodes belong. For example, when considering citation 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.
A very popular model that formalizes this idea is the stochastic block model (see, e.g., [27]). In this model, nodes are classified into & communities: each node is associated with a community 2" where 2"' [n|] + [K] is called the label function. This label function can either be treated as a parameter to estimate, or as a latent variable. In this last case, it assumed that the indexes follow a
vi, 2* (i) Lidd Multinomial [1; a²) where Va [ks) Oa is the probability that node i belongs to the community a. Given this label function, the probability that there exists an edge between nodes i and depends only on the communities of and j. Thus, the matrix of connection probabilities O* can be factorized as follows: O fj Q² (1)) with Q" a k x l symmetric matrix such that Qa is the probability that there exists an edge between given member of the community and given member of the community b. The conditional stochastic block model can be written as:
multinomial distribution:
EQ E [0, 1] 3z* [n]] + [R]]
(2)
LA MIiijSnn n,, A:yl (Q* =²) ind. Bernoulli (Q%-00=))): Au 0.
Assuming that the network follows the stochastic block model, the problem of estimating the matrix of connection probabilities reduces to estimating the label function 2" and the matrix of probabilities of connections between communities Q'. Note that the conditional stochastic block model is at best identifiable up to simultaneous permutation of the communities and of the rows and columns of the parameters Q"
The stochastic block model has attracted considerable interest from the learning community. An important line of work has focused on the problem of estimation of the latent variables 2", see, for example. [38, 10, 1, 41]. The best understood framework is the binary. balanced, symmetrie, assortative block model. In this simpler model, the two communities have the same size, the same probability of intra-con cntra-communiyy connection (Q), Qi p), and nodes are assumed to be more connected with nodes of the same community (p > q = Qi2). Much work has been done on the precise characterisation of the conditions on p. 9 that allow for strong recovery of 2", i.e. to estimate =" exactly with high probability. Closest to model (2) is perhaps the setting considered in [15]. In this work, the authors consider the related problem of community recovery in the binary block model [23],[2], and provide tight bounds on the recovery threshold for the balanced, two communities stochastic block model with missing observations. They propose computationally
3

---

efficient algorithm for estimating 2" in regime where strong recovery is possible; this, however, requires prior knowledge of the parameter Q'
Missing observations scheme Usually, when working with network data, not all the edges are observed. To account for this situation introduce X E {0, 1 Jyy the known sampling matrix where Xij = 1 if A;j is observed and Xij O otherwise. We assume that X is random and independent from the adjacency matrix A and its expectation @ For any S i < n. its entries ind. X; ij are mutually independent and X ij Bernoulli(p) for some sampling rate p 0 such that p w (log(n)/n) when n + 00.
2.2 Conditional maximum likelihood estimator
The log- log-iikeihood of the parameters (z, Q) with respect to the adjacency matrix A and the sampling matrix X is given by
Cx (A: Q) = E
X1
(As log (llo((:(()))))) + (1 -Ai) log(1 (=(0==0)))
1sicjsn
-oggi
Σ Aij + Σ
log(1 Qab)
Σ
x X1s(1 - Aij).
0.5h
(i,))s ((a,b)
asb
Let us denote by Zn, the set of all label functions : [n] + [k]]. For given label function 2 Zn,k. the log-likelihood is maximized by taking
Qub E(ijee-- Aiy
E(iyes 1(a Xij
It is interesting note that, for fixed label function 2, maximizing the likelihood or minimizing the least square criterion defined as Cx (A; =, Q) = Eiej Xúj (Ai (2(0)20)) yields the same estimator for the matrix Q. The main difference between these two methods is rooted in the label functions selected by the two criteria, see, e.g. [19].
To bound the risk of the maximum likelihood estimator, it is usual to assume that there exists sequences Pn and 7h such that Vi < j.
0 T/2 O Pa <.
This ussumption ensures that the loss associated to the maximum likelihood estimator is Lipschitz continuous. See, for example, [7] and [50], where the authors assume that the adjacency matrix is generated by an homogeneous stochastic block model for which the matrix Q" / /Pn has entries bounded away from O.
The restricted maximum likelihood estimator, θ, is based on the maximization of the likelihood among block constant matrices with entries in ['m, Pn]:
Kij 2Z(EE)) @
(2,)E
arg max TEck QElTa ,,,
(A;2,2
(4)
In (4), Yhe and P. are assumed to be known (see [19] for a discussion on how to estimate these parameters). Note that the Expectation Expeetation-Maximizaitii Maximization algorithm used in practice to obtain the variational approximation to the maximum likelihood estimator does not require the knowledge of these parameters. We also assume that k is known and that it can depend the number of nodes n; can be chosen using a network cross-val validation method [12], a sequential goodness-of-fi testing procedure [33] likelihood-baste
model selection method [50]. The following result provides the upper bound on the estimation risk of the maximum likelihood estimator:
Theorem (Corollary 2 in [19].. Assume that A drawn according to the conditional stochastic block model and Pr. w(n ). Then, there exists absolute constants C,, C² > O such that, with probability at least 9 cxp (-Cpm (I?2 + n log()))))
Pn. (k² + nlog(k))
| - 013 3113+ < C"
(5)
Pn- (L-PP)PA3))

---

of the When all network entries are observed, we have p 1. Note that this results implies that, when Pn = (7,,, the maximum likelihood estimator is minimax optimal (see, [29, 16] for statement of the lower bound).
3 Variational approximation to the maximum likelihood estimator
3.1 Definition of the estimator
The optimization of the log- lileiiiiioood function Lx requires search over the set of km labels. As consequence, the maximum likelihood estimator defined in (4) is computationally intractable. Celisse al. [13] and Bickel et [7] are the first to study variational approximation to this estimator. More recently, the authors of [48] used variational methods to approximate the maximum likelihood estimator in networks with missing observations. We start by formally introducing the variational approximation to the maximum likelihood estimator. We consider stochastic block model with random labels with parameters (ax, Q). For this model, the likelihood of the observed adjacency matrix A and sampling matrix X is given by
(A; Q)
Σ 2EZ
No iSn
exp (A; Q)).
Note that the maximization of Ix still requires to evaluate the expectation of the label function for given parameters (ax, Q) by summing over k-" possible labels. To circumvent this problem, one can use the mean-field approximation, which amounts to approximating the posterior distribution P (- C A, a, Q) by a product distribution. To ensure that this product distribution remains close to the posterior distribution, the objective function is penalized by the Dallback-Leible divergence of the two distributions. More precisely, the posterior distribution IP (-|X @ A, a; Q) is approximated by multinomial distribution denoted P,, such that P+(=) ligign m(2/r"), where m(-17") is the density of the multinomial distribution with parameter T = (Fis.., T and T = (T) .r.,....77 "".,""). Then, the variational estimator is defined as
(QVAR Q VAR
AV)
arg max GEA.QEQ.ET
[x(A;T,0,0) Q)
(6)
for Jx(A:T, Q)
log (1x aA Q)) - KL (P-()) O a,a,
where A, Q and T are the respective parameter spaces for the parameters a, Q and r, KL denotes divergence between two distributions, and X A denotes the observed
the Kullback-eeibe entries of A. Since for any parameter (a, Q), KL (P--() [P (- O (,a,Q) 2 0, we see that exp (Jx (A; a, Q)) provides a lower bound on 1x (A;
The expectation maximization (EM) algorithm derived in [48] can be used to iteratively compute the variational estimator. For details, see Appendix C. Since this algorithm is not guaranteed to converge to global maximum, it should be initialized with care, by using, for example, a first clustering step. This solution is implemented in the package miss missSBM.
Statistical guarantees for the variational estimator obtained in [13, 7,3 establish that maximizing max,eT Jx(A; a, Q) is equivalent to maximizing (x (A; a, Q), and that the estimator obtained by maximizing Ix (A; a, Q) converges to the true parameters (a*.Q") Q*). This turn implics that (&VAR Q VAR also converges to "Q"). Note that these results do not provide guarantees on the recovery of the true labels =" the matrix of connection probabilities O In order estimate O¹, we first define the label estimator AV using the minimizer of the objective function (6):
Vign, n, VV AR e arg max (+VAR)
ask
Once we have estimated the community labels using (7), we replace the estimator Q" VAR matrix of connection probabilities by the empirical mean estimator:
Va < k and b < k. k
-AR
EGSEERVARy-CC.) X Aij
E(LDE(EVAAD--OO.) X
5

---

and define C VAR
VAR ML-VAR as + i#j
VAR (3VAR(),SVAR())
=0.
(8) is
We will show respectively in Theorems 2 and that this new estimator (EVAR Q minimax optimal for dense networks with missing observations as well as for sparse networks. The simulation study provided in Section 4 reveals that this estimator also has good performances in practice.
ML- VAR
3.2 Convergence rates of variational approximation to the maximum likelihood estimator In this section, we show the asymptotic equivalence of AVR and 2, where
Q 2) E arg max QEQ,aEZ.,k
Σx (A 2Q Q)
the maximum likelihood estimator. More precisely, we show that, with large probability, there exists a permutation a of {1,...,kt k) such that (ZVAR(((a)) ask = (3(a)) and (Qo(a).o())
a.bck
(Qu.)) a.bkk When this hold, the error of the tractable estimator (SVAR, Q ARR minimax optimal error rate. These results are established under the following assumptions:
ML-VARY
matches the
A.1 There exists > and compact interval Co (0, 1) such that C [c, -cc and Q c Ckx
A.2 The true parameters a* and Q" lie respectively in the interior of A and @;
A.3 The coordinates of a a²Q" are pairwise distinct.
Note that Assumption A.2 and A.3 are standard. Assumption A.2 requires that the true parameters lie in the interior of the parameter space, which classical in parametric estimation. In the most simple case, the parameters a and Q" lie respectively in the interior of sets A and Q of the form A [c, 1 c Q [c', c' syym. for some c, E (0, 1/2). Assumption A.3 ensures the identifiability of stochastic block model parameters. Then, under the assumption that p (n/ log(n)): strong recovery of the labels is possible. Assumption A. is more restrictive, it implies that the network dense. This assumption will be relaxed in Theorem 3, where we consider sparse stochastic block models such that Q" Pn Q" for some fixed Q" and some decreasing, sparsity inducing sequence Pr-
C VARR
The following Theorem shows the minimax optimality of the tractable estimator assumptions A. A.3.
under
Theorem 2. Assume that A is generated from a stochastic block model with parameters (a" Q")
satisfying assumptions A.I A.3. Then, (3V AR ~ 2) + when n - oc. Moreover there exists constant Co- >> depending on Q" such that
P 1110--0
6 VAR Co (k22 + n log(()))
<
1.
p
Let discuss the extension of Theorem 2 to the case of sparse networks. To avoid techni- calities, we will consider the case when the network is fully observed. We will also assume that the proportions of different communities are held constant, while the probabilities of connections between communities may decreases at rate Pn. That is, the parameters (a* Q") verify the following assumptions:
A.4 a* = a for some fixed a such that a > 0 for any a E (1....,k)
A.5 Q" pn Q" for some fixed Q" (0, kx such that 0 aaaaQu =1
a,b=l
Assumption A.5 relaxes Assumption A. and allows consider sparse networks. The normalization constraint Eisabsk of Q0 ab 1 ensure the identifiability of the parameters (Q", P.)) (see (7]). In the following, denote by Q the set of parameters (a, Q) verifying Assumptions A.4 and A.5.

---

The following theorem provides the analogous of Theorem 2 in the case of fully observed sparse networks. It is obtained by combining Propositions 2 and [19]:
Theorem 3. Assume that A is fully observed, and is generated from a stochastic block model with parameters (a", ;Q²) satisfying Assumptions A.4 and A.5, such that Q has identical columns and the sparsity inducing sequence Pn satisfies Pn > log(n)/n. /n. Then, IP (ZV Σ) 1 when + 00. Moreover, there exists a constant Cqp > depending on Q" such that
IP -10-- VAR
S Cn (k² nlog(()))
1.
(10)
Theorems 2 and establish that the variational estimator θ VAR estimation of dense networks with observations missing uniformly random, and sparse networks. For proofs and discussion see Appendix A.
is minimax optimal for both the
4 Numerical Results
4.1 Synthetic data
In this section we provide a simulation study of the performances the maximum likelihood estimator defined in (8), and compare it to the variational estimator defined in [48] and implemented in the package mi seSBM, as well as to the Universal Singular Value Thresholding estimator introduced in [25] and implemented in the package soft Imfutee The results are reported in Figure Thorough descriptions of the simulation protocols are provided in the Appendix.
Dense stochastic block model First, we evaluate the empirical performances of the variational approximation of the maximum likelihood estimator defined in (8) on dense stochastic block models. We estimate the matrix of probabilities of connections, and we compare our estimator with the estimator given by the methods missSBM and softImpute. The quality of the inference is assessed by computing the squared Frobenius distance between the estimators and the true matrix of connection probabilities O
We consider three types of three-communities stochastic block model. The first model, given by (qassort, Qussort.), provides a simple assortative network, where individuals are more connected with people from their communities than with other individuals. On the contrary, the second model, given by (a dasisssorr. Q dissssorrt.) :), is disassortative: individuals are more connected with individuals from outside of their communities. Both the assortative and disassortative models have balanced communities. The third model considered, given by (a méx. Qmie.) ), exhibits neither assortativity nor disassortativity. and the communities are unbalanced. We introduce missing data by observing each entry of the adjacency matrix independently with probability 0.5.
The variational approximation to the maximum likelihood estimator defined in (8) outperforms the softImpute method across all models and all number of nodes. Its error is equivalent that of the oracle estimator with hindsight knowledge of the true label function =" when the network is few hundred nodes large. Interestingly, our estimator also outperforms the variational estimator implement in the package missSBM. We underline however that the primary focus of the missSBM method is to infer the parameters (a* Q*).
Additional experiments illustrating the strong consistency of the variational estimator canbe found in Appendix B.2.
Sparse stochastic block model Next, we investigate the behaviour of our estimator on increasingly sparse networks. We consider a three-communities assortative stochastic block model of 500 nodes with balanced communities, and 50% missing values. The probabilities of connections are given by Q' pQ" where p is parameter controlling the sparsity, which ranges from 0.05 to 1. We compare the performance of the variational approximation to the maximum likelihood estimator to that of the methods softImpute and MissSBM. We also compare these estimators to the trivial estimator with all entries equal to the average degree divided by the number of nodes. The error measured as the squared Frobenius distance between the estimator and the matrix O" divided by p².
7

---

0.08
0.08
0.08
Error
Error
0.04
Error
0.04
0.00
0.00
0.00
200
1000
Number of nodes
Number
Number nodes
(a) Assortative SBM.
Disassortative SBM.
(c) Mixed SBM.
04
0.08
03
Softimpute
Eror
Oracle
0.44
MissSBM
01
Variational Estimator
0.00
Trivial
60
-.00
0.10
1.30
Samsling
Sparsity
(d) Robustness against sparsity.
(c) Rohustness against missing observations.
Figure I: Top: Error of connection probabilities estimation as function of the number of nodes (top left assortative SBM with balanced communities; top middle disassortative SBM with balanced communities; top right: mixed SBM with unbalanced communities) or of the sparsity parameter (bottom left) and of the sampling rate p (bottom right). We compare the variational approximation to the maximum likelihood estimator (in blue) to that of missSBM (in red), that of sof Impute (in green), that of the oracle estimator with knowledge of the label (in black), and that of the trivial estimator with entries equal to the empirical average degree divided by the number of nodes (orange, bottom only). The full lines indicate the median respectively of the mean squared error (top and bottom right) and of the mean squared error divided by the sparsity parameter (bottom left) of the estimators over 100 repetitions, while the dashed lines indicate 25% and 75% quantiles.
As the network sparsity increases, the clustering of the nodes becomes more difficult. The normalized
error of the estimator e -VAR increases up to a threshold corresponding to the normalized error of the trivial estimator with all entries equal to the empirical degree, divided by the number of nodes. Note that when considering very sparse networks, with < log(n) estimator with entries equal to the empirical mean degree is minimax optimal (see, eg, [29])). Thus, the estimator enjoys relatively low error rates in both high and low signal regime. By contrast, the normalized error of the softImpute method diverges as the network becomes increasingly sparse.
/n. (n))n./)
is known that the trivial
Stochastic block model with missing observations To conclude simulation study, evaluate the robustness of the methods against missing observations. We consider a three-communities assortative stochastic block model with balanced communities and 500 nodes. We increase the proportion of missing observations, and we compare the performance of the variational approximation to the maximum likelihood estimator that of the methods softlmpute and missSBM. The error is measured as the squared Frobenius distance between the estimator and the matrix O*.
As the sampling rate decreases, the clustering becomes impossible and the rate of the estimator θ VARR
increases up to that of the trivial estimator obtained by averaging the observed entries of the

---

adjacency matrix. By contrast, the methods softlmpute and missSBM lack robustness against missing observations, and their error diverges as the number of missing observations increases.
4.2 Analysis of real networks
4.2.1 Prediction of interactions within a elementary school
We apply our algorithm analyze a network of interactions within French elementary school collected by the authors of [47]. The network records durations of physical interactions occurring within a primary school between 222 children divided into 10 classes and their 10 teachers over the course of two consecutive days; this dataset was collected using a system of sensors worn by the participants. We consider that an interaction has occurred if the corresponding duration is greater than one minute. If an interaction of less than one minute is observed, we consider that this observation may be erroneous, and treat the corresponding data as missing. By doing so, we remove respectively 11 and 13% of the observations on Day and Day2 2.
The graphs of interactions recorded during Day and Day 2 can be considered as two outcomes of the same random network model characterized by the matrix of connection probabilities O In this spirit, we use the observations collected on Day estimate the matrix O", and evaluate those estimators on the network of interactions corresponding to Day? 2. We note that the network of interactions for Day 1 has rather homogeneous degrees (the maximum degree is 41 and the minimum degree is 5, while the mean degree is 20). Moreover, it exhibits strong community structure. Therefore, we expect the networks of interactions be well approximated by a stochastic block model.
We compare the performance in terms of link prediction of the estimator @VAR defined in (8) to that of the method missSBM, and that of the method softlmpute In this last method, we set the penalty to 0, and we choose the rank of the estimator to be equal to the number of communities, which is estimated according to the Integrated Likelihood Criterion. We also compare these methods to the
naide
naice
naive persistent estimator θ
given by θ Aj = 1 if an interaction between and j has been 1;
d/n if the information is missing, where d is the average degree of the graph for Day 1. Table present the error of the different estimators, measured as the squared Frobenius distance between the adjacency matrix of Day 2 and its predicted value, divided by the squared Frobenius norm of the adjacency matrix of Day 2 (i.e, the error of the trivial null estimator).
recorded on Day 1, naive
=0
0 if no such interaction has been recorded, and θ naice
VAR
SB
SVT
naive
Estimator
X O (A θ) / C
A 12
0.312
0.317
0.357
0.541
Table 1: Link prediction error on the network of interactions within a primary school.
The variational method predicts most accurately the interactions on Day 2. It is closely followed by the estimator provided by the package missSBM. By contrast to the simulation study, the reduction in respectively 1.4% and 12.4%
error when using the new estimator is moderate: the error of V VAR
smaller than that of θ MissSBM and @ softtmppte In addition, the precision-reeall curve presented in the Appendix indicates that no estimator is better across all sensitivity levels. Interestingly, the naive estimator obtains a high error, which suggests a certain versatility in the children's behaviour.
4.2.2 Network of co-authorship
Finally, we use variational approximation to predict unobserved links in network of co-authorship between scientists working on network analysis, first analysed in [43]. We discard the smallest connected components (with less than 5 nodes), and we obtain network of 892 nodes. By contrast to the network of interaction in an elementary school, the network of co-authorship is quite sparse, and presents heterogeneous degrees: the average number of collaborators is 5, while the maximum and minimum number of collaborators are respectively 37 and 1.
In order to obtain unbiased estimates of the error of the estimators θ VAR we introduce 50% of missing values in the dataset. We train the three estimators on the observed
softImpute, and MiM

---

entries of the adjacency matrix, and we use the unobserved entries to evaluate their imputation error. Table 2 present the mean imputation error of the different estimators over 100 random samplings. measured in term of squared Frobenius error and normalized by the squared Frobenius norm of the adjacency matrix of the remaining entries (i.e, the error of the null estimator). Here again, the
VAR
missSRM
SVT
Estimator
[1 X) (A- 1 [[
X) c A
0.857
0.869
0.894
Table 2: Imputation error of the estimators the network of co-authorship.
variational approximation to the maximum likelihood estimator obtains the best performance. The precision-recal curves of these methods, included in the Appendix, indicates that this new estimator preferable across almost all sensitivity levels. We underline however that the errors term of Frobenius norm of the three estimators close, and relatively high. This comes surprise, as the high sparsity of the network causes the link prediction problem to be difficult.
5 Conclusion
In this work, we have introduced of the maximum likelihood estimator. We show that it enjoys the same convergence rates as the maximum likelihood estimator, and that is therefore minimax optimal. Our simulation studies reveal the advantages of our estimator over current methods. In particular, they highlight its robustness against network sparsity and missing observations. Our results pave the way for analysing variational approximations of more general structured network models such as the latent block model.
tractable estimator based variational approximation
Broader Impact
This paper proposes
method for network analysis which is theoretically optimal, and has empirical advantages compared to current algorithms. It can useful to researchers and practitioners with applications, e.g., in biology [40], ethnology [48] and ecology [5]. We acknowledge that improvements in network analysis and link prediction can have negative downstream societal impacts such contributing to community-basee polarization of opinion, improving online surveillance.
Acknowledgments
We thank the anonymous referees for their helpfull comments.
References
[1] E. Abbe and C. Sandon. Community detection general stochastic block models: Funda- mental limits and efficient algorithms for recovery. In 2015 IEEE 56th Annual Symposium Foundations Computer Science, pages 670 688, 2015.
[2] Emmanuel Abbe, Afonso Bandcira, Annina Bracher, and Amit Singer. Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery. IEEE Transactions on Network Science and Engineering, 1(1):10-22, 2014.
[3] Edoardo M. Airoldi, David M. Blei, Stephen E. Fienberg, and Eric Xing. Mixed membership stochastic blockmodels. Journal of Machine Learning Research, 1985):1981-0011 2008
[4] Arash A. Amini and Elizaveta Levina. On semidefinite relaxations for the block model. The Annals of Statistics, 46(1):149 179, 2018.
[5] Avner Bar-Hen, Pierre Barbillon, and Sophie Donnet. Block models for generalized multipartite networks: Applications in ecology and ethnobiology. Statistical Modelling, 2020.
10

---

[6] O. Benyahia, C. Largeron, and B. Jeudy. Community detection in dynamic graphs with missing edges. 2017 11th International Conference on Research Challenges Information Science (RCIS), pages 372-381, 2017.
[7] Peter Bickel, David Choi, Xiangyu Chang, and Hai Zhang. Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels. The Annals of Statistics, 41(4))1922 1943, 2013.
[8] Peter J. Bickel and Aiyou Chen. nonparametric view of network models and newman-girvan and other modularities. Proceedings of the National Academy of Sciences, 106(50):21068 21073, 2009.
[9] Kevin Bleakley, Gérard Biau, and Jean-Philippe Vert. Supervised reconstruction of biological networks with local models. Bioinformatics, 23(13)i57--665, 2007.
[10] Charles Bordenave, Mare Lelarge, and Laurent Massoulié. Nonbacktracking spectrum of random graphs: Community detection and nonregular Ramanujan graphs. The Annals of Probability, 46(1):1 - 71, 2018.
[11] Sourav Chatterjee. Matrix estimation by Universal Singular Value Thresholding. The Annals of Statistics, 43(1):177 214, 2015.
[12] Kehui Chen and Jing Lei. Network voos-vaaii for determining the number of communities in network data. Journal of the American Statistical Association, 113:241 - 251, 2014.
[13] Jean-Jacques Daudin, Franck Picard. and Stéphane Robin. A mixture model for random graph. Statistics and Computing, 18:173-183, 2008
[14] Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical review E, 84:066106, 2011.
[15] Souvik Dhara, Julia Gaudio, Elchanan Mossel, and Colin Sandon. Spectral recovery of binary censored block models. arXiv, 2021.
[16] Chao Gao, Yu Lu, Zongming Ma, and Harrison Zhou. Optimal estimation and completion of matrices with biclustering structures. Journal of Machine Learning Research, 17(1):6022-5600, 2016.
[17] Chao Gao, Yu Lu, and Harrison H. Zhou. Rate-optimal graphon estimation. The Annals of Statistics, 43(6):2624 2652, 2015.
[18] Chao Gao, Aad W. van der Vaart, and Harrison H. Zhou, A general framework for Bayes structured linear models. The Annals of Statistics, 48(5):2848 - 2878, 2020.
[19] Solenne Gaucher and Olga Klopp. Maximum likelihood estimation of sparse networks with missing observations. Journal of Statistical Planning and Inference, 215:299-329, 2021.
[20] Christophe Giraud and Nicolas Verzelen. Partial recovery bounds for clustering with the relaxed K-means. Mathematical Statistics and Learning, 1(3):3 2018.
[21] Roger Guimerà and Marta Sales-Pardo. Missing and spurious interactions and the reconstruction of complex networks. Proceedings of the National Academy of Sciences, 106(52):22073- 22078. 2009.
[22] L. Hagen and A. B. Kahng. New spectral methods for ratio cut partitioning and clustering. IEEE Transactions on Computer-Aided Design of Integrated Cireuits and Systems, 1109):077--0085, 1992.
[23] Bruce Hajek, Yihong Wu, and Jiaming Xu. Exact recovery threshold in the binary censored block model. In 2015 IEEE Information Theory Workshop Fall (ITW), pages 99-103, 2015.
[24] Mark S. Handcock and Krista Gile. Modeling social networks from sampled data. The Annals of Applied Statistics, 4(1), 2010.

---

[25] Trevor Hastie, Rahul Mazumder, Jason D. Lee, and Reza Zadeh. Matrix completion and low-rank svd via fast alternating least squares. Journal of Machine Learning Research, 16(104):3367- 3402, 2015.
[26] Jake M. Hofman and Chris H. Wiggins. Bayesian approach to network modularity, Physical Review Letters, 100:258701, 2008.
[27] Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social Networks, 5(2):109 - 137, 1983.
[28] Michael I. Jordan, Zoubin Ghahramani, Tommi S. Jaakkola, and Lawrence K. Saul. An introduction variational methods for graphical models. Machine Learning. 37(2):183-233, 1999.
[29] Olga Klopp, Alexandre B. Tsybakov, and Nicolas Verzelen. Oracle inequalities for network models and sparse graphon estimation. The Annals of Statistics, 45(1):316 - 354, 2017.
[30] Olga Klopp and Nicolas Verzelen. Optimal graphon estimation in cut distance. Probability Theory and Related Fields, (133)):033-1090 2019.
[31] Gueorgi Kossinets. Effects of missing data in social networks. Social Networks, 28(3):247-268, 2006.
[32] Meghana Kshirsagar, Jaime Carbonell, and Judith Meenh-Secthaaaan.. Techniques to cope with missing data in host-pathogen protein interaction prediction. Bioinformatics, (8166)44466 2012.
[33] Jing Lei. A goodness-of-fi test for stochastic block models. The Annals of Statistics, 44(1):401 424, 2016.
[34] Léa Longepierre and Catherine Matias. Consistency of the maximum likelihood and variational estimators in a dynamic stochastic block model. Electronic Journal of Statistics, 13(2):4157- 4223, 2019.
[35] L. Lovász. Large Networks and Graph Limits. American Mathematical Society colloquium publications. American Mathematical Society, 2012.
[36] Linyuan Lü and Tao Zhou. Link prediction in complex networks: A survey. Physica A: Statistical Mechanics and its Applications, (90(6):1100-1)) 1170, 2011.
[37] Mahendra Mariadassou and Timothée Tabouy. Consistency and asymptotic normality of stochas- tic block models estimators from sampled data. Electronic Journal Statistics, 14(2):3672- 3704, 2020.
[38] Laurent Massoulié. Community detection thresholds and the weak ramanujan property. In Proceedings of the Forty-Sixth Annual ACM Symposium Theory of Computing, STOC 14, page 694-703, New York, NY, USA, 2014. Association for Computing Machinery.
[39] F. McSherry. Spectral partitioning of random graphs. In Proceedings 42nd IEEE Symposium on Foundations Computer Science, pages 529-537, 2001.
[40] Leonardo Morelli, Valentina Giansanti, and Davide Cittaro. Nested stochastic block models applied to the analysis of single cell data. bioRxiv, 2021.
[41] Elchanan Mossel, Joe Neeman, and Allan Sly. Consistency thresholds for the planted bisection model. Electronic Journal of Probability, 21 21(nne):: - 24, 2016.
[42] M. F. Newman. Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103((3))85777-8822 2006.
[43] Mark Newman. Finding community structure in networks using the eigenvectors matrices. Physical review E, 74(3):036104, 2006.
12

---

[44] Debdeep Pati, Anirban Bhattacharya, and Yun Yang. On statistical optimality of variational bayes. Amos Storkey and Fernando Perez-Cruz, Cruz, editors, Proceedings of the Twenty-Fing First International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 1579-1588. PMIR, 2018.
[45] Zahra S. Razaee, Arash A. Amini, and Jingyi Jessica Li. Matched bipartite block model with covariates. Journal of Machine Learning Research, 20(34): 1-44, 2019.
[46] Karl Rohe, Sourav Chatterjee, and Bin Yu. Spectral clustering and the high-dimensional stochastic blockmodel. The Annals of Statistics, 39(4): 1915, 2011.
[47] Juliette Stehlé, Nicolas Voirin, Alain Barrat, Ciro Cattuto, Lorenzo Isella, Jean-François Pinton, Marco Quaggiotto, Wouter Van den Broeck, Corinne Régis, Bruno Lina, and Philippe Vanhems. High-resolution measurements of face-to-face contact patterns in primary school. PLOS ONE, 6(8):1-13, 2011.
[48] Timothée Tabouy, Pierre Barbillon, and Julien Chiquet. Variational inference for stochastic block models from sampled data. Journal of the American Statistical Association, 115(529):455-46, 2020.
[49] M.J. Wainwright and M.I. Jordan. Graphical Models, Exponential Families, and Variational Inference. Foundations and Trends in Machine Learning, 1(1-2):1-305, 2008
[50] Y. X. Rachel Wang and Peter J. Bickel. sagelihood-baseed model selection for stochastic block models. The Annals of Statistics, 45(2):500 528, 2017.
[51] Jiaming Xu. Rates of convergence of spectral methods for graphon estimation. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5433-5442. PMLR, 2018.
[52] Bowen Yan and Steve Gregory. Finding missing edges in networks based on their community structure. Physical review. E, 85:0561 12, 2012.
[53] Yun Yang. Debdeep Pati, and Anirban Bhattacharya. a-variational inference with statistical guarantees. The Annals of Statistics, 48(2):886 - 905, 2020.
[54] Anderson Y. Zhang and Harrison H. Zhou. Thcoretical and computational guarantees of mean field variational inference for community detection. The Annals of Statistics, 48(5):2575 2598, 2020.
[55] Yuan Zhang, Flizaveta Levina, and Ji Zhu. Estimating network edge probabilities by neighbour- hood smoothing. Biometrika, 104(4):771-783, 2017.
[56] Yunpeng Zhao, Yun-Jhong Wu, Elizaveta Levina, and Ji Zhu. Link prediction for partially observed networks. Journal of Computational and Graphical Statistics, 26(3):725-733, 2017.
13


Reviews:
[{"review_id": "Lr2gMKnX0A-", "reviewer": "Reviewer_Pcfk", "summary": "This paper proves that mean-field variational inference is minimax optimal for parameter estimation of the stochastic block model (SBM) with missing data. The paper establishes this result for both dense networks as well as for (more realistic) sparse networks. The paper further reports the results of experiments on both real and synthetic data that clearly corroborate the paper's main theoretical results.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper contributes a significant morsel of knowledge to what we know about the statistical properties of variational inference. The result is powerfully simple: VB is minimax optimal for the SBM with missing links for both dense and sparse networks. This result should impact directly the statistical networks community but also provide a stepping stone to broader/more general theoretical analysis of variational inference.\n\nI say all of that with the caveat that I am not up-to-date with all of the most recent literature on theoretical analysis of VB and have questions for the authors about how their results relate to a pair of related papers that are not cited in the current version. Can the authors describe the relation of their paper to the papers of Debdeep et al. (2018) and Yang et al. (2020) [2]? The first paper provides \"general conditions for obtaining optimal risk bounds for point estimates acquired from mean-field variational Bayesian inference\" and gives examples related to the SBM (i.e., latent Dirichlet allocation). The second paper also provides similar kinds of results that establish minimax optimality of variational Bayes under different conditions.\n\nIn terms of clarity, the paper is well-written but suffers from some notational headaches. The authors should clean up their notation and employ more aliasing so that, for example, the bounds on sums do not take up the entire equation (see line 128). \n\nMinor comments:\n* Add legends to figures 1 and 2. \n* Line 60: \"Constribution\" -> \"Contributions\"\n* Line 95: \"citations\" -> \"citation\"\n\n[1] Pati, Debdeep, Anirban Bhattacharya, and Yun Yang. \"On statistical optimality of variational Bayes.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2018.\n\n[2] Yang, Yun, Debdeep Pati, and Anirban Bhattacharya. \"$\\alpha$-variational inference with statistical guarantees.\" The Annals of Statistics 48.2 (2020): 886-905.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "BwM_B2ZJj6f", "reviewer": "Reviewer_1S7t", "summary": "The main contribution of this paper is to propose and analyze a variational approximation (VA) method for the inference of the SBM. The main result is to establish that VA leads to a tractable and minimax optimal algorithm, specifically the latter is based on the EM principle with a variational approximation scheme. Numerical experiments are also performed to verify the theory. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the paper is well organized and the results are useful to this community. However, the reviewer has several concerns related to the technical novelty, algorithm implementation, as follows:\n\n- The study motivated the variational approximation approach by the need for complexity reduction and the original MLE problem is replaced by the VA problem in line 170 of Sec. 3.1, which is later on tackled by the EM algorithm. Several issues arise here:\n\n-- The VA problem has taken the model distribution $P_\\tau$ as the multinomial distribution to approximate $P(.|X.A, \\alpha, Q)$. The reviewer wonders if this is the only model distribution to use for the algorithm? Does such choice of the model distribution affect the minimax optimal performance of the proposed estimator? Currently, the latter choice is not discussed in the paper. \n\n-- It is mentioned in the study that the EM algorithm is initialized using a clustering step such as \"missSBM\". Furthermore, the analysis in this paper (in the appendix) seems to have assumed that a *global optimizer* is obtained by the EM. The reviewer is concerned about how such global optimality condition can be enforced using the existing algorithm, e.g., is there any guarantee on global optimality when using initialization step such as \"missSBM\"?\n\n-- In the numerical simulation, the study has only compared the EM algorithm (which is a VA of the MLE) to missSBM and softImpute. The reviewer wonders how is the performance of the true MLE? \n\n- The reviewer notices that a number of the intermediate steps in the proof followed from [34]. Upon checking [34], it is also found that the latter paper has proposed a VA method for the inference of the SBM similar this paper. May I know what is the main technical novelty of the current paper with respect to [34]? \n\nMoreoever, in Sec 3.2 on the the convergence rates results, the compact sets ${\\cal A}, {\\cal Q}$ in A1, A2 have not been clearly defined. It may be helpful to give examples for these sets. \n\n- As a minor point, it should be noted that the paper has not followed strictly the official format of an NeurIPS submission (e.g., with a smaller font size). \n\n**--- Post Rebuttal ---**\n\nI have read the authors response, which has sufficiently addressed my previous concern. I have updated my score accordingly. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There isn't any potential negative societal impact. The limitation/suggestions for improvement have been discussed in the main review above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "9YLPkvdYom", "reviewer": "Reviewer_FvDk", "summary": "This paper considers estimation of the parameters of a stochastic block model (community membership and probability parameters) using a variational approach. Both the censored, dense model and the sparse model are considered. Experiments on real and synthetic data compare the estimator to another variational estimator, as well as another estimator based on Universal Singular Value Thresholding.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I don’t see much of a novel contribution in this work. The variational estimator is in large part already present in Reference 17. The only change is accounting for the missing observations by including the X_{ij} variables. Theorems 1 and 3 are cited from prior work, while Theorem 2 seems to follow from Proposition 2 in Reference 17 (see discussion below Proposition 2 in Reference 17). Given that the estimate of the communities is accurate, then Theorem 2 follows from Theorem 1.\n\nMoreover, it seems that the main effort is estimation of the community assignments. From this estimate, the estimator of the matrix of edge probabilities takes on a simple form. There will be some regimes where finding the community assignments exactly is possible via existing methods simpler than the variational method proposed, and this should be acknowledged. This applies to both the standard and censored models.\n\nThe paper claims optimality, so there should be justification of the optimal rates of the estimators.\n\nFinally, the font size appears to have been set small.\n\nEdit: Score updated in light of discussion.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "0Rsnbwp9C1j", "reviewer": "Reviewer_UYYv", "summary": "Paper provides an approximation to MLE of SBM with missing observations variational via variational inference. Paper provided proofs for statistical optimality and associated simulations showing advantages to existing methods.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is a strong work on the variational inference of SBM. The paper achieved the following\n- Connected the variational inference estimator to the MLE, which is believed to be the optimal estimator in the minimax sense. Paper provided the consistency between the two and gave careful mathematical analysis.\n- Simulation shows good performance of the proposed method\n- An EM algorithm is constructed for approximating the VI estimator. Although the convergence guarantee is not built, paper mentioned techniques on avoiding falling into local maximas\n\nIn general, a good contribution to the SBM literature and I'd recommend the conference to accept. \n\nSome points of improvement\n- Consistency result between VI and MLE is very interesting. Theorem suggests that both estimators are the same up to a permutation, which is very surprising since when node number goes up, the signal level requirement is high to ensure such consistency. If you could explain a bit more on this that would be helpful\n- It would be interesting to see community localization errors (say, ratio of nodes with community labels wrong). In this sense you don't need an oracle (which always gives 0 errors), and the ranges are between 0-1 so it gives sense to cross comparison. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Paper mentioned potential negative societal impact. Good for a theoretical work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proves that the mean-field variational inference is minimax optimal for estimating the parameters of the stochastic block model (SBM) even when some of the links are missing. While the mean-field variational method has been studied for the SBM, this paper still addresses an interesting question. In particular, it shows that there is no computational gap in the problem of link prediction for SBM byproviding an estimator that is minimax optimal and computationally feasible (this question had been open for a while). Hence, given this contribution, I agree with the reviewers that the paper should be accepted in Neurips. 
Decision: Accept (Poster)