Entropy Partial Transport with Tree Metrics: Theory and Practice

Tam Le* Truyen Nguyen*

RIKEN AIP The University of Akron

###### Abstract

Optimal transport (OT) theory provides powerful tools to compare probability
measures. However, OT is limited to nonnegative measures having the same mass,
and suffers serious drawbacks about its computation and statistics. This leads
to several proposals of regularized variants of OT in the recent literature.
In this work, we consider an entropy partial transport (EPT) problem for
nonnegative measures on a tree having different masses. The EPT is shown to be
equivalent to a standard complete OT problem on a one-node extended tree. We
derive its dual formulation, then leverage this to propose a novel
regularization for EPT which admits fast computation and negative
definiteness. To our knowledge, the proposed regularized EPT is the first
approach that yields a closed-form solution among available variants of
unbalanced OT. For practical applications without priori knowledge about the
tree structure for measures, we propose tree-sliced variants of the
regularized EPT, computed by averaging the regularized EPT between these
measures using random tree metrics, built adaptively from support data points.
Exploiting the negative definiteness of our regularized EPT, we introduce a
positive definite kernel, and evaluate it against other baselines on benchmark
tasks such as document classification with word embedding and topological data
analysis. In addition, we empirically demonstrate that our regularization also
provides effective approximations.

##  1 Introduction

Optimal transport (OT) theory offers powerful tools to compare probability
measures [67]. OT has been applied for various tasks in machine learning [9,
14, 51, 54], statistics [49, 68] and computer graphics [39, 63]. However, OT
requires input measures having the same mass which may limit its applications
in practice since one often needs to deal with measures of unequal masses. For
instance, in natural language processing, we can view a document as a measure
where each word is regarded as a point in the support with a unit mass. Thus,
documents with different lengths lead to their associated measures having
different masses.

To tackle the transport problem for measures having different masses,
Caffarelli and McCann [10] proposed the partial optimal transport (POT) where
one only transports a fixed amount of mass from a measure into another. Later,
Figalli [20] extended the theory of POT, notably, about the uniqueness of
solutions. A different approach is to optimize the sum of a transport
functional and two convex entropy functionals which quantify the deviation of
the marginals of the transport plan from the input measures [46], i.e., the
optimal entropy transport (OET) problem. This formulation recovers many
different previous works. For examples, when the entropy is equal to the total
variation distance or the $\ell^{2}$ distance, the OET is respectively
equivalent to the generalized Wasserstein distance [56, 57] or the unbalanced
mass transport [5]. It is worth noting that the generalized Wasserstein
distance shares the same spirit as the Kantorovich-Rubinstein discrepancy [25,
26, 45]. Another variant is the unnormalized optimal transport [23] which
mixes Wasserstein distance and the $\ell^{p}$ distance. There are several
applications of the transport problem for measures having different masses
such as in machine learning [22, 31], deep learning [69], topological data
analysis [37], computational imaging [44], and computational biology [61].

One important case for the OET problem is when the entropy is equal to the
Kullback-Leibler (KL) divergence and a particular cost function is used, then
OET is equivalent to the Kantorovich-Hellinger distance (i.e., Wasserstein-
Fisher-Rao distance) [12, 46]. In addition, one can apply the Sinkhorn-based
algorithm to efficiently solve OET problem when the entropy is equal to KL
divergence, i.e., Sinkhorn-based approach for unbalanced optimal transport
(Sinkhorn-UOT) [12, 22]. In [55], Pham et al. showed that the complexity of
Sinkhorn-based algorithm for Sinkhorn-UOT is quadratic which is similar to the
case of entropic regularized OT [15] for probability measures. However, for
large-scale applications where the supports of measures contain a large number
of points, the computation of Sinkhorn-UOT becomes prohibited. Following the
sliced-Wasserstein (SW) distance [8, 58] which projects supports into a one-
dimensional space and employs the closed-form solution of the univariate
optimal transport (1d-OT), Bonneel and Coeurjolly [7] propose the sliced
partial optimal transport (SPOT) for nonnegative measures having different
masses. Unlike the standard 1d-OT, one does not have a closed-form solution
for measures of unequal masses that are supported in a one-dimensional space.
With an assumption of a unit mass on each support, Bonneel and Coeurjolly [7]
derived an efficient algorithm to solve the SPOT problem in quadratic
complexity for the worst case. Especially, in practice, their proposed
algorithm is nearly linear for computation. However, as in SW, the SPOT uses
one-dimensional projection for supports which limits its capacity to capture a
structure of a distribution, especially in high-dimensional settings [43, 47].

In this work, we aim to develop an efficient and scalable approach for the
transport problem when input measures have different masses. Inspired by the
tree-sliced Wasserstein (TSW) distance [43] which has fast closed-form
computation and remedies the curse of dimensionality for SW, we propose to
consider the entropy partial transport (EPT) problem with tree metrics. As a
high level, our main contribution is three-fold as follows:

  * •

We establish a relationship between the EPT problem with mass constraint and a
formulation with Lagrangian multiplier. Then, we employ it to transform the
EPT problem to the standard complete OT problem on a suitable one-node
extended tree.

  * •

We derive a dual formulation for our EPT problem. We then leverage it to
propose a novel regularization which admits a closed-form formula and negative
definiteness. Consequently, we introduce positive definite kernels for our
regularized EPT. We also derive tree-sliced variants of the regularized EPT
for applications without priori knowledge about tree structure for measures.

  * •

We empirically show that (i) our regularization provides both efficient
approximations and fast computations, and (ii) the performances of the
proposed kernels for our regularized EPT compare favorably with other
baselines in applications.

##  2 Preliminaries

Let ${\mathcal{T}}=(V,E)$ be a tree rooting at node $r$ and with nonnegative
edge lengths $\\{w_{e}\\}_{e\in E}$, where $V$ is the collection of nodes and
$E$ is the collection of edges. For convenience, we use ${\mathcal{T}}$ to
denote the set of all nodes together with all points on its edges. We then
recall the definition of tree metric as follow:

######  Definition 2.1 (Tree metric [62](§7, p.145–182)).

A metric $\texttt{d}:\Omega\times\Omega\rightarrow[0,\infty)$ is called a tree
metric on $\Omega$ if there exists tree $\mathcal{T}$ such that
$\Omega\subseteq\mathcal{T}$ and for $x,y\in\Omega$, $\texttt{d}(x,y)$ equals
to the length of the (unique) path between $x$ and $y$.

Assume that $V$ is a subset of a vector space, and let
$d_{\mathcal{T}}(\cdot,\cdot)$ be the tree metric on ${\mathcal{T}}$.
Hereafter, the unique shortest path in ${\mathcal{T}}$ connecting $x$ and $y$
is denoted by $[x,y]$. Let $\omega$ be the unique Borel measure (i.e., the
length measure) on ${\mathcal{T}}$ satisfying
$\omega([x,y])=d_{\mathcal{T}}(x,y)$ for all $x,y\in{\mathcal{T}}$. Given
$x\in{\mathcal{T}}$, the set $\Lambda(x)$ stands for the subtree below $x$.
Precisely,

$\Lambda(x):=\big{\\{}y\in{\mathcal{T}}:\,x\in[r,y]\big{\\}}.\vspace{-6pt}$
(1)

We shall use notation ${\mathcal{M}}({\mathcal{T}})$ to represent the set of
all nonnegative Borel measures on ${\mathcal{T}}$ with a finite mass. Also let
$C({\mathcal{T}})$ be the set of all continuous functions on ${\mathcal{T}}$,
while $L^{\infty}({\mathcal{T}})$ be the collection of all Borel measurable
functions on ${\mathcal{T}}$ that are bounded $\omega$-a.e. Then,
$L^{\infty}({\mathcal{T}})$ is a Banach space under the norm

$\|f\|_{L^{\infty}({\mathcal{T}})}:=\inf\\{a\in{\mathbb{R}}:\,|f(x)|\leq
a\mbox{ for $\omega$-a.e. }x\in{\mathcal{T}}\\}.$

##  3 Entropy Partial Transport (EPT) with Tree Metrics

Let $b\geq 0$ be a constant,
$c:{\mathcal{T}}\times{\mathcal{T}}\to{\mathbb{R}}$ be a continuous cost with
$c(x,x)=0$, $F_{1},\,F_{2}:[0,\infty)\to(0,\infty)$ be entropy functions which
are convex and lower semicontinuous, and let
$w_{1},w_{2}:{\mathcal{T}}\to[0,\infty)$ be two nonnegative weights. For
$\mu,\nu\in{\mathcal{M}}({\mathcal{T}})$, consider the region

$\Pi_{\leq}(\mu,\nu):=\Big{\\{}\gamma\in{\mathcal{M}}({\mathcal{T}}\times{\mathcal{T}}):\,\gamma_{1}\leq\mu,\,\gamma_{2}\leq\nu\Big{\\}}\vspace{-6pt}$

with $\gamma_{i}$ ($i=1,2$) denoting the $i$th marginal of the measure
$\gamma$. For $\gamma\in\Pi_{\leq}(\mu,\nu)$, the Radon-Nikodym derivatives of
$\gamma_{1}$ with respect to $\mu$ and of $\gamma_{2}$ with respect to $\nu$
exist due to $\gamma_{1}\leq\mu$ and $\gamma_{2}\leq\nu$. From now on, we let
$f_{1}$ and $f_{2}$ respectively denote these Radon-Nikodym derivatives, i.e.,
$\gamma_{1}=f_{1}\mu$ and $\gamma_{2}=f_{2}\nu$. Then $0\leq f_{1}\leq 1$
$\mu$-a.e. and $0\leq f_{2}\leq 1$ $\nu$-a.e. Throughout the paper, $\bar{m}$
stands for the minimum of the total masses of $\mu$ and $\nu$. That is,
$\bar{m}:=\min\\{\mu({\mathcal{T}}),\nu({\mathcal{T}})\\}$. Inspiring by [10,
46], we fix a number $m\in[0,\bar{m}]$ and consider the following EPT problem:

$\displaystyle{\mathcal{W}}_{c,m}(\mu,\nu):=\inf_{\gamma\in\Pi_{\leq}(\mu,\nu),\,\gamma({\mathcal{T}}\times{\mathcal{T}})=m}\Big{[}{\mathcal{F}}_{1}(\gamma_{1}|\mu)$
$\displaystyle+{\mathcal{F}}_{2}(\gamma_{2}|\nu)+b\,\int_{{\mathcal{T}}\times{\mathcal{T}}}c(x,y)\gamma(dx,dy)\Big{]},\vspace{-6pt}$
(2)

where
${\mathcal{F}}_{1}(\gamma_{1}|\mu):=\int_{\mathcal{T}}w_{1}(x)F_{1}(f_{1}(x))\mu(dx)$
and
${\mathcal{F}}_{2}(\gamma_{2}|\nu):=\int_{\mathcal{T}}w_{2}(x)F_{2}(f_{2}(x))\nu(dx)$
are the weighted relative entropies. The role of the two entropies in the
minimization problem is to force the marginals of $\gamma$ close to $\mu$ and
$\nu$ respectively. Let us introduce a Lagrange multiplier
$\lambda\in{\mathbb{R}}$ conjugate to the constraint
$\gamma({\mathcal{T}}\times{\mathcal{T}})=m$. As a result, we instead study
the following formulation

$\displaystyle\mathrm{ET}_{c,\lambda}(\mu,\nu):=\inf_{\gamma\in\Pi_{\leq}(\mu,\nu)}\Big{[}{\mathcal{F}}_{1}(\gamma_{1}|\mu)+{\mathcal{F}}_{2}(\gamma_{2}|\nu)$
$\displaystyle+b\,\int_{{\mathcal{T}}\times{\mathcal{T}}}[c(x,y)-\lambda]\gamma(dx,dy)\Big{]}.\vspace{-6pt}$

In this paper, we focus on the specific entropy functions
$F_{1}(s)=F_{2}(s)=|s-1|$. Thus, the quantity of interest becomes

$\displaystyle\mathrm{ET}_{c,\lambda}(\mu,\nu)=\inf_{\gamma\in\Pi_{\leq}(\mu,\nu)}\mathcal{C}_{\lambda}(\gamma),$
(3)

where $\mathcal{C}_{\lambda}(\gamma)$ is defined as follow:

$\displaystyle\mathcal{C}_{\lambda}(\gamma):=\int_{\mathcal{T}}w_{1}[1-f_{1}(x)]\mu(dx)+\int_{\mathcal{T}}w_{2}[1-f_{2}(x)]\nu(dx)$
$\displaystyle\hskip
90.00014pt+b\,\int_{{\mathcal{T}}\times{\mathcal{T}}}[c(x,y)-\lambda]\gamma(dx,dy)$
$\displaystyle=\int_{\mathcal{T}}w_{1}\mu(dx)+\int_{\mathcal{T}}w_{2}\nu(dx)-\int_{\mathcal{T}}w_{1}\gamma_{1}(dx)$
$\displaystyle\hskip
5.0pt-\int_{\mathcal{T}}w_{2}\gamma_{2}(dx)+b\int_{{\mathcal{T}}\times{\mathcal{T}}}[c(x,y)-\lambda]\gamma(dx,dy).$
(4)

Notice that problem (3) is a generalization of the generalized Wasserstein
distance ${\mathcal{W}}_{1}^{a,b}(\mu,\nu)$ introduced in [56, 57]. We next
display some relationships between problem (3) with mass constraint $m$ and
problem (3) with Lagrange multiplier $\lambda$. For this, let
$\Gamma^{0}(\lambda)$ denote the set of all optimal plans (i.e., minimizers
$\gamma$) for $\mathrm{ET}_{c,\lambda}(\mu,\nu)$. Then, since
$\mathcal{C}_{\lambda}(\gamma)$ is an affine function of
$\gamma\in\Pi_{\leq}(\mu,\nu)$, the set $\Gamma^{0}(\lambda)$ is a nonempty
convex set. Indeed, for any
$\tilde{\gamma},\hat{\gamma}\in\Gamma^{0}(\lambda)$ and for any $t\in[0,1]$ we
have $(1-t)\tilde{\gamma}+t\hat{\gamma}\in\Gamma^{0}(\lambda)$ due to
$\mathcal{C}_{\lambda}((1-t)\tilde{\gamma}+t\hat{\gamma})=(1-t)\mathcal{C}_{\lambda}(\tilde{\gamma})+t\mathcal{C}_{\lambda}(\hat{\gamma})\leq(1-t)\mathcal{C}_{\lambda}(\gamma)+t\mathcal{C}_{\lambda}(\gamma)=\mathcal{C}_{\lambda}(\gamma)$
for every $\gamma\in\Pi_{\leq}(\mu,\nu)$. The following result extends
Corollary 2.1 in [10] and reveals the connection between problem (3) and
problem (3).

######  Theorem 3.1.

Let $u(\lambda):=-\mathrm{ET}_{c,\lambda}(\mu,\nu)$ for
$\lambda\in{\mathbb{R}}$, and denote

$\partial u(\lambda):=\Big{\\{}p\in{\mathbb{R}}:u(t)\geq
u(\lambda)+p(t-\lambda),\forall t\in{\mathbb{R}}\Big{\\}}\vspace{-6pt}$

for the set of all subgradients of $u$ at $\lambda$. Also, set $\partial
u({\mathbb{R}}):=\cup_{\lambda\in{\mathbb{R}}}\partial u(\lambda)$. Then, we
have

  * i)

$u$ is a convex function on ${\mathbb{R}}$, and

$\partial
u(\lambda)=\big{\\{}b\,\gamma({\mathcal{T}}\times{\mathcal{T}}):\gamma\in\Gamma^{0}(\lambda)\big{\\}}\quad\forall\lambda\in{\mathbb{R}}.\vspace{-4pt}$

Also if $\lambda_{1}<\lambda_{2}$, then $m_{1}\leq m_{2}$ for every
$m_{1}\in\partial u(\lambda_{1})$ and $m_{2}\in\partial u(\lambda_{2})$.

  * ii)

$u$ is differentiable at $\lambda$ if and only if every optimal plan in
$\Gamma^{0}(\lambda)$ has the same mass. When this happens, we in addition
have $u^{\prime}(\lambda)=b\,\gamma({\mathcal{T}}\times{\mathcal{T}})$ for any
$\gamma\in\Gamma^{0}(\lambda)$.

  * iii)

If there exists a constant $M>0$ such that $w_{1}(x)+w_{2}(y)\leq b\,c(x,y)+M$
for all $x,y\in{\mathcal{T}}$, then $\partial u({\mathbb{R}})=[0,b\,\bar{m}]$.
Moreover,
$u(\lambda)=-\int_{\mathcal{T}}w_{1}\mu(dx)-\int_{\mathcal{T}}w_{2}\nu(dx)$
when $\lambda<-M$, and $u^{\prime}(\lambda)=b\,\bar{m}$ for
$\lambda>\|c\|_{L^{\infty}({\mathcal{T}}\times{\mathcal{T}})}$.

Proof is placed in the Supplementary (§A.1). For any $m\in[0,\bar{m}]$, part
iii) of Theorem 3.1 implies that there exists $\lambda\in{\mathbb{R}}$ such
that $b\,m\in\partial u(\lambda)$. It then follows from part i) of this
theorem that $m=\gamma^{*}({\mathcal{T}}\times{\mathcal{T}})$ for some
$\gamma^{*}\in\Gamma^{0}(\lambda)$. It is also clear that this $\gamma^{*}$ is
an optimal plan for ${\mathcal{W}}_{c,m}(\mu,\nu)$, and

$\displaystyle{\mathcal{W}}_{c,m}(\mu,\nu)=\mathrm{ET}_{c,\lambda}(\mu,\nu)+\lambda
b\,m.$

Thus solving the auxiliary problem (3) gives us a solution to the original
problem (3). When $u$ is differentiable, the relation between $m$ and
$\lambda$ is given explicitly as $u^{\prime}(\lambda)=b\,m$. Note that the
above selection of $\lambda$ is unique only if the function $u$ is strictly
convex. Nevertheless, it enjoys the following monotonicity regardless of the
uniqueness: if $m_{1}<m_{2}$, then $\lambda_{1}\leq\lambda_{2}$. Indeed, we
have $m_{1}=\gamma^{1}({\mathcal{T}}\times{\mathcal{T}})$ and
$m_{2}=\gamma^{2}({\mathcal{T}}\times{\mathcal{T}})$ for some
$\gamma^{1}\in\Gamma^{0}(\lambda_{1})$ and
$\gamma^{2}\in\Gamma^{0}(\lambda_{2})$. Since
$\gamma^{1}({\mathcal{T}}\times{\mathcal{T}})<\gamma^{2}({\mathcal{T}}\times{\mathcal{T}})$,
one has $\lambda_{1}\leq\lambda_{2}$ by i) of Theorem 3.1.

