Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
Spectral clustering is a fast and popular algorithm for finding clusters in networks. Recently, Chaudhuri et al. [1] and Amini et al. [2] proposed inspired variations on the algorithm that artificially inflate the node degrees for improved statistical performance. The current paper extends the previous statistical estimation results to the more canonical spectral clustering algorithm in a way that removes any assumption on the minimum degree and provides guidance on the choice of the tuning parameter. Moreover, our results show how the "star shape" in the eigenvectors-a common feature of empirical networks-can be explained by the Degree-Corrected Stochastic Blockmodel and the Extended Planted Partition model, two statistical models that allow for highly heterogeneous degrees. Throughout, the paper characterizes and justifies several of the variations of the spectral clustering algorithm in terms of these models.
The authors present a theoretical analysis of spectral 
      clustering in the degree corrected stochastic block model. Following 
      earlier work of Chaudhuri et. al. they analyze spectral clustering with 
      the regularized normalized Laplacian, first showing that the population 
      Laplacian reflects the correct block structure, and then showing that the 
      "noisy" graph Laplacian has a similar spectrum. Finally, they bound the 
      number of mis-clustered nodes. They also consider an additional step of 
      normalizing rows of the spectral embedding and show that the resulting 
      bounds are related to the statistical leverage scores. Overall the 
      paper is well written (a few typos are pointed out at the end), addresses 
      an interesting problem and provides a much simpler (albeit weaker) 
      analysis as compared to the earlier work of Chaudhuri et. al. Here 
      are some issues that the authors should clarify: 1. I don't quite 
      understand why the passage before equation (6) is an appropriate 
      definition of mis-clustered nodes. There is already a natural definition 
      from the ground truth clustering. It would help if the authors clarified 
      the relation between the k-means 0/1 error and the set \mathcal{U}. Why 
      are the nodes in \mathcal{U} the only ones on which k-means (which does 
      not have access to population centroids, say with random initialization) 
      makes errors? If not, it would help avoid confusion to not use the term 
      "mis-clustering rate". 2. There should be a more detailed 
      comparison to the earlier work of Chaudhuri et. al. In particular, they 
      provide results on the parameters of the DC-SBM for which there are no 
      errors made by their clustering algorithm and complement this with lower 
      bounds. At least for the case of the SBM, rather than assuming (p-r) is a 
      constant, a proper comparison to known results from McSherry/Chaudhuri et. 
      al. should be made. 3. The role of normalization (of the 
      embedding) is still not clear to me. While the figure shows a case where 
      it seems to help in practice, it would help to clarify its role in the 
      theory. Are the rates worse? If possible, the authors should compare the 
      rates with and without the normalization, and if not they should clarify 
      the reason for normalization. 4. Finally, in the experiments 
      section - you report 50% improvement after dropping 10% of the nodes. 
      However, although the algorithm you propose clusters *all* nodes you only 
      report accuracy on the retained nodes. Does the accuracy on the full set 
      improve at all? Minor typos: 1. Two statistical model 
      --> models 2. Line 59 -- we study **an** 3. 102 -- emphasis 
      --> emphasize 4. 243 and 244 -- centroid --> 
      centroids