k-NN Graph Construction Based on Markov Random Walk

k-nearest-neighbors (k-NN) graphs are widely used in image retrieval, machine learning and other research fields. Selecting its neighbors is a core for constructing the k-NN graph. However, existing selection methods usually encounter some unreliable neighbors in the k-NN graph. This paper proposes an efficient Markov random walk (MRW) based method for selecting more reliable neighbors for constructing the k-NN graph. The MRW model is defined on the raw k-NN graph. The k-NN of a sample is determined by the probability of the MRW. Since the high order transition probabilities reflects complex relationships among data, the neighbors in the graph obtained by our proposed method are more reliable than those of existing methods. Also, our proposed method can improve the performances of some applications with k-NN graph. Experiments are performed on the synthetic and real datasets for comparison. The results show that the graph obtained by our proposed method better correspond to the structure of the data compared to those of the state-of-the-art methods.