PaperlayerView exact revision on arXiv

Source-linked AI summary

Consistency of spectral clustering in stochastic block models

Jing Lei, Alessandro Rinaldo

arXiv:1312.2050v3math.STstat.ML

TL;DR

The paper asks whether spectral clustering can recover communities in stochastic block models when networks are substantially sparser than prior theory permits. It analyzes adjacency-matrix spectral clustering and extends the approach to degree-corrected models. The results establish recovery with maximum expected degree of order log n under stated conditions, supported by a sharper spectral bound for binary random matrices.

  • Problem

    Prior analyses did not adequately establish spectral-clustering guarantees for community recovery in SBM settings where maximum expected degree can be as small as log n.

  • Method

    The paper develops adjacency-matrix spectral-clustering error bounds using subspace perturbation and a sharp spectral bound for binary random matrices, extending the analysis to degree-corrected SBMs with spherical k-median.

  • Results

    Maximum expected degree of order log n suffices for the paper’s spectral-clustering recovery guarantee in SBMs, including recovery of all but a vanishing fraction of memberships with high probability.

  • Takeaways & Limitations

    The results theoretically justify practical spectral-clustering procedures for moderately sparse networks and provide guarantees that compare favorably with most existing results in the stated settings.

  • Takeaways & Limitations

    The analysis applies directly to adjacency-matrix eigenvectors, while extending the results to graph-Laplacian spectral clustering remains future work; small-degree nodes also motivate further regularization analysis in degree-corrected models.

Abstract

from arXiv · show

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.

1. Introduction.

The paper studies whether computationally practical spectral clustering can recover communities in stochastic block models under substantially sparser networks than prior analyses allowed. It develops sharper guarantees for standard and degree-corrected models, including expected degrees of order log n.

  • 1. Introduction.: Community recovery from a single network observation is a central inferential task in stochastic block models.SBMs partition nodes into latent communities and generate edges independently according to community memberships.
  • 1. Introduction.: Spectral clustering is widely used because it combines eigen-decomposition with clustering of leading-eigenvector rows and is easier to implement than many alternatives.The paper emphasizes its comparatively lower computational demands.
  • 1. Introduction.: Existing theoretical analyses generally exclude networks whose maximum expected degree is as small as log n.Prior conditions cited in the paper require expected degrees that are almost linear or polynomial in n.
  • 1. Introduction.: The paper derives new error bounds showing that basic spectral clustering can recover all but a vanishing fraction of SBM memberships with high probability when expected degree is as small as log n.The guarantees apply under weaker sparsity conditions than those used in much of the prior literature.
  • 1. Introduction.: The analysis extends to degree-corrected block models through approximate spherical k-median clustering and combines subspace perturbation with a sharp binary-matrix spectral bound.The spectral bound improves on matrix Bernstein for the relevant large-deviation control and avoids an individual eigengap condition.

2. Preliminaries.

The preliminaries define the SBM, its community-recovery objective, and the adjacency-matrix spectral-clustering procedure. They explain why leading eigenvectors reveal community structure and describe sparsity and related model parameters affecting recovery.

  • 2.1. Model setup: An SBM is parameterized by a membership matrix Θ and a symmetric connectivity matrix B, whose entries specify between-community edge probabilities.Conditional on memberships, adjacency entries are independent Bernoulli variables for distinct node pairs.
  • 2.1. Model setup: Community recovery estimates Θ up to column permutations, with overall and worst-community relative errors measuring different aspects of mis-clustering.The stronger criterion requires good performance for every community, including small ones.
  • 2.2. Spectral clustering: Spectral clustering estimates the leading eigenspace of the adjacency matrix and clusters its rows, exploiting the block structure of the population matrix P = ΘBΘ^T.The population eigenvector matrix has at most K distinct rows under the SBM structure.
  • 2.2. Spectral clustering: The algorithm computes leading adjacency eigenvectors, obtains an approximate K-means solution, and outputs the resulting membership matrix.Approximate K-means is used because finding a global minimizer is NP-hard, while polynomial-time approximation algorithms exist.
  • 2.3. Sparsity scaling: In the symmetric-community example, α_n controls network sparsity and λ measures the relative within-community versus between-community connectivity difference.The quantity nα_n bounds the average and maximum expected degree in that example; small α_n or λ makes communities hard to identify.
  • 2.3. Sparsity scaling: Recovery difficulty also depends on the number of communities, community-size imbalance, and separation between communities.The planted-clique example illustrates how community size affects computational recovery thresholds.

3. Stochastic block models.

