Spectral clustering and the high-dimensional stochastic blockmodel

Karl Rohe; Sourav Chatterjee; Bin Yu

Source-linked AI summary

Spectral clustering and the high-dimensional stochastic blockmodel

Karl Rohe, Sourav Chatterjee, Bin Yu

arXiv:1007.1684v3Jul 9, 2010stat.MLmath.ST

TL;DR

The paper asks when spectral clustering can recover communities in the Stochastic Blockmodel, especially when the number of blocks grows with network size. It proves latent-space eigenvector convergence and uses it to bound spectral-clustering errors. Under degree and spectral-separation conditions, the misclustered proportion vanishes asymptotically, although the required degree condition is often unrealistic for canonical empirical edges.

Problem
The paper addresses limited asymptotic evidence for spectral clustering when Stochastic Blockmodel communities grow in number with the nodes, a regime motivated by large empirical networks.
Method
The paper proves normalized-Laplacian eigenvector convergence under a latent space model, then analyzes population and sample spectral clustering under the Stochastic Blockmodel.
Results
The proportion of nodes misclustered by spectral clustering vanishes asymptotically when minimum expected degree grows fast enough and the smallest nonzero population-Laplacian eigenvalue shrinks slowly enough.
Takeaways & Limitations
The results provide a high-dimensional benchmark for spectral clustering and show that population Laplacian eigenvectors can perfectly identify Stochastic Blockmodel blocks under weak assumptions.
Takeaways & Limitations
The required expected-degree condition is often not satisfied by canonical edges in empirical networks, whose graphs typically have sparse degrees.

Abstract

from arXiv · show

Networks or graphs can easily represent a diverse set of data sources that are characterized by interacting units or actors. Social networks, representing people who communicate with each other, are one example. Communities or clusters of highly connected actors form an essential feature in the structure of several empirical networks. Spectral clustering is a popular and computationally feasible method to discover these communities. The stochastic blockmodel [Social Networks 5 (1983) 109--137] is a social network model with well-defined communities; each node is a member of one community. For a network generated from the Stochastic Blockmodel, we bound the number of nodes "misclustered" by spectral clustering. The asymptotic results in this paper are the first clustering results that allow the number of clusters in the model to grow with the number of nodes, hence the name high-dimensional. In order to study spectral clustering under the stochastic blockmodel, we first show that under the more general latent space model, the eigenvectors of the normalized graph Laplacian asymptotically converge to the eigenvectors of a "population" normalized graph Laplacian. Aside from the implication for spectral clustering, this provides insight into a graph visualization technique. Our method of studying the eigenvectors of random matrices is original.

1. Introduction.

The paper studies spectral clustering as a computationally feasible way to identify communities in networks, using the Stochastic Blockmodel to analyze when estimated clusters recover true blocks. Its high-dimensional results allow the number of blocks to grow with the number of nodes.

Motivation: Searching over all possible graph partitions is computationally intractable, motivating approximate clustering algorithms.Even a 100-node graph can have more partitions than estimated atoms in the universe by twenty orders of magnitude.
Motivation: Spectral clustering offers a popular and computationally feasible approach to discovering highly connected communities in networks.Community identification supports questions across social, biological, and other networked systems.
Statistical estimation: The paper studies spectral clustering, a nonparametric method, on the parametric task of estimating Stochastic Blockmodel blocks.The model provides a benchmark for understanding spectral clustering, although it does not capture all empirical-network complexities.
High-dimensional regime: Modern applications motivate an asymptotic regime in which the number of communities grows with the number of nodes rather than allowing communities to become too large.Empirical networks often contain tight communities of roughly constant size.
High-dimensional regime: The paper provides the first asymptotic clustering results allowing the number of Stochastic Blockmodel blocks to grow with the number of nodes.This makes the problem a form of high-dimensional learning; a likelihood-based contemporaneous approach weakens assumptions but is computationally difficult.
Statistical estimation: Under the latent space model, empirical normalized-Laplacian eigenvectors converge to eigenvectors of a population normalized Laplacian.The population matrix uses conditional expected adjacency probabilities and the result also informs graph visualization.

2. Consistency under the latent space model.

The paper establishes eigenvector consistency for normalized graph Laplacians under a latent space model despite direct matrix convergence failing. It obtains this through convergence of squared matrices, eigenspectral arguments, and an eigengap-sensitive perturbation bound.

