# spectral clustering

*Entry of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org) (course edition), by Alexander Jung, Aalto University. CC BY 4.0. Updated 2026-11-19. [HTML](https://dictionaryofml.org/terms/specclustering.html) · [typeset PDF](https://dictionaryofml.org/terms/specclustering.pdf) · [LaTeX](https://dictionaryofml.org/terms/specclustering.tex) · [Python demo](https://dictionaryofml.org/terms/specclustering.py) · [notebook](https://dictionaryofml.org/terms/specclustering.ipynb)*

Math is LaTeX with the book's macros expanded, so no notation package is needed to read it.

## Abstract

Spectral clustering is a graph clustering method that computes the clusters of a dataset from the eigenvectors of the Laplacian matrix of a graph whose nodes are the data points and whose edge weights express their similarity. The Laplacian matrix is positive semi-definite, and the multiplicity of its eigenvalue $0$ equals the number of connected components of the graph, with their indicator vectors as eigenvectors. For $k$ clusters, the entries of the $k$ eigenvectors with the smallest eigenvalues form a new feature vector for each node, and k-means on these feature vectors delivers the clusters. For two clusters, the method thresholds the Fiedler vector. Spectral clustering is a relaxation of the ratio cut, which divides the total weight of the edges between the clusters by their sizes, and the second-smallest eigenvalue is a lower bound on the ratio cut of every bipartition. Unlike k-means on the raw feature vectors, spectral clustering finds clusters that are connected in the graph but not convex in the feature space. The number of clusters and the construction of the graph are its hyperparameters.

## Definition

Each day of 2024 at the weather station Krems an der Donau is a data point with a feature vector ${\mathbf x} \in \mathbb{R}^{2}$ that holds the morning minimum and the maximum daytime temperature of the day. Connecting each day with its ten nearest days, measured by the Euclidean distance between their feature vectors, turns the $366$ days into the nodes $i = 1, \ldots, n$ of an k-nearest-neighbor graph $\mathcal{G}$ with $n = 366$ nodes and $2209$ edges (Fig. 2(a)). A cluster of this graph is a set of days that are joined by many edges among themselves and by few edges to the remaining days. Spectral clustering is a graph clustering method that finds such clusters from the eigenvectors of the Laplacian matrix of the graph (Hastie et al., 2009, Sect. 14.5.3; Luxburg, 2007; Ng et al., 2001; Shi and Malik, 2000).

Consider a similarity graph of the dataset: a weighted graph $\mathcal{G}$ with nodes $i = 1, \ldots, n$, one node per data point, and edge weights $A_{i,i'} = A_{i',i}
\geq 0$ that express the similarity between the data points $i$ and $i'$; a missing edge has weight $0$. The edge weights form the adjacency matrix ${\mathbf A}^{(\mathcal{G})} \in \mathbb{R}^{n \times n}$, and the node degree $d^{(i)} = \sum_{i'=1}^{n}
A_{i,i'}$ of node $i$ is the sum of its edge weights. The Laplacian matrix of $\mathcal{G}$ is

\begin{equation}
\tag{1}
{\mathbf L}^{(\mathcal{G})} := \mathbf{D} - {\mathbf A}^{(\mathcal{G})}
\quad \text{with } \mathbf{D} :=
\operatorname{diag}\big\{d^{(1)}, \ldots,
d^{(n)}\big\} \text{.}
\end{equation}

For every vector ${\mathbf u} \in \mathbb{R}^{n}$ with entries $u_{i}$, the Laplacian matrix Eq. (1) satisfies

\begin{equation}
\tag{2}
{\mathbf u}^{\top} {\mathbf L}^{(\mathcal{G})} {\mathbf u} = \frac{1}{2}
\sum_{i=1}^{n} \sum_{i'=1}^{n}
A_{i,i'}
\big( u_{i} - u_{i'} \big)^{2} \text{,}
\end{equation}

a weighted sum of squared differences across the edges (Luxburg, 2007, Prop. 1). The quadratic form Eq. (2) is never negative, so ${\mathbf L}^{(\mathcal{G})}$ is a symmetric matrix that is positive semi-definite. It has an eigenvalue decomposition ${\mathbf L}^{(\mathcal{G})} = \mathbf{V} {\boldsymbol \Lambda} \mathbf{V}^{\top}$ with an orthogonal matrix $\mathbf{V} = \big( {\mathbf v}^{(1)}, \ldots, {\mathbf v}^{(n)} \big)$ of eigenvectors and with eigenvalues $0 = \lambda_{1} \leq \lambda_{2} \leq \ldots \leq \lambda_{n}$. The constant vector is an eigenvector for the eigenvalue $0$, since every row of ${\mathbf L}^{(\mathcal{G})}$ sums to zero. More generally, the multiplicity of the eigenvalue $0$ is the number of connected components of $\mathcal{G}$, and the indicator vectors of the components span its eigenvectors (Luxburg, 2007, Prop. 2). The reason is the quadratic form Eq. (2): ${\mathbf L}^{(\mathcal{G})} {\mathbf u} = \mathbf{0}$ forces $u_{i} = u_{i'}$ across every edge, so ${\mathbf u}$ is constant on each component. Fig. 1 shows an undirected graph with two components; its two eigenvectors for the eigenvalue $0$ place the nodes of each component on a single point of a scatterplot.

![Figure 1 of the entry specclustering](https://dictionaryofml.org/terms/fig/specclustering-fig1.svg)

*Figure 1: (a) An undirected graph $\mathcal{G}$ with four nodes $i = 1, 2, 3, 4$ and unit edge weights, each node a data point; node $4$ has no edge, so the graph has two connected components. (b) Its Laplacian matrix ${\mathbf L}^{(\mathcal{G})} \in \mathbb{R}^{4 \times 4}$, whose eigenvalue $0$ has multiplicity two. (c) Scatterplot of the nodes using the new feature vectors $\widetilde{{\mathbf x}}^{(i)} = \big( v^{(1)}_{i}, v^{(2)}_{i} \big)^{\top}$: the nodes $1$, $2$, $3$ of the first component share one point (filled circle) and node $4$ sits at another (open circle). (d) The two eigenvectors ${\mathbf v}^{(1)}, {\mathbf v}^{(2)} \in \mathbb{R}^{4}$ for the eigenvalue $0$, the normalized indicator vectors of the two components*

A graph whose clusters are joined by few edges of small weight is a perturbation of a graph with several components. The eigenvectors of its smallest eigenvalues are then a perturbation of the indicator vectors (Luxburg, 2007, Sect. 7). Spectral clustering with $k$ clusters therefore uses these eigenvectors as new features: node $i$ is represented by the feature vector

\begin{equation}
\tag{3}
\widetilde{{\mathbf x}}^{(i)} := \big(
v^{(1)}_{i}, \ldots, v^{(k)}_{i}
\big)^{\top} \in \mathbb{R}^{k} \text{,}
\end{equation}

which holds the $i$th entries of the $k$ eigenvectors with the smallest eigenvalues. k-means is then applied to the feature vectors $\widetilde{{\mathbf x}}^{(1)}, \ldots, \widetilde{{\mathbf x}}^{(n)}$ (Luxburg, 2007, Sect. 4). Algorithm 1 states the method in full.

![Algorithm 1 of the entry specclustering](https://dictionaryofml.org/terms/fig/specclustering-alg1.svg)

*Algorithm 1: Spectral clustering (Luxburg, 2007, Sect. 4)*

For $k = 2$ the first eigenvector is constant, so the new feature of node $i$ is its entry $v^{(2)}_{i}$ in the Fiedler vector, the eigenvector of the algebraic connectivity $\lambda_{2}$ (Fiedler, 1973). The Fiedler vector is orthogonal to the constant vector, so it has entries of both signs, and k-means on its entries amounts to a threshold. On the days at Krems, the graph is connected with $\lambda_{2} = 0.044$ and $\lambda_{3} = 0.179$, and the Fiedler vector has $190$ negative and $176$ positive entries (Fig. 2(b)). k-means on these entries delivers $192$ cold days and $174$ warm days. Every day of January, February, November, and December is a cold day, and every day from May to August is a warm day. Each of the two clusters is connected in the graph, and the two are joined by $25$ of the $2209$ edges. k-means on the raw feature vectors ${\mathbf x}^{(i)}$, whose clusters are always convex regions of the feature space, delivers almost the same hard clustering: the two methods disagree on two days of October only. The methods differ once the clusters are not convex. Data points on two concentric rings are joined by the edges of an k-nearest-neighbor graph along each ring; spectral clustering returns the rings, while k-means on the raw feature vectors cuts through them (Hastie et al., 2009, Sect. 14.5.3).

![Figure 2 of the entry specclustering](https://dictionaryofml.org/terms/fig/specclustering-fig2.svg)

*Figure 2: (a) The $366$ days of $2024$ at Krems, each a node drawn at its feature vector, and the $2209$ edges (thin gray lines) of the $10$-nearest-neighbor graph; all days are drawn, since the connectivity of the graph is what the panel shows. The two clusters found by spectral clustering with $k = 2$ are the cold days (filled circles) and the warm days (filled squares). (b) The entry $v^{(2)}_{i}$ of the Fiedler vector for every day (thin curve) against the day of the year, with every $18$th day, $21$ days in all, marked as a cold day (circles) or a warm day (squares); the dashed line is the zero level. Data generated by pythondemos/specclustering.py*

Spectral clustering approximately solves a graph partitioning problem (Luxburg, 2007, Sect. 5). For a subset $\mathcal{C} \subseteq \mathcal{V}$ of the nodes, the cut $\operatorname{cut}(\mathcal{C}) := \sum_{i \in \mathcal{C}}
\sum_{i' \notin \mathcal{C}} A_{i,i'}$ is the total weight of the edges leaving $\mathcal{C}$. The subset with the smallest cut is often a single node, so the ratio cut divides the cut by the sizes of both parts (Hagen and Kahng, 1992; Luxburg, 2007, Sect. 5),

\begin{equation}
\tag{4}
\operatorname{RatioCut}(\mathcal{C}) :=
\operatorname{cut}(\mathcal{C}) \bigg( \frac{1}{|\mathcal{C}|} +
\frac{1}{|\mathcal{V} \setminus \mathcal{C}|} \bigg) \text{.}
\end{equation}

Minimizing the ratio cut Eq. (4) over all subsets $\mathcal{C}$ is NP-hard (Luxburg, 2007, Sect. 5.1). The vector ${\mathbf u}$ with entries $u_{i} = \sqrt{|\mathcal{V} \setminus \mathcal{C}| / |\mathcal{C}|}$ for $i \in \mathcal{C}$ and $u_{i} = -\sqrt{|\mathcal{C}| / |\mathcal{V} \setminus \mathcal{C}|}$ otherwise satisfies ${\mathbf u}^{\top} {\mathbf L}^{(\mathcal{G})} {\mathbf u} = n \operatorname{RatioCut}(\mathcal{C})$ by the quadratic form Eq. (2), as well as ${\mathbf u}^{\top} \mathbf{1} = 0$ and $\left\lVert {\mathbf u} \right\rVert_{2}^{2} = n$ (Luxburg, 2007, Sect. 5.1). Dropping the requirement that ${\mathbf u}$ takes only these two values leaves the relaxed problem

\begin{equation}
\tag{5}
\min_{{\mathbf u} \in \mathbb{R}^{n}} {\mathbf u}^{\top} {\mathbf L}^{(\mathcal{G})} {\mathbf u}
\quad \text{subject to } {\mathbf u}^{\top} \mathbf{1} = 0
\text{ and } \left\lVert {\mathbf u} \right\rVert_{2}^{2} = n \text{,}
\end{equation}

and the relaxed problem Eq. (5) has the minimum $n \lambda_{2}$, attained at $\sqrt{n}\, {\mathbf v}^{(2)}$ by the Rayleigh–Ritz theorem (Luxburg, 2007, Sect. 5.1). Thresholding the Fiedler vector turns this minimizer back into a subset, and every subset has a ratio cut of at least $\lambda_{2}$. On the days at Krems, the spectral bipartition has a ratio cut of $0.274$, the bipartition of k-means on the raw feature vectors one of $0.383$ (it cuts $35$ edges), and a random bipartition one of $12.5$, against $\lambda_{2} = 0.044$. For general $k$, the same relaxation of the ratio cut leads to the first $k$ eigenvectors and the feature vector Eq. (3) (Luxburg, 2007, Sect. 5.2). Replacing $|\mathcal{C}|$ by the sum of the node degrees in $\mathcal{C}$ gives the normalized cut (Shi and Malik, 2000), whose relaxation leads to the eigenvectors of the normalized Laplacian matrix $\mathbf{D}^{-1} {\mathbf L}^{(\mathcal{G})}$ (Luxburg, 2007, Sect. 5.3). A variant uses the eigenvectors of $\mathbf{D}^{-1/2} {\mathbf L}^{(\mathcal{G})} \mathbf{D}^{-1/2}$ and scales each feature vector Eq. (3) to unit norm (Ng et al., 2001).

Spectral clustering is not a fixed-point iteration: the eigenvalue decomposition is computed once, and iterations occur only in the k-means step. That step is empirical risk minimization with the clustering error measured in the feature vectors Eq. (3) rather than in the raw ones. The learned hypothesis assigns a cluster to each node of the given graph only; a new data point needs a new node, a new Laplacian matrix, and a new eigenvalue decomposition. The hyperparameters are the number $k$ of clusters and the construction of the graph: how many neighbors the k-nearest-neighbor graph connects, or the bandwidth of a Gaussian kernel that turns distances into edge weights (Luxburg, 2007, Sect. 8.1). A gap in the spectrum, as between $\lambda_{2} = 0.044$ and $\lambda_{3} = 0.179$ at Krems, is the usual informal guide to $k$ (Luxburg, 2007, Sect. 8.3); with $k = 3$, the days at Krems split into $107$ cold, $170$ mild, and $89$ warm days, each cluster connected in the graph.

Spectral clustering is used for image segmentation, where the nodes are pixels or patches and the edge weights decrease with the difference in color and in position (Shi and Malik, 2000), and for community detection in social networks, where the edges are given and no feature vector is needed (Fortunato, 2010).

**See also:** [clustering](https://dictionaryofml.org/terms/clustering.html), [graph clustering](https://dictionaryofml.org/terms/graphclustering.html), [cluster](https://dictionaryofml.org/terms/cluster.html), [$k$-means](https://dictionaryofml.org/terms/kmeans.html), [clustering error](https://dictionaryofml.org/terms/clusteringerror.html), [hard clustering](https://dictionaryofml.org/terms/hardclustering.html), [Laplacian matrix](https://dictionaryofml.org/terms/LapMat.html), adjacency matrix, node degree, [eigenvalue decomposition](https://dictionaryofml.org/terms/evd.html), [eigenvalue](https://dictionaryofml.org/terms/eigenvalue.html), [eigenvector](https://dictionaryofml.org/terms/eigenvector.html), Fiedler vector, algebraic connectivity, connected, positive semi-definite, $k$-nearest-neighbor graph, similarity graph, [weighted graph](https://dictionaryofml.org/terms/weightedgraph.html), [edge weight](https://dictionaryofml.org/terms/edgeweight.html), image segmentation, [hyperparameter](https://dictionaryofml.org/terms/hyperparameter.html).

## References

- Luxburg (2007). A tutorial on spectral clustering. *Statist. Comput.*. <https://doi.org/10.1007/s11222-007-9033-z>
- Hastie et al. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. *Springer Science+Business Media*. <https://doi.org/10.1007/978-0-387-84858-7>
- Ng et al. (2001). On Spectral Clustering: Analysis and an Algorithm. *Adv. Neural Inf. Process. Syst.*. <https://papers.nips.cc/paper_files/paper/2001/hash/801272ee79cfde7fa5960571fee36b9b-Abstract.html>
- Shi and Malik (2000). Normalized Cuts and Image Segmentation. *IEEE Trans. Pattern Anal. Mach. Intell.*. <https://doi.org/10.1109/34.868688>
- Fiedler (1973). Algebraic connectivity of graphs. *Czechoslovak Mathematical Journal*.
- Hagen and Kahng (1992). New Spectral Methods for Ratio Cut Partitioning and Clustering. *IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst.*. <https://doi.org/10.1109/43.159993>
- Fortunato (2010). Community detection in graphs. *Physics Reports*. <https://doi.org/10.1016/j.physrep.2009.11.002>

## Cite this entry

```bibtex
@misc{dictml_specclustering,
  author = {Jung, Alexander},
  editor = {Olioumtsevits, Konstantina and Schnoor, Ekkehard},
  title = {spectral clustering},
  howpublished = {Dictionary of Applied Machine Learning (course edition)},
  year = {2026},
  doi = {10.5281/zenodo.21569296},
  note = {ISBN 978-952-64-3013-3, CC BY 4.0, retrieved 2026-11-20},
  url = {https://dictionaryofml.org/terms/specclustering.html}
}
```
