  Optimal transport (OT) is a popular and powerful tool for comparing
probability measures. However, OT suffers a few drawbacks: (i) input measures
required to have the same mass, (ii) a high computational complexity, and (iii)
indefiniteness which limits its applications on kernel-dependent algorithmic
approaches. To tackle issues (ii)--(iii), Le et al. (2022) recently proposed
Sobolev transport for measures on a graph having the same total mass by
leveraging the graph structure over supports. In this work, we consider
measures that may have different total mass and are supported on a graph metric
space. To alleviate the disadvantages (i)--(iii) of OT, we propose a novel and
scalable approach to extend Sobolev transport for this unbalanced setting where
measures may have different total mass. We show that the proposed unbalanced
Sobolev transport (UST) admits a closed-form formula for fast computation, and
it is also negative definite. Additionally, we derive geometric structures for
the UST and establish relations between our UST and other transport distances.
We further exploit the negative definiteness to design positive definite
kernels and evaluate them on various simulations to illustrate their fast
computation and comparable performances against other transport baselines for
unbalanced measures on a graph.