The paper establishes error guarantees for adjacency-matrix spectral clustering in SBMs under sparsity as low as log n, and derives interpretable consistency conditions and extensions to related settings.

  • General error bound: Theorem 3.1 bounds spectral-clustering reconstruction error for rank-K SBMs using approximate k-means on leading adjacency-matrix eigenvectors.The theorem assumes smallest nonzero population eigenvalue at least γ_n and maximum connectivity entry α_n ≥ log n/n.
  • General error bound: With probability at least 1 − n^-1, all but subsets S_k of nodes are correctly assigned up to a community-label permutation.The exceptional sets contain nodes whose clustering correctness cannot be guaranteed, and their size controls reconstruction error.
  • General error bound: The theorem’s applicability condition is technical because it holds whenever the resulting error bound vanishes, thereby implying consistency.The constants and probability exponent can be adjusted when the sparsity lower bound is changed to c_0 log n/n or the target probability to 1 − n^-r.
  • Interpretable consistency conditions: For balanced communities and constant separation, α_n = Ω(log n/n) gives L(bΘ,Θ) = O_P(K^2/log n), hence consistency when K = o(√log n).This improves an earlier condition requiring α_n of order 1/log n for a similar result.
  • Interpretable consistency conditions: When the relative within- versus between-community edge-probability gap stays bounded away from zero, simple spectral clustering consistently recovers communities with expected degrees no smaller than log n.With constant α_n and varying separation λ_n, recovery instead requires the relative edge-probability gap to grow faster than 1/√n.
  • Examples and comparison: In the planted-clique setting, the method reaches the believed computational barrier up to a constant factor while recovering the hidden clique with relative error at most c′/a.The stated guarantee applies when the clique-size parameter satisfies a_n for some a > c′.
  • Examples and comparison: Compared with McSherry’s alternative spectral method, the paper focuses on how sparsity affects the basic spectral-clustering procedure in a two-community planted-partition setting.The cited comparison considers equal-sized communities and constant λ.

4. Degree corrected stochastic block models.

The paper extends spectral clustering analysis to degree corrected block models, using spherical k-median clustering to accommodate node-level degree heterogeneity. Under conditions including maximum edge probability of order at least log n/n, the method admits recovery guarantees, though heterogeneity and normalization tighten the bounds.

  • Model: DCBMs introduce node-specific degree parameters ψ, allowing varying degrees within communities while retaining conditionally independent edges.The edge probability between nodes i and j is ψ_iψ_jB_{g_i g_j}.
  • Spectral structure and algorithm: In a DCBM, rows of the population eigenvector matrix may differ in magnitude but lie in at most K distinct directions, motivating row normalization and spherical clustering.The algorithm row-normalizes the leading eigenvectors before applying approximate k-median.
  • Main result: Theorem 4.2 gives a main recovery result for spherical k-median spectral clustering when P has rank K, smallest nonzero eigenvalue at least γ_n, and maximum entry at most α_n with α_n ≥ log n/n.The theorem provides an absolute-constant condition under which the estimator satisfies the stated error guarantee.
  • Main result: Corollary 4.3 specializes the DCBM guarantee to B = α_nB_0, assuming λ > 0 and α_n ≥ log n/n.The result uses an approximate spherical k-median solution and explicit scaling through the model parameters.
  • Limitations and comparison: Compared with the SBM case, DCBM conditions are more stringent because they include the heterogeneity term n_kν_k, and the proof may not yield a sharp upper bound.The paper attributes this partly to spherical normalization and the proof strategy.
  • Interpretation: The DCBM error depends on degree heterogeneity ν and minimum effective community size ˜n_min, and can remain o_P(1) at α_n as small as log n/n under sufficiently favorable scaling.The stated conditions require 1/ν, ˜n_min/n, and λ to stay bounded away from zero or approach zero sufficiently slowly.

Comparisons with existing work.

The paper situates its DCBM result against earlier methods that generally require stronger degree growth. Its analysis allows substantially sparser settings, subject to the stated heterogeneity and model conditions.

  • Comparison with existing work: Earlier DCBM spectral results imposed stronger sparsity requirements, including polynomial growth of expected average degree in Jin (2012).The paper contrasts its result with work allowing maximum node degree of order o(n).

5. Proof of the main results.

The proof combines subspace perturbation, a sharp spectral bound for sparse binary random matrices, and deterministic clustering-error guarantees. These ingredients connect adjacency-matrix eigenvectors to community recovery under sparse-network conditions.

  • Proof strategy: The proof framework has three parts: principal-subspace perturbation, spectral control of random binary matrices, and error bounds for k-means or spherical k-median.The scheme applies to SBMs and extends to degree corrected block models.
  • Subspace perturbation: The eigenvector analysis bounds the difference between the leading eigenvectors of the noisy adjacency matrix A and the population matrix P, up to an orthogonal rotation.The rotation accounts for repeated leading eigenvalues.
  • Random-matrix spectral bound: Theorem 5.2 provides a sharp probabilistic upper bound on ∥A − P∥ when independent-edge graphs satisfy d ≥ c_0 log n.The bound improves on what conventional matrix Bernstein inequalities provide.
  • Random-matrix spectral bound: The spectral bound is proved through discretization, separate control of light and heavy vector pairs, and combinatorial counting for heavy pairs.Bernstein’s inequality handles light pairs, while a large-deviation argument controls heavy pairs.
  • Clustering error: Approximate k-means converts Frobenius closeness between empirical and ideal eigenvector matrices into a bound on the misclustered nodes.The guarantee applies to any (1 + ε)-approximate k-means solution and recovers memberships outside the exceptional set.
  • SBM recovery: For the SBM theorem, combining subspace perturbation with the random-matrix bound yields the required eigenvector closeness with probability at least 1 − n^-1.The subsequent argument applies the approximate k-means lemma to obtain the stated recovery result.

