PaperlayerView exact revision on arXiv

Source-linked AI summary

A Tutorial on Spectral Clustering

Ulrike von Luxburg

arXiv:0711.0189v1cs.DScs.LG

TL;DR

Spectral clustering’s behavior and rationale are not immediately clear despite its popularity. This tutorial explains graph Laplacians and derives common algorithms from multiple perspectives, illustrating how eigenvectors encode cluster structure while discussing important limitations.

  • Problem

    The tutorial addresses why spectral clustering works and what it does, questions left unclear despite its popularity and practical advantages.

  • Method

    The paper gives a self-contained treatment of similarity graphs and graph Laplacians, then derives common spectral clustering algorithms from multiple viewpoints.

  • Results

    Eigenvectors of graph Laplacians carry cluster information, enabling thresholding to separate groups in the illustrated graph.

  • Takeaways & Limitations

    Spectral clustering can be understood through graph structure, Laplacian properties, optimization, embeddings, and perturbation arguments.

  • Takeaways & Limitations

    The relaxation used by unnormalized spectral clustering has no guarantee of matching the exact RatioCut solution and can differ arbitrarily.

Abstract

from arXiv · show

In recent years, spectral clustering has become one of the most popular modern clustering algorithms. It is simple to implement, can be solved efficiently by standard linear algebra software, and very often outperforms traditional clustering algorithms such as the k-means algorithm. On the first glance spectral clustering appears slightly mysterious, and it is not obvious to see why it works at all and what it really does. The goal of this tutorial is to give some intuition on those questions. We describe different graph Laplacians and their basic properties, present the most common spectral clustering algorithms, and derive those algorithms from scratch by several different approaches. Advantages and disadvantages of the different spectral clustering algorithms are discussed.

1 Introduction

This section introduces spectral clustering as a tutorial for understanding why the method works. It presents a self-contained, from-scratch treatment requiring only basic linear algebra rather than a comprehensive literature review.

  • 1 Introduction: The tutorial introduces spectral clustering within the broader use of clustering for exploratory data analysis across many scientific fields.Clustering is used to identify groups of similar behavior in empirical data, with applications spanning statistics, computer science, biology, social sciences, and psychology.
  • 1 Introduction: The tutorial is designed as a self-contained introduction that derives spectral clustering from scratch and presents different perspectives on why it works.Its stated goal is to provide readers with multiple points of view on the method’s operation.
  • 1 Introduction: The presentation assumes only basic linear algebra and does not attempt to provide a concise review of the entire spectral-clustering literature.The authors explain that the literature is too extensive for a concise comprehensive review.

2 Similarity graphs

Similarity graphs represent data points through pairwise similarities, with clustering aiming to group similar points and separate dissimilar ones. The section defines weighted graph quantities and surveys ε-neighborhood, k-nearest-neighbor, and fully connected constructions used in spectral clustering.

  • Similarity graph representation: Similarity graphs encode pairwise relationships so points within groups are similar and points across groups are dissimilar.This representation is useful when pairwise similarities are the available information.
  • Graph definitions: A weighted undirected graph uses non-negative edge weights wij, a symmetric adjacency matrix W, and vertex degrees collected in diagonal matrix D.An absent edge is represented by wij = 0.
  • Graph constructions: The ε-neighborhood graph connects points whose pairwise distances are smaller than ε and is usually unweighted.Connected distances are bounded by ε and are roughly on the same scale.
  • Graph constructions: A k-nearest-neighbor graph connects each point to its k nearest neighbors, then symmetrizes the resulting directed neighborhood relation.Undirected edges can be formed when either endpoint is among the other’s k nearest neighbors.
  • Graph constructions: A fully connected graph links every pair with positive similarity and weights edges by sij, making it useful when similarity itself models local neighborhoods.The Gaussian similarity function uses σ to control neighborhood width.
  • Graph constructions: All surveyed graph constructions are used in spectral clustering, but theoretical results on how graph choice affects clustering results are not known.The paper defers discussion of their behavior to Section 8.