Eigenvector consistency: The empirical eigenvectors of L(n) converge to population eigenvectors even though L(n) itself does not converge to its population counterpart.The analysis instead proves Frobenius-norm convergence for L(n)L(n) to the corresponding squared population matrix.
Squared-matrix convergence: For i.i.d. Bernoulli(1/2) matrices, (W/n)^2 converges in Frobenius norm whereas W/n does not.This example motivates studying squared normalized adjacency or Laplacian matrices.
Spectral convergence: Eigenvalues of the squared empirical Laplacian converge to those of the squared population Laplacian under conditions on τn.The result follows from the matrix convergence theorem, Weyl’s inequality, and Frobenius-norm control of spectral norm.
Eigenvector consistency: The Davis–Kahan bound shows that eigenvector convergence depends on the separation between the eigenvalues of interest and the remaining spectrum.Intervals and eigengaps may vary with n, and the relevant eigenspace dimensions must eventually agree.
Assumptions: The theorem requires the minimum expected degree to grow sufficiently fast and the eigengap not to shrink too quickly.The leading eigenvalues are most useful when they remain well separated because they can reveal network clusters or other structure.
Connection to block recovery: When the population spectrum contains the relevant nonzero eigenvalues, equal rows of its eigenvector matrix characterize nodes in the same Stochastic Blockmodel block.Spectral clustering can then apply k-means to recover the block structure from these row representations.

3. The Stochastic Blockmodel.

Under the Stochastic Blockmodel, spectral clustering targets block membership through population eigenvectors and bounds the nodes it misclusters. The result applies even when the number of blocks grows with the number of nodes, under conditions on expected degree and the population Laplacian spectrum.

The Stochastic Blockmodel assigns nodes to blocks with within-block stochastic equivalence, making community detection a statistical estimation problem.
Spectral clustering finds eigenvectors of the graph Laplacian, treats their rows as points, and applies k-means.
Population spectral clustering recovers the block structure because its eigenvectors have k unique rows corresponding to the k blocks.
Observed spectral clustering accounts for eigenvector nonidentifiability by comparing k-means centroids with rotated population centroids.
Theorem 3.1 bounds misclustered nodes when minimum expected degree grows sufficiently and the smallest nonzero population-Laplacian eigenvalue does not shrink too quickly.
When k = O(n^1/4/log n), the proportion of misclustered nodes converges to zero, even though most edges may connect different blocks.

4. Simulations.

Simulations examine how spectral clustering behaves as network size, block count, eigengap, and minimum expected degree vary. They broadly support the asymptotic bounds while exposing sensitivity to eigengap and degree assumptions.

Simulation design: Three simulations use the four-parameter Stochastic Blockmodel to assess whether the paper’s asymptotic bounds guide finite-sample behavior.The designs vary block size, block count, and probabilities while holding different quantities fixed.
Simulation 1: Once the network is sufficiently large, the number of misclustered nodes converges to zero as empirical eigenvectors converge toward population eigenvectors.In Simulation 1, n grows from 40 to 1075, and the decline begins after a threshold near log n = 4.7.
Simulation 3: The simulations show that roughly 50 nodes per block may be needed to separate informative from uninformative eigenvectors.After this threshold, empirical eigenvectors approach population eigenvectors and spectral clustering estimates the block structure.
Simulation 1: Both the normalized Laplacian and eigenvectors converge at rate O(n−1/2), ignoring log n factors.The simulated convergence lines are approximately parallel to the reference line with slope −1/2.
Simulation 2: As the number of blocks grows, the number of misclustered nodes grows approximately as k3, while eigenvector convergence fails when the eigengap shrinks too quickly.The simulations support the theoretical quantity as a finite-sample guide but show that the eigengap can limit recovery.
Simulation 3: Larger networks tolerate smaller τ, suggesting spectral clustering can work when minimum expected degree grows sublinearly, contrary to the theorem assumptions.In Figure 3, the 50-node-per-block design begins worsening near τ = 0.20, whereas the 250-node design begins near τ = 0.07.

5. Empirical edge density.

The empirical analysis examines whether sparse real-world networks satisfy the paper’s degree assumptions. Facebook networks become substantially more connected when adjacency is defined through friends-of-friends rather than canonical friendship edges.

Motivation: Canonical edges in empirical networks are often too sparse for the asymptotic framework assumed by the paper’s main theorems.The paper identifies sparse degrees as a practical challenge for the expected-degree condition.
Alternative adjacency: The authors propose friends-of-friends edges as an alternative notion of adjacency that can increase network connectivity.An edge is added when two nodes are friends of friends.
Empirical comparison: Table 1 compares five university Facebook networks using canonical friendship edges and friends-of-friends edges.It reports average degrees and the proportions of nodes connected to more than 10% of the graph.
Empirical comparison: The networks are much more connected when edges are defined by friends-of-friends.The statistics T_c and T_ff measure the proportion of well-connected nodes, accounting for nodes with very small degree.
Scope and limitation: The empirical sparsity suggests the assumption τ^2 > 2/log n is generally not satisfied in practice.The paper presents alternative similarity notions as a possible way to obtain denser graphs, while weakening the degree assumption remains future work.

6. Discussion.

The paper establishes two main results: normalized-Laplacian eigenvectors converge under latent space models, and spectral clustering asymptotically misclusters a vanishing proportion of nodes under stated conditions. Its framework permits the number of blocks to grow with network size, while its assumptions limit applicability to dense settings and provide only a misclustering bound.

Theorem 2.2 proves convergence of empirical normalized graph-Laplacian eigenvectors to population eigenvectors when minimum expected degree and eigengap conditions hold.
The latent-space eigenvector result also supports graph visualization by showing that empirical and population eigenvector coordinates are asymptotically similar.
Under corresponding degree and eigenvalue conditions, Theorem 3.1 proves that the proportion of nodes misclustered by spectral clustering vanishes asymptotically.
The framework allows the number of blocks to grow with the number of nodes, yielding the first high-dimensional clustering result of this kind.
Theorem 3.1 bounds misclassified nodes but does not establish consistency, and the results require minimum expected degree to grow roughly linearly with n.

APPENDIX A: PROOF OF THEOREM 2.1

The appendix proves Theorem 2.1 by controlling deviations between empirical and population normalized Laplacian matrices, then applying eigenvalue and eigenvector arguments under high-probability events.

The proof uses symmetry to establish that eigenvectors of M are eigenvectors of M^2, with eigenvalues squared.
With τ defined from the minimum expected degree, the deviation bound holds under the condition n^1/2/log n > 2.
The proof introduces events Γ and Λ to control the degree matrix and normalized matrix products.
Diagonal and off-diagonal terms receive separate bounds because their union bounds involve n and approximately n^2 terms, respectively.
Hoeffding’s inequality and a union bound show that the complement of Γ ∩ Λ has exponentially small probability.

APPENDIX B: DAVIS–KAHAN THEOREM

The Davis–Kahan appendix relates eigenspace differences for symmetric matrices to spectral separation and converts principal-angle bounds into Frobenius eigenvector bounds after an orthonormal rotation.

Principal angles are defined through singular values of the cross-product of two orthonormal eigenvector matrices.
Davis–Kahan bounds the principal-angle distance between eigenspaces associated with eigenvalues inside a separated interval S.
The result applies to any two symmetric matrices, with spectral separation controlling the comparison of their selected eigenspaces.
When the eigenspaces have equal dimension, singular value decomposition supplies an orthonormal rotation aligning the eigenvector matrices.
The theorem can be expressed as a Frobenius-norm bound on XU V^T − X rather than only a subspace-distance bound.

APPENDIX C: PROOF OF THEOREM 2.2

The proof of Theorem 2.2 applies Davis–Kahan to empirical and population normalized graph Laplacians, showing that the relevant eigenspaces eventually have matching dimensions and aligned eigenvectors.

The columns of X_n and X̄_n represent eigenvectors of empirical and population normalized Laplacian products within the selected spectral sets.
The selected empirical and population eigenvalue sets eventually contain the same number of elements, so the corresponding eigenvector matrices have equal column dimension.
Singular value decomposition defines orthonormal matrices U_n and V_n to align the two eigenvector matrices.
The convergence result follows by combining the Davis–Kahan theorem with Theorem 2.1.

APPENDIX D: STOCHASTIC BLOCKMODEL

The appendix proves spectral properties of the stochastic blockmodel by reducing the population Laplacian to a k-dimensional block-level matrix. It then identifies the nonzero eigenvalues and eigenvectors needed for the theorem’s clustering argument.

Population matrix representation: The population matrix is factored as L = ZBLZT, with DB defined from block-level connection totals.This representation reduces the n-dimensional matrix to a k-dimensional block structure.
Spectral decomposition: Positive determinant and symmetry ensure that the block-level matrix has nonzero real eigenvalues and admits an eigenvector decomposition.The decomposition uses a matrix V and diagonal matrix Λ.
Eigenvectors of L: The transformed vectors Zµ are orthonormal eigenvectors of L, and the diagonal entries of Λ give all of L’s nonzero eigenvalues.The proof uses µ = (ZT Z)^−1/2V and verifies (Zµ)T(Zµ) = Ik.
Connection to clustering: Theorem 3.1’s proof then compares the leading eigenvector matrix X with the block-based representation and invokes bounds involving R(n,k), δ, and δ′.The supplied proof passages state that the resulting bound is O(min{δ,δ′}) and that Theorem 2.2 follows.
Equal-sized stochastic blockmodel: For equal-sized groups, ZT1n = s1k, so the block-level eigenproblem becomes the analysis of sBL.The model assumes fixed p and r while the number of groups k may grow with n.