betaFeedback

WorksMathematics

Spectral Stability and Convergence of the Unnormalized Graph Laplacian on Noisy Point Clouds

Abstract

The first eigenvalues and eigenvectors of the unnormalized graph Laplacian of clean samples from a manifold, suitably scaled, approximate those of a weighted Laplace-Beltrami operator. However, the samples are usually observed with noise and therefore need not lie on the manifold. We build the clean and noisy graph Laplacians, with bandwidth ε\varepsilon, on the clean samples and on the noisy observations, where the noise is arbitrary but bounded by δδ. We show that, with high probability, the first eigenvalues and eigenvectors of the noisy graph Laplacian are close to those of the clean one: the eigenvalues within O(δ/ε)O(δ/\varepsilon), and the subspaces spanned by the first eigenvectors within O(δ/ε)O(\sqrt{δ/\varepsilon}), whether or not the eigenvalues are simple. Consequently, if δδ is small enough relative to ε\varepsilon, the noisy graph Laplacian approximates the weighted Laplace-Beltrami operator at the same rate as the clean one. We also show that, for large noise, we can get the same rate as the clean graph Laplacian by first using a denoiser, and then building the graph Laplacian on the denoised observations.

Introduction

A point cloud is often analysed through a weighted graph on its points, in which the weight of the edge between two points is given by a kernel, a function of their distance and a bandwidth ε\varepsilon. The unnormalized graph Laplacian of this graph is the diagonal matrix of degrees minus the matrix of weights, where the degree of a point is the sum of the weights of its edges (see, e.g., [28]). The first (smallest) eigenvalues of this matrix, or of a normalized version of it, and their eigenvectors are used to cluster the points [28], to describe the geometry of the point cloud with diffusion maps [11], and to embed the points in a low-dimensional space with Laplacian eigenmaps [2].

When the points are i.i.d. samples from a density on a manifold, the unnormalized graph Laplacian approximates a weighted Laplace–Beltrami operator [7, 16], a continuum operator determined by the manifold and the density (see, e.g., [17]). This approximation has been studied through pointwise limits [3, 20, 21, 26], spectral convergence on domains in Rd\mathbb{R}^d [19], and quantitative spectral estimates for discretizations of a manifold and samples from it [4, 16]. Calder and García Trillos [7] prove that, with high probability, the first eigenvalues of the graph Laplacian approximate those of the weighted Laplace–Beltrami operator at rate O(ε)O(\varepsilon) if ε\varepsilon tends to zero slowly enough as the number of points grows. They also prove, under the same conditions, that the corresponding unit eigenvectors approximate eigenfunctions of this operator at the same rate, even for a multiple eigenvalue. For a simple eigenvalue and slightly different normalizations, García Trillos, Li and Venkatraman [17] improve both rates to O(ε2log⁡(1/ε))O(\varepsilon^2\log(1/\varepsilon)) at the same bandwidth.

In practice the points are observed with noise, which changes the distances between them and may move them off the manifold. We ask how much the first eigenvalues of the graph Laplacian and their eigenvectors can change when each point is moved by at most δ\delta. We consider the unnormalized graph Laplacians of the points and of their noisy observations, built with the same kernel and the same bandwidth, and call them the clean and noisy graph Laplacians. For arbitrary noise bounded by δ\delta, we prove that, for each fixed ll, if δ/ε\delta/\varepsilon is small enough, then with high probability, the ll-th eigenvalue of the noisy graph Laplacian differs by O(δ/ε)O(\delta/\varepsilon) from that of the clean one. If moreover the ll-th and (l+1)(l+1)-st eigenvalues of the weighted Laplace–Beltrami operator are distinct, then the orthogonal projection onto the subspace spanned by the first ll eigenvectors of the noisy graph Laplacian differs by O(δ/ε)O(\sqrt{\delta}/\varepsilon) from the corresponding projection for the clean one. Combined with the rate O(ε)O(\varepsilon) of Calder and García Trillos [7] for clean points, our bounds show that the first eigenvalues of the noisy graph Laplacian approximate those of the weighted Laplace–Beltrami operator at rate O(ε+δ/ε)O(\varepsilon+\delta/\varepsilon), and that the first eigenvectors of the noisy graph Laplacian approximate the eigenfunctions of this operator at rate O(ε+δ/ε)O(\varepsilon+\sqrt{\delta}/\varepsilon).

