💻 computer science

Local Neighborhood Instability in Parametric Projections: Quantitative and Visual Analysis

This paper introduces a quantitative and visual framework for evaluating the local stability of parametric projections against input perturbations, demonstrating its ability to identify unstable regions in UMAP- and t-SNE-based neural projectors that traditional metrics fail to detect.

Original authors: Frederik L. Dennig, Daniel A. Keim

Published 2026-04-24

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Frederik L. Dennig, Daniel A. Keim

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive, messy room filled with thousands of different objects (like a giant warehouse of shoes, clothes, or handwritten numbers). You want to take a photo of this room, but you need to flatten it onto a 2D piece of paper so humans can understand it. This is what Dimensionality Reduction does: it squishes a complex 3D (or 1000D) world into a simple 2D map.

For a long time, the best way to do this was like taking a snapshot of the entire room at once. But if you add just one new shoe to the room, you have to take the whole picture again from scratch. That's slow and annoying.

The New Solution: The "Smart Camera"
Recently, scientists built a "Smart Camera" (a neural network) that learns the rules of the room. Once it learns, it can instantly snap a photo of any new object without re-taking the whole picture. This is called a Parametric Projection. It's great for real-time use, like streaming video or interactive apps.

The Problem: The "Wobbly Map"
Here's the catch: What if the camera is a bit shaky? What if the lighting changes slightly, or the object is moved just a tiny bit (like a measurement error or a smudge on a sensor)?

In a perfect world, a tiny change in the object should result in a tiny change on the map. But with these "Smart Cameras," a tiny wobble in the input can sometimes cause the object to jump wildly across the map, landing in the wrong neighborhood. It's like if you moved your coffee cup one inch to the left, but on the map, it suddenly teleported to the other side of the room.

The Paper's Mission: The "Stability Test"
The authors of this paper built a framework to test how "wobbly" these Smart Cameras are. They didn't just look at how pretty the map looks; they asked: "If I nudge the data slightly, does the map stay calm, or does it freak out?"

They used three main tools to check this:

The "Drift Meter" (Quantitative Measures):
- They picked a few "anchor" points (like the center of a group of red shoes).
- They added tiny, invisible "shakes" (noise) to those shoes.
- They measured how far the shoes moved on the map.
- The Result: They found that some cameras are very sensitive. A tiny shake sends the shoes flying. They also found that adding a specific "stabilizer" (called Jacobian Regularization) acts like a shock absorber, keeping the shoes in place even when the camera shakes.
The "Arrow Map" (Visual Analysis):
- Instead of just numbers, they drew arrows. Imagine an anchor point in the center. When they shake the data, the arrows show where the points land.
- Stable Camera: The arrows are short and point in all directions equally (like a calm breeze).
- Unstable Camera: The arrows are long and all point in the same weird direction (like a strong wind blowing everything off course). This reveals that the map isn't just noisy; it's biased.
The "Neighborhood Guard" (Voronoi Assignment):
- They divided the map into territories, like a game of chess, where each territory belongs to a specific group (e.g., the "Red Shoe Zone").
- They asked: "If I shake a Red Shoe, does it accidentally land in the Blue Shoe Zone?"
- The Result: Without the stabilizer, many shoes crossed the border and got mislabeled. With the stabilizer, they stayed safely in their own zone.

The Big Surprise
The most interesting finding is that the old, standard way of judging these maps (checking if neighbors stay neighbors) failed completely.

Old Metric: "Hey, the neighbors look fine! The map is 95% accurate!"
New Metric: "But if you nudge the data, the whole neighborhood shifts 80%!"

It's like judging a bridge by looking at it when it's empty. It looks fine. But the new test asks, "What happens when a truck drives over it?" The old test missed the fact that the bridge was actually wobbly and dangerous.

The Takeaway
If you are building a system that needs to handle new data in real-time (like a self-driving car or a live medical monitor), you can't just trust the standard "pretty map" metrics. You need to test for stability.

The authors show that by adding a simple "shock absorber" (Jacobian Regularization) to the AI, you can make the map rock-solid. It's a small tweak that prevents the map from going crazy when the real world gets a little noisy.

In short: Don't just check if the map looks right; check if it stays right when you poke it.

1. Problem Statement

Parametric dimensionality reduction (DR) methods, particularly those based on Neural Networks (NNs) like Multi-Layer Perceptrons (MLPs), offer significant advantages over non-parametric methods (e.g., standard UMAP, t-SNE) by enabling real-time embedding of new data points without recomputing the entire global structure. However, a critical gap exists in evaluating these models: local neighborhood instability.

While standard evaluation metrics (e.g., Trustworthiness, Continuity) assess how well a projection preserves the original neighborhood structure of the training data, they fail to measure sensitivity to input perturbations. In real-world scenarios involving measurement noise or data drift, small variations in high-dimensional input can lead to unpredictable, large, or systematically biased shifts in the 2D embedding. The authors argue that current evaluation frameworks do not adequately address whether a parametric projection is robust enough for visual analytics, where analysts must trust that spatial patterns reflect data structures rather than artifacts of instability.

