BEGIN:VCALENDAR VERSION:2.0 PRODID:-//Talks.cam//talks.cam.ac.uk// X-WR-CALNAME:Talks.cam BEGIN:VEVENT SUMMARY:Fast and Guaranteed Learning of Overlapping Communities via Tensor Methods - Anima Anandkumar\, University of California Irvine DTSTART:20130819T100000Z DTEND:20130819T110000Z UID:TALK46572@talks.cam.ac.uk CONTACT:Microsoft Research Cambridge Talks Admins DESCRIPTION:A community refers to a group of related nodes in a network. F or instance\, in a social network\, it can represent individuals with shar ed interests or beliefs\, and in a gene network\, it can represent genes w ith common regulatory mechanisms\, and so on. Detecting hidden communitie s in observed networks is an important problem. However\, most previous ap proaches assume non-overlapping communities where a node can belong to at most one community. In contrast\, we provide a guaranteed approach for de tecting overlapping communities\, when the network is generated from a cla ss of probabilistic mixed membership block models. Our approach is based on fast and scalable tensor decompositions and linear algebraic operation s. We provide guaranteed recovery of community memberships and establish a finite sample analysis of our algorithm. Our theoretical results match the best known scaling requirements in the special case of the popular st ochastic block model (which has non-overlapping communities). \n\nWe have deployed the algorithm on GPUs\, and our code design involves a careful optimization of GPU-CPU storage and communication. Our method is extremely fast and accurate. For instance\, on a real dataset consisting of yelp re views\, with about 40\,000 nodes\, and about 500 hidden communities\, our method takes under 30 minutes to run to convergence\, and recovers communi ties with extremely high accuracy (with error of about 6%). Thus\, our app roach is fast\, scalable and accurate for detecting overlapping communitie s.\n LOCATION:Microsoft Research Ltd\, 21 Station Road\, Cambridge\, CB1 2FB END:VEVENT END:VCALENDAR