Optimal Transport on Graphs and Stochastically Evolving Trees

Abstract

We give an effective algorithm for determining the transportation distance between two given probability density functions defined on the vertices of a graph $G=(V,E)$ by analyzing an associated polytope. The vertices of the polytope correspond to feasible flows on spanning trees in $G$, and the $1$-skeleton of the polytope is a projection of the spanning tree state graph associated with the Glauber dynamics on $G$. The optimal value of this transportation problem, known as the $1$-Wasserstein distance, can be computed by tracing the transportation cost along the vertices of this polytope. We show that a local minimum of the transportation cost is also a global minimum, and this leads to a steepest descent algorithm for solving the transportation problem. If the probability density functions take discrete values in $\delta \mathbb{Z}$ for some $\delta>0$, then the optimal transport cost can be reached in at most $\frac{|V|-1}{\delta}$ steps. As an application, we give an efficient algorithm for computing the Ollivier--Ricci curvature of a graph.