A note on estimating the dimension from a random geometric graph
Caelan Atamanchuk Luc Devroye Gabor Lugosi
Let $G_n$ be a random geometric graph with vertex set $[n]$ based on $n$
i.i.d.\ random vectors $X_1,\ldots,X_n$ drawn from an unknown density $f$ on
$\R^d$. An edge $(i,j)$ is present when $\|X_i -X_j\| \le r_n$, for a given
threshold $r_n$ possibly depending upon $n$, where $\| \cdot \|$ 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 $r_n$ or the vectors $X_i$. The main result of the paper is that
there exists an estimator of $d$ that converges to $d$ in probability as $n \to
\infty$ for all densities with $\int f^5 < \infty$ whenever $n^{3/2} r_n^d \to
\infty$ and $r_n = o(1)$. The conditions allow very sparse graphs since when
$n^{3/2} r_n^d \to 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 $n r_n^d \to \infty$ and $r_n = o(1)$.