# Reconstruction of Random Geometric Graphs: Breaking the Omega(r) distortion barrier

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 32 references that are in the map.
- First posted on arXiv 29 Jul 2021.

## Builds on (most cited first, 10 of 10)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [A Refined Laser Method and Faster Matrix Multiplication](https://mlsanity.com/paper/2010.05846/) (2020)
- [Testing for high-dimensional geometry in random graphs](https://mlsanity.com/paper/1411.5713/) (2014)
- [The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness](https://mlsanity.com/paper/1702.00467/) (2017)
- [Latent Distance Estimation for Random Geometric Graphs](https://mlsanity.com/paper/1909.06841/) (2019)
- [Identifying the latent space geometry of network models through analysis of curvature](https://mlsanity.com/paper/2012.10559/) (2020)
- [Systematic comparison of graph embedding methods in practical tasks](https://mlsanity.com/paper/2106.10198/) (2021)
- [Link prediction with hyperbolic geometry](https://mlsanity.com/paper/1903.08810/) (2019)
- [Learning random points from geometric graphs or orderings](https://mlsanity.com/paper/1809.09879/) (2018)
- [A quest to unravel the metric structure behind perturbed networks](https://mlsanity.com/paper/1703.05475/) (2017)

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

- [Node Regression on Latent Position Random Graphs via Local Averaging](https://mlsanity.com/paper/2410.21987/) (2024)

## Abstract (arXiv)

Embedding graphs in a geographical or latent space, i.e. inferring locations for vertices in Euclidean space or on a smooth manifold or submanifold, is a common task in network analysis, statistical inference, and graph visualization. We consider the classic model of random geometric graphs where n points are scattered uniformly in a square of area n, and two points have an edge between them if and only if their Euclidean distance is less than r. The reconstruction problem then consists of inferring the vertex positions, up to the symmetries of the square, given only the adjacency matrix of the resulting graph. We give an algorithm that, if r=nα for any α > 0, with high probability reconstructs the vertex positions with a maximum error of O(nβ) where β=1/2-(4/3)α, until α ≥ 3/8 where β=0 and the error becomes O(√log n). This improves over earlier results, which were unable to reconstruct with error less than r. Our method estimates Euclidean distances using a hybrid of graph distances and short-range estimates based on the number of common neighbors. We extend our results to the surface of the sphere in R3 and to hypercubes in any constant fixed dimension. Additionally we examine the extent to which reconstruction is still possible when the original adjacency lists have had a subset of the edges independently deleted at random.