On the edge eigenvalues of sparse random geometric graphs

Xiucai Ding; Yichen Hu

REVIEW 3 major objections 3 minor 64 references

On the edge eigenvalues of sparse random geometric graphs

T0 review · 3 major / 3 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For sparse random geometric graphs built from Gaussian samples, the first few nontrivial edge eigenvalues of the scaled random-walk Laplacian converge with high probability to explicitly computable eigenvalues of a weighted Laplace–Beltrami

desk verdict First serious attack on the edge spectrum of sparse Gaussian RGGs, with explicit limits that are likely correct, but the proof's eigenvalue-counting step uses a trace identity that does not apply. read the letter →

arxiv 2509.07372 v1 pith:DRDLKN2J submitted 2025-09-09 math.PR math.STstat.TH

Xiucai Ding , Yichen Hu This is my paper · ORCID

classification math.PRmath.STstat.TH MSC 05C8060D0535P15

keywords randomgeometricgraphsedgeeigenvaluesgraphLaplacianGaussiansamplesunboundedsupportsparseregimeweightedLaplace-BeltramioperatorHermitepolynomials

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes that for sparse random geometric graphs generated by Gaussian samples, the first few non-trivial edge eigenvalues of the random-walk Laplacian have a deterministic, explicit limit. The difficulty is that Gaussian sampling has unbounded support and vanishing density, so classical approaches for compactly supported densities—integral operators or interpolation-based min-max arguments—do not apply. The authors introduce a two-step smoothing–matching argument: they smooth the graph into an everywhere-defined empirical operator and then match its edge eigenvalues to a continuum weighted Laplace–Beltrami operator by contour-integral counting. The resulting limits are the sorted sums of 2(k_i−1)/σ_i², computable directly from the Gaussian covariance without solving a PDE. This gives a concrete spectral fingerprint of pure Gaussian geometry, useful as a baseline for graph-based manifold learning and signal detection.

What carries the argument

The machinery is a smoothed empirical operator rL_n (with deterministic approximation T_n) together with an eigenvalue-counting transfer to the weighted Laplace–Beltrami operator Δ_ρ. rL_n replaces the hard cutoff 1{∥x−x_j∥_p ≤ r_n} by a sigmoid s(α_n(r_n²−∥x−x_j∥_p²)), so it is defined for every x, and its eigenvalues match the smoothed matrix rL except at one value. The eigenfunctions of Δ_ρ are products of physicist's Hermite polynomials H_{k_i}(x_i/σ_i), which form an orthonormal basis of the weighted space F. On these test functions the paper proves ∥(Δ_ρ − rL_n)φ∥_F = o(1) via a bias–variance split, with the bias controlled by a multi-index Hermite expansion and the variance by a trunc

What would settle it

