Strong Consistency, Graph Laplacians, and the Stochastic Block Model
- URL: http://arxiv.org/abs/2004.09780v1
- Date: Tue, 21 Apr 2020 07:16:46 GMT
- Title: Strong Consistency, Graph Laplacians, and the Stochastic Block Model
- Authors: Shaofeng Deng, Shuyang Ling, Thomas Strohmer
- Abstract summary: We study the performance of classical two-step spectral clustering via the graph Laplacian to learn the block model.
We prove that spectral clustering is able to achieve exact recovery of the planted community structure under conditions that match the information-theoretic limits.
- Score: 1.2891210250935143
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Spectral clustering has become one of the most popular algorithms in data
clustering and community detection. We study the performance of classical
two-step spectral clustering via the graph Laplacian to learn the stochastic
block model. Our aim is to answer the following question: when is spectral
clustering via the graph Laplacian able to achieve strong consistency, i.e.,
the exact recovery of the underlying hidden communities? Our work provides an
entrywise analysis (an $\ell_{\infty}$-norm perturbation bound) of the Fielder
eigenvector of both the unnormalized and the normalized Laplacian associated
with the adjacency matrix sampled from the stochastic block model. We prove
that spectral clustering is able to achieve exact recovery of the planted
community structure under conditions that match the information-theoretic
limits.
Related papers
- Graph Generation via Spectral Diffusion [51.60814773299899]
We present GRASP, a novel graph generative model based on 1) the spectral decomposition of the graph Laplacian matrix and 2) a diffusion process.
Specifically, we propose to use a denoising model to sample eigenvectors and eigenvalues from which we can reconstruct the graph Laplacian and adjacency matrix.
Our permutation invariant model can also handle node features by concatenating them to the eigenvectors of each node.
arXiv Detail & Related papers (2024-02-29T09:26:46Z) - Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
We present a probabilistic model based on non-negative matrix factorization which unifies clustering and simplification.
By relaxing the hard clustering to a soft clustering, our algorithm relaxes potentially hard clustering problems to a tractable ones.
arXiv Detail & Related papers (2023-08-12T02:47:57Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
We devise an efficient algorithm that recovers clusters using the observed labels.
We present Instance-Adaptive Clustering (IAC), the first algorithm whose performance matches these lower bounds both in expectation and with high probability.
arXiv Detail & Related papers (2023-06-18T08:46:06Z) - Perfect Spectral Clustering with Discrete Covariates [68.8204255655161]
We propose a spectral algorithm that achieves perfect clustering with high probability on a class of large, sparse networks.
Our method is the first to offer a guarantee of consistent latent structure recovery using spectral clustering.
arXiv Detail & Related papers (2022-05-17T01:41:06Z) - On consistency of constrained spectral clustering under
representation-aware stochastic block model [20.6072287343024]
We study constrained spectral clustering with the aim of finding balanced clusters in a given textitsimilarity graph $mathcalG$.
We develop unnormalized and normalized variants of spectral clustering in this setting.
These algorithms use $mathcalR$ to find clusters in $mathcalG$ that approximately satisfy the proposed constraint.
arXiv Detail & Related papers (2022-03-03T20:41:14Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
Clustering is a fundamental primitive in unsupervised learning.
Recent work has established lower bounds against the class of low-degree methods.
We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
arXiv Detail & Related papers (2021-12-07T18:50:17Z) - Correlation Clustering Reconstruction in Semi-Adversarial Models [70.11015369368272]
Correlation Clustering is an important clustering problem with many applications.
We study the reconstruction version of this problem in which one is seeking to reconstruct a latent clustering corrupted by random noise and adversarial modifications.
arXiv Detail & Related papers (2021-08-10T14:46:17Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree.
In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
arXiv Detail & Related papers (2021-05-03T16:36:27Z) - Robustness of Community Detection to Random Geometric Perturbations [16.575947847660778]
We consider the block model where connection between vertices is perturbed by some latent (and unobserved) random geometric graph.
The objective is to prove that spectral methods are robust to this type of noise, even if they are agnostic to the presence (or not) of the random graph.
arXiv Detail & Related papers (2020-11-09T10:15:40Z) - Average Sensitivity of Spectral Clustering [31.283432482502278]
We study the stability of spectral clustering against edge perturbations in the input graph.
Our results suggest that spectral clustering is stable against edge perturbations when there is a cluster structure in the input graph.
arXiv Detail & Related papers (2020-06-07T09:14:44Z) - Robust spectral clustering using LASSO regularization [0.0]
This paper presents a variant of spectral clustering, called 1-spectral clustering, performed on a new random model closely related to block model.
Its goal is to promote a sparse eigenbasis solution of a 1 minimization problem revealing the natural structure of the graph.
arXiv Detail & Related papers (2020-04-08T07:12:56Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.