UMAP Algorithm

Uniform Manifold Approximation and Projection

Mathematical Foundation

Understand topology, manifolds, and fuzzy simplicial complexes

Algorithm Mechanics

Master graph construction and layout optimization phases

Parameter Tuning

Learn to control local/global balance and embedding quality

Practical Applications

Apply UMAP effectively for visualization and analysis

The Dimensionality Reduction Challenge

Goal: Reduce high-dimensional data to 2-3 dimensions while preserving meaningful structure. But what structure should we preserve?

Traditional Methods' Limitations

  • PCA: Only linear relationships, global structure
  • t-SNE: Slow, loses global structure, crowding problem
  • MDS: Expensive, doesn't scale well
  • Autoencoders: Black box, many parameters

UMAP's Innovation

  • Theoretically grounded in topology
  • Preserves local and global structure
  • Computationally efficient
  • Flexible for different data types

The Manifold Hypothesis: High-dimensional data often lies on or near a lower-dimensional manifold embedded in the high-dimensional space.

Mathematical Foundation

UMAP is built on rigorous mathematical foundations from topology and differential geometry, not just heuristics.

Key Mathematical Concepts

  • Riemannian Manifolds: Locally Euclidean spaces with distance metrics
  • Simplicial Complexes: Higher-dimensional generalizations of graphs
  • Fuzzy Sets: Partial membership instead of binary
  • Category Theory: Functorial relationships between spaces

The UMAP Philosophy

Find a low-dimensional representation that best approximates the topological structure of the high-dimensional data manifold.

Why This Matters

  • Theoretical guarantees: Not just empirical success
  • Principled approach: Parameters have clear meanings
  • Generalizability: Works across data types
  • Predictable behavior: Mathematical intuition applies

UMAP Algorithm Overview

Phase 1

Graph Construction

Build fuzzy simplicial complex

→

Phase 2

Layout Optimization

Find optimal low-D embedding

Phase 1: Graph Construction

  • Step 1: Find k-nearest neighbors for each point
  • Step 2: Estimate local connectivity
  • Step 3: Compute fuzzy membership weights
  • Step 4: Symmetrize through fuzzy union

Fuzzy Membership

$$w_{ij} = \exp\left(-\max(0, d_{ij} - \rho_i) / \sigma_i\right)$$

Phase 2: Layout Optimization

  • Initialize: Random or spectral embedding
  • Optimize: Cross-entropy between graphs
  • Forces: Attractive (connected) vs repulsive (disconnected)
  • Converge: Until embedding stabilizes

Graph Construction: The Heart of UMAP

The fuzzy simplicial complex captures both local neighborhoods and global connectivity through mathematically principled weighting.

Local Connectivity

Key Insight

Each point has a locally defined distance metric based on its nearest neighbor distance ($\rho_i$) and scaling factor ($\sigma_i$).

$$\rho_i = d(x_i, \text{1st neighbor})$$

$$\sigma_i \text{ chosen so that } \sum_{j} w_{ij} = \log_2(k)$$

Fuzzy Union

  • Combine directed edges: $w_{ij} \cup w_{ji}$
  • Fuzzy union: $a \cup b = a + b - ab$
  • Creates symmetric, weighted graph
  • Preserves local manifold structure

Layout Optimization

Find a low-dimensional layout that best preserves the high-dimensional fuzzy simplicial complex structure.

Cross-Entropy Optimization

$$CE = \sum_{ij} w_{ij}^{(high)} \log\left(\frac{w_{ij}^{(high)}}{w_{ij}^{(low)}}\right)$$

Minimize difference between high-D and low-D graphs

Force-Based Interpretation

  • Attractive forces: Pull connected points together
  • Repulsive forces: Push unconnected points apart
  • Balance: Prevents collapse and maintains structure

Stochastic Gradient Descent

  • Sample edges: Positive and negative samples
  • Update positions: Move toward optimal layout
  • Cooling schedule: Reduce learning rate over time
  • Epochs: Typically 200-500 iterations

Key Parameters and Their Effects

n_neighbors (5-100)

  • Low values: Focus on local structure
  • High values: Preserve global structure
  • Trade-off: Local detail vs global topology

min_dist (0.0-1.0)

  • Small values: Tight, dense embeddings
  • Large values: Loose, spread out embeddings
  • Control: How tightly packed points can be

metric (distance function)

  • Euclidean: Standard continuous data
  • Cosine: High-dimensional, sparse data
  • Manhattan: Categorical-like features

n_components (2-100)

  • 2-3: Visualization purposes
  • 5-50: Feature extraction
  • Higher: Preserve more structure

UMAP vs Other Methods

PCA

Linear

Fast, interpretable

Global structure only

vs

t-SNE

Non-linear

Great local structure

Slow, loses global

vs

UMAP

Non-linear

Local + global

Fast, scalable

UMAP Advantages

  • Speed: Much faster than t-SNE
  • Global structure: Preserves large-scale topology
  • Scalability: Handles millions of points
  • Flexibility: Many distance metrics supported
  • Theory: Strong mathematical foundation

When to Use UMAP

  • Large datasets (>10k points)
  • Need both local and global structure
  • Exploratory data analysis
  • Preprocessing for clustering

Practical Applications

Data Exploration

  • High-dimensional data visualization
  • Pattern discovery and outlier detection
  • Understanding data distribution
  • Hypothesis generation

Machine Learning Pipeline

  • Feature extraction and engineering
  • Preprocessing for clustering algorithms
  • Anomaly detection in embeddings
  • Semi-supervised learning

Domain Applications

  • Single-cell genomics analysis
  • Image and document clustering
  • Recommendation systems
  • Network analysis and graph embeddings

Best Practices

  • Preprocessing: Scale features appropriately
  • Parameter tuning: Start with defaults, then adjust
  • Validation: Check multiple random seeds
  • Interpretation: Distances in embedding ≠ original distances

Common Pitfalls

  • Over-interpreting cluster distances
  • Ignoring parameter sensitivity
  • Not validating with domain knowledge

Advanced Topics and Future Directions

UMAP Extensions

  • Parametric UMAP: Neural network for new data projection
  • Supervised UMAP: Incorporates target labels
  • Semi-supervised: Partial label information
  • Inverse transforms: Map back to original space

Implementation Considerations

  • Memory: O(n) for sparse implementations
  • Time complexity: O(n log n) for construction
  • Reproducibility: Set random seeds carefully
  • Hyperparameters: Grid search for optimal settings

Research Directions

  • Theoretical analysis: Better convergence guarantees
  • Dynamic embeddings: Handling streaming data
  • Multi-modal data: Integrating different data types
  • Interpretability: Understanding what embeddings preserve

Key Takeaways

  • UMAP provides theoretically grounded dimensionality reduction
  • Balance of local and global structure preservation
  • Efficient and scalable for large datasets
  • Parameter choices significantly impact results
  • Excellent for exploration, careful interpretation needed
1 / 10