Simulate d=1, σ²=1, g≡1 with n=5,000 and r_n=n^{-0.19} (inside the theorem's window); form L=(2m0/(m2 r_n²))L_rw, count K0 as the number of eigenvalues at most δ=0.5, and measure λ_{K0+1},…,λ_{K0+6} over repeated trials. If these six eigenvalues do not concentrate at 2,4,6,8,10,12 with error tending to 0 as n grows to 10^4, the central claim is wrong.

Watch

Extended reading notes

Core claim

The central claim is Theorem 2.2 with Proposition 2.4: for i.i.d. samples from N_d(0, diag(σ_i²)), any ℓ_p metric with 1≤p≤∞, and radius r_n satisfying n^{-1/(d+4)+ε} << r_n << n^{-ε}, the normalized random-walk Laplacian L = (2m0/(m2 r_n²)) L_rw has, with probability 1−o(1), its first few non-trivial eigenvalues equal to a_{k+1}+o(1). The numbers a_j are the eigenvalues of the weighted Laplace–Beltrami operator Δ_ρ = −ρ^{-2} div(ρ²∇·) with Gaussian weight ρ(x)=exp(−Σ x_i²/(2σ_i²)), and they equal the sorted values of Σ_i 2(k_i−1)/σ_i² over multi-indices. In one dimension this is the arithmetic progression 0, 2/σ², 4/σ², …; in higher dimensions multiplicities appear from coincident sums. The

Load-bearing premise

The proof's load-bearing premise is the radius window (2.9): the graph must be sparse enough yet have r_n far above the Gaussian-tail connectivity scale n^{-1/(d+4)+ε}; below that window the truncation and variance bounds collapse, and the paper gives no evidence the limit statement still holds.

Editorial extensions

If this is right

The limiting edge spectrum is completely explicit: after proper scaling, the nontrivial eigenvalues are the sorted sums of 2(k_i−1)/σ_i², so no numerical PDE solve is required.
The first few eigenvalues of the unscaled random-walk Laplacian L_rw are o(1) in the sparse regime, in contrast with dense RGGs, so the 1/r_n² scaling is the natural one for sparse point clouds.
In one dimension the scaled nontrivial eigenvalues form an arithmetic progression 2(k−1)/σ²; in two dimensions with equal variances they come in level sets with multiplicities 1, 2, 3, ….
The result gives a predictable spectral baseline for Gaussian noise: graph Laplacian spectra of purely Gaussian point clouds are known, which is what makes deviations such as embedded signals detectable.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A natural stress test is to push r_n below the theorem's lower bound toward the connectivity threshold: the proof mechanism fails there, but the paper's own simulations hint the formula may persist, so locating the true breakdown scale would separate technical from fundamental limitations.
The same smoothing–matching–counting route should extend to other sampling densities whose weighted L² space has a known orthogonal-polynomial basis, replacing Hermite polynomials by the corresponding basis; the specific truncation and variance bounds would need reworking.
The statistic T defined in the paper could be turned into a formal goodness-of-fit test for 'clean Gaussian geometry' by calibrating its null distribution; the paper only sketches the idea.
The intermediate eigenvalues between the trivial block and the first nontrivial limit are controlled only through the bound K0 = o(n); their fluctuations are not described and could be studied separately.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: this is the first paper I have seen that gets explicit edge-eigenvalue limits for sparse random geometric graphs with unbounded sampling density. The spectrum of the limit operator in Theorem 3.1 is cleanly derived via Hermite polynomials, and the smoothing-matching-bias-variance machinery in Section 4.3 is genuinely new. The simulations support the stated limits. If the result stands, it resolves an open question and gives a principled handle on radius selection for Laplacian Eigenmaps.

The soft spot is not cosmetic. Section 4.2 converts the finite-test-function closeness (4.20) into exact eigenvalue counts using Theorem A.10. That theorem requires the resolvents to be trace class on the contour. For Δ_ρ the eigenvalues grow linearly in d=1, so sum_j 1/(λ_j−z) diverges; for rL_n the special eigenvalue r_n^{-2} has infinite multiplicity and also kills the trace. So (4.24)–(4.25) are not well-defined as written. The proof offers no substitute, such as finite-rank Riesz projections with a norm gap. That is a load-bearing gap in the central matching argument, not a minor technicality.

Secondary issues: the choice of ϑ in Step two is justified only by saying the two factors are independent, without rates; that is probably repairable but needs an explicit argument. The radius window (2.9) is restrictive relative to the bounded-support regime, and the authors acknowledge the truncation argument forces it. That limits practical reach but does not by itself invalidate the limit claim.

The paper deserves a serious referee. It is important, technically rich, and the gap may be fixable by replacing the trace-counting step with a different spectral comparison argument or by proving enough summability. As it stands, I would not cite the main theorem as established until Section 4.2 is repaired.

Referee Report

3 major / 3 minor

Summary. The paper studies the edge eigenvalues of random-walk Laplacians of sparse random geometric graphs generated by i.i.d. Gaussian samples in R^d with diagonal covariance, for a broad class of l^p metrics and kernel functions. After the scaling L = (2m0/(m2 r_n^2)) L_rw, the first M nontrivial eigenvalues are claimed to converge, with probability 1-o(1), to the eigenvalues of the weighted Laplace-Beltrami operator Δ_ρ. The spectrum of Δ_ρ is computed explicitly in Theorem 3.1 as the values sum_i 2(k_i-1)/σ_i^2 using physicist's Hermite polynomials. The proof strategy combines a smoothed empirical operator, a bias-variance analysis on Hermite eigenfunctions, and an eigenvalue-counting argument based on contour integrals of resolvents.

Significance. If the main theorem is established, the paper provides the first edge-eigenvalue limit for RGGs with unbounded sampling density in a sparse regime, with explicit, parameter-free limits. The spectral computation of Δ_ρ is clean and self-contained, and the bias-variance estimates in Proposition 4.1 are detailed and largely convincing. The numerical simulations are consistent with the stated limit. However, the eigenvalue-counting step that converts pointwise function-space closeness into exact multiplicity statements is not rigorously justified as written, and the current proof does not establish the main theorem.

major comments (3)

[Section 4.2, Eqs. (4.24)-(4.25), Theorem A.10] Theorem A.10 is invoked although its trace-class hypothesis is not satisfied. For Δ_ρ, the eigenvalues grow linearly in d=1 (a_j ~ c j), so sum_j 1/a_j diverges and R(z,Δ_ρ) is not trace class. For rL_n, Lemma B.5 shows that 2m0/(m2 r_n^2) is an eigenvalue of infinite multiplicity, so its resolvent has infinite trace for every z not equal to that value. Consequently the contour integrals of Tr(R(z,rL_n)) in (4.25) are not well-defined, and the counting identity used to conclude exact multiplicities is invalid. This is the central matching step, and it needs to be replaced by a finite-rank Riesz projection or an equivalent argument that explicitly handles the infinite-dimensional eigenspace.
[Section 4.2, Step two, choice of ϑ after (4.28)] The proof asserts that ϑ can be chosen so that ∥(Δ_ρ-rL_n)ϕ_{j,l}∥_F max_{z∈Γ_j}∥R(z,rL_n)∥ = o(1), because the first factor is independent of ϑ and the second is ϑ-dependent and independent. This is not justified: max_{z∈Γ_j}∥R(z,rL_n)∥ = 1/dist(μ_j^*, σ(rL_n)), and no uniform lower bound on this distance is proved. An eigenvalue of rL_n could lie arbitrarily close to the contour, making the resolvent norm unbounded in a way that is not controlled by the pointwise o(1) estimate. A spectral gap or explicit resolvent bound is needed.
[Section 4.2, Eq. (4.18)] The statement that λ_j(L)=λ_j(rL)+o(1) for all j follows from Lemma B.1's ∥L-rL∥=o_P(1) is not immediate. L and rL are non-symmetric random-walk Laplacians, and eigenvalue perturbation in operator norm for nonnormal matrices requires additional control (e.g., uniform condition numbers or comparison of the symmetrized normalized Laplacians). The manuscript does not provide such an argument. Since (4.19) and hence the final eigenvalue matching rely on (4.18), this gap is load-bearing.

minor comments (3)

[Section 2.1, Remark 2.3] The radius window (2.9) is far above the standard connectivity threshold (log n/n)^{1/d}; the authors acknowledge this, but the abstract's phrase 'sparse regime' should be qualified to avoid overstating the range of sparsity covered.
[General notation] There are several typos and OCR artifacts in displayed formulas (e.g., the exponent in the K0 bound in Theorem 2.2, and the conventions paragraph containing 'we use tau for the greatest integer'). These should be corrected in a revision.
[Section 4.1, Eq. (4.16)] The lower bound d_j ≥ n^{2/(d+4)} is a key input for the K0 bound; its dependence on the lower bound in (2.9) should be stated explicitly in the main theorem or in Remark 2.3, since it explains the restrictive radius assumption.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the limit eigenvalues are derived from the Gaussian density and the weighted Laplace–Beltrami operator, not from the graph Laplacian; the graph-side scaling is an independent normalization, and no fitted parameter is renamed as a prediction.

full rationale

I walked the derivation chain. The claimed limit eigenvalues are obtained in Theorem 3.1 by solving the ODE (3.3) with Hermite polynomials; this computation uses only the Gaussian density ρ and the Hilbert space F, not the graph. The graph Laplacian L in (2.3) is normalized by 2m0/(m2 r_n^2), and this constant is chosen so that the deterministic operator T_n in (2.19) approximates Δρ; the bias computation (4.41)–(4.44) shows explicitly that the m0 factor cancels and the leading term is Δρ. This is a standard spectral-normalization argument, not a definition of the target eigenvalues into the construction. No parameter is fitted to data: σ_i are pre-specified distribution parameters, m0 and m2 are kernel moments, and δ, ε, η, α_n, ϑ are auxiliary analytic choices. The proof of Proposition 4.1 is a genuine approximation statement ∥(Δρ − rLn)ϕ∥_F = o(1) on test eigenfunctions, not an equality imposed by construction. The counting argument in Section 4.2 invokes the standard Theorem A.10; whether its trace-class hypothesis is satisfied is a technical correctness concern, not a circularity. The only self-citations (references [21,22] by the first author) occur in a list of related work on complete graph kernels and are not used as load-bearing premises. Similarly, Lemma B.5 is attributed to the external standard source [62]. I therefore find no circular reduction, and at most a harmless non-load-bearing self-citation, giving score 1.

Assumptions & free parameters 4 free parameters · 8 assumptions · 0 invented entities

The central claim rests on standard functional analysis, ODE theory, and concentration inequalities plus domain assumptions. No free parameters are fitted to data; the auxiliary parameters delta, alpha_n, eta, epsilon, beta are analytic choices that do not affect the limiting eigenvalues. No new entities are invented. The main unproven input is the trace-class counting theorem A.10, which is standard.

free parameters (4)

delta
Threshold defining K0 in (2.8); must satisfy delta < min sigma_i^{-2}. The limit eigenvalues do not depend on delta.
alpha_n
Sharpness of sigmoid smoothing in (2.15); assumed alpha_n >> n^{7/2}. Auxiliary and does not affect the limit.
beta
Bulk-region constant in (4.47). Auxiliary truncation parameter.
epsilon, eta, vartheta
Small constants in the radius condition, the K0 bound, and the contour width. Auxiliary and do not enter the limit.

assumptions (8)

standard math Sturm-Liouville theory implies Hermite polynomials form a complete orthonormal basis of each one-dimensional space F_i (Appendix A.1).
Invoked in the proof of Theorem 3.1 to separate variables and diagonalize Delta_rho.
standard math Confluent hypergeometric asymptotics (Lemma A.6) determine which power-series solutions of (3.3) are square-integrable with respect to the Gaussian weight.
Used in Theorem 3.1 to select exactly the Hermite polynomial eigenfunctions.
standard math Residue theorem and trace-class eigenvalue counting (Theorems A.8 and A.10) give integer spectral counts via contour integrals of resolvents.
Central tool in the eigenvalue-counting argument of Section 4.2.
standard math Bernstein/Chernoff concentration for sums of Bernoulli variables (Lemma C.1) and Gaussian tail bounds.
Used in the K0 bound and in variance control of Section 4.3.
domain assumption Samples are i.i.d. N_d(0,Sigma) with diagonal Sigma and fixed dimension d (2.1).
The Gaussian structure and diagonal covariance are essential for the Hermite basis and the explicit spectrum.
domain assumption The radius satisfies the two-sided bound n^{-1/(d+4)+epsilon} << r_n << n^{-epsilon} (2.9).
This sparse-regime window is used throughout the proof to balance degree growth and local geometry.
domain assumption Kernel g is C^2 on [0,infinity), bounded above and below on [0,1], and admits a bounded smooth extension g* (2.15).
Needed to approximate the hard cutoff by the sigmoid and to control the deterministic operator T_n.
domain assumption delta < min sigma_i^{-2} (2.10) and alpha_n >> n^{7/2} (Lemma B.1).
Separates trivial eigenvalues from the first nontrivial limit value and guarantees entrywise closeness of L and rL.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the edge eigenvalues of sparse random geometric graphs." pith.science (2026). https://pith.science/paper/DRDLKN2J

@misc{pith2026250907372,
  author       = {Pith},
  title        = {Pith review of: On the edge eigenvalues of sparse random geometric graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DRDLKN2J}},
  note         = {Machine review of arXiv:2509.07372}
}

