Posterior Contraction Rates for Stochastic Block Models
Tóm tắt
With the advent of structured data in the form of social networks, genetic circuits and protein interaction networks, statistical analysis of networks has gained popularity over recent years. The stochastic block model constitutes a classical cluster-exhibiting random graph model for networks. There is a substantial amount of literature devoted to proposing strategies for estimating and inferring parameters of the model, both from classical and Bayesian viewpoints. Unlike the classical counterpart, there is a dearth of theoretical results on the accuracy of estimation in the Bayesian setting. In this article, we undertake a theoretical investigation of the posterior distribution of the parameters in a stochastic block model. In particular, we show that one obtains near-optimal rates of posterior contraction with routinely used multinomial-Dirichlet priors on cluster indicators and uniform or general Beta priors on the probabilities of the random edge indicators. Our theoretical results are corroborated through a small scale simulation study.
Tài liệu tham khảo
Abramowitz, M. and Stegun, I. (1964). Handbook of mathematical functions: with formulas, graphs, and mathematical tables. No. 55. Courier Corporation.
Airoldi, E. M., Blei, D. M., Fienberg, S. E. and Xing, E. P. (2009). Mixed membership stochastic blockmodels. In: Advances in Neural Information Processing Systems. pp. 33–40.
Airoldi, E., Costa, T. and Chan, S. (2013). Stochastic blockmodel approximation of a graphon: Theory and consistent estimation. In: Advances in Neural Information Processing Systems. pp. 692–700.
Amini, A. A., Chen, A., Bickel, P. J. and Levina, E. (2013). Pseudo-likelihood methods for community detection in large sparse networks. The Annals of Statistics 41, 4, 2097–2122.
Banerjee, S. and Ghosal, S. (2014). Posterior convergence rates for estimating large precision matrices using graphical models. Electronic Journal of Statistics 8, 2, 2111–2137.
Barron, A. R. (1988). The exponential convergence of posterior probabilities with implications for Bayes estimators of density functions. Univ.
Barron, A., Schervish, M. J. and Wasserman, L. (1999). The consistency of posterior distributions in nonparametric problems. The Annals of Statistics 27, 2, 536–561.
Bickel, P. and Chen, A. (2009). A nonparametric view of network models and Newman–Girvan and other modularities. Proceedings of the National Academy of Sciences106, 50, 21068–21073.
Bickel, P. J., Choi, D., Chang, X. and Zhang, H. (2013). Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels. The Annals of Statistics 41, 4, 1922–1943.
Bontemps, D. (2011). Bernstein–von mises theorems for gaussian regression with increasing number of regressors. The Annals of Statistics 39, 5, 2557–2584.
Castillo, I. and van der Vaart, A. W. (2012). Needles and straw in a haystack: Posterior concentration for possibly sparse sequences. The Annals of Statistics 40, 4, 2069–2101.
Castillo, I., Schmidt-Hieber, J. and van der Vaart, A. (2015). Bayesian linear regression with sparse priors. Ann. Statist. 43, 5, 1986–2018. https://doi.org/10.1214/15-AOS1334.
Channarond, A., Daudin, J. -J. and Robin, S. (2012). Classification and estimation in the stochastic block model based on the empirical degrees. Electronic Journal of Statistics 6, 2574–2601.
Chatterjee, S. (2014). Matrix estimation by universal singular value thresholding. The Annals of Statistics 43, 1, 177–214.
Dasgupta, A., Hopcroft, J. E. and McSherry, F. (2004). Spectral analysis of random graphs with skewed degree distributions. IEEE, p. 602–610.
Erdős, P. and Rényi, A. (1961). On the evolution of random graphs. Bull. Inst. Internat. Statist 38, 4, 343–347.
Frank, O. and Strauss, D. (1986). Markov graphs. Journal of the American Statistical association 81, 395, 832–842.
Gao, C., Lu, Y. and Zhou, H. H. (2015). Rate-optimal graphon estimation. The Annals of Statistics 43, 6, 2624–2652.
Gao, C., van der Vaart, A. W. and Zhou, H. H. (2018). A general framework for bayes structured linear models. arXiv:1506.02174.
Geng, J., Bhattacharya, A. and Pati, D. (2018). Probabilistic community detection with unknown number of communities. Journal of American Statistical Association (to appear).
Ghosal, S., Ghosh, J. K. and van der Vaart, A. W. (2000). Convergence rates of posterior distributions. Annals of Statistics 28, 2, 500–531.
Ghosal, S. and Roy, A. (2006). Posterior consistency of gaussian process prior for nonparametric binary regression. The Annals of Statistics, 2413–2429.
Ghosal, S. and van der Vaart, A. W. (2007). Convergence rates of posterior distributions for noniid observations. The Annals of Statistics 35, 1, 192–223.
Goldenberg, A., Zheng, A., Fienberg, S. and Airoldi, E. (2010). A survey of statistical network models. Foundations and Trends®;, in Machine Learning 2, 2, 129–233.
Golightly, A. and Wilkinson, D. J. (2005). Bayesian inference for stochastic kinetic models using a diffusion approximation. Biometrics 61, 3, 781–788.
Hayashi, K., Konishi, T. and Kawamoto, T. (2016). A tractable fully bayesian method for the stochastic block model. arXiv:1602.02256.
Hoff, P. D., Raftery, A. E. and Handcock, M. S. (2002). Latent space approaches to social network analysis. Journal of the American Statistical association 97, 460, 1090–1098.
Holland, P. W. and Leinhardt, S. (1981). An exponential family of probability distributions for directed graphs. Journal of the American Statistical association 76, 373, 33–50.
Holland, P. W., Laskey, K. B. and Leinhardt, S. (1983). Stochastic blockmodels: First steps. Social Networks 5, 2, 109–137.
Karrer, B. and Newman, M. E. J. (2011). Stochastic blockmodels and community structure in networks. Physical Review E 83, 1, 016107.
Lovász, L. and Szegedy, B. (2006). Limits of dense graph sequences. Journal of Combinatorial Theory, Series B 96, 6, 933–957.
McDaid, A., Murphy, T. B., Friel, N. and Hurley, N. (2013). Improved bayesian inference for the stochastic block model with application to large networks. Computational Statistics & Data Analysis 60, 12–31.
Newman, M. E. J. (2012). Communities, modules and large-scale structure in networks. Nature Physics 8, 1, 25–31.
Nowicki, K. and Snijders, T. A. B. (2001). Estimation and prediction for stochastic blockstructures. Journal of the American Statistical Association 96, 455, 1077–1087.
Pati, D., Bhattacharya, A., Pillai, N. S. and Dunson, D. (2014). Posterior contraction in sparse bayesian factor models for massive covariance matrices. The Annals of Statistics 42, 3, 1102–1130.
Rousseau, J. and Mengersen, K. (2011). Asymptotic behaviour of the posterior distribution in overfitted mixture models. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 73, 5, 689–710.
Schwartz, L. (1965). On bayes procedures. Probability Theory and Related Fiel 4, 1, 10–26.
Snijders, T. A. B. and Nowicki, K. (1997). Estimation and prediction for stochastic blockmodels for graphs with latent block structure. Journal of Classification 14, 1, 75–100.
Suwan, S., Lee, D. S., Tang, R., Sussman, D. L., Tang, M. and Priebe, C. E. (2016). Empirical bayes estimation for the stochastic block model. Electronic Journal of Statistics 10, 1, 761–782.
Szemerédi, E. (1975). On sets of integers containing no k elements in arithmetic progression. Acta Arith 27, 199-245, 2.
van der Pas, S., Kleijn, B. and van der Vaart, A. (2014). The horseshoe estimator: Posterior concentration around nearly black vectors. Electronic Journal of Statistics 8, 2, 2585–2618.
van der Pas, S. L. and van der Vaart, A. W. (2018). Bayesian community detection. Bayesian Analysis 13, 3, 767–796.
Vershynin, R. (2012). Introduction to the non-asymptotic analysis of random matrices. Compressed Sensing, 210–268.
Wang, Y. J. and Wong, G. Y. (1987). Stochastic blockmodels for directed graphs. Journal of the American Statistical Association 82, 397, 8–19.
Zhao, Y., Levina, E. and Zhu, J. (2011). Community extraction for social networks. Proceedings of the National Academy of Sciences 108, 18, 7321–7326.
Zhao, Y., Levina, E. and Zhu, J. (2012). Consistency of community detection in networks under degree-corrected stochastic block models. The Annals of Statistics 40, 4, 2266–2292.