Source-linked AI summary
Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embedding
Vince Lyzinski, Daniel Sussman, Minh Tang, Avanti Athreya, Carey Priebe
TL;DR
Vertex clustering in graphs is important, but existing spectral guarantees can permit some misclustered vertices. This paper analyzes adjacency spectral embedding and establishes perfect clustering results for stochastic blockmodels and degree-corrected stochastic blockmodels, alongside a consistency result for random dot product graphs.
Problem
Existing spectral clustering bounds based on global error can allow up to O(log(n)) misclustered vertices, motivating stronger guarantees for graph clustering.
Source: §6 · p. 18Method
The paper bounds individual embedded-vertex errors for adjacency spectral embedding and uses this control to analyze clustering across several random graph models.
Source: §1 · p. 2, §6 · p. 18Results
The results establish asymptotically almost surely perfect clustering in the stochastic and degree-corrected stochastic blockmodels, and strong universal consistency for random dot product graphs.
Source: §1 · p. 3, §6 · pp. 18–19Takeaways & Limitations
Depending on model parameters, the probability of perfect clustering in the degree-corrected stochastic blockmodel tends to one as the number of vertices grows.
Source: §6 · p. 19The assumptions do not hold when both SBM edge-probability parameters a and b are O(1), a setting where consistent estimation is impossible for any such choices [12].
Source: §2.3 · p. 10
Abstract
from arXiv · showhide
Vertex clustering in a stochastic blockmodel graph has wide applicability and has been the subject of extensive research. In thispaper, we provide a short proof that the adjacency spectral embedding can be used to obtain perfect clustering for the stochastic blockmodel and the degree-corrected stochastic blockmodel. We also show an analogous result for the more general random dot product graph model.
1 Introduction
Graph clustering seeks groups of similar vertices, but existing spectral guarantees based on global Frobenius error bounds allow up to O(log(n)) misclusterings. This paper uses adjacency spectral embedding to establish error-free clustering results and extends them to more general graph models.
1 Introduction
- The paper focuses on probabilistic guarantees for spectral clustering across the stochastic blockmodel, degree-corrected stochastic blockmodel, and random dot product graph.These are presented as three nested classes of latent position models.Source: §1 · p. 2
- Global Frobenius norm bounds can leave up to O(log(n)) vertices misclustered because a diminishing fraction of embedded points may contribute disproportionately to total error.Such outliers are very likely to be misclustered.Source: §1 · p. 2
- A maximum-error bound for individual embedded vertices supports improved mean squared error clustering guarantees for adjacency spectral embedding.The bound compares embedded vertices with eigenvectors of the edge probability matrix.Source: §1 · p. 2
- The paper proves that mean squared error clustering via adjacency spectral embedding can be error-free, with zero misclustered vertices.The introduction identifies this as the first main clustering result.Source: §1 · pp. 2–3
- The approach also yields asymptotically error-free clustering for the degree-corrected stochastic blockmodel and strong universal consistency for random dot product graphs.For the degree-corrected model, the cited prior spectral results allow at most O(log(n)) misclusterings [17, Theorem 4.4].Source: §1 · p. 3
2 Setting and main theorem
The section introduces adjacency spectral embedding (ASE) and mean square error clustering, then develops a row-wise error bound used to establish perfect-clustering guarantees for stochastic blockmodels and extensions. These results depend on model conditions, including separation between latent positions, and the perfect-clustering probability approaches one asymptotically under the stated choice of η.
2.1 Random dot product graphs and the adjacency spectral embedding
- ASE embeds vertices using eigenvectors and eigenvalues of the adjacency matrix; in a random dot product graph, latent-position dot products determine edge probabilities.The embedding is defined as ˆX = ˆV ˆS^1/2.Source: §2.1 · pp. 3–4
2.2 Clustering
- MSE clustering groups the rows of the embedding into K clusters, and the paper also considers projected-embedding clustering for the degree-corrected stochastic blockmodel.An SBM is represented by K distinct latent-position rows in the section's formulation.Source: §2.2 · p. 5
2.3 Main theorems
- The row-wise embedding bound controls individual vertex errors, addressing the limitation of Frobenius-norm bounds that permit up to O(log n) misclustered vertices.The paper presents this bound as the tool for proving its error-free clustering result.Source: §2.3 · pp. 6–7
- The results extend to degree-corrected stochastic blockmodels and random dot product graphs; the paper also states strong universal consistency for MSE clustering in the latter setting.The stochastic blockmodel guarantee requires sufficient separation between distinct latent positions; the paper notes that its assumptions do not hold when a = O(1) and b = O(1) in the sparse example.Source: §2.3 · pp. 7, 8, 10
- For the stochastic blockmodel, the theorem bounds the probability of error-free MSE clustering under separation and eigenvalue-gap assumptions; with η = n^-c, that probability approaches one as n grows.The result gives a finite-sample lower bound, not a claim that perfect clustering occurs with probability one for finite n.Source: §2.3 · pp. 7–8
3 Proof of Theorem 2.6
The proof builds individual-row embedding error bounds and uses them to show that optimal MSE clustering preserves the latent-position blocks.
3 Proof of Theorem 2.6
- The proof first collects existing bounds and proves two key lemmas before applying them to Theorem 2.6.The cited lemmas are identified as essential to the argument.Source: §3 · pp. 10–11
- When Δ ≥ 16 log(n/η), the proof bounds the norm of the estimated eigenvalue matrix by min{2Δ, n}, provided the stated events occur.The proof also uses that P is nonnegative, giving ∥S∥2 ≤ Δ.Source: §3 · p. 11
- Combining the bounds for three terms in the embedding error decomposition establishes Lemma 2.5 with probability at least 1 − η.The decomposition separates eigenvector, eigenvalue-scaling, and adjacency-noise terms.Source: §3 · pp. 12–13
- The clustering argument shows that two vertices share a cluster exactly when their latent positions are equal.Disjoint radius-2r balls around the distinct latent positions contain one distinct estimated center each, so equality of latent positions is preserved by the estimated centers.Source: §3 · pp. 13–14
4 Degree corrected SBM
The degree-corrected model permits within-block degree variation, so the method normalizes the spectral embedding before clustering. The section extends error-free clustering guarantees to this model.
4 Degree corrected SBM
- The DCSBM allows vertices within a block to have different expected degrees by scaling a shared unit-vector position.Each latent position has the form Xi = ci yk, with ci in (0, 1).Source: §4 · p. 14
- Projecting each embedded row onto the unit sphere estimates the unit block directions rather than the degree-scaled latent positions.The projection normalizes each row of the embedding; the method uses the resulting estimate of Y for DCSBM clustering.Source: §4 · p. 14
- A rowwise error lemma for the normalized embedding provides the analogue of the earlier individual-row control.It bounds errors between the sphere-projected rows of X and the embedding, conditional on a bound for ∥X̂ − X∥2→∞.Source: §4 · p. 14
- The DCSBM theorem gives a bound on the probability of error-free MSE clustering using the projected embedding.The theorem assumes separated unit block vectors and specifies the smallest block size and scaling factor among its conditions.Source: §4 · pp. 15–16
5 Strong universal consistency
The paper extends strong K-means consistency from sampled latent positions to their adjacency spectral estimates, under the population uniqueness conditions stated for the optimal centers.
5 Strong universal consistency
- The proof strategy defines clustering objectives for empirical and population distributions using a continuous, nondecreasing loss function.The function φ is required to satisfy φ(0) = 0; squared error corresponds to φ(r) = r².Source: §5 · p. 16
- Under Theorem 5.1’s conditions, the estimated centers converge almost surely to the population-optimal centers, and their objective values converge to the population optimum.The result applies when the latent positions are sampled from a common compactly supported distribution and the population minimizer is unique.Source: §5 · pp. 16–17
6 Discussion
The discussion connects individual-row embedding control to perfect clustering and outlines extensions to broader regimes and graph models.
6 Discussion
- Controlling individual rows of the embedding supports asymptotically almost surely perfect clustering in both the SBM and DCSBM.The discussion characterizes this as a substantive improvement over the best existing spectral clustering results.Source: §6 · p. 18
- The approach extends to fixed-parameter SBMs with linear-sized smallest blocks, random independent block memberships, and alternative clustering procedures.The discussion names Gaussian mixture modeling and hierarchical clustering as examples.Source: §6 · p. 18
- The theory can also handle growing block counts and moderately sparse regimes, with effects on d, γ, n_min, and γ, respectively.The discussion refers to examples where asymptotically perfect performance is achieved.Source: §6 · p. 18
- The rowwise error lemma also supports graph matching, vertex classification, and two-sample graph testing beyond clustering.The discussion identifies the lemma as a key component in these consistency results.Source: §6 · p. 18
- For general RDPGs without natural communities, consistent clustering of the embedding is asymptotically equivalent to clustering the latent positions.Choosing k-centers can approximate the latent-position distribution by a mixture of point masses, yielding parsimonious SBM approximations.Source: §6 · p. 19