Please use this identifier to cite or link to this item: https://doi.org/10.1007/s11263-011-0496-1
Title: Dense neighborhoods on affinity graph
Authors: Liu, H. 
Yang, X.
Latecki, L.J.
Yan, S. 
Keywords: Affinity graph
Clustering
Nearest neighbor
Semi-supervised learning
Issue Date: 2012
Source: Liu, H., Yang, X., Latecki, L.J., Yan, S. (2012). Dense neighborhoods on affinity graph. International Journal of Computer Vision 98 (1) : 65-82. ScholarBank@NUS Repository. https://doi.org/10.1007/s11263-011-0496-1
Abstract: In this paper, we study the problem of how to reliably compute neighborhoods on affinity graphs. The k-nearest neighbors (kNN) is one of the most fundamental and simple methods widely used in many tasks, such as classification and graph construction. Previous research focused on how to efficiently compute kNN on vectorial data. However, most real-world data have no vectorial representations, and only have affinity graphs which may contain unreliable affinities. Since the kNN of an object o is a set of k objects with the highest affinities to o, it is easily disturbed by errors in pairwise affinities between o and other objects, and also it cannot well preserve the structure underlying the data. To reliably analyze the neighborhood on affinity graphs, we define the k-dense neighborhood (kDN), which considers all pairwise affinities within the neighborhood, i.e., not only the affinities between o and its neighbors but also between the neighbors. For an object o, its kDN is a set kDN(o) of k objects which maximizes the sum of all pairwise affinities of objects in the set {o} ∪ kDN(o). We analyze the properties of kDN, and propose an efficient algorithm to compute it. Both theoretic analysis and experimental results on shape retrieval, semi-supervised learning, point set matching and data clustering show that kDN significantly outperforms kNN on affinity graphs, especially when many pairwise affinities are unreliable. © 2011 Springer Science+Business Media, LLC.
Source Title: International Journal of Computer Vision
URI: http://scholarbank.nus.edu.sg/handle/10635/43139
ISSN: 09205691
DOI: 10.1007/s11263-011-0496-1
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

20
checked on Dec 7, 2017

WEB OF SCIENCETM
Citations

15
checked on Nov 22, 2017

Page view(s)

93
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.