To investigate problem (3), we recast it as the standard complete OT problem
by using an observation in [10]. More precisely, let $\hat{s}$ be a point
outside ${\mathcal{T}}$ and consider the set
$\hat{\mathcal{T}}:={\mathcal{T}}\cup\\{\hat{s}\\}$. We next extend the cost
function to $\hat{\mathcal{T}}\times\hat{\mathcal{T}}$ as follow

$\hat{c}(x,y):=\left\\{\begin{array}[]{lr}\\!\\!b[c(x,y)-\lambda]\hskip
10.00002pt\mbox{ if }x,y\in{\mathcal{T}},\\\ \\!\\!w_{1}(x)\hskip
40.00006pt\mbox{ if }x\in{\mathcal{T}}\mbox{ and }y=\hat{s},\\\
\\!\\!w_{2}(y)\hskip 40.00006pt\mbox{ if }x=\hat{s}\mbox{ and
}y\in{\mathcal{T}},\\\ \\!\\!0\hskip 60.00009pt\mbox{ if
}x=y=\hat{s}.\end{array}\right.$

The measures $\mu,\nu$ are extended accordingly by adding a Dirac mass at the
isolated point $\hat{s}$: $\hat{\mu}=\mu+\nu({\mathcal{T}})\delta_{\hat{s}}$
and $\hat{\nu}=\nu+\mu({\mathcal{T}})\delta_{\hat{s}}$. As
$\hat{\mu},\hat{\nu}$ have the same total mass on $\hat{\mathcal{T}}$, we can
consider the standard complete OT problem between $\hat{\mu},\hat{\nu}$ as
follow

$\displaystyle\mathrm{KT}(\hat{\mu},\hat{\nu}):=\inf_{\hat{\gamma}\in\Gamma(\hat{\mu},\hat{\nu})}\int_{\hat{\mathcal{T}}\times\hat{\mathcal{T}}}\hat{c}(x,y)\hat{\gamma}(dx,dy),$
(5)

where
$\Gamma(\hat{\mu},\hat{\nu}):=\Big{\\{}\hat{\gamma}\in{\mathcal{M}}(\hat{\mathcal{T}}\times\hat{\mathcal{T}}):\hat{\mu}(U)=\hat{\gamma}(U\times\hat{\mathcal{T}}),\,\hat{\nu}(U)=\hat{\gamma}(\hat{\mathcal{T}}\times
U)\mbox{ for all Borel sets }U\subset\hat{\mathcal{T}}\Big{\\}}$.

A one-to-one correspondence between $\gamma\in\Pi_{\leq}(\mu,\nu)$ and
$\hat{\gamma}\in\Gamma(\hat{\mu},\hat{\nu})$ is given by

$\displaystyle\hat{\gamma}=\gamma+[(1-f_{1})\mu]\otimes\delta_{\hat{s}}+\delta_{\hat{s}}\otimes[(1-f_{2})\nu]$
$\displaystyle+\gamma({\mathcal{T}}\times{\mathcal{T}})\delta_{(\hat{s},\hat{s})}.$
(6)

Indeed, if $\gamma\in\Pi_{\leq}(\mu,\nu)$, then it is clear that
$\hat{\gamma}$ defined by (3) satisfies
$\hat{\gamma}\in\Gamma(\hat{\mu},\hat{\nu})$. The converse is guaranteed by
the next technical result.

######  Lemma 3.2.

For $\hat{\gamma}\in\Gamma(\hat{\mu},\hat{\nu})$, let $\gamma$ be the
restriction of $\hat{\gamma}$ to ${\mathcal{T}}$. Then, relation (3) holds and
$\gamma\in\Pi_{\leq}(\mu,\nu)$.

Proof is placed in the Supplementary (§A.2).

These observations in particular display the following connection between the
EPT problem and the standard complete OT problem.

######  Proposition 3.3 (EPT versus complete OT).

For every $\mu,\nu\in{\mathcal{M}}({\mathcal{T}})$, we have
$\mathrm{ET}_{c,\lambda}(\mu,\nu)=\mathrm{KT}(\hat{\mu},\hat{\nu})$. Moreover,
relation (3) gives a one-to-one correspondence between optimal solution
$\gamma$ for EPT problem (3) and optimal solution $\hat{\gamma}$ for standard
complete OT problem (5).

Proof is placed in the Supplementary (§A.3).

###  3.1 Dual Formulations

The relationship given in Proposition 3.3 allows us to obtain the dual
formulation of EPT in problem (3) from that of problem (5) proved in [10,
Corollary 2.6].

######  Theorem 3.4 (Dual formula for general cost).

For any $\lambda\geq 0$ and nonnegative weights $w_{1}(x),w_{2}(x)$, we have

$\mathrm{ET}_{c,\lambda}(\mu,\nu)=\sup_{(u,v)\in{\mathbb{K}}}\Big{[}\int_{{\mathcal{T}}}u(x)\mu(dx)+\int_{{\mathcal{T}}}v(x)\nu(dx)\Big{]},\vspace{-10pt}$

where ${\mathbb{K}}:=\Big{\\{}(u,v):\,u\leq
w_{1},\,-b\lambda+\inf_{x\in{\mathcal{T}}}[b\,c(x,y)-w_{1}(x)]\leq v(y)\leq
w_{2}(y),\,u(x)+v(y)\leq b[c(x,y)-\lambda]\Big{\\}}$.

Proof is placed in the Supplementary (§A.4).

This dual formula is our main theoretical result and can be rewritten more
explicitly when the cost $c$ is the tree distance. Hereafter, we use
$c(x,y)=d_{\mathcal{T}}(x,y)$. To ease the notations, we simply write
$\mathrm{ET}_{\lambda}(\mu,\nu)$ for
$\mathrm{ET}_{d_{\mathcal{T}},\lambda}(\mu,\nu)$.

######  Corollary 3.5 (Dual formula for tree distance).

Assume that $\lambda\geq 0$ and the nonnegative weights $w_{1},w_{2}$ are
$b$-Lipschitz w.r.t. $d_{\mathcal{T}}$. Then, we have

$\displaystyle\mathrm{ET}_{\lambda}(\mu,\nu)=\sup\left\\{\int_{\mathcal{T}}f(\mu-\nu):\,f\in\mathbb{L}\right\\}$
$\displaystyle\hskip
100.00015pt-\frac{b\lambda}{2}\big{[}\mu({\mathcal{T}})+\nu({\mathcal{T}})\big{]},\vspace{-4pt}$
(7)

where $\mathbb{L}:=\Big{\\{}f\in
C({\mathcal{T}}):\,-w_{2}-\frac{b\lambda}{2}\leq f\leq
w_{1}+\frac{b\lambda}{2},\,|f(x)-f(y)|\leq b\,d_{\mathcal{T}}(x,y)\Big{\\}}$.

Proof is placed in the Supplementary (§A.5).

Corollary 3.5 extends the dual formulation for the generalized Wasserstein
distance ${\mathcal{W}}_{1}^{a,b}(\mu,\nu)$ proved in [57, Theorem 2] and
[13]. In the next section, we will leverage (3.5) to propose an effective
regularization for computation in practice.

######  Remark 3.6.

An example of $b$-Lipschitz weight is
$w(x)=a_{1}\,d_{\mathcal{T}}(x,x_{0})+a_{0}$ for some $x_{0}\in{\mathcal{T}}$
and for some constants $a_{1}\in[0,b]$ and $a_{0}\in[0,\infty)$.

As a consequence of the dual formulation, we obtain the following geometric
properties:

######  Proposition 3.7 (Geometric structures of metric d).

Assume that $\lambda\geq 0$ and the weights $w_{1},w_{2}$ are positive and
$b$-Lipschitz w.r.t. $d_{\mathcal{T}}$. Define
$d(\mu,\nu):=\mathrm{ET}_{\lambda}(\mu,\nu)+\frac{b\lambda}{2}\big{[}\mu({\mathcal{T}})+\nu({\mathcal{T}})\big{]}$.
Then, we have

  1. i)

$d(\mu+\sigma,\nu+\sigma)=d(\mu,\nu)$,
$\forall\sigma\in{\mathcal{M}}({\mathcal{T}})$.

  2. ii)

$d$ is a divergence and satisfies the triangle inequality $d(\mu,\nu)\leq
d(\mu,\sigma)+d(\sigma,\nu)$.

  3. iii)

If in addition $w_{1}=w_{2}$, then $({\mathcal{M}}({\mathcal{T}}),d)$ is a
complete metric space. Moreover, it is a geodesic space in the sense that for
every two points $\mu$ and $\nu$ in ${\mathcal{M}}({\mathcal{T}})$ there
exists a path $\varphi:[0,a]\to{\mathcal{M}}({\mathcal{T}})$ with
$a:=d(\mu,\nu)$ such that $\varphi(0)=\mu$, $\varphi(a)=\nu$, and

$d(\varphi(t),\varphi(s))=|t-s|\quad\mbox{for all }t,s\in[0,a].\vspace{-6pt}$

Proof is placed in the Supplementary (§A.6).

Let $m\in[0,\bar{m}]$, and choose $\lambda\geq 0$ such that there exists an
optimal plan $\gamma^{0}$ for $\mathrm{ET}_{\lambda}(\mu,\nu)$ with
$\gamma^{0}({\mathcal{T}}\times{\mathcal{T}})=m$. As pointed out right after
Theorem 3.1, this choice of $\lambda$ is possible. Then, the proof of Lemma
A.1 in the Supplementary (§A.6) shows that

$\displaystyle\inf_{\gamma\in\Pi_{\leq}(\mu,\nu),\,\gamma({\mathcal{T}}\times{\mathcal{T}})=m}\Big{[}{\mathcal{F}}_{1}(\gamma_{1}|\mu)+{\mathcal{F}}_{2}(\gamma_{2}|\nu)$
$\displaystyle\hskip
70.0001pt+b\,\int_{{\mathcal{T}}\times{\mathcal{T}}}c(x,y)\gamma(dx,dy)\Big{]}\leq
d(\mu,\nu).\vspace{-6pt}$

Moreover, the equality happens if and only if there exists an optimal plan
$\gamma^{0}$ for $\mathrm{ET}_{\lambda}(\mu,\nu)$ such that
$m=\gamma^{0}({\mathcal{T}}\times{\mathcal{T}})=\frac{1}{2}[\mu({\mathcal{T}})+\nu({\mathcal{T}})]$.
The necessary conditions for the latter one to hold is
$\mu({\mathcal{T}})=\nu({\mathcal{T}})$ and $m=\bar{m}$.

###  3.2 An Efficient Regularization for Entropy Partial Transport with Tree
Metrics

First observe that any $f\in\mathbb{L}$ can be represented by

$f(x)=f(r)+\int_{[r,x]}g(y)\omega(dy)\vspace{-4pt}$

for some function $g\in L^{\infty}({\mathcal{T}})$ with
$\|g\|_{L^{\infty}({\mathcal{T}})}\leq b$. Note that condition
$|f(x)-f(y)|\leq b\,d_{\mathcal{T}}(x,y)$ is equivalent to
$\|g\|_{L^{\infty}({\mathcal{T}})}\leq b$. It follows that
$\mathbb{L}\subset\mathbb{L}_{0}$, where we define for
$0\leq\alpha\leq\frac{1}{2}[b\lambda+w_{1}(r)+w_{2}(r)]$ that
$\mathbb{L}_{\alpha}$ is the collection of all functions $f$ of the form

$f(x)=s+\int_{[r,x]}g(y)\omega(dy),\vspace{-6pt}$

with $s$ being a constant in the interval
$\Big{[}-w_{2}(r)-\frac{b\lambda}{2}+\alpha,w_{1}(r)+\frac{b\lambda}{2}-\alpha\Big{]}$
and with $\|g\|_{L^{\infty}({\mathcal{T}})}\leq b$. This leads us to consider
the following regularization for $\mathrm{ET}_{\lambda}(\mu,\nu)$:

$\displaystyle\widetilde{\mathrm{ET}}_{\lambda}^{\alpha}(\mu,\nu):=\sup\left\\{\int_{\mathcal{T}}f(\mu-\nu):\,f\in\mathbb{L}_{\alpha}\right\\}$
$\displaystyle\hskip
100.00015pt-\frac{b\lambda}{2}\big{[}\mu({\mathcal{T}})+\nu({\mathcal{T}})\big{]}.\vspace{-10pt}$
(8)

Especially, when $\alpha=0$ and notice that $\mathbb{L}\subset\mathbb{L}_{0}$,
$\widetilde{\mathrm{ET}}_{\lambda}^{0}(\mu,\nu)$ is an upper bound of
$\mathrm{ET}_{\lambda}(\mu,\nu)$ through the dual formulation. The next result
gives a closed-form formula for
$\widetilde{\mathrm{ET}}_{\lambda}^{\alpha}(\mu,\nu)$ and is our main formula
used for computation in practice.

######  Proposition 3.8 (closed-form for regularized EPT).

Assume that $\lambda,w_{1}(r),w_{2}(r)$ are nonnegative numbers. Then, for
$0\leq\alpha\leq\frac{1}{2}[b\lambda+w_{1}(r)+w_{2}(r)]$, we have

$\displaystyle\widetilde{\mathrm{ET}}_{\lambda}^{\alpha}(\mu,\nu)=\int_{{\mathcal{T}}}|\mu(\Lambda(x))-\nu(\Lambda(x))|\,\omega(dx)$
$\displaystyle-\frac{b\lambda}{2}\big{[}\mu({\mathcal{T}})+\nu({\mathcal{T}})\big{]}+\big{[}w_{i}(r)+\frac{b\lambda}{2}-\alpha\big{]}|\mu({\mathcal{T}})-\nu({\mathcal{T}})|$

with $i:=1$ if $\mu({\mathcal{T}})\geq\nu({\mathcal{T}})$ and $i:=2$ if
$\mu({\mathcal{T}})<\nu({\mathcal{T}})$. In particular, the map
$\alpha\longmapsto\widetilde{\mathrm{ET}}_{\lambda}^{\alpha}(\mu,\nu)$ is
nonincreasing and

$|\widetilde{\mathrm{ET}}_{\lambda}^{\alpha_{1}}(\mu,\nu)-\widetilde{\mathrm{ET}}_{\lambda}^{\alpha_{2}}(\mu,\nu)|=|\alpha_{1}-\alpha_{2}||\mu({\mathcal{T}})-\nu({\mathcal{T}})|.$

Proof is placed in the Supplementary (§A.7).

It is also possible to use
$\widetilde{\mathrm{ET}}_{\lambda}^{\alpha}(\mu,\nu)$ to upper or lower bound
the distance $\mathrm{ET}_{\lambda}(\mu,\nu)$ as follows:

######  Proposition 3.9.

Assume that $\lambda\geq 0$ and the weights $w_{1},w_{2}$ are $b$-Lipschitz
w.r.t. $d_{\mathcal{T}}$. Then,

$\mathrm{ET}_{\lambda}(\mu,\nu)\leq\widetilde{\mathrm{ET}}_{\lambda}^{0}(\mu,\nu).\vspace{-4pt}$

In addition, if $[4L_{{\mathcal{T}}}-\lambda]b\leq w_{1}(r)+w_{2}(r)$ where
$L_{{\mathcal{T}}}:=\max_{x\in{\mathcal{T}}}\omega([r,x])$, then

$\widetilde{\mathrm{ET}}_{\lambda}^{\alpha}(\mu,\nu)\leq\mathrm{ET}_{\lambda}(\mu,\nu),\vspace{-4pt}$

for every
$2bL_{{\mathcal{T}}}\leq\alpha\leq\frac{1}{2}[b\lambda+w_{1}(r)+w_{2}(r)]$.

Proof is placed in the Supplementary (§A.8).

Analogous to Proposition 3.7, we obtain:

######  Proposition 3.10 (Geometric structures of regularized metric
$d_{\alpha}$).

Assume that $\lambda,w_{1}(r),w_{2}(r)$ are nonnegative numbers. For
$0\leq\alpha<\frac{b\lambda}{2}+\min\\{w_{1}(r),w_{2}(r)\\}$, define

$d_{\alpha}(\mu,\nu):=\widetilde{\mathrm{ET}}_{\lambda}^{\alpha}(\mu,\nu)+\frac{b\lambda}{2}\big{[}\mu({\mathcal{T}})+\nu({\mathcal{T}})\big{]}.\vspace{-6pt}$
(9)

Then, we have

  1. i)

$d_{\alpha}(\mu+\sigma,\nu+\sigma)=d_{\alpha}(\mu,\nu)$,
$\forall\sigma\in{\mathcal{M}}({\mathcal{T}})$.

  2. ii)

$d_{\alpha}$ is a divergence and satisfies the triangle inequality
$d_{\alpha}(\mu,\nu)\leq d_{\alpha}(\mu,\sigma)+d_{\alpha}(\sigma,\nu)$.

  3. iii)

If in addition $w_{1}(r)=w_{2}(r)$, then
$({\mathcal{M}}({\mathcal{T}}),d_{\alpha})$ is a complete metric space.
Moreover, it is a geodesic space in the sense defined in part iii) of
Proposition 3.7 but with $d_{\alpha}$ replacing $d$.

Proof is placed in the Supplementary (§A.9).

######  Proposition 3.11.

With the same assumptions as in Proposition 3.8 for
$\widetilde{\mathrm{ET}}_{\lambda}^{\alpha}$ and in Proposition 3.10 for
$d_{\alpha}$, both $\widetilde{\mathrm{ET}}_{\lambda}^{\alpha}$ and
$d_{\alpha}$ are negative definite.

Proof is placed in the Supplementary (§A.10).

From Proposition 3.11 and following Berg et al. [6] (Theorem 3.2.2, p.74),
given $t>0$, the kernels
$k_{\widetilde{\mathrm{ET}}_{\lambda}^{\alpha}}(\mu,\nu):=\exp\left(-t\widetilde{\mathrm{ET}}_{\lambda}^{\alpha}(\mu,\nu)\right)$
and $k_{d_{\alpha}}(\mu,\nu):=\exp\left(-td_{\alpha}(\mu,\nu)\right)$ are
positive definite.

