Entropic Optimal Transport in Random Graphs
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 $\epsilon$-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.
Code (1)
Similar Papers 제목 키워드 기반
Stability of Entropic Wasserstein Barycenters and application to random geometric graphs
As interest in graph data has grown in recent years, the computation of various geometric tools has become essential. In some area such as mesh processing, they often rely on the computation of geodesics and shortest pat…
An improved central limit theorem and fast convergence rates for entropic transportation costs
We prove a central limit theorem for the entropic transportation cost between subgaussian probability measures, centered at the population cost. This is the first result which allows for asymptotically valid inference fo…
validInformation-Theoretic Equivalence of Entropic Multi-Marginal Optimal Transport: A Theory for Multi-Agent Communication
In this paper, we propose our information-theoretic equivalence of entropic multi-marginal optimal transport (MOT). This equivalence can be easily reduced to the case of entropic optimal transport (OT). Because OT is wid…
Entropic estimation of optimal transport maps
We develop a computationally tractable method for estimating the optimal map between two distributions over $\mathbb{R}^d$ with rigorous finite-sample guarantees. Leveraging an entropic version of Brenier's theorem, we s…
Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport
We derive nearly tight and non-asymptotic convergence bounds for solutions of entropic semi-discrete optimal transport. These bounds quantify the stability of the dual solutions of the regularized problem (sometimes call…