Central limit theorems for the eigenvalues of graph Laplacians on data clouds
This work provides foundational theoretical insights into the statistical properties of graph Laplacians, which are crucial for manifold learning and spectral methods in machine learning, though it is incremental in extending central limit theorems to this context.
The paper tackles the problem of understanding the asymptotic fluctuations of eigenvalues of graph Laplacians on data clouds sampled from low-dimensional manifolds, proving that scaled eigenvalue deviations are asymptotically Gaussian with an explicitly characterized variance, and interprets this variance geometrically and statistically as related to a Cramer-Rao lower bound.
Given i.i.d.\ samples $X_n =\{ x_1, \dots, x_n \}$ from a distribution supported on a low dimensional manifold ${M}$ embedded in Eucliden space, we consider the graph Laplacian operator $Δ_n$ associated to an $\varepsilon$-proximity graph over $X_n$ and study the asymptotic fluctuations of its eigenvalues around their means. In particular, letting $\hatλ_l^\varepsilon$ denote the $l$-th eigenvalue of $Δ_n$, and under suitable assumptions on the data generating model and on the rate of decay of $\varepsilon$, we prove that $\sqrt{n } (\hatλ_{l}^\varepsilon - \mathbb{E}[\hatλ_{l}^\varepsilon] )$ is asymptotically Gaussian with a variance that we can explicitly characterize. A formal argument allows us to interpret this asymptotic variance as the dissipation of a gradient flow of a suitable energy with respect to the Fisher-Rao geometry. This geometric interpretation allows us to give, in turn, a statistical interpretation of the asymptotic variance in terms of a Cramer-Rao lower bound for the estimation of the eigenvalues of certain weighted Laplace-Beltrami operator. The latter interpretation suggests a form of asymptotic statistical efficiency for the eigenvalues of the graph Laplacian. We also present CLTs for multiple eigenvalues and through several numerical experiments explore the validity of our results when some of the assumptions that we make in our theoretical analysis are relaxed.