Combinatorics and Probability Seminar
Julia Gaudio
Northwestern
Spectral Algorithms for Community Detection
Abstract: Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms have been successfully used for graph partitioning, hidden clique recovery and graph coloring.
We analyze spectral algorithms for the problem of identifying latent community structure in large random graphs. In particular, we consider the problem of recovering community assignments exactly in the censored stochastic block model, where each edge status is revealed independently with some probability. We show that spectral algorithms achieve the information-theoretic threshold for exact recovery. In order to achieve this optimality, we encode the graph into two adjacency matrices, and then perform clustering on a weighted sum of their top eigenvalues. We show that using two matrices is necessary to achieve optimality for all but a narrow class of censored SBMs.
(Joint work with Souvik Dhara, Elchanan Mossel, and Colin Sandon)
Monday September 19, 2022 at 2:00 PM in 636 SEO