Impact of regularization on Spectral Clustering

Abstract

The performance of spectral clustering can be considerably improved via regularization, as demonstrated empirically in Amini et. al (2012). 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 performance. By examining the scenario where the regularization parameter $\tau$ is large we show that the minimum degree assumption can potentially be removed. As a special case, for an SBM with two blocks, the results require the maximum degree to be large (grow faster than $\log n$) as opposed to the minimum degree. More importantly, we show the usefulness of regularization in situations where not all nodes belong to well-defined clusters. Our results rely on a `bias-variance'-like trade-off that arises from understanding the concentration of the sample Laplacian and the eigen gap as a function of the regularization parameter. As a byproduct of our bounds, we propose a data-driven technique \textit{DKest} (standing for estimated Davis-Kahan bounds) for choosing the regularization parameter. This technique is shown to work well through simulations and on a real data set.

arXiv comment37 pages

References in corpus (6)

• Finding and evaluating community structure in networks
• Stochastic blockmodels and community structure in networks
• Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
• Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges
• Clustering with Spectral Norm and the k-means Algorithm
• Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap

Cited by in corpus (12)

• Rate-optimal graphon estimation
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• A Survey on Theoretical Advances of Community Detection in Networks
• Detecting Overlapping Communities in Networks Using Spectral Methods
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Co-clustering for directed graphs: the Stochastic co-Blockmodel and spectral algorithm Di-Sim
• Community Detection in Degree-Corrected Block Models
• Community detection with nodal information
• Revisiting the Bethe-Hessian: Improved Community Detection in Sparse Heterogeneous Graphs
• Robust Spectral Detection of Global Structures in the Data by Learning a Regularization
• Random reversible Markov matrices with tunable extremal eigenvalues
• Linear-Sample Learning of Low-Rank Distributions