PaperlayerView exact revision on arXiv

Source-linked AI summary

Consistency of spectral clustering

Ulrike von Luxburg, Mikhail Belkin, Olivier Bousquet

arXiv:0804.0678v1math.ST

TL;DR

The paper asks whether spectral clustering is consistent for data sampled from an underlying probability distribution, a question with little prior limit-behavior theory. It develops methods proving convergence of graph-Laplacian eigenvalues and eigenvectors to limit-operator counterparts. Normalized clustering converges under mild or very general conditions, while unnormalized clustering needs stronger conditions that may fail in practice, supporting normalized clustering as the preferred approach.

  • Problem

    The paper addresses the lack of results on whether spectral-clustering partitions converge for samples drawn from an underlying probability distribution.

  • Method

    The paper proves convergence of eigenvalues and eigenvectors of growing random graph-Laplacian matrices to those of suitable limit operators.

  • Results

    Normalized spectral clustering converges under mild assumptions, while unnormalized spectral clustering converges under more restrictive spectral conditions.

  • Takeaways & Limitations

    The authors conclude that normalized spectral clustering should generally be preferred, and unnormalized methods require checking whether relevant eigenvalues lie below the continuous spectrum.

  • Takeaways & Limitations

    Unnormalized spectral clustering can fail to yield sensible results when its eigenvalue-isolation condition λ ∉ rg(d) is violated.

Abstract

from arXiv · show

Consistency is a key property of all statistical procedures analyzing randomly sampled data. Surprisingly, despite decades of work, little is known about consistency of most clustering algorithms. In this paper we investigate consistency of the popular family of spectral clustering algorithms, which clusters the data with the help of eigenvectors of graph Laplacian matrices. We develop new methods to establish that, for increasing sample size, those eigenvectors converge to the eigenvectors of certain limit operators. As a result, we can prove that one of the two major classes of spectral clustering (normalized clustering) converges under very general conditions, while the other (unnormalized clustering) is only consistent under strong additional assumptions, which are not always satisfied in real data. We conclude that our analysis provides strong evidence for the superiority of normalized spectral clustering.

1. Introduction.

The paper addresses the largely unresolved consistency and limit behavior of spectral clustering for random samples. It develops convergence results showing a broad advantage for normalized over unnormalized spectral clustering.

  • Consistency asks whether sample clusterings converge to a clustering of the underlying space and whether that limiting partition is reasonable.
  • Prior theory mainly studied spectral clustering on finite point sets, leaving its limit behavior for samples from probability distributions unaddressed.
  • The paper establishes consistency results and convergence rates for several spectral-clustering variants by proving convergence of random graph-Laplacian eigenvalues and eigenvectors.
  • Normalized spectral clustering is consistent under very general conditions, whereas unnormalized clustering requires specific conditions that may fail in practice.
  • Growing Laplacian dimensions and dependent entries prevent direct application of standard random-matrix results, motivating new methods for more general conditions.
  • The analysis provides the paper’s first theoretical resolution of the normalized-versus-unnormalized debate from a statistical perspective.

2. Spectral clustering.

Spectral clustering partitions data using eigenvectors of graph Laplacians built from pairwise similarities. The paper distinguishes normalized and unnormalized variants and studies their eigenvector-based sample partitions.

  • Given symmetric, nonnegative pairwise similarities, the data form an affinity matrix K, while D is the diagonal matrix of similarity degrees.
  • The two major algorithmic variants are normalized and unnormalized spectral clustering.
  • Basic spectral clustering finds the eigenvector corresponding to the second-smallest eigenvalue of the selected Laplacian problem.
  • Graph Laplacians encode graph partitioning, seeking low-weight edges between groups and high-weight edges within groups.
  • Practical implementations may use several eigenvectors and more complex partitioning rules when producing more than two clusters.
  • The paper studies how normalized and unnormalized Laplacians, whose matrices depend on sample size n, behave as n grows.

3. Informal statement of our results.