read the original abstract

In this paper, we study the edge eigenvalues of random geometric graphs (RGGs) generated by multivariate Gaussian samples in the sparse regime under a broad class of distance metrics. Previous work on edge eigenvalues under related setups has relied on methods based on integral operators or the Courant-Fischer min-max principle with interpolation. However, these approaches typically require either a dense regime or sampling distributions that are compactly supported and non-vanishing, and therefore cannot be generalized to our setting. We introduce a two-step smoothing-matching argument. First, we construct a smoothed empirical operator from the given RGG. We then match its edge eigenvalues to those of a continuum limit operator via a counting argument. We show that, after proper normalization, the first few nontrivial edge eigenvalues of the RGG converge with high probability to those of a differential operator, which can be computed explicitly through a simple second-order linear partial differential equation. To the best of our knowledge, these are the first results on the edge eigenvalues of RGGs generated from samples with unbounded support and vanishing density functions.

Figures

Figures reproduced from arXiv: 2509.07372 by the authors.

**Figure 1.** Empirical accuracy and the impact of rn. Here we use the setup of Example 2.5 with σ “ 1, n “ 5, 000 and g ” 1 in (1.1). In Figure 1a, we choose rn “ 0.05 and illustrate the empirical convergence of the first six non-trivial edge eigenvalues using violin plots; the theoretical limits µ2p∆̺q, ¨ ¨ ¨ , µ7p∆̺q from Example 2.5 are marked by the blue points. In Figure 1b, we compare the relative errors ř6 k“1 |λK0`kpLq ´… view at source ↗

**Figure 2.** Behavior of edge eigenvalues across different setups. He [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

**Figure 3.** Partition of pδ, µ˚ M0 ` ϑq. r0, δs is the trivial region and will not be studied by our eigenvaluecounting argument, pµ ˚ j ´ ϑ, µ˚ j ` ϑq’s are the counting regions, and rµ ˚ j ` ϑ, µ˚ j`1 ´ ϑs’s and pδ, µ˚ 1 ´ ϑs are the empty regions. show that each pµ ˚ j ´ ϑ, µ˚ j ` ϑq contains at least one eigenvalue of Lrn. In Step two, we show that exactly nj eigenvalues of Lrn (counting multiplicities) lie in pµ ˚ j ´ ϑ, … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

