# High-dimensional Semi-supervised Classification via the Fermat Distance

arXiv: https://arxiv.org/abs/2604.23573 · HTML: https://mlsanity.com/paper/2604.23573/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 60 references that are in the map.
- First posted on arXiv 26 Apr 2026.

## Builds on (most cited first, 26 of 26)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [FixMatch: Simplifying Semi-Supervised Learning with Consistency and Confidence](https://mlsanity.com/paper/2001.07685/) (2020)
- [Depth Anything: Unleashing the Power of Large-Scale Unlabeled Data](https://mlsanity.com/paper/2401.10891/) (2024)
- [Estimating the intrinsic dimension of datasets by a minimal neighborhood information](https://mlsanity.com/paper/1803.06992/) (2018)
- [Prediction-Powered Inference](https://mlsanity.com/paper/2301.09633/) (2023)
- [Cross-Prediction-Powered Inference](https://mlsanity.com/paper/2309.16598/) (2023)
- [On the Intrinsic Dimensionality of Image Representations](https://mlsanity.com/paper/1803.09672/) (2018)
- [Poisson Learning: Graph Based Semi-Supervised Learning At Very Low Label Rates](https://mlsanity.com/paper/2006.11184/) (2020)
- [Semi-supervised Inference: General Theory and Estimation of Means](https://mlsanity.com/paper/1606.07268/) (2016)
- [Statistical exploration of the Manifold Hypothesis](https://mlsanity.com/paper/2208.11665/) (2022)
- [Path-Based Spectral Clustering: Guarantees, Robustness to Outliers, and Fast Algorithms](https://mlsanity.com/paper/1712.06206/) (2017)
- [Balancing Geometry and Density: Path Distances on High-Dimensional Data](https://mlsanity.com/paper/2012.09385/) (2020)
- [Semi-supervised Inference for Explained Variance in High-dimensional Linear Regression and Its Applications](https://mlsanity.com/paper/1806.06179/) (2018)
- [Fermat Distances: Metric Approximation, Spectral Convergence, and Clustering Algorithms](https://mlsanity.com/paper/2307.05750/) (2023)
- [Power Weighted Shortest Paths for Clustering Euclidean Data](https://mlsanity.com/paper/1905.13345/) (2019)
- [Consistent Semi-Supervised Graph Regularization for High Dimensional Data](https://mlsanity.com/paper/2006.07575/) (2020)
- [Optimal and Safe Estimation for High-Dimensional Semi-Supervised Learning](https://mlsanity.com/paper/2011.14185/) (2020)
- [Semi-supervised Semantic Segmentation for Remote Sensing Images via Multi-scale Uncertainty Consistency and Cross-Teacher-Student Attention](https://mlsanity.com/paper/2501.10736/) (2025)
- [A study of the classification of low-dimensional data with supervised manifold learning](https://mlsanity.com/paper/1507.05880/) (2015)
- [Intrinsic persistent homology via density-based metric learning](https://mlsanity.com/paper/2012.07621/) (2020)
- [Hamilton-Jacobi equations on graphs with applications to semi-supervised learning and data depth](https://mlsanity.com/paper/2202.08789/) (2022)
- [Contrastive Pessimistic Likelihood Estimation for Semi-Supervised Classification](https://mlsanity.com/paper/1503.00269/) (2015)
- [Robust Transfer Learning with Unreliable Source Data](https://mlsanity.com/paper/2310.04606/) (2023)
- [Semi-Supervised U-statistics](https://mlsanity.com/paper/2402.18921/) (2024)
- [HiLoTs: High-Low Temporal Sensitive Representation Learning for Semi-Supervised LiDAR Segmentation in Autonomous Driving](https://mlsanity.com/paper/2503.17752/) (2025)
- [Sharp-SSL: Selective high-dimensional axis-aligned random projections for semi-supervised learning](https://mlsanity.com/paper/2304.09154/) (2023)

## Built on by (most cited first, 1 of 1)

- [Fermat Active Laplace Learning for Semi-Supervised Hyperspectral Image Classification](https://mlsanity.com/paper/2608.02483/) (2026)

## Abstract (arXiv)

Semi-supervised classification, where unlabeled data are massive but labeled data are limited, often arises in machine learning applications. We address this challenge under high-dimensional data by leveraging the manifold and cluster assumptions. Based on the Fermat distance, a density-sensitive metric that naturally encodes the cluster assumption, we propose the weighted k-nearest neighbors (NN) classifier and multidimensional scaling (MDS)-induced classifiers. The use of MDS with a large target dimension allows the effective application of linear classifiers to complex manifold data. Theoretically, we derive a sharp lower bound for the expected excess risk within clusters and prove that the weighted k-NN classifier utilizing the true Fermat distance is minimax optimal. Furthermore, we explicitly quantify the utility of unlabeled data by showing that the error arising from estimating the Fermat distance decays exponentially with the pooled sample size. Such a rate is much faster than the related rates in the literature. Extensive experiments on synthetic and real datasets demonstrate competitive or superior performance of our approaches compared to state-of-the-art graph-based semi-supervised classifiers.