Consistency of spectral clustering in stochastic block models

By Jing Lei, Alessandro Rinaldo. 2013

677 citations recorded by the source corpus.

We analyze the performance of spectral clustering for community extraction in stochastic block models. We show that, under mild conditions, spectral clustering applied to the adjacency matrix of the network can consistently recover hidden communities even when the order of the maximum expected degree is as small as $\log n$, with $n$ the number of nodes. This result applies to some popular polynomial time spectral clustering algorithms and is further extended to degree corrected stochastic block models using a spherical $k$-median spectral clustering method. A key component of our analysis is a combinatorial bound on the spectrum of binary random matrices, which is sharper than the conventional matrix Bernstein inequality and may be of independent interest.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/5e97df7539dcf2e5262ae7d195e4b9967cd76f3c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

In Statistics and Probability

Citations in the corpus

Compressive Spectral Clustering (2016, methodology): “We ﬁrst perform well-controlled experiments on the Stochastic Block Model (SBM), a model of random graphs with community structure, that was showed suitable as a benchmark for SC in (Lei & Rinaldo, 2015).”
Random graph asymptotics for treatment effect estimation under network interference (2020, positive): “2 in Lei and Rinaldo (2015). Lei and Rinaldo (2015) show that with a probability converging to 1, ‖E − E‖op ≤ C √ d if nmaxE∗ ij ≤ d.”
Limit theorems for eigenvectors of the normalized Laplacian for random graphs (2016, background): “The stochastic blockmodel [20] is a popular generative model for random graphs with latent community structure and many results are known regarding consistent recovery of the block assignments; see for example [7, 13, 24, 28, 29, 31, 35, 37, 40] and the references therein.”
Approximate Gradient Coding via Sparse Random Graphs (2017, background): “This bound was later improved by the following result from [13].”
Statistical Inference on Random Dot Product Graphs: a Survey (2017, background): “As we will see shortly, one can show that ∥A−XX⊺∥ = O(∥X∥) = o(∥XX⊺∥) with high probability [57, 62, 76, 103].”
Optimal full ranking from pairwise comparisons (2021, background): “2 in [31] and Bound (34) is from standard concentration of sums of i.”
Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss (2021, background): “The eigenvalue problems are closely related to graph partitioning as shown in spectral graph theory [17] for both worst-case graphs [11, 25, 29, 33] and random graphs [1, 30, 34].”