# All You Need is Resistance: On the Equivalence of Effective Resistance and
Certain Optimal Transport Problems on Graphs

Sawyer Robertson, Zhengchao Wan, and Alexander Cloninger∗22footnotemark: 2
Department of Mathematics, University of California, San DiegoHalıcıoğlu Data
Science Institute, University of California, San Diego

###### Abstract

The fields of effective resistance and optimal transport on graphs are filled
with rich connections to combinatorics, geometry, machine learning, and
beyond. In this article we put forth a bold claim: that the two fields should
be understood as one and the same, up to a choice of $p$. We make this claim
precise by introducing the parameterized family of $p$-Beckmann distances for
probability measures on graphs and relate them sharply to certain Wasserstein
distances. Then, we break open a suite of results including explicit
connections to optimal stopping times and random walks on graphs, graph
Sobolev spaces, and a Benamou-Brenier type formula for $2$-Beckmann distance.
We further explore empirical implications in the world of unsupervised
learning for graph data and propose further study of the usage of these
metrics where Wasserstein distance may produce computational bottlenecks.

Keywords: effective resistance, optimal transport, graph Laplacians, convex
optimization, random walks

MSC: 65K10, 05C21, 90C25, 68R10, 05C50

###### Contents

  1. 1 Introduction and notation
    1. 1.1 Introduction
    2. 1.2 Outline of this paper
    3. 1.3 Related work
    4. 1.4 Mathematical background
  2. 2 General properties of the Beckmann problem
    1. 2.1 Duality theory for the p-Beckmann problem
    2. 2.2 Comparing p-Beckmann and p-Wasserstein distances
    3. 2.3 Worked examples: Paths and trees
  3. 3 The 2-Beckmann problem: Three perspectives
    1. 3.1 Effective resistance between measures
    2. 3.2 Sobolev norms and a graph Benamou-Brenier formula
    3. 3.3 A linearized optimal transportation distance
  4. 4 Acknowledgements
  5. A Proofs
    1. A.1 Proofs from section 2
    2. A.2 Proofs from section 3

##  1 Introduction and notation

###  1.1 Introduction

The theory of optimal transportation (OT), which traces its roots to the Monge
formulation as early as 1781 [56] as well as the Kantorovich relaxation
articulated in 1942 [41], is typically framed as an optimization problem for
some convex or affine function which measures the cost of mass transportation
over all feasible plans which provide recipes for transporting some mass
distribution to another. OT has received significant attention due to its
connections to geometry [85, 33], partial differential equations [7, 30, 29],
applied mathematics [63, 71, 72, 32, 69], and many other fields. For discrete
measures and domains in particular, OT and Wasserstein distance have been used
and studied for a variety of purposes including document retrieval [44],
statistics [81, 61, 11], image registration [38], distance approximation [75],
political redistricting [55, 15, 1], graph neural networks [16, 17, 92], and
graph Ollivier-Ricci curvature [83, 4, 70, 59].

When the underlying metric space of the transportation process is a graph,
much attention has been focused on the $1$-Wasserstein metric, which can be
informally set up as a linear program of the following form:

(1)
$\displaystyle\mathcal{W}_{1}(\alpha,\beta)=\inf\left\\{\sum_{ij}\pi_{ij}d(i,j):\pi\in\Pi(\alpha,\beta)\right\\},$

where $\Pi(\alpha,\beta)$ consists of the couplings of two generic probability
distributions $\alpha,\beta$ on the nodes of a graph and $d(i,j)$ is the
shortest path metric on the vertex set $V$ (see Definition 1.3 for a complete
description). It so happens on graphs that this metric can also be written in
a fashion often termed the Beckmann formulation:

(2)
$\displaystyle\mathcal{W}_{1}(\alpha,\beta)=\inf\left\\{\sum_{e}|J(e)|w_{e}:J:E\rightarrow\mathbb{R},\hskip
2.84544ptBJ=\alpha-\beta\right\\}$

where $B$ is the graph incidence matrix, $J$ is any map on the edges of the
graph and which is identified as a vector in $\mathbb{R}^{|E|}$, and $w_{e}$
is the nonnegative weight for edge $e\in E$ (see Definition 1.4 for a complete
description). This formulation is named after Martin Beckmann who studied
dynamic formulations of OT beginning in the 1950s [5], and whose models for OT
in the continuous setting Eq. 2 closely mirrors in a discrete sense. The
variable $J$ is sometimes called a feasbile flow between $\alpha$ and $\beta$
(see Fig. 1), and as such Eq. 2 is also sometimes deemed a flow-based
formulation for OT on graphs.

Seemingly separately, effective resistance (ER) on graphs has long been
studied for its metric properties between nodes and its connections to many
other problems in graph theory. Recall that for two nodes $i,j\in V$, and
corresponding standard basis vectors
$\delta_{i},\delta_{j}\in\mathbb{R}^{|V|}$, the ER between them is given by
$r_{ij}=(\delta_{i}-\delta_{j})^{T}L^{\dagger}(\delta_{i}-\delta_{j})$ where
$L^{\dagger}$ is the Moore-Penrose psuedo inverse of the graph Laplacian.
Applications and research on ER include foundational work by Spielman and
Srivastava on spectral graph sparsifcation using ER [76], as well as spectral
clustering models leveraging computational advantages of ER solvers [42]. ER
has also been used for computing and studying statistics associated to random
walks on graphs [25, 82, 50]. Interestingly, in the case of directed and
connection graphs, the opposite is the case as random walk statistics have
been used to obtain versions of ER [78, 19]. Moreover, there exist geometric
applications involving ER as an ingredient for defining discrete Ricci
curvature [22, 23]. For other references which study and utilize effective
resistance in various contexts, see, e.g., [25, 40, 34, 91, 36, 12, 18, 10].

This paper is built on an observation which seems to have not yet appeared in
the field: that effective resistance, when extended to probability measures on
a graph $G$, can be realized as an OT distance obtained from a Beckmann-type
problem with a $2$-norm penalty. The resulting metric, while removed from a
conventional coupling-based formulation of OT, is intricately connected to the
theory of random walks on graphs, the graph Laplacian matrix, and graph
Sobolev spaces.

######  Theorem 1.1 (Informal statement of Theorem 3.4).

Let $G=(V,E,w)$ be a weighted connected graph with Laplacian matrix $L$ and
psuedoinverse $L^{\dagger}$. Denote the oriented vertex-edge incidence matrix
of $G$ by $B$, and let $\alpha,\beta$ be fixed probability measures on $V$
regarded as vectors in $\mathbb{R}^{|V|}$. For $1\leq p<\infty$, define
$\mathcal{B}_{p}(\alpha,\beta)$ by the following convex optimization problem:

(3) $\displaystyle\mathcal{B}_{p}(\alpha,\beta)^{p}=\inf\left\\{\sum_{e\in
E}|J(e)|^{p}w_{e}:J:E\rightarrow\mathbb{R},\hskip
2.84544ptBJ=\alpha-\beta\right\\}.$

Then it holds:

  1. (a)

When $p=1$, $\mathcal{B}_{1}(\alpha,\beta)=\mathcal{W}_{1}(\alpha,\beta)$.

  2. (b)

When $p=2$,
$\mathcal{B}_{2}(\alpha,\beta)^{2}=(\alpha-\beta)^{T}L^{\dagger}(\alpha-\beta)$.

The metric introduced in Theorem 1.1 for $p=2$ is a (squared) norm distance,
so its properties and structures are fundamentally different from the
(nonlinear) Wasserstein metric in general. However, this metric seems to
posses a rich array of properties and characterizations which demonstrate
strong homophily with the classical results in OT. This metric also shows
promise for use in kernel-based learning methods for data defined on graphs,
and in terms of complexity, is significantly less expensive to compute at
scale compared to the Wasserstein metric.

Our main contributions are summarized as follows.

  1. 1.

We introduce the notion of $p$-Beckmann distance between probability measures,
and derive various bounds between $p$-Beckmann distances and $p$-Wasserstein
distances for measures on general graphs (e.g., Corollary 2.11).

  2. 2.

We provide an explicit formula for $\mathcal{B}_{p}$ on trees (Proposition
2.15).

  3. 3.

We obtain a generalized commute time formula for $2$-Beckmann distance, or
measure effective resistance, in terms of optimal access times of the simple
random walk on a graph (Theorem 3.13).

  4. 4.

We realize $2$-Beckmann distance as a negative Sobolev-type semi-norm distance
and use this property to obtain a Benamou-Brenier type formula for
$2$-Beckmann distance (Theorem 3.22).

  5. 5.

We apply $2$-Beckmann distance to an unsupervised kernel-based clustering
method involving handwritten digit data, and compare the results with the
$2$-Wasserstein kernel; and thereby establish empirical evidence for the usage
of a $2$-Beckmann kernel on a drop-in basis in place of a $2$-Wasserstein
kernel for datasets defined on graphs (Fig. 6).

###  1.2 Outline of this paper

In Section 1.4, we provide relevant mathematical background and notation.

In Section 2, we delve into the general properties of the $p$-Beckmann
problem, including duality theory in Section 2.1 and estimates between
Beckmann and Wasserstein distances Section 2.2. In Section 2.3, we highlight
some specialized results in the cases of paths and trees.

In Section 3 we focus exclusively in the properties and theory of the
$2$-Beckmann distance. In Section 3.1 we frame the metric as effective
resistance between measures and relate it to optimal stopping times and access
times between probability measures on $G$. In Section 3.2 we frame the metric
as a negative Sobolev-type seminorm and obtain a graph Bemaou-Brenier-type
formula. Finally, in Section 3.3 we apply the $2$-Beckmann distance to an
unsupervised learning problem and explore various empirical observations and
implications.

Lastly, in Appendix A we provide proofs of the results mentioned in the main
component of the paper.

###  1.3 Related work

In this section we wish to highlight some particularly relevant works on which
this paper is based in parts, and in doing so, better situate the novelty of
our contributions in a broader context.

The most relevant investigation of OT on graphs, including regularization and
convex duality, appears in work by Essid and Solomon [28] and further studies
in the field can be found in [75, 74, 62, 57, 67, 49, 65].

The introduction of $p$-Beckmann distances in Section 2 and its study as an
effective resistance metric in Section 3.1 should be understood as extensions
of the notion of $p$-resistances from work of Alamgir and Luxburg [2] to
general probability measures (from the case of nodes, i.e., Dirac measures).
Such generalizations of resistances and their implications in unsupervised
models were also considered by Nguyen and Hamitsuka [60], and Saito and
Herbster [68] but only between nodes. The notions of measure access times and
optimal stopping times have been studied at length by Lovász, Winkler and
Beveridge across several papers [50, 51, 52, 9, 8].

Separately, the notion of using negative Sobolev distance as a linearization
of quadratic Wasserstein distance was studied by Greengard, Hoskins, Marshall,
and Singer in [37] and is a homophilous framework appearing in the continuous
setting. The proof of the Benamou-Brenier-type formula for $2$-Beckmann
distance is a direct discretization of the proof appearing in [35]. It is also
notable that our model of $2$-Beckmann distance as a negative Sobolev distance
on graphs is parallel to the works by Le, T. Nguyen, Phung, V. A. Nguyen, and
Fukumizo and appearing in [46, 47, 48]; but our definitions differ slightly
from theirs. Linearized OT and its usage in the unsupervised setting is also
explored by Moosmüller and AC [58], and results therein form a basis for our
Theorem 3.25 on linear separation of measures in the $2$-Beckmann metric
space.

###  1.4 Mathematical background

Let $G=(V,E,w)$ be a graph, where $V=\\{1,2,\dotsc,n\\}$ is the set of
vertices, $E\subset{V\choose 2}$ is a set of undirected edges of cardinality
$m\geq 0$, and $w=(w_{ij})_{i,j\in V}$ is a choice of real edge weights
satisfying $w_{ij}\geq 0$, $w_{ij}=w_{ji}$, and $w_{ij}>0$ if and only if
$\\{i,j\\}\in E$. In order to ensure the feasibility of optimal transportation
problems and simplify the exposition in places, we assume that $G$ is finite,
has no multiple edges or loops, and is connected.

For our purposes, a path in $G$ is an ordered sequence of nodes
$P=(i_{0},i_{1},\dotsc,i_{k})$ such that $i_{\ell}\sim i_{\ell+1}$ for
$0\leq\ell\leq k-1$. If $P$ is a path, $|P|$ is the (integral) length of the
path, i.e., $|P|=k$, and $|P|_{w}$ is the weighted length of $P$, or the sum
of the weights of edges it contains; i.e.
$|P|_{w}=\sum_{\ell=0}^{k-1}w_{i_{\ell}i_{\ell+1}}$. For any two nodes $i,j\in
V$, $\mathscr{P}(i,j)$ is the set of all paths which begin at $i$ and end at
$j$.

In this paper, we will consider several different metrics on $V$. A metric on
$V$ is a map $\kappa:V\times V\rightarrow\mathbb{R}$ such that

  1. (i)

(Nonnegativity) $\kappa(i,j)\geq 0$ for each $i,j\in V$,

  2. (ii)

(Definiteness) $\kappa(i,j)=0$ if and only if $i=j$,

  3. (iii)

(Symmetry) $\kappa(i,j)=\kappa(j,i)$ for each $i,j\in V$,

  4. (iv)

(Triangle inequality) $\kappa(i,k)\leq\kappa(i,j)+\kappa(j,k)$ for each
$i,j,k\in V$.

We will primarily use variants of the shortest path metric on $V$ and the
metrics induced by effective resistance.

######  Definition 1.2.

Let $1\leq p<\infty$. Define the weighted $p$-shortest path metric on $V$ by
the formula

(4) $\displaystyle
d_{p}(i,j)=\inf\left\\{\left(\sum_{\ell=0}^{k-1}w_{i_{\ell}i_{\ell+1}}^{p}\right)^{1/p}:P=(i=i_{0},i_{1},\dotsc,i_{k}=j)\in\mathscr{P}(i,j)\right\\}$

It is relatively straightforward to verify that $d_{p}$ satisfies the
properties necessary for a metric on $V$ for each $p,w$.

We define the Adjacency matrix $A\in\mathbb{R}^{n\times n}$ entrywise by

(5) $\displaystyle A_{ij}$ $\displaystyle=\begin{cases}w_{ij}&\text{ if }i\sim
j\\\ 0&\text{ otherwise}\end{cases}.$

where the notation $i\sim j$ means $\\{i,j\\}\in E$. For each $i\in V$ we
define its degree $d_{i}=\sum_{j\sim i}w_{ij}$. We will also use the diagonal
degree matrix $D=\mathrm{diag}(d_{1},\dotsc,d_{n})\in\mathbb{R}^{n\times n}$
and the diagonal edge weight matrix
$W=\mathrm{diag}(w_{e_{1}},\dotsc,w_{e_{m}})\in\mathbb{R}^{m\times m}$.

For technical purposes, we may ocassionally refer to the index-oriented and
bi-oriented edge sets $E^{\prime}$ and $E^{\prime\prime}$, respectively,
defined below:

(6) $\displaystyle E^{\prime}$ $\displaystyle=\left\\{(i,j):i,j\in V,i\sim
j,i<j\right\\}$ (7) $\displaystyle E^{\prime\prime}$
$\displaystyle=\left\\{(i,j),(j,i):i,j\in V,i\sim j\right\\}.$

We define the incidence matrix $B\in\mathbb{R}^{n\times m}$, with rows indexed
by $V$ and columns indexed by $E^{\prime}$, by the formula:

(8) $\displaystyle B_{i,e_{j}}$ $\displaystyle=\begin{cases}1&\text{ if
}e_{j}=(i,\cdot)\\\ -1&\text{ if }e_{j}=(\cdot,i)\\\ 0&\text{
otherwise}\end{cases}.$

We also occasionally use the matrix $\widetilde{B}\in\mathbb{R}^{n\times 2m}$,
with rows indexed by $V$ and columns indexed by $E^{\prime\prime}$, defined by
an identical formula as in Eq. 8. We define the Laplacian matrix $L$ by the
formula $L=D-A$, or $L=BWB^{T}$. Note that
$\widetilde{B}\widetilde{W}\widetilde{B}^{T}=2L$, where
$\widetilde{W}\in\mathbb{R}^{2m\times 2m}$ is the diagonal matrix of edge
weights of $E^{\prime\prime}$. We recall that $L$ is symmetric, positive semi-
definite, and has a set of nonnegative eigenvalues

(9) $\displaystyle 0=\lambda_{0}\leq\lambda_{1}\leq\dotsc\leq\lambda_{n}.$

We use
$\Lambda=\mathrm{diag}(\lambda_{0},\lambda_{1},\dotsc,\lambda_{n})\in\mathbb{R}^{n\times
n}$ for the diagonal matrix of eigenvalues, and
$U=\begin{bmatrix}u_{1}&u_{2}&\cdots&u_{n}\end{bmatrix}$ for the respective
orthonormal eigenvectors of $L$. The spectral decomposition of $L$ is given by
the equation $L=U\Lambda U^{T}$.

