# Consistent recovery threshold of hidden nearest neighbor graphs

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Nov 2019.

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

- [Random Graph Matching with Improved Noise Robustness](https://mlsanity.com/paper/2101.11783/) (2021)
- [The planted matching problem: Sharp threshold and infinite-order phase transition](https://mlsanity.com/paper/2103.09383/) (2021)
- [Detection-Recovery Gap for Planted Dense Cycles](https://mlsanity.com/paper/2302.06737/) (2023)
- [Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms](https://mlsanity.com/paper/2201.06438/) (2022)
- [Information-Theoretic Thresholds for Planted Dense Cycles](https://mlsanity.com/paper/2402.00305/) (2024)
- [Recovery thresholds for hidden weighted sparse graphs](https://mlsanity.com/paper/2606.14335/) (2026)

## Abstract (arXiv)

Motivated by applications such as discovering strong ties in social networks and assembling genome subsequences in biology, we study the problem of recovering a hidden 2k-nearest neighbor (NN) graph in an n-vertex complete graph, whose edge weights are independent and distributed according to Pn for edges in the hidden 2k-NN graph and Qn otherwise. The special case of Bernoulli distributions corresponds to a variant of the Watts-Strogatz small-world graph. We focus on two types of asymptotic recovery guarantees as n→ ∞: (1) exact recovery: all edges are classified correctly with probability tending to one; (2) almost exact recovery: the expected number of misclassified edges is o(nk). We show that the maximum likelihood estimator achieves (1) exact recovery for 2 ≤ k ≤ no(1) if  liminf frac2αnlog n>1; (2) almost exact recovery for  1 ≤ k ≤ oleft( fraclog nlog log n right) if liminf frackD(Pn||Qn)log n>1, where αn triangleq -2 log int √d Pn d Qn is the R'enyi divergence of order frac12 and D(Pn||Qn) is the Kullback-Leibler divergence. Under mild distributional assumptions, these conditions are shown to be information-theoretically necessary for any algorithm to succeed. A key challenge in the analysis is the enumeration of 2k-NN graphs that differ from the hidden one by a given number of edges.