2. Methodology: Stability Evaluation Framework

The authors propose a comprehensive framework to probe and visualize the local stability of parametric projections (specifically MLPs approximating UMAP and t-SNE) under Gaussian perturbations.

A. Experimental Setup

Base Models: The framework uses MLPs trained to approximate non-parametric projections (UMAP and t-SNE) on MNIST and Fashion-MNIST datasets.
Anchor Selection: Representative anchor points are selected based on class centroids in the projection space to ensure they are not outliers.
Perturbation Strategy: Isotropic Gaussian noise is added to anchor samples. The noise scale ( $\sigma$ ) is derived from a target radius $r$ (set to the 0.25th percentile of pairwise distances) to ensure perturbations remain within a realistic, interpretable neighborhood.
Regularization: The study compares standard MLPs against those trained with Jacobian Regularization, which penalizes the Frobenius norm of the input-output Jacobian to enforce local smoothness.

B. Quantitative Stability Measures

The authors introduce three specific metrics to quantify instability:

Mean Displacement ( $D_{dev}$ ): Measures the average magnitude of the shift in the 2D embedding caused by noise ( $\|z - z_0\|$ ). Lower values indicate better stability.
Displacement Bias ( $D_{bias}$ ): Measures the systematic drift of the mean projected position away from the original anchor ( $\|\frac{1}{N}\sum z_i - z_0\|$ ). High bias indicates the model consistently pushes points in a specific direction under noise.
Nearest-Anchor Assignment Error ( $E_{NA}$ ): Calculates the probability that a perturbed sample moves into the Voronoi region of a different anchor class. This directly measures the risk of misclassification or cluster confusion due to noise.

C. Visual Diagnostics

To complement quantitative metrics, three visualizations are proposed:

Anchor Lines: Vectors connecting the original anchor to its noisy projections, revealing directional bias and coherence.
Local PCA Ellipsoids: Principal Component Analysis performed on the cloud of noisy projections around an anchor. The shape and orientation of the resulting ellipsoid indicate anisotropy (directional amplification/attenuation of noise).
Voronoi Assignment: Visualizes which anchor's region a perturbed point falls into, highlighting areas where noise causes samples to cross decision boundaries.

3. Key Contributions

Novel Stability Metrics: Introduction of $D_{dev}$ , $D_{bias}$ , and $E_{NA}$ to specifically quantify local neighborhood instability in parametric projections, addressing a blind spot in standard DR evaluation.
Visual Analysis Framework: A suite of visual diagnostics (Anchor Lines, Local PCA, Voronoi) that link quantitative stability measures to spatial deformations in the embedding.
Empirical Validation: A rigorous comparison of MLP-based parametric UMAP and t-SNE across different network sizes and regularization strategies.
Open Science: Release of analysis code, results, and source code on OSF and GitHub to ensure reproducibility.

4. Key Results

The evaluation was conducted on MNIST and Fashion-MNIST datasets using MLP-small and MLP-large architectures, with and without Jacobian regularization (+J).

Failure of Standard Metrics: Traditional metrics (Trustworthiness and Continuity) remained nearly constant across all models (ranging from 0.85 to 0.94), failing to detect the massive stability differences revealed by the new metrics.
Impact of Jacobian Regularization:
- Drastic Stability Gains: Jacobian regularization reduced mean displacement by 28–85% across all settings. For example, on MNIST (UMAP), MLP-small+J reduced displacement from 1.80 to 0.265 (an 85% reduction).
- Error Reduction: The Nearest-Anchor Assignment Error ( $E_{NA}$ ) dropped significantly, approaching zero for regularized models (e.g., from 0.294 to 0.006 on MNIST UMAP).
- Bias Correction: Unregularized models often exhibited high displacement bias (systematic drift), whereas regularized models showed near-isropic, random noise distribution.
Network Capacity vs. Regularization: Increasing network capacity alone (MLP-large vs. MLP-small) provided only moderate stability improvements. Jacobian regularization was found to be substantially more effective than simply increasing model size.
No Trade-off with Reconstruction: The most stable models (MLP-large+J) also achieved the lowest Mean Squared Error (MSE) on reconstruction, indicating that stability and fidelity can be optimized simultaneously.

5. Significance and Implications

Trust in Visual Analytics: The paper demonstrates that two models can have identical neighborhood preservation scores but vastly different behaviors under noise. For visual analytics, this means analysts cannot rely solely on Trustworthiness/Continuity; they must verify that spatial patterns are robust to data drift.
Practical Guidance: The study provides a concrete recommendation: Pair parametric projections with smoothness constraints (like Jacobian regularization) before deployment in noise-prone environments. This yields more stable, trustworthy embeddings without sacrificing reconstruction quality.
New Evaluation Paradigm: The work shifts the focus of DR evaluation from static structural preservation to dynamic robustness, offering a necessary toolkit for deploying parametric DR in streaming and interactive applications.

In conclusion, the authors successfully identify a critical vulnerability in parametric projections—local instability under noise—and provide both the mathematical tools and visual methods to detect and mitigate it, primarily through Jacobian regularization.