For any matrix $X\in\mathbb{R}^{\ell\times k}$, we will use the notation
$X^{\dagger}\in\mathbb{R}^{k\times\ell}$ for its Moore-Penrose psuedoinverse.
We recall that $X^{\dagger}$ is the unique matrix satisfying the following
four properties [6]:

  1. (i)

$XX^{\dagger}X=X$

  2. (ii)

$X^{\dagger}XX^{\dagger}=X^{\dagger}$

  3. (iii)

$(XX^{\dagger})^{T}=XX^{\dagger}$

  4. (iv)

$(X^{\dagger}X)^{T}=X^{\dagger}X$

where $(\cdot)^{T}$ indicates matrix transpose.

In the case of the Laplacian matrix $L$, we have

$L^{\dagger}=U\Lambda^{-1}U^{T}$

where, with an abuse of notation, we write

(10)
$\displaystyle\Lambda^{-1}=\mathrm{diag}(\lambda_{0}=0,\lambda_{1}^{-1},\dotsc,\lambda_{n}^{-1})\in\mathbb{R}^{n\times
n}.$

Similarly, we write $L^{-1/2}=U\Lambda^{-1/2}U^{T}$.

For a finite set $S$, we define $\ell_{2}(S)$ to be the linear space of
functions $f:S\rightarrow\mathbb{R}$ with the standard Euclidean inner product
$\langle f,g\rangle_{\ell_{2}(S)}=g^{T}f$. We identify $\ell_{2}(V)$ with
$\mathbb{R}^{n}$ and $\ell_{2}(E^{\prime})$ with $\mathbb{R}^{m}$,
respectively.

For a vector $x\in\mathbb{R}^{n}$ and $1\leq p<\infty$, we define the vector
$p$-norm by

$\|x\|_{p}=\left(\sum_{i=1}^{n}|x_{i}|^{p}\right)^{1/p}.$

For any finite set $S$, in a similar manner as before, we can define
$\ell_{p}(S)$ to be the linear linear space of functions
$f:S\rightarrow\mathbb{R}$ with the norm $\|\cdot\|_{p}$. If in some cases we
wish to refer simply to the linear space of functions on $S$, such as when we
employ multiple norms at once, we use the notation $\ell(S)$ and specify the
norm or inner product in context.

If $J\in\ell(E^{\prime})$, then we can weight the norm $\|\cdot\|_{p}$ by the
edge weights as follows:

(11) $\displaystyle\|J\|_{w,p}$ $\displaystyle=\left(\sum_{e\in
E^{\prime}}|J(e)|^{p}w_{e}\right)^{1/p},$

and similarly for $\ell(E^{\prime\prime})$. We will use the subscript of $w$
to indicate the presence of edge weights.

As a matter of notation, functions in $\ell(V)$ will be denoted with lowercase
Latin and Greek letters (in the case of measures), and functions in
$\ell(E^{\prime})$ and $\ell(E^{\prime\prime})$ will be denoted with uppercase
Latin letters.

Note that the matrices $B$, $B^{T}$, and $L$ act on their respective function
spaces by matrix multiplication. We summarize their pointwise formulas below.

(12) $\displaystyle(BJ)(i)$ $\displaystyle=\sum_{e\in
E^{\prime}:e=(i,\cdot)}J(e)-\sum_{e\in E^{\prime}:e=(\cdot,i)}J(e),$
$\displaystyle i\in V,J\in\ell(E^{\prime})$ (13)
$\displaystyle(B^{T}f)(e=(i,j))$ $\displaystyle=f(i)-f(j),$ $\displaystyle
e\in E^{\prime},f\in\ell(V)$ (14) $\displaystyle(Lf)(i)$
$\displaystyle=\sum_{j\sim i}(f(i)-f(j))w_{ij},$ $\displaystyle i\in
V,f\in\ell(V)$

It is worth noting that in some contexts (e.g., [27, 26]), $B(\cdot)$ and
$B^{T}(\cdot)$ are considered the graph equivalents of the divergence and
gradient operators, respectively. We will also occasionally use the Dirichlet
energy functional for $f\in\ell(V)$, defined by the quadratic form of the
Laplacian matrix:

(15) $\displaystyle f^{T}Lf=\sum_{(i,j)\in
E^{\prime}}w_{ij}(f(i)-f(j))^{2}=\|B^{T}f\|_{w,2}^{2}$

We define the probability measure simplex $\mathcal{P}(V)$ by the set

(16) $\displaystyle\mathcal{P}(V):=\left\\{\alpha\in\ell(V):\alpha\geq
0,\sum_{i\in V}\alpha(i)=1\right\\}.$

For $i\in V$, $\delta_{i}$ is the Dirac or unit measure at node $i$,
identified with the $i$-th standard basis vector in $\mathbb{R}^{n}$.

The primary objects of study for this paper are two different optimal
transportation distances between probability measures on $V$. The first, which
is classical and extensively studied on graphs, is $p$-Wasserstein distance.

######  Definition 1.3.

Let $\alpha,\beta\in\mathcal{P}(V)$, $1\leq p<\infty$, and $k$ any metric on
$V$. Define the set of transportation couplings between $\alpha$ and $\beta$,
denoted $\Pi(\alpha,\beta)$, by the following set

(17) $\displaystyle\Pi(\alpha,\beta)=\left\\{\pi\in\mathbb{R}^{n\times
n}:\pi\geq 0,\pi\mathbf{1}=\alpha,\mathbf{1}^{T}\pi=\beta^{T}\right\\},$

where $\mathbf{1}\in\mathbb{R}^{n}$ is the vector containing all ones. We
define the $(k,p)$-Wasserstein distance between two probability measures ,
denoted $\mathcal{W}_{k,p}(\alpha,\beta)$ by the following optimization
problem:

(18)
$\displaystyle\mathcal{W}_{k,p}(\alpha,\beta)=\inf\left\\{\left(\sum_{i,j\in
V}\pi_{ij}k(i,j)^{p}\right)^{1/p}:\pi\in\Pi(\alpha,\beta)\right\\}.$

As a matter of convention, when $k=d_{1}$, that is, the weighted $1$-shortest-
path metric, we write $\mathcal{W}_{d_{1},p}=\mathcal{W}_{p}$. The second
optimal mass transportation distance is much less studied in its own right
except in the cases of $p=1$ and to a seemingly much lesser extent, $p=2$.

######  Definition 1.4.

Let $1\leq p<\infty$ and $\alpha,\beta\in\mathcal{P}(V)$. Define the set of
feasible edge flows between $\alpha$ and $\beta$, denoted
$\mathcal{J}(\alpha,\beta)$, by the affine region

(19) $\displaystyle\mathcal{J}(\alpha,\beta)$
$\displaystyle=\left\\{J\in\ell_{2}(E^{\prime}):BJ=\alpha-\beta\right\\}.$

Then the $p$-Beckmann distance between $\alpha,\beta$, denoted
$\mathcal{B}_{p}(\alpha,\beta)$ is given by the following constrainted norm
optimization problem:

(20) $\displaystyle\mathcal{B}_{p}(\alpha,\beta)$
$\displaystyle=\inf\left\\{\|J\|_{w,p}:J\in\mathcal{J}(\alpha,\beta)\right\\}$

$\alpha$$\beta$ (a) $p=1$,
$\mathcal{B}_{1}(\alpha,\beta)=\mathcal{W}_{1}(\alpha,\beta)\approx 9.3$.

$\alpha$$\beta$ (b) $p=2$, $\mathcal{W}_{2}(\alpha,\beta)\approx 1.225$,
$\mathcal{B}_{2}(\alpha,\beta)\approx 1.499$

Figure 1: A side-by-side comparison of optimal flows for the $1$-Beckmann and
$2$-Beckmann problems on a $4\times 4$ hexagonal lattice graph. The masses of
$\alpha,\beta$ at each node are rendered proportionally to opacity; and
similarly the optimal flow values at each edge are rendered proportionally to
opacity. The arrows indicate orientation of the flow value; i.e.,
$\circ\rightarrow\circ^{\prime}$ if the optimal flow $J$ satisfies
$J(\circ,\circ^{\prime})>0$ and $\circ\leftarrow\circ^{\prime}$ if
$J(\circ,\circ^{\prime})<0$.

Note that $\mathcal{J}(\alpha,\beta)\neq\varnothing$ for any $\alpha,\beta$
since the column space of $B$ is exactly the mean zero functions on $V$. The
$p$-Wasserstein and $p$-Beckmann problems are essentially two different
perspectives on optimal transportation for measures on graphs. The
“Wasserstein philosophy” being that mass transportation is tracked between all
pairs of nodes, and is accounted according to $d_{ij}^{p}$. We can also think
of this philosophy as one of mass teleportation- the primal variable, or
coupling, does not reveal how mass $\pi_{ij}$ moves from $i$ to $j$, only that
it did so along a shortest path somewhere, or a combination of shortest paths.
The “Beckmann philosophy” is the viewpoint that mass must move along edges and
the transportation should be accounted in terms of edge flows, which are
really just signed mass values on each oriented edge. In this formulation, the
penalty lies on $|J(e)|^{p}$, so transportation flows can often be non-sparse,
or occur along weighted combinations of shortest and non-shortest paths.
Comparisons of optimal flows for values $p=1,2$ in an example setting are
shown in Fig. 1.

######  Remark 1.5.

A slightly different way to formulate Definition 1.4 would be through
$E^{\prime\prime}$ with a nonnegativity constraint. That is, let

(21) $\displaystyle\mathcal{J}^{\prime\prime}(\alpha,\beta)$
$\displaystyle=\left\\{J\in\ell_{2}(E^{\prime\prime}):J\geq
0,\widetilde{B}J=\alpha-\beta,\right\\}.$

and then,

(22) $\displaystyle\mathcal{B}_{p}(\alpha,\beta)$
$\displaystyle=\inf\left\\{\|J\|_{w,p}:J\in\mathcal{J}^{\prime\prime}(\alpha,\beta)\right\\}.$

It is not hard to show that these two formulations arrive at the same value.
Definition 1.4 simply allows for signed flows; for example, a flow value of
$-1$ along the oriented edge $(1,2)$ represents one unit of mass transported
from node $2$ to node $1$. We opt to drop the nonnegativity constraint for
this paper and focus on the former formulation as it simplifies the
calculations slightly, but we may have occassion to use this formulation
instead.

In the Proposition below, we summarize two relevant properties of
$\mathcal{W}_{p}$ and $\mathcal{B}_{p}$.

######  Proposition 1.6.

Let $\alpha,\beta\in\mathcal{P}(V)$.

  1. (i)

The objective functions for both $\mathcal{W}_{p}(\alpha,\beta)$ and
$\mathcal{B}_{p}(\alpha,\beta)$ are convex for all $1\leq p<\infty$, and the
infima are always achieved.

  2. (ii)

The objective for $\mathcal{B}_{p}(\alpha,\beta)$ is strictly convex for
$p>1$. The infimum is always achieved and is unique in the case $p>1$.

  3. (iii)

$\mathcal{W}_{p}$ and $\mathcal{B}_{p}(\alpha,\beta)$ define metrics on
$\mathcal{P}(V)$.

Proofs of items (i) and (ii) are straightforward since the objectives are
defined either by affine functions or common norms whose convexity properties
are well-understood. For (iii), a proof for $\mathcal{W}_{p}$ can be found in
[62, Ch. 2], and the case of $\mathcal{B}_{p}$ is relatively straightforward.

##  2 General properties of the Beckmann problem

In this section, we look at a few interesting properties of the Beckman
problem $\mathcal{B}_{p}(\alpha,\beta)$ for general $1\leq p<\infty$. In
Section 2.1 we derive the Lagrangian dual to the $p$-Beckmann problem, in
Section 2.2 we obtain bounds that relate certain Beckmann and Wasserstein
distances, and finally, in Section 2.3, we work through some example results
on paths and trees to highlight examples of Wasserstein and Beckmann
distances.

###  2.1 Duality theory for the p-Beckmann problem

In this subsection we study the convex duality of the $p$-Beckmann problem. In
[2] Alamgir and Luxburg introduced formulations of $p$-resistances, that is,
generalizations of effective resistance obtained by Beckmann-type $\min$ cost
flow problems penalized by a $p$-norm. They studied the primal and dual forms
of these problems, and thereby obtained so-called potential-based formulations
of the resistance problems. As described in Section 1.3, the results presented
in this section may be considered extensions of the results concerning
$p$-resistances to the case of general probability measures; namely, we
understand the $p$-resistance between generic nodes $i,j$ to be $p$-Beckmann
distance between Dirac measures at $i,j$. In Theorem 2.1 we obtain the dual
formulation of the $p$-Beckmann optimization problem, and thus generalize the
Kantorovich-Rubenstein duality on graphs to all $1\leq p<\infty$ (see Remark
2.3).

######  Theorem 2.1.

Let $\alpha,\beta\in\mathcal{P}(V)$ and $1<p<\infty$ be fixed. Let $q$ be the
conjugate of $p$ so that $\frac{1}{p}+\frac{1}{q}=1$. Then the dual to the
$p$-Beckmann problem, given by

(23) $\displaystyle\mathcal{B}_{p}(\alpha,\beta)$
$\displaystyle=\inf\left\\{\|J\|_{w,p}:J\in\ell(E^{\prime}),BJ=\alpha-\beta\right\\},$

is given by the maximization problem

(24) $\displaystyle\mathcal{B}_{p}(\alpha,\beta)$
$\displaystyle=\sup\left\\{\phi^{T}(\alpha-\beta):\phi\in\ell(V),\left\|B^{T}\phi\right\|_{w^{1-q},q}\leq
1\right\\},$

and strong duality holds. In the special case of $p=1$ and $q=\infty$, we have

(25) $\displaystyle\mathcal{B}_{1}(\alpha,\beta)$
$\displaystyle=\inf\left\\{\|J\|_{w,1}:J\in\ell(E^{\prime}),BJ=\alpha-\beta\right\\}=\sup\left\\{\phi^{T}(\alpha-\beta):\phi\in\ell(V),\left\|B^{T}\phi\right\|_{w^{-1},\infty}\leq
1\right\\}$

We defer the proof to Section A.1.

######  Remark 2.2.

If we specialize to the case where the edge weights are all unit value; i.e.,
$G$ is unweighted, then the weights can be dropped from the preceding results.
In particular, the dual norm to $\|\cdot\|_{p}$ is simply $\|\cdot\|_{q}$ and

(26)
$\displaystyle\mathcal{B}_{p}(\alpha,\beta)=\inf\left\\{\|J\|_{p}:J\in\ell(E^{\prime}),BJ=\alpha-\beta\right\\}=\sup\left\\{\phi^{T}(\alpha-\beta):\phi\in\ell(V),\left\|B^{T}\phi\right\|_{q}\leq
1\right\\}$

######  Remark 2.3.

The case $p=1$ and $q=\infty$ is the conventional Kantorovich-Rubenstein
duality on graphs [89], which can be more conventionally written as

(27) $\displaystyle\inf\left\\{\sum_{e\in
E^{\prime}}|J(e)|w_{e}:J\in\ell(E^{\prime}),BJ=\alpha-\beta\right\\}=\sup\left\\{\phi^{T}(\alpha-\beta):\phi\in\ell(V),\|\phi\|_{\mathrm{Lip}}\leq
1\right\\}$

where the Lipschitz seminorm
$\|\phi\|_{\mathrm{Lip}}=\|B^{T}\phi\|_{w^{-1},\infty}$ on $\ell(V)$ is
defined by

(28)
$\displaystyle\|\phi\|_{\mathrm{Lip}}=\max\frac{|\phi(i)-\phi(j)|}{d(i,j)}=\max_{i\sim
j}\frac{|\phi(i)-\phi(j)|}{w_{ij}}.$

Note also that this duality occurs in a homophilous manner for Beckmann’s
minimal flow problem in the continuous setting [71, Sec 4.2], which is the
namesake for the minimal flow formulations on graphs.

###  2.2 Comparing p-Beckmann and p-Wasserstein distances

In this section, we establish some bounds between $\mathcal{B}_{p}$ and
$\mathcal{W}_{p}$ in certain situations. Section 2.2.1 introduces a technique
for obtaining an edge flow from a given coupling with some control on the
cost, and uses it to derive elementary bounds for general $p$; and in Section
2.2.2 we focus on the case of $\mathcal{W}_{1}$ and obtain sharp estimates
related to $\mathcal{B}_{2}$, the latter of which is of particular interest in
the ensuing sections.

####  2.2.1 From coupling to flow

An essential ingredient in comparing the optimal values of transportation
metrics is having the ability to convert a coupling $\pi$ to a feasible edge
flow $J$, and vice-versa. In this subsection we will make use of the bi-
oriented edge flow formulation of $\mathcal{B}_{p}$, which was discussed in
Remark 1.5.

######  Definition 2.4.

Let $i,j\in V$. Let $P\in\mathscr{P}(i,j)$ be a path between $i,j$. Write
$P=(i=i_{0},i_{1},\dotsc,i_{k}=j)$. Define

