# Randomized Optimal Transport on a Graph: framework and new distance measures

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jun 2018.

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

- [Relative Entropy-Regularized Optimal Transport on a Graph: a new algorithm and an experimental comparison](https://mlsanity.com/paper/2108.10004/) (2021)
- [Dissecting graph measure performance for node clustering in LFR parameter space](https://mlsanity.com/paper/2202.09827/) (2022)
- [Cost-augmented Schr"odinger bridges on graphs are exactly solvable: a Feynman-Kac tilt replaces learned control](https://mlsanity.com/paper/2610.02195/) (2026)

## Abstract (arXiv)

The recently developed bag-of-paths (BoP) framework consists in setting a Gibbs-Boltzmann distribution on all feasible paths of a graph. This probability distribution favors short paths over long ones, with a free parameter (the temperature T) controlling the entropic level of the distribution. This formalism enables the computation of new distances or dissimilarities, interpolating between the shortest-path and the resistance distance, which have been shown to perform well in clustering and classification tasks. In this work, the bag-of-paths formalism is extended by adding two independent equality constraints fixing starting and ending nodes distributions of paths (margins). When the temperature is low, this formalism is shown to be equivalent to a relaxation of the optimal transport problem on a network where paths carry a flow between two discrete distributions on nodes. The randomization is achieved by considering free energy minimization instead of traditional cost minimization. Algorithms computing the optimal free energy solution are developed for two types of paths: hitting (or absorbing) paths and non-hitting, regular, paths, and require the inversion of an n × n matrix with n being the number of nodes. Interestingly, for regular paths on an undirected graph, the resulting optimal policy interpolates between the deterministic optimal transport policy (T rightarrow 0+) and the solution to the corresponding electrical circuit (T rightarrow ∞). Two distance measures between nodes and a dissimilarity between groups of nodes, both integrating weights on nodes, are derived from this framework.