Consistent Recovery Threshold of Hidden Nearest Neighbor Graphs

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 lim inf 2n log n 1; (2) almost exact recovery for 1 k o log n log log n if lim inf kD(Pn||Qn) log n 1, where n-2 log dPndQn is the Rényi divergence of order 1 2 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

Duke Scholars

Author Jiaming Xu Fuqua School of Business