A Tensor Spectral Approach to Learning Mixed Membership Community Models

Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham Kakade
Proceedings of the 26th Annual Conference on Learning Theory, PMLR 30:867-881, 2013.

Abstract

Modeling community formation and detecting hidden communities in networks is a well studied problem. However, theoretical analysis of community detection has been mostly limited to models with non-overlapping communities such as the stochastic block model. In this paper, we remove this restriction, and consider a family of probabilistic network models with overlapping communities, termed as the mixed membership Dirichlet model, first introduced in Aioroldi et. al (2008). This model allows for nodes to have fractional memberships in multiple communities and assumes that the community memberships are drawn from a Dirichlet distribution. 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 algebra 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. Additionally, our results match the best known scaling requirements in the special case of the stochastic block model.

Cite this Paper

BibTeX
@InProceedings{pmlr-v30-Anandkumar13, title = {A Tensor Spectral Approach to Learning Mixed Membership Community Models}, author = {Anandkumar, Animashree and Ge, Rong and Hsu, Daniel and Kakade, Sham}, booktitle = {Proceedings of the 26th Annual Conference on Learning Theory}, pages = {867--881}, year = {2013}, editor = {Shalev-Shwartz, Shai and Steinwart, Ingo}, volume = {30}, series = {Proceedings of Machine Learning Research}, address = {Princeton, NJ, USA}, month = {12--14 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v30/Anandkumar13.pdf}, url = {https://proceedings.mlr.press/v30/Anandkumar13.html}, abstract = {Modeling community formation and detecting hidden communities in networks is a well studied problem. However, theoretical analysis of community detection has been mostly limited to models with non-overlapping communities such as the stochastic block model. In this paper, we remove this restriction, and consider a family of probabilistic network models with overlapping communities, termed as the mixed membership Dirichlet model, first introduced in Aioroldi et. al (2008). This model allows for nodes to have fractional memberships in multiple communities and assumes that the community memberships are drawn from a Dirichlet distribution. 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 algebra 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. Additionally, our results match the best known scaling requirements in the special case of the stochastic block model.} }
Endnote
%0 Conference Paper %T A Tensor Spectral Approach to Learning Mixed Membership Community Models %A Animashree Anandkumar %A Rong Ge %A Daniel Hsu %A Sham Kakade %B Proceedings of the 26th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2013 %E Shai Shalev-Shwartz %E Ingo Steinwart %F pmlr-v30-Anandkumar13 %I PMLR %P 867--881 %U https://proceedings.mlr.press/v30/Anandkumar13.html %V 30 %X Modeling community formation and detecting hidden communities in networks is a well studied problem. However, theoretical analysis of community detection has been mostly limited to models with non-overlapping communities such as the stochastic block model. In this paper, we remove this restriction, and consider a family of probabilistic network models with overlapping communities, termed as the mixed membership Dirichlet model, first introduced in Aioroldi et. al (2008). This model allows for nodes to have fractional memberships in multiple communities and assumes that the community memberships are drawn from a Dirichlet distribution. 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 algebra 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. Additionally, our results match the best known scaling requirements in the special case of the stochastic block model.
RIS
TY - CPAPER TI - A Tensor Spectral Approach to Learning Mixed Membership Community Models AU - Animashree Anandkumar AU - Rong Ge AU - Daniel Hsu AU - Sham Kakade BT - Proceedings of the 26th Annual Conference on Learning Theory DA - 2013/06/13 ED - Shai Shalev-Shwartz ED - Ingo Steinwart ID - pmlr-v30-Anandkumar13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 30 SP - 867 EP - 881 L1 - http://proceedings.mlr.press/v30/Anandkumar13.pdf UR - https://proceedings.mlr.press/v30/Anandkumar13.html AB - Modeling community formation and detecting hidden communities in networks is a well studied problem. However, theoretical analysis of community detection has been mostly limited to models with non-overlapping communities such as the stochastic block model. In this paper, we remove this restriction, and consider a family of probabilistic network models with overlapping communities, termed as the mixed membership Dirichlet model, first introduced in Aioroldi et. al (2008). This model allows for nodes to have fractional memberships in multiple communities and assumes that the community memberships are drawn from a Dirichlet distribution. 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 algebra 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. Additionally, our results match the best known scaling requirements in the special case of the stochastic block model. ER -
APA
Anandkumar, A., Ge, R., Hsu, D. & Kakade, S.. (2013). A Tensor Spectral Approach to Learning Mixed Membership Community Models. Proceedings of the 26th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 30:867-881 Available from https://proceedings.mlr.press/v30/Anandkumar13.html.

Related Material