jmlr jmlr2008 jmlr2008-61 jmlr2008-61-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Edoardo M. Airoldi, David M. Blei, Stephen E. Fienberg, Eric P. Xing
Abstract: Consider data consisting of pairwise measurements, such as presence or absence of links between pairs of objects. These data arise, for instance, in the analysis of protein interactions and gene regulatory networks, collections of author-recipient email, and social networks. Analyzing pairwise measurements with probabilistic models requires special assumptions, since the usual independence or exchangeability assumptions no longer hold. Here we introduce a class of variance allocation models for pairwise measurements: mixed membership stochastic blockmodels. These models combine global parameters that instantiate dense patches of connectivity (blockmodel) with local parameters that instantiate node-specific variability in the connections (mixed membership). We develop a general variational inference algorithm for fast approximate posterior inference. We demonstrate the advantages of mixed membership stochastic blockmodels with applications to social networks and protein interaction networks. Keywords: hierarchical Bayes, latent variables, mean-field approximation, statistical network analysis, social networks, protein interaction networks
E. M. Airoldi. Getting started in probabilistic graphical models. PLoS Computational Biology, 3 (12):e252, 2007. E. M. Airoldi, D. M. Blei, E. P. Xing, and S. E. Fienberg. A latent mixed-membership model for relational data. In ACM SIGKDD Workshop on Link Discovery: Issues, Approaches and Applications, 2005. E. M. Airoldi, S. E. Fienberg, and E. P. Xing. Mixed membership analysis of expression studies— attribute data. Manuscript, 2007. URL http://arxiv.org/abs/0711.2520/. B. Alberts, A. Johnson, J. Lewis, M. Raff, K. Roberts, and P. Walter. Molecular Biology of the Cell. Garland, 4th edition, 2002. M. Ashburner, C. A. Ball, J. A. Blake, D. Botstein, H. Butler, J. M. Cherry, A. P. Davis, K. Dolinski, S. S. Dwight, J. T. Eppig, M. A. Harris, D. P. Hill, L. Issel-Tarver, A. Kasarskis, S. Lewis, J. C. Matese, J. E. Richardson, M. Ringwald, G. M. Rubinand, and G. Sherlock. Gene ontology: Tool for the unification of biology. The gene ontology consortium. Nature Genetics, 25(1):25–29, 2000. M. J. Beal and Z. Ghahramani. The variational Bayesian EM algorithm for incomplete data: With application to scoring graphical model structures. In J. M. Bernardo, M. J. Bayarri, J. O. Berger, A. P. Dawid, D. Heckerman, A. F. M. Smith, and M. West, editors, Bayesian Statistics, volume 7, pages 453–464. Oxford University Press, 2003. L. Berkman, B. H. Singer, and K. Manton. Black/white differences in health status and mortality among the elderly. Demography, 26(4):661–678, 1989. C. Bishop, D. Spiegelhalter, and J. Winn. VIBES: A variational inference engine for Bayesian networks. In S. Becker, S. Thrun, and K. Obermayer, editors, Advances in Neural Information Processing Systems 15, pages 777–784. MIT Press, Cambridge, MA, 2003. D. M. Blei, A. Ng, and M. I. Jordan. Latent Dirichlet allocation. Journal of Machine Learning Research, 3:993–1022, 2003. R. T. Bradley. Charisma and Social Structure. Paragon House, 1987. M. Braun and J. McAuliffe. Variational inference for large-scale models of discrete choice. Manuscript, 2007. URL http://arxiv.org/abs/0712.2526/. R. L. Breiger, S. A. Boorman, and P. Arabie. An algorithm for clustering relational data with applications to social network analysis and comparison to multidimensional scaling. Journal of Mathematical Psychology, 12:328–383, 1975. W. L. Buntine and A. Jakulin. Discrete components analysis. In C. Saunders, M. Grobelnik, S. Gunn, and J. Shawe-Taylor, editors, Subspace, Latent Structure and Feature Selection Techniques. Springer-Verlag, 2006. URL http://arxiv.org/abs/math.ST/0604410/. G. B. Davis and K. M. Carley. Clearing the FOG: Fuzzy, overlapping groups for social networks. Manuscript, 2006. 2011 A IROLDI , B LEI , F IENBERG AND X ING A. Dempster, N. Laird, and D. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, Series B, 39:1–38, 1977. P. Doreian, V. Batagelj, and A. Ferligoj. Generalized Blockmodeling. Cambridge University Press, 2004. P. Doreian, V. Batagelj, and A. Ferligoj. Discussion of “Model-based clustering for social networks”. Journal of the Royal Statistical Society, Series A, 170, 2007. E. A. Erosheva. Grade of Membership and Latent Structure Models with Application to Disability Survey Data. PhD thesis, Carnegie Mellon University, Department of Statistics, 2002. E. A. Erosheva and S. E. Fienberg. Bayesian mixed membership models for soft clustering and classification. In C. Weihs and W. Gaul, editors, Classification—The Ubiquitous Challenge, pages 11–26. Springer-Verlag, 2005. M. Escobar and M. West. Bayesian density estimation and inference using mixtures. Journal of the American Statistical Association, 90:577–588, 1995. S. E. Fienberg, M. M. Meyer, and S. Wasserman. Statistical analysis of multiple sociometric relations. Journal of the American Statistical Association, 80:51–67, 1985. O. Frank and D. Strauss. Markov graphs. Journal of the American Statistical Association, 81: 832–842, 1986. A. C. Gavin, M. Bosche, R. Krause, P. Grandi, M. Marzioch, A. Bauer, J. Schultz, and et. al. Functional organization of the yeast proteome by systematic analysis of protein complexes. Nature, 415:141–147, 2002. T. L. Griffiths and M. Steyvers. Finding scientific topics. Proceedings of the National Academy of Sciences, 101(Suppl. 1):5228–5235, 2004. M. S. Handcock, A. E. Raftery, and J. M. Tantrum. Model-based clustering for social networks. Journal of the Royal Statistical Society, Series A, 170:1–22, 2007. K. M. Harris, F. Florey, J. Tabor, P. S. Bearman, J. Jones, and R. J. Udry. The national longitudinal study of adolescent health: research design. Technical report, Caorlina Population Center, University of North Carolina, Chapel Hill, 2003. Y. Ho, A. Gruhler, A. Heilbut, G. D. Bader, L. Moore, S. L. Adams, A. Millar, P. Taylor, K. Bennett, and K. Boutilier et. al. Systematic identification of protein complexes in saccharomyces cerevisiae by mass spectrometry. Nature, 415:180–183, 2002. P. D. Hoff, A. E. Raftery, and M. S. Handcock. Latent space approaches to social network analysis. Journal of the American Statistical Association, 97:1090–1098, 2002. P. W. Holland and S. Leinhardt. Local structure in social networks. In D. Heise, editor, Sociological Methodology, pages 1–45. Jossey-Bass, 1975. M. Jordan, Z. Ghahramani, T. Jaakkola, and L. Saul. Introduction to variational methods for graphical models. Machine Learning, 37:183–233, 1999. 2012 M IXED M EMBERSHIP S TOCHASTIC B LOCKMODELS C. Joutard, E. M. Airoldi, S. E. Fienberg, and T. M. Love. Discovery of latent patterns with hierarchical bayesian mixed-membership models and the issue of model choice. In Data Mining Patterns, New Methods and Applications, 2007. Forthcoming. C. Kemp, T. L. Griffiths, and J. B. Tenenbaum. Discovering latent classes in relational data. Technical Report AI Memo 2004-019, MIT, 2004. C. Kemp, J. B. Tenenbaum, T. L. Griffiths, T. Yamada, and N. Ueda. Learning systems of concepts with an infinite relational model. In Proceedings of the 21st National Conference on Artificial Intelligence, 2006. N. J. Krogan, G. Cagney, H. Yu, G. Zhong, X. Guo, A. Ignatchenko, J. Li, S. Pu, N. Datta, A. P. Tikuisis, T. Punna, J. M. Peregrin-Alvarez, M. Shales, X. Zhang, M. Davey, M. D. Robinson, A. Paccanaro, J. E. Bray, A. Sheung, B. Beattie, D. P. Richards, V. Canadien, A. Lalev, F. Mena, P. Wong, A. Starostine, M. M. Canete, J. Vlasblom, S. Wu, C. Orsi, S. R. Collins, S. Chandran, R. Haw, J. J. Rilstone, K. Gandi, N. J. Thompson, G. Musso, P. St Onge, S. Ghanny, M. H. Y. Lam, G. Butland, A. M. Altaf-Ul, S. Kanaya, A. Shilatifard, E. O’Shea, J. S. Weissman, C. J. Ingles, T. R. Hughes, J. Parkinson, M. Gerstein, S. J. Wodak, A. Emili, and J. F. Greenblatt. Global landscape of protein complexes in the yeast Saccharomyces Cerevisiae. Nature, 440 (7084):637–643, 2006. F.-F. Li and P. Perona. A Bayesian hierarchical model for learning natural scene categories. IEEE Computer Vision and Pattern Recognition, 2005. F. Lorrain and H. C. White. Structural equivalence of individuals in social networks. Journal of Mathematical Sociology, 1:49–80, 1971. A. McCallum, X. Wang, and N. Mohanty. Joint group and topic discovery from relations and text. In Statistical Network Analysis: Models, Issues and New Directions, Lecture Notes in Computer Science. Springer-Verlag, 2007. H. W. Mewes, C. Amid, R. Arnold, D. Frishman, U. Guldener, and et. al. Mips: analysis and annotation of proteins from whole genomes. Nucleic Acids Research, 32:D41–44, 2004. T. Minka. Estimating a Dirichlet distribution. Manuscript, 2003. T. Minka and J. Lafferty. Expectation-propagation for the generative aspect model. In Uncertainty in Artificial Intelligence, 2002. C. L. Myers, D. A. Barret, M. A. Hibbs, C. Huttenhower, and O. G. Troyanskaya. Finding function: An evaluation framework for functional genomics. BMC Genomics, 7(187), 2006. J. K. Pritchard, M. Stephens, N. A. Rosenberg, and P. Donnelly. Association mapping in structured populations. American Journal of Human Genetics, 67:170–181, 2000. F. S. Sampson. A Novitiate in a Period of Change: An Experimental and Case Study of Social Relationships. PhD thesis, Cornell University, 1968. Mark J. Schervish. Theory of Statistics. Springer, 1995. 2013 A IROLDI , B LEI , F IENBERG AND X ING T. A. B. Snijders. Markov chain monte carlo estimation of exponential random graph models. Journal of Social Structure, 2002. T. A. B. Snijders and K. Nowicki. Estimation and prediction for stochastic blockmodels for graphs with latent block structure. Journal of Classification, 14:75–100, 1997. B. Taskar, M. F. Wong, P. Abbeel, and D. Koller. Link prediction in relational data. In Neural Information Processing Systems 15, 2003. Y. W. Teh, M. I. Jordan, M. J. Beal, and D. M. Blei. Hierarchical Dirichlet processes. Journal of the American Statistical Association, 101(476):1566–1581, 2006. Y. W. Teh, D. Newman, and M. Welling. A collapsed variational bayesian inference algorithm for latent dirichlet allocation. In Advances in Neural Information Processing Systems, volume 19, 2007. R. J. Udry. The national longitudinal study of adolescent health: (add health) waves i and ii, 1994– 1996; wave iii 2001–2002. Technical report, Caorlina Population Center, University of North Carolina, Chapel Hill, 2003. C. T. Volinsky and A. E. Raftery. Bayesian information criterion for censored survival models. Biometrics, 56:256–262, 2000. M. J. Wainwright and M. I. Jordan. Graphical models, exponential families and variational inference. Technical Report 649, Department of Statistics, University of California, Berkeley, 2003. Y. J. Wang and G. Y. Wong. Stochastic blockmodels for directed graphs. Journal of the American Statistical Association, 82:8–19, 1987. S. Wasserman and P. Pattison. Logit models and logistic regression for social networks: I. an introduction to markov graphs and p∗ . Psychometrika, 61:401–425, 1996. E. P. Xing, M. I. Jordan, and S. Russell. A generalized mean field algorithm for variational inference in exponential families. In Uncertainty in Artificial Intelligence, volume 19, 2003. Z. Xu, V. Tresp, K. Yu, and H.-P. Kriegel. Infinite hidden relational models. In Uncertainty in Artificial Intelligence, 2006. 2014