Neighborhoods and Hubs

Part II — Inside the Space

The question a vector cannot answer alone

Hand someone a single embedding vector — [0.13, -0.82, ...] — and ask what it means. They cannot say. Chapter 5 is why: the basis is not identifiable, the scale is model-specific, no coordinate names a concept.

Hand them the same vector and its ten nearest neighbors — all customer-support apologies, all in the same register — and they can usually name the topic, the register, and roughly what the point is about.

A point becomes interpretable through its relationships to other points, and the neighborhood is one of the most useful ways to inspect those relationships. It is not meaning itself. Neighborhood membership depends on the representation, the normalization, the comparison rule, the value of k, the composition of the index, and — if you use approximate search — the search configuration. Change any of those and the neighbors can change. So the neighborhood is a readout of local geometry, and this chapter asks how much that readout can be trusted, and where.

How uniform is local structure across an embedding space, and where is it untrustworthy?

The through-line is a discipline: keep three questions separate. What does the local geometry look like? What, if anything, do those neighbors have in common for the task? And does an irregularity in the geometry actually change a downstream outcome? The measured experiment in this chapter exists to show why running them together is a mistake.

What a nearest-neighbor graph actually is

Fix a finite set of vectors and a comparison rule — say cosine. The k-nearest-neighbor set of a point x, written NN_k(x), is the k other points that rank highest under that rule. Three things about that definition matter for everything below:

• k is a parameter, and the rule is a choice. NN_10 under cosine and NN_10 under L1 can differ, and Chapter 4 showed why.
• Self-matches are excluded. In the item-to-item graph, a point is never its own neighbor.
• The relation is directed. If B is one of A’s ten nearest neighbors, A need not be one of B’s.

That last point is not a high-dimensional curiosity. It follows from nothing more than uneven density. Put three points on a line at positions 0, 1, and 10, and take k = 1:

NN_1(0)  = {1}      (distance 1)
NN_1(1)  = {0}      (distance 1, not 10)
NN_1(10) = {1}      (distance 9)

Point 1 is the nearest neighbor of two other points; point 0 of one; point 10 of none. The neighbor graph is directed and its in-degrees are already unequal — in one dimension, with three points. Whenever some points are attractive neighbors to many others, in-degree spreads out. High-dimensional geometry can make that spread dramatic under some data distributions and metrics; it does not invent it.

Mean in-degree is exactly k

Here is the fact that makes the rest of the chapter easy to read. In a directed k-NN graph over n points, every point emits exactly k outgoing edges. So the graph has exactly nk edges, and every edge is an incoming edge for someone. Therefore:

mean in-degree = nk / n = k,   exactly,

whether the graph is perfectly even or violently lopsided. For k = 10, the mean in-degree across all points is exactly 10. No individual point is required to have in-degree 10; some can have zero while others have dozens.

So hubness is invisible in the mean by construction. It lives in the shape of the distribution around that fixed mean: variance, skew, maximum, the share of edges captured by the top tail, and the count of zero-in-degree points. A maximum of 49 against a mean of 10 tells us the most extreme item is highly connected; skew and top-tail share tell us whether that extremity is part of a broader lopsided distribution rather than a single exceptional point.

Hubs and anti-hubs, described before judged

A hub is a point with unusually high in-degree in a k-NN graph built a particular way. That is the entire definition. It says nothing about why.

A hub might be a near-duplicate of many items, a geometrically central point, a broad semantic prototype, a genuinely good answer to many different queries, a piece of boilerplate that matches everything weakly, or an artifact of the representation. These are hypotheses to check by looking at the items, not conclusions you can read off the degree.

Call a point with in-degree zero an anti-hub in the strict sense: it appears in none of the other corpus items’ k-NN lists. Points with small but nonzero in-degree are simply low-participation neighbors unless you explicitly adopt a broader thresholded definition. Either way, the degree is only a geometric observation. It does not tell you whether the text is short, generic, malformed, rare, or perfectly ordinary; inspect the items before assigning a content explanation.

Hubness as a phenomenon has been studied in high-dimensional nearest-neighbor systems, and its mechanisms are genuinely varied: they depend on the data distribution, the intrinsic dimensionality, the normalization, any anisotropy, the metric, local density variation, and duplicates. One tidy causal story — “distance concentration makes central points into hubs” — is one possibility among several, and it needs special care for L2-normalized embeddings, where every vector sits at the same distance from the origin and “central versus peripheral” has to be defined in terms of the directional distribution rather than radius. The reliable move is to measure the in-degree distribution first and treat the mechanism as an open question.

Local density

A cheap, full-space proxy for how crowded a region is:

density_proxy(x; k, metric) = distance from x to its k-th nearest neighbor