###  3.3 Tree-sliced Variants by Sampling Tree Metrics

In most of practical applications, we usually do not have priori knowledge
about tree structure for measures. Therefore, we need to choose or sample tree
metrics from support data points for a given task. We use the tree metric
sampling methods in [43]: (i) partition-based tree metric sampling for a low-
dimensional space, or (ii) clustering-based tree metric sampling for a high-
dimensional space. Moreover, those tree metric sampling methods are not only
fast for computation111E.g., the complexity of the clustering-based tree
metric is $\mathcal{O}(H_{\mathcal{T}}m\log\kappa)$ when we set $\kappa$
clusters for the farthest-point clustering [24], and $H_{\mathcal{T}}$ for the
predefined tree deepest level for $m$ input support data points., but also
adaptive to the distribution of supports. We further propose the tree-sliced
variants of the regularized EPT, computed by averaging the regularized EPT
using those randomly sampled tree metrics. One advantage is to reduce the
quantization effects or cluster sensitivity problems (i.e, support data points
are quantized, or clustered into an adjacent hypercube, or cluster
respectively) within the tree metric sampling procedure.

Although one can leverage tree metrics to approximate arbitrary metrics [3, 4,
11, 19, 29], our goal is rather to sample tree metrics and use them as ground
metrics in the regularized EPT, similar to TSW. Despite the fact that one-
dimensional projections do not have interesting properties in terms of
distortion viewpoints, they remain useful for SPOT (or SW, sliced-Gromov-
Wasserstein [66]). In the same vein, we believe that trees with high
distortion are still useful for EPT, similar as in TSW. Moreover, one may not
need to spend excessive effort to optimize $\textnormal{ET}_{\lambda}$ (in
Equation (3.5)) for a randomly sampled tree metric since it can lead to
overfitting within the computation of the EPT itself. Therefore, the proposed
efficient regularization of EPT (e.g,
$\widetilde{\textnormal{ET}}_{\lambda}^{\alpha}$ in Equation (3.2)) is not
only fast for computation (i.e., closed-form), but also gives a benefit to
overcome the overfitting problem within the computation of the EPT.

##  4 Discussion and Related Work

One can leverage tree metrics to approximate arbitrary metrics for speeding up
a computation [3, 4, 11, 19, 29]. For instances, (i) Indyk and Thaper [30]
applied tree metrics (e.g., quadtree) to approximate OT with Euclidean cost
metric for a fast image retrieval. (ii) Sato et al. [60] considered a
generalized Kantorovich-Rubinstein discrepancy [25, 26, 45] with general
weights for unbalanced OT, and used a quadtree as in [30] to approximate the
proposed distance via a dynamic programming with infinitely many states. They
then derived an efficient algorithm with a quasi-linear time complexity to
speed up the dynamic programming computation by leveraging high-level
programming techniques. However, such approximations following the approach of
[30] result in large distortions in high dimensional spaces [53].

##  5 Experiments

In this section, we first illustrate that
$\widetilde{\textnormal{ET}}_{\lambda}^{\alpha}$ (Equation (3.2)) is an
efficient approximation for $\textnormal{ET}_{\lambda}$ (Equation (3.5)).
Then, we evaluate our proposed
$\widetilde{\textnormal{ET}}_{\lambda}^{\alpha}$ and $d_{\alpha}$ (Equation
(9)) for comparing measures in document classification with word embedding and
topological data analysis (TDA). Experiments are evaluated with Intel Xeon CPU
E7-8891v3 2.80GHz and 256GB RAM.

##### Documents with word embedding.

We consider each document as a measure where each word is regarded as a point
in the support with a unit mass. Following [36, 43], we applied the word2vec
word embedding [50], pretrained on Google
News222https://code.google.com/p/word2vec containing about 3 millions
words/phrases. Each word/phrase in a document is mapped into a vector in
$\mathbb{R}^{300}$. We removed all SMART stop word [59], and dropped words in
documents if they are not available in the pretrained word2vec.

##### Geometric structured data via persistence diagrams in TDA.

TDA has recently emerged in machine learning community as a powerful tool to
analyze geometric structured data such as material data, or linked twist maps
[1, 37, 42]. TDA applies algebraic topology methods (e.g., persistence
homology) to extract robust topological features (e.g., connected components,
rings, cavities) and output a multiset of 2-dimensional points, i.e.,
persistence diagram (PD). The coordinates of a 2-dimensional point in PD are
corresponding to the birth and death time of a particular topological feature.
Therefore, each point in PD summarizes a life span of a topological feature.
We can regard PD as measures where each 2-dimensional point is considered as a
point in the support with a unit mass.

##### Tree metric sampling.

In our experiments, we do not have priori knowledge about tree metrics for
neither word embeddings in documents nor 2-dimensional points in persistence
diagrams (PDs). To compute the EPT, e.g.,
$\widetilde{\textnormal{ET}}_{\lambda}^{\alpha}$ and its associated
$d_{\alpha}$, we considered $n_{s}$ randomized tree metrics. We employed the
clustering-based tree metric sampling for word embeddings in documents (i.e.,
high-dimensional space $\mathbb{R}^{300}$), while we used the partition-based
tree metric sampling for 2-dimensional points in PDs (i.e., low-dimensional
space $\mathbb{R}^{2}$). Those tree metric sampling methods are built with a
predefined deepest level $H_{\mathcal{T}}$ of tree $\mathcal{T}$ as a stopping
condition as in [43].

##### Baselines and setup.

We considered 2 baselines based on OT theory for measures with different
masses: (i) Sinkhorn-UOT [12, 22], and (ii) SPOT [7]. Following [43], we apply
the kernel approach in the form $\exp(-t\bar{d})$ with SVM for document
classification with word embedding. Here, $\bar{d}$ is a discrepancy between
measures and $t>0$. We also employed this kernel approach for various tasks in
TDA, e.g., orbit recognition and object shape classification with SVM, as well
as change point detection for material data analysis with kernel Fisher
discriminant ratio (KFDR) [27]. While kernels for
$\widetilde{\textnormal{ET}}_{\lambda}^{\alpha}$ and $d_{\alpha}$ are positive
definite, kernels for Sinkhorn-UOT and SPOT are empirically indefinite333In
practice, we observed negative eigenvalues of some Gram matrices corresponding
to kernels for Sinkhorn-UOT and SPOT.. When kernels are indefinite, we
regularized for the corresponding Gram matrices by adding a sufficiently large
diagonal term as in [15, 43]. For SVM, we randomly split each dataset into
$70\%/30\%$ for training and test with 10 repeats. Typically, we choose hyper-
parameters via cross validation, choose $1/t$ from
$\\{q_{10},q_{20},q_{50}\\}$ where $q_{s}$ is the $s\%$ quantile of a subset
of corresponding discrepancies observed on a training set, use 1-vs-1 strategy
with Libsvm444https://www.csie.ntu.edu.tw/$\sim$cjlin/libsvm/ for multi-class
classification, and choose SVM regularization from
$\left\\{10^{-2:1:2}\right\\}$. For Sinkhorn-UOT, we select the entropic
regularization from $\left\\{0.01,0.05,0.1,0.5,1\right\\}$. Following
Proposition 3.9, we take $\alpha=0$ for
$\widetilde{\textnormal{ET}}_{\lambda}^{\alpha}$ and $d_{\alpha}$ in all our
experiments.

###  5.1 Efficient Approximation of
$\widetilde{\textnormal{ET}}_{\lambda}^{0}$ for $\textnormal{ET}_{\lambda}$

Figure 1: Relative difference between
$\widetilde{\textnormal{ET}}_{\lambda}^{0}$ and $\textnormal{ET}_{\lambda}$
w.r.t. Lipschitz const. of $w_{1},w_{2}$.

We randomly sample 500K pairs of documents in TWITTER dataset. Following
Proposition 3.3, we compute $\textnormal{ET}_{\lambda}$ via the corresponding
KT (Equation (5)). Our goal is to compare
$\widetilde{\textnormal{ET}}_{\lambda}^{0}$ to $\textnormal{ET}_{\lambda}$.

Figure 2: Relative difference between
$\widetilde{\textnormal{ET}}_{\lambda}^{0}$ and $\textnormal{ET}_{\lambda}$
w.r.t. $\lambda$ when $a_{1}=b$. (LT := $L_{\mathcal{T}}$)

Change Lipschitz constants. We choose
$w_{1}(x)=w_{2}(x)=a_{1}d_{\mathcal{T}}(r,x)+a_{0}$, and set $\lambda=b=1$,
$a_{0}=1$. In particular, $a_{1}\in[0,b]$ since $w_{1},w_{2}$ are
$b$-Lipschitz functions (see Corollary 3.5 and Remark 3.6). We illustrate the
relative difference
$(\widetilde{\textnormal{ET}}_{\lambda}^{0}-\textnormal{ET}_{\lambda})/\textnormal{ET}_{\lambda}$
when $a_{1}$ is changed in $[0,b]$ in Figure 1. We observe that when $a_{1}$
is close to $b$ (i.e., the Lipschitz constants of $w_{1},w_{2}$ are close to
$b$), $\widetilde{\textnormal{ET}}_{\lambda}^{0}$ becomes closer to
$\textnormal{ET}_{\lambda}$. When $a_{1}=b$, the values of
$\widetilde{\textnormal{ET}}_{\lambda}^{0}$ is almost identical to
$\textnormal{ET}_{\lambda}$.

Change $\lambda$. From the results in Figure 1, we set $a_{1}=b$ to
investigate the relative different between
$\widetilde{\textnormal{ET}}_{\lambda}^{0}$ and $\textnormal{ET}_{\lambda}$
when $\lambda$ is changed. As illustrated in Figure 2,
$\widetilde{\textnormal{ET}}_{\lambda}^{0}$ is almost identical to
$\textnormal{ET}_{\lambda}$ regardless the value of $\lambda$ when $a_{1}=b$.

###  5.2 Document Classification with Word Embedding

We consider 4 datasets: TWITTER, RECIPE, CLASSIC and AMAZON for document
classification with word embedding. Statistical characteristics of these
datasets are summarized in Figure 3.

Figure 3: SVM results on document classification (row 1), and corresponding
time consumption of kernel matrices (row 2). For each dataset, the numbers in
the parenthesis are respectively the number of classes, the number of
documents, and the maximum number of unique words for each document.

###  5.3 Topological Data Analysis (TDA)

Figure 4: SVM results for TDA (row 1), and corresponding time consumption of
kernel matrices (row 2). For each dataset, the numbers in the parenthesis are
respectively the number of PDs, and the maximum number of points in PD.

####  5.3.1 Orbit Recognition

We considered a synthesized dataset, proposed by Adams et al. [1], for link
twist map which is a discrete dynamical system to model flows in DNA
microarrays [28]. There are 5 classes of orbits. Following [42], we generated
1000 orbits for each class of orbits, and each orbit has 1000 points. We used
the 1-dimensional topological features for PD extracted with Vietoris-Rips
complex filtration [16].

####  5.3.2 Object Shape Classification

We evaluated our approach for object shape classification on a subset of MPEG7
dataset [38] containing 10 classes where each class has 20 samples as in [42].
For simplicity, we followed [42] to extract $1$-dimensional topological
features for PD with Vietoris-Rips complex filtration555A more complicated and
advanced filtration for this task is considered in [65]. [16].

####  5.3.3 Change Point Detection for Material Analysis

We applied our approach on change point detection for material analysis with
KFDR as a statistical score on granular packing system (GPS) [21] and SiO2
[52] datasets. Statistical characteristics of these datasets are summarized in
Figure 5. Following [42], we set $10^{-3}$ for the regularization parameter in
KFDR and used the ball model filtration to extract 2-dimensional topological
features for PD in GPS dataset, and 1-dimensional topological features for PD
in SiO2 dataset. Note that we omit the baseline kernel for Sinkhorn-UOT in
this application since its computation of Sinkhorn-UOT is out of memory.

Figure 5: KFDR graphs and time consumption of kernel matrices for change point
detection. For each dataset, the numbers in the parenthesis are respectively
the number of PDs, and the maximum number of points in PD.

We illustrate the KFDR graphs for both datasets in Figure 5. For GPS dataset,
all kernel approaches get the change point at the index 23 which supports the
observation (corresponding id = 23) in [2]. For SiO2 dataset, all kernel
approaches get the change point in a supported range ($35\leq\text{id}\leq
50)$, obtained by a traditional physical approach [17]. The KFDR results of
kernels corresponding to $d_{0}$ and
$\widetilde{\textnormal{ET}}_{\lambda}^{0}$ compare favorably with those of
kernel for SPOT.

###  5.4 Results of SVM, Time Consumption and Discussions

Figure 6: SVM results and time consumption for corresponding kernel matrices
in TWITTER dataset w.r.t. the number of (tree) slices.

We illustrate the results of SVM and time consumption of kernel matrices in
document classification with word embedding and TDA in Figure 3 and Figure 4
respectively. The performances of kernels for
$\widetilde{\textnormal{ET}}_{\lambda}^{0}$ and $d_{0}$ outperform those of
kernels for SPOT. They also outperform those of kernels for Sinkhorn-UOT on
TDA, and are comparative on document classification. The fact that SPOT uses
the 1-dimensional projection for support data points may limit its ability to
capture high-dimensional structure in data distributions [43, 47]. The
regularized EPT remedies this problem by leveraging the tree metrics which
have more flexibility and degrees of freedom (e.g., choose a tree rather than
a line). In addition, while kernels for
$\widetilde{\textnormal{ET}}_{\lambda}^{0}$ and $d_{0}$ are positive definite,
kernels for SPOT and Sinkhorn-UOT are empirically indefinite. The
indefiniteness of kernels may affect their performances in some applications,
e.g., kernels for Sinkhorn-UOT work well for document classification with word
embedding, but perform poorly in TDA applications. There are also similar
observations in [43]. Additionally, we illustrate a trade-off between
performances and computational time for different number of (tree) slices in
TWITTER dataset in Figure 6. The performances are usually improved with more
slices, but with a trade-off about the computational time. In applications, we
observed that a good trade off is about $n_{s}=10$ slices.

Tree metric sampling. Time consumption for the tree metric sampling is
negligible in applications. With the predefined tree deepest level
$H_{\mathcal{T}}=6$ and tree branches $\kappa=4$ as in [43], it took
$1.5,11.0,17.5,20.5$ seconds for TWITTER, RECIPE, CLASSIC, AMAZON datasets
respectively, and $21.0,0.1$ seconds for Orbit, MPEG7 datasets respectively.

$\widetilde{\textnormal{ET}}_{\lambda}^{0}$ versus
$\textnormal{ET}_{\lambda}$. We also compare
$\widetilde{\textnormal{ET}}_{\lambda}^{0}$ and $\textnormal{ET}_{\lambda}$
(or KT) in TWITTER dataset for document classification, and in MPEG7 dataset
for object shape recognition in TDA. The performances of
$\widetilde{\textnormal{ET}}_{\lambda}^{0}$ and $\textnormal{ET}_{\lambda}$
are identical (i.e., their kernel matrices are almost the same for those
datasets), but $\widetilde{\textnormal{ET}}_{\lambda}^{0}$ is faster than
$\textnormal{ET}_{\lambda}$ about 11 times in TWITTER dataset, and 81 times in
MPEG7 dataset when $n_{s}=10$ slices.

Further results are placed in the supplementary (§B).

##  6 Conclusion

We have developed a rigorous theory for the entropy partial transport (EPT)
problem for nonnegative measures on a tree having different masses. We show
that the EPT problem is equivalent to a standard complete OT problem on a
suitable one-node extended tree which allows us to develop its dual
formulation. By leveraging the dual problem, we proposed efficient novel
regularization for EPT which yields closed-form solution for a fast
computation and negative definiteness—an important property to build positive
definite kernels required in many kernel-dependent frameworks. Moreover, our
regularization also provides effective approximations in applications. We
further derive tree-sliced variants of the regularized EPT for practical
applications without priori knowledge about a tree structure for measures. The
question about sampling efficient tree metrics for the tree-sliced variants
from data points is left for future work.