6. Concluding remarks.

The paper develops spectral-clustering guarantees for sparse stochastic block models, tracks five model parameters, and identifies extensions and limitations for adjacency-based analysis.

  • 6. Concluding remarks.: Adjacency-matrix analysis does not directly cover graph-Laplacian spectral clustering, whose degree normalization can introduce extra noise in sparse networks.The authors identify extending their results to regularized graph-Laplacian methods as future work.
  • 6. Concluding remarks.: Regularization may improve degree-corrected block-model error bounds when isolated or very small degree parameters disproportionately affect the guarantees.The authors propose discarding sufficiently small-degree nodes and analyzing an appropriate regularization in future work.
  • 6. Concluding remarks.: The error bounds explicitly track K, α_n, λ, n_min, and n_max rather than treating some of these parameters as fixed.This parameterization is presented as a distinction from many existing analyses.
  • 6. Concluding remarks.: c√n: spectral clustering can find a planted clique when its size is at least c√n for a sufficiently large constant c.This implication is stated for the planted clique model.
  • 6. Concluding remarks.: K²/(nλ²) → 0: in the balanced example with α_n ≡ 1, spectral clustering is consistent under this condition.The example assumes n_max = n_min = n/K.

APPENDIX: TECHNICAL PROOFS

The appendix defines the standard matrix inner product used in the technical proofs.

  • APPENDIX: TECHNICAL PROOFS: ⟨A,B⟩ = trace(A^T B) defines the standard matrix inner product for same-dimensional matrices.The notation applies to any two matrices A and B of equal dimension.

A.1. Proof of Lemma 5.1.

The proof combines an orthogonal alignment of eigenspaces, norm comparisons, and Davis–Kahan perturbation control to bound eigenvector error.

  • A.1. Proof of Lemma 5.1.: An orthogonal K-dimensional matrix Q aligns the relevant subspaces.The existence of Q follows from Proposition 2.2 of Vu and Lei (2013).
  • A.1. Proof of Lemma 5.1.: The proof compares Frobenius and operator-norm projections involving U and the estimated eigenvector matrix.These inequalities provide the norm control used in the perturbation argument.
  • A.1. Proof of Lemma 5.1.: ∥A − P∥ ≤ γ_n/2: under this perturbation condition, the Davis–Kahan sinΘ theorem supplies the required eigenspace bound.The theorem is invoked after establishing the spectral-norm deviation condition.

A.2. Proof of Lemma 5.3.

The proof establishes a row-clustering correspondence by showing that approximate cluster representatives are equal within groups and distinct across groups.

  • A.2. Proof of Lemma 5.3.: The first claim follows from the displayed inequality in equation (A.1).The proof concludes this part immediately after invoking the bound.
  • A.2. Proof of Lemma 5.3.: Under the second lemma assumption, equation (A.1) provides the additional control needed for the remainder of the argument.The proof then uses the stated cluster-size condition.
  • A.2. Proof of Lemma 5.3.: T_k ≠ ∅ for every k, and rows assigned to different groups cannot share the same approximate representative.Otherwise, the separation inequality would be violated.
  • A.2. Proof of Lemma 5.3.: Rows within the same T_k must share one representative because allowing more than one would create more than K distinct rows.At least K − 1 other rows are already occupied by members of the remaining groups.
  • A.2. Proof of Lemma 5.3.: The resulting equality-within and inequality-across relation establishes the correspondence between the rows and the clustering.This is the concluding structural step shown in the supplied proof.

A.3. Proofs for degree corrected block models.

The proof of Theorem 4.2 establishes spectral clustering guarantees for degree-corrected block models by controlling zero rows, normalized eigenvector distances, and approximate k-median error. These bounds imply that mis-clustered nodes are confined to a controlled exceptional set.

  • The proof simplifies notation by taking Q = I_K; the general case follows by substituting U with UQ.
  • Lemma A.1 bounds the number of zero rows in the leading eigenvector matrix bU for degree-corrected block models.The lemma concerns leading eigenvectors of the adjacency matrix A and population matrix P under Theorem 4.2's conditions.
  • The proof compares an approximate k-median solution with the targeted row-normalized solution U′′ using a (2,1)-norm triangle inequality.The comparison begins with ∥bΘ + bX − U′′∥2,1 ≤ ∥bΘ + bX − bU′∥2,1 + ∥bU′ − U′′∥2,1.
  • The resulting approximation error satisfies ∥bΘ + bX − U′′∥2,1 ≤ (2 + ε)∥bU′ − U′′∥2,1.
  • Mis-clustered nodes are contained in I0 ∪ S, whose cardinality is bounded by the right-hand side of (A.4), yielding the claimed theorem after choosing c = 8C.Condition (4.3) ensures every true cluster intersects the nonexceptional set G = I+ \ S.
Loading 1312.2050v3…