64 extracted references · 60 canonical work pages

[1]

Adhikari, R

K. Adhikari, R. J. Adler, O. Bobrowski, and R. Rosenthal. On the s pectrum of dense random geometric graphs. The Annals of Applied Probability , 32(3):1734–1773, 2022

work page 2022
[2]

L. Ahlfors. Complex Analysis: An Introduction to The Theory of Analytic Functions of One Complex Variable. McGraw-Hill Education, 1979

work page 1979
[3]

Belkin and P

M. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality reduc tion and data representation. Neural computation, 15(6):1373–1396, 2003

work page 2003
[4]

Belkin and P

M. Belkin and P. Niyogi. Convergence of Laplacian eigenmaps. Advances in neural information pro- cessing systems , 19, 2006

work page 2006
[5]

R. F. Betzel, A. Griﬀa, P. Hagmann, and B. Miˇ si´ c. Distance-dependent consensus thresholds for gener- ating group-representative structural brain networks. Network neuroscience, 3(2):475–496, 2019

work page 2019
[6]

Bollobas

B. Bollobas. Random graphs. Number 73 in Cambridge studies in advanced mathematics. Cambridg e University Press, 2 edition, 2001

work page 2001
[7]

Bordenave

C. Bordenave. Eigenvalues of Euclidean random matrices. Random Structures & Algorithms , 33(4):515– 532, 2008

