k-NN Graph Construction Based on Markov Random Walk

Jiangzhong Cao, Bingo Wing-Kuen Ling, Wai-Lok Woo, Zhijing Yang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


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.
Original languageEnglish
Title of host publication2015 IEEE International Conference on Digital Signal Processing (DSP)
ISBN (Electronic)978-1-4799-8058-1
Publication statusPublished - 10 Sept 2015


Dive into the research topics of 'k-NN Graph Construction Based on Markov Random Walk'. Together they form a unique fingerprint.

Cite this