A short k-th-neighbor distance means a crowded neighborhood at that scale under that metric; a long one means an empty patch. Like in-degree, this is a geometric quantity and not a semantic label. A dense region can come from duplication, from templated text, from genuinely common subject matter, or from a compression artifact of the model. A sparse region can hold rare content, or can simply be a sparsely sampled part of the index — few examples collected, not necessarily unusual meaning. Keep the measurement and the interpretation apart.

Clusters and boundaries

A cluster here is just a group of points picked out by some chosen criterion — density, proximity to a centroid, connectivity in the neighbor graph, a cut in a hierarchy. Different clustering methods optimize different objectives and will not agree. Whatever method produces it, the same rule from Chapter 2 applies: the cluster is a geometric object, and its human label is a separate claim that has to be validated by reading members and non-members.

A boundary is always relative to some chosen partition or task notion of groups. A candidate boundary point may sit at similar distances from multiple clusters, or have a neighborhood that mixes several known labels. That does not make ranking instability automatic. Test it: perturb the query text, swap the model version, change k, change the metric, and measure how much the top-k list turns over (neighbor_overlap(x, perturbation)). This chapter does not run that stability measurement; it identifies it as the next diagnostic when a point appears to lie between groups.

The manifold hypothesis, treated as a hypothesis

There is a comforting story that embeddings of real text lie on a smooth low-dimensional surface — a manifold — inside the high-dimensional space, with distance along the surface tracking meaning. It is worth being careful here, because this chapter does not measure any such surface.

What is defensible is the underlying intuition: high-dimensional observations often concentrate near lower-dimensional structure, and a local neighborhood may have fewer effective degrees of freedom than the ambient dimension. That is the manifold hypothesis, and it is a modeling assumption, not something established by seeing clusters in a plot.

Several tempting embellishments do not follow:

• Separate clusters do not prove there is “no surface between them.” A manifold can have low-density bridges; there can be several disconnected pieces; or the data may not fit a clean manifold model at all. And the Euclidean distance between two points is mathematically defined regardless. The real question is never whether the distance exists — it always does — but whether that distance supports the semantic inference you want to make. Across a sparse gap, usually it does not.
• Rare-in-the-corpus is not the same as “off-manifold.” A rare item can sit squarely inside a well-populated semantic region; a common item can be geometrically odd. If you mean “few nearby examples in this index,” measure that directly with the k-th-neighbor distance and say so.
• Local intrinsic dimension may vary from region to region — a tight near-duplicate cluster plausibly has fewer degrees of freedom than a diverse region. Whether that is true, and by how much, is a measurement, and it belongs to Chapter 7.

The practical residue is a question, not a theorem: does the local sampling support the semantic use you want to make of distance? A dense neighborhood gives you more nearby observations with which to test that claim; a sparse neighborhood gives you less local evidence. Neither density nor isolation, by itself, proves that the metric is semantically trustworthy or untrustworthy. That uncertainty is exactly where a 2D map is easiest to over-read.

Visualization, briefly

Chapter 2 measured this directly: projecting RELATE to 2D kept about 15% of the variance and only about 20% of each item’s ten nearest neighbors, and its dominant axis correlated with sentence length. Nothing in this chapter changes that verdict, and it is worth restating the mechanics precisely. t-SNE and UMAP optimize different objectives and expose different controls — t-SNE has perplexity; UMAP has n_neighbors and min_dist — so they are not interchangeable knobs on one method. Both can distort apparent density substantially. The safe rule: do not infer full-space density, inter-group distance, or the reality of a gap from a 2D layout without checking it in the source space. Discover in the picture; verify in the space.

Predict, then measure: hubness on RELATE

MEASURED on RELATE v0.1, Wave 1 row 1.5 — artifact experiments/embeddings-from-first-principles/wave1/artifacts/hubness.json. Five encoders, L2-normalized embeddings, k = 10.

Two separate graphs are involved, and keeping them apart makes the result easy to reason about:

1. Hub detection builds the item-to-item 10-NN graph over all 1,173 RELATE items (cosine from V Vᵀ, self-scores excluded) and counts, for each item, how many other items’ top-10 lists it appears in.
2. The intervention is a query-to-item retrieval evaluation: for each RELATE query, rank the items by cosine to the query, optionally drop the detected hub items from the candidate pool, and score Recall@10 against the graded-relevant set.

First, the geometry. The 11 highest-degree items — about 0.9% of the corpus — and how large the right tail is:

Every model’s in-degree distribution is right-skewed. If neighbor participation were perfectly uniform, those 11 items would hold about 0.9% of the 11,730 neighbor slots; measured, they hold 2.5% to 3.5% — roughly three to four times their proportional share. The three statistics answer different questions: skew summarizes asymmetry across the distribution, max/mean describes the most extreme observed item, and top-tail share shows how much incoming-neighbor mass the selected high-degree group captures. Together they establish concentration without telling us why those items attract neighbors.

The two encoders with the lowest random-pair cosine baselines in Chapter 5 (MiniLM, mpnet) also have the two lowest in-degree skews here, while the other three are higher. With only five model-level observations and no controlled intervention on anisotropy, treat that pattern as a clue worth testing, not evidence that anisotropy causes hubness.

Now make the naive policy falsifiable. If the highest-degree items were predominantly irrelevant generic distractors that displaced relevant results, then excluding them should improve Recall@10, or at least avoid reducing it.

The measured intervention goes the other way: Recall@10 drops slightly for all five encoders.

MEASURED: the in-degree distribution is concentrated for every tested encoder (skew 0.58 to 1.90; top-11 items hold 2.5–3.5% of neighbor slots). Blindly excluding those detected hubs lowered Recall@10 in every case (for example, bge-large 1.0000 → 0.9960, mpnet 1.0000 → 0.9907). On this corpus and query set, item-item kNN in-degree alone is not a valid suppression criterion.

What this establishes and what it does not:

• It establishes that a suppression rule of the form “drop the highest-degree ~1% of items” is not justified here. Because Recall@10 decreases when those candidates are excluded, at least some removed items were needed to recover graded-relevant results for some RELATE queries. The artifact does not record which hub texts those were or why they had high in-degree.
• It does not establish that hubness causes no retrieval harm. This intervention is not a clean counterfactual — there is no version of the same representation without its hubs to compare against. Removing high-degree items simultaneously removes any harmful generic neighbors, removes genuinely relevant items, and changes which candidates are available at all. A drop in Recall shows the policy is wrong for this setup; it does not isolate the causal effect of hubness itself.
• The scope is Recall@10 on the RELATE query set. Nothing here speaks to precision, nDCG, calibration, result diversity, latency, or behavior on other tasks, other values of k, other data distributions, or much larger indexes.
• The hub identities were not recorded. This experiment measured degrees and recall, not what the hub texts are; classifying them is the next diagnostic, not a result to report.

Detector and policy are different objects

The chapter’s reusable lesson is a separation. A hubness detector measures unusual neighbor participation — in-degree skew, max, tail share. A hub-suppression policy takes an action based on that measurement — reweighting, mutual-k-NN, dropping candidates. The detector can be perfectly valid while the policy is harmful, which is exactly what the RELATE result shows: the geometry really is lumpy, and acting on the lumpiness the obvious way made retrieval worse.

Detect the irregularity. Diagnose what it is. Measure the consequence before you intervene.

Mitigations for genuine hub-induced harm do exist — mutual-k-NN, local scaling, similarity normalization, centering — and they belong in the retrieval policy layer (Chapter 12). The point here is upstream of any of them: a measured anomaly is not a control decision.

Lab 6: measure the hubness, then try to act on it

MEASURED — artifact experiments/embeddings-from-first-principles/wave1/artifacts/hubness.json (5 encoders, k = 10). REPRODUCIBLE — run_wave1.py 1.5.

Question. Is neighbor-list participation uneven across the space, and does removing the most-connected items improve retrieval?

Step 1 — build the directed k-NN graph. For each encoder, compute the item-to-item 10-NN graph over all 1,173 items. Check the arithmetic: mean in-degree is 10.0 for every model, as it must be. The preserved Wave 1 artifact records maximum in-degree, skew, and the share of neighbor slots held by the top ~1%. When you rerun the analysis, also record the fraction of items with in-degree zero; that additional anti-hub statistic is useful, but it is not present in the current artifact.

Step 2 — inspect the tail (reader exercise; not preserved as an artifact). Read the ten highest-degree items for one encoder. Do not assume a type. Classify each candidate cause: exact or near-duplicate, boilerplate that matches weakly everywhere, a broadly useful representative answer, malformed text, ordinary domain-common phrasing, or something else. The histogram tells you concentration exists; only reading the items tells you what it is.

Step 3 — intervene. Remove the top ~1% of items by in-degree from the retrieval candidate pool and re-score Recall@10.

Step 4 — read the negative result.

bge-large:  1.0000 → 0.9960
bge-small:  0.9706 → 0.9675
mxbai:      1.0000 → 0.9960
minilm-l6:  0.9932 → 0.9904
mpnet-base: 1.0000 → 0.9907

Recall fell for every model. High in-degree did not mark an item as safely removable; the drop implies that the excluded set contained items needed for relevant retrieval on at least some RELATE queries.