Noise that is not small compared with the bandwidth can sometimes be handled through its structure. Several results concern random noise in high ambient dimension. El Karoui [14] shows that, if the noise is spherical, the kernel matrix of the noisy points is, to first order, the kernel matrix of the clean points with a different kernel. Ding and Wu [12] study how close the eigenvalues of the kernel matrix of the noisy points are to those of the kernel matrix of the clean points, depending on the bandwidth and on the variance of the clean points relative to that of the noise. Landa, Coifman and Kluger [24] show that a Gaussian kernel matrix with the doubly stochastic normalization changes little under noise whose covariance may differ from point to point. Cheng and Landa [10] prove pointwise consistency under outlier noise for a graph Laplacian with an approximate version of this normalization.

Noise that is not small compared with the bandwidth can also be handled by denoising before building the graph [1, 18, 22, 25, 27]. Each denoised point may depend on all the observations, so the errors that remain after denoising need not be independent. Our results allow such dependence, since they hold for arbitrary noise bounded by a deterministic δ\delta. Section 1.4 explains how our results apply after denoising.

Section 1.3 compares our results with those of García Trillos, Sanz-Alonso and Yang [18], of Burago, Ivanov and Kurylev [5], and of Divol [13].

Setting and main results

We use the setting of Section 2. The clean points x1,…,xnx_1,\ldots,x_n are i.i.d. samples from a density ρ\rho on an mm-dimensional manifold M⊂Rd\mathcal{M} \subset\mathbb{R}^d. For a non-increasing Lipschitz kernel profile η\eta supported in [0,1][0,1], the scaled unnormalized graph Laplacian LL acts on u∈Rnu \in\mathbb{R}^n by

(Lu)i=1nεm+2∑j=1nωij(ui−uj),ωij=η(∥xi−xj∥ε).(Lu)_i = \frac{1}{n\varepsilon^{m+2}}\sum_{j=1}^{n}\omega_{ij}(u_i-u_j), \qquad\omega_{ij}=\eta\left(\frac{\lVert x_i-x_j\rVert}{\varepsilon}\right).

The noisy graph Laplacian L~\widetilde{L} is built in the same way from yi=xi+δiy_i=x_i+\delta_i, where ∥δi∥≤δ\lVert\delta_i\rVert\leq\delta for a deterministic bound δ\delta, possibly depending on nn. The displacements are otherwise arbitrary and may depend on the clean points.

Write λl\lambda_l, λ~l\widetilde{\lambda}_l and λlM\lambda_l^{\mathcal{M}} for the ll-th smallest eigenvalues of LL, of L~\widetilde{L} and of the weighted Laplace–Beltrami operator Δρ\Delta_\rho defined in Section 2. Fix ll and p≥1p\geq1, and choose ε=Cε(log⁡n/n)1/(m+4)\varepsilon=C_\varepsilon(\log n/n)^{1/(m+4)} with CεC_\varepsilon large enough, as in [7]. For δ/ε\delta/\varepsilon small enough and nn large enough, the following bounds hold with probability at least 1−O(n−p)1 - O(n^{-p}). Theorem 1 shows that λ~l\widetilde{\lambda}_l is close to λl\lambda_l:

∣λl−λ~l∣=O(δ/ε).|\lambda_l - \widetilde{\lambda}_l| = O(\delta/\varepsilon).

Let PlP_l and P~l\widetilde{P}_l be the orthogonal projections onto the subspaces spanned by the first ll eigenvectors of LL and of L~\widetilde{L}. If λlM<λl+1M\lambda_l^M < \lambda_{l+1}^M, whether or not λlM\lambda_l^M is simple, Theorem 3 shows that P~l\widetilde{P}_l is close to PlP_l:

∥Pl−P~l∥HS,n=O(δ/ε).\|P_l - \widetilde{P}_l\|_{\mathrm{HS},n} = O(\sqrt{\delta/\varepsilon}).

where ∥⋅∥HS,n\|\cdot\|_{\mathrm{HS},n} is the Hilbert–Schmidt norm, equal to the Frobenius norm (§ 3).

For each bound, the event depends only on the clean points, so the bound holds for all displacements with ∥δi∥≤δ\|\delta_i\| \le\delta at once (Lemma 42).

Corollary 2 and Theorem 4 combine these bounds with the clean-sample results of [7] to give the eigenvalue and eigenvector convergence rates stated above.

Idea of the proofs

We bracket both graph Laplacians between two graph Laplacians on the clean points. García Trillos, Sanz-Alonso and Yang [18 Lemma 18] use this idea for the indicator kernel. Moving each point by at most δ\delta changes the distance between two points by at most 2δ2\delta. Since η\eta is non-increasing, shifting its argument ∥xi−xj∥/ε\|x_i-x_j\|/\varepsilon up or down by 2δ/ε2\delta/\varepsilon, with negative arguments replaced by zero, gives lower and upper bounds for both the clean and the noisy weights. The graph Laplacians on the clean points with these weights, scaled as LL, are the comparison operators AA and BB, and

