Entropic Optimal Transport in Random Graphs
This addresses a fundamental problem in graph analysis for researchers working with latent space models, offering theoretical guarantees for distance estimation, though it appears incremental as it builds on existing entropic OT and graph theory.
The paper tackles the problem of estimating distances between groups of nodes in latent space random graphs using only graph structure, showing that entropic-regularized Optimal Transport distances can be consistently estimated. It provides a stability result for entropic OT with respect to cost matrix perturbations and applies it to examples like graphons and ε-graphs on manifolds, with new concentration results for estimators.
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.