Seminars

View all Seminars  |  Download ICal for this event

Detecting Hidden Communities by Power Iterations with Connections to Vanilla Spectral Algorithms

Series: Bangalore Theory Seminars

Speaker: Chandrasekhar Mukherjee, University of Southern California

Date/Time: Nov 17 11:00:00

Location: Online Talk (See Teams link below)

Abstract:
Community detection in the stochastic block model is one of the central problems of graph clustering. Since its introduction by Holland, Laskey, and Leinhardt (Social Networks, 1983), many subsequent papers have made great strides in solving and understanding this model. However, despite the long history of study, there are still unsolved challenges. In this direction, two primary open problems are: how to recover large clusters in the presence of small clusters (we call it small cluster barrier), and how to analyze simple and practical spectral algorithms (we call them vanilla spectral algorithms), especially when the number of communities is large.

In this paper, we use a power iteration approach to make progress in both these directions.

We design the first parameter-free community recovery algorithm that recovers large clusters in the presence of small clusters. Our algorithm only compares the rows of the powered adjacency matrix and has a recovery guarantee poly-logarithmically close to that of the state-of-the-art algorithms in this problem that require knowledge of model parameters.

Then based on a connection between the powered adjacency matrix and eigenvectors, we provide a vanilla spectral algorithm in the balanced case when the number of communities is large. This answers an open question by Van Vu (Combinatorics Probability and Computing, 2018) in the balanced case. Our methods also partially solve technical barriers discussed by Abbe, Fan, Wang, and Zhong (Annals of Statistics, 2020).

This talk is based on joint work with Jiapeng Zhang, and will appear in SODA 2024.

Speaker Bio:
Microsoft Teams link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d We are grateful to the Kirani family for generously supporting the theory seminar series Hosts: Rameesh Paul, Rahul Madhavan, Rachana Gusain, KVN Sreenivas