Fast and Guaranteed Learning of Overlapping Communities via Tensor Decomposition

Speaker: Anima Anandkumar , U.C.Irvine

Date: Monday, October 28, 2013

Time: 2:30 PM to 3:30 PM Note: all times are in the Eastern Time Zone

Refreshments: 2:15 PM

Public: Yes

Location: 36-428

Event Type:

Room Description:

Host: Bill Freeman, Advanced Network Architecture group, CSAIL, MIT

Contact: Francis Doughty, 253-4602,

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to:,

Reminder Subject: TALK: Fast and Guaranteed Learning of Overlapping Communities via Tensor Decomposition

Detecting hidden communities in networks is an important
problem.  Most previous approaches assume non-overlapping communities
where a node can belong to at most one community.  In contrast, we
provide a guaranteed approach for detecting overlapping communities
when the network is generated from a class of probabilistic mixed
membership models.  Our approach is based on the method of moments,
and specifically, we consider counts of simple subgraphs such as
stars. We establish that the star subgraph count tensor has a low rank
CP tensor decomposition. Our community learning method thus consists
of fast and scalable  tensor decompositions and linear algebraic
operations. It is guaranteed to correctly recover the mixed-membership
communities, and for the special case of the stochastic block model
(where the communities are non-overlapping), these sufficient
conditions turn out to be tight and match the lower bounds (up to
poly-log factors). The tensor decomposition approach is also
applicable for learning a wide class of latent variable models such as
topic models, Gaussian mixtures and hidden Markov models. We have
tested the algorithm on many real-world social network  datasets, e.g.
from Facebook, Yelp and DBLP. The method is extremely fast and
accurate   compared to the state-of-art stochastic variational method
for learning mixed membership models.

Bio: Anima Anandkumar is  a faculty at the EECS Dept. at U.C.Irvine.
Her research interests are in the area of large-scale machine learning
and high-dimensional statistics.  She received her B.Tech in
Electrical Engineering from IIT Madras  and her PhD from Cornell
University. She has been a visiting faculty  at Microsoft Research New
England and  a postdoctoral researcher at the Stochastic Systems Group
at MIT. She is the recipient of the Microsoft Faculty Fellowship,  ARO
Young Investigator Award, NSF CAREER Award, IBM Fran Allen PhD
fellowship, and paper awards from the ACM SIGMETRICS and IEEE Signal
Processing societies.

Research Areas:

Impact Areas:

This event is not part of a series.

Created by Francis Doughty Email at Monday, September 30, 2013 at 3:14 PM.