Understanding Regularized Spectral Clustering via Graph Conductance
This paper uses the relationship between graph conductance and spectral clustering to study (i) the failures of spectral clustering and (ii) the benefits of regularization. The explanation is simple. Sparse and stochastic graphs create several "dangling sets", or small trees that are connected to the core of the graph by only one edge. Graph conductance is sensitive to these noisy dangling sets and spectral clustering inherits this sensitivity. The second part of the paper starts from a previously proposed form of regularized spectral clustering and shows that it is related to the graph conductance on a "regularized graph". When graph conductance is computed on the regularized graph, we call it CoreCut. Based upon previous arguments that relate graph conductance to spectral clustering (e.g. Cheeger inequality), minimizing CoreCut relaxes to regularized spectral clustering. Simple inspection of CoreCut reveals why it is less sensitive to dangling sets. Together, these results show that unbalanced partitions from spectral clustering can be understood as overfitting to noise in the periphery of a sparse and stochastic graph. Regularization fixes this overfitting. In addition to this statistical benefit, these results also demonstrate how regularization can improve the computational speed of spectral clustering. We provide simulations and data examples to illustrate these results.
I am familiar with spectral clustering and its relation to graph conductance, but do not know much about the references on regularized SC, such as [17, 9, 11]. So my assessment on regularized SC is based on what I learnt from this work.  Here are my comments: + The paper provides a good understanding of regularized-SC for sparse-graph partitioning based on solid theoretical reasoning. The extensive experimental results also well justify the statements. As a large fraction of social networks are sparse, so the assumptions are acceptable.  + The paper is written well and easy to follow. All theoretical results are presented well and show insight on why regularized-SC is important (Thm 4.3) and when spectral SC can work well(Corollary 4.7) - The main concern is about the usage of regularized-SC in practice. I agree that the when using spectral clustering without regularization, the first-round partition may yield a huge component and several small parts like the dangling sets mentioned in this work. However, in practice, we can easily do another round of graph partition by focusing on the obtained huge component to refine the clustering results. Regularized-SC may not require such additional effort but it introduces a parameter \tau whose tuning is not easy.   Two suggestions: -The format of 2-way-partition regularized-SC seems equivalent to global Pagerank where \tau is to control the probability of random jump. Pagerank algorithm is widely used everywhere. It would better to give some discussion on this point and review related references. Some work on Pagerank also shows connection with graph conductance such as Andersen et al.  Local graph partitioning using pagerank vectors  [FOCS2006]    - Since sparsity comes from the real social networks, it may be better to provide some real evidence on the number of dangling sets in social networks. Moreover, as shown in the appendix, Thm 3.4 requires another assumption which should be added within the statement in the main text.     Some minor typo: Line 29: sigular  -> singular Line 31: tau -> \tau Line 75:covolutional -> convolutional