Sobolev Transport: A Scalable Metric for Probability Measures with Graph Metrics
This work addresses scalability and kernel applicability issues in optimal transport for researchers and practitioners in machine learning, particularly in domains like document analysis and topological data analysis, though it is incremental as it builds on existing transport methods.
The authors tackled the computational complexity and indefiniteness of optimal transport for probability measures on graphs by proposing the Sobolev transport metric, which offers a closed-form formula for fast computation and is negative definite, enabling efficient kernel design and achieving competitive results in document classification and topological data analysis.
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.