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. |
Year | Venue | Field |
---|---|---|
2016 | arXiv: Other Computer Science | Discrete mathematics,Graph,Discretization,Vertex (geometry),Computer science,Quadratic equation,Probability distribution,Fluid dynamics,Triangle inequality,Scaling |
DocType | Volume | Citations |
Journal | abs/1603.06927 | 4 |
PageRank | References | Authors |
0.50 | 18 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Justin Solomon | 1 | 827 | 48.48 |
Raif M. Rustamov | 2 | 251 | 19.58 |
Leonidas J. Guibas | 3 | 13084 | 1262.73 |
Adrian Butscher | 4 | 423 | 13.41 |