Step 5 — design the experiment that would actually help. The useful question is not merely “does my space have high-in-degree points?” but “which kinds of hub hurt which kinds of query, under which retrieval conditions?” That requires the Step 2 classification plus a per-query-type breakdown — a diagnosis, not a blanket rule.

Try it yourself

Rerun the intervention under your own retrieval conditions rather than assuming RELATE’s result transfers. Vary:

index size:      1k → 10k → 100k → ...
k:               5 → 10 → 25 → 50
hub threshold:   top 0.1% → 0.5% → 1% → 5%
corpus mix:      duplicate rate, domain balance, query distribution

The goal is to find whether there is any regime — scale, task, hub type — where suppression improves your metric. If you cannot find one, do not suppress. And do not conclude from a small clean index that hubs are harmless everywhere; that is equally unproven.

Companion component: the neighborhood report

The companion design for the Observatory is a standing neighborhood diagnostic, so lumpiness is checked deliberately rather than discovered only during an incident. Keep persisted measurements separate from diagnostics that are proposed but not yet emitted by the current Wave 1 artifact, and — most importantly — make any intervention result travel with the diagnosis.

neighborhood_report:
  metric:  <cosine | l2 | ...>
  k:       <int>

  indegree:
    mean:               <float>   # derivable: equals k
    max:                <int>     # measured in current artifact
    skew:               <float>   # measured in current artifact
    top_tail_share:     <float>   # measured in current artifact
    zero_degree_fraction: <float> # recommended additional diagnostic

  local_support:
    kth_neighbor_distance: <per-item>  # recommended additional diagnostic

  inspected_hubs:                 # analyst input, not automatic
    ids: [...]
    annotations: [...]            # duplicate | boilerplate | prototype | malformed | ...

  intervention:                   # measured when an intervention is actually run
    policy:                       # e.g. "exclude top ~1% by in-degree"
    task_metric:                  # e.g. "Recall@10 on RELATE queries"
    before:
    after:

  local_intrinsic_dimension:      # deferred to Chapter 7

The report authorizes no action on its own. It records what was measured, identifies what still needs inspection, and forces any suppression policy to travel with the task-level effect it actually produced. That keeps a detector from quietly turning into a policy.

Failure modes

Each is a mistake, why it is tempting, and the check.

• Reading high in-degree as importance or as badness. Tempting because a highly connected point looks either popular or parasitic, and the cosine score cannot tell you which. Check: read the hub texts, then run a task-level intervention and measure the metric you actually care about before acting.
• Suppressing an anomaly before testing the policy. Tempting because a measured irregularity feels like a defect to fix. Check: the detector and the policy are separate — confirm the suppression rule improves your metric on your data before adopting it. This chapter’s experiment is the cautionary case.
• Trusting k-NN quality uniformly across the space. Tempting because a strong global retrieval metric looks like permission to trust every neighborhood equally. Check: inspect in-degree and k-th-neighbor-distance distributions, then measure task quality by region before claiming a regional failure.
• Reading a 2D gap as full-space structure. Tempting because the layout looks like a map. Check: treat the gap as a hypothesis, vary the projection settings, and then test the intended source-space claim directly — for example with full-space neighbor overlap, distances, or a cluster-separation statistic appropriate to the task (Chapter 2).
• Treating local density as relevance. Tempting because “lots of neighbors” feels like “well supported.” Check: density measures geometric crowding at a stated k and metric, not correctness. Dense regions may be useful semantic neighborhoods, duplicates, templates, or something else.

What this chapter established

• The k-NN graph is directed, and its mean in-degree is exactly k — so hubness is invisible in the mean by construction. It lives in the shape of the distribution around that fixed value: skew, maximum, top-tail share.
• A hub is a high-in-degree item under a stated graph construction, nothing more. Its content type, cause, and usefulness are separate empirical questions, and this experiment answered none of them.
• Excluding the top ~1% by in-degree lowered Recall@10 for all five encoders — which rejects item-item in-degree as a suppression rule here, without isolating what hubness itself costs.
• Local density is a crowding diagnostic at a stated k and metric, not a semantic label; the manifold picture remains a modeling hypothesis this chapter does not measure.
• Detect the irregularity. Diagnose what it is. Measure the consequence before you intervene. The neighborhood report exists to keep those three steps from collapsing into one.

Next

The k-NN graph is lopsided, and Chapter 5 showed the axes are arbitrary. Both point at the same open question: how many independent directions does the structure a task relies on actually require? The next chapter measures that — the singular-value spectrum, rank and effective rank, and several notions of intrinsic dimension — and asks which of those numbers is the one worth reporting for a given space and task.