(29) $\displaystyle
I_{P}=\sum_{\ell=0}^{k-1}\delta_{(i_{\ell},i_{\ell+1})}\in\ell(E^{\prime\prime}).$

######  Proposition 2.5.

Let $\alpha,\beta\in\mathcal{P}(V)$, $1\leq p<\infty$, and suppose
$\pi\in\Pi(\alpha,\beta)$. For each pair of nodes $i,j\in V$ with $i\neq j$,
let $P_{ij}\in\mathscr{P}(i,j)$ be a fixed path between $i,j$. Define the edge
flow $J^{\pi}=J^{\pi,(P_{ij})}\in\ell(E^{\prime\prime})$ by the expression

(30) $\displaystyle J^{\pi}=\sum_{i\neq j\in V}\pi_{ij}I_{P_{ij}}$

Then $J^{\pi}$ is a feasible flow for $\mathcal{B}_{p}(\alpha,\beta)$, i.e.,
$J^{\pi}\geq 0$ and $BJ^{\pi}=\alpha-\beta$, and the following estimate holds:

(31) $\displaystyle\|J^{\pi}\|_{w,p}\leq\sum_{i,j\in
V}\pi_{ij}\|I_{P_{ij}}\|_{w,p}.$

We include a proof in Section A.1. We can use Proposition 1.6 to derive at
least two estimates which relate $\mathcal{B}_{p}$ to $\mathcal{W}_{k,p}$ for
different choices of $k$. The first is somewhat brutal, but is informative for
$p$ small.

######  Theorem 2.6.

Let $\alpha,\beta\in\mathcal{P}(V)$, $1\leq p<\infty$, and assume that
$w_{ij}\geq 1$ for each $i,j\in V$ such that $i\sim j$. Then

(32)
$\displaystyle\mathcal{B}_{p}(\alpha,\beta)\leq\mathcal{W}_{p}(\alpha,\beta)^{p}$

###### Proof.

Let $\pi\in\Pi(\alpha,\beta)$ be an optimal coupling for
$\mathcal{W}_{p}(\alpha,\beta)$. For each $i,j$, let
$P_{ij}\in\mathscr{P}(i,j)$ be a choice of path which is minimal in the sense
of $d_{1}$, and let $J^{\pi}=J^{\pi,(P_{ij})}$ be the feasible flow as in
Proposition 2.5. Then

(33)
$\displaystyle\mathcal{B}_{p}(\alpha,\beta)\leq\|J^{\pi}\|_{w,p}\leq\sum_{i,j\in
V}\pi_{ij}\|I_{P_{ij}}\|_{w,p}\leq\sum_{i,j\in
V}\pi_{ij}d_{1}(i,j)^{p}=\mathcal{W}_{p}(\alpha,\beta)^{p}$

since $\|\cdot\|_{w,p}\leq\|\cdot\|_{w,1}^{p}$ provided $w_{ij}\geq 1$. ∎

If we allow for some flexibility when picking the underlying metric $k$ of
$\mathcal{W}_{k,p}$, then we can provide a tighter estimate when $\mathcal{W}$
is large.

######  Theorem 2.7.

Let $\alpha,\beta\in\mathcal{P}(V)$, $1<p<\infty$ and let $q$ be the conjugate
of $p$ such that $\frac{1}{p}+\frac{1}{q}=1$. Then

(34) $\displaystyle\mathcal{B}_{p}(\alpha,\beta)\leq
n^{2/q}\mathcal{W}_{d_{p},p}(\alpha,\beta).$

The proof of Theorem 2.7 follows mainly from Hölder’s inequality and
Proposition 2.5; we provide the proof in Section A.1. Note in particular that
when $p=2$, we have $q=2$ and thus it holds $\mathcal{B}_{2}(\alpha,\beta)\leq
n\mathcal{W}_{d_{2},2}(\alpha,\beta)$.

####  2.2.2 Estimating from the $p=1$ case

When $p=1$ and the choice of metric is $k=d_{1}$ there is a direct overlap
between $\mathcal{B}_{1}$ and $\mathcal{W}_{1}$ [62, 28].

######  Theorem 2.8.

Let $\alpha,\beta\in\mathcal{P}(V)$. Then

$\mathcal{B}_{1}(\alpha,\beta)=\mathcal{W}_{1}(\alpha,\beta).$

For a proof of this result, we recommend the exposition in [62, Ch. 6]. Note
that for $p\geq 1$ and $J\in\ell(E^{\prime})$, we have that since
$\|\cdot\|_{p}\leq\|\cdot\|_{1}$ in general,

$\|J\|_{w,p}=\|W^{1/p}J\|_{p}\leq\|W^{1/p}J\|_{1}\leq\|J\|_{w,1}\left(\max_{e\in
E^{\prime}}w_{e}^{1/p-1}\right).$

Thus if $C_{w,p}=\max_{e\in E^{\prime}}w_{e}^{1/p-1}$ we have $\|J\|_{w,p}\leq
C_{w,p}\|J\|_{w,1}$. If $J^{\ast}$ is an optimal flow for
$\mathcal{B}_{1}(\alpha,\beta)$, we have

(35) $\displaystyle\mathcal{B}_{p}(\alpha,\beta)\leq\|J^{\ast}\|_{w,p}\leq
C_{w,p}\|J^{\ast}\|_{w,1}=C_{w,p}\mathcal{B}_{1}(\alpha,\beta)$

Therefore, we have the following two estimates for any choice of
$\alpha,\beta$ and $p\geq 1$.

######  Corollary 2.9.

Let $\alpha,\beta\in\mathcal{P}(V)$ and $1\leq p<\infty$. Then the following
estimates hold:

(36) $\displaystyle\mathcal{B}_{p}(\alpha,\beta)$ $\displaystyle\leq
C_{w,p}\mathcal{B}_{1}(\alpha,\beta)$ (37)
$\displaystyle\mathcal{B}_{p}(\alpha,\beta)$ $\displaystyle\leq
C_{w,p}\mathcal{W}_{1}(\alpha,\beta)$

Moreover, via similar logic as before, since $\|\cdot\|_{1}\leq
m^{1-1/p}\|\cdot\|_{p}$ on $\ell(E^{\prime})$, where we recall $m=|E|$, we
have for $J\in\ell(E^{\prime})$,

(38) $\displaystyle\|J\|_{w,1}=\|WJ\|_{1}\leq m^{1-1/p}\|WJ\|_{p}\leq
m^{1-1/p}\|W\mathbf{1}_{E^{\prime}}\|_{\infty}^{\frac{p-1}{p}}\|J\|_{w,p}$

Therefore if we set
$C_{w,m,p}=m^{1-1/p}\|W\mathbf{1}_{E^{\prime}}\|_{\infty}^{\frac{p-1}{p}}$, we
have $\|J\|_{w,1}\leq C_{w,m,p}\|J\|_{w,p}$ and using a similar argument as
before, the following corollary holds.

######  Corollary 2.10.

Let $\alpha,\beta\in\mathcal{P}(V)$ and $1\leq p<\infty$. Then the following
estimates hold:

(39) $\displaystyle\mathcal{B}_{1}(\alpha,\beta)$ $\displaystyle\leq
C_{w,m,p}\mathcal{B}_{p}(\alpha,\beta)$ (40)
$\displaystyle\mathcal{W}_{1}(\alpha,\beta)$ $\displaystyle\leq
C_{w,m,p}\mathcal{B}_{p}(\alpha,\beta)$

An application of this allows us to relate $2$-Beckmann distance to
$\mathcal{W}_{1}$, which we state as a corollary below.

######  Corollary 2.11.

Let $\alpha,\beta\in\mathcal{P}(V)$. Then

(41) $\displaystyle\mathcal{B}_{2}(\alpha,\beta)\leq
C_{w,2}\mathcal{W}_{1}(\alpha,\beta)\leq
C_{w,2}C_{w,m,2}\mathcal{B}_{2}(\alpha,\beta).$

If in particular the graph is unweighted, then we have that $C_{w,2}=1$ and
$C_{w,m,2}=m^{1/2}$, so that

(42)
$\displaystyle\mathcal{B}_{2}(\alpha,\beta)\leq\mathcal{W}_{1}(\alpha,\beta)\leq
m^{1/2}\mathcal{B}_{2}(\alpha,\beta).$

######  Remark 2.12.

Note that the bound in Corollary 2.11 is sharp without making additional
assumptions on the structure of $G$ or $\alpha,\beta$. Suppose $G$ is a path
on $n$ vertices with $m=n-1$, then the upper and lower bounds are achieved,
respectively, when we have:

  1. (i)

$\alpha=\delta_{1}$, $\beta=\delta_{n}$, so that
$\mathcal{B}_{2}(\delta_{1},\delta_{n})=\sqrt{n-1}$ and
$\mathcal{W}_{1}(\delta_{1},\delta_{n})=n-1$ so
$\mathcal{W}_{1}=m^{1/2}\mathcal{B}_{2}$.

  2. (ii)

$\alpha=\delta_{1}$ and $\beta=\delta_{2}$, so that
$\mathcal{B}_{2}=\mathcal{W}_{1}=1$.

Proofs of these statements could be obtained directly or by way of Proposition
2.13 and Proposition 2.14, which we discuss in the next subsection. This leads
to an as-yet open question: If one constrains the structure of $G$ or
$\alpha,\beta$, can the bound in Corollary 2.11 be improved?

###  2.3 Worked examples: Paths and trees

$\alpha(i)$$i$$\frac{1}{2}$$1$$\frac{1}{2}$$2$$0$$3$$\beta(i)$$0$$\frac{1}{4}$$\frac{3}{4}$
(a) Illustration of two copies of $P_{3}$ with arrows indicating orientation
of the edges. Example probability measures $\alpha,\beta$ are shown with node
color opacity proportional to mass.

$K_{\alpha}(e)$$e$$(1,2)$$\frac{1}{2}$$(2,3)$$1$$K_{\beta}(e)$$0$$\frac{1}{4}$
(b) Illustration of two copies of $P_{3}$ with arrows indicating orientation
of the edges. The edge cdfs $K_{\alpha}$ and $K_{\beta}$ are shown with edge
color opacity proportional to value.

$0$$1$$2$$3$$0$$0.25$$0.5$$0.75$$1$$F_{\widehat{\alpha}}(x)$$F_{\widehat{\beta}}(x)$$x$
(c) Plots of the cdfs $F_{\widehat{\alpha}},F_{\widehat{\beta}}$ of the
empirical measures $\widehat{\alpha},\widehat{\beta}$ on $\mathbb{R}$. From
Proposition 2.14 we have $\mathcal{B}_{p}(\alpha,\beta)^{p}=0.5^{p}+0.75^{p}$.

$0$$0.25$$0.5$$0.75$$1$$0$$1$$2$$3$$F_{\widehat{\alpha}}^{-1}(t)$$\hskip
170.71652ptF_{\widehat{\beta}}^{-1}(t)$$t$ (d) Plots of the inverse cdfs
$F_{\widehat{\alpha}}^{-1}$ and $F_{\widehat{\beta}}^{-1}$ of the empirical
measure $\widehat{\alpha},\widehat{\beta}$ on $\mathbb{R}$. From Proposition
2.13 we have
$\mathcal{W}_{p}(\alpha,\beta)^{p}=1^{p}(0.25)+2^{p}(0.25)+1^{p}(0.5)$.

Figure 2: (a)-(b) Illustrations of two measures $\alpha,\beta$ and their edge
cdfs $K_{\alpha},K_{\beta}$ for the fixed path graph $P_{3}$. (c)-(d) Plots of
the empirical cdfs $F_{\widehat{\alpha}}$ and $F_{\widehat{\beta}}$, as well
as their inverses. Note that the shaded regions are reflections of each other;
and that for $p=1$ their common area is
$\mathcal{B}_{1}(\alpha,\beta)=\mathcal{W}_{1}(\alpha,\beta)$. This also
demonstrates the divergence of the metrics for $p>1$.

In this subsection, we specialize to the case of the path graph $P_{n}$ and
derive explicit formulas for $\mathcal{W}_{p}$ and $\mathcal{B}_{p}$ so as to
illustrate their connections to optimal transportation in the setting of the
real line and to elucidate their differences when $p>1$. We also take a look
at $\mathcal{B}_{p}$ on tree graphs, and obtain a closed-form solution for all
$1\leq p<\infty$ which generalizes the known formula for 1-Wasserstein
distance on trees. Proofs of Proposition 2.13, Proposition 2.14, and
Proposition 2.15 are all included in Section A.1.

Let $P_{n}$ be the unweighted path graph with $n$ nodes ordered from $1$ to
$n$, and oriented edges $E^{\prime}$ of the form $(i,i+1)$ for $1\leq i\leq
n-1$. For $\alpha\in\mathcal{P}(V(P_{n}))$, let
$\widehat{\alpha}=\sum_{i=1}^{n}\alpha(i)\delta_{i}$ be the empirical measure
on $\mathbb{R}$ induced by $\alpha$ where, with a slight abuse of notation,
$\delta_{i}$ is the Dirac measure on $\mathbb{R}$ at $x=i$. Let
$F_{\widehat{\alpha}}$ be the cumulative distribution function of
$\widehat{\alpha}$, and let $F_{\widehat{\alpha}}^{-1}$ be its psuedo-inverse
or quantile function, i.e.,
$F_{\widehat{\alpha}}^{-1}(t)=\inf\\{x:F_{\widehat{\alpha}}(x)\geq t\\}$ for
$t\in[0,1]$. The proposition below is an adaptation of the classical inverse
cdf result for $\mathcal{W}_{p}$ on $\mathbb{R}$ to the case of path graphs;
for more detail, see, e.g., [64, 71].

######  Proposition 2.13.

Let $\alpha,\beta\in\mathcal{P}(V(P_{n}))$ and $1\leq p<\infty$. Then the
$p$-Wasserstein distance $\mathcal{W}_{p}(\alpha,\beta)$ on $P_{n}$ is given
by

(43)
$\displaystyle\mathcal{W}_{p}(\alpha,\beta)^{p}=\int_{0}^{1}\left|F_{\widehat{\alpha}}^{-1}(t)-F_{\widehat{\beta}}^{-1}(t)\right|^{p}{\mathrm{d}}t.$

To characterize $p$-Beckmann distance on $P_{n}$, we introduce a bit more
notation. For $\alpha\in\mathbb{P}(V)$ and an oriented edge $e=(i,i+1)\in
E^{\prime}$, let $K_{\alpha}\in\ell(E^{\prime})$ be the “edge cdf,” i.e.,

(44) $\displaystyle K_{\alpha}(i,i+1)=\sum_{j\leq i}\alpha(j).$

Note that, naturally, $K_{\alpha}(i,i+1)=F_{\widehat{\alpha}}(i)$.

######  Proposition 2.14.

Let $\alpha,\beta\in\mathcal{P}(V(P_{n}))$ and $1\leq p<\infty$. Then the
$p$-Beckmann distance $\mathcal{B}_{p}(\alpha,\beta)$ on $P_{n}$ is given by

(45)
$\displaystyle\mathcal{B}_{p}(\alpha,\beta)^{p}=\|K_{\alpha}-K_{\beta}\|_{p}^{p}=\int_{\mathbb{R}}|F_{\widehat{\alpha}}(t)-F_{\widehat{\beta}}(t)|^{p}{\mathrm{d}}t.$

Proposition 2.13 and Proposition 2.14 provide an alternate, albeit circuitous,
proof of Theorem 2.8 on paths by applying a change of variables. This also
demonstrates why we do not expect the two families of metrics to overlap for
$p>1$. A worked example of Proposition 2.13 and Proposition 2.14 in action is
illustrated in Fig. 2.

It is also intriguing to note that much in the same way that
$\mathcal{W}_{1}$, and hence $\mathcal{B}_{1}$, is determined explicitly on
trees (a result which itself has been leveraged in other applications such as
computer vision and natural language processing [79, 53, 90, 80, 31, 45]),
$\mathcal{B}_{p}$ can be determined in an similar manner for general $p$ on
trees.

######  Proposition 2.15.

Let $T=(V,E,w)$ be a weighted tree, $\alpha,\beta\in\mathcal{P}(V)$, and fix
$1\leq p<\infty$. For an oriented edge $e=(i,j)\in E^{\prime}$, define a
generalized version of Eq. 44 by

$K_{\alpha}(e=(i,j))=\sum_{k\in V^{\ast}(i;e)}\alpha(k),$

where $V^{\ast}(i;e)\subset V$ is the set of nodes belonging to the subtree
with root $i$ obtained from $T$ by removing the edge $e$ (and similarly for
$K_{\beta}$). Then it holds

(46)
$\displaystyle\mathcal{B}_{p}(\alpha,\beta)=\|K_{\alpha}-K_{\beta}\|_{w,p}.$

##  3 The 2-Beckmann problem: Three perspectives

