Theoretical and computational guarantees of mean field variational inference for community detection (Q2215750)

The authors study the mean field method for community detection under the stochastic block model. They consider the statistical and computational guarantees of the iterative variational inference algorithm for community detection. The primary goal of community detection problem is to recover the community membership in a network. Denote the underlying ground truth by \(Z^*\). For a network of $n$ nodes and $k$ communities, \(Z^*\) is an \(n\times k\) matrix with each row a standard Euclidean basis in \(\mathbb R^k\). They propose an iterative algorithm called batch coordinate ascent variational inference (BCAVI), a slight modification of CAVI with batch updates, to make parallel and distributed computing possible. Let \(\pi^{(s)}\) denote the output of the $s$-th iteration, a \(\{\pi_i ^{(s)} \}_{i=1}^n\) is equal to 1, which is interpreted as an approximate posterior probability of assigning the corresponding node of each row into \(k\) communities. An informal statement of the main result: Let \(\pi^{(s)}\) be the estimation of community membership from the iterative algorithm BCAVI after \(s\) iterations. Under weak regularity condition, for some \(c_n = o_n(1)\), with high probability, we have for all $s\geq 0$, \[ l(\pi^{(s+1)},Z^*)\leq\text{ minimax rate }+ c_n l (\pi^{(s)}, Z^*) .\tag{1} \] The main contribution of this paper is equation (1).