  Optimal transport (OT) is a popular measure to compare probability
distributions. However, OT suffers a few drawbacks such as (i) a high
complexity for computation, (ii) indefiniteness which limits its applicability
to kernel machines. In this work, we consider probability measures supported on
a graph metric space and propose a novel Sobolev transport metric. We show that
the Sobolev transport metric yields a closed-form formula for fast computation
and it is negative definite. We show that the space of probability measures
endowed with this transport distance is isometric to a bounded convex set in a
Euclidean space with a weighted $\ell_p$ distance. We further exploit the
negative definiteness of the Sobolev transport to design positive-definite
kernels, and evaluate their performances against other baselines in document
classification with word embeddings and in topological data analysis.
