# Entropic Optimal Transport in Random Graphs

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 56 references that are in the map.
- First posted on arXiv 11 Jan 2022.

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

- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Graph Embedding Techniques, Applications, and Performance: A Survey](https://mlsanity.com/paper/1705.02801/) (2017)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem](https://mlsanity.com/paper/1905.11882/) (2019)
- [Convergence and Stability of Graph Convolutional Networks on Large Random Graphs](https://mlsanity.com/paper/2006.01868/) (2020)
- [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)
- [On Projection Robust Optimal Transport: Sample Complexity and Model Misspecification](https://mlsanity.com/paper/2006.12301/) (2020)
- [On the Universality of Graph Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2105.13099/) (2021)
- [Continuum limit of total variation on point clouds](https://mlsanity.com/paper/1403.6355/) (2014)
- [The Geometry of Continuous Latent Space Models for Network Data](https://mlsanity.com/paper/1712.08641/) (2017)
- [Latent Distance Estimation for Random Geometric Graphs](https://mlsanity.com/paper/1909.06841/) (2019)
- [SISTA: learning optimal transport costs under sparsity constraints](https://mlsanity.com/paper/2009.08564/) (2020)
- [Approximating geodesics via random points](https://mlsanity.com/paper/1711.06952/) (2017)
- [Sparse and Smooth: improved guarantees for Spectral Clustering in the Dynamic Stochastic Block Model](https://mlsanity.com/paper/2002.02892/) (2020)

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

- [Stability of Entropic Wasserstein Barycenters and application to random geometric graphs](https://mlsanity.com/paper/2210.10535/) (2022)
- [Optimal Transport with Heterogeneously Missing Data](https://mlsanity.com/paper/2505.17291/) (2025)
- [Optimal Transport under Group Fairness Constraints](https://mlsanity.com/paper/2601.07144/) (2026)

## Abstract (arXiv)

In graph analysis, a classic task consists in computing similarity measures between (groups of) nodes. In latent space random graphs, nodes are associated to unknown latent variables. One may then seek to compute distances directly in the latent space, using only the graph structure. In this paper, we show that it is possible to consistently estimate entropic-regularized Optimal Transport (OT) distances between groups of nodes in the latent space. We provide a general stability result for entropic OT with respect to perturbations of the cost matrix. We then apply it to several examples of random graphs, such as graphons or ε-graphs on manifolds. Along the way, we prove new concentration results for the so-called Universal Singular Value Thresholding estimator, and for the estimation of geodesic distances on a manifold.