3 Graph Laplacians and their basic properties

This section defines unnormalized and normalized graph Laplacians and summarizes their key spectral properties. In particular, the multiplicity of eigenvalue 0 identifies the graph’s connected components, with component indicators spanning the corresponding eigenspaces.

  • Graph Laplacians: Graph Laplacians are the main mathematical tools for spectral clustering, and the literature uses multiple conventions for which matrix is called the graph Laplacian.The section distinguishes unnormalized and normalized variants.
  • Unnormalized graph Laplacian: The unnormalized Laplacian L is symmetric and positive semi-definite, with n non-negative real eigenvalues ordered as 0 = λ1 ≤ λ2 ≤ . . . ≤ λn.Its smallest eigenvalue is 0, with the constant one vector 1 as an eigenvector.
  • Unnormalized graph Laplacian: The multiplicity k of eigenvalue 0 of L equals the number of connected components, whose indicator vectors 1A1, . . . , 1Ak span its zero-eigenspace.For eigenvalue 0, eigenvectors are constant on each connected component.
  • Normalized graph Laplacians: The normalized Laplacians Lsym and Lrw are related through eigenvector transformations and generalized eigenproblems involving L u = λD u.An eigenvector u of Lrw corresponds to w = D1/2u for Lsym.
  • Normalized graph Laplacians: For both normalized Laplacians, the multiplicity of eigenvalue 0 equals the number of connected components; their zero-eigenspaces use component indicators, scaled by D1/2 for Lsym.For Lrw, the zero-eigenspace is spanned by 1Ai; for Lsym, it is spanned by D1/2 1Ai.

4 Spectral Clustering Algorithms

The section presents three spectral clustering algorithms that transform data through graph-Laplacian eigenvectors before applying k-means, differing by their use of unnormalized, random-walk, or symmetric-normalized Laplacians. A toy example illustrates how graph connectivity and subsequent eigenvectors encode cluster information.

  • Unnormalized spectral clustering: Unnormalized spectral clustering computes the first k eigenvectors of L, uses their row vectors as y_i, and clusters them with k-means.The input is a similarity matrix S and a requested number k of clusters; the method first constructs a weighted similarity graph.
  • Normalized spectral clustering: Shi–Malik normalized spectral clustering computes generalized eigenvectors of Lu = λDu, equivalent to eigenvectors of the random-walk normalized Laplacian L_rw, then applies k-means.It follows the same row-vector embedding pattern as the unnormalized algorithm.
  • Normalized spectral clustering: Ng–Jordan–Weiss normalized spectral clustering computes the first k eigenvectors of L_sym, row-normalizes their matrix to norm 1, and clusters the resulting points with k-means.The row normalization is the additional step distinguishing this algorithm from the other two.
  • Common structure: All three algorithms map abstract data points x_i to vectors y_i ∈ R^k, making clusters easier to detect through graph-Laplacian properties.The transformed representation is the central common mechanism across the algorithms.
  • Toy example: In the toy example, disconnected nearest-neighbor graph components yield eigenvectors characterized by graph connectivity, while a fully connected graph has one zero eigenvalue and later eigenvectors carry cluster information.The fully connected graph has one connected component because the Gaussian similarity function is always positive.

5 Graph cut point of view

