Scientific Computing and Numerics (SCAN) Seminar

Anil DamleCornell University
Robust and efficient multi-way spectral clustering

Monday, September 11, 2017 - 1:25pm
Gates 406

A common question arising in the study of graphs is how to partition nodes into well-connected clusters. One standard methodology, known as spectral clustering, utilizes an eigenvector embedding as a starting point for clustering the nodes. Given that embedding, we present a new algorithm for spectral clustering based on a column-pivoted QR factorization. Our method is simple to implement, direct, scalable, and requires no initial guess. We also provide theoretical justification for our algorithm and experimentally demonstrate that its performance tracks recent information theoretic bounds for exact recovery in the stochastic block model.