Hubs in Space: Popular Nearest Neighbors in High-Dimensional Data

By Miloš Radovanović, Alexandros Nanopoulos, Mirjana Ivanovic. Journal of machine learning research, 2010

708 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/f620ec7bc0632be5518718cb81e2bfb57c81e950

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Zero-shot Image Recognition Using Relational Matching, Adaptation and Calibration (2019, background): “study [15] showed that the nearest-neighbor search in such a high-dimensional space suffers from the hubness phenomenon because only a certain number of data-points becomes nearest neighbor or hubs for almost all the query points, resulting in erroneous classification results.”
Learning a Deep Embedding Model for Zero-Shot Learning (2016, methodology): “Note that since our ZSL model is a neural network, it is possible now to learn the RNN encoding subnet using the training data together with the rest of the network in an end-to-end fashion.”
A benchmarking study of embedding-based entity alignment for knowledge graphs (2020, neutral): “metric and designing an alignment inference strategy. Distance metrics. Cosine, Euclidean and Manhattan distances are three widely-used metrics. In high-dimensional spaces, a few vectors (called hubs [60]) may repeatedly occur as the k-nearest neighbors of others, the so-called hubness problem [11].”
Does Feature Selection Improve Classification? A Large Scale Experiment in OpenML (2016, neutral): “This is exactly what we would expect: due to the curse of dimensionality, nearest neighbour methods can suffer from too many attributes [16] and Naive Bayes is vulnerable to correlated features [9].”
Transductive Zero-Shot Learning for 3D Point Cloud Classification (2019, methodology): “We validate this claim by measuring the skewness of the distribution Nk [46, 33] when projected in each direction, and the associated accuracy.”
A robust self-learning method for fully unsupervised cross-lingual mappings of word embeddings (2018, background): “This phenomenon is known to occur as an effect of the curse of dimensionality, and causes a few points (known as hubs ) to be nearest neighbors of many other points (Radovanovi´c et al., 2010a,b).”
A survey on unsupervised outlier detection in high‐dimensional numerical data (2012, background): “[66]: the other side of the coin of hubness is probably rather relevant for outlier detection in high-dimensional data.”
Content-based visual search learned from social media (2012, methodology): “As feature dimensionality increases, the method suffers from the curse of dimensionality [92].”
Semi-supervised Learning on Graphs with Generative Adversarial Nets (2018, background): “…a new game, in which G would generate samples in density layer h ( n ) ( x ) . node lies in density gap if and only if it lies in density gap in h ( n ) ( x ) space like h ( n ) ( x ) , the central area is far more narrow than outer Training data in the central area are easy to become hubs [25].”
Word Translation Without Parallel Data (2017, background): “In high-dimensional spaces (Radovanović et al., 2010), this leads to a phenomenon that is detrimental to matching pairs based on a nearest neighbor rule: some vectors, dubbed hubs, are with high probability nearest neighbors of many other points, while others (anti-hubs) are not nearest neighbors of”
Approximate Nearest Neighbor Search on High Dimensional Data - Experiments, Analyses, and Improvement (v1.0) (2016, background): “This is not uncommon in high dimensional data due to the phenomena of “hubness”[36] where a large portion of data points rarely serve as K-NN of other data points, and thus have no or only a few incoming edges in the K-NN graph.”
Acoustic Scene Classification: Classifying environments from the sounds they produce (2014, background): “This observation echoes the problem of hubs encountered in music information retrieval, whereby certain songs are always misclassified by algorithms [41].”
Density Matching for Bilingual Word Embedding (2019, background): “When performing this retrieval, it has been noted that high-dimensional embedding spaces tend to suffer from the “hubness” problem (Radovanovi´c et al., 2010) where some vectors (known as hubs ) are nearest neighbors of many other points, which is detrimental to reliably retrieving translations in…”
Mitigating the Hubness Problem for Zero-Shot Learning of 3D Objects (2019, methodology): “The hubness problem: The hubness problem in high dimensional nearest neighbor search spaces was first investigated in [28] where they illustrate that the hubness problem is related to the data distribution in the high dimensional space.”