Spectral clustering reformulates graph partitioning as balanced cut minimization and solves relaxed RatioCut or Ncut objectives through graph-Laplacian eigenvectors. The approach addresses mincut’s tendency to isolate individual vertices but provides no guarantee that the relaxed solution is close to the exact optimum.

  • Graph cut motivation: Graph clustering seeks partitions with low-weight edges between groups and high-weight edges within groups.This expresses dissimilarity across clusters and similarity within them.
  • Graph cut motivation: Mincut directly minimizes cross-group edge weight, but often produces an unsatisfactory partition by separating one vertex from the rest.For k = 2, mincut is efficiently solvable, yet this degeneracy makes it unsuitable in many practical cases.
  • Balanced cuts: Balancing clusters by vertex counts or volumes yields RatioCut and Ncut objectives, but introducing these conditions makes the problem NP hard.Relaxing RatioCut leads to unnormalized spectral clustering, whereas relaxing Ncut leads to normalized spectral clustering.
  • RatioCut relaxation: For two clusters, relaxing RatioCut’s discrete indicator constraint gives the second eigenvector of the unnormalized Laplacian, whose coordinates are then clustered into two groups.This procedure is the unnormalized spectral clustering algorithm for k = 2.
  • Ncut relaxation: For Ncut, a change of variables converts the relaxed problem to the normalized Laplacian, yielding its second eigenvector or the corresponding generalized eigenvector.For k > 2, the analogous trace minimization uses multiple eigenvectors under orthogonality constraints.
  • Limitations: The relaxed spectral solution has no guarantee of matching the exact cut optimum, and its excess RatioCut value can be arbitrarily large.This limitation applies when comparing the unnormalized spectral clustering partition with the exact RatioCut solution.

6 Random walks point of view

The random-walk view interprets spectral clustering as finding partitions where walks remain within clusters and rarely cross between them. Commute distances provide a related Laplacian-based embedding intuition, but their connection to spectral clustering is generally loose.

  • Random-walk interpretation: Spectral clustering seeks graph partitions in which a random walk stays within each cluster and seldom jumps between clusters.This interpretation complements the graph-cut perspective.
  • Random-walk interpretation: For a stationary random walk on a connected, non-bipartite graph, Ncut equals the sum of cross-cluster transition probabilities in both directions.Thus minimizing Ncut favors cuts that make transitions between the two sides rare.
  • Commute distance: The commute distance c_ij is the expected time for a random walk to travel from vertex v_i to v_j and back.It is also called resistance distance and has properties useful for machine learning.
  • Commute distance: The square root of commute distance can be treated as a Euclidean distance, enabling an embedding whose Euclidean distances coincide with graph commute distances.This construction uses the generalized inverse L† of the graph Laplacian.
  • Relation to spectral embedding: Commute-time and spectral embeddings differ because the former scales Laplacian eigenvectors by inverse eigenvalues, emphasizing eigenvectors with small eigenvalues.They may behave similarly in some situations, but the embeddings are not identical.
  • Relation to spectral embedding: Without further assumptions, the relation between commute distance and spectral clustering remains loose rather than a precise mathematical equivalence.The paper notes that stronger assumptions, such as a strictly positive definite similarity function, might tighten the connection.

7 Perturbation theory point of view

Perturbation theory explains spectral clustering by showing that small graph perturbations preserve relevant eigenspaces when the eigengap is sufficiently large. This supports k-means separation in nearly ideal graphs, while highlighting limitations for some matrices and low-degree vertices.

  • Perturbation framework: For nearly ideal graphs, spectral-clustering embedding points remain close to component-indicator vectors, so k-means can still separate clusters when perturbations are small.In the ideal case, all points from one connected component coincide at the same indicator vector.
  • Perturbation framework: The Davis-Kahan theorem bounds distances between eigenspaces of symmetric matrices after perturbation, using canonical-angle-based subspace distances.It applies to A and its perturbed version A+H under Frobenius or two-norm measures.
  • Perturbation framework: Choosing the Davis-Kahan eigenvalue interval requires the first k eigenvalues of both Laplacians to remain included; smaller perturbations and larger eigengaps make this easier.If the perturbation is too large or the eigengap too small, the comparison may need to include different numbers of eigenvalues and becomes weaker.
  • Cautions: Perturbation arguments require meaningful eigenvalue ordering and eigenvector entries that remain safely separated from zero for reliable cluster interpretation.These conditions are automatic for Laplacians’ component-associated zero eigenvectors but may fail for similarity or adjacency matrices.
  • Cautions: Unnormalized spectral clustering and normalized clustering with Lrw are well justified, whereas Lsym requires caution when vertices have very low degrees.For Lsym, low-degree vertices can produce particularly small eigenvector entries and problematic cluster assignments.

8 Practical details

