Sobolev Transport: A Scalable Metric for Probability Measures with Graph Metrics

However, evaluating the OT incurs a high computational complexity in Optimal transport (OT) is a popular measure general (Peyré and Cuturi, 2019) which leads to several to compare probability distributions. However, proposals in the recent literature to address this drawback OT suffers a few drawbacks such as (i) of OT, e.g., approximate using entropic regularization a high complexity for computation, (ii) indefiniteness (Cuturi, 2013), or exploit geometric structure which limits its applicability to of supports (Rabin et al., 2011; Le et al., 2019; Le and kernel machines. In this work, we consider Nguyen, 2021). Among them, tree-Wasserstein (Evans probability measures supported on a graph and Matsen, 2012; Le et al., 2019) (TW) leverages the metric space and propose a novel Sobolev tree structure over supports to obtain a closed-form transport metric. We show that the Sobolev for fast computation. However, the requirement about transport metric yields a closed-form formula tree structure for supports may be restricted in applications.