Source-linked AI summary
Testing for high-dimensional geometry in random graphs
Sébastien Bubeck, Jian Ding, Ronen Eldan, Miklós Rácz
TL;DR
The paper asks whether a random graph contains latent high-dimensional geometric structure rather than arising from an Erdős-Rényi model. It proposes signed triangles for near-optimal testing in the dense regime and derives detection results, a sparse-regime conjecture, and preliminary dimension-estimation steps. The main scope boundary is that the sparse-regime optimality claim remains conjectural.
Problem
The paper studies how to distinguish Erdős-Rényi graphs from graphs generated by latent points uniformly distributed on a sphere with proximity-based edges.
Method
The paper introduces signed triangles, whose centering creates cancellations and reduces variance relative to ordinary triangle counts.
Results
In the dense regime, signed triangles yield a near-optimal and computationally efficient testing procedure, while the sparse regime receives a conjectured optimal detection boundary.
Takeaways & Limitations
Signed-triangle statistics provide a powerful way to detect latent geometric structure, and the paper also develops preliminary methods for estimating dimension.
Takeaways & Limitations
For the sparse regime, the paper conjectures rather than proves that the stated detection boundary is tight, and the supporting rationale relies on local equivalence when d ≫ log^3(n).
Abstract
from arXiv · showhide
We study the problem of detecting the presence of an underlying high-dimensional geometric structure in a random graph. Under the null hypothesis, the observed graph is a realization of an Erdős-Rényi random graph $G(n,p)$. Under the alternative, the graph is generated from the $G(n,p,d)$ model, where each vertex corresponds to a latent independent random vector uniformly distributed on the sphere $\mathbb{S}^{d-1}$, and two vertices are connected if the corresponding latent vectors are close enough. In the dense regime (i.e., $p$ is a constant), we propose a near-optimal and computationally efficient testing procedure based on a new quantity which we call signed triangles. The proof of the detection lower bound is based on a new bound on the total variation distance between a Wishart matrix and an appropriately normalized GOE matrix. In the sparse regime, we make a conjecture for the optimal detection boundary. We conclude the paper with some preliminary steps on the problem of estimating the dimension in $G(n,p,d)$.
1 Introduction
The paper tests whether random graphs contain latent high-dimensional geometric structure rather than arising from an Erdős-Rényi model. It introduces signed triangles for near-optimal dense-regime testing, characterizes dense detectability, conjectures the sparse boundary, and gives preliminary dimension-estimation results.
- Motivation: Triangles exploit the geometric implication that two neighbors of a vertex are more likely to be connected, increasing triangle counts at fixed edge density.This motivates triangles as a basic statistic for detecting dependence induced by geometry.
- Dense-regime method: Signed triangles reweight triangles, induced single edges, wedges, and independent sets with positive and negative signs, reducing variance through cancellation.Under G(n, p), their variance is of order n^3 rather than n^4 for ordinary triangles.
- Problem: The testing problem distinguishes G(n, p) from G(n, p, d), where geometric edges arise from thresholded inner products of independent uniform sphere vectors.The paper considers high-dimensional settings with both constant p and sparse p = c/n.
- Dense-regime results: In the dense regime, signed triangles are asymptotically powerful when d/n^3 → 0, while the paper reports a total-variation phase transition at dimension order n^3.The results tightly characterize the dense regime.
- Sparse-regime results: For the sparse regime p = c/n, the paper gives a result when d/log^3(n) → 0 and conjectures that the corresponding upper boundary is tight.The conjecture is motivated by local equivalence and matching asymptotic Poisson triangle counts at larger dimensions.
2 Estimates for the number of triangles in a geometric graph
This section estimates triangle probabilities in the spherical geometric graph by conditioning on inner products and exploiting spherical symmetry. These estimates establish bounds used to characterize expected triangle counts across edge-density regimes.
- Triangle probabilities: The expected triangle count is obtained from the probability that three independent sphere points satisfy all three pairwise connection conditions.The relevant event requires each pairwise inner product to exceed t_p,d, equivalently each geodesic distance to lie below the connection threshold.
- Bounds: The resulting estimates hold uniformly through constants depending on p or universal constants, with separate bounds covering low and moderate edge probabilities.The section states universal-constant estimates in Lemmas 1 and 2 and p-dependent estimates for fixed p.
- Conditioning and symmetry: The analysis conditions on one inner product and studies how the remaining joint connection probability changes with that value.Monotonicity and rotational invariance reduce the calculation to one-dimensional marginal densities and conditional probabilities.
- Triangle probabilities: For p < 1/2, the triangle probability is decomposed into a conditional-dependence term plus the independent baseline p^3.The decomposition isolates the geometric excess over the Erdős-Rényi triangle probability p^3.
- Density regimes: For p ≥ 1/2, the proof instead bounds the probability that all three relevant edges are absent and uses symmetry between p and 1-p.The argument treats the complementary event and invokes t_1−p,d = −t_p,d.
3 Proof of Theorem 2
The proof of Theorem 2 analyzes signed triangles under the Erdős-Rényi and geometric-graph models, showing that their expectations separate the models while their variances remain controlled. The argument combines spherical-cap calculations, independence, rotational invariance, and concentration.
- Signed triangles are analyzed through adjacency-matrix expressions and their expectations and variances under G(n,p) and G(n,p,d).The proof compares the statistic componentwise across the two graph models.
- Under G(n,p), each signed-triangle term has expectation zero, and distinct vertex triples have zero covariance.For an individual triple, the matching second-moment contribution is p^3(1-p)^3.
- The geometric-model analysis bounds signed-triangle expectations using spherical-cap intersections and the cap measure identity σ(S_x)−p^2.The proof represents the relevant overlap through normalized Haar measure on the sphere.
- Combining the expectation and variance bounds with Chebyshev’s inequality completes the proof of Theorem 2.The final bound has a constant C depending only on p.
- Rotational invariance and independence reduce the variance calculation to four overlap types, with independent or symmetric terms vanishing and the remaining terms bounded geometrically.The proof uses W_4=0 by independence and establishes W_3=0 through conditioning and rotational invariance.
4 Proof of Theorem 3
This section bounds the first two moments of triangle counts in the sparse geometric graph and uses them to establish the theorem’s asymptotic conclusion.
- Triangle-count setup: For p=c/n, the proof defines triangle indicators and expands the triangle count into sums of these indicators.The indicator T_G(i,j,k) equals A_i,j A_i,k A_j,k.
- Variance control: Triangle indicators are independent when their vertex triples share at most one vertex, because the triples share no edge.This independence organizes the variance calculation by overlap patterns.
- Variance control: The variance satisfies Var[T(G(n,c/n,d))] ≤ (2c + 1) E[T(G(n,c/n,d))].The bound follows by expanding the squared triangle count and controlling dependent overlap terms.
- Probability bounds: Chebyshev’s inequality and Markov’s inequality convert the moment bounds into probability bounds for the triangle statistic.The proof applies these inequalities after obtaining the expectation and variance estimates.
- Conclusion: Both resulting upper bounds vanish when d/log^3(n) → 0, completing the proof of Theorem 3.The conclusion is obtained from estimate (31).
5 Proof of the lower bound
The lower-bound proof compares geometric-graph and Erdős–Rényi adjacency matrices through Wishart and GOE representations, then controls the resulting total variation errors.
- Matrix representations: A normalized Gaussian matrix yields a Wishart representation whose thresholded off-diagonal entries have the law of G(n,p,d).If W=YY^T, normalized inner products of Gaussian rows represent latent spherical inner products; the threshold map is H_p,d.
- Matrix representations: A shifted and scaled GOE matrix provides an analogous representation of G(n,p) through the map K_p,d.The construction uses M(n,d)=√d M(n)+dI_n and thresholds its off-diagonal entries.
- Total variation decomposition: The total variation distance between the graph models is bounded by the sum of a Wishart–GOE distance and a threshold-map discrepancy.The triangle inequality gives TV(G(n,p,d),G(n,p)) ≤ TV(H_p,d(W),H_p,d(M)) + TV(H_p,d(M),K_p,d(M)).
- Wishart–GOE comparison: Under d/n^3 → ∞, all statistics of the Wishart and normalized GOE ensembles have asymptotically the same distribution.This is stronger than matching selected spectral statistics alone.
6 Dimension estimation
The paper develops preliminary dimension-estimation results using signed triangles and bounds on how triangle expectations change across dimensions, with a proof currently limited to p=1/2.
- Estimation strategy: Dimension estimation uses the signed-triangle statistic together with bounds on the difference in expected triangle counts between consecutive dimensions.This requires more than a lower bound on the expected triangle count at one dimension.
- Scope boundary: The key lemma is proved only for p=1/2, although the authors believe it should hold for every fixed 0<p<1.They state that extending the proof appears substantially more involved.
- Geometric lemma: The proof analyzes spherical coordinates and projection events involving independent uniform vectors on S^{d−1}.Rotational invariance reduces the relevant probability to the angle of a two-dimensional wedge.
- Geometric lemma: The dimension-dependent density calculations establish a universal lower bound needed for the consecutive-dimension comparison.The argument changes variables through arccos and uses monotonicity and concavity properties of trigonometric functions.
- Estimation guarantee: Combining the expectation separation with variance bounds and Chebyshev’s inequality yields the stated dimension-estimation guarantee.The proof combines the bounds for dimensions d1<d2 and selects a universal constant C.
A The error term in the proof of the lower bound
This appendix controls the threshold-map error in the lower-bound argument by comparing transformed GOE matrices through intermediate Gaussian variables and total variation bounds.
- Threshold-map comparison: When d/n^3 → ∞, the second discrepancy TV(H_p,d(M(n,d)),K_p,d(M(n,d))) tends to zero uniformly over p∈[0,1].This is the content of Lemma 6.
- Error decomposition: The proof reduces the threshold-map discrepancy to two total variation terms involving intermediate matrices X, Y, and Z.The triangle inequality gives TV(X,Y) ≤ TV(X,Z)+TV(Y,Z).
- Entrywise control: A union bound reduces the probability that any transformed matrix entry differs to n^2 times the corresponding two-entry mismatch probability.The argument first bounds TV(Y,Z) by the event that at least one off-diagonal entry differs.
- Entrywise control: For fixed p, the entrywise mismatch is controlled using the threshold expansion, with p=1/2 giving zero for the relevant expression and general fixed p yielding O(1/d).Symmetry relates thresholds at p and 1−p.
- Density comparison: The remaining comparison bounds TV(X,Z) through the distance between D(f(M)) and D(M), whose densities are related by a change of variables and Jacobian calculation.The proof compares the push-forward density w(x) with the standard Gaussian density q(x).