work page 2008
[8]

M. L. Braun. Accurate error bounds for the eigenvalues of the kernel matrix. J. Mach. Learn. Res. , 7:2303–2328, 2006

work page 2006

Show all 64 references

[9]

Brennan, G

M. Brennan, G. Bresler, and D. Nagaraj. Phase transitions for detecting latent geometry in random graphs. Probability Theory and Related Fields , 178(3):1215–1289, 2020

2020
[10]

Bubeck, J

S. Bubeck, J. Ding, R. Eldan, and M. Z. Racz. Testing for high-d imensional geometry in random graphs. Random Struct. Algorithms , 49(3):503–532, 2016

2016
[11]

Calder and N

J. Calder and N. G. Trillos. Improved spectral convergence ra tes for graph Laplacians on ε-graphs and k-nn graphs. Applied and Computational Harmonic Analysis , 60:123–175, 2022

2022
[12]

Cao and Y

Y. Cao and Y. Zhu. Spectra of high-dimensional sparse random geometric graphs. arXiv preprint arXiv:2507.06556, 2025

2025 arXiv
[13]

Cheng and A

X. Cheng and A. Singer. The spectrum of random inner-produc t kernel matrices. Random Matrices: Theory and Applications , 02(04):1350010, 2013

2013
[14]

Cheng and H.-T

