When One Point Is Not Enough: Addressing Ambiguous Instances in Dimensionality Reduction by Splitting

Technical Summary: Addressing Ambiguous Instances in Dimensionality Reduction by Splitting

Problem Definition
Dimensionality Reduction (DR) is a fundamental tool for visualizing high-dimensional data, yet it is inherently a lossy process. While existing literature has cataloged various distortions, such as manifold tearing, this paper identifies a previously overlooked source of visual artifacts: ambiguous instances. These are data points that are highly similar to multiple, mutually dissimilar neighborhoods in the high-dimensional space.

Standard DR methods map each data instance to a single point in the visual space. Consequently, an ambiguous instance cannot faithfully represent its membership in multiple distinct neighborhoods simultaneously. It is forced into a single location, resulting in partial neighborhood embedding. In this state, the instance appears to belong to only one neighborhood (or none), obscuring its true relationship to other dissimilar groups. This artifact is particularly problematic for instance-level analyses, such as Explainable AI (XAI) or single-cell biology, where understanding the precise neighborhood structure is critical. Existing metrics like trustworthiness and continuity fail to distinguish partial neighborhood embedding from other distortions because they operate on the final embedding without access to the underlying data ambiguity.

Methodology
The authors propose a graph-based approach to identify and resolve these ambiguities by "splitting" ambiguous instances into multiple points, each placed within its respective neighborhood. The methodology follows the two-phase DR framework (relationship and mapping) introduced by Paulovich et al.:

1. Graph Construction and Sparsification:

   • The high-dimensional relationships are modeled as an undirected weighted graph $G$.
   • To expose meaningful neighborhood structures and remove redundant edges caused by incidental proximity, the authors apply spectral sparsification using the Spielman-Srivastava algorithm. This produces a reduced graph $\bar{G}$ that preserves the structural and algebraic properties of the original while removing weak connections.

2. Identification of Ambiguous Instances:

   • Ambiguity is defined topologically. The authors adapt the concept of Local Articulation Points (LAPs). A vertex is considered an LAP if its removal increases the number of connected components within a local $r$-step induced neighborhood.
   • An instance is deemed ambiguous if it is an LAP in the sparsified graph $\bar{G}$. This indicates the instance connects disjoint neighborhoods that would otherwise be separated.
   • Lemma 3.1 is utilized to optimize computation: if a vertex is not an LAP at a certain radius $r$, it cannot be an LAP at any larger radius $r' > r$.

3. Vertex Splitting and Decision Rules:

   • Once an ambiguous vertex $v_i$ is identified, it is split into $K$ copies, where $K$ corresponds to the number of connected components remaining after $v_i$ is removed from its local neighborhood.
   • Decision Rules: Not all potential splits are executed. The approach filters out:
     • LAP-LAP connections: If an edge bridges two neighborhoods and both endpoints are LAPs, the split is suppressed to avoid creating artificial isolation.
     • Weak connections: A user-defined threshold $\tau_w$ (ratio of connection strength to the strongest component) filters out splits where the connection to a neighborhood is too weak to be meaningful. This prevents the creation of visually isolated points due to insufficient attraction forces.

4. Mapping and Visualization:

   • The modified graph, containing split vertices, is projected into the visual space using standard local DR techniques (e.g., UMAP or ForceAtlas2).
   • Visual Encoding: Split instances are rendered as distinct markers (e.g., crosses) connected by dashed lines to their original position or to each other, allowing analysts to trace the multiple neighborhood memberships of a single data point.

Key Contributions

• Definition of Partial Neighborhood Embedding: The paper formally introduces and defines this specific artifact arising from ambiguous instances, distinguishing it from general DR distortions.
• Graph-Theoretic Detection: It presents a method to identify ambiguous instances using Local Articulation Points on sparsified neighborhood graphs.
• Splitting Mechanism: The authors propose a concrete, near-linear time complexity approach to split ambiguous instances, replicating them in the projection to reflect multiple neighborhood memberships.
• Empirical Validation: The approach is demonstrated across diverse datasets (SVHN, MNIST, text corpora, and single-cell RNA sequencing), showing that it reveals hidden neighborhood memberships not visible in standard projections.

Results

• Qualitative Insights: In the SVHN dataset, a misclassified digit '1' (predicted as '7') was shown in standard UMAP to belong solely to the '7' neighborhood. The proposed approach split the instance, revealing its simultaneous similarity to the '1' neighborhood, thereby explaining the ambiguity of the classifier's error. Similarly, in text data, a paper on "ILP-Assisted Models for Toxicology" was shown to belong to both ILP and Case-Based Reasoning (CBR) clusters, a duality obscured in standard projections.
• Quantitative Analysis:
  • Sparsification Impact: Experiments measuring preserved $k$-nearest neighbors ($k$NN) showed that spectral sparsification retains local neighborhood structures comparable to the original graph (ratios near 1 for most datasets), though some variance was observed in high-intrinsic-dimensionality single-cell data.
  • Metric Limitations: Standard metrics (trustworthiness and continuity) were found to be ineffective at identifying ambiguous instances, as these points are distributed similarly to non-ambiguous points across the metric distributions.
  • Parameter Sensitivity: Increasing the number of neighbors in the initial graph generally reduced the number of detected splits, as increased connectivity bridges neighborhoods that would otherwise appear disjoint.

Significance and Claims
The paper argues that recognizing ambiguity is essential for interpreting fine-grained local structures in DR. The authors claim that failing to account for ambiguous instances can lead to incomplete or incorrect interpretations, particularly in domains like XAI and biology where instance-level context is vital. By splitting these instances, the method provides a more faithful representation of the data's high-dimensional topology, revealing "previously hidden neighborhood memberships." The work suggests that current DR quality metrics are insufficient for this specific type of artifact and that future evaluation frameworks must account for data-driven ambiguity rather than just mapping-induced instability.