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 $P_n$ for edges in the hidden $2k$-NN graph and $Q_n$ 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\to \infty$: (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 \le k \le n^{ o(1)}$ if $ \liminf \frac{ 2\alpha_n}{ \log n}>1$; (2) almost exact recovery for $ 1 \le k \le o\left( \frac{ \log n}{ \log \log n} \right)$ if $\liminf \frac{ kD(P_n||Q_n)}{ \log n}>1$, where $\alpha_n \triangleq -2 \log \int \sqrt{ d P_n d Q_n}$ is the R\'enyi divergence of order $\frac{ 1}{ 2}$ and $D(P_n||Q_n)$ 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.
Categories: cs.DS cs.LG cs.SI math.ST stat.ML stat.TH