Abstract
Abstract. Optimal transport is widely used in pure and applied mathematics to find probabilistic solutions to hard combinatorial matching problems. We extend the Wasserstein metric and other elements of optimal transport from the matching of sets to the matching of graphs and other structured data. This structurepreserving form of optimal transport relaxes the usual notion of homomorphism between structures. It applies to graphs, directed and undirected, labeled and unlabeled, and to any other structure that can be realized as a C-set for some finitely presented category C. We construct both Hausdorff-style and Wasserstein-style metrics on C-sets and we show that the latter are convex relaxations of the former. Like the classical Wasserstein metric, the Wasserstein metric on C-sets is the value of a linear program and is therefore efficiently computable.
Introduction
How do you measure the distance between two graphs or, in a broader sense, quantify the similarity or dissimilarity of two graphs? Metrics and other dissimilarity measures are useful tools for mathematicians who study graphs, and also for practitioners in statistics, machine learning, and other fields who analyze graph-structured data. Many distances and dissimilarities have been proposed as part of the general study of graph matching [16, 39] , yet current methods tend to suffer from one of two problems. Methods that fully exploit the graph structure, such as graph edit distances and related distances based on maximum common subgraphs [6] , are generally NP-hard to compute and must be approximated by heuristic search algorithms.
The fundamental difficulty in graph matching is that the optimal correspondence of vertices between two graphs is unknown and must be estimated from a combinatorially large set of possibilities. The theory of optimal transport [51, 52, 37] , now routinely used to find probabilistic matchings of metric spaces [35] , suggests itself as a general strategy to circumvent this combinatorial problem. Several authors have proposed specific methods to match graphs or other structured data using optimal transport [2, 11, 36, 49] .
Simplifying somewhat, current applications of optimal transport to graph matching draw on two major ideas, the Wasserstein distance between measures supported on a common metric space and the Gromov-Wasserstein distance between metric measure spaces [48, 35] . If you have a way of embedding the vertices of two graphs into a common metric space, say a Euclidean space, then you can compute the Wasserstein distance between these two subspaces [36] . Alternatively, if you have a way of converting each vertex set into its own metric space, then you can compute the Gromov-Wasserstein distance between these disjoint spaces. In the latter case, the distance between two vertices in a graph is often defined to be the length of the shortest path between them, although there are other possibilities. The two approaches, via the Wasserstein and Gromov-Wasserstein distances, can also be combined [49] .
Methods of this style reduce the problem of matching graphs to that of matching metric spaces, and then apply the usual tools of optimal transport for metric matching. While this may suffice for some purposes, it is conceptually unsatisfying for the simple reason that graphs are not identical with metric spaces. Any information that cannot be encoded in the metric is lost to optimal transport. Thus, if we take the shortest path distance on vertices, the optimal coupling of vertices depends on the graph's edges only through the lengths of the shortest paths.
Here we describe a form of optimal transport between graphs that makes no such reduction. Probabilistic mappings are established between both vertex and edge sets, and compatibility between the mappings is enforced according to the nearest analogue of graph homomorphism. These probabilistic graph homomorphisms are defined as solutions to linear programs and are therefore efficiently computable.
Our methodology is not ultimately about graphs, but about how the idea of a homomorphism, or structure-preserving map, can be deformed both probabilistically and metrically. We set forth a general notion of structure-preserving optimal transport that applies to a limited but important class of structures. This class encompasses directed, undirected, and bipartite graphs; graphs with vertex attributes, edge attributes, or both; simplicial sets, the higher-dimensional generalization of graphs; other variants of graphs, such as hypergraphs; and unrelated structures. The ensuing optimization problems are in all cases linear programs. 
. Relations of major concepts and section dependencies
Other authors have proposed convex or otherwise tractable relaxations of graph matching, based on spectral methods [10] , semidefinite programming [42] , and doubly stochastic matrices [1] . Closest to ours is the last method, which relaxes the vertex permutation of a graph isomorphism into a doubly stochastic matrix. Unlike ours, this method does not straightforwardly generalize from graph isomorphism to graph homomorphism or to metrics on graphs, nor to graphs with vertex labels or to structures other than graphs.
Let us outline in more detail the major concepts and sections of the paper. In the mainly expository Section 2, we review C-sets, the class of structures treated throughout. We give numerous examples of C-sets, including several kinds of graphs. We also introduce their functorial semantics, a device we use incessantly to equip Csets with probabilistic and metric structure, beginning in Section 3. There we relax the C-set homomorphism problem by replacing functions with their probabilistic analogue, Markov kernels. 1 We arrive at a feasibility problem reminiscent of optimal transport, although it is expressed using Markov kernels instead of couplings.
We devote the rest of the paper to studying metrics on C-sets, exact and probabilistic. Section 4 isolates the purely metric aspects of the problem. We establish a general method for lifting metrics on the hom-sets of a category S to a metric on C-sets in S, and we instantiate the theorem to define a Hausdorff-style metric on C-sets. This metric, which generalizes the classical Hausdorff metric on subsets of a metric space, is generally hard to compute, but may be of theoretical interest.
We then set out to construct a Wasserstein-style metric on C-sets, using the same framework. To do this, we must take a detour in Section 5 to define a Wasserstein metric on Markov kernels. The definition strikes us as very natural, though we can find no source for it in the literature. It is possibly of independent interest, being the probabilistic analogue of the L p metrics and the functional analogue of the usual Wasserstein metric. Finally, in Section 6, we bring together these threads to construct a Wasserstein metric on C-sets. It is a convex relaxation of the Hausdorff metric on C-sets and it is, like the classical optimal transport problem, expressible as a linear program.
The relations between the major concepts are summarized in Figure 1 .1, which also serves as a dependency graph for the sections of the paper. If the meaning of this diagram is not now entirely clear, we hope that it will become so by the end.
Graphs, C-sets, and functorial semantics
Graphs belong to a class of algebraic structures known as C-sets. As a logical system, this class is extremely simple, yet it is broad enough to encompass a range of useful and important structures, such as directed and undirected graphs and their higher-dimensional generalizations. It also easily accommodates the attachment of extra data to arbitrary substructures, as in vertex-or edge-attributed graphs.
In this section we describe the essential elements of C-sets, their morphisms, and their functorial semantics. We give many examples that should be useful in applications. Most of what we say appears in the literature on category theory [32, 33, 34, 38, 46, 47] , but we assume of the reader nothing more than the definitions of a category, a functor, and a natural transformation. Definition 2.1 (C-sets). Let C be a small category. A C-set 2 is a functor X : C → Set from the category C to the category of sets and functions.
Thus, a C-set X consists of, for every object c in C, a set X(c), and for every morphism f : c → c
, such that the assignment of functions preserves composition and identities.
Our categories C will always have finite presentations, which we regard as logical theories. A C-set is then an instance or model of that theory. A few examples will bring this out. Example 2.2 (Graphs). The theory of graphs is the category with two objects and two parallel morphisms:
A functor X : Th (Graph) → Set consists of a vertex set X(V ) and an edge set X(E), together with source and target maps X(src), X(tgt) : X(E) → X(V ) which assign the source and target vertices of each edge. Thus, a Th (Graph)-set is simply a graph.
In this paper, a "graph" without qualification is a directed graph, possibly with multiple edges and self-loops (Figure 2 .1).
3
Different kinds of graphs arise as C-sets for different categories C. Example 2.3 (Symmetric graphs). The theory of symmetric graphs extends the theory of graphs with an edge involution:
A Th (SGraph)-set, or symmetric graph, is a graph X endowed with an involution on edges, that is, a self-inverse, orientation-reversing edge map X(inv) : X(E) → X(E). Loosely speaking, a symmetric graph is a graph in which every edge has a matching edge going in the opposite direction (Figure 2 .2). Symmetric graphs are essentially the same as undirected graphs.
4
Before giving further examples, we define the notion of homomorphism appropriate for C-sets. Definition 2.4 (C-set morphisms). Let C be a small category and let X and Y be C-sets. A morphism of C-sets from X to Y is a natural transformation φ : X → Y . Thus, a C-set morphism φ : X → Y assigns a function φ c : X(c) → Y (c) to each object c ∈ C in such a way that for every morphism f : c → c
A morphism of graphs, according to this definition, is a graph homomorphism as ordinarily understood, consisting of a vertex map φ V : X(V ) → Y (V ) and an edge map φ E : X(E) → Y (E) that preserves the assignment of source and target vertices:
In the commutative diagrams, we adopt the convention of writing simply f for X(f ) or Y (f ) where no confusion can arise. Similarly, a morphism of symmetric graphs is a graph homomorphism that preserves the edge involution. The next example shows that different categories C can define essentially the same C-sets while yielding genuinely different C-set morphisms.
Example 2.5 (Reflexive graphs). The theory of reflexive graphs is
A reflexive graph is a graph whose every vertex is endowed with a distinguished loop (Figure 2. 3). As objects, reflexive graphs are the same as graphs, inasmuch as they are in one-to-one correspondence with each other. However, morphisms of reflexive graphs can "collapse" edges into vertices by mapping them onto distinguished loops, a possibility not permitted of a graph homomorphism. For this reason reflexive graph morphisms are sometimes called "degenerate maps."
Symmetry and reflexivity combine straightforwardly in symmetric reflexive graphs, in which the distinguished loops are fixed by the edge involution. Bipartite graphs form another important class of graphs.
Example 2.6 (Bipartite graphs). The theory of bipartite graphs is
A bipartite graph X consists of two vertex sets, X(U) and X(V ), and a set X(E) of edges with sources in X(U) and targets in X(V ) (Figure 2.4) . A morphism of bipartite graphs φ : X → Y has two vertex maps, φ U :
, and an edge map φ E : X(E) → Y (E) that preserves the source and target vertices.
We have not exhausted the list of graph-like structures that can be defined as C-sets. For example, hypergraphs, which generalize graphs by allowing edges with multiple sources and multiple targets, are C-sets [18, 46] . So are simplicial sets, the higher-dimensional analogue of graphs and combinatorial analogue of simplicial complexes.
Example 2.7 (Semi-simplicial sets). The semi-simplicial category, truncated to two dimensions, is
A ∆ 2 + -set, or two-dimensional semi-simplicial set, is a collection of triangles, edges, and vertices. Each triangle has three edges, in a definite order, and each edge has two vertices, also in a definite order, in such a way that the induced assignment of vertices to triangles is consistent, according to the simplicial identities (Figure 2 .5).
Semi-simplicial sets up to any dimension n, or in all dimensions n, can be defined as C-sets, as can several other kinds of simplicial sets [17, 19, 46] . We will not present the simplicial categories here, but we summarize the idea that graphs are one-dimensional simplicial sets in the table below.
1-dimensional
n-dimensional graphs semi-simplicial sets reflexive graphs simplicial sets symmetric graphs symmetric semi-simplicial sets symmetric reflexive graphs symmetric simplicial sets We take this list of examples to establish that many graph-like structures can be represented as C-sets. The next example is rather trivial, but later we use its attributed variant to recover the classical Hausdorff and Wasserstein distances as special cases of metrics on C-sets.
Example 2.8 (Sets). If 1 = { * } is the discrete category on one object, then 1-sets are sets and morphisms of 1-sets are functions.
Example 2.9 (Bisets). If 2 is the discrete category on two objects, then 2-sets are pairs of sets and morphisms of 2-sets are pairs of functions.
Example 2.10 (Dynamical systems). The theory of discrete dynamical systems is
A discrete dynamical system is a set X = X( * ) together with a function T : X → X. The set X is the state space of the system and the transformation T defines the transitions between states.
In applications, graphs and other structures often bear additional data in the form of discrete labels or continuous measurements. Data attributes are easily attached to C-sets by extending the theory C. An attributed set is thus a set X = X( * ) equipped with an map X attr − − → X(A) that assigns to each element x ∈ X an attribute value attr(x). A vertex-attributed graph is a graph X equipped with a map X(V ) attr − − → X(A) that assigns an attribute to each vertex. Such graphs are usually called "vertex-labeled" when the attribute set X(A) is discrete.
Edge-attributed, or vertex-and edge-attributed, graphs can be defined similarly. Indeed, any number of attributes can be attached to any substructure of a C-set, making the class of C-sets closed under attachment of extra data.
Often all the C-sets under consideration take attributes in a common space A, such as a fixed set of labels or a Euclidean space. In this case, we restrict the C-set morphisms φ : X → Y to those whose attribute maps X(A) = A φ A − → A = Y (A) are the identity 1 A . We will note when this restriction is in force by describing the attribute space as fixed.
At this juncture, the reader may wonder what is gained by the formalism of Csets over, say, an equational fragment of first-order logic or even ordinary, informal mathematics. This question has many valid answers, but the most pertinent is that viewing theories as categories in their own right makes it extremely simple to define models with extra structure, be it topological, metric, measure-theoretic, or otherwise. We simply replace the category Set of sets and functions with a category S having that extra structure. Definition 2.13 (Functorial semantics). Let C be a small category and let S be any category. The functor category [C, S] has functors C → S as objects and natural transformations between them as morphisms. We call the objects of this category S-valued C-sets or C-sets in S.
Functorial semantics goes back to Lawvere's pioneering thesis [30] . When S = Set, we recover the original definitions of C-sets and C-set morphisms. So, in our main example, the category of graphs and graph homomorphisms is the category of functors Th (Graph) → Set, that is,
The starting point for much subsequent development is the category Meas of measurable spaces and measurable functions, defined more carefully below. A measurable C-set, or C-set in Meas, is a C-set X whose internal sets X(c) are equipped with σ-algebras and whose internal maps X(f ) are measurable with respect to these σ-algebras. We will introduce other categories as we need them. Throughout the paper we explore the consequences of enriching graphs and other C-sets with metrics, measures, and Markov morphisms.
Markov morphisms of measurable C-spaces
On the topic of matching of C-sets, the seemingly most elementary question one can ask is: Problem 3.1 (C-set homomorphism). Given C-sets X and Y , does there exist a C-set morphism φ : X → Y ? For C = 1, the problem is trivial. A function φ : X → Y exists if and only if the codomain Y is nonempty. But for other categories C the problem is computationally hard. The graph homomorphism problem, occurring when C = Th (Graph), is a famous NP-complete problem.
5
In the case of reflexive graphs, the homomorphism problem becomes trivial again, because there is a reflexive graph morphism X → Y if and only if codomain Y is nonempty (contains a vertex). Yet the same cannot be said of similar matching problems, such as:
The isomorphism problem for reflexive graphs is equivalent to the graph isomorphism problem, so is once again computationally hard. In summary, while the complexity depends on the category C and on the specific C-sets under consideration, it is generally computationally intractable to find C-set morphisms, to say nothing of enumerating them or optimizing over them.
A popular strategy for solving hard combinatorial problems, especially when inexact solutions are acceptable, is to relax the problem to a continuous one that is easier to solve. Functorial semantics offer a simple way to implement this strategy: replace the category Set with a category having better computational properties. In what will be a recurring theme, we replace categories of functions with categories of Markov kernels, which are the probabilistic analogue of functions. The reader unfamiliar with Markov kernels will find references and a short review in Appendix A. [55, 14] .
Functions are Markov kernels that contain no randomness. To be more formal, a Markov kernel M : X → Y is deterministic if for every x ∈ X, the distribution M(x) is a Dirac delta measure. Given any measurable function f :
, and every deterministic Markov kernel arises uniquely in this way. Measurable functions can therefore be identified with deterministic Markov kernels. Moreover, the identification is functorial. Given composable measurable functions X f − → Y g − → Z, one easily checks that M(f · g) = Mf · Mg. Also, M(1 X ) = 1 X . We summarize these statements by saying that M : Meas → Markov is an identity-on-objects embedding functor. In what follows we will not always distinguish notationally between a function f and its corresponding Markov kernel M(f ).
Let us now make precise the relaxation of the C-set homomorphism problem. Strictly speaking, the relaxation is not from C-sets, but from measurable C-sets. A measurable C-space is a C-set in Meas.
The sought-after relaxation is a nearly immediate consequence of the embedding Meas in Markov. 
in Markov commutes.
Proposition 3.7 (Relaxation of C-set homomorphism). Given measurable C-spaces X and Y , the problem of finding a Markov morphism Φ : X → Y is a convex relaxation of the problem of finding a (measurable) morphism φ : X → Y .
Proof. The proposition makes two assertions, concerning relaxation and convexity. To establish the relaxation, observe that if φ : X → Y is a measurable morphism, then M(φ) := (M(φ c )) c∈C : X → Y is a Markov morphism, because, by functoriality, the embedding M : Meas → Markov preserves naturality squares:
. 
Thus

