On Out-of-sample Embedding in UMAP

• URL: http://arxiv.org/abs/2606.04451v1
• Date: Wed, 03 Jun 2026 04:54:45 GMT
• Title: On Out-of-sample Embedding in UMAP
• Abstract summary: Neighbor embedding algorithms reveal correlations in high-dimensional data by constructing an equivalent graph representation in a lower-dimensional space.<n>We show how to overcome the repulsion effect'' by optimizing pairwise interactions within the original k-nearest-neighbor graph.<n>We also show that the repulsion effect is naturally mitigated when a parameterized UMAP is employed to embed the data.
• Score: 0.28647133890966986
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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.

Related papers

• Understanding and Improving UMAP with Geometric and Topological Priors: The JORC-UMAP Algorithm [1.7484982792736636]
  dimensionality reduction techniques, particularly UMAP, are widely used for visualizing high-dimensional data.<n>We introduce Ollivier-Ricci curvature as a geometric prior, reinforcing edges at geometric bottlenecks and reducing redundant links.<n>Experiments on synthetic and real-world datasets show that JORC-UMAP reduces tearing and collapse more effectively than standard UMAP and other DR methods.
  arXiv  Detail & Related papers  (2026-01-23T08:42:56Z)
• EmbedOR: Provable Cluster-Preserving Visualizations with Curvature-Based Stochastic Neighbor Embeddings [18.64124104660797]
  Neighbor Embedding (SNE) algorithms like UMAP and tSNE often produce visualizations that do not preserve the geometry of noisy and high dimensional data.<n>We propose EmbedOR, a SNE algorithm that incorporates discrete graph curvature.<n>Our algorithmally embeds the data using a curvature-enhanced distance metric that emphasizes underlying cluster structure.
  arXiv  Detail & Related papers  (2025-09-03T20:38:39Z)
• Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
  We introduce a new adaptive $k$-nearest neighbours ($kK$-NN) algorithm that explores the local curvature at a sample to adaptively defining the neighborhood size. Results on many real-world datasets indicate that the new $kK$-NN algorithm yields superior balanced accuracy compared to the established $k$-NN method.
  arXiv  Detail & Related papers  (2024-09-08T13:08:45Z)
• Boundary Detection Algorithm Inspired by Locally Linear Embedding [8.259071011958254]
  We propose a method for detecting boundary points inspired by the widely used locally linear embedding algorithm.<n>In the presence of high-dimensional noise, we propose a framework aimed at enhancing boundary detection in noisy data.
  arXiv  Detail & Related papers  (2024-06-26T16:05:57Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• Far Away in the Deep Space: Dense Nearest-Neighbor-Based Out-of-Distribution Detection [33.78080060234557]
  Nearest-Neighbors approaches have been shown to work well in object-centric data domains. We show that nearest-neighbor approaches also yield state-of-the-art results on dense novelty detection in complex driving scenes.
  arXiv  Detail & Related papers  (2022-11-12T13:32:19Z)
• Riemannian classification of EEG signals with missing values [67.90148548467762]
  This paper proposes two strategies to handle missing data for the classification of electroencephalograms. The first approach estimates the covariance from imputed data with the $k$-nearest neighbors algorithm; the second relies on the observed data by leveraging the observed-data likelihood within an expectation-maximization algorithm. As results show, the proposed strategies perform better than the classification based on observed data and allow to keep a high accuracy even when the missing data ratio increases.
  arXiv  Detail & Related papers  (2021-10-19T14:24:50Z)
• Spatial-spectral Hyperspectral Image Classification via Multiple Random Anchor Graphs Ensemble Learning [88.60285937702304]
  This paper proposes a novel spatial-spectral HSI classification method via multiple random anchor graphs ensemble learning (RAGE) Firstly, the local binary pattern is adopted to extract the more descriptive features on each selected band, which preserves local structures and subtle changes of a region. Secondly, the adaptive neighbors assignment is introduced in the construction of anchor graph, to reduce the computational complexity.
  arXiv  Detail & Related papers  (2021-03-25T09:31:41Z)
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams [69.4411417775822]
  Adversarial examples are a widely studied phenomenon in machine learning models. We propose an algorithm for evaluating the adversarial robustness of $k$-nearest neighbor classification.
  arXiv  Detail & Related papers  (2020-11-19T08:49:10Z)
• DecAug: Augmenting HOI Detection via Decomposition [54.65572599920679]
  Current algorithms suffer from insufficient training samples and category imbalance within datasets. We propose an efficient and effective data augmentation method called DecAug for HOI detection. Experiments show that our method brings up to 3.3 mAP and 1.6 mAP improvements on V-COCO and HICODET dataset.
  arXiv  Detail & Related papers  (2020-10-02T13:59:05Z)
• Parametric UMAP embeddings for representation and semi-supervised learning [0.03823356975862005]
  UMAP is a non-parametric graph-based dimensionality reduction algorithm to find low-dimensional embeddings of structured data. We show that Parametric UMAP performs comparably to its non-parametric counterpart while conferring the benefit of a learned parametric mapping. We then explore UMAP as a regularization, constraining the latent distribution of autoencoders, parametrically varying global structure preservation, and improving classifier accuracy for semi-supervised learning.
  arXiv  Detail & Related papers  (2020-09-27T23:45:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.