Spectra of high-dimensional sparse random geometric graphs
Yifan Cao, Yizhe Zhu · 2025
Read Spectra of high-dimensional sparse random geometric graphs by Yifan Cao, Yizhe Zhu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-06556.txt.
Introduction
Yifan Cao and Yizhe Zhu find the limiting spectrum of sparse geometric random graphs in this 2025 paper. In these graphs, points sit at random on a high-dimensional sphere. Two points join when their alignment passes a set threshold.
Edges share the same chance as in the classic random graph model. The hidden geometry, though, makes the edges depend on each other. The team show that this dependence fades from the global spectrum in two sparse regimes. The spectrum settles onto the famous semicircle law in one case. Such results ground the theory of networks built from positions. They matter for data that live naturally in high dimensions.
Catalog record
| CREATOR | Yifan Cao, Yizhe Zhu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-06556
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Spectra of high-dimensional sparse random geometric graphs Yifan Cao, Yizhe Zhu Abstract . We analyze the spectral properties of the high-dimensional random geometric graph 𝒢 ( n , d , p ) \mathcal{G}(n,d,p) , formed by sampling n n i.i.d vectors { v i } i = 1 n \{v_{i}\}_{i=1}^{n} uniformly on a d d -dimensional unit sphere and connecting each pair { i , j } \{i,j\} whenever ⟨ v i , v j ⟩ ≥ τ \langle v_{i},v_{j}\rangle\geq\tau so that p = ℙ ( ⟨ v i , v j ⟩ ≥ τ ) p=\mathbb{P}(\langle v_{i},v_{j}\rangle\geq\tau) . This model defines a nonlinear random matrix ensemble with dependent entries. We show that if d = ω ( n p log 2 ( 1 / p ) ) d=\omega(np\log^{2}(1/p)) and n p → ∞ np\to\infty , the limiting spectral distribution of the normalized adjacency matrix A n p ( 1 − p ) \frac{A}{\sqrt{np(1-p)}} is the semicircle law. To our knowledge, this is the first such result for 𝒢 ( n , d , p ) \mathcal{G}(n,d,p) in the sparse regime. In the constant sparsity case p = α / n p=\alpha/n , we further show that if d = ω ( log 2 ( n ) ) d=\omega(\log^{2}(n)) the limiting spectral distribution of A A in 𝒢 ( n , d , α / n ) \mathcal{G}(n,d,\alpha/n) coincides with that of the Erdős-Rényi graph 𝒢 ( n , α / n ) \mathcal{G}(n,\alpha/n) . Our approach combines the classical moment method in random matrix theory with a novel recursive decomposition of closed-walk graphs, leveraging block‐cut trees and ear decompositions, to control 𝔼 tr ( A k ) \mathbb{E}\operatorname{tr}(A^{k}) . A refined high trace analysis further yields a near-optimal bound on the second eigenvalue when n p = Ω ( log 4 ( n ) ) np=\Omega(\log^{4}(n)) , removing technical conditions previously imposed in [ 32 ] . 1. Introduction Random geometric graphs arise naturally in modeling complex systems with latent spatial or geometric structures [ 42 , 33 ] , such as wireless communication networks [ 37 ] , biological networks [ 24 ] , and social graphs [ 25 ] . In a random geometric graph, each node is assigned a random position in a geometric space, and edges are formed based on pairwise geometric proximity, inducing intricate dependencies between edges. These dependencies distinguish random geometric graphs from classical random graph models like Erdős–Rényi graphs, where edges are included independently. Let \mathbf{v}_{1},\dots,\mathbf{v}_{n}\in\mathbb{R}^{d} be n independent random vectors uniformly distributed on the (d-1) -dimensional unit sphere \mathbb{S}^{d-1} . The random geometric graph \mathcal{G}(n,d,p) is constructed by adding edges between two vertices i and j if their corresponding vectors satisfy \langle\mathbf{v}_{i},\mathbf{v}_{j}\rangle\geq\tau . The threshold parameter \tau is chosen such that for i\not=j , \mathbb{E}\mathbf{1}(\langle\mathbf{v}_{i},\mathbf{v}_{j}\rangle\geq\tau)=p . This implies the edge density of \mathcal{G}(n,d,p) is the same as the Erdős-Rényi graph \mathcal{G}(n,p) . A compelling aspect of this model is that the graph structure emerges from a geometric representation of the vertices. This makes it particularly suitable for modeling applications in data science, where network nodes are naturally described by feature vectors in a d -dimensional space, and edges reflect similarity in features [ 43 ] . Additionally, the geometric random graph exhibits the triangle-closing property [ 13 ] , the phenomenon that “a friend of a friend is also likely to be a friend.” This arises from the inherent dependency among edges: if two nodes are each close to a common neighbor in the geometric space, then they are more likely to be close to each other as well, making the formation of triangles more probable. Such edge correlations are absent in classical Erdős–Rényi graphs, but are crucial for capturing clustering behaviors observed in real-world networks. In this paper, our primary objective is to investigate the limiting spectral distribution and the second eigenvalue of the adjacency matrix associated with \mathcal{G}(n,d,p) , and to determine under what conditions it resembles the spectral properties of \mathcal{G}(n,p) . Understanding the spectral properties of random geometric graphs, particularly in high dimensions and sparse regimes, is crucial for advancing both theoretical and applied research in network science, high-dimensional statistics, and random matrix theory. Testing high-dimensional geometry Recent advances in statistics and learning theory highlight the growing importance of high-dimensional feature spaces. In this context, the random geometric graph model \mathcal{G}(n,p,d) has become a canonical model. [ 14 ] first showed that that for fixed n and d\to\infty , \mathcal{G}(n,p,d) and \mathcal{G}(n,p) become indistinguishable in total variation distance. When n,d\to\infty , with constant p , [ 11 ] identified a sharp phase transition at d\asymp n^{3} in the total variation distance between the two models. In the sparse regime p=\frac{\alpha}{n} for a constant \alpha>0 , the same authors proved showed that the total variation distance between the two distributions goes to 1 if d=o(\log^{3}(n)) and they also conjectured a a critical window at d\asymp\log^{3}(n) . This conjecture was nearly solved by [ 31 ] , who showed that indistinguishability holds when d=\Omega(\log^{36}(n)) . Subsequent works have extended these testing thresholds to varied settings. [ 3 ] used Edgeworth‐style expansions to analyze random toroidal graphs. [ 5 , 6 ] investigated low‐degree polynomial complexity and the sandwiching coupling for comparing random geometric and Erdős–Rényi graphs. [ 10 ] determined thresholds for anisotropic latent geometries, and [ 30 , 36 ] studied the recovery of the latent inner product \langle\mathbf{v}_{i},\mathbf{v}_{j}\rangle , locating a threshold at d\asymp np\log(1/p) . While the total variation distance gives one angle of comparison, another perspective comes from spectral graph theory. Since Wigner’s semicircle law, it has been known that for the Erdős–Rényi model \mathcal{G}(n,p) , the empirical eigenvalue distribution of its adjacency matrix converges to the semicircle law [ 46 ] . This raises the question: Can one distinguish \mathcal{G}(n,d,p) from \mathcal{G}(n,p) by their limiting spectral distributions? We answer this in the negative under a mild dimension condition: as soon as d\gg np\log^{2}(1/p) , the two models share the same global spectrum for all p\in(0,1/2) . We treat the case when np\to\infty and np=c differently since \mathcal{G}(n,p) has different limiting spectral distributions [ 28 , 46 ] . The case when np\to 0 is trivial since (1-o(1))n many vertices are isolated and 1-o(1) portion of the eigenvalues are 0 . Our results (Theorems 2.1 and 2.2 ) thus reveal a universality phenomenon: despite their very different constructions, \mathcal{G}(n,d,p) and \mathcal{G}(n,p) become spectrally indistinguishable above a critical dimension. Based on the entropic and spectral thresholds d\asymp np\log(1/p) pointed out in [ 6 , 30 , 36 ] , we conjecture that the true threshold for semicircle convergence is in fact d\gg np\log(1/p) , removing just a single logarithmic factor from our current condition. Nonlinear random matrices A nonlinear random matrix is obtained by a nonlinear function applied entrywise to a classical random matrix ensemble. In recent years, a rich theory has emerged around such models, including kernel random matrices [ 8 , 12 , 15 , 17 , 39 , 40 ] , conjugate kernels and neural tangent kernels arising from neural networks [ 34 ,