Neighborhood Preservation Probe¶
Validation probe — instantiates Local-Chart Atlas Modeling
Checks whether an embedding or projection keeps each point's true near-neighbors near, rather than inventing false ones at folds.
The Neighborhood Preservation Probe asks one sharp question of a finished embedding or projection: does each point's set of nearest neighbours in the low-dimensional view match its true near-neighbours in the original space? A projection can look smooth and still lie locally — pulling unrelated points together at a fold (false neighbours) or tearing genuine neighbours apart (missed neighbours). The probe scores that neighbour-set fidelity, point by point and region by region, against a stated tolerance. Its defining move is to judge who is near whom — the local rank and membership of neighbourhoods — rather than how far apart things are or whether the space is a manifold at all. It validates an existing representation's local honesty; it does not measure route distance, and it does not decide whether the manifold was real to begin with.
Example¶
A search team builds a 2-D UMAP visualization of document embeddings so analysts can eyeball clusters of related articles. The plot looks reassuringly tidy — neat islands of colour — but before anyone trusts it for "show me documents like this one," the team runs a Neighborhood Preservation Probe. For a sample of documents it compares each one's true nearest neighbours in the original high-dimensional embedding against its nearest neighbours in the 2-D plot. Most points preserve their neighbourhoods well, but a band near where two clusters meet scores badly: documents about tax law and tax software have been laid side by side on the page though they are far apart in the source space — false neighbours created by the projection squashing a fold.
The probe reports a preservation score per region and marks that seam as untrustworthy for neighbour queries. The team does not throw the plot away; they stop reading "adjacent on screen" as "similar in meaning" in the flagged band, and route similarity questions there back to the high-dimensional index. The picture stays useful for overview and becomes honest about where its local structure cannot be trusted.
How it works¶
- Sample points and take their true neighbours. For each sampled case, list its k nearest neighbours in the original space — the ground truth of who is near whom.
- Take the embedded neighbours. List the same point's k nearest neighbours in the projection.
- Score the overlap. Measure how much the two neighbour sets agree — capturing both false neighbours (near in the plot, far in truth) and missed neighbours (near in truth, far in the plot).
- Localize the failures. Aggregate the scores by region so the low-fidelity folds and seams are named, not just an overall average.
Tuning parameters¶
- Neighbourhood size k — how many neighbours define "local"; small k probes fine structure but is noisy, large k is stable but blurs the local question into a global one.
- Preservation budget — the minimum neighbour-agreement score a region must clear to be trusted; strict budgets flag more seams, loose ones pass distortion.
- False- vs missed-neighbour weighting — whether inventing false neighbours or losing true ones is penalized more; the choice depends on whether the cost is spurious matches or missed ones.
- Sampling density — how many points are probed and where; dense sampling near suspected folds finds local failures a uniform sample would average out.
When it helps, and when it misleads¶
Its strength is that it targets the exact lie of a pretty projection — local neighbour distortion — and turns it into a per-region score, so an embedding can be trusted where it is faithful and distrusted where it is not, instead of wholesale. It formalizes what metrics like trustworthiness and continuity[1] were built to capture: false neighbours and missed neighbours as distinct, measurable failures.
Its failure mode is scale-blindness: a probe fixed at one k reports fidelity at that radius only, and an embedding can preserve tight neighbourhoods while badly distorting slightly-larger ones, so a single passing score can flatter a projection that fails at another scale. Its classic misuse is running the probe once, globally, and reading a decent average as a licence to trust the whole plot — including the folds the average washed out. The guarding discipline is to probe at several neighbourhood sizes and report scores by region, so local failures survive aggregation rather than being hidden by it.
How it implements the components¶
embedding_preservation_target— it is the check on this target: whether the embedding meets a stated standard for keeping true neighbours together.distortion_budget— the preservation-score threshold is a distortion budget on local neighbour error, drawing the line between trustworthy and untrustworthy regions.
It does not test the manifold hypothesis or carve chart domains — the manifold_hypothesis_scope and local_chart_domain are Manifold Learning Diagnostic's — and it does not measure route distance: the navigation_path_rule geodesics and hole_or_loop_marker flags belong to Geodesic or Path-Distance Audit. This probe judges neighbour membership; those siblings judge whether structure exists and how far apart things really are.
Related¶
- Instantiates: Local-Chart Atlas Modeling — it validates that an embedding used inside the atlas preserves local neighbourhoods where the atlas relies on them.
- Sibling mechanisms: Manifold Learning Diagnostic · Geodesic or Path-Distance Audit · Local Model Ensemble with Gating · Chart Atlas Map · Round-Trip Consistency Test · Overlap Transition Table · Coordinate Translation Protocol · Boundary Case Path Trace · Atlas Stewardship Review
Editorial Notes¶
Form Classification¶
Form family: Assessment, Review & Assurance
Rationale: The mechanism compares original-space and projected neighbor sets and produces a localized validity finding about false and missed neighborhoods.
Nearest alternative: Experiment, Test & Rehearsal — It runs a validation probe, but the defining output is assurance about an existing embedding rather than exploratory learning through varied conditions.
Review outcome: Adjudicated after independent review; high confidence.
Origin Attribution¶
Primary origin: Data Science & Analytics
Origin pattern: Cross-disciplinary synthesis
Present-day reach: Multi-domain
Rationale: Dimensionality-reduction research developed neighborhood-fidelity probes to detect false and missing neighbors in an embedding.
Related originating lineages:
- Computer Science & Software Engineering — Embedding algorithms and approximate-neighbor systems supply the computational object of the probe.
- Mathematics — Metric geometry and topology supplied the formal notion of preserving local neighborhoods under a mapping.
Review resolution: Both independent reviews agree on primary origin data_science; reconciliation resolves alternate_origin_disagreement, domain_reach_disagreement, encyclopedia_synthesis_disagreement. Formative alternate lineages retained: mathematics, computer_science. The broader reach of later applications is kept separate as domain_reach=multi_domain; origin_mode=cross_disciplinary_synthesis describes the historical relationship among lineages. Confidence is conservatively reconciled to high, and encyclopedia_synthesis=true preserves the reviewers' boundary judgment.
Encyclopedia synthesis: The exact catalogued form synthesizes established practice rather than reproducing a single standard historical label.
Review outcome: Reconciled after independent review; high confidence.
References¶
[1] Venna, Jarkko, and Samuel Kaski. "Neighborhood Preservation in Nonlinear Projection Methods: An Experimental Study". Artificial Neural Networks — ICANN 2001, LNCS 2130, 485–491 (2001). Provides complementary quantitative measures for false display neighbours and for original neighbours lost in projection. registry ↩