## References

  * [1] Henry Adams, Tegan Emerson, Michael Kirby, Rachel Neville, Chris Peterson, Patrick Shipman, Sofya Chepushtanova, Eric Hanson, Francis Motta, and Lori Ziegelmeier.  Persistence images: A stable vector representation of persistent homology.  Journal of Machine Learning Research, 18(1):218–252, 2017.
  * [2] Anonymous.  What is random packing?  Nature, 239:488–489, 1972.
  * [3] Yair Bartal.  Probabilistic approximation of metric spaces and its algorithmic applications.  In Proceedings of 37th Conference on Foundations of Computer Science, pages 184–193, 1996.
  * [4] Yair Bartal.  On approximating arbitrary metrices by tree metrics.  In ACM Symposium on Theory of Computing (STOC), volume 98, pages 161–168, 1998.
  * [5] Jean-David Benamou.  Numerical resolution of an “unbalanced” mass transport problem.  ESAIM: Mathematical Modelling and Numerical Analysis-Modélisation Mathématique et Analyse Numérique, 37(5):851–868, 2003.
  * [6] C. Berg, J. P. R. Christensen, and P. Ressel, editors.  Harmonic analysis on semigroups.  Springer-Verglag, New York, 1984.
  * [7] Nicolas Bonneel and David Coeurjolly.  Spot: sliced partial optimal transport.  ACM Transactions on Graphics (TOG), 38(4):1–13, 2019.
  * [8] Nicolas Bonneel, Julien Rabin, Gabriel Peyré, and Hanspeter Pfister.  Sliced and radon wasserstein barycenters of measures.  Journal of Mathematical Imaging and Vision, 51(1):22–45, 2015.
  * [9] Charlotte Bunne, David Alvarez-Melis, Andreas Krause, and Stefanie Jegelka.  Learning Generative Models across Incomparable Spaces.  In International Conference on Machine Learning (ICML), volume 97, 2019.
  * [10] Luis A Caffarelli and Robert J McCann.  Free boundaries in optimal transport and monge-ampere obstacle problems.  Annals of mathematics, pages 673–730, 2010.
  * [11] Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, and Serge Plotkin.  Approximating a finite metric by a small number of tree metrics.  In Proceedings 39th Annual Symposium on Foundations of Computer Science (FOCS), pages 379–388, 1998.
  * [12] Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavier Vialard.  Scaling algorithms for unbalanced optimal transport problems.  Mathematics of Computation, 87(314):2563–2609, 2018.
  * [13] Nhan-Phu Chung and Thanh-Son Trinh.  Duality and quotient spaces of generalized wasserstein spaces.  arXiv preprint arXiv:1904.12461, 2019.
  * [14] Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamonjy.  Joint distribution optimal transportation for domain adaptation.  In Advances in Neural Information Processing Systems, pages 3730–3739, 2017.
  * [15] M. Cuturi.  Sinkhorn distances: Lightspeed computation of optimal transport.  In Advances in Neural Information Processing Systems, pages 2292–2300, 2013.
  * [16] Herbert Edelsbrunner and John Harer.  Persistent homology-a survey.  Contemporary mathematics, 453:257–282, 2008.
  * [17] Stephen Richard Elliott.  Physics of amorphous materials.  Longman Group, 1983.
  * [18] Steven N Evans and Frederick A Matsen.  The phylogenetic kantorovich–rubinstein metric for environmental sequence samples.  Journal of the Royal Statistical Society: Series B (Statistical Methodology), 74(3):569–592, 2012.
  * [19] Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar.  A tight bound on approximating arbitrary metrics by tree metrics.  Journal of Computer and System Sciences, 69(3):485–497, 2004.
  * [20] Alessio Figalli.  The optimal partial transport problem.  Archive for rational mechanics and analysis, 195(2):533–560, 2010\.
  * [21] Nicolas Francois, Mohammad Saadatfar, R Cruikshank, and A Sheppard.  Geometrical frustration in amorphous and partially crystallized packings of spheres.  Physical review letters, 111(14):148001, 2013.
  * [22] Charlie Frogner, Chiyuan Zhang, Hossein Mobahi, Mauricio Araya, and Tomaso A Poggio.  Learning with a wasserstein loss.  In Advances in neural information processing systems, pages 2053–2061, 2015.
  * [23] Wilfrid Gangbo, Wuchen Li, Stanley Osher, and Michael Puthawala.  Unnormalized optimal transport.  Journal of Computational Physics, 399:108940, 2019.
  * [24] Teofilo F Gonzalez.  Clustering to minimize the maximum intercluster distance.  Theoretical Computer Science, 38:293–306, 1985.
  * [25] Kevin Guittet.  Extended kantorovich norms: a tool for optimization.  INRIA report, 2002.
  * [26] Leonid G Hanin.  Kantorovich-rubinstein norm and its application in the theory of lipschitz spaces.  Proceedings of the American Mathematical Society, 115(2):345–352, 1992.
  * [27] Zaid Harchaoui, Eric Moulines, and Francis R Bach.  Kernel change-point analysis.  In Advances in neural information processing systems, pages 609–616, 2009.
  * [28] Jan-Martin Hertzsch, Rob Sturman, and Stephen Wiggins.  Dna microarrays: design principles for maximizing ergodic, chaotic mixing.  Small, 3(2):202–218, 2007.
  * [29] Piotr Indyk.  Algorithmic applications of low-distortion geometric embeddings.  In Proceedings 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pages 10–33, 2001.
  * [30] Piotr Indyk and Nitin Thaper.  Fast image retrieval via embeddings.  In International workshop on statistical and computational theories of vision, volume 2, page 5, 2003.
  * [31] Hicham Janati, Marco Cuturi, and Alexandre Gramfort.  Wasserstein regularization for sparse multi-task regression.  In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1407–1416, 2019.
  * [32] Hicham Janati, Boris Muzellec, Gabriel Peyré, and Marco Cuturi.  Entropic optimal transport between (unbalanced) gaussian measures has a closed form.  In Advances in neural information processing systems, 2020.
  * [33] Benoît R Kloeckner.  A geometric study of Wasserstein spaces: ultrametrics.  Mathematika, 61(1):162–178, 2015.
  * [34] Soheil Kolouri, Kimia Nadjahi, Umut Simsekli, Roland Badeau, and Gustavo Rohde.  Generalized sliced wasserstein distances.  In Advances in Neural Information Processing Systems, pages 261–272, 2019.
  * [35] Genki Kusano, Kenji Fukumizu, and Yasuaki Hiraoka.  Kernel method for persistence diagrams via kernel embedding and weight factor.  The Journal of Machine Learning Research, 18(1):6947–6987, 2017\.
  * [36] Matt Kusner, Yu Sun, Nicholas Kolkin, and Kilian Weinberger.  From word embeddings to document distances.  In International conference on machine learning, pages 957–966, 2015.
  * [37] Théo Lacombe, Marco Cuturi, and Steve Oudot.  Large scale computation of means and clusters for persistence diagrams using optimal transport.  In Advances in Neural Information Processing Systems, pages 9770–9780, 2018.
  * [38] Longin Jan Latecki, Rolf Lakamper, and T Eckhardt.  Shape descriptors for non-rigid shapes with a single closed contour.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), volume 1, pages 424–429, 2000.
  * [39] Hugo Lavenant, Sebastian Claici, Edward Chien, and Justin Solomon.  Dynamical optimal transport on discrete surfaces.  In SIGGRAPH Asia 2018 Technical Papers, page 250. ACM, 2018.
  * [40] Tam Le, Nhat Ho, and Makoto Yamada.  Flow-based alignment approaches for probability measures in different spaces.  In International Conference on Artificial Intelligence and Statistics (AISTATS). 2021.
  * [41] Tam Le, Viet Huynh, Nhat Ho, Dinh Phung, and Makoto Yamada.  On scalable variant of wasserstein barycenter.  arXiv preprint arXiv:1910.04483, 2019.
  * [42] Tam Le and Makoto Yamada.  Persistence Fisher kernel: A Riemannian manifold kernel for persistence diagrams.  In Advances in Neural Information Processing Systems, pages 10007–10018, 2018.
  * [43] Tam Le, Makoto Yamada, Kenji Fukumizu, and Marco Cuturi.  Tree-sliced variants of Wasserstein distances.  In Advances in neural information processing systems, pages 12283–12294, 2019.
  * [44] John Lee, Nicholas P Bertrand, and Christopher J Rozell.  Parallel unbalanced optimal transport regularization for large scale imaging problems.  arXiv preprint arXiv:1909.00149, 2019.
  * [45] Jan Lellmann, Dirk A Lorenz, Carola Schonlieb, and Tuomo Valkonen.  Imaging with kantorovich–rubinstein discrepancy.  SIAM Journal on Imaging Sciences, 7(4):2833–2859, 2014.
  * [46] Matthias Liero, Alexander Mielke, and Giuseppe Savaré.  Optimal entropy-transport problems and a new hellinger–kantorovich distance between positive measures.  Inventiones mathematicae, 211(3):969–1117, 2018.
  * [47] Antoine Liutkus, Umut Simsekli, Szymon Majewski, Alain Durmus, and Fabian-Robert Stöter.  Sliced-wasserstein flows: Nonparametric generative modeling via optimal transport and diffusions.  In International Conference on Machine Learning, pages 4104–4113, 2019.
  * [48] Facundo Mémoli, Axel Munk, Zhengchao Wan, and Christoph Weitkamp.  The ultrametric gromov-wasserstein distance.  arXiv preprint arXiv:2101.05756, 2021.
  * [49] Gonzalo Mena and Jonathan Niles-Weed.  Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem.  In Advances in Neural Information Processing Systems, pages 4541–4551, 2019.
  * [50] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean.  Distributed representations of words and phrases and their compositionality.  In Advances in neural information processing systems, pages 3111–3119, 2013.
  * [51] Kimia Nadjahi, Alain Durmus, Umut Simsekli, and Roland Badeau.  Asymptotic guarantees for learning generative models with the sliced-wasserstein distance.  In Advances in Neural Information Processing Systems, pages 250–260, 2019.
  * [52] Takenobu Nakamura, Yasuaki Hiraoka, Akihiko Hirata, Emerson G Escolar, and Yasumasa Nishiura.  Persistent homology and many-body atomic structure for medium-range order in the glass.  Nanotechnology, 26(30):304001, 2015.
  * [53] Assaf Naor and Gideon Schechtman.  Planar Earthmover is not in L_1.  SIAM Journal on Computing, 37(3):804–826, 2007.
  * [54] Gabriel Peyré and Marco Cuturi.  Computational optimal transport.  Foundations and Trends® in Machine Learning, 11(5-6):355–607, 2019.
  * [55] Khiem Pham, Khang Le, Nhat Ho, Tung Pham, and Hung Bui.  On unbalanced optimal transport: An analysis of Sinkhorn algorithm.  In Proceedings of the International Conference on Machine Learning, 2020.
  * [56] Benedetto Piccoli and Francesco Rossi.  Generalized wasserstein distance and its application to transport equations with source.  Archive for Rational Mechanics and Analysis, 211(1):335–358, 2014\.
  * [57] Benedetto Piccoli and Francesco Rossi.  On properties of the generalized wasserstein distance.  Archive for Rational Mechanics and Analysis, 222(3):1339–1365, 2016\.
  * [58] Julien Rabin, Gabriel Peyré, Julie Delon, and Marc Bernot.  Wasserstein barycenter and its application to texture mixing.  In International Conference on Scale Space and Variational Methods in Computer Vision, pages 435–446, 2011.
  * [59] Gerard Salton and Christopher Buckley.  Term-weighting approaches in automatic text retrieval.  Information processing & management, 24(5):513–523, 1988.
  * [60] Ryoma Sato, Makoto Yamada, and Hisashi Kashima.  Fast unbalanced optimal transport on tree.  In Advances in neural information processing systems, 2020.
  * [61] Geoffrey Schiebinger, Jian Shu, Marcin Tabaka, Brian Cleary, Vidya Subramanian, Aryeh Solomon, Joshua Gould, Siyan Liu, Stacie Lin, Peter Berube, et al.  Optimal-transport analysis of single-cell gene expression identifies developmental trajectories in reprogramming.  Cell, 176(4):928–943, 2019.
  * [62] Charles Semple and Mike Steel.  Phylogenetics.  Oxford Lecture Series in Mathematics and its Applications, 2003\.
  * [63] Justin Solomon, Fernando De Goes, Gabriel Peyré, Marco Cuturi, Adrian Butscher, Andy Nguyen, Tao Du, and Leonidas Guibas.  Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains.  ACM Transactions on Graphics (TOG), 34(4):66, 2015.
  * [64] Max Sommerfeld and A. Munk.  Inference for empirical wasserstein distances on finite spaces.  Journal of The Royal Statistical Society Series B-statistical Methodology, 80:219–238, 2016.
  * [65] Katharine Turner, Sayan Mukherjee, and Doug M Boyer.  Persistent homology transform for modeling shapes and surfaces.  Information and Inference: A Journal of the IMA, 3(4):310–344, 2014\.
  * [66] Titouan Vayer, Rémi Flamary, Romain Tavenard, Laetitia Chapel, and Nicolas Courty.  Sliced Gromov-Wasserstein.  Advances in Neural Information Processing Systems, 2019.
  * [67] Cédric Villani.  Optimal transport: old and new, volume 338.  Springer Science & Business Media, 2008.
  * [68] Jonathan Weed and Quentin Berthet.  Estimation of smooth densities in wasserstein distance.  In Proceedings of the Thirty-Second Conference on Learning Theory, volume 99, pages 3118–3119, 2019.
  * [69] Karren D. Yang and Caroline Uhler.  Scalable unbalanced optimal transport using generative adversarial networks.  In International Conference on Learning Representations, 2019.

In the supplementary,

  * •

We give detailed proofs of the theoretical results in the main text for the
entropy partial transport (EPT) problem for nonnegative measures on a tree
having different masses in §A.

  * •

We provide further experimental results in §B. For examples,

    * –

about more setups for the efficient approximation of
$\widetilde{\textnormal{ET}}_{\lambda}^{0}$ for
$\widetilde{\textnormal{ET}}_{\lambda}^{\alpha}$,

    * –

about different values of $\alpha$,

    * –

about different numbers of slices,

    * –

and about different parameters in tree metric sampling.

  * •

We next give more details and discussions in §C. For examples,

    * –

more details about experiments (e.g., softwares, datasets, more details about
the experiment setup).

    * –

some brief review about kernels, and more referred details (e.g., for tree
metric sampling, persistence diagrams and related mathematical definitions in
topological data analysis).

    * –

more discussions about other relations with other work.

##  Appendix A Detailed Proofs

In this section, we present detailed proofs of the theoretical results in the
main text.

###  A.1 Proof for Theorem 3.1 in the main text

###### Proof.

i) Note that $\mathrm{ET}_{c,\lambda}(\mu,\nu)$ is a concave function in
$\lambda$ since it is the infimum of a family of concave functions in
$\lambda$. Therefore, $u$ is convex on ${\mathbb{R}}$. In particular, $u$ is
differentiable almost everywhere on ${\mathbb{R}}$.

Let $\lambda\in{\mathbb{R}}$, recall the definition of
$\mathcal{C}_{\lambda}(\gamma)$ in Equation (4) in the main text. Then for any
$\gamma\in\Gamma^{0}(\lambda)$, we have

$\displaystyle\mathrm{ET}_{c,\lambda+\delta}(\mu,\nu)\leq\mathcal{C}_{\lambda+\delta}(\gamma)=\mathcal{C}_{\lambda}(\gamma)-b\delta\gamma({\mathcal{T}}\times{\mathcal{T}})=\mathrm{ET}_{c,\lambda}(\mu,\nu)-b\delta\gamma({\mathcal{T}}\times{\mathcal{T}})\,\,\,\forall\delta\in{\mathbb{R}}.$
(10)

This implies that

$\big{\\{}b\,\gamma({\mathcal{T}}\times{\mathcal{T}}):\gamma\in\Gamma^{0}(\lambda)\big{\\}}\subset\partial
u(\lambda).$

We next show that the opposite inclusion is also true, i.e.,
$\big{\\{}b\,\gamma({\mathcal{T}}\times{\mathcal{T}}):\gamma\in\Gamma^{0}(\lambda)\big{\\}}=\partial
u(\lambda)$. This is obviously holds if $\partial u(\lambda)$ is singleton and
hence we only need to consider $\lambda$ for which the convex set $\partial
u(\lambda)$ has more than one element.

Let $m\in\partial u(\lambda)$, then $m$ can be expressed as a convex
combination of extreme points $m_{1},\dotsc,m_{N}$ of $\partial u(\lambda)$,
i.e., $m=\sum_{i=1}^{N}t_{i}m_{i}$ with $0\leq t_{i}\leq 1$ and
$\sum_{i=1}^{N}t_{i}=1$. As $m_{i}$ is an extreme point of $\partial
u(\lambda)$, there exists a sequence $\lambda_{n}\to\lambda$ such that
$\lambda_{n}$ is a differentiable point of $u$ and $u^{\prime}(\lambda_{n})\to
m_{i}$.

Let $\gamma^{n}\in\Gamma^{0}(\lambda_{n})$, then
$b\,\gamma^{n}({\mathcal{T}}\times{\mathcal{T}})=u^{\prime}(\lambda_{n})\to
m_{i}$. By compactness, there exists a subsequence $\\{\gamma^{n_{k}}\\}$ and
$\tilde{\gamma}^{i}\in\Pi_{\leq}(\mu,\nu)$ such that
$\gamma^{n_{k}}\to\tilde{\gamma}^{i}$ weakly. It follows that
$\gamma^{n_{k}}({\mathcal{T}}\times{\mathcal{T}})\to\tilde{\gamma}^{i}({\mathcal{T}}\times{\mathcal{T}})$,
and hence we must have
$b\,\tilde{\gamma}^{i}({\mathcal{T}}\times{\mathcal{T}})=m_{i}$. We have

$\displaystyle\mathcal{C}_{\lambda_{n_{k}}}(\gamma^{\lambda_{n_{k}}})=\mathcal{C}_{\lambda}(\gamma^{\lambda_{n_{k}}})+b(\lambda-\lambda_{n_{k}})\gamma^{n_{k}}({\mathcal{T}}\times{\mathcal{T}})$
$\displaystyle\geq\mathrm{ET}_{c,\lambda}(\mu,\nu)+b(\lambda-\lambda_{n_{k}})\gamma^{n_{k}}({\mathcal{T}}\times{\mathcal{T}})$
$\displaystyle\geq\mathrm{ET}_{c,\lambda}(\mu,\nu)-b\bar{m}|\lambda-\lambda_{n_{k}}|$

and for any $\gamma\in\Gamma^{0}(\lambda)$, there holds

$\displaystyle\mathcal{C}_{\lambda_{n_{k}}}(\gamma^{\lambda_{n_{k}}})\leq\mathcal{C}_{\lambda_{n_{k}}}(\gamma)=\mathcal{C}_{\lambda}(\gamma)+b(\lambda-\lambda_{n_{k}})\gamma({\mathcal{T}}\times{\mathcal{T}})=\mathrm{ET}_{c,\lambda}(\mu,\nu)+b(\lambda-\lambda_{n_{k}})\gamma({\mathcal{T}}\times{\mathcal{T}}).$

We thus deduce that
$\lim_{k\to\infty}\mathcal{C}_{\lambda_{n_{k}}}(\gamma^{\lambda_{n_{k}}})=\mathrm{ET}_{c,\lambda}(\mu,\nu)$.
These together with the lower semicontinuity of $\mathcal{C}_{\lambda}$ give

$\displaystyle\mathrm{ET}_{c,\lambda}(\mu,\nu)=\liminf_{k\to\infty}\mathcal{C}_{\lambda_{n_{k}}}(\gamma^{\lambda_{n_{k}}})$
$\displaystyle=\liminf_{k\to\infty}\Big{[}\mathcal{C}_{\lambda}(\gamma^{\lambda_{n_{k}}})+b(\lambda-\lambda_{n_{k}})\gamma^{n_{k}}({\mathcal{T}}\times{\mathcal{T}})\Big{]}$
$\displaystyle=\liminf_{k\to\infty}\mathcal{C}_{\lambda}(\gamma^{\lambda_{n_{k}}})\geq\mathcal{C}_{\lambda}(\tilde{\gamma}^{i}).$