X. Cheng and H.-T. Wu. Convergence of graph laplacian with knn s elf-tuned kernels. Information and Inference: A Journal of the IMA , 11(3):889–957, 2022

2022
[15]

Cheng and N

X. Cheng and N. Wu. Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation. Applied and Computational Harmonic Analysis , 61:132–190, 2022

2022
[16]

F. R. Chung. Spectral graph theory, volume 92. American Mathematical Soc., 1997

1997
[17]

R. R. Coifman and S. Lafon. Diﬀusion maps. Applied and computational harmonic analysis , 21(1):5–30, 2006

2006
[18]

Davis and S

E. Davis and S. Sethuraman. Consistency of modularity cluster ing on random geometric graphs. The Annals of Applied Probability , 28(4):2003–2062, 2018. 46

2003
[19]

C. R. De Oliveira. Intermediate spectral theory and quantum dynamics . Springer, 2009

2009
[20]

Devroye, A

L. Devroye, A. Gy¨ orgy, G. Lugosi, and F. Udina. High-dimensio nal random geometric graphs and their clique number. ELECTRONIC JOURNAL OF PROBABILITY , 16:2481–2508, 2011

2011
[21]

Ding and H.-T

X. Ding and H.-T. Wu. On the spectral property of kernel-base d sensor fusion algorithms of high dimensional data. IEEE Transactions on Information Theory , 67(1):640–670, 2021

2021
[22]

Ding and H.-T

X. Ding and H.-T. Wu. Impact of signal-to-noise ratio and bandwid th on graph Laplacian spectrum from high-dimensional noisy point cloud. IEEE Transactions on Information Theory , 69(3):1899–1931, 2022

1931
[23]

Do and V

Y. Do and V. Vu. The spectrum of random kernel matrices: univ ersality results for rough and varying kernels. Random Matrices: Theory and Applications , 2(03):1350005, 2013

2013
[24]

Dubova, Y

S. Dubova, Y. M. Lu, B. McKenna, and H.-T. Yau. Universality fo r the global spectrum of random inner-product kernel matrices in the polynomial regime. arXiv preprint arXiv:2310.18280 , 2023

2023 arXiv
[25]

Duchemin and Y

Q. Duchemin and Y. De Castro. Random geometric graph: Some r ecent developments and perspectives. High Dimensional Probability IX: The Ethereal Volume , pages 347–392, 2023

2023
[26]

D. B. Dunson, H.-T. Wu, and N. Wu. Spectral convergence of g raph Laplacian and heat kernel re- construction in ℓ8 from random samples. Applied and Computational Harmonic Analysis , 55:282–336, 2021

2021
[27]

Estrada, S

E. Estrada, S. Meloni, M. Sheerin, and Y. Moreno. Epidemic spre ading in random rectangular networks. Physical review E , 94(5):052316, 2016

2016
[28]

Estrada and M

E. Estrada and M. Sheerin. Consensus dynamics on random rec tangular graphs. Physica D: Nonlinear Phenomena, 323:20–26, 2016