This section is focused entirely on $\mathcal{B}_{2}$. The foundational
premise of this section is that $\mathcal{B}_{2}$, while ostensibly a simple
least squares optimization problem, actually posesses a rich supply of
connections and contexts to other notions that already exist in graph theory.
In Section 3.1 we view $\mathcal{B}_{2}$ as an effective resistance metric
between measures, and connect it to the simple random walk on $G$ and optimal
stopping times for measures. In Section 3.2, we view $\mathcal{B}_{2}$ as a
negative Sobolev norm for functions on graphs, and thereby obtain a Benamou-
Brenier type formula for $\mathcal{B}_{2}$. Lastly, in Section 3.3, we view
$\mathcal{B}_{2}$ as a linearized variant of $\mathcal{W}_{2}$, prove a convex
separation result, and showcase its potential application in unsupervised
learning problems for graph data.

###  3.1 Effective resistance between measures

In this subsection we consider $\mathcal{B}_{2}$ from the perspective of
effective resistance. We begin with some supplemental background on effective
resistance which will be needed, and then proceed with discussion of the main
results.

####  3.1.1 Background on effective resistance

######  Definition 3.1.

Let $i,j\in V$ be any two nodes. The effective resistance between $i,j$,
denoted $r_{ij}$, is given by the formula

(47) $\displaystyle
r_{ij}=(\delta_{i}-\delta_{j})^{T}L^{\dagger}(\delta_{i}-\delta_{j}).$

The effective resistance between the nodes of a graph has many different
properties and representations, many of which intersect with the simple random
walk on $G$. We give its definition and some of its properties below.

######  Definition 3.2.

The simple random walk on $G$ is the Markov chain $(X_{t})_{t\geq 0}$ on the
state space of nodes $V$ with transition probability matrix $D^{-1}A$; that
is,

$\mathbb{P}[X_{t+1}=j|X_{t}=i]=\begin{cases}\frac{w_{ij}}{d_{i}}&\text{ if
}i\sim j\\\ 0&\text{otherwise }\end{cases}.$

Recall that $X_{t}$ will admit a stationary distribution whenever $G$ is
connected and will be ergodic whenever $G$ is also non-bipartite. The
stationary distribution, which we denote $\rho$, is always proportional to the
degree at each node. A useful tool is the vertex hitting time

(48) $\displaystyle T^{s}_{j}=\inf\left\\{t\geq s:X_{t}=j\right\\},\hskip
14.22636pts\geq 0,j\in V.$

Also, let ${\operatorname{vol}}(G)=\sum_{i\in V}d_{i}$ denote the volume of
the graph $G$.

######  Proposition 3.3.

Let $i,j\in V$ be any two nodes. Then the following observations hold

  1. (i)

$(i,j)\mapsto r_{ij}$ is a metric on $V$,

  2. (ii)

$(i,j)\mapsto r_{ij}^{1/2}$ is a metric on $V$,

  3. (iii)

$r_{ij}=\inf\\{f^{T}Lf:Lf=\delta_{i}-\delta_{j}\\}$,

  4. (iv)

$r_{ij}=\|L^{-1/2}(u_{i}-u_{j})\|_{2}^{2}$, where $u_{i}$ is the $i$-th
orthonormal eigenvector of the graph Laplacian $L$.

  5. (v)

$r_{ij}=\frac{1}{\mathrm{vol}(G)}\left(\mathbb{E}[T^{0}_{i}:X_{0}=j]+\mathbb{E}[T^{0}_{j}:X_{0}=i]\right)$,
i.e., $r_{ij}$ is proportional to the commute time between $i,j$.

For proofs of these results, see, e.g., [40, 50, 25].

####  3.1.2 $2$-Beckmann as measure effective resistance

We begin with the observation that $\mathcal{B}_{2}(\alpha,\beta)^{2}$ can be
realized as a type of effective resistance for measures. We make this precise
in the theorem below.

######  Theorem 3.4.

Let $\alpha,\beta\in\mathcal{P}(V)$. Then

(49)
$\displaystyle\mathcal{B}_{2}(\alpha,\beta)^{2}=(\alpha-\beta)^{T}L^{\dagger}(\alpha-\beta).$

###### Proof.

We can write

(50) $\displaystyle\mathcal{B}_{2}(\alpha,\beta)^{2}$
$\displaystyle=\inf\\{\|J\|_{w,2}^{2}:BJ=\alpha-\beta\\}$ (51)
$\displaystyle=\inf\\{\|W^{1/2}J\|_{2}^{2}:BJ=\alpha-\beta\\}$ (52)
$\displaystyle=\inf\\{\|S\|_{2}^{2}:(BW^{-1/2})S=\alpha-\beta\\}$

with $S=W^{1/2}J$. Recall that for matrices $X,x$ it holds that
$X^{\dagger}x=\mathrm{argmin}\\{\|y\|_{2}:Xy=x\\}$ when $x$ belongs to the
column space of $X$ [6], and thus we have

(53) $\displaystyle\mathcal{B}_{2}(\alpha,\beta)^{2}$
$\displaystyle=\|(BW^{-1/2})^{\dagger}(\alpha-\beta)\|_{2}^{2}$ (54)
$\displaystyle=(\alpha-\beta)^{T}((BW^{-1/2})^{\dagger})^{T}(BW^{-1/2})^{\dagger}(\alpha-\beta)$
(55) $\displaystyle=(\alpha-\beta)^{T}L^{\dagger}(\alpha-\beta)$

since $L=BWB^{T}$. ∎

One immediate consequence of Theorem 3.4 is a Brenier-type theorem for graphs,
which we state as a corollary below. Based on the discussion following Eq. 12,
in this theorem we opt to use the notation $B^{T}=\nabla$ to achieve homophily
with the continuous setting.

######  Corollary 3.5.

Let $\alpha,\beta\in\mathcal{P}(V)$. The unique optimal edge flow $J^{\ast}$
for $\mathcal{B}_{2}(\alpha,\beta)$ can be written $J^{\ast}=\nabla f$ where
$f$ is a mean-zero potential function of minimal $\ell_{2}$ norm satisfying
the Poisson-type equation $Lf=\alpha-\beta$. The optimal cost is $\|\nabla
f\|_{w,2}$.

###### Proof.

It is enough to write
$(\alpha-\beta)^{T}L^{\dagger}(\alpha-\beta)=(\alpha-\beta)^{T}L^{\dagger}LL^{\dagger}(\alpha-\beta)$
and $L=BWB^{T}$. The claim then follows from the proof of Theorem 3.4. ∎

Based on the Theorem 3.4, we introduce the following definition and notation
of effective resistance for measures.

######  Definition 3.6.

Let $\alpha,\beta\in\mathcal{P}(V)$. Then we define the measure effective
resistance by

(56) $\displaystyle
r_{\alpha\beta}=(\alpha-\beta)^{T}L^{\dagger}(\alpha-\beta).$

In the subsequent sections, we will explore the properties of
$r_{\alpha\beta}$ in its own right, with particular focus on its relationship
to optimal stopping rules of the simple random walk.

####  3.1.3 Measure effective resistance and optimal stopping rules

We have already argued in Theorem 3.4 that measure effective resistance can be
understood as a type of flow-based optimal transportation distance between the
measures. The goal of this section is to essentially set that aside and think
about $r_{\alpha\beta}$ in its own right. A natural approach along these lines
is to take Proposition 3.3 as a starting point. Immediately, $r_{\alpha\beta}$
has several analagous properties, which we state below without proof.

######  Proposition 3.7.

Let $\alpha,\beta\in\mathcal{P}(V)$. Then the following statements hold:

  1. (i)

$(\alpha,\beta)\mapsto r_{\alpha\beta}^{1/2}$ is a metric on $\mathcal{P}(V)$,

  2. (ii)

$r_{\alpha\beta}=\inf\left\\{f^{T}Lf:Lf=\alpha-\beta\right\\}$,

  3. (iii)

$r_{\alpha\beta}=\|L^{-1/2}(\alpha-\beta)\|_{2}^{2}$.

To go deeper, we pose the following question along the lines of Proposition
3.3(v): To what extent can $r_{\alpha\beta}$ be understood as a generalized
commute time between the measures $\alpha,\beta$? To answer this question, we
need to use results that concern stopping rules for the simple random walk.

######  Definition 3.8.

A stopping rule is a map $\Gamma$ that associates to each finite path
$\omega=(X_{0},X_{1},\dotsc,X_{k})$ on $G$ a number $\Gamma(\omega)$ in
$[0,1]$. We can think of $\Gamma(\omega)$ as the probability that we continue
a random walk given that $\omega$ is the walk so far observed. Alternatively,
$\Gamma$ can be considered a random variable taking values in
$\\{0,1,2,\dotsc\\}$ whose distribution depends only on the steps
$(X_{0},X_{1},\dotsc,X_{\Gamma})$.

The mean length $\mathbb{E}[\Gamma]$ is the expected duration of the walk. If
$\mathbb{E}[\Gamma]<\infty$ then the walk stops almost surely in finite time,
so we define $X_{\Gamma}$ to be the position of the random walk at the
stopping time. Having defined stopping rules, we can define the generalized
hitting time between $\alpha,\beta$.

######  Definition 3.9.

Let $\alpha,\beta\in\mathcal{P}(V)$. The access time $H(\alpha,\beta)$ is
defined as

(57) $\displaystyle
H(\alpha,\beta)=\inf\left\\{\mathbb{E}[\Gamma|X_{0}\sim\alpha]:\mathbb{E}[\Gamma]<\infty,\text{
and }X_{\Gamma}\sim\beta\right\\}.$

where for any random variable $Y$ on $V$, we say $Y\sim\alpha$ if
$\mathbb{P}[Y=i]=\alpha(i)$ for $i\in V$. In other words, $H(\alpha,\beta)$ is
the minimum mean length of walks that originate with distribution $\alpha$ and
terminate according to a stopping rule that achieves distribution $\beta$ at
stopping time. If $\Gamma$ achieves the $\inf$ in $H(\alpha,\beta)$, then
$\Gamma$ is said to be an optimal stopping rule.

######  Remark 3.10.

It is not hard to see that the set of feasible stopping rules in Definition
3.9 is nonempty. The so-called “naïve” stopping rule $\Gamma_{n}$ can be
obtained from the following construction: at the beginning of the random walk,
sample $j\sim\beta$, and stop the walk when $X_{\Gamma_{n}}=j$. It is readily
verified that $X_{\Gamma_{n}}\sim\beta$, and that

$\mathbb{E}[\Gamma_{n}]=\sum_{i,j\in V}\alpha_{i}\beta_{j}H(i,j)$

where for $i,j\in V$, the hitting time $H(i,j)$ is defined by
$H(i,j)=H(\delta_{i},\delta_{j})$ (or, the mean number of steps to reach $j$
from $i$).

$\alpha$$\beta$ (a) Initial distribution $\alpha$, stopping distribution
$\beta$.

$\alpha$$\beta$ (b) Initial distribution $\beta$, stopping distribution
$\alpha$.

Figure 3: Two illustrations of 1000 simulated simple random walks on the
dodecahedral graph with given initial distribution, illustrated with node
opacity proportional to density; and naïve stopping rule according to the
given stopping distribution, illustrated with opposite node color and opacity
proportional to density. The edges are dashed only to indicate depth, and edge
opacity is proportional to the total number of times the simulated random
walks landed on each edge. The mean lengths of paths in (a) (resp. (b))
correspond to $H_{n}(\alpha,\beta)$ (resp. $H_{n}(\beta,\alpha))$.

Several examples of optimal stopping rules for general distributions are given
in [52], and in particular, it is shown thereby that any such $\alpha,\beta$
admit an optimal stopping rule provided $G$ is connected.

The access time $H(\alpha,\beta)$ has several notable properties, which we
summarize in the Proposition below. The proofs of these results can be found
in [52].

######  Proposition 3.11.

Let $\alpha,\beta\in\mathcal{P}(V)$. Then the following facts hold for
$H(\alpha,\beta)$:

  1. (i)

When $\beta$ is concentrated at a node $j\in V$, it holds
$H(\alpha,j)=\sum_{i\in V}\alpha_{i}H(i,j)$,

  2. (ii)

$H(\alpha,\beta)=\max_{j}\sum_{i\in V}(\alpha_{i}-\beta_{i})H(i,j)$,

  3. (iii)

$H(\alpha,\beta)$ is convex in both of its arguments; namely if
$\alpha,\alpha^{\prime},\beta,\beta^{\prime}\in\mathcal{P}(V)$ and
$c\in[0,1]$, we have

(58) $\displaystyle H(c\alpha+(1-c)\alpha^{\prime},\beta)$ $\displaystyle\leq
cH(\alpha,\beta)+(1-c)H(\alpha^{\prime},\beta)$ (59) $\displaystyle
H(\alpha,c\beta+(1-c)\beta^{\prime})$ $\displaystyle\leq
cH(\alpha,\beta)+(1-c)H(\alpha,\beta^{\prime})$

Beveridge [8] also established a connection between the entries of the
psuedoinverse of the graph Laplacian (treated as a discrete Green’s function)
and the access time between nodes and the stationary distribution of the
random walk. We reproduce that formula here as a proposition, in a modified
form to match our conventional choice of Laplacian matrix.

######  Theorem 3.12 (Access Time Formula for the Discrete Green’s Function,
Beveridge [8]).

Let $\rho$ be the stationary distribution of the simple random walk on $V$.
Then the $i,j$-th entry of $L^{\dagger}$ can be expressed as

(60)
$\displaystyle(L^{\dagger})_{ij}=\frac{1}{{\operatorname{vol}}(G)}\left(H(\rho,j)-H(i,j)\right),$

where ${\operatorname{vol}}(G)=\sum_{i\in V}d_{i}$.

For $\alpha\in\mathcal{P}(V)$, define $H_{\alpha}\in\ell(V)$ by
$H_{\alpha}(i)=H(\alpha,i)$. We are ready to state our main result connecting
$r_{\alpha\beta}$ to the access time.

######  Theorem 3.13 (Generalized Commute Time Formula).

Let $\alpha,\beta\in\mathcal{P}(V)$. Then

(61) $\displaystyle
r_{\alpha\beta}=-\frac{1}{{\operatorname{vol}}(G)}(\alpha-\beta)^{T}(H_{\alpha}-H_{\beta}).$

Or, in alternative expanded forms,

(62) $\displaystyle r_{\alpha\beta}$
$\displaystyle=-\frac{1}{{\operatorname{vol}}(G)}\sum_{i\in
V}(\alpha_{i}-\beta_{i})(H(\alpha,i)-H(\beta,i))$ (63)
$\displaystyle=-\frac{1}{{\operatorname{vol}}(G)}\sum_{i,k\in
V}(\alpha_{i}-\beta_{i})(\alpha_{k}-\beta_{k})H(i,k).$

We provide the proof in Section A.2. The reason we term Theorem 3.13 a
generalized commute time formula is that in the case where $\alpha,\beta$ are
Dirac measures, this recovers the result that $r_{ij}\propto(H(i,j)+H(j,i))$,
since we have