Therefore, $\tilde{\gamma}^{i}\in\Gamma^{0}(\lambda)$ with mass
$b\,\tilde{\gamma}^{i}({\mathcal{T}}\times{\mathcal{T}})=m_{i}$. Due to the
convexity of $\Gamma^{0}(\lambda)$, we have
$\bar{\gamma}:=\sum_{i=1}^{N}t_{i}\tilde{\gamma}^{i}\in\Gamma^{0}(\lambda)$
with
$b\,\bar{\gamma}({\mathcal{T}}\times{\mathcal{T}})=\sum_{i=1}^{N}t_{i}m_{i}=m$.
That is,

$\partial
u(\lambda)\subset\big{\\{}b\,\gamma({\mathcal{T}}\times{\mathcal{T}}):\gamma\in\Gamma^{0}(\lambda)\big{\\}},$

and we thus infer that
$\big{\\{}b\,\gamma({\mathcal{T}}\times{\mathcal{T}}):\gamma\in\Gamma^{0}(\lambda)\big{\\}}=\partial
u(\lambda)$ for all $\lambda\in{\mathbb{R}}$.

In order to prove the second part of i), let
$\gamma\in\Gamma^{0}(\lambda_{1})$ and
$\tilde{\gamma}\in\Gamma^{0}(\lambda_{2})$ be arbitrary. We have

$\displaystyle\mathrm{ET}_{c,\lambda_{2}}(\mu,\nu)=\mathcal{C}_{\lambda_{2}}(\tilde{\gamma})$
$\displaystyle=\mathcal{C}_{\lambda_{1}}(\tilde{\gamma})-b(\lambda_{2}-\lambda_{1})\tilde{\gamma}({\mathcal{T}}\times{\mathcal{T}})$
$\displaystyle\geq\mathrm{ET}_{c,\lambda_{1}}(\mu,\nu)-b(\lambda_{2}-\lambda_{1})\tilde{\gamma}({\mathcal{T}}\times{\mathcal{T}}).$
(11)

Hence by combining with (10), we deduce that

$\displaystyle\mathrm{ET}_{c,\lambda_{1}}(\mu,\nu)-b(\lambda_{2}-\lambda_{1})\tilde{\gamma}({\mathcal{T}}\times{\mathcal{T}})\leq\mathrm{ET}_{c,\lambda_{2}}(\mu,\nu)\leq\mathrm{ET}_{c,\lambda_{1}}(\mu,\nu)-b(\lambda_{2}-\lambda_{1})\gamma({\mathcal{T}}\times{\mathcal{T}}),$

which yields
$\gamma({\mathcal{T}}\times{\mathcal{T}})\leq\tilde{\gamma}({\mathcal{T}}\times{\mathcal{T}})$.
This together with the above characterization of $\partial u(\lambda)$ implies
the second part of i).

ii) If $u$ is differentiable at $\lambda$, then $\partial u(\lambda)$ is a
singleton set. However, as $\partial
u(\lambda)=\big{\\{}b\,\gamma({\mathcal{T}}\times{\mathcal{T}}):\gamma\in\Gamma^{0}(\lambda)\big{\\}}$
by i), we thus infer that the mass $\gamma({\mathcal{T}}\times{\mathcal{T}})$
must be the same for every $\gamma\in\Gamma^{0}(\lambda)$.

Next assume that every element in $\Gamma^{0}(\lambda)$ has the same mass, say
$m$. For $\delta\neq 0$, let
$\gamma^{\lambda+\delta}\in\Gamma^{0}(\lambda+\delta)$ and
$m(\lambda+\delta):=\gamma^{\lambda+\delta}({\mathcal{T}}\times{\mathcal{T}})$.
Then, we claim that

$\lim_{\delta\to 0}m(\lambda+\delta)=m.$ (12)

Assume the claim for the moment, and let $\delta>0$. Then, as in (10)–(A.1),
we have

$\displaystyle\mathrm{ET}_{c,\lambda+\delta}(\mu,\nu)\leq\mathrm{ET}_{c,\lambda}(\mu,\nu)-b\delta
m\quad\mbox{and}\quad\mathrm{ET}_{c,\lambda+\delta}(\mu,\nu)\geq\mathrm{ET}_{c,\lambda}(\mu,\nu)-b\delta
m(\lambda+\delta).$

It follows that

$-bm(\lambda+\delta)\leq\frac{\mathrm{ET}_{c,\lambda+\delta}(\mu,\nu)-\mathrm{ET}_{c,\lambda}(\mu,\nu)}{\delta}\leq-
bm.$

This together with claim (12) gives $\lim_{\delta\to
0^{+}}\frac{\mathrm{ET}_{c,\lambda+\delta}(\mu,\nu)-\mathrm{ET}_{c,\lambda}(\mu,\nu)}{\delta}=-bm$.
By the same argument, we also have $\lim_{\delta\to
0^{-}}\frac{\mathrm{ET}_{c,\lambda+\delta}(\mu,\nu)-\mathrm{ET}_{c,\lambda}(\mu,\nu)}{\delta}=-bm$.
Thus, we infer that $u$ is differentiable at $\lambda$ with
$u^{\prime}(\lambda)=bm$. Therefore, it remains to prove claim (12).

Indeed, by compactness there exists a subsequence, still labeled by
$\gamma^{\lambda+\delta}$, and $\gamma\in\Pi_{\leq}(\mu,\nu)$ such that
$\gamma^{\lambda+\delta}\to\gamma$ weakly as $\delta\to 0$. As in i), we can
show that $\gamma\in\Gamma^{0}(\lambda)$. Then, as the mass functional is
weakly continuous, we obtain
$m(\lambda+\delta)=\gamma^{\lambda+\delta}({\mathcal{T}}\times{\mathcal{T}})\to\gamma({\mathcal{T}}\times{\mathcal{T}})=m$.
We in fact have shown that any subsequence of
$\\{m(\lambda+\delta)\\}_{\delta}$ has a further subsequence converging to the
same number $m$. Therefore, the full sequence
$\\{m(\lambda+\delta)\\}_{\delta}$ must converge to $m$, and hence (12) is
proved.

iii) For any $\lambda\in{\mathbb{R}}$, we have $\partial
u(\lambda)=\big{\\{}b\,\gamma({\mathcal{T}}\times{\mathcal{T}}):\gamma\in\Gamma^{0}(\lambda)\big{\\}}\subset[0,b\,\bar{m}]$.
Thus, we only need to prove $[0,b\,\bar{m}]\subset\partial u({\mathbb{R}})$.
First, note that as $\partial u(\lambda)\subset{\mathbb{R}}$ is a compact and
convex set, it must be a finite and closed interval. Therefore, if we let

$\gamma^{\lambda}_{min}:=\operatorname*{arg\,min}_{\gamma\in\Gamma^{0}(\lambda)}\gamma({\mathcal{T}}\times{\mathcal{T}})\quad\mbox{and}\quad\gamma^{\lambda}_{max}:=\operatorname*{arg\,max}_{\gamma\in\Gamma^{0}(\lambda)}\gamma({\mathcal{T}}\times{\mathcal{T}}),$

then it follows from ii) that $\partial
u(\lambda)=\big{[}b\,\gamma^{\lambda}_{min}({\mathcal{T}}\times{\mathcal{T}}),b\,\gamma^{\lambda}_{max}({\mathcal{T}}\times{\mathcal{T}})\big{]}$
for every $\lambda\in{\mathbb{R}}$. From Equation (4) in the main text, it is
clear that $\partial u(\lambda)=\\{0\\}$ for $\lambda$ negative enough.
Indeed, if we take $\lambda<-M$, then as $w_{1}(x)+w_{2}(y)\leq b\,c(x,y)+M$,
we have $0<b\,c(x,y)-w_{1}(x)-w_{2}(y)-\lambda$ for all $x,y\in{\mathcal{T}}$.
Then, we obtain from Equation (4) in the main text that
$\mathcal{C}_{\lambda}(0)\leq\mathcal{C}_{\lambda}(\gamma)$ for every
$\gamma\in\Pi_{\leq}(\mu,\nu)$ and the strict inequality holds if $\gamma\neq
0$. Thus, $\Gamma^{0}(\lambda)=\\{0\\}$ which gives $\partial
u(\lambda)=\\{0\\}$ and
$u(\lambda)=-\int_{\mathcal{T}}w_{1}\mu(dx)-\int_{\mathcal{T}}w_{2}\nu(dx)$.

We next show that $\partial u(\lambda)=\\{b\,\bar{m}\\}$ for $\lambda$
positive enough. Since $c(x,y)$ is bounded due to its continuity on
${\mathcal{T}}\times{\mathcal{T}}$, we can choose $\lambda\in{\mathbb{R}}$
such that $c(x,y)-\lambda<0$ for all $x,y\in{\mathcal{T}}$. Let
$\gamma\in\Gamma^{0}(\lambda)$. We claim that either $\gamma_{1}=\mu$ or
$\gamma_{2}=\nu$. Indeed, since otherwise we have
$\gamma_{1}(A_{0})<\mu(A_{0})$ and $\gamma_{2}(B_{0})<\nu(B_{0})$ for some
Borel sets $A_{0},B_{0}\subset{\mathcal{T}}$. Let
$\tilde{\gamma}:=\gamma+[(\mu-\gamma_{1})\chi_{A_{0}}]\otimes[(\nu-\gamma_{2})\chi_{B_{0}}]$.
Then, for any Borel set $A\subset{\mathcal{T}}$ we have

$\displaystyle\tilde{\gamma}_{1}(A)=\gamma_{1}(A)+\mu(A\cap
A_{0})-\gamma_{1}(A\cap A_{0})$ $\displaystyle=\gamma_{1}(A\setminus
A_{0})+\mu(A\cap A_{0})$ $\displaystyle\leq\mu(A\setminus A_{0})+\mu(A\cap
A_{0})=\mu(A).$

Likewise, $\tilde{\gamma}_{2}(B)\leq\nu(B)$ for any Borel set
$B\subset{\mathcal{T}}$. Thus $\tilde{\gamma}\in\Pi_{\leq}(\mu,\nu)$. On the
other hand, it is clear from Equation (4) in the main text and the facts
$\gamma_{1}\leq\tilde{\gamma}_{1}$, $\gamma_{2}\leq\tilde{\gamma}_{2}$, and
$c-\lambda<0$ that
$\mathcal{C}_{\lambda}(\tilde{\gamma})<\mathcal{C}_{\lambda}(\gamma)$. This is
impossible and so the claim is proved. That is, either $\gamma_{1}=\mu$ or
$\gamma_{2}=\nu$. It follows that
$\gamma({\mathcal{T}}\times{\mathcal{T}})=\bar{m}$ for every
$\gamma\in\Gamma^{0}(\lambda)$, and hence $\partial
u(\lambda)=\\{b\,\bar{m}\\}$. This also means that $u$ is differentiable at
$\lambda$ with $u^{\prime}(\lambda)=b\,\bar{m}$.

Therefore, it remains to show that

$(0,b\,\bar{m})\subset\partial
u({\mathbb{R}})=\bigcup_{\lambda\in{\mathbb{R}}}\big{[}b\,\gamma^{\lambda}_{min}({\mathcal{T}}\times{\mathcal{T}}),b\,\gamma^{\lambda}_{max}({\mathcal{T}}\times{\mathcal{T}})\big{]}.$
(13)

Assume by contradiction that there exists $m\in(0,b\,\bar{m})$ such that
$m\not\in\partial u(\lambda)$ for every $\lambda\in{\mathbb{R}}$. For
convenience, we adopt the following notation: for sets
$A,B\subset{\mathbb{R}}$ and $r\in{\mathbb{R}}$, we write $A<r$ if $a<r$ for
every $a\in A$, and $A<B$ if $a<b$ for every $a\in A$ and $b\in B$. Let us
consider the following two sets

$S_{1}:=\\{\lambda:\partial u(\lambda)<m\\}\quad\mbox{and}\quad
S_{2}:=\\{\lambda:\partial u(\lambda)>m\\}.$

Then $\lambda\in S_{1}$ if $\lambda$ is negative enough, and $\lambda\in
S_{2}$ if $\lambda$ is positive enough. For any $\lambda_{1}\in S_{1}$ and
$\lambda_{2}\in S_{2}$, we have $\partial u(\lambda_{1})<m<\partial
u(\lambda_{2})$, and hence $\lambda_{1}<\lambda_{2}$ by the monotonicity in
i). That is, $S_{1}<S_{2}$ and so we obtain

$\lambda^{*}:=\sup\\{\lambda:\lambda\in S_{1}\\}\leq\inf\\{\lambda:\lambda\in
S_{2}\\}=:\lambda^{**}.$

If $\lambda^{*}<\lambda^{**}$, then for any
$\lambda\in(\lambda^{*},\lambda^{**})$ we have $\lambda\not\in S_{1}$ and
$\lambda\not\in S_{2}$. Therefore, $\partial u(\lambda)\not<m$ and $\partial
u(\lambda)\not>m$. Hence, we can find $m_{1},m_{2}\in\partial u(\lambda)$ such
that $m_{1}\geq m$ and $m_{2}\leq m$. Thus, $m\in[m_{2},m_{1}]\subset\partial
u(\lambda)$ due to the convexity of the set $\partial u(\lambda)$. This
contradicts our hypothesis, and we conclude that $\lambda^{*}=\lambda^{**}$.

We next select sequences $\\{\lambda^{1}_{n}\\}\subset S_{1}$ and
$\\{\lambda^{2}_{n}\\}\subset S_{2}$ such that $\lambda^{1}_{n}\to\lambda^{*}$
and $\lambda^{2}_{n}\to\lambda^{**}=\lambda^{*}$. For each $n$, let

$\gamma^{n}_{min}:=\operatorname*{arg\,min}_{\gamma\in\Gamma^{0}(\lambda^{1}_{n})}\gamma({\mathcal{T}}\times{\mathcal{T}})\quad\mbox{and}\quad\gamma^{n}_{max}:=\operatorname*{arg\,max}_{\gamma\in\Gamma^{0}(\lambda^{2}_{n})}\gamma({\mathcal{T}}\times{\mathcal{T}}).$

By compactness, there exist subsequences, still labeled as
$\\{\gamma^{n}_{min}\\}$ and $\\{\gamma^{n}_{max}\\}$, and
$\gamma^{*},\gamma^{**}\in\Pi_{\leq}(\mu,\nu)$ such that
$\gamma^{n}_{min}\to\gamma^{*}$ weakly and $\gamma^{n}_{max}\to\gamma^{**}$
weakly. By arguing exactly as in i), we then obtain
$\gamma^{*},\gamma^{**}\in\Gamma^{0}(\lambda^{*})$,
$\gamma^{n}_{min}({\mathcal{T}}\times{\mathcal{T}})\to\gamma^{*}({\mathcal{T}}\times{\mathcal{T}})$,
and
$\gamma^{n}_{max}({\mathcal{T}}\times{\mathcal{T}})\to\gamma^{**}({\mathcal{T}}\times{\mathcal{T}})$.
As $b\,\gamma^{n}_{min}({\mathcal{T}}\times{\mathcal{T}})<m$ due to
$\lambda^{1}_{n}\in S_{1}$, we must have
$b\,\gamma^{*}({\mathcal{T}}\times{\mathcal{T}})\leq m$. Likewise, we have
$b\,\gamma^{**}({\mathcal{T}}\times{\mathcal{T}})\geq m$ as
$b\,\gamma^{n}_{max}({\mathcal{T}}\times{\mathcal{T}})>m$ for all $n$. Hence,
$m\in[b\,\gamma^{*}({\mathcal{T}}\times{\mathcal{T}}),b\,\gamma^{**}({\mathcal{T}}\times{\mathcal{T}})]$.
Since $\gamma^{*},\gamma^{**}\in\Gamma^{0}(\lambda^{*})$, we infer that
$m\in\partial u(\lambda^{*})$. This is a contradiction and the proof is
complete. We note that since
$\lambda^{1}_{n}\leq\lambda^{*}\leq\lambda^{2}_{n}$, we have from the
monotonicity in i) that

$\gamma^{n}_{min}({\mathcal{T}}\times{\mathcal{T}})\leq\gamma({\mathcal{T}}\times{\mathcal{T}})\leq\gamma^{n}_{max}({\mathcal{T}}\times{\mathcal{T}})$

for every $\gamma\in\Gamma^{0}(\lambda^{*})$. By sending $n$ to infinity, it
follows that
$\gamma^{*}({\mathcal{T}}\times{\mathcal{T}})\leq\gamma({\mathcal{T}}\times{\mathcal{T}})\leq\gamma^{**}({\mathcal{T}}\times{\mathcal{T}})$
for every $\gamma\in\Gamma^{0}(\lambda^{*})$. That is,
$\gamma^{*}=\gamma^{\lambda^{*}}_{min}$ and
$\gamma^{**}=\gamma^{\lambda^{*}}_{max}$. ∎

###  A.2 Proof for Lemma 3.2 in the main text

###### Proof.

We first observe for any Borel set $A\subset{\mathcal{T}}$ that

$\displaystyle\hat{\gamma}(A\times\\{\hat{s}\\})=\hat{\gamma}(A\times\hat{\mathcal{T}})-\hat{\gamma}(A\times{\mathcal{T}})=\hat{\mu}(A)-\gamma(A\times{\mathcal{T}})=\mu(A)-\gamma_{1}(A)=\int_{A}(1-f_{1})\mu(dx).$

For the same reason, we have $\hat{\gamma}(\\{\hat{s}\\}\times
B)=\int_{B}(1-f_{2})\nu(dx)$ for any set Borel set $B\subset{\mathcal{T}}$.
Also,

$\displaystyle\hat{\gamma}(\\{\hat{s}\\}\times\\{\hat{s}\\})$
$\displaystyle=\hat{\gamma}(\hat{\mathcal{T}}\times\\{\hat{s}\\})-\hat{\gamma}({\mathcal{T}}\times\\{\hat{s}\\})$
$\displaystyle=\hat{\gamma}(\hat{\mathcal{T}}\times\hat{\mathcal{T}})-\hat{\gamma}(\hat{\mathcal{T}}\times{\mathcal{T}})-\big{[}\hat{\gamma}({\mathcal{T}}\times\hat{\mathcal{T}})-\hat{\gamma}({\mathcal{T}}\times{\mathcal{T}})\big{]}$
$\displaystyle=\hat{\mu}(\hat{\mathcal{T}})-\hat{\nu}({\mathcal{T}})-\hat{\mu}({\mathcal{T}})+\gamma({\mathcal{T}}\times{\mathcal{T}})=\gamma({\mathcal{T}}\times{\mathcal{T}}).$