This section raises awareness of practical implementation issues in spectral clustering, including choices and parameter settings. It points to the broader literature for thorough studies of real-world behavior.

  • 8 Practical details: Implementing spectral clustering involves several choices and parameters that must be set.The section introduces these issues as practical concerns arising during implementation.
  • 8 Practical details: The discussion is intended mainly to raise awareness of general implementation problems.It is presented as a brief overview rather than a thorough behavioral study.
  • 8 Practical details: Thorough studies of spectral clustering across real-world tasks are left to the literature.The section refers readers to existing literature for such analyses.

8.1 Constructing the similarity graph

Constructing the similarity graph requires a meaningful similarity function and careful choices about graph type and connectivity. These choices strongly affect spectral clustering, yet theoretical guidance remains limited.

  • Similarity function: A meaningful similarity function should identify points that are closely related in the underlying application, because it induces the graph’s local neighborhoods.The similarity function must make “very similar” points correspond to genuinely close relationships in the data’s application.
  • Graph types: The ε-neighborhood graph is difficult to tune across different scales: with ε = 0.3, the middle moon is tightly connected while the Gaussian is barely connected.This scale mismatch occurs when distances between data points differ across regions of the space.
  • Graph types: The k-nearest neighbor graph connects points across different scales but can split into disconnected components when distant high-density regions are present.In the example, it connects the low-density Gaussian with the high-density moon, while the two moons can form separate components.
  • Graph types: The mutual k-nearest neighbor graph connects within constant-density regions while avoiding connections between regions of different densities.It can therefore act across different scales without mixing those scales, but disconnected parts are always selected as clusters.
  • Connectivity parameters: Connectivity parameters should generally avoid producing more connected components than requested clusters, because spectral clustering then returns those components as clusters.For k-nearest neighbor graphs, a rule of thumb is to seek a connected graph or choose k in the order of log(n) for very large graphs.
  • Parameter sensitivity: Spectral clustering can be quite sensitive to the similarity graph and its parameters, while existing recommendations lack firm theoretical grounding.The paper notes that no systematic study had established well-justified rules of thumb.

8.2 Computing the eigenvectors

Spectral clustering computes the first k eigenvectors of a potentially large graph Laplace matrix, with sparse neighborhood graphs enabling efficient numerical methods. Repeated eigenvalues may yield different basis vectors, but the resulting eigenspace still preserves cluster structure for k-means.

  • Computing the eigenvectors: Sparse k-nearest neighbor and ε-neighborhood graph Laplacians enable efficient computation of their first k eigenvectors.Power and Krylov-subspace methods, including Lanczos, are among the standard approaches for sparse matrices.
  • Computing the eigenvectors: When an eigenvalue has multiplicity greater than one, numerical eigensolvers may return vectors different from the cluster indicator vectors.For k disconnected clusters, eigenvalue 0 has multiplicity k, and its eigenspace is spanned by the cluster indicator vectors.
  • Computing the eigenvectors: All vectors in the cluster-indicator eigenspace are piecewise constant on clusters, so k-means can use them to reconstruct the clusters.Such vectors have the form u = Σ_i a_i1_Ai for coefficients a_i.

8.3 The number of clusters

Choosing the number of clusters is a general challenge, and spectral clustering offers the eigengap heuristic: select k so the first k eigenvalues are small while the next is relatively large. The choice of cluster number also interacts with the neighborhood graph’s connectivity parameters.

  • The number of clusters: Choosing k is a general problem for clustering algorithms, with established likelihood-based criteria mainly available in model-based settings.Such criteria treat data log-likelihood in frequentist or Bayesian frameworks.
  • The number of clusters: The eigengap heuristic selects k such that λ1, . . . , λk are very small and λk+1 is relatively large.This tool is specifically designed for spectral clustering and applies to all three graph Laplacians.
  • The number of clusters: The heuristic is illustrated on increasingly difficult Gaussian toy data using a 10-nearest neighbor graph and the normalized Laplacian Lrw.The experiment varies clustering difficulty by increasing Gaussian variance and plots the Laplacian eigenvalues.
  • The number of clusters: Cluster-number selection and neighborhood-graph connectivity affect each other, because a graph with k0 connected components validly supports choosing k0 clusters.Once the neighborhood graph is connected, the relationship between cluster number and connectivity parameters becomes unclear.