(64) $\displaystyle r_{i}j$
$\displaystyle=-\frac{1}{{\operatorname{vol}}(G)}(\delta_{i}-\delta_{j})^{T}(H_{\delta_{i}}-H_{\delta_{j}})$
(65)
$\displaystyle=-\frac{1}{{\operatorname{vol}}(G)}(H(i,i)-H(i,j)+H(j,j)-H(j,i)$
(66) $\displaystyle=\frac{1}{{\operatorname{vol}}(G)}(H(i,j)+H(j,i)).$

Theorem 3.13 shows, however, that in the more general case of measures
$r_{\alpha\beta}$ is not exactly the same as a measure commute time
$H(\alpha,\beta)+H(\beta,\alpha)$. Theorem 3.13 can be used to establish a
relationship between the measure commute time and the measure resistance, as
we show below.

######  Corollary 3.14 (Measure Commute Time Inequalities).

Let $\alpha,\beta\in\mathcal{P}(V)$. Then $r_{\alpha\beta}$ satisfies the
following two inequalities:

(67) $\displaystyle r_{\alpha\beta}$
$\displaystyle\leq\frac{2}{{\operatorname{vol}}(G)}\max\\{H(\alpha,\beta),H(\beta,\alpha)\\}$
(68) $\displaystyle r_{\alpha\beta}$
$\displaystyle\leq\frac{1}{{\operatorname{vol}}(G)}(H_{n}(\alpha,\beta)+H_{n}(\beta,\alpha))$

where $H_{n}(\alpha,\beta)=\mathbb{E}[\Gamma_{n}]$ (resp.
$H_{n}(\beta,\alpha)$) is the expected duration of the naïve stopping rule
described in Remark 3.10 with initial distribution $\alpha$ (resp. $\beta$)
and stopping node sampled from $\beta$ (resp. $\alpha$).

The proof of Corollary 3.14 is located in Section A.2. Note that the second
half of the proof of Corollary 3.14 actually contains a related observation
regarding $\mathcal{B}_{2}$ and $\mathcal{W}_{r,1}$, which we state as another
corollary below, without proof.

######  Corollary 3.15.

Let $\alpha,\beta\in\mathcal{P}(V)$, and let $r$ be the effective resistance
metric on $V$. Then we have

$\mathcal{B}_{2}(\alpha,\beta)\leq\mathcal{W}_{r,1}(\alpha,\beta)^{1/2}.$

A final observation that one can glean from the random walk and access time
setting is an interpretation of the transportation potential
$f=L^{\dagger}(\alpha-\beta)$ mentioned in Corollary 3.5.

######  Proposition 3.16.

Let $\alpha,\beta\in\mathcal{P}(V)$, and let $\Gamma$ be any stopping rule
such that $\mathbb{E}[\Gamma]<\infty$ and $X_{\Gamma}\sim\beta$. Let
$f_{\Gamma}$ be the degree-weighted exit frequencies

$f_{\Gamma}(i)=\mathbb{E}\left[\sum_{t=0}^{\Gamma-1}\frac{1}{d_{i}}\delta_{\\{X_{t}=i\\}}(i):X_{0}\sim\alpha\right].$

Then $Lf_{\Gamma}=\alpha-\beta$. In particular, the transportation potential
$L^{\dagger}(\alpha-\beta)$ is given by the mean normalized function
$f_{\Gamma}-\frac{1}{n}f_{\Gamma}^{T}\mathbf{1}_{n}$ for any suitable stopping
rule $\Gamma$.

This proposition follows from applying the so-called conservation equation for
exit frequencies, mentioned in, e.g., [52, 51]. Another way of putting it is
that the unique optimal flow for $\mathcal{B}_{2}(\alpha,\beta)$ can be
realized as the gradient of the degree-normalized exit frequencies of any
finite-mean stopping rule which achieves a stopping distribution of $\beta$,
having been intialized at $\alpha$ (since, moreover, as discussed in [51], any
two degree-normalized exit frequencies for different stopping times differ by
a constant, and thus have the same gradient).

###  3.2 Sobolev norms and a graph Benamou-Brenier formula

The relationship between Sobolev spaces and optimal transportation have been
explored at length in the continuous setting [84, 63, 37, 77]. The goal of
this subsection is to present the 2-Beckmann problem as an optimization
problem on a negative Sobolev space for functions defined on graphs. In this
section we follow the exposition laid out in [63] in the continuous setting by
analogy to the discrete setting. As it turns out, there are at least two
results that achieve strong homophily between the graph and continuous
setting.

####  3.2.1 Background from the continuous setting

Recall that if $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is a function with a
square integrable derivative $\nabla f$ in the weak sense and $\mu$ is a Borel
probability measure which is absolutely continuous with respect to the
Lebesgue measure ${\mathrm{d}}x$; i.e. so that
${\mathrm{d}}\mu=g{\mathrm{d}}x$ for a density function $g$, we can define the
Sobolev-type seminorm $\|\cdot\|_{\dot{H}^{1}(\mu)}^{2}$ by

(69) $\displaystyle\|f\|_{\dot{H}^{1}(\mu)}^{2}=\int_{\mathbb{R}^{n}}\|\nabla
f\|_{2}^{2}{\mathrm{d}}\mu.$

The dot $\dot{H}^{1}(\mu)$ serves to distinguish
$\|\cdot\|_{\dot{H}^{1}(\mu)}^{2}$ from a true Sobolev norm, which include a
contribution from $\|\cdot\|_{L^{2}}$. We can then define the possibly
infinite dual norm to $\|f\|_{\dot{H}^{1}(\mu)}^{2}$, denoted
$\|\cdot\|_{\dot{H}^{-1}(\mu)}$ by the following, for any ${\mathrm{d}}x$\-
absolutely continuous signed measure $\nu=h{\mathrm{d}}x$:

(70)
$\displaystyle\|h{\mathrm{d}}x\|_{\dot{H}^{-1}(\mu)}=\sup\left\\{\int_{\mathbb{R}^{n}}fhd\mu:\|f\|_{\dot{H}^{1}(\mu)}\leq
1\right\\}.$

This setup leads to two results (among others) in the continuous setting,
which are of interest in the graph setting as well.

######  Theorem 3.17 ($\dot{H}^{-1}$ \- Linearization of $\mathcal{W}_{2}$
[63]).

If $\mu$ is a Borel probability measure on $\mathbb{R}^{n}$ and
${\mathrm{d}}\mu$ is an infintesimally small perturbation of $\mu$, then

$\mathcal{W}_{2}(\mu,\mu+{\mathrm{d}}\mu)=\|{\mathrm{d}}\mu\|_{\dot{H}^{-1}(\mu)}+o({\mathrm{d}}\mu).$

The second result which interests us is the Sobolev form of the Benamou-
Brenier formula, which we state below.

######  Theorem 3.18 (Benamou-Brenier formula, $\dot{H}^{-1}$ form [63]).

Let $\mu,\nu$ be Borel probability measures on $\mathbb{R}^{n}$. Then it
holds:

(71)
$\displaystyle\mathcal{W}_{2}(\mu,\nu)=\inf\left\\{\int_{0}^{1}\|{\mathrm{d}}\mu_{t}\|_{\dot{H}^{-1}(\mu_{t})}:\mu_{0}=\mu,\mu_{1}=\nu\right\\}.$

####  3.2.2 Graph sobolev norms

Next we transition to defining the appropriate discrete analogues of
$\|\cdot\|_{\dot{H}^{1}(\mu)}$ and $\|\cdot\|_{\dot{H}^{-1}(\mu)}$ on the
graph $G$.

######  Definition 3.19.

Let $f,g\in\ell(V)$. We define the graph Sobolev seminorm
$\|\cdot\|_{\dot{H}^{1}(V)}$ by the equation

(72) $\displaystyle\|f\|_{\dot{H}^{1}(V)}^{2}=\sum_{(i,j)\in
E^{\prime}}w_{ij}|\nabla f(i,j)|_{2}^{2}=\sum_{(i,j)\in
E^{\prime}}w_{ij}|f(i)-f(j)|_{2}^{2}.$

We define the (possibly infinite) dual graph Sobolev norm
$\|\cdot\|_{\dot{H}^{-1}(V)}$ by the supremum

(73)
$\displaystyle\|g\|_{\dot{H}^{-1}(V)}^{2}=\sup\left\\{f^{T}g:\|f\|_{\dot{H}^{1}(V)}\leq
1\right\\}.$

It is useful to note that for mean zero functions,
$\|\cdot\|_{\dot{H}^{1}(V)}$ and $\|\cdot\|_{\dot{H}^{-1}(V)}$ will be true
norms (in particular, the former will be definite and the latter will be
finite). The first proposition in the section elucidates the relationship
between graph Sobolev norms and the graph Laplacian matrix.

######  Proposition 3.20.

Let $f,g\in\ell(V)$. Then the following hold:

  1. (i)

$\|f\|_{\dot{H}^{1}(V)}^{2}=f^{T}Lf$.

  2. (ii)

If $\mathbf{1}^{T}g=0$, then $\|g\|_{\dot{H}^{-1}(V)}^{2}=g^{T}L^{\dagger}g$.

###### Proof.

The first claim is straightforward. The second requires a closer look. We can
work backwards and use the proof of Theorem 2.1 to obtain

(74) $\displaystyle(g^{T}L^{\dagger}g)^{1/2}$
$\displaystyle=\|L^{-1/2}g\|_{2}$ (75)
$\displaystyle=\inf\\{\|f\|_{2}:L^{1/2}f=g\\}$ (76)
$\displaystyle=\sup\left\\{f^{T}g:\|L^{1/2}f\|_{2}\leq 1\right\\},$

where $L^{\\{-1/2,1/2\\}}=U\Lambda^{\\{-1/2,1/2\\}}U^{T}$ as in Eq. 10. But
$\|L^{1/2}f\|_{2}^{2}=f^{T}Lf=\|f\|_{\dot{H}^{1}(V)}^{2}$, so the claim
follows. ∎

####  3.2.3 $2$-Beckmann as a negative Sobolev distance

Since our definitions have been set up and explained properly, we can derive
the following result, which follows directly from Proposition 3.20 and Theorem
3.4. We consider this a graph analogue of Theorem 3.17 for $2$-Beckmann
distance.

######  Theorem 3.21.

Let $\alpha,\beta\in\mathcal{P}(V)$. Then

$\mathcal{B}_{2}(\alpha,\beta)=\|\alpha-\beta\|_{\dot{H}^{-1}(V)}.$

Thus in particular if $\beta=\alpha+{\mathrm{d}}\alpha$ for a small
perturbation ${\mathrm{d}}\alpha$, then
$\mathcal{B}_{2}(\alpha,\alpha+{\mathrm{d}}\alpha)=\|{\mathrm{d}}\alpha\|_{\dot{H}^{-1}(V)}$.

Note that since the $\dot{H}^{-1}$ norm depends on the operator $L^{-1/2}$,
the Beckmann distance $\mathcal{B}_{2}(\alpha,\alpha+{\mathrm{d}}\alpha)$ can
be articulated in terms of the spectral coefficients of ${\mathrm{d}}\alpha$;
to wit, if ${\mathrm{d}}\alpha=\sum_{\ell=2}^{n}c_{\ell}u_{\ell}$ is the
spectral decomposition of a mean-zero perturbation
${\mathrm{d}}\alpha\in\ell(V)$ in terms of the eigenvectors $u_{\ell}$ of $L$,
then

(77)
$\displaystyle\mathcal{B}_{2}(\alpha,\alpha+{\mathrm{d}}\alpha)^{2}=\|L^{-1/2}{\mathrm{d}}\alpha\|_{2}^{2}=\sum_{\ell=2}^{n}\frac{c_{\ell}^{2}}{\lambda_{\ell}}.$

Therefore in general, one has
$\mathcal{B}_{2}(\alpha,\alpha+{\mathrm{d}}\alpha)\leq\lambda_{2}^{-1/2}\|{\mathrm{d}}\alpha\|_{2}$;
but if the spectral properties of ${\mathrm{d}}\alpha$ are known, this
estimate may be sharpened.

The next result which leverages the Sobolev norm perspective on graph optimal
transport can be considered a graph analogue of the Benamou-Brenier formula.
Let $\mu_{t}\in\ell(V)$ for each $t\in[0,1]$. We say $\mu_{t}\in C^{1}([0,1])$
if the map $t\mapsto\mu_{t}:[0,1]\rightarrow\ell(V)$ is continuously
differentiable as a map from $[0,1]$ to $\mathbb{R}^{n}$. Moreover, when
$\mu_{t}$ admits a derivative, we write
${\mathrm{d}}\mu_{t}=\left.\frac{{\mathrm{d}}}{{\mathrm{d}}s}\mu_{s}\right|_{s=t}$.

######  Theorem 3.22 (Graph Benamou-Brenier Formula).

Let $\alpha,\beta\in\mathcal{P}(V)$. Then we have

(78)
$\displaystyle\mathcal{B}_{2}(\alpha,\beta)^{2}=\inf\left\\{\int_{0}^{1}\left\|{\mathrm{d}}\mu_{t}\right\|_{\dot{H}^{-1}(V)}^{2}{\mathrm{d}}t:\mu_{t}\in
C^{1}([0,1]),\mu_{0}=\alpha,\mu_{1}=\beta\right\\}.$

See Section A.2 for a proof, which is based on the proof appearing in the
lecture notes [35]. Note that the infimum is achieved by a linear line segment
connecting $\alpha$ to $\beta$, which underlines the idea that
$\mathcal{B}_{2}$ should be treated as a linearized variant of Wasserstein
distance. We explore the linearization angle and its implications on graph
learning tasks in the next section.

###  3.3 A linearized optimal transportation distance

A third and final perspective on $2$-Beckmann distance is from the world of
clustering and classification of graph data. We begin with a background
discussion from the continuous setting, and then explore convex separation
properties for graph data as well as an application involving a handwritten
digit dataset.

####  3.3.1 Background from the continuous setting

A typical classification scenario usually consists of some data
$\\{x_{i}\\}\subset\mathbb{R}^{n}$ which one wishes to separate into classes
or clusters either without prior knowledge of the data labels (unsupervised)
or with some information about the class labels of the dataset (semi-
supervised or supervised). In many applications, e.g., [20, 93, 13], the data
$x_{i}$ can often occur not as vectors in $\mathbb{R}^{n}$ but as
distributions $\mu_{i}$ on $\mathbb{R}^{n}$.

In such scenarios, Wasserstein distance, formulated in the Monge sense as

(79)
$\displaystyle\mathcal{W}_{2}(\mu,\nu)^{2}=\inf_{T:T_{\sharp}\mu=\nu}\int_{\mathbb{R}^{n}}\|T(x)-x\|_{2}^{2}d\mu(x),$

where $T_{\sharp}\mu$ is the push-forward of $\mu$ under the map $T$ and the
$\inf$ is over all such $T$ exhibiting desired regularity, arises as a natural
distance metric between probabilitiy measures on $\mathbb{R}^{n}$. However,
this metric can be slow to compute at scale, and in the discrete setting can
even suffer from being undefined.

One approach to resolving this issue involves the usage and study of
Linearized Optimal Transport embeddings [58, 88, 54, 43, 21], which can be
summarized as follows. Given data measures $\\{\mu_{i}\\}$, fix a reference
measure $\mu$, and define
$T_{i}=\mathrm{argmin}_{T:T_{\sharp}\mu=\mu_{i}}\int_{\mathbb{R}^{n}}\|T(x)-x\|_{2}^{2}d\mu(x)$.
Then the measures are featurized in the form of the maps
$T_{i}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ and $2$-Wasserstein distance
between the data measures is then approximated by $\|T_{i}-T_{j}\|_{L^{2}}$.

Theoretically, the ability of Linearized Optimal Transport in approximating
$2$-Wasserstein distance can be captured by the following two results, the
informal statements of which we restate from [58].

######  Theorem 3.23 (Informal Statement of Theorem 4.4 from [58]).

If $\mathscr{P}=\\{\mu_{i}\\}$ are $\epsilon$-perturbations of shifts and
scalings of $\mu$, and $\mathscr{Q}=\\{\nu_{i}\\}$ are
$\epsilon$-perturbations of shifts and scalings of $\nu$, and $\mathscr{P}$
and $\mathscr{Q}$ have small minimal distance depending on $\epsilon$ and
satisfy a few technical assumptions, $\mathscr{P}$ and $\mathscr{Q}$ are
linearly separable in LOT embedding space.

######  Theorem 3.24 (Informal Statement of Theorem 4.1 from [58]).

If $\mu,\nu$ are $\epsilon$-perturbations of shifts and scalings of one
another, then

(80)
$\displaystyle\mathcal{W}_{2}(\mu,\nu)\leq\mathcal{W}_{2}^{\mathrm{LOT}}(\mu,\nu)\leq\mathcal{W}_{2}(\mu,\nu)+C_{\sigma}\epsilon+C_{\sigma}^{\prime}\epsilon^{1/2}.$

In particular, when $\epsilon=0$ and $\mu,\nu$ are shifts and scalings of each
other, LOT is an isometry.

It is also worth noting that in the situation where $\mu_{i}$ is some shift or
scaling of $\mu$, i.e., $\mu_{i}=T_{\sharp}\mu$ for an affine combination of
scaling and translation $T$ on $\mathbb{R}^{n}$, then the LOT embedding of
$\mu_{i}$ will be the map $T$ itself; i.e., $T$ is optimal in the Wasserstein
cost.

####  3.3.2 Linear separtation for 2-Beckmann distance

To set up the problem, suppose we have data sampled from $C$ classes, and each
class is associated to a canonical distribution $\alpha_{i}\in\mathcal{P}(V)$
so that our data may be represented in the form
$\mathcal{D}=\\{T\alpha_{i}\\}_{i=1,\dotsc,C;T\in\mathcal{T}}$. That is, each
data point is of the form $T\alpha_{i}$ where $\alpha_{i}$ is the underlying
distribution of the class and the map
$T:\mathcal{P}(V)\rightarrow\mathcal{P}(V)$ represents a perturbation of the
class distribution among valid perturbations $\mathcal{T}$ (to be determined).

For example, consider a hypothetical dataset of images with resolution
$k\times\ell$. In this setting, $G$ is the $k\times\ell$ lattice graph, and
after normalization each image can be understood as a distribution on $G$. In
our data model, we assume that each image may be expressed as a perturbation
of a canonical distribution associated to the corresponding image class.

In the unsupervised setting, we simply have $\mathcal{D}$ and we wish to use
some clustering technique, e.g., $k$-means or principal geodesic analysis,
associated to a metric on $\mathcal{P}(V)$. In the supervised setting, we have
data equipped with labels
$\mathcal{D}^{\prime}=\\{(T\alpha_{i},y_{i})\\}_{i=1,\dotsc,C;T\in\mathcal{T}}$
so that each label depends only on the class distribution and we seek to build
some classifier, ideally linear, which facilitates predictive analysis.

We treat $\mathcal{B}_{2}$ as a linearization of $\mathcal{W}_{2}$ on graphs.
In this setting, the featurization of each canonical class distribution is
given by $\alpha_{i}\mapsto L^{-1/2}\alpha_{i}$ and similarly for the
individual samples $T\alpha_{i}$.

