Entropic Optimal Transport on Random Graphs

DOI10.1137/22M1518281MaRDI QIDQ6148350zbMATH OpenOpenAlexFDO

Authors Nicolas Keriven

Publication date 11 January 2024

Published in SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2201.03949

zbMATH Keywords

optimal transportrandom graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: 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.

Cites work

• scientific article; zbMATH DE number 1502618 (Why is no real title available?)
• scientific article; zbMATH DE number 878897 (Why is no real title available?)
• scientific article; zbMATH DE number 5055767 (Why is no real title available?)
• <scp>SISTA</scp>: Learning Optimal Transport Costs under Sparsity Constraints
• A survey of statistical network models
• Approximating geodesics via random points
• Barycenters in the Wasserstein space
• Community detection and stochastic block models: recent developments
• Computational optimal transport. With applications to data sciences
• Consistency of spectral clustering
• Consistency of spectral clustering in stochastic block models
• Continuum limit of total variation on point clouds
• Convolutional Wasserstein distances: efficient optimal transportation on geometric domains
• Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator
• Expected distance based on random walks
• Geodesic methods in computer vision and graphics
• Graph Representation Learning
• Gromov-Wasserstein distances and the metric approach to object matching
• Hitting and commute times in large random neighborhood graphs
• Large networks and graph limits
• Latent Space Approaches to Social Network Analysis
• Matrix estimation by universal singular value thresholding
• Network science. With Márton Pósfai
• On learning with integral operators
• On the estimation of latent distances using graph distances
• Optimal Transport
• Optimal transportation networks. Models and theory
• Quantitative stability of regularized optimal transport and convergence of Sinkhorn's algorithm
• Shortest path through random points
• Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model
• Stability results on the smoothness of optimal transport maps with general costs
• The Gromov-Wasserstein distance: a brief overview
• The geometry of continuous latent space models for network data
• Towards a theoretical foundation for Laplacian-based manifold methods
• Universally consistent vertex classification for latent positions graphs

Cited in

(1)

• Stability and sample complexity of divergence regularized optimal transport

This page was built for publication: Entropic Optimal Transport on Random Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6148350)