Continuous-Flow Graph Transportation Distances

Abstract

Optimal transportation distances are valuable for comparing and analyzing probability distributions, but larger-scale computational techniques for the theoretically favorable quadratic case are limited to smooth domains or regularized approximations. Motivated by fluid flow-based transportation on ${\mathbb{R}}^n$, however, this paper introduces an alternative definition of optimal transportation between distributions over graph vertices. This new distance still satisfies the triangle inequality but has better scaling and a connection to continuous theories of transportation. It is constructed by adapting a Riemannian structure over probability distributions to the graph case, providing transportation distances as shortest-paths in probability space. After defining and analyzing theoretical properties of our new distance, we provide a time discretization as well as experiments verifying its effectiveness.

References in corpus (4)

• Efficient Estimation of Word Representations in Vector Space
• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Optimal Transport with Proximal Splitting
• An Explicit Formulation of the Earth Movers Distance with Continuous Road Map Distances

Cited by in corpus (6)

• Topological metric detects hidden order in disordered media
• Stochastic control liaisons: Richard Sinkhorn meets Gaspard Monge on a Schroedinger bridge
• Scalable Global Alignment Graph Kernel Using Random Features: From Node Embedding to Graph Embedding
• The Atlas for the Aspiring Network Scientist
• Optimal perturbations for nonlinear systems using graph-based optimal transport
• Solving graph compression via optimal transport