# Bi-stochastically normalized graph Laplacian: convergence to manifold Laplacian and robustness to outlier noise

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 56 references that are in the map.
- First posted on arXiv 22 Jun 2022.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [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)
- [Analysis of p-Laplacian Regularization in Semi-Supervised Learning](https://mlsanity.com/paper/1707.06213/) (2017)
- [Spectral convergence of diffusion maps: improved error bounds and an alternative normalisation](https://mlsanity.com/paper/2006.02037/) (2020)
- [Lipschitz regularity of graph Laplacians on random data clouds](https://mlsanity.com/paper/2007.06679/) (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)
- [Spectral Convergence of the connection Laplacian from random samples](https://mlsanity.com/paper/1306.1587/) (2013)
- [Improved spectral convergence rates for graph Laplacians on epsilon-graphs and k-NN graphs](https://mlsanity.com/paper/1910.13476/) (2019)
- [Convergence of Graph Laplacian with kNN Self-tuned Kernels](https://mlsanity.com/paper/2011.01479/) (2020)
- [Unperturbed: spectral analysis beyond Davis-Kahan](https://mlsanity.com/paper/1706.06516/) (2017)
- [Doubly-Stochastic Normalization of the Gaussian Kernel is Robust to Heteroskedastic Noise](https://mlsanity.com/paper/2006.00402/) (2020)
- [Analysis and algorithms for ℓp-based semi-supervised learning on graphs](https://mlsanity.com/paper/1901.05031/) (2019)
- [Impact of signal-to-noise ratio and bandwidth on graph Laplacian spectrum from high-dimensional noisy point cloud](https://mlsanity.com/paper/2011.10725/) (2020)
- [Spectral Analysis Of Weighted Laplacians Arising In Data Clustering](https://mlsanity.com/paper/1909.06389/) (2019)
- [Landmark Diffusion Maps (L-dMaps): Accelerated manifold learning out-of-sample extension](https://mlsanity.com/paper/1706.09396/) (2017)
- [Spectral Convergence Rate of Graph Laplacian](https://mlsanity.com/paper/1510.08110/) (2015)

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

- [Robust Inference of Manifold Density and Geometry by Doubly Stochastic Scaling](https://mlsanity.com/paper/2209.08004/) (2022)
- [Entropic Optimal Transport Eigenmaps for Nonlinear Alignment and Joint Embedding of High-Dimensional Datasets](https://mlsanity.com/paper/2407.01718/) (2024)
- [Manifold learning in metric spaces](https://mlsanity.com/paper/2503.16187/) (2025)
- [Sinkhorn Normalization of Diffusion Kernels](https://mlsanity.com/paper/2507.06161/) (2025)
- [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)
- [Learning manifold diffusion semigroups from graph transition matrices](https://mlsanity.com/paper/2605.25383/) (2026)

## Abstract (arXiv)

Bi-stochastic normalization provides an alternative normalization of graph Laplacians in graph-based data analysis and can be computed efficiently by Sinkhorn-Knopp (SK) iterations. This paper proves the convergence of bi-stochastically normalized graph Laplacian to manifold (weighted-)Laplacian with rates, when n data points are i.i.d. sampled from a general d-dimensional manifold embedded in a possibly high-dimensional space. Under certain joint limit of n → ∞ and kernel bandwidth ε → 0, the point-wise convergence rate of the graph Laplacian operator (under 2-norm) is proved to be  O( n-1/(d/2+3)) at finite large n up to log factors, achieved at the scaling of ε ~ n-1/(d/2+3) . When the manifold data are corrupted by outlier noise, we theoretically prove the graph Laplacian point-wise consistency which matches the rate for clean manifold data plus an additional term proportional to the boundedness of the inner-products of the noise vectors among themselves and with data vectors. Motivated by our analysis, which suggests that not exact bi-stochastic normalization but an approximate one will achieve the same consistency rate, we propose an approximate and constrained matrix scaling problem that can be solved by SK iterations with early termination. Numerical experiments support our theoretical results and show the robustness of bi-stochastically normalized graph Laplacian to high-dimensional outlier noise.