Improving the quality of K-NN graphs for image databases through vector sparsification

Neighborhood graphs are an essential component of many established methods for content-based image retrieval and automated image annotation. The performance of such methods relies heavily on the semantic quality of the graphs, which can be measured as the proportion of neighbors sharing the same class label as their query images. In this paper, we propose a new framework for the efficient construction of K-nearest neighbor (K-NN) graphs based on nearestneighbor descent (NN-Descent), in which selective sparsification of object feature vectors is interleaved with neighborhood refinement operations in an effort to improve the semantic quality of the result. A local variant of the Laplacian Score is used to identify noisy features with respect to individual images, whose values are then set to 0 (the global mean value after standardization). We show through extensive experiments that our graph construction method is able to increase the proportion of semantically-related images over unrelated images within the neighbor sets.