Since the Equation (6) in the main text is obviously true for sets of the form
$A\times B$ with $A,B\subset{\mathcal{T}}$ being Borel sets, we only need to
verify it for sets of the following forms: $(A\cup\\{\hat{s}\\})\times B$,
$A\times(B\cup\\{\hat{s}\\})$,
$(A\cup\\{\hat{s}\\})\times(B\cup\\{\hat{s}\\})$ for Borel sets
$A,B\subset{\mathcal{T}}$. We check it case by case as follows.

Case 1: Using the above observation, we have

$\displaystyle\hat{\gamma}((A\cup\\{\hat{s}\\})\times B)$
$\displaystyle=\hat{\gamma}(A\times B)+\hat{\gamma}(\\{\hat{s}\\}\times
B)=\gamma(A\times B)+\int_{B}(1-f_{2})\nu(dx).$

Therefore, the Equation (6) in the main text holds in this case.

Case 2: the Equation (6) in the main text is also true for this case because

$\displaystyle\hat{\gamma}(A\times(B\cup\\{\hat{s}\\}))$
$\displaystyle=\hat{\gamma}(A\times
B)+\hat{\gamma}(A\times\\{\hat{s}\\})=\gamma(A\times
B)+\int_{A}(1-f_{1})\mu(dx).$

Case 3: the Equation (6) in the main text is true as well since

$\displaystyle\hat{\gamma}((A\cup\\{\hat{s}\\})\times(B\cup\\{\hat{s}\\}))$
$\displaystyle=\hat{\gamma}(A\times
B)+\hat{\gamma}(A\times\\{\hat{s}\\})+\hat{\gamma}(\\{\hat{s}\\}\times
B)+\hat{\gamma}(\\{\hat{s}\\}\times\\{\hat{s}\\})$
$\displaystyle=\gamma(A\times
B)+\int_{A}(1-f_{1})\mu(dx)+\int_{B}(1-f_{2})\nu(dx)+\gamma({\mathcal{T}}\times{\mathcal{T}}).$

Now as the Equation (6) in the main text holds, we obviously have
$\gamma(U\times{\mathcal{T}})\leq\hat{\gamma}(U\times{\mathcal{T}})\leq\hat{\gamma}(U\times\hat{\mathcal{T}})=\hat{\mu}(U)=\mu(U)$
for any Borel set $U\subset{\mathcal{T}}$. Likewise,
$\gamma({\mathcal{T}}\times U)\leq\nu(U)$ for any Borel set
$U\subset{\mathcal{T}}$. Therefore, $\gamma\in\Pi_{\leq}(\mu,\nu)$. ∎

###  A.3 Proof for Proposition 3.3 in the main text

###### Proof.

We first show that
$\mathrm{KT}(\hat{\mu},\hat{\nu})\leq\mathrm{ET}_{c,\lambda}(\mu,\nu)$.

For any $\gamma\in\Pi_{\leq}(\mu,\nu)$, let $\hat{\gamma}$ be given by the
Equation (6) in the main text. Then,
$\hat{\gamma}\in\Gamma(\hat{\mu},\hat{\nu})$ and

$\displaystyle\mathrm{KT}(\hat{\mu},\hat{\nu})\leq\int_{\hat{\mathcal{T}}\times\hat{\mathcal{T}}}\hat{c}(x,y)\hat{\gamma}(dx,dy)$
$\displaystyle=b\int_{{\mathcal{T}}\times{\mathcal{T}}}[c(x,y)-\lambda]\gamma(dx,dy)$
$\displaystyle\quad+\int_{\mathcal{T}}w_{1}[1-f_{1}(x)]\mu(dx)+\int_{\mathcal{T}}w_{2}[1-f_{2}(x)]\nu(dx).$

It follows that
$\mathrm{KT}(\hat{\mu},\hat{\nu})\leq\mathrm{ET}_{c,\lambda}(\mu,\nu)$.

We next show that
$\mathrm{KT}(\hat{\mu},\hat{\nu})\geq\mathrm{ET}_{c,\lambda}(\mu,\nu)$. To see
this, for any $\hat{\gamma}\in\Gamma(\hat{\mu},\hat{\nu})$ we let $\gamma$ be
the restriction of $\hat{\gamma}$ to ${\mathcal{T}}$. Then by Lemma 3.2 in the
main text, we have $\gamma\in\Pi_{\leq}(\mu,\nu)$ and the Equation (6) in the
main text holds. Consequently,

$\displaystyle\int_{\hat{\mathcal{T}}\times\hat{\mathcal{T}}}\hat{c}(x,y)\hat{\gamma}(dx,dy)$
$\displaystyle=b\int_{{\mathcal{T}}\times{\mathcal{T}}}[c(x,y)-\lambda]\gamma(dx,dy)$
$\displaystyle\quad+\int_{\mathcal{T}}w_{1}[1-f_{1}(x)]\mu(dx)+\int_{\mathcal{T}}w_{2}[1-f_{2}(x)]\nu(dx)$
$\displaystyle\geq\mathrm{ET}_{c,\lambda}(\mu,\nu).$

By taking the infimum over $\hat{\gamma}$, we infer that
$\mathrm{KT}(\hat{\mu},\hat{\nu})\geq\mathrm{ET}_{c,\lambda}(\mu,\nu)$.

Thus we obtain

$\mathrm{KT}(\hat{\mu},\hat{\nu})=\mathrm{ET}_{c,\lambda}(\mu,\nu).$

The relation about the optimal solutions also follows from the above
arguments. ∎

###  A.4 Proof for Theorem 3.4 in the main text

###### Proof.

From Proposition 3.3 in the main text and the dual formulation for
$\mathrm{KT}(\hat{\mu},\hat{\nu})$ proved in [10, Corollary 2.6], we have

$\displaystyle\mathrm{ET}_{c,\lambda}(\mu,\nu)=\sup_{\begin{subarray}{c}\hat{u}\in
L^{1}(\hat{\mu}),\,\hat{v}\in L^{1}(\hat{\nu})\\\
\hat{u}(x)+\hat{v}(y)\leq\hat{c}(x,y)\end{subarray}}\int_{\hat{\mathcal{T}}}\hat{u}(x)\hat{\mu}(dx)+\int_{\hat{\mathcal{T}}}\hat{v}(x)\hat{\nu}(dx)=:I.$

Therefore, it is enough to prove that $I=J$ where

$J:=\sup_{(u,v)\in{\mathbb{K}}}\Big{[}\int_{{\mathcal{T}}}u(x)\mu(dx)+\int_{{\mathcal{T}}}v(x)\nu(dx)\Big{]}.$

For $(u,v)$ satisfying $u\leq w_{1}$, $v\leq w_{2}$ and $u(x)+v(y)\leq
b[c(x,y)-\lambda]$, we extend it to $\hat{\mathcal{T}}$ by taking
$\hat{u}(\hat{s})=0$ and $\hat{v}(\hat{s})=0$. Then, it is clear that
$\hat{u}(x)+\hat{v}(y)\leq\hat{c}(x,y)$ for $x,y\in\hat{\mathcal{T}}$, and

$\displaystyle
I\geq\int_{\hat{\mathcal{T}}}\hat{u}(x)\hat{\mu}(dx)+\int_{\hat{\mathcal{T}}}\hat{v}(x)\hat{\nu}(dx)=\int_{{\mathcal{T}}}u(x)\mu(dx)+\int_{{\mathcal{T}}}v(x)\nu(dx).$

It follows that $I\geq J$. In order to prove the converse, let
$(\hat{u},\hat{v})$ be a maximizer for $I$. Then, by considering
$(\hat{u}-\hat{u}(\hat{s}),\hat{v}+\hat{u}(\hat{s}))$, we can assume that
$\hat{u}(\hat{s})=0$. Also, if we let
$v(y):=\inf_{x\in\hat{\mathcal{T}}}[\hat{c}(x,y)-\hat{u}(x)]$, then
$(\hat{u},v)$ is still in the admissible class for $I$ and $\hat{v}(y)\leq
v(y)$. This implies that $(\hat{u},v)$ is also a maximizer for $I$. For these
reasons, we can assume w.l.g. that the maximizer $(\hat{u},\hat{v})$ has the
following additional properties: $\hat{u}(\hat{s})=0$ and

$\hat{v}(y)=\inf_{x\in\hat{\mathcal{T}}}[\hat{c}(x,y)-\hat{u}(x)]\quad\forall
y\in\hat{\mathcal{T}}.$

In particular,
$\hat{v}(\hat{s})=\inf_{x\in\hat{\mathcal{T}}}[\hat{c}(x,\hat{s})-\hat{u}(x)]$.
For convenience, define $w_{1}(\hat{s})=0$ and consider the following two
possibilities.

Case 1: $\inf_{x\in\hat{\mathcal{T}}}[w_{1}(x)-\hat{u}(x)]\geq 0$. Then, since
$\hat{c}(\hat{s},\hat{s})-\hat{u}(\hat{s})=0$ and
$\inf_{x\in{\mathcal{T}}}[\hat{c}(x,\hat{s})-\hat{u}(x)]=\inf_{x\in{\mathcal{T}}}[w_{1}(x)-\hat{u}(x)]\geq
0$, we have $\hat{v}(\hat{s})=0$. Also,
$\hat{v}(y)\leq\hat{c}(\hat{s},y)-\hat{u}(\hat{s})\leq w_{2}(y)$ for all
$y\in\hat{\mathcal{T}}$. For each $y\in{\mathcal{T}}$, by using the facts
$\hat{u}\leq w_{1}$ and $\hat{c}(\hat{s},y)-w_{1}(\hat{s})=w_{2}(y)\geq 0$ we
get

$\displaystyle\hat{v}(y)\geq\inf_{x\in\hat{\mathcal{T}}}[\hat{c}(x,y)-w_{1}(x)]=\inf_{x\in{\mathcal{T}}}\\{b[c(x,y)-\lambda]-w_{1}(x)\\}=-b\lambda+\inf_{x\in{\mathcal{T}}}[b\,c(x,y)-w_{1}(x)].$

Thus $(\hat{u},\hat{v})\in{\mathbb{K}}$ and

$\displaystyle
I=\int_{\hat{\mathcal{T}}}\hat{u}(x)\hat{\mu}(dx)+\int_{\hat{\mathcal{T}}}\hat{v}(x)\hat{\nu}(dx)$
$\displaystyle=\int_{{\mathcal{T}}}\hat{u}(x)\hat{\mu}(dx)+\int_{{\mathcal{T}}}\hat{v}(x)\hat{\nu}(dx)+\hat{v}(\hat{s})\mu({\mathcal{T}})$
$\displaystyle=\int_{{\mathcal{T}}}\hat{u}(x)\mu(dx)+\int_{{\mathcal{T}}}\hat{v}(x)\nu(dx)\leq
J.$

Case 2: $\inf_{x\in\hat{\mathcal{T}}}[w_{1}(x)-\hat{u}(x)]<0$. Then, by
arguing as in Case 1, we have
$\hat{v}(\hat{s})=\inf_{x\in{\mathcal{T}}}[w_{1}(x)-\hat{u}(x)]<0$ and

$\displaystyle
I=\int_{{\mathcal{T}}}\hat{v}(x)\nu(dx)+\int_{{\mathcal{T}}}\hat{u}(x)\mu(dx)+\mu({\mathcal{T}})\inf_{{\mathcal{T}}}[w_{1}-\hat{u}].$
(14)

Let $\tilde{u}(x):=\min\\{\hat{u}(x),w_{1}(x)\\}$. Then, it is obvious that
$\tilde{u}(x)+\hat{v}(y)\leq\hat{c}(x,y)$ and $\tilde{u}(\hat{s})=0$. Since
$\inf_{x\in{\mathcal{T}}}[w_{1}(x)-\hat{u}(x)]<0$, there exists
$x_{0}\in{\mathcal{T}}$ such that $w_{1}(x_{0})<\hat{u}(x_{0})$. Thus,
$\tilde{u}(x_{0})=w_{1}(x_{0})$ and hence
$\inf_{{\mathcal{T}}}[w_{1}-\tilde{u}]\leq 0$. As $\tilde{u}\leq w_{1}$, we
infer further that $\inf_{{\mathcal{T}}}[w_{1}-\tilde{u}]=0$. We also have

$\displaystyle\int_{{\mathcal{T}}}\hat{u}(x)\mu(dx)+\mu({\mathcal{T}})\inf_{{\mathcal{T}}}[w_{1}-\hat{u}]$
$\displaystyle=\int_{{\mathcal{T}}}\tilde{u}(x)\mu(dx)+\int_{{\mathcal{T}}:\hat{u}>w_{1}}[\hat{u}(x)-w_{1}(x)]\mu(dx)+\mu({\mathcal{T}})\inf_{{\mathcal{T}}}[w_{1}-\hat{u}]\leq\int_{{\mathcal{T}}}\tilde{u}(x)\mu(dx).$

This together with (14) gives

$\displaystyle
I\leq\int_{{\mathcal{T}}}\tilde{u}(x)\mu(dx)+\int_{{\mathcal{T}}}\hat{v}(x)\nu(dx).$

Now let $\tilde{v}(y)=\inf_{x\in\hat{\mathcal{T}}}[\hat{c}(x,y)-\tilde{u}(x)]$
for $y\in{\mathcal{T}}$. Then,
$\hat{v}(y)\leq\tilde{v}(y)\leq\hat{c}(\hat{s},y)-\tilde{u}(\hat{s})=w_{2}(y)$
for $y\in{\mathcal{T}}$. For each $y\in{\mathcal{T}}$, by using the facts
$\tilde{u}\leq w_{1}$ and $\hat{c}(\hat{s},y)-w_{1}(\hat{s})=w_{2}(y)\geq 0$
we also get

$\displaystyle\tilde{v}(y)\geq\inf_{x\in\hat{\mathcal{T}}}[\hat{c}(x,y)-w_{1}(x)]=\inf_{x\in{\mathcal{T}}}\\{b[c(x,y)-\lambda]-w_{1}(x)\\}=-b\lambda+\inf_{x\in{\mathcal{T}}}[b\,c(x,y)-w_{1}(x)].$

It follows that $(\tilde{u},\tilde{v})\in{\mathbb{K}}$ and

$\displaystyle
I\leq\int_{{\mathcal{T}}}\tilde{u}(x)\mu(dx)+\int_{{\mathcal{T}}}\tilde{v}(x)\nu(dx)\leq
J.$

Thus we conclude that $I=J$ and the theorem follows. ∎

###  A.5 Proof for Corollary 3.5 in the main text

###### Proof.

Notice that as $w_{i}$ ($i=1,2$) is $b$-Lipschitz, we have for every
$x\in{\mathcal{T}}$ that

$-w_{i}(x)\leq\inf_{y\in{\mathcal{T}}}\big{[}b\,d_{\mathcal{T}}(x,y)-w_{i}(y)\big{]}.$
(15)

For each $(u,v)\in{\mathbb{K}}$, let

$\displaystyle v^{*}(x)$
$\displaystyle:=\inf_{y\in{\mathcal{T}}}\big{\\{}b[d_{\mathcal{T}}(x,y)-\lambda]-v(y)\big{\\}}=-b\lambda+\inf_{y\in{\mathcal{T}}}\big{[}b\,d_{\mathcal{T}}(x,y)-v(y)\big{]}\geq
u(x),$ $\displaystyle v^{**}(y)$
$\displaystyle:=\inf_{x\in{\mathcal{T}}}\big{\\{}b[d_{\mathcal{T}}(x,y)-\lambda]-v^{*}(x)\big{\\}}=-b\lambda+\inf_{x\in{\mathcal{T}}}\big{[}b\,d_{\mathcal{T}}(x,y)-v^{*}(x)\big{]}\geq
v(y).$

By using
$-b\lambda+\inf_{x\in{\mathcal{T}}}[b\,d_{\mathcal{T}}(x,y)-w_{1}(x)]\leq
v(y)\leq w_{2}(y)$ and (15), we obtain for every $x\in{\mathcal{T}}$ that

$\displaystyle v^{*}(x)$
$\displaystyle\leq-b\lambda-v(x)\leq-\inf_{y\in{\mathcal{T}}}[b\,d_{\mathcal{T}}(x,y)-w_{1}(y)]\leq
w_{1}(x),$ $\displaystyle v^{*}(x)$
$\displaystyle\geq-b\lambda+\inf_{y\in{\mathcal{T}}}\big{[}b\,d_{\mathcal{T}}(x,y)-w_{2}(y)\big{]}\geq-b\lambda-
w_{2}(x).$

We also have $v^{*}$ is $b$-Lipschitz, i.e., $|v^{*}(x_{1})-v^{*}(x_{2})|\leq
b\,d_{\mathcal{T}}(x_{1},x_{2})$. Indeed, let $x_{1},x_{2}\in{\mathcal{T}}$.
Then for any $\varepsilon>0$, there exists $y_{1}\in{\mathcal{T}}$ such that
$b\,d_{\mathcal{T}}(x_{1},y_{1})-v(y_{1})<v^{*}(x_{1})+b\lambda+\varepsilon$.
It follows that

$v^{*}(x_{2})-v^{*}(x_{1})\leq
b\,d_{\mathcal{T}}(x_{2},y_{1})-v(y_{1})+\varepsilon-[b\,d_{\mathcal{T}}(x_{1},y_{1})-v(y_{1})]\leq
b\,d_{\mathcal{T}}(x_{1},x_{2})+\varepsilon.$

Since this holds for every $\varepsilon>0$, we get
$v^{*}(x_{2})-v^{*}(x_{1})\leq b\,d_{\mathcal{T}}(x_{1},x_{2})$. By
interchanging the role of $x_{1}$ and $x_{2}$, we also obtain
$v^{*}(x_{1})-v^{*}(x_{2})\leq b\,d_{\mathcal{T}}(x_{1},x_{2})$. Thus,
$|v^{*}(x_{1})-v^{*}(x_{2})|\leq b\,d_{\mathcal{T}}(x_{1},x_{2})$. Hence, we
have shown that $v^{*}\in\mathbb{L^{\prime}}$ with

