Consensus of k-NNs for Robust Neighborhood Selection on Graph-Based Manifolds

Vittal Premachandran, Ramakrishna Kakarala; The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2013, pp. 1594-1601

Abstract


Propagating similarity information along the data manifold requires careful selection of local neighborhood. Selecting a "good" neighborhood in an unsupervised setting, given an affinity graph, has been a difficult task. The most common way to select a local neighborhood has been to use the k-nearest neighborhood (k-NN) selection criterion. However, it has the tendency to include noisy edges. In this paper, we propose a way to select a robust neighborhood using the consensus of multiple rounds of k-NNs. We explain how using consensus information can give better control over neighborhood selection. We also explain in detail the problems with another recently proposed neighborhood selection criteria, i.e., Dominant Neighbors, and show that our method is immune to those problems. Finally, we show the results from experiments in which we compare our method to other neighborhood selection approaches. The results corroborate our claims that consensus of k-NNs does indeed help in selecting more robust and stable localities.

Related Material


[pdf]
[bibtex]
@InProceedings{Premachandran_2013_CVPR,
author = {Premachandran, Vittal and Kakarala, Ramakrishna},
title = {Consensus of k-NNs for Robust Neighborhood Selection on Graph-Based Manifolds},
booktitle = {The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)},
month = {June},
year = {2013}
}