For a set of measures
$\mathcal{A}=\\{\alpha_{1},\dotsc,\alpha_{k}\\}\subset\mathcal{P}(V)$, define
the mutual support by

$\mathscr{MS}(\mathcal{A})=\bigcap_{i=1}^{k}\mathrm{supp}(\alpha_{i})\subset
V,$

where $\mathrm{supp}(\alpha_{i})$ is the subset of nodes in $V$ on which
$\alpha>0$.

######  Theorem 3.25.

Let $\alpha_{1}\neq\alpha_{2}\in\mathcal{P}(V)$ be the canonical class
distributions for a binary distributional dataset
$\mathcal{D}=\\{T\alpha_{i}\\}_{i=1,2;T\in\mathcal{T}}$. Assume
$\mathscr{MS}(\\{\alpha_{1},\alpha_{2}\\})\neq\varnothing$ and let
$\mathcal{T}$ be the set of affine perturbation maps defined by

$T\alpha=\alpha+{\mathrm{d}}T$

where ${\mathrm{d}}T\in\ell(V)$ is vector which satisfies the three
conditions:

  1. (i)

${\mathrm{d}}T$ is mean zero, or $\mathbf{1}_{n}^{T}{\mathrm{d}}T=0$;

  2. (ii)

${\operatorname{supp}}({\mathrm{d}}T)\subset\mathscr{MS}(\\{\alpha_{1},\alpha_{2}\\})$;
and

  3. (iii)

$\|{\mathrm{d}}T\|_{1}<\delta$, where

(81)
$\displaystyle\delta=\min\left\\{\frac{1}{3}\|\alpha_{1}-\alpha_{2}\|_{2},\min_{\begin{subarray}{c}i=1,2\\\
k\in\mathscr{MS}(\\{\alpha_{1},\alpha_{2}\\})\end{subarray}}\alpha_{i}(k)\right\\}>0.$

Then the sets $\mathcal{A}_{1}=\\{T\alpha_{1}\\}_{T\in\mathcal{T}}$ and
$\mathcal{A}_{2}=\\{T\alpha_{2}\\}_{T\in\mathcal{T}}$, which belong to the
metric space $(\mathcal{P}(V),\mathcal{B}_{2})$, can be isometrically embedded
into $\ell_{2}(V)$ under $L^{-1/2}$ so that their images are linearly
separable as convex sets in $\mathbb{R}^{n}$.

See Section A.2 for the proof. Note that it is not hard to extend Theorem 3.23
to the case of $C>2$ classes, by simply requiring that the perturbations be
smaller than the mutual distances between the canonical class distributions,
up to an appropriate constant, so that in the data model there are no
overlapping perturbations. The main point of this result is that $L^{-1/2}$ as
an embedding of measures, is well-behaved; in the sense that as long as the
original collections of measures were separable, $L^{-1/2}$ will not imbue any
pathology.

####  3.3.3 Experimental results

$x\mapsto x/(\mathbf{1}^{T}x)$$\alpha\mapsto
L^{-1/2}\alpha$$\mathbb{R}^{64}$$\mathcal{P}(V)$$\ell_{2}(V)$$-0.05$$0$$0.05$$15$$7.5$$0$
Figure 4: An illustration of the preprocessing pipeline for the digits data,
with an example from the class of handwritten zeros. The first step is a mass
normalization to convert the pixel values into a fixed-sum distribution viewed
on the nodes $V$ of the $8\times 8$ lattice graph. The second step is an
embedding $\alpha\mapsto L^{-1/2}\alpha$, such that $\ell_{2}$ distance in the
target corresponds to $2$-Beckmann distance in $\mathcal{P}(V)$. When
computing $\mathcal{W}_{2}$, we omit the final step. Figure 5: Using the
digits dataset, and for each pair of digit classes, we computed the pairwise
$2$-Beckmann and $2$-Wasserstein distances for each pair of samples
originating from the respective digit classes (with around 30,000 pairs of
distances per pair of digit classes). Within each tile of the grid, we render
a scatterplot of the distances over the overall linear regression between
$\mathcal{B}_{2}$ and $\mathcal{W}_{2}$ for the experiment given by
$\mathcal{W}_{2}\approx 8.446\mathcal{B}_{2}$.

(a) Similarity kernel between each image is given by
$\exp\\{-\mathcal{B}_{2}(\cdot,\cdot)^{2}\\}$

(b) Similarity kernel between each image is given by
$\exp\\{-\mathcal{W}_{2}(\cdot,\cdot)^{2}\\}$

| RI | ARI | MI | AMI | Hom | Com
---|---|---|---|---|---|---
$\mathcal{B}_{2}$ | 0.940 | 0.685 | 1.782 | 0.783 | 0.774 | 0.797
$\mathcal{W}_{2}$ | 0.935 | 0.656 | 1.719 | 0.755 | 0.747 | 0.775
(c) Performance metrics

Figure 6:  (a)-(b) Using the digits dataset, we demonstrate the results of an
unsupervised clustering algorithm with different choices of similarity kernel.
Each node corresponds to an image of a digit, which we featurize as a
distribution on the $8\times 8$ square lattice graph. We built a $k=42$
nearest neighbor graph on the nodes (shown), and then apply spectral
clustering [87] to create predicted classes. The text labels of the nodes
correspond to the ground truth classes, i.e., digit values. The colors of the
nodes on the left (resp. right) are given by the ground truth classes (resp.
predicted classes). (c) We evaluate the performance of the unsupervised
clustering alogrithm for each kernel. We compare across several metrics,
including Rand index (RI) and adjusted Rand index (ARI) [39]; mutual
information (MI) and adjusted mutual information (AMI) [86]; and homogeneity
(Hom) and completeness (Com) [66]. In all such cases other than MI, a value of
$1.0$ corresponds to perfect clustering as compared to the ground truth. Since
the predictions depend on a random initialization in the $k$-means step, we
simulated 100 runs of the algorithm and reported the best result for each
kernel across the six metrics.

To further explore the implications of our results on learning with graph
data, we conducted two experiments which illuminate some of the potential
applications and underlying properties of $2$-Beckmann distance between
measures. Both examples make use of the “Pen-Based Recognition of Handwritten
Digits” dataset [3], accessed and processed via the Sklearn Python package
[14]. The dataset contains 1797 grayscale handwritten digits of resolution
$8\times 8$ and pixel values ranging from $0-15$. The reason for choosing this
dataset is that the $2$-Wasserstein kernel is computationally prohibitive at
scale without approximation, so rather than regularize the Wasserstein metric,
we opt for a lighter-weight image dataset. Specifically, if $\mathcal{W}_{2}$
is obtained via, e.g., a Hungarian algorithm or a linear program, the time
complexity to obtain a kernel matrix for $N$ samples, each defined on a graph
of $n$ nodes, is roughly $O(n^{3}N^{2})$. A Beckmann kernel matrix, on the
other hand, runs $O(n^{3}+(n^{2}+n)N^{2})$ since only a single SVD calculation
of $L^{\dagger}$ is required at the beginning, and then subsequent entries of
the kernel matrix are obtained through matrix-vector multiplication and
pairwise comparison. The Wasserstein metric $\mathcal{W}_{2}(\alpha,\beta)$
was directly evaluated for each pair of examples $\alpha,\beta$ by using the
CVXPY convex optimization Python package [24] with initialization determined
by the trivial coupling $\beta\alpha^{T}$. Fig. 4 illustrates the pre-
processing pipeline for an example image of a handwritten zero.

The first experiment, described in detail in Fig. 5, is a comparative study of
$\mathcal{B}_{2}$ and $\mathcal{W}_{2}$ in which we show that the two metrics
are well-correlated for the dataset in question. The second experiment,
described in Fig. 6, is a comparative study of $\mathcal{B}_{2}$ and
$\mathcal{W}_{2}$ within the context of unsupervised learning on the digit
dataset. In this setup, we show that the two kernels perform almost
identically on the dataset with respect to several metrics (with a slight edge
toward $\mathcal{B}_{2}$), and thus there is some empirical evidence for drop-
in usage of $\mathcal{B}_{2}$ where $\mathcal{W}_{2}$, or perhaps
$\mathcal{W}_{p}$ more generally, may present a computational bottleneck.

##  4 Acknowledgements

The authors would like to acknowledge Yusu Wang for her inspirational
discussions early on in this project, Stefan Steinerberger for his help
placing the preliminary results within the context of the broader OT space,
Zachary Lubberts for his helpful discussions on applications of graph OT to
discrete geometry, and Caroline Moosmüller for her helpful feedback on
linearized Wasserstein distance and Sobolev transport in the continuous
setting. SR wishes to acknowledge Evangelos Nikitopoulos, as well as financial
support from the Halıcıoğlu Data Science Institute through their Graduate
Prize Fellowship. AC was funded by NSF DMS 2012266 and a gift from Intel. ZW
was supported by NSF CCF 2217058.