$\mathbb{L^{\prime}}:=\Big{\\{}f\in C({\mathcal{T}}):\,-b\lambda-w_{2}\leq
f\leq w_{1},\,|f(x)-f(y)|\leq b\,d_{\mathcal{T}}(x,y)\Big{\\}}.$

We next claim $v^{**}=-b\lambda-v^{*}$. For this, it is clear from the
definition that $v^{**}(y)\leq-b\lambda-v^{*}(y)$. On the other hand, from the
Lipschitz property of $v^{*}$ we obtain

$-v^{*}(y)\leq b\,d_{\mathcal{T}}(x,y)-v^{*}(x)\quad\forall
x\in{\mathcal{T}},$

which gives $-b\lambda-v^{*}(y)\leq v^{**}(y)$. Thus, we conclude that
$v^{**}=-b\lambda-v^{*}$ as claimed.

From these, we obtain that

$\displaystyle\int_{{\mathcal{T}}}u(x)\mu(dx)+\int_{{\mathcal{T}}}v(x)\nu(dx)$
$\displaystyle\leq\int_{{\mathcal{T}}}v^{*}(x)\mu(dx)+\int_{{\mathcal{T}}}v^{**}(x)\nu(dx)$
$\displaystyle=\int_{{\mathcal{T}}}v^{*}(x)\mu(dx)-\int_{{\mathcal{T}}}v^{*}(x)\nu(dx)-b\lambda\nu({\mathcal{T}})$
$\displaystyle\leq-b\lambda\nu({\mathcal{T}})+\sup\left\\{\int_{\mathcal{T}}f(\mu-\nu):\,f\in\mathbb{L^{\prime}}\right\\}.$

This together with Theorem 3.4 in the main text implies that
$\mathrm{ET}_{\lambda}(\mu,\nu)\leq-b\lambda\nu({\mathcal{T}})+\sup\left\\{\int_{\mathcal{T}}f(\mu-\nu):\,f\in\mathbb{L^{\prime}}\right\\}$.
To prove the converse, let $f\in\mathbb{L^{\prime}}$. Define $u:=f$ and
$v:=-b\lambda-f$. Then, we have $u(x)\leq w_{1}(x)$,
$v(x)\leq-b\lambda-[-b\lambda-w_{2}(x)]=w_{2}(x)$, and

$v(x)\geq-b\lambda-
w_{1}(x)\geq-b\lambda+\inf_{y\in{\mathcal{T}}}[b\,d_{\mathcal{T}}(x,y)-w_{1}(y)].$

Also, the Lipschitz property of $f$ gives

$u(x)+v(y)=-b\lambda+f(x)-f(y)\leq b[d_{\mathcal{T}}(x,y)-\lambda]\quad\forall
x,y\in{\mathcal{T}}.$

Thus $(u,v)\in{\mathbb{K}}$, and hence we obtain from Theorem 3.4 in the main
text that

$\displaystyle-b\lambda\nu({\mathcal{T}})+\int_{\mathcal{T}}f(\mu-\nu)=\int_{{\mathcal{T}}}u(x)\mu(dx)+\int_{{\mathcal{T}}}v(x)\nu(dx)\leq\mathrm{ET}_{\lambda}(\mu,\nu).$

As this holds for every $f\in\mathbb{L^{\prime}}$, we get

$-b\lambda\nu({\mathcal{T}})+\sup\left\\{\int_{\mathcal{T}}f(\mu-\nu):\,f\in\mathbb{L^{\prime}}\right\\}\leq\mathrm{ET}_{\lambda}(\mu,\nu).$

Thus, we have shown that

$\mathrm{ET}_{\lambda}(\mu,\nu)=-b\lambda\nu({\mathcal{T}})+\sup\left\\{\int_{\mathcal{T}}f(\mu-\nu):\,f\in\mathbb{L^{\prime}}\right\\}.$
(16)

Now consider $f=\tilde{f}-\frac{b\lambda}{2}$. Then, $f\in\mathbb{L^{\prime}}$
if and only if $\tilde{f}\in\mathbb{L}$. Moreover,

$\int_{\mathcal{T}}f(\mu-\nu)=-\frac{b\lambda}{2}\big{[}\mu({\mathcal{T}})-\nu({\mathcal{T}})\big{]}+\int_{\mathcal{T}}\tilde{f}(\mu-\nu).$

Therefore, the conclusion of the corollary follows from (16). ∎

###  A.6 Proof for Proposition 3.7 in the main text

In order to prove Proposition 3.7 in the main text, we need the following
auxiliary result.

######  Lemma A.1.

Assume that $w_{1}>0$ and $w_{2}>0$. Then, $d(\mu,\nu)=0$ implies that
$\mu=\nu$.

###### Proof.

Assume that $d(\mu,\nu)=0$. Let $\gamma^{0}$ be an optimal plan for
$\mathrm{ET}_{\lambda}(\mu,\nu)$, and set
$m:=\gamma^{0}({\mathcal{T}}\times{\mathcal{T}})$. Then,
$m\leq\min\\{\mu({\mathcal{T}}),\nu({\mathcal{T}})\\}$, and hence we obtain
from Problem (3) in the main text that

$\displaystyle\int_{\mathcal{T}}w_{1}[1-f_{1}(x)]\mu(dx)+\int_{\mathcal{T}}w_{2}[1-f_{2}(x)]\nu(dx)+b\,\int_{{\mathcal{T}}\times{\mathcal{T}}}d_{\mathcal{T}}(x,y)\gamma^{0}(dx,dy)$
$\displaystyle=\mathrm{ET}_{\lambda}(\mu,\nu)+\lambda
bm\leq\mathrm{ET}_{\lambda}(\mu,\nu)+\frac{b\lambda}{2}\big{[}\mu({\mathcal{T}})+\nu({\mathcal{T}})\big{]}=d(\mu,\nu)=0.$

Thus,

$\displaystyle\int_{\mathcal{T}}w_{1}[1-f_{1}(x)]\mu(dx)=\int_{\mathcal{T}}w_{2}[1-f_{2}(x)]\nu(dx)=\int_{{\mathcal{T}}\times{\mathcal{T}}}d_{\mathcal{T}}(x,y)\gamma^{0}(dx,dy)=0.$

Since $w_{1}$ and $w_{2}$ are positive, it follows in particular that
$f_{1}=1$ $\mu$-a.e. and $f_{2}=1$ $\nu$-a.e. That is, $\gamma^{0}_{1}=\mu$
and $\gamma^{0}_{2}=\nu$. Moreover, the above last identity implies that
$\gamma^{0}$ is supported on the diagonal $(y=x)$. Therefore, for any
continuous function $\varphi$ on ${\mathcal{T}}$ we have

$\int_{\mathcal{T}}\varphi(x)\mu(dx)=\int_{{\mathcal{T}}\times{\mathcal{T}}}\varphi(x)\gamma^{0}(dx,dy)=\int_{{\mathcal{T}}\times{\mathcal{T}}}\varphi(y)\gamma^{0}(dx,dy)=\int_{\mathcal{T}}\varphi(y)\nu(dy).$

We thus conclude that $\mu=\nu$. ∎

###### Proof.

[Of Proposition 3.7 in the main text]

i) This follows immediately from Corollary 3.5 in the main text.

ii) By Corollary 3.5 in the main text, it is clear that $d(\mu,\nu)\geq 0$ and
$d(\mu,\mu)=0$. Also, if $d(\mu,\nu)=0$, then by Lemma A.1, we have $\mu=\nu$.
It is obvious that $d$ satisfies the triangle inequality.

iii) Due to the assumption $w_{1}=w_{2}$ we have $f\in\mathbb{L}$ if and only
if $-f\in\mathbb{L}$. It follows that $d(\mu,\nu)=d(\nu,\mu)$. This together
with ii) implies that $({\mathcal{M}}({\mathcal{T}}),d)$ is a metric space.
Its completeness follows from [56, Proposition 4]. As a complete metric space,
it is well known that $({\mathcal{M}}({\mathcal{T}}),d)$ is a geodesic space
if and only if for every $\mu,\nu\in{\mathcal{M}}({\mathcal{T}})$ there exists
$\sigma\in{\mathcal{M}}({\mathcal{T}})$ such that

$d(\mu,\sigma)=d(\nu,\sigma)=\frac{1}{2}d(\mu,\nu).$

To verify the latter, take $\sigma:=\frac{\mu+\nu}{2}$. Then using Corollary
3.5 in the main text, we obtain

$d(\mu,\sigma)=\frac{1}{2}\sup_{f\in\mathbb{L}}\int_{\mathcal{T}}f(\mu-\nu)=\frac{1}{2}d(\mu,\nu)$

and

$d(\nu,\sigma)=\frac{1}{2}\sup_{f\in\mathbb{L}}\int_{\mathcal{T}}f(\nu-\mu)=\frac{1}{2}d(\nu,\mu)=\frac{1}{2}d(\mu,\nu).$

∎

###  A.7 Proof for Proposition 3.8 in the main text

###### Proof.

Observe that

$\displaystyle\widetilde{\mathrm{ET}}_{\lambda}^{\alpha}(\mu,\nu)$
$\displaystyle=-\frac{b\lambda}{2}\big{[}\mu({\mathcal{T}})+\nu({\mathcal{T}})\big{]}$
$\displaystyle\quad+\sup\Big{\\{}s[\mu({\mathcal{T}})-\nu({\mathcal{T}})]:\,s\in\big{[}-\frac{b\lambda}{2}-w_{2}(r)+\alpha,w_{1}(r)+\frac{b\lambda}{2}-\alpha\big{]}\Big{\\}}$
$\displaystyle\quad+\sup\left\\{\int_{\mathcal{T}}\Big{[}\int_{[r,x]}g(y)\omega(dy\Big{]}(\mu-\nu)(dx):\,\|g\|_{L^{\infty}({\mathcal{T}})}\leq
b\right\\}.$

The first supremum equals to
$[w_{1}(r)+\frac{b\lambda}{2}-\alpha][\mu({\mathcal{T}})-\nu({\mathcal{T}})]$
if $\mu({\mathcal{T}})\geq\nu({\mathcal{T}})$ and equals to
$-[w_{2}(r)+\frac{b\lambda}{2}-\alpha][\mu({\mathcal{T}})-\nu({\mathcal{T}})]$
if $\mu({\mathcal{T}})<\nu({\mathcal{T}})$. On the other hand, by the same
arguments as in [18, p.575-576], we see that the second supremum equals to
$\int_{{\mathcal{T}}}|\mu(\Lambda(x))-\nu(\Lambda(x))|\,\omega(dx)$. Putting
them together, we obtain the desired formula for
$\widetilde{\mathrm{ET}}_{\lambda}^{\alpha}(\mu,\nu)$. ∎

###  A.8 Proof for Proposition 3.9 in the main text

###### Proof.

The inequality
$\mathrm{ET}_{\lambda}(\mu,\nu)\leq\widetilde{\mathrm{ET}}_{\lambda}^{0}(\mu,\nu)$
holds due to $\mathbb{L}\subset\mathbb{L}_{0}$ and Corollary 3.5 in the main
text. Next, let

$2bL({\mathcal{T}})\leq\alpha\leq\frac{1}{2}[b\lambda+w_{1}(r)+w_{2}(r)].$

Then, thanks to Corollary 3.5 in the main text, the stated lower bound will
follow if $\mathbb{L}_{\alpha}\subset\mathbb{L}$. This is achieved if we can
show that any $f\in\mathbb{L}_{\alpha}$ satisfies
$-w_{2}-\frac{b\lambda}{2}\leq f\leq w_{1}+\frac{b\lambda}{2}$. Indeed, for
such function $f$ we have

$f(x)=s+\int_{[r,x]}g(y)\omega(dy),$

with
$s\in\big{[}-w_{2}(r)-\frac{b\lambda}{2}+\alpha,w_{1}(r)+\frac{b\lambda}{2}-\alpha\big{]}$
and $\|g\|_{L^{\infty}({\mathcal{T}})}\leq b$. This together the $b$-Lipschitz
property of $w_{1},w_{2}$ gives for every $x\in{\mathcal{T}}$ that

$f(x)\leq s+\|g\|_{L^{\infty}({\mathcal{T}})}\omega([r,x])\leq
w_{1}(r)+\frac{b\lambda}{2}-\alpha+bL({\mathcal{T}})\leq
w_{1}(x)+\frac{b\lambda}{2}-\alpha+2bL({\mathcal{T}})\leq
w_{1}(x)+\frac{b\lambda}{2}$

and

$\displaystyle f(x)$ $\displaystyle\geq
s-\|g\|_{L^{\infty}({\mathcal{T}})}\omega([r,x])\geq-
w_{2}(r)-\frac{b\lambda}{2}+\alpha-bL({\mathcal{T}})$ $\displaystyle\geq-
w_{2}(x)-\frac{b\lambda}{2}+\alpha-2bL({\mathcal{T}})\geq-
w_{2}(x)-\frac{b\lambda}{2}.$

It follows that $f\in\mathbb{L}$. Thus, $\mathbb{L}_{\alpha}\subset\mathbb{L}$
and we obtain

$\widetilde{\mathrm{ET}}_{\lambda}^{\alpha}(\mu,\nu)\leq\mathrm{ET}_{\lambda}(\mu,\nu).$

∎

###  A.9 Proof of Proposition 3.10 in the main text

We begin with the following auxiliary result.

######  Lemma A.2.

Let $\mu,\nu\in{\mathcal{M}}({\mathcal{T}})$. Then, $\mu=\nu$ if and only if
$\mu(\Lambda(x))=\nu(\Lambda(x))$ for every $x$ in ${\mathcal{T}}$.

###### Proof.

It is obvious that $\mu=\nu$ implies that $\mu(\Lambda(x))=\nu(\Lambda(x))$
for every $x$ in ${\mathcal{T}}$. Now assume that
$\mu(\Lambda(x))=\nu(\Lambda(x))$ for every $x$ in ${\mathcal{T}}$. We first
claim that $\mu(\\{a\\})=\nu(\\{a\\})$ for any $a\in{\mathcal{T}}$. Indeed, if
$a$ is not a node then we have
$\Lambda(a)\setminus\Lambda(a_{n})\downarrow\\{a\\}$, where
$\\{a_{n}\\}_{n=1}^{\infty}$ is a sequence of distinct points on the same edge
as $a$ and converges to $a$ from below. Hence,

$\mu(\\{a\\})=\lim_{n\to\infty}\big{[}\mu(\Lambda(a))-\mu(\Lambda(a_{n}))\big{]}=\lim_{n\to\infty}\big{[}\nu(\Lambda(a))-\nu(\Lambda(a_{n}))\big{]}=\nu(\\{a\\}).$

In case $a$ is a common node for edges $e_{1},...,e_{k}$, then we have
$\Gamma(a)\setminus\cup_{i=1}^{k}\Gamma(a^{i}_{n})\downarrow\\{a\\}$, where
$\\{a^{i}_{n}\\}_{n=1}^{\infty}$ is a sequence of distinct points on edge
$e_{i}$ that converges to $a$ from below. Then, we obtain

$\displaystyle\mu(\\{a\\})=\lim_{n\to\infty}\big{[}\mu(\Lambda(a))-\sum_{i=1}^{k}\mu(\Lambda(a^{i}_{n}))\big{]}=\lim_{n\to\infty}\big{[}\nu(\Lambda(a))-\sum_{i=1}^{k}\nu(\Lambda(a^{i}_{n}))\big{]}=\nu(\\{a\\}).$

Thus, the claim is proved. On the other hand, for any points $x,y$ belonging
to the same edge

$\mu([x,y))=\mu(\Lambda(x))-\mu(\Lambda(y))=\nu(\Lambda(x))-\nu(\Lambda(y))=\nu([x,y)).$

Thus, by combining them, we infer further that $\mu([x,y])=\nu([x,y])$ for any
$x,y\in{\mathcal{T}}$. It follows that $\mu=\nu$, and the proof is complete. ∎

###### Proof.

[Of Proposition 3.10 in the main text] We note first that the quantity
$d_{\alpha}$ depends only on the values of the weights at the root $r$ of the
tree. This comes from the fact that only $w_{1}(r)$ and $w_{2}(r)$ are used in
the definition of $\mathbb{L}_{\alpha}$. The proofs of i) and iii) are exactly
the same as that of Proposition 3.7 in the main text.

For ii), it follows from the fact

$d_{\alpha}(\mu,\nu)=\sup\left\\{\int_{\mathcal{T}}f(\mu-\nu):\,f\in\mathbb{L}_{\alpha}\right\\}$

that $d_{\alpha}(\mu,\nu)\geq 0$, $d_{\alpha}(\mu,\mu)=0$, and $d_{\alpha}$
satisfies the triangle inequality. Also, if $d_{\alpha}(\mu,\nu)=0$, then by
Proposition 3.8 in the main text, we get

$\big{[}w_{i}(r)+\frac{b\lambda}{2}-\alpha\big{]}|\mu({\mathcal{T}})-\nu({\mathcal{T}})|+\int_{{\mathcal{T}}}|\mu(\Lambda(x))-\nu(\Lambda(x))|\,\omega(dx)=0.$

As $\big{[}w_{i}(r)+\frac{b\lambda}{2}-\alpha\big{]}>0$ by the assumption, we
must have $\mu({\mathcal{T}})=\nu({\mathcal{T}})$ and
$\int_{{\mathcal{T}}}|\mu(\Lambda(x))-\nu(\Lambda(x))|\,\omega(dx)=0$.
Therefore, $\mu(\Lambda(x))=\nu(\Lambda(x))$ for every $x\in{\mathcal{T}}$. By
using Lemma A.2, we then conclude that $\mu=\nu$.

Alternatively, we can argue as follows. Assume that $d_{\alpha}(\mu,\nu)=0$.
Since

$\mathbb{L}_{\alpha}\supset\tilde{\mathbb{L}}:=\left\\{f:\,-w_{2}(r)-\frac{b\lambda}{2}+\alpha\leq
f(x)\leq w_{1}(r)+\frac{b\lambda}{2}-\alpha,\,\|f\|_{Lip({\mathcal{T}})}\leq
b\right\\},$

we have

$0\leq\sup_{f\in\tilde{\mathbb{L}}}\int_{\mathcal{T}}f(\mu-\nu)\leq
d_{\alpha}(\mu,\nu)=0.$