A⪯L⪯B,A⪯L~⪯B,A \preceq L \preceq B,\qquad A \preceq\widetilde{L} \preceq B,

for every point cloud and all displacements with ∥δi∥≤δ\|\delta_i\| \le\delta, where S⪯TS \preceq T means ⟨Su,u⟩n≤⟨Tu,u⟩n\langle Su,u\rangle_n \le\langle Tu,u\rangle_n for every u∈Rnu \in\mathbb{R}^n, and ⟨u,v⟩n=n−1∑iuivi\langle u,v\rangle_n = n^{-1}\sum_i u_i v_i is the empirical inner product, with norm ∥u∥n\|u\|_n. By the Courant–Fischer principle [23 Theorem 4.2.6, p. 236], the ll-th eigenvalues of LL and L~\widetilde{L} therefore both lie between those of AA and BB.

Write ωij−≤ωij+\omega_{ij}^{-} \le\omega_{ij}^{+} for the weights of AA and BB. These weights differ by O(δ/ε)O(\delta/\varepsilon), and only for pairs of clean points at distance at most ε+2δ\varepsilon+ 2\delta; with high probability each point has O(nεm)O(n\varepsilon^m) such neighbours. For every vector uu,

⟨(B−A)u,u⟩n=12n2εm+2∑i,j(ωij−−ωij+)(ui−uj)2.\langle(B-A)u,u\rangle_n = \frac{1}{2n^2\varepsilon^{m+2}}\sum_{i,j}(\omega_{ij}^{-}-\omega_{ij}^{+})(u_i-u_j)^2.

so ⟨(B−A)u,u⟩n=O(δ/ε)\langle(B-A)u,u\rangle_n = O(\delta/\varepsilon) if ∥u∥n=1\|u\|_n = 1 and the entries uiu_i and uju_j differ by O(ε)O(\varepsilon) whenever ∥xi−xj∥≤ε+2δ\|x_i-x_j\| \le\varepsilon+ 2\delta. For a unit eigenvector uu of a graph Laplacian on i.i.d. samples, with eigenvalue below a fixed cutoff, the Lipschitz estimate of Calder, García Trillos and Lewicka [8 Theorem 2.3] bounds ∣ui−uj∣|u_i-u_j| by a constant multiple of the geodesic distance between xix_i and xjx_j plus the bandwidth. The operator AA is built on the clean points, its shifted kernels satisfy the hypotheses of this estimate, and the constants of the estimate can be chosen uniformly in the shift (§ 4.3 and Appendix § 8). With high probability, therefore, the entries of each of the first ll unit eigenvectors of AA differ by O(ε)O(\varepsilon) whenever ∥xi−xj∥≤ε+2δ\|x_i-x_j\| \le\varepsilon+ 2\delta. Since ll is fixed, the same holds for every unit vector uu in their span, so ⟨(B−A)u,u⟩n=O(δ/ε)\langle(B-A)u,u\rangle_n = O(\delta/\varepsilon) for every such uu. The Courant–Fischer principle [23 Theorem 4.2.6, p. 236] then bounds the difference between the ll-th eigenvalues of AA and BB, and hence ∣λl−λ~l∣|\lambda_l-\widetilde{\lambda}_l|, by O(δ/ε)O(\delta/\varepsilon) (§ 5).