8.4 The k-means step

The spectral clustering algorithms use k-means to obtain a final partition from eigenvector representations, but this choice is not principled or uniquely determined. Alternative post-processing methods instead exploit meaningful Euclidean distances or approximate the eigenvector subspace with piecewise constant vectors.

  • The k-means step: All three presented spectral clustering algorithms use k-means as the final step for extracting a partition from the real-valued eigenvector matrix.The tutorial notes that this step should be simple when clusters are well expressed.
  • The k-means step: The final clustering algorithm is somewhat arbitrary, although Euclidean distances between eigenvector-representation points y_i provide a meaningful quantity.These distances relate to graph commute distance and more general diffusion distances.
  • The k-means step: Alternatives to k-means include hyperplane-based methods and approximating the span of the first k eigenvectors with piecewise constant vectors.The latter approach leads to minimizing certain Euclidean distances.

8.5 Which graph Laplacian should be used?

The choice of graph Laplacian should begin with the similarity graph’s degree distribution: when degrees are similar, all Laplacians perform similarly, whereas normalized methods are preferable for broadly varying degrees. Normalized spectral clustering implements both between- and within-cluster objectives, has clearer statistical convergence, and the paper advocates Lrw over Lsym.

  • When most vertices have approximately equal degrees, all three graph Laplacians are very similar and work equally well for clustering.
  • Normalized spectral clustering implements both minimizing between-cluster similarity and maximizing within-cluster similarity, whereas unnormalized spectral clustering implements only the first objective.Ncut promotes small cuts and large cluster volumes, aligning its objective with within-cluster similarity.
  • Both normalized spectral clustering algorithms have provable consistency, with Lsym converging to an operator whose eigenvalues and eigenvectors support convergence of the clustering.The induced partition can be interpreted through a diffusion process on the data space.
  • Unnormalized spectral clustering can fail to converge or converge to trivial single-point clusters, problems that do not occur for Lrw or Lsym.The paper therefore recommends avoiding unnormalized spectral clustering from a statistical perspective.
  • The paper advocates Lrw over Lsym because Lrw eigenvectors are cluster indicator vectors, while Lsym eigenvectors are additionally multiplied by D1/2 and offer no computational advantage.

9 Outlook and further reading

The section places spectral clustering in its historical and machine-learning context, emphasizing its flexibility and efficient implementation. It also highlights broader graph-Laplacian applications and theoretical connections to continuous operators and graph structure.

  • Historical origins: Spectral clustering originated with Donath and Hoffman’s adjacency-matrix partitioning and Fiedler’s use of the Laplacian’s second eigenvector for bipartitioning.These foundational developments date to 1973.
  • Machine-learning developments: Machine-learning researchers popularized spectral clustering and extended it to co-clustering, side information, and connections with weighted kernel-k-means.The cited works include Shi and Malik, Ng et al., Meila and Shi, Ding, Dhillon, and Joachims.
  • Advantages: Spectral clustering succeeds because it makes few assumptions about cluster shape, handling intertwined spirals unlike k-means, while remaining efficient when the similarity graph is sparse.Its scalability depends on ensuring graph sparsity.
  • Broader applications: Graph Laplacians support tasks beyond clustering, including semi-supervised learning and manifold reconstruction, by regularizing functions whose values vary smoothly across strongly connected data points.The regularizer is the quadratic form f′Lf.
  • Theoretical connections: Theory shows that graph Laplacians built from randomly sampled similarity graphs converge to continuous Laplace or Laplace-Beltrami operators on the underlying space.The cited convergence results include work by Belkin, Lafon, Hein, Audibert, von Luxburg, Belkin and Niyogi, and others.
Loading 0711.0189v1…