Thus, $\sup_{f\in\tilde{\mathbb{L}}}\int_{\mathcal{T}}f(\mu-\nu)=0$. Then, by
applying Corollary 3.5 in the main text and Lemma A.1 for constant weights
$\tilde{w}_{1}:=w_{1}(r)+\frac{b\lambda}{2}-\alpha>0$ and
$\tilde{w}_{2}:=w_{2}(r)+\frac{b\lambda}{2}-\alpha>0$, we obtain that
$\mu=\nu$. ∎

###  A.10 Proof for Proposition 3.11 in the main text

###### Proof.

Let $\mathbf{f}(x_{i},x_{j})=\tilde{a}(x_{i}+x_{j})$ for
$\tilde{a},x_{i},x_{j}\in\mathbb{R}$. We first prove that $\mathbf{f}$ is
negative definite.

For all $n\geq 2$, for $c_{1},c_{2},\dotsc,c_{n}$ such that
$\sum_{i=1}^{n}c_{i}=0$. Given $x_{1},x_{2},\dotsc,x_{n}\in\mathbb{R}$, we
have

$\sum_{i,j}c_{i}c_{j}\mathbf{f}(x_{i},x_{j})=\sum_{i,j}c_{i}c_{j}\tilde{a}x_{i}+\sum_{i,j}c_{i}c_{j}\tilde{a}x_{j}\leq
0.$

Therefore, $\mathbf{f}$ is negative definite.

From Proposition 3.8 in the main text, we have

$\widetilde{\mathrm{ET}}_{\lambda}^{\alpha}(\mu,\nu)=-\frac{b\lambda}{2}\big{[}\mu({\mathcal{T}})+\nu({\mathcal{T}})\big{]}+\big{[}w_{i}(r)+\frac{b\lambda}{2}-\alpha\big{]}|\mu({\mathcal{T}})-\nu({\mathcal{T}})|+\int_{{\mathcal{T}}}|\mu(\Lambda(x))-\nu(\Lambda(x))|\,\omega(dx).$

The first term is negative definite since $\mathbf{f}$ is negative definite.
Additionally, the second and third terms are equivalent to the weighted
$\ell_{1}$ distance with nonnegative weights (i.e., $\alpha\leq
w_{i}(r)+\frac{b\lambda}{2}$ and lengths of edges in tree ${\mathcal{T}}$ are
nonnegative). Therefore, the second and third terms are also negative
definite. Hence, $\widetilde{\mathrm{ET}}_{\lambda}^{\alpha}$ is negative
definite.

From Proposition 3.10 in the main text, we have

$d_{\alpha}(\mu,\nu)=\widetilde{\mathrm{ET}}_{\lambda}^{\alpha}(\mu,\nu)+\frac{b\lambda}{2}\big{[}\mu({\mathcal{T}})+\nu({\mathcal{T}})\big{]}.$

Both terms are negative definite. Therefore, $d_{\alpha}$ is also negative
definite.

∎

##  Appendix B Further Experimental Results

In this section, we illustrate further experimental results.

###  B.1 Further Results on the Efficient Approximation of
$\widetilde{\textnormal{ET}}_{\lambda}^{0}$ for $\textnormal{ET}_{\lambda}$

In this section, we consider some further setups.

##### Change $\lambda$.

In Figure 7(a), we use the same setup as in Figure 2 in the main text, but set
the Lipschitz $a_{1}=\frac{b}{2}=0.5$ for $w_{1},w_{2}$. It shows that when
$\lambda$ is increased, $\widetilde{\textnormal{ET}}_{\lambda}^{0}$ is farther
to $\textnormal{ET}_{\lambda}$.

(a)

(b)

(c)

Figure 7: In (7(a)), an illustration about the relative difference between
$\widetilde{\textnormal{ET}}_{\lambda}^{0}$ and $\textnormal{ET}_{\lambda}$
w.r.t. $\lambda$. LT is the longest path from a root to a node in tree
$\mathcal{T}$ (LT := $L_{\mathcal{T}}$). Lipchitz for functions $w_{1},w_{2}$
is $a_{1}=0.5$ (where $b=1$). In (7(b), 7(c)), an illustration about the
absolute relative difference between
$\widetilde{\textnormal{ET}}_{\lambda}^{0}$ and $\textnormal{ET}_{\lambda}$,
i.e.,
$(\widetilde{\textnormal{ET}}_{\lambda}^{0}-\textnormal{ET}_{\lambda})/\left|\textnormal{ET}_{\lambda}\right|$,
w.r.t. $b$. For (7(b)), the weight functions $w_{1},w_{2}$ are set constants
($a_{1}=0$, or $w_{1}=w_{2}=a_{0}$) while for (7(c)), the weight functions
$w_{1},w_{2}$ are set with largest Lipchitz ($a_{1}=b$).

##### Change $b$.

We consider 2 following cases:

#####  $\bullet$ For constant functions $w_{1},w_{2}$ (with $a_{1}=0$).

We use the same setup as in Figure 1 in the main text, but with constant
functions for $w_{1},w_{2}$ (i.e., $a_{1}=0$, or $w_{1}=w_{2}=a_{0}$), and
change $b$. We set $\lambda=a_{0}=1$. In Figure 7(b), we illustrate that when
the regularization $b$ between entropy and partial matching is farther to $1$
(one of the two terms is more weighted, see Equation (2) in the main text),
$\widetilde{\textnormal{ET}}_{\lambda}^{0}$ is farther to
$\textnormal{ET}_{\lambda}$.

#####  $\bullet$ For functions $w_{1},w_{2}$ with largest Lipschitz $a_{1}=b$.

We use the same setup as in Figure 7(b), but with $a_{1}=b$. Figure 7(c) shows
similar results as in Figure 7(b) for $a_{1}=0$. For the largest Lipchitz for
functions $w_{1},w_{2}$ (i.e., $a_{1}=b$), but for $b=a_{0}=1$,
$\widetilde{\textnormal{ET}}$ is almost identical to KT, but they are
different when when the regularization $b$ between entropy and partial
matching is farther to $1$ (one of the two terms is more weighted, see
Equation (2) in the main text).

###  B.2 Further Results w.r.t. $\alpha$

We illustrate further SVM results of $d_{\alpha}$ and
$\widetilde{\textnormal{ET}}_{\lambda}^{\alpha}$ w.r.t. value of $\alpha$ in
TWITTER, RECIPE, CLASSIC, AMAZON datasets in Figure 8(a), and in Orbit, MPEG7
datasets in Figure 8(b). The value of $\alpha$ may affect performances of
$d_{\alpha}$ and $\widetilde{\textnormal{ET}}_{\lambda}^{\alpha}$ in some
datasets (e.g., RECIPE, AMAZON datasets for document classification, and Orbit
dataset in TDA), but may not sensitive in some other datasets (e.g., TWITTER,
CLASSIC datasets for document classification, and MPEG7 dataset in TDA).
Therefore, although $\alpha=0$ gives
$\widetilde{\textnormal{ET}}_{\lambda}^{\alpha}$ good property as in
Proposition 3.9 in the main text (upper bound for
$\textnormal{ET}_{\lambda}$), there is a possibility to choose suitable value
for $\alpha$ (e.g., via cross validation) to improve performances of
$d_{\alpha}$ and $\widetilde{\textnormal{ET}}_{\lambda}^{\alpha}$ for some
certain datasets.

(a) In TWITTER, RECIPE, CLASSIC, AMAZON datasets.

(b) In Orbit, MPEG7 datasets.

Figure 8: SVM results of $d_{\alpha}$ and
$\widetilde{\textnormal{ET}}_{\lambda}^{\alpha}$ w.r.t. value of $\alpha$ with
10 tree slices.

###  B.3 Further Results w.r.t. the Number of (Tree) Slices

Similar as Figure 6 in the main text, we illustrate further SVM results and
time consumption for corresponding kernel matrices for document classification
(e.g., TWITTER, RECIPE, CLASSIC, AMAZON datasets) and TDA (Orbit, MPEG7
datasets in Figure 9(a) and Figure 9(b) respectively. For a trade-off between
performances and time consumption, one can choose about $n_{s}=10$ slices in
applications.

(a) In TWITTER, RECIPE, CLASSIC, AMAZON datasets.

(b) In Orbit, MPEG7 datasets.

Figure 9: SVM results and time consumption for corresponding kernel matrices
w.r.t. the number of (tree) slices.

###  B.4 Further Results w.r.t. Parameters of Tree Metric Sampling

##### Document classification.

  * •

In Figure 10(a), Figure 10(b), Figure 10(c), Figure 10(d), we illustrate
further SVM results and time consumption for corresponding kernel matrices of
$d_{0}$ in TWITTER, RECIPE, CLASSIC, AMAZON datasets respectively w.r.t.
different parameters for clustering-based tree metric sampling such as the
predefined tree deepest level $H_{\mathcal{T}}$, and number of tree branches
$\kappa$ which is the number of clusters in the farthest-point clustering.

  * •

In Figure 11(a), Figure 11(b), Figure 11(c), Figure 11(d), we illustrate
further SVM results and time consumption for corresponding kernel matrices of
$\widetilde{\textnormal{ET}}_{\lambda}^{0}$ in TWITTER, RECIPE, CLASSIC,
AMAZON datasets respectively w.r.t. different parameters for clustering-based
tree metric sampling such as the predefined tree deepest level
$H_{\mathcal{T}}$, and number of tree branches $\kappa$ which is the number of
clusters in the farthest-point clustering.

(a) In TWITTER dataset.

(b) In RECIPE dataset.

(c) In CLASSIC dataset.

(d) In AMAZON dataset.

Figure 10: SVM results and time consumption for corresponding kernel matrices
of $d_{0}$ w.r.t. different parameters for clustering-based tree metric
sampling (predefined tree deepest level $H_{\mathcal{T}}$, and number of tree
branches $\kappa$—the number of clusters in the farthest-point clustering.).

(a) In TWITTER dataset.

(b) In RECIPE dataset.

(c) In CLASSIC dataset.

(d) In AMAZON dataset.

Figure 11: SVM results and time consumption for corresponding kernel matrices
of $\widetilde{\textnormal{ET}}_{\lambda}^{0}$ w.r.t. different parameters for
clustering-based tree metric sampling (predefined tree deepest level
$H_{\mathcal{T}}$, and number of tree branches $\kappa$—the number of clusters
in the farthest-point clustering.).

##### TDA.

  * •

In Figure 12(a), we illustrate further SVM results and time consumption for
corresponding kernel matrices of $d_{0}$ in Orbit, MPEG7 datasets w.r.t.
different parameters for partition-based tree metric sampling such as the
predefined tree deepest level $H_{\mathcal{T}}$.

  * •

In Figure 12(b), we illustrate further SVM results and time consumption for
corresponding kernel matrices of $\widetilde{\textnormal{ET}}_{\lambda}^{0}$
in Orbit, MPEG7 datasets w.r.t. different parameters for partition-based tree
metric sampling such as the predefined tree deepest level $H_{\mathcal{T}}$.

(a) For $d_{0}$.

(b) For $\widetilde{\textnormal{ET}}_{\lambda}^{0}$.

Figure 12: SVM results and time consumption for corresponding kernel matrices
in Orbit, MPEG7 datasets w.r.t. different parameters for partition-based tree
metric sampling (predefined tree deepest level $H_{\mathcal{T}}$).

Similar as in [43] (tree metric sampling for tree-sliced-Wasserstein in
applications), we also observed that the default parameters (e.g., the
predefined deepest level $H_{\mathcal{T}}=6$, and the tree branches
$\kappa=4$—the number of clusters in the farthest-point clustering) is a
reasonable choice to trade-off about performances and time consumption. With
these default parameters, sampled trees contains about $4000$ nodes.

##  Appendix C Further Details and Discussions

In this section, we give further details about experiments, some brief reviews
about important aspects used in our work and discuss other relations to other
work.

###  C.1 More Details about Experiments

In this section, we give further details about softwares, datasets and
experimental setups.

##### For softwares.

  * •

For experiments in topological data analysis, we used DIPHA toolbox, available
at https://github.com/DIPHA/dipha, to extract persistence diagrams.

  * •

For the standard complete optimal transport (OT) problem (e.g., KT in our work
which we used to compute the corresponding $\textnormal{ET}_{\lambda}$), we
used a fast OT implementation, available at https://github.com/gpeyre/2017-ot-
beginners/tree/master/matlab/mexEMD. It is about 4 times faster than the
popular mex-file with Rubner’s implementation in C, available at
http://robotics.stanford.edu/~rubner/emd/default.htm.

  * •

For tree metric sampling, we used the MATLAB implementation, available at
https://github.com/lttam/TreeWasserstein. We directly used this code for
clustering-based tree metric sampling, and adapted it into its special case
partition-based tree metric sampling.

  * •

For Sinkhorn-based approach for unbalanced OT (Sinkhorn-UOT), we used the
MATLAB implementation, available at https://github.com/gpeyre/2017-MCOM-
unbalanced-ot.

  * •

For sliced partial optimal transport (SPOT), we adapt the C++ implementation,
available at https://github.com/nbonneel/spot, into MATLAB.

##### For datasets.

  * •

For document datasets (e.g., TWITTER, RECIPE, CLASSIC, AMAZON), they are
available at https://github.com/mkusner/wmd.

  * •

For Orbit dataset, we follow the procedure, detailed in [1] to generate the
dataset.

  * •

For MPEG7 dataset, it is available at
http://www.imageprocessingplace.com/downloads_V3/root_downloads/image_databases/MPEG7_CE-
Shape-1_Part_B.zip, then we follow [43] to extract the 10-class subset of the
dataset.

  * •

For granular packing system and SiO2 datasets, one may access to them by
contacting the corresponding authors.

##### For experimental setups.

We further clarify some details about experimental setup.

As mentioned in the main text, for $d_{0}$ and
$\widetilde{\textnormal{ET}}_{\lambda}^{0}$, we choose the weight functions
for $w_{1},w_{2}$ as

$w_{1}(x)=w_{2}(x)=a_{1}d_{\mathcal{T}}(r,x)+a_{0},$

where $r$ is the root of tree $\mathcal{T}$, we set $\lambda=b=1$, $a_{0}=1$.
Following §5.1 in the main text, we set $a_{1}=b=1$. As in §3.2 in the main
text,
$\alpha\in\left[0,\frac{1}{2}\left(b\lambda+w_{1}(r)+w_{2}(r)\right)\right]$.
Thus, $\alpha\in[0,\frac{3}{2}]$ in our experiments (see more experiment
results with different values of $\alpha$ in §B.2). We used $n_{s}=10$ (tree)
slices for $d_{0}$, $\widetilde{\textnormal{ET}}_{\lambda}^{0}$ and SPOT. For
tree metric sampling, we used the default hyperparameters, the predefined tree
deepest level $H_{\mathcal{T}}=6$, and the tree branches $\kappa=4$—the number
of clusters used in the farthest-point clustering.

###  C.2 Some Brief Reviews

In this section, we give some brief reviews (or more referred details) about
some important aspects in our work.

##### For kernels.

We review some important definitions (e.g., positive/negative definite kernels
[6]) and theorems (e.g., Theorem 3.2.2 in [6]) about kernels used in our work.

#####  $\bullet$ Positive definite kernels [6, p.66–67].

A kernel function $k:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}$ is
positive definite if $\forall n\in\mathbb{N}^{*},\forall
x_{1},x_{2},...,x_{n}\in\mathcal{X}$, we have

$\sum_{i,j}c_{i}c_{j}k(x_{i},x_{j})\geq 0,\qquad\forall c_{i}\in\mathbb{R}.$

#####  $\bullet$ Negative definite kernels [6, p.66–67].

A kernel function $k:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}$ is
negative definite if $\forall n\geq 2,\forall
x_{1},x_{2},...,x_{n}\in\mathcal{X}$, we have

$\sum_{i,j}c_{i}c_{j}k(x_{i},x_{j})\leq 0,\qquad\forall
c_{i}\in\mathbb{R}\,\,\text{s.t.}\,\sum_{i}c_{i}=0.$

#####  $\bullet$ Theorem 3.2.2 in [6, p.74] for kernels.

If $\kappa$ is a negative definite kernel, then $\forall t>0$, kernel

$k_{t}(x,z):=\exp{\left(-t\kappa(x,z)\right)}$

is positive definite.

##### For tree metric sampling.

The tree metric sampling is described in details in [43][S4]. Le et al. [43]
also reviewed the details of the farthest-point clustering in §4.2 in the
supplementary, discussed about thee quantization/clustering sensitivity
problems of tree metric sampling in §5 in the supplementary.

##### For persistence diagrams and related mathematical definitions in
topological data analysis.

We refer the reader into [35, §2] for a review about mathematical framework
for persistence diagrams (e.g., persistence diagrams, filtrations, persistent
homology).

###  C.3 Discussions about Other Relations to Other Work

We note that ultrametric (i.e., non-Archimedean metric, or isosceles metric)
and its special case—binary metric are tree metrics [43]. Additionally, a
metric for points in a line (e.g., in 1-dimensional projections for supports
in SPOT, or SW), or in 1-dimensional manifold (e.g., in 1-dimensional manifold
projections for supports in generalized SW [34]) is also a tree metric since
we have a corresponding tree as a chain of these points.

We also list some other studies related to OT problem with tree metrics as
follows: (i) Kloeckner [33] derived geometric properties of OT space for
measures on an ultrametric space, (ii) Sommerfeld and Munk [64] studied
statistical inferences for OT on finite spaces including tree metrics, (iii)
tree-Wasserstein barycenter [41], (iv) alignment problems for probability
measures having supports in different spaces (i.e., fast tree variants for
Gromov-Wasserstein) [40], and ultrametric Gromov-Wasserstein [48].

We note that we consider the discrete measures in our work (e.g., empirical
measures). The closed-form formulation of our regularized entropy partial
transport (EPT) $\widetilde{\textnormal{ET}}_{\lambda}^{\alpha}$ in Equation
(8) in the main text is for general discrete nonnegative measures having
different masses. To our knowledge, the proposed regularized EPT (i.e.,
$\widetilde{\textnormal{ET}}_{\lambda}^{\alpha}$ in Equation (8) in the main
text) is the first approach that yields a closed-form solution among available
variants of unbalanced OT for discrete measures. In the context of unbalanced
OT for continuous measures (e.g., probability measures are scaled by positive
constants), Janati et al. [32] recently showed that entropic optimal transport
for unbalanced Gaussian measures (i.e., Gaussian measures are scaled by
different positive constants) has a closed-form solution.