## References

  * Abrishami et al. [2020] Tara Abrishami, Nestor Guillen, Parker Rule, Zachary Schutzman, Justin Solomon, Thomas Weighill, and Si Wu.  Geometry of graph partitions via optimal transport.  _SIAM Journal on Scientific Computing_ , 42(5), 2020.
  * Alamgir and Luxburg [2011] Morteza Alamgir and Ulrike Luxburg.  Phase transition in the family of p-resistances.  _Advances in neural information processing systems_ , 24, 2011.
  * Alpaydin and Alimoglu [1998] E. Alpaydin and Fevzi. Alimoglu.  Pen-Based Recognition of Handwritten Digits.  UCI Machine Learning Repository, 1998.
  * Bauer et al. [2011] Frank Bauer, Jürgen Jost, and Shiping Liu.  Ollivier-ricci curvature and the spectrum of the normalized graph laplace operator.  _arXiv preprint arXiv:1105.3803_ , 2011.
  * Beckmann [1952] Martin Beckmann.  A continuous model of transportation.  _Econometrica: Journal of the Econometric Society_ , 1952.
  * Ben-Israel and Charnes [1963] Adi Ben-Israel and A Charnes.  Contributions to the theory of generalized inverses.  _Journal of the Society for Industrial and Applied Mathematics_ , 11(3), 1963.
  * Benamou and Brenier [2000] Jean-David Benamou and Yann Brenier.  A computational fluid mechanics solution to the monge-kantorovich mass transfer problem.  _Numerische Mathematik_ , 84(3):375–393, 2000.
  * Beveridge [2016] Andrew Beveridge.  A hitting time formula for the discrete green’s function.  _Combinatorics, Probability and Computing_ , 25(3), 2016.
  * Beveridge and Lovász [2010] Andrew Beveridge and László Lovász.  Exit frequency matrices for finite markov chains.  _Combinatorics, Probability and Computing_ , 19(4), 2010.
  * Bhattacharjee et al. [2023] Robi Bhattacharjee, Alexander Cloninger, Yoav Freund, and Andreas Oslandsbotn.  Effective resistance in metric spaces.  _arXiv preprint arXiv:2306.15649_ , 2023.
  * Bigot [2020] Jérémie Bigot.  Statistical data analysis in the wasserstein space.  _ESAIM: Proceedings and Surveys_ , 68, 2020.
  * Black et al. [2023] Mitchell Black, Zhengchao Wan, Amir Nayyeri, and Yusu Wang.  Understanding oversquashing in gnns through the lens of effective resistance.  In _International Conference on Machine Learning_ , pages 2528–2547. PMLR, 2023.
  * Bruggner et al. [2014] Robert V Bruggner, Bernd Bodenmiller, David L Dill, Robert J Tibshirani, and Garry P Nolan.  Automated identification of stratifying signatures in cellular subpopulations.  _Proceedings of the National Academy of Sciences_ , 111(26), 2014.
  * Buitinck et al. [2013] Lars Buitinck, Gilles Louppe, Mathieu Blondel, Fabian Pedregosa, Andreas Mueller, Olivier Grisel, Vlad Niculae, Peter Prettenhofer, Alexandre Gramfort, Jaques Grobler, Robert Layton, Jake VanderPlas, Arnaud Joly, Brian Holt, and Gaël Varoquaux.  API design for machine learning software: experiences from the scikit-learn project.  In _ECML PKDD Workshop: Languages for Data Mining and Machine Learning_ , 2013.
  * Cannon et al. [2022] Sarah Cannon, Moon Duchin, Dana Randall, and Parker Rule.  Spanning tree methods for sampling graph partitions.  _arXiv preprint arXiv:2210.01401_ , 2022.
  * Chen et al. [2020] Benson Chen, Gary Bécigneul, Octavian-Eugen Ganea, Regina Barzilay, and Tommi Jaakkola.  Optimal transport graph neural networks.  _arXiv preprint arXiv:2006.04804_ , 2020.
  * Chen et al. [2022] Samantha Chen, Sunhyuk Lim, Facundo Mémoli, Zhengchao Wan, and Yusu Wang.  Weisfeiler-lehman meets gromov-wasserstein.  In _International Conference on Machine Learning_ , pages 3371–3416. PMLR, 2022.
  * Chung et al. [2014] Fan Chung, Wenbo Zhao, and Mark Kempton.  Ranking and sparsifying a connection graph.  _Internet Mathematics_ , 10(1-2), 2014.
  * Cloninger et al. [2023a] Alex Cloninger, Gal Mishne, Andreas Oslandsbotn, Sawyer Jack Robertson, Zhengchao Wan, and Yusu Wang.  Random walks, conductance, and resistance for the connection graph laplacian.  _arXiv preprint arXiv:2308.09690_ , 2023a.
  * Cloninger et al. [2019] Alexander Cloninger, Brita Roy, Carley Riley, and Harlan M Krumholz.  People mover’s distance: Class level geometry using fast pairwise data adaptive transportation costs.  _Applied and Computational Harmonic Analysis_ , 47(1), 2019.
  * Cloninger et al. [2023b] Alexander Cloninger, Keaton Hamm, Varun Khurana, and Caroline Moosmüller.  Linearized wasserstein dimensionality reduction with approximation guarantees.  _arXiv preprint arXiv:2302.07373_ , 2023b.
  * Devriendt and Lambiotte [2022] Karel Devriendt and Renaud Lambiotte.  Discrete curvature on graphs from the effective resistance.  _Journal of Physics: Complexity_ , 3(2), 2022.
  * Devriendt et al. [2024] Karel Devriendt, Andrea Ottolini, and Stefan Steinerberger.  Graph curvature via resistance distance.  _Discrete Applied Mathematics_ , 348, 2024.
  * Diamond and Boyd [2016] Steven Diamond and Stephen Boyd.  CVXPY: A Python-embedded modeling language for convex optimization.  _Journal of Machine Learning Research_ , 2016.
  * Doyle and Snell [1984] Peter G Doyle and J Laurie Snell.  _Random walks and electric networks_ , volume 22.  American Mathematical Soc., 1984.
  * Elmoataz et al. [2008] Abderrahim Elmoataz, Olivier Lezoray, and Sébastien Bougleux.  Nonlocal discrete regularization on weighted graphs: a framework for image and manifold processing.  _IEEE transactions on Image Processing_ , 17(7), 2008.
  * Elmoataz et al. [2015] Abderrahim Elmoataz, Matthieu Toutain, and Daniel Tenbrinck.  On the p-laplacian and infinity-laplacian on graphs with applications in image and data processing.  _SIAM Journal on Imaging Sciences_ , 8(4), 2015.
  * Essid and Solomon [2018] Montacer Essid and Justin Solomon.  Quadratically regularized optimal transport on graphs.  _SIAM Journal on Scientific Computing_ , 40(4), 2018.
  * Evans [1997] Lawrence C Evans.  Partial differential equations and monge-kantorovich mass transfer.  _Current developments in mathematics_ , 1997(1), 1997.
  * Evans and Gangbo [1999] Lawrence C Evans and Wilfrid Gangbo.  _Differential equations methods for the Monge-Kantorovich mass transfer problem_.  American Mathematical Soc., 1999.
  * Fang et al. [2023] Zhongxi Fang, Jianming Huang, Xun Su, and Hiroyuki Kasai.  Wasserstein graph distance based on l1–approximated tree edit distance between weisfeiler–lehman subtrees.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 37, 2023.
  * Galichon [2018] Alfred Galichon.  _Optimal transport methods in economics_.  Princeton University Press, 2018.
  * Gangbo and McCann [1996] Wilfrid Gangbo and Robert J McCann.  The geometry of optimal transportation.  _Acta Mathematica_ , 177, 1996.
  * Ge and Dong [2020] Jun Ge and Fengming Dong.  Spanning trees in complete bipartite graphs and resistance distance in nearly complete bipartite graphs.  _Discrete Applied Mathematics_ , 283, 2020.
  * Gerolin [2013] Augusto Gerolin.  Benamou-brenier’s approach for ott.  In _Optimal Transport and Applications_. Summer School, Lake Arrowhead, 2013.
  * Gervacio [2016] Severino V Gervacio.  Resistance distance in complete n-partite graphs.  _Discrete Applied Mathematics_ , 203, 2016.
  * Greengard et al. [2022] Philip Greengard, Jeremy G Hoskins, Nicholas F Marshall, and Amit Singer.  On a linearization of quadratic wasserstein distance.  _arXiv preprint arXiv:2201.13386_ , 2022.
  * Haker et al. [2004] Steven Haker, Lei Zhu, Allen Tannenbaum, and Sigurd Angenent.  Optimal mass transport for registration and warping.  _International Journal of computer vision_ , 60, 2004.
  * Hubert and Arabie [1985] Lawrence Hubert and Phipps Arabie.  Comparing partitions.  _Journal of classification_ , 2, 1985.
  * Jorgensen and Pearse [2023] Palle Jorgensen and Erin PJ Pearse.  _Operator theory and analysis of infinite networks_ , volume 7.  World Scientific, 2023.
  * Kantorovich [1942] Leonid V Kantorovich.  On the translocation of masses.  In _Dokl. Akad. Nauk. USSR (NS)_ , volume 37, 1942.
  * Khoa and Chawla [2012] Nguyen Lu Dang Khoa and Sanjay Chawla.  Large scale spectral clustering using resistance distance and spielman-teng solvers.  In _Discovery Science: 15th International Conference, DS 2012, Lyon, France, October 29-31, 2012. Proceedings 15_. Springer, 2012.
  * Khurana et al. [2023] Varun Khurana, Harish Kannan, Alexander Cloninger, and Caroline Moosmüller.  Supervised learning of sheared distributions using linearized optimal transport.  _Sampling Theory, Signal Processing, and Data Analysis_ , 21(1), 2023.
  * Kusner et al. [2015] Matt Kusner, Yu Sun, Nicholas Kolkin, and Kilian Weinberger.  From word embeddings to document distances.  In _International conference on machine learning_. PMLR, 2015.
  * Le et al. [2019] Tam Le, Makoto Yamada, Kenji Fukumizu, and Marco Cuturi.  Tree-sliced variants of wasserstein distances.  _Advances in neural information processing systems_ , 32, 2019.
  * Le et al. [2022] Tam Le, Truyen Nguyen, Dinh Phung, and Viet Anh Nguyen.  Sobolev transport: A scalable metric for probability measures with graph metrics.  In _International Conference on Artificial Intelligence and Statistics_ , pages 9844–9868. PMLR, 2022.
  * Le et al. [2023] Tam Le, Truyen Nguyen, and Kenji Fukumizu.  Scalable unbalanced sobolev transport for measures on a graph.  In _International Conference on Artificial Intelligence and Statistics_. PMLR, 2023.
  * Le et al. [2024] Tam Le, Truyen Nguyen, and Kenji Fukumizu.  Generalized sobolev transport for probability measures on a graph.  _arXiv preprint arXiv:2402.04516_ , 2024.
  * Ling and Okada [2007] Haibin Ling and Kazunori Okada.  An efficient earth mover’s distance algorithm for robust histogram comparison.  _IEEE transactions on pattern analysis and machine intelligence_ , 29(5), 2007.
  * Lovász [1993] László Lovász.  Random walks on graphs.  _Combinatorics, Paul erdos is eighty_ , 2(1-46), 1993.
  * Lovász and Winkler [1995a] László Lovász and Peter Winkler.  Efficient stopping rules for markov chains.  In _Proceedings of the twenty-seventh annual ACM symposium on Theory of computing_ , 1995a.
  * Lovász and Winkler [1995b] László Lovász and Peter Winkler.  Mixing of random walks and other diffusions on a graph.  _London Mathematical Society Lecture Note Series_ , 1995b.
  * Mathey-Prevot and Valette [2023] Maxime Mathey-Prevot and Alain Valette.  Wasserstein distance and metric trees.  _L’Enseignement Mathématique_ , 69(3), 2023.
  * Mérigot et al. [2020] Quentin Mérigot, Alex Delalande, and Frederic Chazal.  Quantitative stability of optimal transport maps and linearization of the 2-wasserstein space.  In _International Conference on Artificial Intelligence and Statistics_. PMLR, 2020.
  * Miller [2007] Stacy Miller.  The problem of redistricting: the use of centroidal voronoi diagrams to build unbiased congressional districts.  _Senior project, Whitman College_ , 2007.
  * Monge [1781] Gaspard Monge.  Mémoire sur la théorie des déblais et des remblais.  _Mem. Math. Phys. Acad. Royale Sci._ , 1781.
  * Montrucchio and Pistone [2019] LUIGI Montrucchio and Giovanni Pistone.  Kantorovich distance on a weighted graph.  _arXiv preprint arXiv:1905.07547_ , 1420, 2019.
  * Moosmüller and Cloninger [2020] Caroline Moosmüller and Alexander Cloninger.  Linear optimal transport embedding: Provable wasserstein classification for certain rigid transformations and perturbations.  _arXiv preprint arXiv:2008.09165_ , 2020.
  * Münch and Wojciechowski [2019] Florentin Münch and Radosław K Wojciechowski.  Ollivier ricci curvature for general graph laplacians: heat equation, laplacian comparison, non-explosion and diameter bounds.  _Advances in Mathematics_ , 356, 2019.
  * Nguyen and Mamitsuka [2016] Canh Hao Nguyen and Hiroshi Mamitsuka.  New resistance distances with global information on large graphs.  In _Artificial intelligence and statistics_. PMLR, 2016.
  * Panaretos and Zemel [2019] Victor M Panaretos and Yoav Zemel.  Statistical aspects of wasserstein distances.  _Annual review of statistics and its application_ , 6, 2019.
  * Peyré et al. [2017] Gabriel Peyré, Marco Cuturi, et al.  Computational optimal transport.  _Center for Research in Economics and Statistics Working Papers_ , 1(2017-86), 2017.
  * Peyre [2018] Rémi Peyre.  Comparison between w2 distance and h- 1 norm, and localization of wasserstein distance.  _ESAIM: Control, Optimisation and Calculus of Variations_ , 24(4), 2018.
  * Ramdas et al. [2017] Aaditya Ramdas, Nicolás García Trillos, and Marco Cuturi.  On wasserstein two-sample testing and related families of nonparametric tests.  _Entropy_ , 19(2), 2017.
  * Robertson et al. [2023] Sawyer Robertson, Dhruv Kohli, Gal Mishne, and Alexander Cloninger.  On a generalization of wasserstein distance and the beckmann problem to connection graphs.  _arXiv preprint arXiv:2312.10295_ , 2023.
  * Rosenberg and Hirschberg [2007] Andrew Rosenberg and Julia Hirschberg.  V-measure: A conditional entropy-based external cluster evaluation measure.  In _Proceedings of the 2007 joint conference on empirical methods in natural language processing and computational natural language learning (EMNLP-CoNLL)_ , 2007.
  * Ryu et al. [2018] Ernest K Ryu, Yongxin Chen, Wuchen Li, and Stanley Osher.  Vector and matrix optimal mass transport: theory, algorithm, and applications.  _SIAM Journal on Scientific Computing_ , 40(5), 2018.
  * Saito and Herbster [2023] Shota Saito and Mark Herbster.  Multi-class graph clustering via approximated effective $p$-resistance.  In _International Conference on Machine Learning_. PMLR, 2023.
  * Salimans et al. [2018] Tim Salimans, Han Zhang, Alec Radford, and Dimitris Metaxas.  Improving gans using optimal transport.  _arXiv preprint arXiv:1803.05573_ , 2018.
  * Samal et al. [2018] Areejit Samal, RP Sreejith, Jiao Gu, Shiping Liu, Emil Saucan, and Jürgen Jost.  Comparative analysis of two discretizations of ricci curvature for complex networks.  _Scientific reports_ , 8(1), 2018.
  * Santambrogio [2015] Filippo Santambrogio.  Optimal transport for applied mathematicians.  _Birkäuser, NY_ , 55(58-63), 2015.
  * Schiebinger et al. [2019] 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), 2019.
  * Sion [1958] Maurice Sion.  On general minimax theorems.  _Pacific J. Math._ , 8(4), 1958.
  * Solomon [2018] Justin Solomon.  Optimal transport on discrete domains.  _AMS Short Course on Discrete Differential Geometry_ , 2018.
  * Solomon et al. [2014] Justin Solomon, Raif Rustamov, Leonidas Guibas, and Adrian Butscher.  Earth mover’s distances on discrete surfaces.  _ACM Transactions on Graphics (ToG)_ , 33(4), 2014.
  * Spielman and Srivastava [2008] Daniel A Spielman and Nikhil Srivastava.  Graph sparsification by effective resistances.  In _Proceedings of the fortieth annual ACM symposium on Theory of computing_ , 2008.
  * Steinerberger [2021] Stefan Steinerberger.  A wasserstein inequality and minimal green energy on compact manifolds.  _Journal of Functional Analysis_ , 281(5), 2021.
  * Sugiyama and Sato [2023] Tomohiro Sugiyama and Kazuhiro Sato.  Kron reduction and effective resistance of directed graphs.  _SIAM Journal on Matrix Analysis and Applications_ , 44(1), 2023.
  * Takezawa et al. [2021] Yuki Takezawa, Ryoma Sato, and Makoto Yamada.  Supervised tree-wasserstein distance.  In _International Conference on Machine Learning_. PMLR, 2021.
  * Takezawa et al. [2022] Yuki Takezawa, Ryoma Sato, Zornitsa Kozareva, Sujith Ravi, and Makoto Yamada.  Fixed support tree-sliced wasserstein barycenter.  _IEICE Technical Report; IEICE Tech. Rep._ , 122(325), 2022.
  * TANG et al. [2017] MINH TANG, AVANTI ATHREYA, DANIEL L SUSSMAN, VINCE LYZINSKI, and CAREY E PRIEBE.  A nonparametric two-sample hypothesis testing problem for random graphs.  _Bernoulli_ , 2017.
  * Tetali [1991] Prasad Tetali.  Random walks and the effective resistance of networks.  _Journal of Theoretical Probability_ , 4, 1991.
  * Tian et al. [2023] Yu Tian, Zachary Lubberts, and Melanie Weber.  Curvature-based clustering on graphs.  _arXiv preprint arXiv:2307.10155_ , 2023.
  * Villani [2021] Cédric Villani.  _Topics in optimal transportation_ , volume 58.  American Mathematical Soc., 2021.
  * Villani et al. [2009] Cédric Villani et al.  _Optimal transport: old and new_ , volume 338.  Springer, 2009.
  * Vinh et al. [2009] NX Vinh, J Epps, and J Bailey.  Information theoretic measures for clusterings comparison: Variants.  _Properties, Normalization and Correction for Chance_ , 18, 2009.
  * Von Luxburg [2007] Ulrike Von Luxburg.  A tutorial on spectral clustering.  _Statistics and computing_ , 17, 2007.
  * Wang et al. [2013] Wei Wang, Dejan Slepčev, Saurav Basu, John A Ozolek, and Gustavo K Rohde.  A linear optimal transportation framework for quantifying and visualizing variations in sets of images.  _International journal of computer vision_ , 101, 2013.
  * Weaver [2018] Nik Weaver.  _Lipschitz algebras_.  World Scientific, 2018.
  * Yamada et al. [2022] Makoto Yamada, Yuki Takezawa, Ryoma Sato, Han Bao, Zornitsa Kozareva, and Sujith Ravi.  Approximating 1-wasserstein distance with trees.  _Transactions on Machine Learning Research_ , 2022.
  * Ye and Yan [2019] Luzh Ye and Weigen Yan.  Resistance between two vertices of almost complete bipartite graphs.  _Discrete Applied Mathematics_ , 257, 2019.
  * Ye et al. [2021] Ze Ye, Tengfei Ma, Chien-Chun Ni, Kin Sum Liu, Jie Gao, and Chao Chen.  Ricci-{gnn}: Defending against structural attacks through a geometric approach, 2021.  URL https://openreview.net/forum?id=_qoQkWNEhS.
  * Zhang et al. [2010] Yin Zhang, Rong Jin, and Zhi-Hua Zhou.  Understanding bag-of-words model: a statistical framework.  _International journal of machine learning and cybernetics_ , 1, 2010.

##  Appendix A Proofs

This appendix contains deferred proofs from the remainder of the paper.

###  A.1 Proofs from section 2

###### Proof of Theorem 2.1.

We can derive the Lagrangian dual in a fairly straightforward manner. We
rewrite the constraint $BJ=\alpha-\beta$ using the expresion

(82) $\displaystyle\sup_{\phi\in\ell(V)}\phi^{T}(\alpha-\beta)-\phi^{T}(BJ)$
$\displaystyle=\begin{cases}0&\text{ if }BJ=\alpha-\beta\\\ +\infty&\text{
otherwise.}\end{cases}$

Thus the Beckmann problem may be rewritten as the following

(83) $\displaystyle\inf_{BJ=\alpha-\beta}\|J\|_{w,p}$
$\displaystyle=\inf_{J}\left\\{\|J\|_{w,p}+\sup_{\phi}\phi^{T}(\alpha-\beta)-\phi^{T}(BJ)\right\\}$
(84)
$\displaystyle=\sup_{\phi}\left\\{\phi^{T}(\alpha-\beta)+\inf_{J}\|J\|_{w,p}-\phi^{T}(BJ)\right\\},$

where we exchange the $\sup$ and $\inf$ using, e.g., Sion’s minimax theorem
[73] or Slater’s condition. Now we have that, using the Legendre transform of
$\|\cdot\|_{p}$,

(85) $\displaystyle\inf_{J}\|J(e)\|_{w,p}-\phi^{T}(BJ)$
$\displaystyle=\inf_{J}\|J\|_{w,p}-J^{T}(B^{T}\phi)$ (86)
$\displaystyle=\begin{cases}0&\text{ if }\|B^{T}\phi\|_{w^{1-q},q}\leq 1\\\
-\infty&\text{ otherwise }\end{cases}$

since the dual norm to $\|\cdot\|_{w,p}$ is $\|\cdot\|_{w^{1-q},q}$.
Therefore, the Lagrangian dual becomes

(87)
$\displaystyle\sup\left\\{\phi^{T}(\alpha-\beta):\phi\in\ell(V),\left\|B^{T}\phi\right\|_{w^{1-q},q}\leq
1\right\\}$

The special case of $p=1$ and $q=\infty$ follows from the same proof, with the
only change being that the dual norm to $\|\cdot\|_{w,1}$ is
$\|\cdot\|_{w^{-1},\infty}$, which can be shown directly or through a limiting
argument. ∎

###### Proof of Proposition 2.5.

Let $i,j\in V$ be fixed distinct vertices. We begin by noting simply that by
inspection,

$\widetilde{B}(\pi_{ij}I_{P_{ij}})=\pi_{ij}(\delta_{i}-\delta_{j})$

and thus that

(88) $\displaystyle\widetilde{B}\left(\sum_{i,j\in
V}\pi_{ij}I_{P_{ij}}\right)$ $\displaystyle=\sum_{i,j\in
V}\pi_{ij}(\delta_{i}-\delta_{j})$ (89) $\displaystyle=\sum_{i\in
V}\delta_{i}(\pi\mathbf{1})_{i}-\sum_{j\in
V}\delta_{j}(\mathbf{1}^{T}\pi)_{j}$ (90) $\displaystyle=\alpha-\beta.$

Since $J^{\pi}\geq 0$ by construction, $J^{\pi}$ is a feasible edge flow for
$\mathcal{B}_{p}(\alpha,\beta)$. The estimate on $\|J^{\pi}\|_{w,p}$ follows
immediately from the triangle inequality. ∎

###### Proof of Theorem 2.7.

Suppose $\pi\in\Pi(\alpha,\beta)$ is an optimal coupling for
$\mathcal{W}_{d_{p},p}(\alpha,\beta)$. For each $i,j$, let
$P_{ij}\in\mathscr{P}(i,j)$ be a choice of path which is minimal in the sense
of $d_{p}$, and let $J^{\pi}=J^{\pi,(P_{ij})}$ be the feasible flow as in
Proposition 2.5. Then by Hölder’s inequality,

(91) $\displaystyle\mathcal{B}_{p}(\alpha,\beta)$
$\displaystyle\leq\|J^{\pi}\|_{w,p}$ (92) $\displaystyle\leq\sum_{i,j\in
V}\pi_{ij}\|I_{P_{ij}}\|_{w,p}$ (93) $\displaystyle\leq\sum_{i,j\in
V}\pi_{ij}d_{p}(i,j)$ (94) $\displaystyle\leq\|\mathbf{1}_{V\times
V}\|_{q}\left(\sum_{i,j\in V}\pi_{ij}^{p}d_{p}(i,j)^{p}\right)^{1/p}$ (95)
$\displaystyle\leq\|\mathbf{1}_{V\times V}\|_{q}\left(\sum_{i,j\in
V}\pi_{ij}d_{p}(i,j)^{p}\right)^{1/p}=n^{2/q}\mathcal{W}_{d_{p},p}(\alpha,\beta)$

since $\pi_{ij}\leq 1$ and $p>1$. ∎

###### Proof of Proposition 2.13.

The proof of this result is straightforward and comes in two parts. First, we
observe that
$\mathcal{W}_{p}(\alpha,\beta)=\mathcal{W}_{p}(\widehat{\alpha},\widehat{\beta})$
where

(96)
$\displaystyle\mathcal{W}_{p}(\widehat{\alpha},\widehat{\beta})^{p}=\inf\left\\{\int_{\mathbb{R}\times\mathbb{R}}|x-y|^{p}{\mathrm{d}}\pi(x,y):\pi\in\Pi(\widehat{\alpha},\widehat{\beta})\right\\}.$

In this case, $\Pi(\widehat{\alpha},\widehat{\beta})$ is the set of all Borel
probability measures on $\mathbb{R}\times\mathbb{R}$ with respective marginals
$\alpha,\beta$. Equality here holds because any such
$\pi\in\Pi(\widehat{\alpha},\widehat{\beta})$, since it has discrete
marginals, must itself be discrete and supported on the Cartesian product
$\\{1,\dotsc,n\\}\times\\{1,\dotsc,n\\}$; i.e., it can be written as a matrix.
Thus, there is a one-to-one correspondence between the feasible couplings on
$V\times V$ and $\mathbb{R}\times\mathbb{R}$, and the cost of any such pair of
corresponding couplings is identical since shortest path distance on
$V(P_{n})$ is $|i-j|$.

The second part of the proof is classical, and it suffices to observe that the
$p$-Wasserstein distance between probability measures on $\mathbb{R}$ is
simply the $p$-norm distance between their inverse cdfs. For a proof we
recommend, e.g., [64]. ∎

###### Proof of Proposition 2.14.

We note that the signed incidence matrix $B$, which is of shape $n\times n-1$,
must have no kernel- for the rank of $B$ agrees with the rank of $BB^{T}=L$,
which is $n-1$ for any connected graph on $n$ nodes. Therefore, for any $1\leq
p<\infty$, $\mathcal{B}_{p}(\alpha,\beta)$ is the $p$-norm of the unique flow
$J$ such that $BJ=\alpha-\beta$ and which does not depend on $p$. We therefore
need only show that $B(K_{\alpha}-K_{\beta})=\alpha-\beta$. To wit, if $i=1$,
note that

$BK_{\alpha}(1)=K_{\alpha}(1,2)=\alpha(1),$

and if $1<i<n$,

$BK_{\alpha}(i)=K_{\alpha}(i,i+1)-K_{\alpha}(i-1,i)=\alpha(i),$

and lastly if $i=n$,

$BK_{\alpha}(n)=-K_{\alpha}(n-1,n)=\alpha(n)-1.$

Therefore, with a simple cancellation, it holds
$B(K_{\alpha}-K_{\beta})=\alpha-\beta$ for all $i\in V$. The first equality in
the proposition therefore follows, and the second follows immediately upon
inspection. ∎

$I_{1}$$I_{2}$$\vdots$$I_{N}$$O_{1}$$O_{2}$$\vdots$$O_{M}$$i$ Figure 7: A
sketch of a vertex neighborhood in an oriented tree.

###### Proof of Proposition 2.15.

Once again the proof of this result is a matter of rigid feasibility: there
can only really be one feasible flow $J\in\ell(E^{\prime})$ satisfying
$BJ=\alpha-\beta$ owing to, e.g., rank considerations for Laplacians on trees.
Thus it is enough only to establish that
$B(K_{\alpha}-K_{\beta})=\alpha-\beta$. Let $i\in V$ be fixed, and suppose $i$
has $N$ incoming oriented edges, and $M$ outgoing oriented edges. At the root
of each incoming oriented edge is a subtree $I_{\ell}$, and at the head of
each outgoing oriented edge is a subtree $O_{\ell}$. This setup is illustrated
in Fig. 7. For each $1\leq\ell\leq N$, let $\alpha(I_{\ell})$ be the total
mass of $\alpha$ on that component, and similarly for $\alpha(O_{\ell})$. We
split up the argument into a few cases depending on $M,N$. Assume for a moment
that $M\geq 2$ and $N\geq 1$; then by inspection we have

(97) $\displaystyle(BK_{\alpha})(i)$
$\displaystyle=-(\alpha(I_{1})+\alpha(I_{2})+\dotsc+\alpha(I_{N}))$ (98)
$\displaystyle+\left(\alpha(i)+\sum_{\ell=1}^{N}\alpha(I_{\ell})+\sum_{\ell\neq
1}\alpha(O_{\ell})\right)+\cdots+\left(\alpha(i)+\sum_{\ell=1}^{N}\alpha(I_{\ell})+\sum_{\ell\neq
M}\alpha(O_{\ell})\right)$ (99)
$\displaystyle=M\alpha(i)+(M-1)\sum_{\ell=1}^{N}\alpha(I_{\ell})+(M-1)\sum_{\ell=1}^{M}\alpha(O_{\ell})$
(100) $\displaystyle=\alpha(i)+M-1.$

If $M=1$ and $N\geq 1$, then $(BK_{\alpha})(i)=\alpha(i)$. If $M=0$ and $N\geq
1$, then $(BK_{\alpha})(i)=\alpha(i)-1$. If $N=0$, then
$(BK_{\alpha})(i)=\alpha(i)+M-1$, as before, since the only difference is the
lack of contribution of the $I_{\ell}$’s. Therefore, $BK_{\alpha}=\alpha+c$
where $c\in\mathbb{R}^{n}$ is a vector which does not depend on $\alpha$, and
thus it holds that $B(K_{\alpha}-K_{\beta})=\alpha-\beta$. The claim follows.
∎

###  A.2 Proofs from section 3

###### Proof of Theorem 3.13.

We start by considering the pointwise value of the vector
$L^{\dagger}(\alpha-\beta)$. To this end, a useful observation is that for any
coupling $\pi\in\Pi(\alpha,\beta)$, we have

$\alpha-\beta=\sum_{i,j\in V}\pi_{ij}(\delta_{i}-\delta_{j}).$

With this in hand alongside Theorem 3.12, we can calculate

(101) $\displaystyle L^{\dagger}(\alpha-\beta)_{i}$ $\displaystyle=\sum_{j\in
V}\left((L^{\dagger})_{ij}\sum_{k,\ell\in
V}\pi_{k\ell}(\delta_{k}(j)-\delta_{\ell}(j))\right)$ (102)
$\displaystyle=\frac{1}{{\operatorname{vol}}(G)}\sum_{j,k,\ell\in
V}\left(H(\rho,j)-H(i,j)\right)\pi_{k\ell}(\delta_{k}(j)-\delta_{\ell}(j))$
(103) $\displaystyle=\frac{1}{{\operatorname{vol}}(G)}\sum_{k,\ell\in
V}\pi_{k\ell}\left(H(\rho,k)-H(i,k)-H(\rho,\ell)+H(i,\ell)\right)$ (104)
$\displaystyle=\frac{1}{{\operatorname{vol}}(G)}\sum_{k}\alpha_{k}(H(\rho,k)-H(i,k))-\sum_{\ell}\beta_{\ell}(H(\rho,\ell)-H(i,\ell))$
(105)
$\displaystyle=\frac{1}{{\operatorname{vol}}(G)}\sum_{k}(\alpha_{k}-\beta_{k})(H(\rho,k)-H(i,k))$
(106)
$\displaystyle=c-\frac{1}{{\operatorname{vol}}(G)}\sum_{k}(\alpha_{k}-\beta_{k})H(i,k)$

where by introducing the placeholder $c$ for some $c\in\mathbb{R}$, we are
separating the first piece of the summand which does not depend on $i$ and
which will be eliminated in the subsequent calculation. Then, multiplying by
$(\alpha-\beta)^{T}$, and using the fact that
$(\alpha-\beta)^{T}\mathbf{1}_{n}=0$, we get

(107) $\displaystyle(\alpha-\beta)^{T}L^{\dagger}(\alpha-\beta)$
$\displaystyle=-\frac{1}{{\operatorname{vol}}(G)}\sum_{i,k\in
V}(\alpha_{i}-\beta_{i})(\alpha_{k}-\beta_{k})H(i,k)$ (108)
$\displaystyle=-\frac{1}{{\operatorname{vol}}(G)}\sum_{k\in
V}(\alpha_{k}-\beta_{k})\sum_{i\in V}(\alpha_{i}H(i,k)-\beta_{i}H(i,k))$ (109)
$\displaystyle=-\frac{1}{{\operatorname{vol}}(G)}\sum_{k\in
V}(\alpha_{k}-\beta_{k})(H(\alpha,k)-H(\beta,k))$

using Proposition 3.11(i) in the final line. The claim follows. ∎

###### Proof of Corollary 3.14.

From the proof of Theorem 3.13 and Hölder’s inequality, we have

(110) $\displaystyle r_{\alpha\beta}$
$\displaystyle=-\frac{1}{{\operatorname{vol}}(G)}\sum_{i,k\in
V}(\alpha_{i}-\beta_{i})(\alpha_{k}-\beta_{k})H(i,k)$ (111)
$\displaystyle=\frac{1}{{\operatorname{vol}}(G)}\sum_{k}(\beta_{k}-\alpha_{k})\sum_{i}(\alpha_{i}-\beta_{i})H(i,k)$
(112)
$\displaystyle\leq\frac{1}{{\operatorname{vol}}(G)}\left\|\alpha-\beta\right\|_{1}\left\|\sum_{i}(\alpha_{i}-\beta_{i})H(i,k)\right\|_{\infty}$
(113)
$\displaystyle\leq\frac{2}{{\operatorname{vol}}(G)}\max\\{H(\alpha,\beta),H(\beta,\alpha)\\}.$

where in the final line we make use of Proposition 3.11(ii). The second
inequality in the Corollary follows from the observation in the proof of
Theorem 3.13 that if $\pi\in\Pi(\alpha,\beta)$ is any coupling,
$\alpha-\beta=\sum_{i,j\in V}\pi_{ij}(\delta_{i}-\delta_{j})$. Then since
$x\mapsto\|L^{-1/2}x\|_{2}^{2}$ is convex in $x$,

(114) $\displaystyle(\alpha-\beta)^{T}L^{\dagger}(\alpha-\beta)$
$\displaystyle=\left\|L^{-1/2}(\alpha-\beta)\right\|_{2}^{2}$ (115)
$\displaystyle=\left\|\sum_{i,j}\pi_{ij}L^{-1/2}(\delta_{i}-\delta_{j})\right\|_{2}^{2}$
(116) $\displaystyle\leq\sum_{i,j}\pi_{ij}r_{ij}.$

Thus in the special case where $\pi=\alpha\beta^{T}$,

(117) $\displaystyle r_{\alpha\beta}$
$\displaystyle\leq\frac{1}{{\operatorname{vol}}(G)}\sum_{i,j\in
V}\alpha_{i}\beta_{j}(H(i,j)+H(j,i))$ (118)
$\displaystyle=\frac{1}{{\operatorname{vol}}(G)}(H_{n}(\alpha,\beta)+H_{n}(\beta,\alpha)).$

∎

###### Proof of Theorem 3.22.

Let $\mu_{t}\in C^{1}([0,1])$ such that $\mu_{0}=\alpha$ and $\mu_{1}=\beta$.
Then we estimate, using Proposition 3.20 and the fact that
$L^{\dagger}=L^{\dagger}LL^{\dagger}$,

(119)
$\displaystyle\int_{0}^{1}\left\|{\mathrm{d}}\mu_{t}\right\|_{\dot{H}^{-1}(V)}^{2}{\mathrm{d}}t$
$\displaystyle=\int_{0}^{1}({\mathrm{d}}\mu_{t})^{T}L^{\dagger}{\mathrm{d}}\mu_{t}{\mathrm{d}}t$
(120)
$\displaystyle=\int_{0}^{1}(L^{\dagger}{\mathrm{d}}\mu_{t})^{T}L(L^{\dagger}{\mathrm{d}}\mu_{t}){\mathrm{d}}t$
(121) $\displaystyle=\int_{0}^{1}\sum_{(i,j)\in
E^{\prime}}w_{ij}\left|L^{\dagger}{\mathrm{d}}\mu_{t}(i)-L^{\dagger}{\mathrm{d}}\mu_{t}(j)\right|^{2}{\mathrm{d}}t$
(122) $\displaystyle=\sum_{(i,j)\in
E^{\prime}}w_{ij}\int_{0}^{1}\left|L^{\dagger}{\mathrm{d}}\mu_{t}(i)-L^{\dagger}{\mathrm{d}}\mu_{t}(j)\right|^{2}{\mathrm{d}}t$
(123) $\displaystyle\geq\sum_{(i,j)\in
E^{\prime}}w_{ij}\left|\int_{0}^{1}(L^{\dagger}{\mathrm{d}}\mu_{t}(i)-L^{\dagger}{\mathrm{d}}\mu_{t}(j)){\mathrm{d}}t\right|^{2}$

where the final inequality follows from Jensen’s inequality. Then, focusing on
the inner term and letting $e=(i,j)\in E^{\prime}$ we evaluate

(124)
$\displaystyle\int_{0}^{1}(L^{\dagger}{\mathrm{d}}\mu_{t}(i)-L^{\dagger}{\mathrm{d}}\mu_{t}(j)){\mathrm{d}}t$
$\displaystyle=B^{T}\left(\int_{0}^{1}L^{\dagger}{\mathrm{d}}\mu_{t}{\mathrm{d}}t\right)(e)$
(125)
$\displaystyle=B^{T}L^{\dagger}\left(\int_{0}^{1}{\mathrm{d}}\mu_{t}{\mathrm{d}}t\right)(e)$
(126) $\displaystyle=B^{T}L^{\dagger}(\beta-\alpha)(e).$

Hence,

(128) $\displaystyle\sum_{(i,j)\in
E^{\prime}}w_{ij}\left|\int_{0}^{1}(L^{\dagger}{\mathrm{d}}\mu_{t}(i)-L^{\dagger}{\mathrm{d}}\mu_{t}(j)){\mathrm{d}}t\right|^{2}$
$\displaystyle=\sum_{(i,j)\in
E^{\prime}}w_{ij}\left|B^{T}L^{\dagger}(\beta-\alpha)(i,j)\right|^{2}$ (129)
$\displaystyle=(L^{\dagger}(\beta-\alpha))^{T}L(L^{\dagger}(\beta-\alpha))$
(130) $\displaystyle=(\alpha-\beta)^{T}L^{\dagger}(\alpha-\beta),$

and therefore,

(131)
$\displaystyle\inf\left\\{\int_{0}^{1}\left\|{\mathrm{d}}\mu_{t}\right\|_{\dot{H}^{-1}(V)}^{2}{\mathrm{d}}t:\mu_{t}\in
C^{1}([0,1]),\mu_{0}=\alpha,\mu_{1}=\beta\right\\}\geq(\alpha-\beta)^{T}L^{\dagger}(\alpha-\beta)=\mathcal{B}_{2}(\alpha,\beta)^{2}.$

For the reverse inequality, it is sufficient to consider the special curve
$\mu_{t}=(1-t)\alpha-t\beta$, which satisfies
$\int_{0}^{1}\left\|{\mathrm{d}}\mu_{t}\right\|_{\dot{H}^{-1}(V)}^{2}{\mathrm{d}}t=(\alpha-\beta)^{T}L^{\dagger}(\alpha-\beta)=\mathcal{B}_{2}(\alpha,\beta)^{2}$.
∎

###### Proof of Theorem 3.25.

We observe first that the collection of vectors
$\\{{\mathrm{d}}T\\}_{T\in\mathcal{T}}\subset\ell(V)$ is convex; for the first
two conditions (i) and (ii) are equivalent to the intersection of a finite
number of linear constraints; and (iii) is stable under convex combinations.
Since $L^{-1/2}$ is a linear map, the image $L^{-1/2}\mathcal{A}_{i}$ will be
convex for $i=1,2$. Separately, we have for $S,T\in\mathcal{T}$:

(132) $\displaystyle\|T\alpha_{1}-S\alpha_{2}\|_{2}$
$\displaystyle=\|(\alpha_{1}-\alpha_{2})+({\mathrm{d}}T-{\mathrm{d}}S)\|_{2}$
(133)
$\displaystyle\geq\left|\|\alpha_{1}-\alpha_{2}\|_{2}-\|{\mathrm{d}}T-{\mathrm{d}}S\|_{2}\right|$
(134) $\displaystyle\geq\|\alpha_{1}-\alpha_{2}\|_{2}-2\delta>0.$

Thus,

(135) $\displaystyle\min_{S,T\in\mathcal{T}}\|T\alpha_{1}-S\alpha_{2}\|_{2}>0$

and hence $\mathcal{A}_{1}\cap\mathcal{A}_{2}=\varnothing$. Note moreover that
$L^{-1/2}$ (and more generally, any power of $L$) will act nonsingularly on
mean zero vectors since its kernel is exactly the constant functions.
Therefore, since $T\alpha_{1}-S\alpha_{2}$ is mean zero for any $T,S$, and
since $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ are disjoint, the sets
$L^{-1/2}\mathcal{A}_{1}$ and $L^{-1/2}\mathcal{A}_{2}$ are disjoint as well;
and thus they are linearly separable. ∎