Dictionary of Applied Machine Learning: 147 machine-learning terms, each with a definition, a figure, citations and a Python demo · All terms · Demos · Start here
Updated on 2026-11-19
Readiness 88/100
See also clustering graph clustering cluster $k$-means clustering error hard clustering Laplacian matrix eigenvalue decomposition eigenvalue eigenvector weighted graph edge weight hyperparameter
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 (psd), 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.

specclustering.py, which recomputes what the entry states: the script block by block · open in ColabB-dataEach 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 a $k$-nearest-neighbor graph ($k$-NN 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).
B-graphConsider 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}
\label{equ_specclustering_laplacian_dict}
{\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
\(\eqref{equ_specclustering_laplacian_dict}\) satisfies
\begin{equation}
\label{equ_specclustering_quadform_dict}
{\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
\(\eqref{equ_specclustering_quadform_dict}\) is never negative, so
${\mathbf L}^{(\mathcal{G})}$ is a symmetric matrix that is positive semi-definite (psd).
It has an eigenvalue decomposition (EVD)
${\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 \(\eqref{equ_specclustering_quadform_dict}\):
${\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.
pythondemos/specclustering.py
Spectral clustering is not a fixed-point iteration: the EVD is computed once, and iterations occur only in the $k$-means step. That step is empirical risk minimization (ERM) with the clustering error measured in the feature vectors \(\eqref{equ_specclustering_embedding_dict}\) 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 EVD. The hyperparameters are the number $k$ of clusters and the construction of the graph: how many neighbors the $k$-NN 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, graph clustering, cluster, $k$-means, clustering error, hard clustering, Laplacian matrix, adjacency matrix, node degree, eigenvalue decomposition, eigenvalue, eigenvector, Fiedler vector, algebraic connectivity, connected, positive semi-definite, $k$-nearest-neighbor graph, similarity graph, weighted graph, edge weight, image segmentation, hyperparameter.
@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}
}