Please use this identifier to cite or link to this item:
Title: Dense neighborhoods on affinity graph
Authors: Liu, H. 
Yang, X.
Latecki, L.J.
Yan, S. 
Keywords: Affinity graph
Nearest neighbor
Semi-supervised learning
Issue Date: 2012
Citation: 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.
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
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.


checked on Jan 14, 2021


checked on Jan 14, 2021

Page view(s)

checked on Jan 20, 2021

Google ScholarTM



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