  We present a new algorithm for spectral clustering based on a column-pivoted
QR factorization that may be directly used for cluster assignment or to provide
an initial guess for k-means. Our algorithm is simple to implement, direct, and
requires no initial guess. Furthermore, it scales linearly in the number of
nodes of the graph and a randomized variant provides significant computational
gains. Provided the subspace spanned by the eigenvectors used for clustering
contains a basis that resembles the set of indicator vectors on the clusters,
we prove that both our deterministic and randomized algorithms recover a basis
close to the indicators in Frobenius norm. We also experimentally demonstrate
that the performance of our algorithm tracks recent information theoretic
bounds for exact recovery in the stochastic block model. Finally, we explore
the performance of our algorithm when applied to a real world graph.
