this article is to analyze the *spectral clustering* procedure for identifying coarse structure in a dataset by means of appropriate spectral embeddings. In particular, we combine ideas from spectral geometry, metastability, optimal transport, and spectral analysis of elliptic operators to describe the geometry of the embeddings that form the basis of spectral clustering in the case where the generative model for the data is sufficiently “well-separated".

Throughout this article we assume the data set ${\mathcal{M}}_n= \{ {\mathbf{x}}_1, \dots, {\mathbf{x}}_n\}$ consists of points that are distributed according to an underlying probability measure $\nu$ supported on a manifold ${\mathcal{M}}$ embedded in some Euclidean space ${\mathbb{R}}^d$. The first step in spectral clustering is to construct a similarity graph $G:=\{ {\mathcal{M}}_n, {\mathbf{W}}_n\}$ with vertices ${\mathcal{M}}_n$ and edge weight matrix ${\mathbf{W}}_n$. The entries in ${\mathbf{W}}_n$ indicate how similar two points in ${\mathcal{M}}_n$ are; typical constructions are proximity graphs, where a length scale ${\varepsilon}>0$ is chosen and high weights are given to pairs of points that are within distance ${\varepsilon}$ from each other. Once the graph has been constructed a [*graph Laplacian*]{} operator is introduced. The first few eigenvectors of the [graph Laplacian]{} are then used to define an embedding that maps the data points ${\mathcal{M}}_n$ 