Fast and Guaranteed Learning of Overlapping Communities via Tensor Decomposition

SHARE:

Event Speaker: 

Anima Anandkumar , U.C.Irvine

Event Location: 

36-428

Event Date/Time: 

Monday, October 28, 2013 - 2:30pm

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.