Sparse and Smooth: improved guarantees for Spectral Clustering in the Dynamic Stochastic Block Model

2020-02-07 · Nicolas Keriven, Samuel Vaiter

In this paper, we analyse classical variants of the Spectral Clustering (SC) algorithm in the Dynamic Stochastic Block Model (DSBM). Existing results show that, in the relatively sparse case where the expected degree grows logarithmically with the number of nodes, guarantees in the static case can be extended to the dynamic case and yield improved error bounds when the DSBM is sufficiently smooth in time, that is, the communities do not change too much between two time steps. We improve over these results by drawing a new link between the sparsity and the smoothness of the DSBM: the more regular the DSBM is, the more sparse it can be, while still guaranteeing consistent recovery. In particular, a mild condition on the smoothness allows to treat the sparse case with bounded degree. We also extend these guarantees to the normalized Laplacian, and as a by-product of our analysis, we obtain to our knowledge the best spectral concentration bound available for the normalized Laplacian of matrices with independent Bernoulli entries.

📄 PDF Abstract BibTeX arXiv:2002.02892

Code (0)

등록된 구현이 없습니다.

Tasks

ClusteringStochastic Block Model

Methods 이 논문이 사용한 방법론

Spectral Clustering Spectral clustering has attracted increasing attention due to the promising ability in dealing with nonlinearly separable datasets [15], [16]. In spectral clustering, the…

A Manifold Proximal Linear Method for Sparse Spectral Clustering with Application to Single-Cell RNA Sequencing Data Analysis

2020-07-18 · Zhongruo Wang, Bingyuan Liu, Shixiang Chen, Shiqian Ma 외

Spectral clustering is one of the fundamental unsupervised learning methods widely used in data analysis. Sparse spectral clustering (SSC) imposes sparsity to the spectral clustering and it improves the interpretability …

Clustering

Spectral clustering in the dynamic stochastic block model

2017-05-02 · Marianna Pensky, Teng Zhang

In the present paper, we studied a Dynamic Stochastic Block Model (DSBM) under the assumptions that the connection probabilities, as functions of time, are smooth and that at most $s$ nodes can switch their class members…

Clustering model Stochastic Block Model

Spatial Sparse subspace clustering for Compressive Spectral imaging

2019-11-05 · Jianchen Zhu, Tong Zhang, Shengjie Zhao, Carlos Hinojosa 외

This paper aims at developing a clustering approach with spectral images directly from CASSI compressive measurements. The proposed clustering method first assumes that compressed measurements lie in the union of multipl…

Clustering Image Clustering

Perfect Clustering for Sparse Directed Stochastic Block Models

2026-01-23 · Behzad Aalipur, Yichen Qin arxiv

Exact recovery in stochastic block models (SBMs) is well understood in undirected settings, but remains considerably less developed for directed and sparse networks, particularly when the number of communities diverges. …

Community Detection

Convergence of Spectral Descent for Non-smooth Optimization

2026-05-26 · Yixuan Yang, Yuqing He, Song Li arxiv

The Muon optimizer has recently demonstrated remarkable empirical success in training large language models. However, the theoretical understanding of its mechanisms remains limited. Current convergence guarantees for Mu…