Impact of regularization on spectral clustering (Q309744)

This paper reviews the regularized spectral clustering (RSC) procedure proposed in [\textit{A. A. Amini} et al., Ann. Stat. 41, No. 4, 2097--2122 (2013; Zbl 1277.62166)] and the stochastic block model (SBM) introduced in [\textit{P. W. Holland} et al., ``Stochastic blockmodels: first steps'', Soc. Netw. 5, 109--137 (1983; \url{doi:10.1016/0378-8733(83)90021-7})]. It focuses on the SBM and an extension of this model, and attempts to understand regularization for SBM. It provides a theoretical justification for the regularization in the RSC procedure. It is shown why choosing a large regularization parameter can lead to good results. It also partly explains empirical findings in [Amini et al., loc. cit.] showing that the performance of regularized spectral clustering becomes insensitive for larger values of regularization parameters. A data dependent method \textit{DKest} is proposed for choosing the regularization parameter. This technique is shown to work well through simulations and on a real data set.