# Relative Entropy-Regularized Optimal Transport on a Graph: a new algorithm and an experimental comparison

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 80 references that are in the map.
- First posted on arXiv 23 Aug 2021.

## Builds on (most cited first, 10 of 10)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Robust transport over networks](https://mlsanity.com/paper/1603.08129/) (2016)
- [A bag-of-paths framework for network data analysis](https://mlsanity.com/paper/1302.6766/) (2013)
- [Randomized Optimal Transport on a Graph: framework and new distance measures](https://mlsanity.com/paper/1806.03232/) (2018)
- [Two betweenness centrality measures based on Randomized Shortest Paths](https://mlsanity.com/paper/1509.03147/) (2015)
- [Covariance and Correlation Kernels on a Graph in the Generalized Bag-of-Paths Formalism](https://mlsanity.com/paper/1902.03002/) (2019)
- [Randomized Shortest Paths with Net Flows and Capacity Constraints](https://mlsanity.com/paper/1910.01849/) (2019)
- [Sparse Randomized Shortest Paths Routing with Tsallis Divergence Regularization](https://mlsanity.com/paper/2007.00419/) (2020)
- [A Constrained Randomized Shortest-Paths Framework for Optimal Exploration](https://mlsanity.com/paper/1807.04551/) (2018)

## Abstract (arXiv)

Following [21, 23], the present work investigates a new relative entropy-regularized algorithm for solving the optimal transport on a graph problem within the randomized shortest paths formalism. More precisely, a unit flow is injected into a set of input nodes and collected from a set of output nodes while minimizing the expected transportation cost together with a paths relative entropy regularization term, providing a randomized routing policy. The main advantage of this new formulation is the fact that it can easily accommodate edge flow capacity constraints which commonly occur in real-world problems. The resulting optimal routing policy, i.e., the probability distribution of following an edge in each node, is Markovian and is computed by constraining the input and output flows to the prescribed marginal probabilities thanks to a variant of the algorithm developed in [8]. In addition, experimental comparisons with other recently developed techniques show that the distance measure between nodes derived from the introduced model provides competitive results on semi-supervised classification tasks.