References

  1. [1]Yariv Aizenbud and Barak Sober. Estimation of local geometric structure on manifolds from noisy data. Journal of Machine Learning Research, 26(64):1–89, 2025.arxiv.org/abs/2503.07220
  2. [2]Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6):1373–1396, 2003.DOI
  3. [3]Mikhail Belkin and Partha Niyogi. Towards a theoretical foundation for Laplacian-based manifold methods. Journal of Computer and System Sciences, 74(8):1289–1308, 2008.
  4. [4]Dmitri Burago, Sergei Ivanov, and Yaroslav Kurylev. A graph discretization of the Laplace–Beltrami operator. Journal of Spectral Theory, 4(4):675–714, 2014.arxiv.org/abs/1301.2222
  5. [5]Dmitri Burago, Sergei Ivanov, and Yaroslav Kurylev. Spectral stability of metric-measure Laplacians. Israel Journal of Mathematics, 232(1):125–158, 2019.arxiv.org/abs/1506.06781
  6. [6]Annegret Burtscher and Gert Heckman. Variations of Weyl’s tube formula. The Journal of Geometric Analysis, 31(12):11952–11970, 2021.DOI
  7. [7]Jeff Calder and Nicolás García Trillos. Improved spectral convergence rates for graph Laplacians on ε-graphs and k-NN graphs. Applied and Computational Harmonic Analysis, 60:123–175, 2022.DOI
  8. [8]Jeff Calder, Nicolás García Trillos, and Marta Lewicka. Lipschitz regularity of graph Laplacians on random data clouds. SIAM Journal on Mathematical Analysis, 54(1):1169–1222, 2022.arxiv.org/abs/2007.06679
  9. [9]Bang-Yen Chen. Riemannian submanifolds. In F. Dillen and L. Verstraelen, editors, Handbook of Differential Geometry, Vol. I, pages 187–418. North-Holland, 2000.
  10. [10]Xiuyuan Cheng and Boris Landa. Bi-stochastically normalized graph Laplacian: convergence to manifold Laplacian and robustness to outlier noise. Information and Inference: A Journal of the IMA, 13(4):iaae026, 2024.DOI
  11. [11]Ronald R. Coifman and Stéphane Lafon. Diffusion maps. Applied and Computational Harmonic Analysis, 21(1):5–30, 2006.DOI
  12. [12]Xiucai Ding and Hau-Tieng Wu. Impact of signal-to-noise ratio and bandwidth on graph Laplacian spectrum from high-dimensional noisy point cloud. IEEE Transactions on Information Theory, 69(3):1899–1931, 2023.arxiv.org/abs/2011.10725
  13. [13]Vincent Divol. Spectral stability of empirical metric-measure Laplacians. arXiv preprint arXiv:2608.23150v1, 2026.arxiv.org/abs/2608.23150
  14. [14]Noureddine El Karoui. On information plus noise kernel random matrices. The Annals of Statistics, 38(5):3191–3216, 2010.
  15. [15]Herbert Federer. Curvature measures. Transactions of the American Mathematical Society, 93(3):418–491, 1959.DOI
  16. [16]Nicolás García Trillos, Moritz Gerlach, Matthias Hein, and Dejan Slepčev. Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace–Beltrami operator. Foundations of Computational Mathematics, 20(4):827–887, 2020.DOI
  17. [17]Nicolás García Trillos, Chenghui Li, and Raghavendra Venkatraman. Minimax rates for the estimation of eigenpairs of weighted Laplace–Beltrami operators on manifolds. IEEE Transactions on Information Theory, 72(11):8778–8815, 2026.arxiv.org/abs/2506.00171
  18. [18]Nicolás García Trillos, Daniel Sanz-Alonso, and Ruiyi Yang. Local regularization of noisy point clouds: improved global geometric estimates and data analysis. Journal of Machine Learning Research, 20(136):1–37, 2019.arxiv.org/abs/1904.03335
  19. [19]Nicolás García Trillos and Dejan Slepčev. A variational approach to the consistency of spectral clustering. Applied and Computational Harmonic Analysis, 45(2):239–281, 2018.
  20. [20]Evarist Giné and Vladimir Koltchinskii. Empirical graph Laplacian approximation of Laplace–Beltrami operators: large sample results. In Evarist Giné, Vladimir Koltchinskii, Wenbo Li, and Joel Zinn, editors, High Dimensional Probability: Proceedings of the Fourth International Conference, volume 51 of IMS Lecture Notes–Monograph Series, pages 238–259. Institute of Mathematical Statistics, Beachwood, OH, 2006.DOI
  21. [21]Matthias Hein, Jean-Yves Audibert, and Ulrike von Luxburg. Graph Laplacians and their convergence on random neighborhood graphs. Journal of Machine Learning Research, 8(48):1325–1368, 2007.arxiv.org/abs/math/0608522
  22. [22]Matthias Hein and Markus Maier. Manifold denoising. In Advances in Neural Information Processing Systems 19, pages 561–568. MIT Press, 2007.DOI
  23. [23]Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, second edition, 2013.
  24. [24]Boris Landa, Ronald R. Coifman, and Yuval Kluger. Doubly stochastic normalization of the Gaussian kernel is robust to heteroskedastic noise. SIAM Journal on Mathematics of Data Science, 3(1):388–413, 2021.DOI
  25. [25]Nikita Puchkin and Vladimir Spokoiny. Structure-adaptive manifold estimation. Journal of Machine Learning Research, 23(40):1–62, 2022.
  26. [26]Amit Singer. From graph to manifold Laplacian: the convergence rate. Applied and Computational Harmonic Analysis, 21(1):128–134, 2006.DOI
  27. [27]Barak Sober and David Levin. Manifold approximation by moving least-squares projection (MMLS). Constructive Approximation, 52(3):433–478, 2020.DOI
  28. [28]Ulrike von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395–416, 2007.arxiv.org/abs/0711.0189

Paper details

vlnc:W_gvjzevf3
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents