Generalized Sobolev Transport for Probability Measures on a Graph
Tam Le Truyen Nguyen Kenji Fukumizu
We study the optimal transport (OT) problem for measures supported on a graph
metric space. Recently, Le et al. (2022) leverage the graph structure and
propose a variant of OT, namely Sobolev transport (ST), which yields a
closed-form expression for a fast computation. However, ST is essentially
coupled with the $L^p$ geometric structure within its definition which makes it
nontrivial to utilize ST for other prior structures. In contrast, the classic
OT has the flexibility to adapt to various geometric structures by modifying
the underlying cost function. An important instance is the Orlicz-Wasserstein
(OW) which moves beyond the $L^p$ structure by leveraging the \emph{Orlicz
geometric structure}. Comparing to the usage of standard $p$-order Wasserstein,
OW remarkably helps to advance certain machine learning approaches.
Nevertheless, OW brings up a new challenge on its computation due to its
two-level optimization formulation. In this work, we leverage a specific class
of convex functions for Orlicz structure to propose the generalized Sobolev
transport (GST). GST encompasses the ST as its special case, and can be
utilized for prior structures beyond the $L^p$ geometry. In connection with the
OW, we show that one only needs to simply solve a univariate optimization
problem to compute the GST, unlike the complex two-level optimization problem
in OW. We empirically illustrate that GST is several-order faster than the OW.
Moreover, we provide preliminary evidences on the advantages of GST for
document classification and for several tasks in topological data analysis.