A Theoretical Case Study of Structured Variational Inference for Community Detection

Mingzhang Yin, Y. X. Rachel Wang, Purnamrita Sarkar
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:3750-3761, 2020.

Abstract

Mean-field variational inference (MFVI) has been widely applied in large scale Bayesian inference. However, MFVI assumes independent distribution on the latent variables, which often leads to objective functions with many local optima, making optimization algorithms sensitive to initialization. In this paper, we study the advantage of structured variational inference in the context of the two-class Stochastic Blockmodel. To facilitate theoretical analysis, the variational distribution is constructed to have a simple pairwise dependency structure on the nodes of the network. We prove that, in a broad density regime and for general random initializations, unlike MFVI, the estimated class labels by structured VI converge to the ground truth with high probability, when the model parameters are known, estimated within a reasonable range or jointly optimized with the variational parameters. In addition, empirically we demonstrate structured VI is more robust compared with MFVI when the graph is sparse and the signal to noise ratio is low. The paper takes a first step towards understanding the importance of dependency structure in variational inference for community detection.

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-yin20a, title = {A Theoretical Case Study of Structured Variational Inference for Community Detection}, author = {Yin, Mingzhang and Wang, Y. X. Rachel and Sarkar, Purnamrita}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {3750--3761}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/yin20a/yin20a.pdf}, url = {https://proceedings.mlr.press/v108/yin20a.html}, abstract = {Mean-field variational inference (MFVI) has been widely applied in large scale Bayesian inference. However, MFVI assumes independent distribution on the latent variables, which often leads to objective functions with many local optima, making optimization algorithms sensitive to initialization. In this paper, we study the advantage of structured variational inference in the context of the two-class Stochastic Blockmodel. To facilitate theoretical analysis, the variational distribution is constructed to have a simple pairwise dependency structure on the nodes of the network. We prove that, in a broad density regime and for general random initializations, unlike MFVI, the estimated class labels by structured VI converge to the ground truth with high probability, when the model parameters are known, estimated within a reasonable range or jointly optimized with the variational parameters. In addition, empirically we demonstrate structured VI is more robust compared with MFVI when the graph is sparse and the signal to noise ratio is low. The paper takes a first step towards understanding the importance of dependency structure in variational inference for community detection.} }
Endnote
%0 Conference Paper %T A Theoretical Case Study of Structured Variational Inference for Community Detection %A Mingzhang Yin %A Y. X. Rachel Wang %A Purnamrita Sarkar %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-yin20a %I PMLR %P 3750--3761 %U https://proceedings.mlr.press/v108/yin20a.html %V 108 %X Mean-field variational inference (MFVI) has been widely applied in large scale Bayesian inference. However, MFVI assumes independent distribution on the latent variables, which often leads to objective functions with many local optima, making optimization algorithms sensitive to initialization. In this paper, we study the advantage of structured variational inference in the context of the two-class Stochastic Blockmodel. To facilitate theoretical analysis, the variational distribution is constructed to have a simple pairwise dependency structure on the nodes of the network. We prove that, in a broad density regime and for general random initializations, unlike MFVI, the estimated class labels by structured VI converge to the ground truth with high probability, when the model parameters are known, estimated within a reasonable range or jointly optimized with the variational parameters. In addition, empirically we demonstrate structured VI is more robust compared with MFVI when the graph is sparse and the signal to noise ratio is low. The paper takes a first step towards understanding the importance of dependency structure in variational inference for community detection.
APA
Yin, M., Wang, Y.X.R. & Sarkar, P.. (2020). A Theoretical Case Study of Structured Variational Inference for Community Detection. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:3750-3761 Available from https://proceedings.mlr.press/v108/yin20a.html.

Related Material