In a 500-feature audio catalogue, why do a few tracks appear in nearly every track's neighbour list?

## What hubness is Define the **k-occurrence** of a point as the number of other points whose `k` nearest neighbours include it. In a low-dimensional dataset this count is well behaved: it averages `k` and most points sit near that average. As the intrinsic dimension grows, the distribution of k-occurrences becomes strongly right-skewed. A small number of points — **hubs** — appear in an enormous share of neighbour lists, while a long tail of **antihubs** appear in none at all. That asymmetry is the phenomenon, and it is a property of high-dimensional geometry, not of the data's semantics. In a 500-feature audio catalogue this shows up as a handful of tracks turning up as a neighbour of nearly every song, whatever the query sounds like, plus a large set of tracks that are never retrieved by anything. ## Why it happens Two facts combine. First, distances concentrate: with many effective dimensions, the distances from a query to all candidates bunch into a narrow band, so the ranking is decided by very small differences. Second, those small differences are not random. A point's expected distance to a randomly chosen other point depends on how far it sits from the centre of the data cloud — points nearer the centroid have a slightly lower expected distance to everything. In low dimensions that advantage is swamped by genuine variation. In high dimensions, where contrast has almost vanished, a systematic bias of a fraction of a percent is enough to win the comparison over and over. So the points closest to the centre become universal neighbours. The important corollary is that a hub is **not** an outlier and **not** necessarily a popular item. It is a geometrically central one. An obscure track with unremarkable feature values can be a hub precisely because it is unremarkable. ## Why it hurts - **Classification.** If a hub carries a label that does not match most of the queries that retrieve it, it becomes a "bad hub" and spreads its label across the dataset, producing a distinctive pattern of correlated errors that tuning `k` does not remove. - **Retrieval and recommendation.** A few tracks are surfaced to everyone regardless of the query, so results look repetitive and generic. Coverage collapses at the other end: antihubs are unreachable through neighbour search, so a slice of the catalogue is effectively invisible. - **Broken intuition about symmetry.** Engineers routinely assume the neighbour relation is mutual. It is not, and in a hub-heavy space it is badly not: a hub is in thousands of lists while its own list contains only a handful of points. ## How to detect it Compute the `k` nearest neighbours for every item, tally how many times each item is retrieved, and inspect that distribution. Useful readings: the skewness of the k-occurrence counts, the maximum count against the mean of `k`, the share of all retrievals captured by the top one percent of items, and the fraction of items with a k-occurrence of zero. A healthy low-dimensional catalogue looks roughly balanced around `k`; a hub-heavy one has a long right tail and a large zero bar. Comparing that distribution before and after a dimensionality change is also how you demonstrate a fix. ## How to reduce it - **Centre the data.** Subtracting the mean from every feature removes the common offset that gives centre-of-cloud points their advantage, and often flattens the k-occurrence distribution noticeably. - **Symmetrise the neighbour relation.** Keep an edge only if each point is in the other's list — a mutual-neighbour rule — so a hub cannot be attached to points that do not consider it close. - **Use shared-neighbour similarity.** Score two items by how many neighbours their lists have in common rather than by raw distance. This is far less sensitive to one item being globally close to everything. - **Scale distances locally.** Divide each point's distances by the distance to its own `k`-th neighbour, so a point sitting in a dense central region does not automatically look close to everyone. - **Cut the dimension.** Hubness grows with intrinsic dimension, so reducing the number of effective directions attacks the cause rather than the symptom. ## What does not work Raising `k` does not remove hubs; it enlarges every list and typically leaves the same items dominating. Filtering by popularity misdiagnoses the cause, since hubness is independent of play counts. And re-checking the distance implementation is wasted effort — the arithmetic is correct, it is the geometry that is unhelpful.