×

Likelihood inference for large scale stochastic blockmodels with covariates based on a divide-and-conquer parallelizable algorithm with communication. (English) Zbl 07499080

Summary: We consider a stochastic blockmodel equipped with node covariate information, that is, helpful in analyzing social network data. The key objective is to obtain maximum likelihood estimates of the model parameters. For this task, we devise a fast, scalable Monte Carlo EM type algorithm based on case-control approximation of the log-likelihood coupled with a subsampling approach. A key feature of the proposed algorithm is its parallelizability, by processing portions of the data on several cores, while leveraging communication of key statistics across the cores during each iteration of the algorithm. The performance of the algorithm is evaluated on synthetic datasets and compared with competing methods for blockmodel parameter estimation. We also illustrate the model on data from a Facebook derived social network enhanced with node covariate information. Supplemental materials for this article are available online.

MSC:

62-XX Statistics

Software:

HOGWILD
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Agarwal, A.; Duchi, J. C., “Distributed Delayed Stochastic Optimization,”, in Advances in Neural Information Processing Systems, 873-881 (2011)
[2] Airoldi, E. M.; Blei, D. M.; Fienberg, S. E.; Xing, E. P., “Mixed Membership Stochastic Blockmodels,”, Journal of Machine Learning Research, 9, 1981-2014 (2008) · Zbl 1225.68143
[3] Amini, A. A.; Chen, A.; Bickel, P. J.; Levina, E., “Pseudo-Likelihood Methods for Community Detection in Large Sparse Networks,”, The Annals of Statistics, 41, 2097-2122 (2013) · Zbl 1277.62166 · doi:10.1214/13-AOS1138
[4] Breslow, N. E., “Statistics in Epidemiology: The Case-Control Study,”, Journal of the American Statistical Association, 91, 14-28 (1996) · Zbl 0870.62082 · doi:10.1080/01621459.1996.10476660
[5] Breslow, N. E.; Day, N.; Schlesselman, J. J., “Statistical Methods in Cancer Research. Volume 1: The Analysis of Case-Control Studies,”, Journal of Occupational and Environmental Medicine, 24, 255-257 (1982)
[6] Choi, D. S.; Wolfe, P. J.; Airoldi, E. M., “Stochastic Blockmodels With a Growing Number of Classes,”, Biometrika, 99, 273-284 (2012) · Zbl 1318.62207 · doi:10.1093/biomet/asr053
[7] Decelle, A.; Krzakala, F.; Moore, C.; Zdeborová, L., “Asymptotic Analysis of the Stochastic Block Model for Modular Networks and Its Algorithmic Applications,”, Physical Review E, 84, 066106 (2011)
[8] Dekel, O.; Gilad-Bachrach, R.; Shamir, O.; Xiao, L., “Optimal Distributed Online Prediction Using Mini-Batches,”, The Journal of Machine Learning Research, 13, 165-202 (2012) · Zbl 1283.68404
[9] Duchi, J. C.; Agarwal, A.; Wainwright, M. J., “Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling,”, IEEE Transactions on Automatic Control, 57, 592-606 (2012) · Zbl 1369.90156 · doi:10.1109/TAC.2011.2161027
[10] Fithian, W.; Hastie, T., “Local Case-Control Sampling: Efficient Subsampling in Imbalanced Data Sets,”, Annals of Statistics, 42, 1693 (2014) · Zbl 1305.62096 · doi:10.1214/14-AOS1220
[11] Fortunato, S., “Community Detection in Graphs,”, Physics Reports,, 486, 75-174 (2010) · doi:10.1016/j.physrep.2009.11.002
[12] Gelman, A.; Meng, X.-L, “Simulating Normalizing Constants: From Importance Sampling to Bridge Sampling to Path Sampling,”, Statistical Science, 13, 163-185 (1998) · Zbl 0966.65004 · doi:10.1214/ss/1028905934
[13] Girvan, M.; Newman, M. E., “Community Structure in Social and Biological Networks,”, Proceedings of the National Academy of Sciences, 99, 7821-7826 (2002) · Zbl 1032.91716 · doi:10.1073/pnas.122653799
[14] Handcock, M. S.; Raftery, A. E.; Tantrum, J. M., “Model-Based Clustering for Social Networks,”, Journal of the Royal Statistical Society, Series A, 170, 301-354 (2007) · doi:10.1111/j.1467-985X.2007.00471.x
[15] Hoff, P. D., “Bilinear Mixed-Effects Models for Dyadic Data,”, Journal of the American Statistical Association, 100, 286-295 (2005) · Zbl 1117.62353 · doi:10.1198/016214504000001015
[16] Hoff, P. D., “Dyadic Data Analysis With Amen,”, arXiv preprint arXiv, 1506, 08237 (2015)
[17] Hoff, P. D.; Raftery, A. E.; Handcock, M. S., “Latent Space Approaches to Social Network Analysis,”, Journal of the American Statistical Association, 97, 1090-1098 (2002) · Zbl 1041.62098 · doi:10.1198/016214502388618906
[18] Holland, P. W.; Laskey, K. B.; Leinhardt, S., “Stochastic Blockmodels: First Steps,”, Social Networks, 5, 109-137 (1983) · doi:10.1016/0378-8733(83)90021-7
[19] Johansson, B.; Rabi, M.; Johansson, M., “A Randomized Incremental Subgradient Method for Distributed Optimization in Networked Systems,”, SIAM Journal on Optimization,, 20, 1157-1170 (2009) · Zbl 1201.65100 · doi:10.1137/08073038X
[20] Latouche, P.; Robin, S.; Ouadah, S., “Goodness of Fit of Logistic Regression Models for Random Graphs,”, Journal of Computational and Graphical Statistics, 27, 98-109 (2018) · Zbl 07498970 · doi:10.1080/10618600.2017.1349663
[21] Ma, Z.; Ma, Z., “Exploration of Large Networks via Fast and Universal Latent Space Model Fitting,”, arXiv preprint arXiv, 1705, 02372 (2017)
[22] Mariadassou, M.; Robin, S.; Vacher, C., “Uncovering Latent Structure in Valued Graphs: A Variational Approach,”, The Annals of Applied Statistics, 4, 715-742 (2010) · Zbl 1194.62125 · doi:10.1214/10-AOAS361
[23] McDonald, R.; Hall, K.; Mann, G., 456-464 (2010), Association for Computational Linguistics
[24] Mcdonald, R.; Mohri, M.; Silberman, N.; Walker, D.; Mann, G. S., “Efficient Large-Scale Distributed Training of Conditional Maximum Entropy Models,”, in Advances in Neural Information Processing Systems, 1231-1239 (2009)
[25] Nedic, A.; Ozdaglar, A., “Distributed Subgradient Methods for Multi-Agent Optimization,”, IEEE Transactions on Automatic Control, 54, 48-61 (2009) · Zbl 1367.90086 · doi:10.1109/TAC.2008.2009515
[26] Nowicki, K.; Snijders, T. A. B., “Estimation and Prediction for Stochastic Blockstructures,”, Journal of the American Statistical Association, 96, 1077-1087 (2001) · Zbl 1072.62542 · doi:10.1198/016214501753208735
[27] Raftery, A. E.; Niu, X.; Hoff, P. D.; Yeung, K. Y., “Fast Inference for the Latent Space Network Model Using a Case-Control Approximate Likelihood,”, Journal of Computational and Graphical Statistics, 21, 901-919 (2012) · doi:10.1080/10618600.2012.679240
[28] Ram, S. S.; Nedić, A.; Veeravalli, V. V., “Distributed Stochastic Subgradient Projection Algorithms for Convex Optimization,”, Journal of Optimization Theory and Applications, 147, 516-545 (2010) · Zbl 1254.90171 · doi:10.1007/s10957-010-9737-7
[29] Recht, B.; Re, C.; Wright, S.; Niu, F., “Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent,”, in Advances in Neural Information Processing Systems, 693-701 (2011)
[30] Robert, C.; Casella, G., Monte Carlo Statistical Methods (2013), Berlin: Springer Science & Business Media, Berlin
[31] Rohe, K.; Chatterjee, S.; Yu, B., “Spectral Clustering and the High-Dimensional Stochastic Blockmodel,”, The Annals of Statistics, 39, 1878-1915 (2011) · Zbl 1227.62042 · doi:10.1214/11-AOS887
[32] Salter-Townshend, M.; Murphy, T. B., “Variational Bayesian Inference for the Latent Position Cluster Model for Network Data,”, Computational Statistics & Data Analysis, 57, 661-671 (2013) · Zbl 1365.62246 · doi:10.1016/j.csda.2012.08.004
[33] Snijders, T. A.; Nowicki, K., “Estimation and Prediction for Stochastic Blockmodels for Graphs With Latent Block Structure,”, Journal of Classification,, 14, 75-100 (1997) · Zbl 0896.62063 · doi:10.1007/s003579900004
[34] Tallberg, C., “A Bayesian Approach to Modeling Stochastic Blockstructures With Covariates,”, Journal of Mathematical Sociology, 29, 1-23 (2004) · Zbl 1101.91067 · doi:10.1080/00222500590889703
[35] Traud, A. L.; Mucha, P. J.; Porter, M. A., “Social Structure of Facebook Networks,”, Physica A: Statistical Mechanics and its Applications, 391, 4165-4180 (2012) · doi:10.1016/j.physa.2011.12.021
[36] Von Luxburg, U., “Clustering Stability: An Overview,”, Foundations and Trends[textregistered] in Machine Learning, 2, 235-274 (2010) · Zbl 1191.68615
[37] Wei, G. C.; Tanner, M. A., “A Monte Carlo Implementation of the EM Algorithm and the Poor Man’s Data Augmentation Algorithms,”, Journal of the American statistical Association, 85, 699-704 (1990) · doi:10.1080/01621459.1990.10474930
[38] White, S.; Smyth, P., SDM, 5, “A Spectral Clustering Approach to Finding Communities in Graph,”, 76-84 (2005), Philadelphia, PA: SIAM, Philadelphia, PA
[39] Zhang, Y.; Duchi, J. C.; Wainwright, M. J., “Communication-Efficient Algorithms for Statistical Optimization,”, Journal of Machine Learning Research, 14, 3321-3363 (2013) · Zbl 1318.62016
[40] Zinkevich, M.; Weimer, M.; Li, L.; Smola, A. J., “Parallelized Stochastic Gradient Descent,”, in Advances in Neural Information Processing Systems, 2595-2603 (2010)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.