Geometric structure of graph Laplacian embeddings
This provides theoretical guarantees for spectral clustering in identifying coarse structure in data, which is incremental for machine learning practitioners dealing with manifold-based data.
The paper analyzes spectral clustering by studying the geometry of graph Laplacian embeddings for data sampled from a mixture model on a manifold, proving that under well-separated conditions, the embedded data concentrates on cones around orthogonal vectors with high probability.
We analyze the spectral clustering procedure for identifying coarse structure in a data set $x_1, \dots, x_n$, and in particular study the geometry of graph Laplacian embeddings which form the basis for spectral clustering algorithms. More precisely, we assume that the data is sampled from a mixture model supported on a manifold $\mathcal{M}$ embedded in $\mathbb{R}^d$, and pick a connectivity length-scale $\varepsilon>0$ to construct a kernelized graph Laplacian. We introduce a notion of a well-separated mixture model which only depends on the model itself, and prove that when the model is well separated, with high probability the embedded data set concentrates on cones that are centered around orthogonal vectors. Our results are meaningful in the regime where $\varepsilon = \varepsilon(n)$ is allowed to decay to zero at a slow enough rate as the number of data points grows. This rate depends on the intrinsic dimension of the manifold on which the data is supported.