Entropic Optimal Transport in Random Graphs
Not on the map. Why?
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.
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
21 of 56 references.
References · 21
- 2019A Comprehensive Survey on Graph Neural Networkscited by 2,919
- 2013Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distancescited by 2,316
- 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
- 2016node2vec: Scalable Feature Learning for Networkscited by 1,918
- 2018Deep Graph Infomaxcited by 1,106
- 2018Computational Optimal Transportcited by 780
- 2017Community Detection and Stochastic Block Modelscited by 319
- 2016Stochastic Optimization for Large-scale Optimal Transportcited by 189
- 2017Graph Embedding Techniques, Applications, and Performance: A Surveycited by 188
- 2013Consistency of spectral clustering in stochastic block modelscited by 129
- 2019Statistical bounds for entropic optimal transport: sample complexity and the central limit theoremcited by 85
- 2020Convergence and Stability of Graph Convolutional Networks on Large Random Graphscited by 76
9 more
- 2018Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace--Beltrami operatorcited by 70
- 2020On Projection Robust Optimal Transport: Sample Complexity and Model Misspecificationcited by 34
- 2021On the Universality of Graph Neural Networks on Large Random Graphscited by 26
- 2014Continuum limit of total variation on point cloudscited by 24
- 2017The Geometry of Continuous Latent Space Models for Network Datacited by 11
- 2019Latent Distance Estimation for Random Geometric Graphscited by 11
- 2020SISTA: learning optimal transport costs under sparsity constraintscited by 7
- 2017Approximating geodesics via random pointscited by 6
- 2020Sparse and Smooth: improved guarantees for Spectral Clustering in the Dynamic Stochastic Block Modelcited by 6
Built on by
Citing papers per year: 2022: 1; 2023: 0; 2024: 0; 2025: 1; 2026: 1.
3 papers.