RobustVis: High-Dimensional Data Visualization from Sparse Similarity Graphs with Uncertain Non-edges

Neighborhood-graph-based high-dimensional data visualization methods depend on pairwise relations that are inevitably imperfect. Under conventional cross-entropy objectives, a single false-positive edge or false-negative non-edge can have unbounded loss and gradient influence near the boundary of the low-dimensional affinity. We introduce RobustVis, a bounded-influence optimization framework for high-dimensional data visualization. Its asymmetric positive- and negative-pair losses place robustness parameters inside the logarithms, uniformly bounding pairwise losses and derivatives while retaining strong attraction for trusted edges. We establish perturbation bounds for both the objective and the embedding gradient under graph corruption, and derive an importance-weighted negative-pair estimator for scalable optimization. Moreover, we develop an extension for RobustVis that can effectively account for uncertainty in positive edges. Experiments on synthetic manifold data and diverse real datasets demonstrate the effectiveness of the proposed methods in comparison to strong baselines.