Impact of regularization on spectral clustering
From MaRDI portal
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 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 ) 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 extit{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.
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.
Recommendations
- Consistency of regularized spectral clustering
- Analysis of spectral clustering algorithms for community detection: the general bipartite setting
- Consistency of spectral clustering
- Role of normalization in spectral clustering for stochastic blockmodels
- A review on spectral clustering and stochastic block models
Cites work
- A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
- A nonparametric view of network models and Newman–Girvan and other modularities
- Community structure in social and biological networks
- Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown
- scientific article; zbMATH DE number 967931 (Why is no real title available?)
- Impact of regularization on spectral clustering
- Improved Cheeger's inequality, analysis of spectral partitioning algorithms through higher order spectral gap
- Improved spectral-norm bounds for clustering
- Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
- Matrix concentration inequalities via the method of exchangeable pairs
- On the convergence to equilibrium of Kac's random walk on matrices
- Pseudo-likelihood methods for community detection in large sparse networks
- Spectral clustering and the high-dimensional stochastic blockmodel
Cited in
(45)- Community detection by \(L_{0}\)-penalized graph Laplacian
- Estimating a network from multiple noisy realizations
- On semidefinite relaxations for the block model
- Limit theorems for eigenvectors of the normalized Laplacian for random graphs
- Fusing data depth with complex networks: community detection with prior information
- Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
- A review on spectral clustering and stochastic block models
- Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator
- Clustering with \(r\)-regular graphs
- Role of normalization in spectral clustering for stochastic blockmodels
- Impact of regularization on spectral clustering
- Analysis of spectral clustering algorithms for community detection: the general bipartite setting
- Change point estimation in a dynamic stochastic block model
- Ranking and synchronization from pairwise measurements via SVD
- Determining the number of communities in degree-corrected stochastic block models
- Enhanced equivalence projective simulation: a framework for modeling formation of stimulus equivalence classes
- Graph powering and spectral robustness
- Detecting overlapping communities in networks using spectral methods
- Community Detection in Sparse Networks Using the Symmetrized Laplacian Inverse Matrix (SLIM)
- scientific article; zbMATH DE number 7626708 (Why is no real title available?)
- scientific article; zbMATH DE number 7626732 (Why is no real title available?)
- scientific article; zbMATH DE number 7626779 (Why is no real title available?)
- Randomized Spectral Clustering in Large-Scale Stochastic Block Models
- scientific article; zbMATH DE number 7307464 (Why is no real title available?)
- Hierarchical Community Detection by Recursive Partitioning
- Modularity Maximization for Graphons
- Large volatility matrix analysis using global and national factor models
- Fast Network Community Detection With Profile-Pseudo Likelihood Methods
- Estimating mixed-memberships using the symmetric Laplacian inverse matrix
- Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
- Analyzing the impact of regularization on REMSE
- Community detection in complex networks: from statistical foundations to data science applications
- A Time-Varying Network for Cryptocurrencies
- PCABM: Pairwise Covariates-Adjusted Block Model for Community Detection
- Applications of dual regularized Laplacian matrix for community detection
- Spectral clustering in the dynamic stochastic block model
- Overlapping community detection in weighted networks
- Spectral clustering on aggregated multilayer networks with covariates
- Network-adjusted covariates for community detection
- Detecting small clusters in the stochastic block model
- Adaptive subsampling spectral clustering based on second-order neighbour relationships for sparse networks
- Consistency of Lloyd's algorithm under perturbations
- Latent class analysis by regularized spectral clustering
- Regularized spectral clustering in overlapping networks
- Community detection in sparse networks via Grothendieck's inequality
This page was built for publication: Impact of regularization on spectral clustering
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q309744)
