Threshold for Detecting High Dimensional Geometry in Anisotropic Random Geometric Graphs

In the anisotropic random geometric graph model, vertices correspond to points drawn from a high-dimensional Gaussian distribution and two vertices are connected if their distance is smaller than a specified threshold. We study when it is possible to hypothesis test between such a graph and an Erdős-Rényi graph with the same edge probability. If $n$ is the number of vertices and $\alpha$ is the vector of eigenvalues, Eldan and Mikulincer show that detection is possible when $n^3\gg (\mathrm{\parallel }\alpha {\mathrm{\parallel }}_2\mathrm{/}\mathrm{\parallel }\alpha {\mathrm{\parallel }}_3{)}^6$ and impossible when $n^3\ll (\mathrm{\parallel }\alpha {\mathrm{\parallel }}_2\mathrm{/}\mathrm{\parallel }\alpha {\mathrm{\parallel }}_4{)}^4$. We show detection is impossible when $n^3\ll (\mathrm{\parallel }\alpha {\mathrm{\parallel }}_2\mathrm{/}\mathrm{\parallel }\alpha {\mathrm{\parallel }}_3{)}^6$, closing this gap and affirmatively resolving the conjecture of Eldan and Mikulincer.