Research map / Graph learning / Graph algorithms and clustering
Dimension Reduction with Locally Adjusted Graphs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes LocalMAP, a PaCMAP-based dimension reduction method that dynamically reweights nearest-neighbor edges and resamples local further-pair edges during optimization to produce crisper cluster separation.
Problem
Dimension reduction graphs built from high-dimensional distances are unreliable (false positive neighbor edges), and fixed further-pair negative sampling becomes insufficient as dataset size grows, causing overlapping clusters in DR embeddings of large high-dimensional data such as transcriptomics.
Approach
Adjust the graph during optimization: reweight NN attractive forces by low-dimensional distance (down-weighting likely false positives) and resample further-pair repulsive edges locally within a proximal cluster-distance threshold, applied in the final PaCMAP optimization phase.
Key results
- LocalMAP achieves the highest silhouette score on MNIST (0.58), USPS (0.60), and Kang (0.60) among default-parameter methods in the reported table.
- With tuned hyperparameters, Optimized UMAP and Optimized LargeVis score higher on COIL20 (0.63 and 0.65 vs 0.56 for LocalMAP), which the authors attribute to intra-cluster compaction rather than better separation.
- LocalMAP is reported to consistently separate all 10 MNIST clusters across random initializations, while no other method does so in any run.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LocalMAP instead of PaCMAP | dimension reduction · MNIST | silhouette score: 0.54$\pm$0.01 -> 0.58$\pm$0.00 | Helped |
| Use LocalMAP instead of UMAP | dimension reduction · FMNIST | silhouette score: 0.19$\pm$0.00 -> 0.19$\pm$0.00 | No clear effect |
| Use LocalMAP instead of PaCMAP | dimension reduction · USPS | silhouette score: 0.56$\pm$0.00 -> 0.60$\pm$0.00 | Helped |
| Use LocalMAP instead of UMAP | dimension reduction · COIL20 | silhouette score: 0.58$\pm$0.01 -> 0.56$\pm$0.01 | Hurt |
| Use LocalMAP instead of PaCMAP | dimension reduction · 20NG | silhouette score: -0.11$\pm$0.01 -> -0.10$\pm$0.00 | Helped |
| Use LocalMAP instead of TriMAP | dimension reduction · Kang | silhouette score: 0.55$\pm$0.00 -> 0.60$\pm$0.00 | Helped |
| Use LocalMAP instead of TriMAP | dimension reduction · Seurat | silhouette score: 0.32$\pm$0.00 -> 0.32$\pm$0.00 | No clear effect |
| Use LocalMAP instead of PaCMAP | dimension reduction · Human Cortex | silhouette score: 0.13$\pm$0.01 -> 0.14$\pm$0.00 | Helped |
| Use LocalMAP instead of Neg-t-SNE | dimension reduction · CBMC | silhouette score: 0.24$\pm$0.00 -> 0.22$\pm$0.00 | No clear effect |
| Add local FP resampling (ablation) | LocalMAP · MNIST | cluster separation | Helped |
| Add adjusted NN edge weights (ablation) | LocalMAP · MNIST | cluster separation | Helped |
Surprising findings
- Tuned LargeVis and UMAP beat LocalMAP on COIL20 silhouette score, though the authors argue these improvements come from tighter clusters rather than added separation.
Limitations
- Posthoc classification is acknowledged as an imperfect metric, and silhouette score is the main evaluation measure.
- Runtime is somewhat higher than some baselines, such as PaCMAP and UMAP, due to dynamic resampling.
- The adjusted-graph hyperparameter d_adj is set from approximate observations (~10) rather than derived in general.
Experimental setup
Datasets: MNIST FMNIST USPS COIL20 20NG Kang Seurat Human Cortex CBMC
Benchmarks: MNIST FMNIST USPS COIL20 20NG Kang Seurat Human Cortex CBMC
Metrics: silhouette score SVM posthoc classification accuracy running time
Baselines: PCA t-SNE UMAP PaCMAP LargeVis TriMAP PHATE h-NNE Neg-t-SNE NCVis InfoNC-t-SNE
Builds on: PaCMAP t-SNE UMAP
Closest papers by meaning
- Hierarchical Nearest Neighbor Graph Embedding for Efficient Dimensionality Reduction (CVPR 2022 · similarity 0.87)
- SpaceMAP: Visualizing High-Dimensional Data by Space Expansion (ICML 2022 · similarity 0.85)
- Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering (ICML 2021 · similarity 0.84)
- Subquadratic High-Dimensional Hierarchical Clustering (NeurIPS 2019 · similarity 0.84)
- Contrastive dimension reduction: when and how? (NeurIPS 2024 · similarity 0.82)
- Enhanced Denesity Peak Clustering for High-Dimensional Data (AAAI 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.