Graphs with no homomorphisms or Markov morphisms
As for the convexity, the Markov morphism problem,
is a convex feasibility problem, possibly in infinite dimensions. The variables, namely Markov kernels Φ c : X(c) → Y (c) indexed by c ∈ C, form a convex space, and the constraints are linear in the variables.
One way to think about this result is that the constraints defining a C-set morphism, which are only formally linear, become actually linear upon relaxation. In the case of greatest practical interest, when the C-sets are finite, the result is a linear program.
To make this as transparent as possible, let us write out the linear program. Given finite C-sets X and Y , identify a function X(f ) : X(c) → X(c ′ ) with a binary matrix X(f ) ∈ {0, 1} |X(c)|×|X(c ′ )| whose rows sum to 1 and identify a Markov kernel
where · denotes the usual matrix multiplication and ½ denotes the column vector of all 1's (whose dimensionality is left implicit in the notation). This feasibility problem is a linear program with linear equality constraints and nonnegativity constraints. 
, and a Markov kernel on edges, Φ E : X(E) → Y (E), such that the two diagrams
in Markov commute. Since the vertex and edge maps are nondeterministic, it does not make sense to ask that the source and target vertices be preserved exactly, as in a graph homomorphism. The naturality squares assert the next best thing, that for every edge e in X(E), the distribution of e's source vertex under Φ V is equal to that of the source vertices in the edge distribution of e under Φ E , and similarly for target vertices.
We bring out the difference between graph homomorphisms and Markov morphisms in a series of examples. Between the graphs X and Y of Figure 3 .1, there are two graph homomorphisms φ 1 , φ 2 : X → Y , corresponding to the two directed paths in Y . Both are, of course, Markov morphisms, as is any mixture Φ = tφ 1 + (1 − t)φ 2 , where t ∈ [0, 1]. In this case, every Markov morphism is a mixture of graph homomorphisms, so little is lost (or gained) by the relaxation. Figure 3 .2 presents a similar picture. The graph X is a loop and the graph Y is a cycle, though not a directed one. There are no Markov graph morphisms from X to Y , deterministic or otherwise. Figure 3 .3 looks superficially similar, with the graph Y now a directed cycle, but the outcome is more interesting. As before, there is no graph homomorphism from X to Y , but there is a Markov morphism. In fact, if C n is the directed cycle of length n, then for any m, n ≥ 1, a Markov morphism Φ : C m → C n is given by assigning the uniform distributions on all vertices and edges:
In particular, it is sometimes possible to find a Markov graph morphism that is not a mixture of deterministic morphisms, proving that the notion of Markov homomorphism is genuinely weaker than graph homomorphism. That should not be surprising, given that the graph homomorphism problem is NP-hard, while the Markov graph morphism problem is a linear program, hence solvable in polynomial time. Finally, Figure 3 .4 shows the terminal graph for both deterministic and Markov morphisms. Any graph X has a unique graph homomorphism, indeed a unique Markov morphism, into the loop Y . One might suppose that the strategy for relaxing C-set homomorphism carries over directly to C-set isomorphism, but that is not so. The constraints imposed by isomorphism are bilinear, not linear, so convexity would be lost in a direct translation. The problem is not just computational, though, as the following result shows. Proof. Under the given assumptions, the extreme points of the convex set Prob(X) of probability measures on X are exactly the point masses [45, Example 8.16 ]. If M : X → Y is an isomorphism in Markov, then it acts as a linear isomorphism on Prob(X) and hence preserves the extreme points of Prob(X). Thus, for every x ∈ X, there exists y ∈ Y such that M(x) = δ x M = δ y , which proves that M is deterministic.
As there is nothing to be gained, computationally or mathematically, by looking at the isomorphisms in Markov, we will formulate the isomorphism problem in a different way. Let X and Y be finite C-sets and equip every set With this motivation, we define: Definition 3.10 (Measure C-spaces). The category Meas * has σ-finite measures on Polish measurable spaces as objects and measurable maps as morphisms. The category Markov * has the same objects and Markov kernels as morphisms.
A measure C-space is a C-set in Meas * .
Recall that a measurable map f :
between measure spaces is measure-preserving if µ X M = µ Y , as expressed in the operator notation of Definition A.3. When the measure spaces coincide, that is, X = Y and µ X = µ Y , the measure µ X is also called an invariant measure of f or M. Let Fix(Meas * ) and Fix(Markov * ) denote the subcategories of Meas * and Markov * whose morphisms preserve measure.
Example 3.11 (Invariant dynamics). A discrete dynamical system in Fix(Meas * ) is a measure-preserving dynamical system, the basic object of study in ergodic theory. A discrete dynamical system in Fix(Markov * ) is a Markov chain together with an invariant measure. Due to the motivating case of finite sets and counting measures, the problem of measure C-space homomorphism is no easier to solve than C-set isomorphism; however, its relaxation to measure-preserving Markov morphism is easier to solve, being a convex feasibility problem. Proposition 3.13 (Relaxation of measure-preserving C-set morphism). Given measure C-spaces X and Y , the problem of finding a measure-preserving Markov morphism Φ : X → Y is a convex relaxation of the problem of finding a measurepreserving morphism φ : X → Y .
Proof. For any function f on a measure space µ, we have µf = µM(f ). Thus, measure-preserving functions correspond to measure-preserving deterministic kernels, and the embedding M : Meas * → Meas * restricts to an embedding Fix(Meas * ) → Fix(Markov * ). The relaxation follows by the argument of Proposition 3.7. To prove the convexity, observe that the measure-preserving Markov morphism problem,
merely adds linear equality constraints to the Markov morphism problem.
As before, when the C-sets are finite, the feasibility problem is a linear program.
Insisting that Markov kernels preserve measure brings us closer to classical optimal transport, formulated in terms of couplings. For any Markov kernel M : X → Y preserving finite measures µ X and µ Y , the product measure µ X ⊗ M has marginals µ X and µ X M = µ Y and hence is a coupling of µ X and µ Y . Conversely, if π is a product measure on X × Y with marginals µ X and µ Y , then by the disintegration theorem (Theorem A.4), there exists a Markov kernel M : X → Y , unique up to sets of µ X -measure zero, such that π = µ X ⊗ M, and any such kernel M satisfies µ X M = µ Y . So, up to null sets, couplings and measure-preserving Markov kernels are the same. They are even the same as morphisms of measure spaces. Couplings have a standard composition law, known in optimal transport as the gluing lemma [51, Lemma 7.6], and the composition laws for couplings and kernels are compatible.
Despite this equivalence, we formulate the content of this paper entirely using Markov kernels, not couplings. In order to compose couplings, one must first compute disintegrations, and, while disintegration is a linear operation, introducing it complicates the optimization problem. Also, and more importantly, we routinely use Markov kernels that are not measure-preserving. There is no correspondence between general Markov kernels and couplings. The difference, roughly speaking, is that Markov kernels are the probabilistic analogue of functions, while couplings are an analogue of bijections, or of correspondences [35] .
Incidentally, workers in optimal transport have long observed that the measurepreserving property of a coupling, which in particular requires that the coupled measures have equal mass, is burdensome in applications. In response various notions of unbalanced optimal transport have been proposed [37, Section 10.2] . Markov kernels offer another alternative to couplings.
Hausdorff metric on metric C-spaces
The C-set homomorphism problem is too stringent for practical matching of graphs and other structures. Morphisms of C-sets, even Markov morphisms, are all-ornothing: either they exist or they do not, and when they do exist, they are distinguished only by coarse qualitative distinctions, like that of homomorphism versus isomorphism. This is problematic in scientific and statistical applications, in which the data, be it structural or numerical, is generally subject to randomness and measurement error. To be tolerant to noise, we should use an inexact, quantitative measure of structural similarity or dissimilarity. One approach to dissimilarity, possibly the most important, is via the ubiquitous mathematical concept of metric.
Throughout the rest of this paper, we develop the metric approach to matching C-sets. We will eventually, in Section 6, construct a computationally tractable, Wasserstein-style metric on C-sets. In this section, we focus on the purely metric aspects of the problem. The Hausdorff-style metric on C-sets that we propose is generally hard to compute, but is helpful in isolating the metric concepts from the probabilistic. It may also be interesting in its own right, as a theoretical tool.
The central idea is to weaken the constraints defining a C-set homomorphism from exact equality to approximate equality, with the quality of approximation determined by a metric on morphisms. Schematically, if X and Y are C-sets and φ : X → Y is a transformation, not necessarily natural, then for each morphism f : c → c ′ in C, we have a "lax" naturality square
where the double arrow represents the value
. We aggregate these values over all morphisms, or all morphism generators, f : c → c ′ in C to obtain an total nonnegative weight for the transformation. The Hausdorff distance d H (X, Y ) is the weight attained by optimizing over all transformations φ : X → Y .
As a first step in rendering this idea precise, we recall the basic concepts of metric spaces and metrics on function spaces. It is convenient to work with a definition of metric that is more general than the classical notion.
Definition 4.1 (Metric spaces). A Lawvere metric space, which we call simply a metric space, is a set X together with a function d X : X × X → [0, ∞], taking values in the extended nonnegative real numbers, that satisfies the identity law, d X (x, x) = 0 for all x ∈ X, and the triangle inequality,
A metric space (X, d X ) is classical if three further axioms are satisfied:
The category Met has metric spaces as objects and functions between them as morphisms.
Unless otherwise noted, all metrics in this paper are in the above generalized sense.
Example 4.2 (Shortest path distance). To reprise an example from Section 1, if X is a graph, then a metric is defined on its vertices by letting d X(V ) (v, v ′ ) be the length of the shortest directed path from v to v ′ . The metric is finite if X is finite and strongly connected, it is always positive definite, and it is symmetric if X is a symmetric graph. Generalizing slightly, if X is a weighted graph, where each edge carries a nonnegative weight, a metric on its vertices is defined by the shortest weighted path. This metric is positive definite if the edge weights are strictly positive.
As outlined above, we will work with C-sets in categories S admitting a measure of distance between morphisms.
Definition 4.3 (Metric categories).
A metric category is a category enriched in Met, i.e., a category S whose hom-sets S(X, Y ) each have the structure of a metric space.
Under the supremum metric, Met is itself a metric category. Recall that for any set X and metric space Y , the supremum metric on functions f, g : X → Y is defined by
When Y is a classical metric space, the supremum metric is also classical when restricted to bounded functions, i.e., to functions f : X → Y such that
for some (and hence any) y 0 ∈ Y .
Another prominent example of a metric category comes from metric measure spaces. Later, in Section 6, we will see other examples. Definition 4.4 (Metric measure spaces). A metric measure space, or mm space, is a Polish measurable space X together with a metric d X and a σ-finite measure µ X . We do not assume that d X is a classical metric or that it metrizes the topology of X, although we do require that d X be lower-semicontinuous with respect to the topology of X and so, in particular, be Borel measurable.
10
The category MM has metric measure spaces as objects and measurable functions as morphisms.
Under any of the L p metrics, MM is a metric category. Recall that for any measure space X and metric space Y , the L p metric on measurable functions f,
The essential supremum metric differs from the supremum metric only in being insensitive to sets of µ X -measure zero. When Y is a classical metric space, the L p metrics are also classical when restricted to the L p spaces. In this context, the space L p (X, Y ) consists of equivalence classes of functions f : X → Y that have finite moments of order p,
p µ X (dx) < ∞ for some (and hence any) y 0 ∈ Y , when 1 ≤ p < ∞, or that are essentially bounded, when p = ∞. The equivalence relation is that of equality µ X -almost everywhere.
Definition 4.5 (Metric C-spaces).
A metric C-space is a C-set in Met. Likewise, a metric measure C-space, or mm C-space, is a C-set in MM.
As Met and MM are metric categories, we will be able to define quantitative measures of dissimilarity between metric C-spaces and between metric measure Cspaces. However, in order that the dissimilarity measures be metrics, we must restrict the C-set transformations to those whose components do not increase distances. We now formulate this requirement abstractly, for a general metric category S. 
The class of morphisms in S that do not increases distances upon pre-composition is clearly closed under composition and includes the identities, and likewise for postcomposition. The short morphisms in S therefore form a subcategory of S, which we denote by Short(S).
Characterizing the short morphisms of metric spaces and metric measure spaces is straightforward. The first example shows that our terminology is consistent with standard usage. 
Consequently, Short(Met) is the category of metric spaces and short maps.
Proof. For any functions f : X → Y and g, g ′ : Y → Z, we have
If, moreover, f is a short map, then for any functions h, h
Thus short maps are short morphisms of Met. Conversely, if f : X → Y is a short morphism, let e x : I → X denote the unique map from the terminal space I = { * } onto x ∈ X. Then for any x, x ′ ∈ X,
proving that f is a short map. On the other hand, not every short map can be extended to a graph homomorphism (consider a constant map). Thus, shorts map of graphs are a weakening of graph homomorphisms.
Proposition 4.9 (Short morphisms of mm spaces). The short morphisms between metric measure spaces X and Y are measurable maps f : X → Y that are both measure-decreasing,
and distance-decreasing,
Consequently, Short(MM) is the category of mm spaces and distance-and measuredecreasing maps.
11 Other names for short maps are "contractions," "distance-decreasing maps," "metric maps," and "nonexpansive maps." Alternatively, short maps are Lipschitz functions with Lipschitz constant 1. The category of metric spaces and short maps was first studied by Isbell [23] , in the case of classical metric spaces, and by Lawvere [31] , in the case of generalized metric spaces.
Proof. We prove only the case 1 ≤ p < ∞.
First, we show that f : X → Y is measure-decreasing if and only if pre-composing with f decreases L p distances. If f is measure-decreasing, then for measurable func-
Conversely, if f is not measure-decreasing, then there exists a set B ∈ Σ Y such that µ X f (B) > µ Y (B). Choose a classical metric space Z with at least two points z and z ′ , let g : Y → Z be the constant function at z, and let g ′ : Y → Z be the function equal to z ′ on B and equal to z outside of B. Then, by construction,
. Now we show that f : X → Y is distance-decreasing (a short map of metric spaces) if and only if post-composing with f decreases L p distances. If f is distancedecreasing, then for any measurable functions h, h
For the converse direction, let I = { * } be the singleton probability space and let e x : I → X denote the generalized elements, as in the proof of Proposition 4.7. Then for any x,
proving that f is distance-decreasing.
We saw in Section 3 that a measure-preserving function is a surrogate for a bijection. Likewise, a measure-decreasing function is a surrogate for an injection, since a function on finite sets is measure-decreasing with respect to counting measure if and only if it is injective. For functions on finite measure spaces of equal mass, particularly probability spaces, being measure-decreasing is the same as being measurepreserving. The elementary version of this fact is that on finite sets of equal size, injections are the same as bijections.
By definition, a metric category is a category enriched in Met. The enrichment extends to short morphisms in that for any category S enriched in Met, the subcategory Short(S) is enriched in Short(Met). We digress slightly to clarify this statement. (ii) For any morphisms
and for any morphisms
Proof. Conditions (i) and (ii) are equivalent by the definition of an enriched category. We prove that (ii) and (iii) are equivalent. If (ii) holds, then taking f = g gives
). Conversely, if (iii) holds, then by the triangle inequality,
We now define a Hausdorff-style metric on C-sets in a general metric category S. We instantiate it with S = Met and S = MM below and with other metric categories in Section 6. In the definition, fix 1 ≤ p ≤ ∞ and write the ℓ 1/p when p < ∞ and a + p b = max{a, b} when p = ∞.
Definition 4.11 (Hausdorff metric on C-sets).
Let C be a finitely presented category and let S be a metric category. The Hausdorff metric on C-sets in S is given by, for
where the ℓ p sum is over a fixed, finite generating set of morphisms in C and the infimum is over all transformations φ : X → Y , not necessarily natural, whose components φ c : X(c) → Y (c) in S are short morphisms (so belong to Short(S)).
The Hausdorff metric is indeed a metric, albeit not a classical one. Theorem 4.12. As defined above, the Hausdorff metric on C-sets in S is a metric.
Proof. For any C-set X in S, taking the identity transformation 1 X : X → X gives
So we need only verify the triangle inequality. Let X, Y , and Z be C-sets in S. 
Take the infimum over the transformations φ : X → Y and ψ :
To prove the triangle inequality for the weights, let X φ − → Y ψ − → Z be composable transformations and consider a "pasting diagram" of form
Here is the argument encoded informally by this diagram, which is easy to understand if cumbersome to write down. Since the components of φ and ψ are short morphisms, we have
Therefore, by the triangle inequality in the hom-space S(X(c), Z(c ′ )),
This completes the proof of the triangle inequality for |−| f and hence also for d H .
The assumptions of the theorem can be weakened or strengthened with concomitant effects on the conclusion. Remark 4.13 (General cost functions). As the proof shows, the restriction to short morphisms is what guarantees the triangle inequality. Thus, in situations where the triangle inequality is inessential, we are free to take the infimum over arbitrary transformations φ : X → Y with components in S. We may as well also allow the hom-sets of S to carry general cost functions, not necessarily metrics.
Remark 4.14 (Generators and composites). From the coordinate-free perspective of categorical logic, the restriction to a finite generating set of morphisms in C is open to criticism, since it makes the Hausdorff metric depend on how the category C is presented. Can anything be said about the deviation from naturality for a generic morphism in C? In general, no. If, however, we strengthen the assumptions to include X and Y being C-sets in Short(S), not merely in S, then for any composable
shows that for all transformations φ : X → Y , |φ| f ·g ≤ |φ| f + |φ| g . Thus, for C-sets X and Y in Short(S), bounds on the weights of φ : X → Y at generators yield wscott@example.org.
We emphasize that the Hausdorff metric on S-valued C-sets is not a classical metric. Even when the underlying metrics on S are symmetric, the Hausdorff metric is not, although it can be symmetrized in one of the usual ways, such as
. As a more fundamental matter, the Hausdorff metric is not positive definite, since d H (X, Y ) = 0 whenever there exists a C-set homomorphism φ : X → Y with components in Short(S). Similar statements apply to the symmetrized metrics. Indeed, under any reasonable definition, the distance between isomorphic C-sets should be zero, so we cannot expect to get positive definiteness without passing to equivalence classes of isomorphic C-sets. This is not a matter we will pursue.
We turn now to concrete examples. We frequently need to make a metric space out of a set with no metric structure. There are several generic ways to do this, but the most useful is the discrete metric, defined on a set X as
A map f : X → Y out of a discrete metric space X is always short.
13
We can make a C-set X into a metric C-space by equipping every set X(c), c ∈ C, with the discrete metric. On such discrete metric C-spaces, the Hausdorff metric reduces to the C-set homomorphism problem:
It can therefore be at least as hard to compute the Hausdorff metric on metric C-spaces as it is to solve the C-set homomorphism problem, which is generally NPhard. Overcoming such computational difficulties is a major motivation for Sections 5 and 6. More interesting things happen when the underlying metrics are not all discrete. As a first example, we show that the classical Hausdorff metric on subsets of a metric space is a special case of the Hausdorff metric on C-sets, justifying our terminology. 
which is the classical Hausdorff metric in non-symmetric form. Assuming A is a symmetric metric space, we recover the standard Hausdorff metric upon symmetrization:
In the next two examples, we define several possible Hausdorff metrics on graphs.
Example 4.16 (Hausdorff metric on attributed graphs). Let X and Y be vertexattributed graphs, as in Example 2.12, with discrete metrics on the vertex and edge sets and arbitrary metrics on the attribute sets. Then X and Y are attributed graphs in Met and the Hausdorff distance between them is
where the infimum is over graph homomorphisms φ = (φ V , φ E ) : X → Y and short maps φ A : X(A) → Y (A). This metric optimizes both the graph homomorphism and the matching of the attribute spaces X(A) and Y (A). If instead we fix a metric space A for the attributes, the Hausdorff distance is
where the infimum is now only over graph homomorphisms φ : X → Y .
Example 4.17 (Weak Hausdorff metric on graphs)
. Let X and Y be graphs, with discrete metrics on the edge sets, the shortest path distances of Example 4.2 on the vertex sets, and counting measures on both vertex and edge sets. Then X and Y are graphs in MM and, for p = 1, the Hausdorff distance between them is
where the infimum is over injective maps φ E : X(E) → Y (E) of the edges and injective short maps φ V : X(V ) → Y (V ) of the vertices. If X is monomorphic to Y , that is, there is an injective graph homomorphism from X to Y , then d H (X, Y ) = 0. But, unlike the previous example, we can still have d H (X, Y ) < ∞ even when X is not homomorphic to Y , because the edge map is allowed violate the source and target constraints. A concrete example is shown in Figure 4 .1. The 2-cycle X is plainly not homomorphic to the 4-cycle Y , but, due to the pictured transformation, the Hausdorff distance from X to Y is d H (X, Y ) = 2. In general, if C n is the directed cycle of length n, then it can be shown that d H (C m , C n ) = min{m, n − m} for any 1 ≤ m ≤ n. This quantity is the length of the shortest path between the endpoints of an m-path on the n-cycle. In the other direction, d H (C m , C n ) = ∞ when m > n since there is no longer any injection from C m to C n .
A stream of further examples can be generated by combining the features above, namely data attributes and metric weakening of the homomorphism constraints, in graphs or in other C-sets, such as symmetric graphs, reflexive graphs, and their higher-dimensional generalizations. 
Wasserstein metric on Markov kernels
Our goal is now to define a Wasserstein-style metric on metric measure C-spaces, thus bringing together the threads of the two preceding sections. As a first step, we define a metric on Markov kernels, to serve the same role for the Wasserstein metric as the supremum or L p metrics do for the Hausdorff metric. Defining a metric on Markov kernels is more subtle than defining a metric on functions, and will be the subject of this section.
The Wasserstein metric on Markov kernels generalizes the Wasserstein metric on probability distributions. Our development parallels that of the classical metric theory for optimal transport, to be found, for instance, in [51, Chapter 7] or [52, Chapter 6] . In this spirit, we begin with two notions of coupling for Markov kernels. The set of all couplings of Markov kernels M and N is denoted by Coup(M, N) and the set of all products by Prod(M, N).
To phrase it differently, a Markov kernel Π : X → Y × Z is a coupling of M : X → Y and N : X → Z if for every x ∈ X, the probability distribution Π(x) is a coupling of M(x) and N(x). Similarly, a Markov kernel Π : W × X → Y × Z is a product of M : W → Y and N : X → Z if for every w ∈ W and x ∈ X, the distribution Π(w, x) is a coupling of M(w) and N(x). In the special case where W and X are singleton sets, couplings and products of Markov kernels coincide and amount to couplings of probability measures.
The set of products of Markov kernels M : W → Y and N : X → Z is never empty, because one can always take the independent product,
given by the pointwise independent product of probability measures. When the kernels M and N share a common domain X, products are extensions of couplings, because any product Π ∈ Prod(M, N) gives rise to a coupling ∆ X · Π ∈ Coup(M, N) by pre-composing with the diagonal map ∆ X : x → (x, x). In particular, the set of couplings is never empty either.
Definition 5.2 (Wasserstein metrics on Markov kernels). Let
This metric generalizes two famous constructions in analysis. When the kernels are deterministic, we recover the L p metric on functions between metric measure spaces, reviewed in Section 4. When X = { * } is a singleton set, the kernels M and N can be identified with probability measures µ = M( * ) and ν = N( * ), and we recover the classical Wasserstein metric on probability measures,
The relationships between the base metric and its derived metrics are summarized in the diagram of Figure 5 .1. It is possible to define a Wasserstein metric on Markov kernels in the case p = ∞, generalizing the L ∞ metric on functions and the W ∞ metric on probability measures [9] , [41, Section 3.2]. We do not pursue this case here, as the optimization problem ceases to be linear in the coupling Π.
We need to verify that the proposed metric on Markov kernels is actually a metric. As in the proof for the classical Wasserstein metric, the main property to verify is the triangle inequality, and crucial step in doing so is establishing a gluing lemma. Loosely speaking, the gluing lemma says that Markov kernels into X × Y and Y × Z that share a common marginal along Y can be glued along Y to form a Markov kernel into X × Y × Z. 
satisfies the desired properties.
By a variant of the usual gluing argument, we show that the Wasserstein metric on Markov kernels is indeed a metric.
Theorem 5.4. Let X and Y be metric measure spaces. For any 1 ≤ p < ∞, the Wasserstein metric of order p on Markov kernels X → Y is a metric.
Moreover, if Y is a classical metric space, then the Wasserstein metric is also classical when restricted to equivalence classes of Markov kernels with finite moments of order p, i.e., to Markov kernels M :
for some (and hence any) y 0 ∈ Y , where we regard Markov kernels M and
Proof. We prove the triangle inequality first. Let , i < j, are the evident projections. Forming the coupling Π 13 := Π · proj 13 ∈ Coup(M 1 , M 3 ), we estimate
where we apply the triangle inequality in the second inequality and Minkowski's inequality on L p (X ×Y 3 , µ X ⊗Π) in the third inequality. Since the resulting inequality holds for any couplings Π 12 and Π 23 , we conclude that 
Moreover, for any Markov kernel
For each such x, since the metric d Y is positive definite, Π(x) is concentrated on the diagonal. Thus Π(x) = ν · ∆ Y for some probability measure ν on Y and hence
e. x ∈ X, and we conclude that W p is positive definite. Next, W p is symmetric since the base metric d Y is. Finally, by taking the independent coupling and using Minkowski's inequality again, it is easy to show that W p is finite on Markov kernels with finite moments of order p.
In the second half of the proof, we assumed the following result. 
Proof. According to a known existence theorem for optimal couplings (Theorem A.6), the infimum can even be achieved simultaneously at every point x. That is, there exists a coupling Π ∈ Coup(M, N) such that for every x ∈ X,
The proof even shows that the Wasserstein metric on Markov kernels can be written in terms of the Wasserstein metric on probability measures as
Thus, if we view a Markov kernel X → Y as a function X → Prob(Y ) of metric spaces, the Wasserstein metric on Markov kernels reduces to the familiar L p metric.
However, this result depends on the existence theorem for optimal couplings (Theorem A.6), the proof of which is non-trivial. Wherever possible we prefer to work with the original Definition 5.2 in terms of couplings of Markov kernels. When at least one of the kernels is deterministic, the Wasserstein metric has a simple, closed-form expression.
Proposition 5.6 (Wasserstein metric on deterministic kernels). Let X, Y, Z be metric measure spaces. For any Markov kernel M : X → Y and measurable functions f : X → Z and g : Y → Z,
In particular, for any measurable functions f, g : X → Y ,
Proof. To prove the first statement, notice that f and M · g have a single coupling, at once deterministic and independent. By Tonelli's theorem,
The second statement follows from the first by taking X = Y and M = 1 X .
Wasserstein metric on metric measure C-spaces
We are at last ready to construct a Wasserstein-style metric on metric measure C-spaces, combining the general metric theory for C-sets with the Wasserstein metric on Markov kernels.
Let MMarkov be the category with metric measures spaces as objects and Markov kernels as morphisms. In Section 3, we identified measurable functions with deterministic Markov kernels, obtaining an embedding functor M : Meas → Markov and thus a relaxation of the C-set homomorphism problem. In exactly the same way, the category MM of metric measure spaces is functorially embedded inside MMarkov. We denote this embedding also by M : MM → MMarkov. Just as we relaxed the C-set homomorphism problem, so will we relax the Hausdorff metric on mm C-spaces.
As a first step, we make MMarkov into a metric category compatible with the L p metrics. By Theorem 5.4, MMarkov is a metric category under the Wasserstein metric of order p, for any 1 ≤ p < ∞. Furthermore, by Proposition 5.6, this metric agrees with the corresponding L p metric on deterministic Markov kernels. Thus, the embedding M : MM → MMarkov is an isometry of metric categories.
In Section 4, we characterized the short morphisms of MM under its L p metric. The next proposition extends this characterization to MMarkov, formally reducing to Proposition 4.9 when all the morphisms are deterministic Markov kernels. Consequently, the isometric embedding functor M : MM → MMarkov restricts to an embedding Short(MM) → Short(MMarkov) of short morphisms. (
for all Markov kernels P, P ′ : W → X if and only if M is distance-decreasing of order p, i.e., there exists a product Π of M with itself such that
Consequently, a Markov kernel is a short morphism if and only if it is distancedecreasing and measure-decreasing. Short(MMarkov) is the category of mm spaces and distance-and measure-decreasing Markov kernels. 
. Let Z be a classical metric space with at least two points z and z ′ , let g : Y → Z be the constant function at z, and let g ′ : Y → Z be the function equal to z ′ on B and equal to z outside of B. The composite Mg is also constant, so by Proposition 5.6 we have
To prove part (b), suppose M : X → Y is distance-decreasing, and let Π be a product of M with itself that attains the bound. For any coupling Λ : W → X × X of P and P ′ , the composite Λ · Π : W → Y × Y is a coupling of P · M and P ′ · M. Therefore,
Since Λ ∈ Coup(P, P ′ ) is arbitrary, we obtain
Conversely, suppose this inequality holds for all Markov kernels P, P ′ . As in the proofs of Propositions 4.7 and 4.9, let W = I = { * } be the singleton probability space and let e x : I → X denote the generalized element at x ∈ X. For any x, x ′ ∈ X, take P = e x and P
Conclude that M is distance-decreasing.
The Wasserstein metric on mm C-spaces is the Hausdorff metric (Definition 4.11) on C-sets in the metric category MMarkov. In concrete terms, the definition is: Definition 6.2 (Wasserstein metric on mm C-spaces). Let C be a finitely presented category. For any 1 ≤ p < ∞, the Wasserstein metric of order p on metric measure C-spaces is given by, for X, Y ∈ [C, MM],
, where the sum is over a fixed, finite generating set of morphisms in C and the infimum is over all Markov transformations Φ : X → Y , not necessarily natural, whose components Φ c : X(c) → Y (c) are short morphisms (so belong to Short(MMarkov)).
indexed by objects c ∈ C and morphisms f : c → c ′ generating C, and subject to the constraints, for all c ∈ C,
In this optimization problem, the optimization variables belong to convex spaces, the objective is linear, and all the constraints, including those for couplings and products, are linear equalities or inequalities. The problem is therefore convex.
As in Section 3, the optimization problem is a linear program provided the C-sets are finite. Let X and Y be finite metric measure C-spaces. Identifying Markov kernels with right stochastic matrices, measures with row vectors, and exponentiated metrics d
is the value of the linear program:
We leave implicit in the notation the dimensionalities of the projection operators proj i and of column vectors ½ consisting of all 1's.
While it appears forbidding, this linear program simplifies in certain common situations. When X(c) has the discrete metric, any Markov kernel Φ c : X(c) → Y (c) is distance-decreasing, so the product Π c and associated constraints can be eliminated from the program. When X(c
is fixed to be the identity, as happens for fixed attribute sets, then for any morphism f : c → c ′ , the Wasserstein distance between Xf and Φ c · Y f has a closed form (Proposition 5.6). The coupling Π f and associated constraints can thus be eliminated.
Both kinds of simplification occur in the next two examples.
Example 6.4 (Classical Wasserstein metric). Continuing Examples 2.11 and 4.15, let X and Y be attributed sets, equipped with discrete metrics and any probability measures, and taking attributes in a fixed mm space A. Then X and Y are attributed sets in MM and the Wasserstein metric of order p between them is 
, where the infimum is over Markov graph morphisms Φ : X → Y with measuredecreasing components Φ V and Φ E .
This metric takes an infinite value whenever no Markov graph morphism exists. The next example features a weaker metric, presented, for simplicity, in the case of unattributed graphs. Example 6.6 (Weak Wasserstein metric on graphs). Let X and Y be graphs. Continuing Example 4.17, equip the edge sets with discrete metrics, the vertex sets with shortest path distances, and the vertex and edge sets with counting measures. The Wasserstein metric of order 1 is then
where the infimum is over measure-decreasing Markov kernels Φ E and distance-and measure-decreasing Markov kernels Φ V . By Proposition 6.3, this metric relaxes the Hausdorff metric of Example 4.17. It is genuinely weaker: on directed cycles, we have d W,1 (C m , C n ) = 0 when 1 ≤ m ≤ n, as witnessed by the uniform Markov graph morphisms of Example 3.8. (They do not increase distances, like any Markov kernels equal everywhere to a constant distribution.) We still have d W,1 (C m , C n ) = ∞ when m > n due to the measure-decreasing constraint.
Conclusion
We have introduced Hausdorff and Wasserstein metrics on graphs and other Csets and illustrated them through a variety of examples. That being said, we have established only the most basic properties of the concepts involved. Possibilities abound for extending this work, in both theoretical and practical directions. Let us mention a few of them.
Although encompassing graphs, simplicial sets, dynamical systems, and other structures, the formalism of C-sets remains possibly the simplest equational logic, sitting at the bottom of a hierarchy of increasingly expressive systems [29, 12] . By admitting categories C with extra structure, such as sums, products, or exponentials, more complicated structures can be realized as structure-preserving functors from C into Set or some other category S. For example, categories with finite products describe monoids, groups, rings, modules, and other familiar algebraic structures. This is the original setting of categorical logic [30] .
Many of the ideas developed here extend to categories C with extra structure. The pertinent questions are whether the extra structure can be accommodated in the category Markov and its variants and how this affects the computation. Sums (coproducts) and units (terminal objects) are easily handled. Markov has finite sums and a unit, and since the direct sum of Markov kernels is a linear operation, it preserves the class of linear optimization problems. Products are more important and more delicate. Markov does not have categorical products, and its natural tensor product, the independent product, is not a linear operation. In keeping with the spirit of this paper, products in C should be translated into optimal couplings in Markov, resulting in a larger optimization problem. We leave a proper development of this idea to future work.
A linear program is solvable in polynomial time and therefore improves dramatically in tractability over an NP-hard combinatorial problem. Nevertheless, solving a generic linear program is not always practical. Indeed, the recent surge in popularity of optimal transport is due partly to the introduction, by Cuturi and others, of specialized algorithms for solving the optimal transport program, which far outperform generic interior-point solvers [13, 37] . It would be useful to know whether and how these fast algorithms for optimal transport can be adapted to the linear programs in this paper.
In the new algorithms for optimal transport, the optimization objective is augmented by a term proportional to the negative entropy of the coupling, a technique known as entropic regularization. With this addition, the optimal transport problem improves from merely convex to strongly convex and, in particular, has a unique solution. Besides being useful for optimization, entropic regularization has a statistical interpretation as Gaussian deconvolution [40] .
For the Markov morphism feasibility problem of Section 3, adding entropic regularization yields an optimization problem whose solution is the Markov morphism of maximum entropy. For instance, in Figure 3 .1, the maximum entropy Markov morphism is the uniform mixture Φ = 1 2 φ 1 + 1 2 φ 2 of the two graph homomorphisms φ 1 and φ 2 . In Figure 3 .3, the unique Markov morphism has the maximum possible entropy, with all vertex and edge distributions being uniform. As these examples show, entropic regularization is antithetically opposed to the recovery of deterministic solutions. Entropic regularization should be investigated more systematically in this context, for algorithmic reasons and for its intrinsic interest.
Appendix A. Markov kernels
A Markov kernel is the probabilistic analogue of a function, assigning to every point in its domain not a single point in its codomain but a whole probability distribution over its codomain. Markov kernels are fundamental objects in probability theory and statistics [8, 24, 25, 28] . In this appendix, we recall the definition and basic properties of Markov kernels, as well as a few more obscure results from the literature. x ∈ X, C ∈ Σ Z .
The identity 1 X : X → X with respect to this composition law is the usual identity function regarded as a Markov kernel, 1 X : x → δ x .
A third perspective on Markov kernels is that they are linear operators on spaces of measures or probability measures (see, for instance, [8 With this definition, M is a Markov operator : writing Meas(X) for the space of all finite nonnegative measures on X, the Markov kernel M acts as linear map Meas(X) → Meas(Y ) that preserves the total mass, µM(Y ) = µ(X). In particular, M acts as a linear map Prob(X) → Prob(Y ) on spaces of probability measures.
Let µ be a measure on X and let M : X → Y be a Markov kernel. Besides applying M to µ, yielding the measure µM on Y , we can also take the product of µ and M, yielding a measure µ ⊗ M on X × Y defined on measurable rectangles by where A ∈ Σ X and B ∈ Σ Y . The product measure µ ⊗ M has marginal µ along X and marginal µM along Y . In the special case where M(x) equals a fixed measure ν for all x, we recover the usual product measure µ ⊗ ν.
It is often useful to know that the product operation is invertible. The inverse operation is called disintegration. What is less well known is that Markov kernels into product spaces can also be disintegrated. We use this result in Section 5 to prove a gluing lemma for Markov kernels. In the special case where X = { * } is a singleton, a Markov kernel Π : X → Y ×Z is a probability distribution on Y × Z and we recover a version of the previous theorem.
Under mild assumptions, optimal couplings of probability measures exist, according to a standard result in optimal transport [52 We invoke this theorem in Section 5 to show that the infimum defining the Wasserstein metric on Markov kernels is attained.

{'paper_id': '195766993', 'title': 'Hausdorff and Wasserstein metrics on graphs and other structured data', 's2_url': 'https://api.semanticscholar.org/CorpusID:195766993', 'source': 'S2ORC'}