A note on estimating the dimension from a random geometric graph

• Authors: Caelan Atamanchuk, Luc P Devroye and Gábor Lugosi.
• Electronic Journal of Statistics, Vol. 18, No. 2, 5659-5678, July 2024.

Let Gn be a random geometric graph with vertex set [n] based on n i.i.d. random vectors X1, …, Xn drawn from an unknown density f on Rd. An edge (i, j) is present when Xi − Xj ‖ ≤ rn, for a given threshold rn possibly depending upon n, where denotes Euclidean distance. We study the problem of estimating the dimension d of the underlying space when we have access to the adjacency matrix of the graph but do not know rn or the vectors Xi . The main result of the paper is that there exists an estimator ∫of d that converges to d in probability as n → ∞ for all densities with f5 < ∞ whenever n3/2 rnd → ∞ and rn = o(1). The conditions allow very sparse graphs since when n3/2 rnd → 0, the graph contains isolated edges only, with high probability. We also show that, without any condition on the density, a consistent estimator of d exists when nrnd → ∞ and rn = o(1).