# Latent Distance Estimation for Random Geometric Graphs

arXiv: https://arxiv.org/abs/1909.06841 · HTML: https://mlsanity.com/paper/1909.06841/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Sep 2019.

## Built on by (most cited first, 11 of 11)

- [On the Universality of Graph Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2105.13099/) (2021)
- [Graph Coarsening with Message-Passing Guarantees](https://mlsanity.com/paper/2405.18127/) (2024)
- [Spectral clustering in the Gaussian mixture block model](https://mlsanity.com/paper/2305.00979/) (2023)
- [Matrix factorisation and the interpretation of geodesic distance](https://mlsanity.com/paper/2106.01260/) (2021)
- [Detection-Recovery Gap for Planted Dense Cycles](https://mlsanity.com/paper/2302.06737/) (2023)
- [Entropic Optimal Transport in Random Graphs](https://mlsanity.com/paper/2201.03949/) (2022)
- [Information-Theoretic Thresholds for Planted Dense Cycles](https://mlsanity.com/paper/2402.00305/) (2024)
- [Reconstruction of Random Geometric Graphs: Breaking the Omega(r) distortion barrier](https://mlsanity.com/paper/2107.14323/) (2021)
- [Impossibility of latent inner product recovery via rate distortion](https://mlsanity.com/paper/2407.11932/) (2024)
- [A note on estimating the dimension from a random geometric graph](https://mlsanity.com/paper/2311.13059/) (2023)
- [Recovery of latent inner products from an anisotropic Gaussian random geometric graph](https://mlsanity.com/paper/2607.23723/) (2026)

## Abstract (arXiv)

Random geometric graphs are a popular choice for a latent points generative model for networks. Their definition is based on a sample of n points X1,X2,cdots,Xn on the Euclidean sphere~mathbbSd-1 which represents the latent positions of nodes of the network. The connection probabilities between the nodes are determined by an unknown function (referred to as the "link" function) evaluated at the distance between the latent points. We introduce a spectral estimator of the pairwise distance between latent points and we prove that its rate of convergence is the same as the nonparametric estimation of a function on mathbbSd-1, up to a logarithmic factor. In addition, we provide an efficient spectral algorithm to compute this estimator without any knowledge on the nonparametric link function. As a byproduct, our method can also consistently estimate the dimension d of the latent space.