The paper shows that normalized spectral clustering converges under mild conditions, whereas unnormalized clustering requires stronger spectral assumptions that may fail and cannot be checked from finite samples.

  • Overview: Eigenvectors of discrete Laplacian operators are shown to converge to eigenfunctions of limit operators, which then define a partition of the whole data space.The finite-sample eigenvectors are interpreted as functions on the sampled points and connected to limit eigenfunctions.
  • Normalized spectral clustering: Under mild assumptions, normalized spectral clustering converges almost surely to a limit clustering of the whole data space.The result requires the first r limit eigenvalues to differ from 1 and have multiplicity 1.
  • Unnormalized spectral clustering: Unnormalized spectral clustering requires simple limit eigenvalues outside the range of the degree function for its eigenvalues, eigenvectors, and clusterings to converge.These conditions ensure the relevant eigenvalues are isolated in the limit operator's spectrum.
  • Unnormalized spectral clustering: There are similarity functions with no nonzero eigenvalue outside the degree-function range, causing unnormalized clustering eigenvectors to produce no sensible clustering.The same problem can arise when more than finitely many suitable eigenvalues are requested.
  • Implications: The unnormalized convergence condition concerns the limit case and cannot be verified on a finite sample, while normalized clustering also has convergence-rate results.For Gaussian similarity on R^d, the paper reports a rate beginning with O(1/√.
  • Practical behavior: Theoretical results are used to demonstrate practical differences between normalized and unnormalized spectral clustering.The passage states that the paper investigates how the theory influences clustering behavior in practice.

4. Prerequisites and notation.

The paper fixes assumptions and notation for sampled similarity graphs, Laplacian matrices, function ranges, operators, spectra, and perturbation results used to establish convergence.

  • General assumptions: The data space is a compact metric space with an i.i.d. sample from a probability measure, and the similarity function is symmetric, continuous, and bounded below by a positive constant.The support of the probability measure is assumed to equal the data space.
  • Matrices and notation: Finite samples define a similarity matrix, a diagonal degree matrix, and unnormalized and normalized graph Laplacian matrices.The degree matrix uses empirical averages of pairwise similarities.
  • Matrices and notation: Laplacian eigenvalues are ordered increasingly with the trivial first eigenvalue equal to 0, while transposes, primes, and the identity matrix have fixed notation.The ordering respects multiplicities.
  • Function notation: The restriction operator maps a continuous function to its values at the sampled points, and rg(f) denotes the range of a real-valued function.For connected X and continuous f, the range is the interval between its infimum and supremum.
  • Spectral notation: The spectrum is divided into discrete isolated finite-multiplicity eigenvalues and essential spectrum, which compact perturbations do not change.Spectral projections are defined for isolated spectral parts and project onto the associated invariant subspaces.
  • Operator convergence: Pointwise, compact, operator-norm, collectively compact, and collectively compact convergence are defined for bounded linear operators.Operator-norm and collectively compact convergence imply compact convergence.
  • Perturbation theory: Compact convergence yields convergence of isolated finite-multiplicity eigenvalues and spectral projections, while simple eigenvalues additionally yield eigenvector convergence up to sign.The perturbation result applies when the limiting eigenvalue is isolated from the rest of the spectrum.
  • Perturbation theory: The paper introduces quantitative perturbation theory for spectral projections to derive convergence rates.The stated theorem concerns collectively compactly convergent compact operators and isolates a nonzero eigenvalue.

5. Convergence of normalized spectral clustering.

For normalized spectral clustering, the analysis studies eigenvectors of normalized Laplacians through operators on a common function space, establishing almost-sure convergence to limit eigenfunctions.

  • Approach: The normalized case is analyzed through the normalized Laplacian, using its relationship with the generalized eigenproblem L_nv = λD_nv.Results for the other equivalent formulations can be carried over naturally.
  • Approach: The main technical issue is that eigenvectors from different sample sizes lie in different-dimensional spaces, so ordinary convergence does not apply directly.The desired comparison is between a sample eigenvector and the restriction of a continuous limit function to the sampled points.
  • Approach: The second sample eigenvector is treated as the eigenfunction of a random operator on C(X), and convergence reduces to uniform convergence of that eigenfunction to a fixed function.Because the operators and eigenfunctions are random, the convergence is almost sure.
  • Approach: The operator construction is used to establish convergence of normalized Laplacian eigenvectors in a common function-space framework.The passage identifies the limit operator U′ as the operator whose eigenfunction represents the limiting behavior.

Step 1 [Relating the matrices L′

The paper relates finite-sample normalized graph-Laplacian matrices to operators on C(X), then transfers operator spectral convergence to matrix eigenvectors and clustering sets.

  • Operator construction: The analysis studies random operators on C(X) whose restrictions to sampled points behave like normalized graph-Laplacian matrices.This replaces direct matrix convergence with convergence of corresponding operators and then recovers matrix eigenvectors from operator eigenfunctions.
  • Spectral correspondence: Eigenfunctions and eigenvectors of the normalized operator and graph Laplacian correspond one-to-one when the eigenvalue is not 1.The restriction relation is v = ρ_nf, and the reverse construction is given by the paper’s equation (1).
  • Compact convergence: The empirical degree functions converge uniformly to the true degree function because the relevant function classes are Glivenko–Cantelli.Uniform convergence, together with uniform continuity on compact X, supports the stronger operator convergence used later.
  • Compact convergence: Under the general assumptions, the normalized random operators converge pointwise and collectively compactly almost surely to their limit operators.These convergence statements provide the operator-level basis for spectral convergence.
  • Spectral convergence: For an isolated limit eigenvalue, eigenvalues and spectral projections converge almost surely; simple eigenvalues additionally yield eigenvector convergence up to sign.The sampled eigenvector coordinates converge uniformly to the limiting eigenfunction, and threshold-based clustering sets converge in probability.

6. Rates of convergence in the normalized case.

The normalized spectral-clustering eigenvector rate is controlled by an empirical-process supremum, yielding an O(1/√n) rate for Gaussian kernels under the stated assumptions.

  • Rate theorem: Theorem 16 bounds normalized spectral-clustering eigenfunction convergence by the supremum empirical-process deviation over F = K ∪ (u · H) ∪ (H · H).The constant depends only on the similarity function, the limit-operator spectrum, and the selected eigenvalue.
  • Rate theorem: The rate of normalized eigenvector convergence is at least as good as the convergence rate of the empirical-process supremum indexed by F.Covering numbers, VC dimension, and Rademacher complexities can be used to control this supremum.
  • Gaussian-kernel example: O(1/√n) is obtained for normalized eigenfunctions with a Gaussian kernel through an entropy bound for the relevant function class.The paper notes that the covering-number approach is simple and may not provide the sharpest possible bounds.
  • Comparison: The unnormalized case can also admit convergence-rate results, but its required operator assumptions differ because only compact, not collectively compact, convergence is available.The authors do not discuss those rates further because they recommend normalized spectral clustering.
  • Gaussian-kernel example: The Gaussian-kernel rate follows by bounding covering numbers for K and extending those bounds to K ∪ (u · H) ∪ (H · H).The entropy calculation is combined with Theorem 16 to transfer the empirical-process rate to the eigenfunctions.

7. The unnormalized case.

Unnormalized spectral clustering converges only for isolated limit eigenvalues outside the range of the degree function, a condition that can fail because of continuous spectrum.

  • Scope and limitations: When the required conditions fail, the eigenvectors of unnormalized spectral clustering do not contain useful information about clustering the data space.This is the paper’s stated practical boundary for the unnormalized approach.
  • Convergence theorem: The unnormalized convergence theorem requires the eigenvalue λ to lie outside rg(d) and be isolated in the limit operator’s spectrum.Under this condition, the theorem establishes convergence of eigenvalues, spectral projections, and, for simple eigenvalues, eigenvectors.
  • Convergence theorem: Eigenvalues and spectral projections of the scaled unnormalized Laplacian converge almost surely under the theorem’s isolation condition.The spectral projections associated with the relevant isolated spectral sets converge to the projection for the limit eigenvalue.
  • Convergence theorem: For a simple limit eigenvalue, unnormalized Laplacian eigenvectors converge almost surely up to sign, and their threshold partitions converge in probability.The coordinate vectors converge uniformly to the corresponding limit eigenfunction on the sampled points.
  • Scope and limitations: Unlike the normalized case, the unnormalized isolation condition can fail because the limit operator has a large continuous spectrum.The paper states that this failure leads to serious problems and that the conditions are often violated in practice.

3. If v is an eigenvector of the matrix 1

The paper relates finite-sample Laplacian eigenvectors to limit operators through spectral convergence, with isolated-eigenvalue conditions governing when eigenvector convergence applies. This condition is substantially weaker for normalized than unnormalized spectral clustering.

  • The essential spectrum of the unnormalized limit operator U_n equals rg(d_n), and its eigenvalues are nonnegative with accumulation only there.The analogous spectral statements hold for U.
  • Eigenvalues of U_n outside rg(d_n) correspond one-to-one with eigenvalues of the finite normalized matrix 1/n L_n.This correspondence requires λ /∉rg(d_n).
  • U_n converges compactly to U almost surely by separately establishing convergence of its integral and multiplication-operator components.The integral operators converge collectively compactly, while multiplication operators converge in operator norm via Glivenko–Cantelli.
  • Normalized limit-operator eigenvalues are isolated whenever λ ≠ 1, whereas unnormalized eigenvalues must satisfy λ /∉rg(d).Both conditions ensure spectral isolation, which is required for perturbation-based eigenvector convergence.

8. Nonisolated eigenvalues.

The unnormalized method can fail when relevant limit eigenvalues are not isolated from the continuous spectrum rg(d). In such cases, finite-precision eigensolvers can return eigenvectors concentrated at minimum-degree points rather than informative cluster structure, while normalized eigenvectors remain informative in the illustrated examples.

  • Theoretical results: There are similarity functions for which the only eigenvalue of U outside rg(d) is the trivial eigenvalue 0.For k(x,y) = xy and the specified piecewise-constant density, this holds analytically.
  • Theoretical results: When λ2 /∈rg(d) fails, the second eigenvalue of 1/n L_n converges to min_x∈X d(x), and its eigenfunction approximates a point-mass indicator.With multiple minimizers, the corresponding eigenspace can contain linear combinations of delta-functions.
  • Theoretical results: Finite-precision eigensolvers may mistake approximate eigenfunctions for eigenvectors across rg(d), eventually populating that interval with apparent eigenvalues.The construction uses localized functions around points attaining a chosen degree value.
  • Theoretical results: The condition λ /∉rg(d) can fail in practical settings and cannot be checked exactly without knowing the underlying distribution.The paper recommends estimating the critical region by [min_i d_i/n, max_i d_i/n] and checking relevant eigenvalues against it.
  • Theoretical results: Under analytic similarity and density assumptions, with finitely many degree minimizers, U has only finitely many eigenvalues outside rg(d).This establishes finiteness of the discrete spectrum outside the continuous range, not its sufficiency for clustering.
  • Empirical results: For four well-separated Gaussian clusters using a Gaussian kernel, normalized eigenvectors remain informative for σ = 1, 5, and 50, unlike unnormalized eigenvectors near or inside rg(d).In the unnormalized case, informative eigenvectors can separate cluster groupings, but eigenvectors near rg(d) become Dirac-like; the normalized plots show no such Dirac form.
  • Conclusion: The paper concludes that normalized eigenvectors converge under standard assumptions, whereas unnormalized convergence requires eigenvalues below the continuous spectrum.When that condition fails, the corresponding eigenvector information is misleading for clustering.

9. Conclusion.

The paper recommends normalized spectral clustering whenever possible. If unnormalized clustering is used, eigenvalues should be checked against the continuous spectrum and corresponding eigenvectors discarded when they are not sufficiently separated.

  • Normalized rather than unnormalized spectral clustering should be used whenever possible from a statistical perspective.
  • For unnormalized clustering, eigenvalues used by the algorithm should lie significantly below the continuous spectrum.Eigenvectors failing this check should be discarded because they do not provide clustering information.
Loading 0804.0678v1…