Out-of-Sample Embedding with Proximity Data: Projection versus Restricted Reconstruction

Michael W. Trosset; Kaiyi Tan; Minh Tang; Carey E. Priebe

stat.MLMay 10, 2025

Out-of-Sample Embedding with Proximity Data: Projection versus Restricted Reconstruction

Authors: Michael W. Trosset, Kaiyi Tan, Minh Tang, Carey E. Priebe

Organizations: Department of Statistics, Indiana University. · Department of Statistics, North Carolina State University. · Department of Applied Mathematics & Statistics, Johns Hopkins University.

Abstract

The problem of using proximity (similarity or dissimilarity) data for the purpose of "adding a point to a vector diagram" was first studied by J.C. Gower in 1968. Since then, a number of methods -- mostly kernel methods -- have been proposed for solving what has come to be called the problem of out-of-sample embedding. We survey the various kernel methods that we have encountered and show that each can be derived from one or the other of two competing strategies: projection or restricted reconstruction. Projection can be analogized to a well-known formula for adding a point to a principal component analysis. Restricted reconstruction poses a different challenge: how to best approximate redoing the entire multivariate analysis while holding fixed the vector diagram that was previously obtained. This strategy results in a nonlinear optimization problem that can be simplified to a unidimensional search. Various circumstances may warrant either projection or restricted reconstruction.

Explore similar work

On Out-of-sample Embedding in UMAP
Jun 3, 2026Mohammad Tariqul Islam, Jason W. FleischerManifold Learning Method Rotational Repulsion Mechanism
Euclidean Embedding of Data Using Local Distances
May 19, 2026Dimitris ArabadjisManifold Learning Method Distance
When One Point Is Not Enough: Addressing Ambiguous Instances in Dimensionality Reduction by Splitting
May 22, 2026Diede P. M. van der Hoorn, Alessio Arleo, Fernando V. PaulovichDimensionality Reduction Distortion

Jun 3, 2026 · cs.LGJ/K move · Enter open · S save

On Out-of-sample Embedding in UMAP

Mohammad Tariqul Islam, Jason W. Fleischer

Media Lab, Massachusetts Institute of Technology, Cambridge, MA · Electrical and Computer Engineering, Princeton University, Princeton, NJ

Neighbor embedding algorithms reveal correlations in high-dimensional data by constructing an equivalent graph representation in a lower-dimensional space. An increasingly popular algorithm is Uniform Manifold Learning and Projection (UMAP), which uses algebraic topology to map distances between the two spaces. While it works well on many types of data sets, UMAP has trouble adding out-of-sample points to a pre-existing mapping. In particular, UMAP often places new points on the periphery of the found clusters, rather than in their interiors with their correlated neighbors. Here, we overcome this ``repulsion effect'' by optimizing pairwise interactions within the original k-nearest-neighbor graph. Moreover, we show that parameterizing UMAP obtains better embeddings than non-parametric algorithms, particularly as the data gets more complex (e.g., medical images). We also show that the repulsion effect is naturally mitigated when a parameterized UMAP is employed to embed the data. We characterize different UMAP approaches using trustworthiness, nearest neighbor classifiers, and by analyzing attractive and repulsive forces in the embeddings.

Manifold Learning Method Rotational Repulsion Mechanism Multiple Centrality Measures

Open paper Ask about it PDF

Abstract

Explore similar work

On Out-of-sample Embedding in UMAP

Euclidean Embedding of Data Using Local Distances

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