  The $k$-NN graph has played a central role in increasingly popular
data-driven techniques for various learning and vision tasks; yet, finding an
efficient and effective way to construct $k$-NN graphs remains a challenge,
especially for large-scale high-dimensional data. In this paper, we propose a
new approach to construct approximate $k$-NN graphs with emphasis in:
efficiency and accuracy. We hierarchically and randomly divide the data points
into subsets and build an exact neighborhood graph over each subset, achieving
a base approximate neighborhood graph; we then repeat this process for several
times to generate multiple neighborhood graphs, which are combined to yield a
more accurate approximate neighborhood graph. Furthermore, we propose a
neighborhood propagation scheme to further enhance the accuracy. We show both
theoretical and empirical accuracy and efficiency of our approach to $k$-NN
graph construction and demonstrate significant speed-up in dealing with large
scale visual data.
