# Robust Inference of Manifold Density and Geometry by Doubly Stochastic Scaling

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 88 references that are in the map.
- First posted on arXiv 16 Sep 2022.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace--Beltrami operator](https://mlsanity.com/paper/1801.10108/) (2018)
- [Spectral convergence of diffusion maps: improved error bounds and an alternative normalisation](https://mlsanity.com/paper/2006.02037/) (2020)
- [Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation](https://mlsanity.com/paper/2101.09875/) (2021)
- [Manifold learning with bi-stochastic kernels](https://mlsanity.com/paper/1711.06711/) (2017)
- [Improved spectral convergence rates for graph Laplacians on epsilon-graphs and k-NN graphs](https://mlsanity.com/paper/1910.13476/) (2019)
- [Doubly-Stochastic Normalization of the Gaussian Kernel is Robust to Heteroskedastic Noise](https://mlsanity.com/paper/2006.00402/) (2020)
- [Doubly Stochastic Subspace Clustering](https://mlsanity.com/paper/2011.14859/) (2020)
- [Much Faster Algorithms for Matrix Scaling](https://mlsanity.com/paper/1704.02315/) (2017)
- [Geometric structure of graph Laplacian embeddings](https://mlsanity.com/paper/1901.10651/) (2019)
- [Role of normalization in spectral clustering for stochastic blockmodels](https://mlsanity.com/paper/1310.1495/) (2013)
- [The steerable graph Laplacian and its application to filtering image data-sets](https://mlsanity.com/paper/1802.01894/) (2018)
- [Bi-stochastically normalized graph Laplacian: convergence to manifold Laplacian and robustness to outlier noise](https://mlsanity.com/paper/2206.11386/) (2022)
- [Strong Uniform Consistency with Rates for Kernel Density Estimators with General Kernels on Manifolds](https://mlsanity.com/paper/2007.06408/) (2020)
- [A common variable minimax theorem for graphs](https://mlsanity.com/paper/2107.14747/) (2021)

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

- [A Convergence Rate for Manifold Neural Networks](https://mlsanity.com/paper/2212.12606/) (2022)
- [Entropic Optimal Transport Eigenmaps for Nonlinear Alignment and Joint Embedding of High-Dimensional Datasets](https://mlsanity.com/paper/2407.01718/) (2024)
- [t-SNE Exaggerates Clusters, Provably](https://mlsanity.com/paper/2510.07746/) (2025)
- [Manifold Learning with Sparse Regularised Optimal Transport](https://mlsanity.com/paper/2307.09816/) (2023)
- [Local EGOP for Continuous Index Learning](https://mlsanity.com/paper/2601.07061/) (2026)
- [Euclidean Distance Deflation Under High-Dimensional Heteroskedastic Noise](https://mlsanity.com/paper/2507.18520/) (2025)
- [Robust Tangent Space Estimation via Laplacian Eigenvector Gradient Orthogonalization](https://mlsanity.com/paper/2510.02308/) (2025)

## Abstract (arXiv)

The Gaussian kernel and its traditional normalizations (e.g., row-stochastic) are popular approaches for assessing similarities between data points. Yet, they can be inaccurate under high-dimensional noise, especially if the noise magnitude varies considerably across the data, e.g., under heteroskedasticity or outliers. In this work, we investigate a more robust alternative -- the doubly stochastic normalization of the Gaussian kernel. We consider a setting where points are sampled from an unknown density on a low-dimensional manifold embedded in high-dimensional space and corrupted by possibly strong, non-identically distributed, sub-Gaussian noise. We establish that the doubly stochastic affinity matrix and its scaling factors concentrate around certain population forms, and provide corresponding finite-sample probabilistic error bounds. We then utilize these results to develop several tools for robust inference under general high-dimensional noise. First, we derive a robust density estimator that reliably infers the underlying sampling density and can substantially outperform the standard kernel density estimator under heteroskedasticity and outliers. Second, we obtain estimators for the pointwise noise magnitudes, the pointwise signal magnitudes, and the pairwise Euclidean distances between clean data points. Lastly, we derive robust graph Laplacian normalizations that accurately approximate various manifold Laplacians, including the Laplace Beltrami operator, improving over traditional normalizations in noisy settings. We exemplify our results in simulations and on real single-cell RNA-sequencing data. For the latter, we show that in contrast to traditional methods, our approach is robust to variability in technical noise levels across cell types.