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.
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
- scientific article; zbMATH DE number 967931 (Why is no real title available?)
- 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
- 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
(37)- Community detection by \(L_{0}\)-penalized graph Laplacian
- Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
- Limit theorems for eigenvectors of the normalized Laplacian for random graphs
- Fusing data depth with complex networks: community detection with prior information
- scientific article; zbMATH DE number 7255138 (Why is no real title available?)
- scientific article; zbMATH DE number 7370586 (Why is no real title available?)
- scientific article; zbMATH DE number 7626732 (Why is no real title available?)
- Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
- Fast Network Community Detection With Profile-Pseudo Likelihood Methods
- Analyzing the impact of regularization on REMSE
- scientific article; zbMATH DE number 7626708 (Why is no real title available?)
- Clustering with \(r\)-regular graphs
- Community detection in complex networks: from statistical foundations to data science applications
- Community Detection in Sparse Networks Using the Symmetrized Laplacian Inverse Matrix (SLIM)
- Enhanced equivalence projective simulation: a framework for modeling formation of stimulus equivalence classes
- Large volatility matrix analysis using global and national factor models
- Modularity Maximization for Graphons
- Estimating mixed-memberships using the symmetric Laplacian inverse matrix
- scientific article; zbMATH DE number 7370536 (Why is no real title available?)
- scientific article; zbMATH DE number 7626779 (Why is no real title available?)
- Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator
- On semidefinite relaxations for the block model
- Graph powering and spectral robustness
- Spectral clustering in the dynamic stochastic block model
- Analysis of spectral clustering algorithms for community detection: the general bipartite setting
- Impact of regularization on spectral clustering
- A Time-Varying Network for Cryptocurrencies
- Role of normalization in spectral clustering for stochastic blockmodels
- PCABM: Pairwise Covariates-Adjusted Block Model for Community Detection
- Community detection in sparse networks via Grothendieck's inequality
- scientific article; zbMATH DE number 7307464 (Why is no real title available?)
- Detecting overlapping communities in networks using spectral methods
- A review on spectral clustering and stochastic block models
- Applications of dual regularized Laplacian matrix for community detection
- Hierarchical Community Detection by Recursive Partitioning
- Randomized Spectral Clustering in Large-Scale Stochastic Block Models
- Estimating a network from multiple noisy realizations
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)
