Consistent Recovery Threshold of Hidden Nearest Neighbor Graphs
Jian Ding, Yihong Wu, Jiaming Xu, Dana Yang · IEEE Transactions on Information Theory · 2021
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\frac 2αnlogn > 1; (2) almost exact recovery for 1 ≤ k ≤ o(\frac lognloglogn ) if liminf\frac kD(Pn||Qn)logn > 1, where αn \triangleq -2 log∫√{d Pn d Qn} is the Rényi divergence of order \frac 12 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. We also analyze several computationally efficient algorithms and provide sufficient conditions under which they achieve exact/almost exact recovery. In particular, we develop a polynomial-time algorithm that attains the threshold for exact recovery under the small-world model.