Mean Field for the Stochastic Blockmodel: Optimization Landscape and Convergence Issues
Variational approximation has been widely used in large-scale Bayesian inference recently, the simplest kind of which involves imposing a mean field assumption to approximate complicated latent structures. Despite the computational scalability of mean field, theoretical studies of its loss function surface and the convergence behavior of iterative updates for optimizing the loss are far from complete. In this paper, we focus on the problem of community detection for a simple twoclass Stochastic Blockmodel (SBM). Using batch co-ordinate ascent (BCAVI) for updates, we show different convergence behavior with respect to different initializations. When the parameters are known, we show that a random initialization can converge to the ground truth, whereas in the case when the parameters themselves need to be estimated, a random initialization will converge to an uninformative local optimum.
Considers a simple variant of the stochastic block model (SBM) for networks with 2 communities/clusters.  Previous work has studied the asymptotic behavior of the global optimizer of the mean field variational inference objective; this paper instead analyzes the dynamics of mean field coordinate ascent updates.  It shows recovery of the correct community structure for most random initializations given correct model parameters, but for a particular way of initializing inference with unknown community interaction probabilities, inference converges to an uninformative local optimum with high probability.  ORIGINALITY:  Recent papers have given related analyses of inference algorithms for mixture models, but study of inference dynamics for the SBM appears novel.  CLARITY:  The fairly technical results here would clearly be easier to present in an extended journal paper.  This submission puts some proofs in the supplement, but in my view this only partially succeeds in making the main manuscript readable.  It would benefit from moving a few more details from Sec. 3 to the supplement, and adding additional explanation.  There is a lot of mathematical notation, some introduced with no explanation even on first use, and I found myself repeatedly hunting through the paper to find the definition of terms.  Some more detailed comments: 1) Sec. 2 does not mention that the reason probabilities B are constrained symmetric is that A is the symmetric adjacency matrix of an undirected graph.  (Several previous papers have developed SBM variants for directed graphs, with non-symmetric B.) 2) Sec. 2 needs to be slower in explaining how the algorithm is changing in the last two equations.  (Batch updates are not coordinate ascent on the mean field objective, and in general are not guaranteed convergent.  The "population" variant justification is ignored.)  Also \xi^(s) is not defined, and its connection to \psi^(s) is not specified. 3) Proposition 3.1 statement, second "eigenvalues" should be "eigenvectors".  Alpha variables are an example of notation introduced without comment in the middle of a technical argument, that you then assume the reader will remember when trying to understand your experiments in Sec. 4.  EXPERIMENTS:  The (limited) experiments in Sec. 4 are a useful supplement to the earlier theory, but the text here is terse and includes insufficient explanation for the conceptual interpretation of the variables involved.  In particular, a much clearer explanation for Figure 1(a) is needed.  TECHNICAL CONTENT & SIGNIFICANCE:   The technical derivations needed to establish the main theorems are non-trivial, and the key arguments in the main paper all seem correct.  (I did not verify all proofs from the appendices.)  Given that the model is restricted to two communities, it found it unsurprising to find (Theorem 3.3) that mean field converges to the correct community structure with known parameters.  (This is similar to the positive results of [25] for 2-cluster Gaussian mixtures, but I would argue that the negative results in [13] with 3 or more clusters are more illuminating and important.)  The negative results of Sec. 3.2 are more interesting.  They essentially say that if inference is initialized with random community assignments, and model parameters are updated from there, the probability of identification of correct communities is exponentially small.  However, I disagree with the claim in Sec. 5 that this is "typically done by most practitioner".  The researchers who I know that do applied work with cluster-based models know that initializing with random partitions tends to lead to very poor local optima.  For this SBM, here is one example of a more standard initialization: 1) Sample a "reasonable" set of initial block interaction probabilities.  (For this model, this proposal would pick p >> q.) 2) Do at least one, and perhaps several, updates of the community probabilities psi given the fixed initial (p,q). 3) From this point, update (p,q) and then iterate as analyzed in the paper.  The positive results in Sec. 3.1 with correct (p,q) suggest that if the (p,q) sampled in step #1 is within a neighborhood of the correct values, this algorithm may lead to a good optimum.  Analysis of such a more realistic inference scheme could be an interesting area for future research.