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.
翻译:最佳运输(OT)是比较概率度量的流行和强大的工具。然而,OT有一些缺点:(一) 要求投入措施,其质量必须相同,(二) 计算复杂程度高,(三) 无限性,限制其应用于依赖内核的算法方法。为了解决问题(二)-(三),Le等人(2022)最近提议Sobolev运输,在图中测量总质量相同,利用图形结构而不是支持。在这项工作中,我们考虑可能具有不同总质量和在图形度空间上得到支持的措施。为了减轻OT的缺点(一)-(三),我们建议采用新颖和可伸缩的办法,扩大Sobolev运输范围,使之适用于可能具有不同总质量的不平衡的计算方法。我们表明,拟议的Sobolev运输(UST)接受一种封闭式的快速计算公式,而且也是否定的。此外,我们为UST得出几何结构,并在我们的AS和其他运输距离之间建立关系。我们进一步利用负面的确定性精确性方法,以设计精确性基准和测测算。</s>