Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

I 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.

In 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). 

Minor comments:
* Add legends to figures 1 and 2. 
* Line 60: "Constribution" -> "Contributions"
* Line 95: "citations" -> "citation"

[1] Pati, Debdeep, Anirban Bhattacharya, and Yun Yang. "On statistical optimality of variational Bayes." International Conference on Artificial Intelligence and Statistics. PMLR, 2018.

[2] Yang, Yun, Debdeep Pati, and Anirban Bhattacharya. "$\alpha$-variational inference with statistical guarantees." The Annals of Statistics 48.2 (2020): 886-905.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: This is a strong work on the variational inference of SBM. The paper achieved the following
- 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.
- Simulation shows good performance of the proposed method
- 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

In general, a good contribution to the SBM literature and I'd recommend the conference to accept. 

Some points of improvement
- 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
- 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. 
limitations_and_societal_impact: Paper mentioned potential negative societal impact. Good for a theoretical work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

Moreover, 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.

The paper claims optimality, so there should be justification of the optimal rates of the estimators.

Finally, the font size appears to have been set small.

Edit: Score updated in light of discussion.

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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:

- 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:

-- 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. 

-- 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"?

-- 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? 

- 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]? 

Moreoever, 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. 

- 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). 

**--- Post Rebuttal ---**

I have read the authors response, which has sufficiently addressed my previous concern. I have updated my score accordingly. 
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_title: null

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)