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