2016
[29]

Fan and A

Z. Fan and A. Montanari. The spectral norm of random inner-p roduct kernel matrices. Probability Theory and Related Fields , 173(1):27–85, 2019

2019
[30]

W. Feller. An introduction to probability theory and its applications , Volume 2 , volume 2. John Wiley & Sons, 1991

1991
[31]

Garc ´ ıa Trillos, M

N. Garc ´ ıa Trillos, M. Gerlach, M. Hein, and D. Slepˇ cev. Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace–B eltrami operator. Foundations of Computational Mathematics , 20(4):827–887, 2020

2020
[32]

R. M. Gray et al. Toeplitz and circulant matrices: A review. Foundations and Trends ® in Communi- cations and Information Theory , 2(3):155–239, 2006

2006
[33]

Haenggi, J

M. Haenggi, J. G. Andrews, F. Baccelli, O. Dousse, and M. Franc eschetti. Stochastic geometry and random graphs for the analysis and design of wireless networks. IEEE journal on selected areas in communications, 27(7):1029–1046, 2009

2009
[34]

Hamidouche

M. Hamidouche. Spectral analysis of random geometric graphs . PhD thesis, Universit´ e Cˆ ote d’Azur, 2020

2020
[35]

Hein, J.-Y

M. Hein, J.-Y. Audibert, and U. v. Luxburg. Graph laplacians and their convergence on random neighborhood graphs. Journal of Machine Learning Research , 8(6), 2007. 47

2007
[36]

D. J. Higham, M. Raˇ sajski, and N. Prˇ zulj. Fitting a geometric g raph to a protein–protein interaction network. Bioinformatics, 24(8):1093–1099, 2008

2008
[37]

P. D. Hoﬀ, A. E. Raftery, and M. S. Handcock. Latent space a pproaches to social network analysis. Journal of the american Statistical association , 97(460):1090–1098, 2002

2002
[38]

T. Jiang. Distributions of eigenvalues of large Euclidean matrices generated from lp balls and spheres. Linear Algebra and its Applications , 473:14–36, 2015

2015
[39]

N. E. Karoui. The spectrum of kernel random matrices. The Annals of Statistics , 38(1):1 – 50, 2010

2010
[40]

T. Kato. Perturbation theory for linear operators , volume 132. Springer Science & Business Media, 2013

2013
[41]

Koltchinskii and E

V. Koltchinskii and E. Gin´ e. Random matrix approximation of spe ctra of integral operators. Bernoulli, pages 113–167, 2000

2000
[42]

C. Li, N. G. Trillos, H. Li, and L. Suchan. Central limit theorems fo r the eigenvalues of graph laplacians on data clouds. arXiv preprint arXiv:2507.18803 , 2025

2025 arXiv
[43]

S. Liu. Geometry of Random Graphs . PhD thesis, Princeton University, 2022

2022
[44]

S. Liu, S. Mohanty, T. Schramm, and E. Yang. Testing thresho lds for high-dimensional sparse ran- dom geometric graphs. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theor y of Computing, pages 672–677, 2022

2022
[45]

Y. M. Lu and H.-T. Yau. An equivalence principle for the spectrum of random inner-product kernel matrices with polynomial scalings. arXiv preprint arXiv:2205.06308 , 2022

2022 arXiv
[46]

Maier, M

M. Maier, M. Hein, and U. Von Luxburg. Optimal construction of k-nearest-neighbor graphs for iden- tifying noisy clusters. Theoretical Computer Science , 410(19):1749–1764, 2009

2009
[47]

Mitzenmacher and E

M. Mitzenmacher and E. Upfal. Probability and computing: Randomization and probabilist ic techniques in algorithms and data analysis . Cambridge university press, 2017

2017
[48]

G. Nagy. Ordinary Diﬀerential Equations . Michigan State University, 2021

2021
[49]

Olver, D

F. Olver, D. Lozier, R. Boisvert, and C. Clark. The NIST Handbook of Mathematical Functions . Cam- bridge University Press, 2010

2010
[50]

P´ ech´ e and V

