Impact of regularization on spectral clustering

DOI10.1214/16-AOS1447zbMATH Open1357.62229arXiv1312.1733OpenAlexW2464534118MaRDI QIDQ309744FDOQ309744

Bin Yu, Antony Joseph

Publication date: 7 September 2016

Published in: The Annals of Statistics (Search for Journal in Brave)

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 $au$ 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 $logn$) 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.

Full work available at URL: https://arxiv.org/abs/1312.1733

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

zbMATH Keywords

stochastic block modelregularizationcommunity detectionnetwork analysisregularized spectral clustering (RSC)

Mathematics Subject Classification ID

Nonparametric estimation (62G05) Asymptotic properties of nonparametric inference (62G20) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Multivariate analysis (62H99)

Cites Work

• A nonparametric view of network models and Newman–Girvan and other modularities
• Spectral clustering and the high-dimensional stochastic blockmodel
• Pseudo-likelihood methods for community detection in large sparse networks
• Community structure in social and biological networks
• Title not available (Why is that?)
• Consistent Adjacency-Spectral Partitioning for the Stochastic Block Model When the Model Parameters Are Unknown
• A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
• 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
• Impact of regularization on spectral clustering
• Improved Spectral-Norm Bounds for Clustering
• Improved Cheeger's inequality

Cited In (35)

• Fast Network Community Detection With Profile-Pseudo Likelihood Methods
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Time-Varying Network for Cryptocurrencies
• A review on spectral clustering and stochastic block models
• Fusing data depth with complex networks: community detection with prior information
• Title not available (Why is that?)
• On semidefinite relaxations for the block model
• Estimating mixed-memberships using the symmetric Laplacian inverse matrix
• Graph Powering and Spectral Robustness
• Community detection by \(L_{0}\)-penalized graph Laplacian
• Modularity Maximization for Graphons
• Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator
• Community detection in complex networks: from statistical foundations to data science applications
• Impact of regularization on spectral clustering
• Enhanced Equivalence Projective Simulation: A Framework for Modeling Formation of Stimulus Equivalence Classes
• Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
• Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
• PCABM: Pairwise Covariates-Adjusted Block Model for Community Detection
• Community Detection in Sparse Networks Using the Symmetrized Laplacian Inverse Matrix (SLIM)
• Randomized Spectral Clustering in Large-Scale Stochastic Block Models
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Role of normalization in spectral clustering for stochastic blockmodels
• Applications of dual regularized Laplacian matrix for community detection
• Limit theorems for eigenvectors of the normalized Laplacian for random graphs
• Detecting Overlapping Communities in Networks Using Spectral Methods
• Spectral clustering in the dynamic stochastic block model
• Hierarchical Community Detection by Recursive Partitioning
• Large volatility matrix analysis using global and national factor models
• Title not available (Why is that?)
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Community detection in sparse networks via Grothendieck's inequality
• 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)