# Computation of Optimal Transport on Discrete Metric Measure Spaces

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jul 2017.

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

- [Resistance Distance and Linearized Optimal Transport on Graphs](https://mlsanity.com/paper/2404.15261/) (2024)
- [Learning Discrete Diffusion of Graphs via Free-Energy Gradient Flows](https://mlsanity.com/paper/2604.11311/) (2026)
- [Static and Dynamic Approaches to Computing Barycenters of Probability Measures on Graphs](https://mlsanity.com/paper/2603.26940/) (2026)
- [Discrete Action Matching: Learning Stochastic Dynamics from Samples via State Graphs](https://mlsanity.com/paper/2610.05071/) (2026)

## Abstract (arXiv)

In this paper we investigate the numerical approximation of an analogue of the Wasserstein distance for optimal transport on graphs that is defined via a discrete modification of the Benamou--Brenier formula. This approach involves the logarithmic mean of measure densities on adjacent nodes of the graph. For this model a variational time discretization of the probability densities on graph nodes and the momenta on graph edges is proposed. A robust descent algorithm for the action functional is derived, which in particular uses a proximal splitting with an edgewise nonlinear projection on the convex subgraph of the logarithmic mean. Thereby, suitable chosen slack variables avoid a global coupling of probability densities on all graph nodes in the projection step. For the time discrete action functional Gamma--convergence to the time continuous action is established. Numerical results for a selection of test cases show qualitative and quantitative properties of the optimal transport on graphs. Finally, we use our algorithm to implement a JKO scheme for the gradient flow of the entropy in the discrete transportation distance, which is known to coincide with the underlying Markov semigroup, and test our results against a classical backward Euler discretization of this discrete heat flow.