S. P´ ech´ e and V. Perchet. Robustness of community detect ion to random geometric perturbations. Advances in Neural Information Processing Systems , 33:17827–17837, 2020

2020
[51]

M. Penrose. Random geometric graphs . OUP Oxford, 2003

2003
[52]

V. M. Preciado and A. Jadbabaie. Spectral analysis of virus spr eading in random geometric networks. In Proceedings of the 48h IEEE Conference on Decision and Contr ol (CDC) held jointly with 2009 28th Chinese Control Conference , pages 4802–4807. IEEE, 2009

2009
[53]

S. Rai. The spectrum of a random geometric graph is concentra ted. Journal of Theoretical Probability , 20(2):119–132, 2007

2007
[54]

W. Rudin. Principles of Mathematical Analysis . International series in pure and applied mathematics. McGraw-Hill, 1976. 48

1976
[55]

Shen and H.-T

C. Shen and H.-T. Wu. Scalability and robustness of spectral em bedding: landmark diﬀusion is all you need. Information and Inference: A Journal of the IMA , 11(4):1527–1595, 2022

2022
[56]

A. Singer. From graph to manifold Laplacian: The convergence r ate. Applied and Computational Harmonic Analysis , 21(1):128–134, 2006

2006
[57]

Singer and H.-T

A. Singer and H.-T. Wu. Spectral convergence of the connect ion Laplacian from random samples. Information and Inference: A Journal of the IMA , 6(1):58–123, 2017

2017
[58]

W. Strauss. Partial Diﬀerential Equations: An Introduction . Wiley, 2007

2007
[59]

G. Szeg. Orthogonal polynomials. American Mathematical Society colloquium publications. American Mathematical Society, 1939

1939
[60]

J. B. Tenenbaum, V. d. Silva, and J. C. Langford. A global geom etric framework for nonlinear dimen- sionality reduction. Science, 290(5500):2319–2323, 2000

2000
[61]

N. G. Trillos, F. Hoﬀmann, and B. Hosseini. Geometric structure of graph Laplacian embeddings. Journal of Machine Learning Research , 22(63):1–55, 2021

2021
[62]

Von Luxburg, M

U. Von Luxburg, M. Belkin, and O. Bousquet. Consistency of sp ectral clustering. The Annals of Statistics, pages 555–586, 2008

2008
[63]

M. J. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint , volume 48. Cambridge university press, 2019

2019
[64]

W. Walter. Ordinary diﬀerential equations , volume 182. Springer Science & Business Media, 2013. 49

2013

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.

[1] [1]

Adhikari, R

K. Adhikari, R. J. Adler, O. Bobrowski, and R. Rosenthal. On the s pectrum of dense random geometric graphs. The Annals of Applied Probability , 32(3):1734–1773, 2022

work page 2022

[2] [2]

L. Ahlfors. Complex Analysis: An Introduction to The Theory of Analytic Functions of One Complex Variable. McGraw-Hill Education, 1979

work page 1979

[3] [3]

Belkin and P

M. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality reduc tion and data representation. Neural computation, 15(6):1373–1396, 2003

work page 2003

[4] [4]

Belkin and P

M. Belkin and P. Niyogi. Convergence of Laplacian eigenmaps. Advances in neural information pro- cessing systems , 19, 2006

work page 2006

[5] [5]

R. F. Betzel, A. Griﬀa, P. Hagmann, and B. Miˇ si´ c. Distance-dependent consensus thresholds for gener- ating group-representative structural brain networks. Network neuroscience, 3(2):475–496, 2019

work page 2019

[6] [6]

Bollobas

B. Bollobas. Random graphs. Number 73 in Cambridge studies in advanced mathematics. Cambridg e University Press, 2 edition, 2001

work page 2001

[7] [7]

Bordenave

C. Bordenave. Eigenvalues of Euclidean random matrices. Random Structures & Algorithms , 33(4):515– 532, 2008

work page 2008

[8] [8]

M. L. Braun. Accurate error bounds for the eigenvalues of the kernel matrix. J. Mach. Learn. Res. , 7:2303–2328, 2006

work page 2006