Impact of regularization on spectral clustering

The performance of spectral clustering can be considerably improved via regularization, as demonstrated empirically in Amini et al. [Ann. Statist. 41 (2013) 2097–2122]. Here, we provide an attempt at quantifying this improvement through theoretical analysis. Under the stochastic block model (SBM), and its extensions, previous results on spectral clustering relied on the minimum degree of the graph being sufficiently large for its good...