A tensor approach to learning mixed membership community models

By Anima Anandkumar, Rong Ge, Daniel J. Hsu, Sham M. Kakade. 2013

160 citations recorded by the source corpus.

Community detection is the task of detecting hidden communities from observed interactions. Guaranteed community detection has so far been mostly limited to models with non-overlapping communities such as the stochastic block model. In this paper, we remove this restriction, and provide guaranteed community detection for a family of probabilistic network models with overlapping communities, termed as the mixed membership Dirichlet model, first introduced by Airoldi et al. This model allows for nodes to have fractional memberships in multiple communities and assumes that the community memberships are drawn from a Dirichlet distribution. Moreover, it contains the stochastic block model as a special case. We propose a unified approach to learning these models via a tensor spectral decomposition method. Our estimator is based on low-order moment tensor of the observed network, consisting of 3-star counts. Our learning method is fast and is based on simple linear algebraic operations, e.g. singular value decomposition and tensor power iterations. We provide guaranteed recovery of community memberships and model parameters and present a careful finite sample analysis of our learning method. As an important special case, our results match the best known scaling requirements for the (homogeneous) stochastic block model.

Subfields: Computational Mathematics, Statistical and Nonlinear Physics, Transportation

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

In Statistical and Nonlinear Physics

In Transportation

Citations in the corpus

Polynomial-Time Tensor Decompositions with Sum-of-Squares (2016, background): “These algorithms lead to the best known provable guarantees for a wide range of unsupervised learning problems [8]– [11], including learning mixtures of Gaussians [12], Latent Dirichlet topic modeling [13], and dictionary learning [14].”
Consistency of spectral clustering in stochastic block models (2013, methodology): “…2004), likelihood methods (Bickel & Chen, 2009; Choi et al., 2012; Zhao et al., 2012; Amini et al., 2012; Celisse et al., 2012), method of moments (Anandkumar et al., 2013), belief propagation (Decelle et al., 2011), convex optimization (Chen et al., 2012), spectral clustering (Rohe et al., 2011;…”
A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning (2021, background): “spectral clustering [15], [16] and statistical inference [17], [18].”