pith. sign in

arxiv: 1907.00257 · v2 · pith:FLSVUUDDnew · submitted 2019-06-29 · 🧮 math.OC · math.MG

Hausdorff and Wasserstein metrics on graphs and other structured data

Evan Patterson This is my paper

Pith reviewed 2026-05-25 12:36 UTC · model grok-4.3

classification 🧮 math.OC math.MG
keywords optimal transportWasserstein metricHausdorff metricC-setsgraphsstructured dataconvex relaxationlinear programming
0
0 comments X

The pith

Wasserstein metrics on C-sets are convex relaxations of Hausdorff metrics and reduce to linear programs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper extends optimal transport from plain sets to graphs and other structured data by modeling them as C-sets for finitely presented categories. It defines Hausdorff-style metrics that enforce strict structure-preserving maps and Wasserstein-style metrics that allow probabilistic transport plans instead. These Wasserstein metrics are shown to be convex relaxations of the Hausdorff ones, and like the classical case they equal the optimum of a linear program. A sympathetic reader would care because the construction turns combinatorial matching of structures into a tractable optimization task that applies uniformly to directed graphs, undirected graphs, labeled data, and similar objects.

Core claim

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 structure-preserving 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 efic

What carries the argument

The Wasserstein metric on C-sets, which assigns to a pair of C-sets the optimal value of a linear program whose feasible region encodes structure-preserving transport plans.

If this is right

  • Graphs and other C-set structures can be compared using efficiently solvable linear programs.
  • Optimal transport supplies probabilistic rather than deterministic solutions to matching problems on structured data.
  • The same construction works for directed graphs, undirected graphs, labeled graphs, and unlabeled graphs.
  • Hausdorff-style distances on C-sets possess convex relaxations that remain computable.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The method could be used to define similarity measures for database schemas or chemical reaction networks modeled as C-sets.
  • Software implementations could leverage existing linear programming libraries to compute distances between large graphs.
  • The relaxation might be combined with other convex optimization techniques for tasks such as structure alignment in machine learning.

Load-bearing premise

Structures that can be realized as C-sets for a finitely presented category admit a well-defined structure-preserving optimal transport that relaxes the usual notion of homomorphism.

What would settle it

A concrete pair of C-sets for which the linear program either fails to produce a value that relaxes the Hausdorff distance or violates the metric axioms.

Figures

Figures reproduced from arXiv: 1907.00257 by Evan Patterson.

Figure 1.1
Figure 1.1. Figure 1.1: 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 dou￾bly 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 st… view at source ↗
Figure 2.1
Figure 2.1. Figure 2.1: A graph [PITH_FULL_IMAGE:figures/full_fig_p005_2_1.png] view at source ↗
Figure 2.3
Figure 2.3. Figure 2.3: A reflexive graph [PITH_FULL_IMAGE:figures/full_fig_p006_2_3.png] view at source ↗
Figure 2.5
Figure 2.5. Figure 2.5: A two-dimensional semi-simplicial set 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 s… view at source ↗
Figure 3.1
Figure 3.1. Figure 3.1: Graphs whose Markov morphisms are mixtures of graph homomorphisms X Y [PITH_FULL_IMAGE:figures/full_fig_p012_3_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: looks superficially similar, with the graph [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figure 3.4
Figure 3.4. Figure 3.4: The terminal graph, for both homomorphisms and Markov morphisms 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. Proposition 3.9 … view at source ↗
Figure 4.1
Figure 4.1. Figure 4.1: An approximate graph homomorphism between two cycles 5. 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. De… view at source ↗
Figure 5.1
Figure 5.1. Figure 5.1: Lifting a metric from points to functions, distributions, and Markov kernels W → Z are Markov kernels, and ΠXY ∈ Coup(MX , MY ) and ΠY Z ∈ Coup(MY , MZ) are couplings thereof. Then there exists a Markov kernel ΠXY Z : W → X × Y × Z with marginals ΠXY along X × Y and ΠY Z along Y × Z. Proof. By the disintegration theorem for Markov kernels (Theorem A.5), there exist Markov kernels ΠX | Y : W ×Y → X and ΠZ… view at source ↗
read the original 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 structure-preserving 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper extends optimal transport concepts to structured data by defining Hausdorff-style and Wasserstein-style metrics on C-sets for finitely presented categories C (encompassing graphs and similar structures). It constructs these metrics and claims that the Wasserstein versions serve as convex relaxations of the Hausdorff ones, with the Wasserstein metric computable as the optimum of a linear program.

Significance. If the constructions and relaxation property are rigorously established, the work offers a principled way to apply optimal transport to matching problems on graphs and other relational structures while preserving the underlying categorical structure, with the added benefit of efficient LP-based computation.

major comments (1)
  1. [LP formulation and relaxation proof] The central relaxation claim (Wasserstein metric as convex relaxation of Hausdorff metric, with zero distance implying a structure-preserving map) requires that the LP constraints encode all relations from the finite presentation of C. The formulation must be shown to enforce functoriality or naturality conditions derived from the morphisms and relations in C; otherwise the relaxation property fails for categories with non-trivial relations.
minor comments (1)
  1. Clarify in the introduction or abstract how the finite presentation of C is used to derive the explicit LP constraints.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying this key point about the LP formulation. We address the major comment below.

read point-by-point responses

  1. Referee: [LP formulation and relaxation proof] The central relaxation claim (Wasserstein metric as convex relaxation of Hausdorff metric, with zero distance implying a structure-preserving map) requires that the LP constraints encode all relations from the finite presentation of C. The formulation must be shown to enforce functoriality or naturality conditions derived from the morphisms and relations in C; otherwise the relaxation property fails for categories with non-trivial relations.

    Authors: We agree that the LP must encode the relations of the finite presentation to guarantee the relaxation property. Our construction defines the Wasserstein metric via an LP whose variables are maps on the generating objects of the C-set and whose constraints are generated exactly by the morphisms and relations in the presentation of C; feasible solutions are therefore required to satisfy the corresponding naturality conditions. The proof that the Wasserstein metric relaxes the Hausdorff metric (and that zero distance yields a structure-preserving map) is built on this encoding. To make the dependence on the presentation fully explicit, we will insert a short lemma in the revised manuscript showing that every relation in the presentation induces a corresponding linear constraint and that the resulting feasible set is precisely the convex hull of the set of functors. This addition will not change the stated theorems but will strengthen their justification. revision: yes

Circularity Check

0 steps flagged

No circularity: metrics constructed from standard OT and C-set homomorphisms without self-referential reduction.

full rationale

The abstract and description present a direct construction: Wasserstein metrics on C-sets are defined via linear programs that relax the classical notion of homomorphism, with Hausdorff-style metrics as the non-relaxed counterpart. No equations, parameters, or uniqueness claims are shown to reduce to fitted inputs or prior self-citations by construction. The derivation relies on external category theory and optimal transport, remaining self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on standard results from optimal transport theory and category theory. No free parameters, new axioms beyond standard math, or invented entities are apparent from the abstract.

axioms (1)
  • standard math Standard theorems of optimal transport and category theory for C-sets
    The constructions build directly on existing OT and category-theoretic frameworks.

pith-pipeline@v0.9.0 · 5654 in / 1203 out tokens · 45602 ms · 2026-05-25T12:36:38.679360+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

56 extracted references · 56 canonical work pages · 9 internal anchors

  1. [1]

    O n convex relax- ation of graph isomorphism

    Yonathan Aflalo, Alexander Bronstein, and Ron Kimmel. “O n convex relax- ation of graph isomorphism”. Proceedings of the National Academy of Sciences 112.10 (2015), pp. 2942–2947

    work page 2015

  2. [2]

    Structured Optimal Transport

    David Alvarez-Melis, Tommi Jaakkola, and Stefanie Jege lka. “Structured opti- mal transport”. International Conference on Artificial Intelligence and St atis- tics. 2018, pp. 1771–1780. arXiv: 1712.06199

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  3. [3]

    Optimal measures and Markov transit ion kernels

    Roman V. Belavkin. “Optimal measures and Markov transit ion kernels”. Jour- nal of Global Optimization 55.2 (2013), pp. 387–416

    work page 2013

  4. [4]

    Shortest -path kernels on graphs

    Karsten M. Borgwardt and Hans-Peter Kriegel. “Shortest -path kernels on graphs”. Fifth IEEE International Conference on Data Mining (ICDM’0 5). IEEE. 2005, 8–pp

    work page 2005

  5. [5]

    Bridson and André Haefliger

    Martin R. Bridson and André Haefliger. Metric spaces of non-positive curvature. Springer, 1999. 42 REFERENCES

    work page 1999

  6. [6]

    On a relation between graph edit distance a nd maximum com- mon subgraph

    Horst Bunke. “On a relation between graph edit distance a nd maximum com- mon subgraph”. Pattern Recognition Letters 18.8 (1997), pp. 689–694

    work page 1997

  7. [7]

    A course in metric geometry

    Dmitri Burago, Yuri Burago, and Sergei Ivanov. A course in metric geometry . American Mathematical Society, 2001

    work page 2001

  8. [8]

    N. N. Čencov. Statistical decision rules and optimal inference . Translations of Mathematical Monographs 53. American Mathematical Societ y, 1982

    work page 1982

  9. [9]

    The ∞ -Wasserstein distance: Local solutions and existence of optimal transpo rt maps

    Thierry Champion, Luigi De Pascale, and Petri Juutinen. “The ∞ -Wasserstein distance: Local solutions and existence of optimal transpo rt maps”. SIAM Jour- nal on Mathematical Analysis 40.1 (2008), pp. 1–20

    work page 2008

  10. [10]

    Ba lanced graph match- ing

    Timothee Cour, Praveen Srinivasan, and Jianbo Shi. “Ba lanced graph match- ing”. Advances in Neural Information Processing Systems . 2007, pp. 313–320

    work page 2007

  11. [11]

    Optimal Transport for Domain Adaptation

    Nicolas Courty, Rémi Flamary, Devis Tuia, and Alain Rak otomamonjy. “Opti- mal transport for domain adaptation”. IEEE Transactions on Pattern Analysis and Machine Intelligence 39.9 (2017), pp. 1853–1865. arXiv: 1507.00504

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  12. [12]

    Roy L. Crole. Categories for types . Cambridge University Press, 1993

    work page 1993

  13. [13]

    Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances

    Marco Cuturi. “Sinkhorn distances: Lightspeed comput ation of optimal trans- port”. Advances in Neural Information Processing Systems. 2013, pp. 2292–2300. arXiv: 1306.0895

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  14. [14]

    Strong stationar y times via a new form of duality

    Persi Diaconis and James Allen Fill. “Strong stationar y times via a new form of duality”. The Annals of Probability 18.4 (1990), pp. 1483–1522

    work page 1990

  15. [15]

    Markov chains

    Randal Douc, Eric Moulines, Pierre Priouret, and Phili ppe Soulier. Markov chains. Springer, 2018

    work page 2018

  16. [16]

    Fifty years of graph matching, network alignment and network comparison

    Frank Emmert-Streib, Matthias Dehmer, and Yongtang Sh i. “Fifty years of graph matching, network alignment and network comparison” . Information Sci- ences 346 (2016), pp. 180–197

    work page 2016

  17. [17]

    Survey article: An elementary illustr ated introduction to sim- plicial sets

    Greg Friedman. “Survey article: An elementary illustr ated introduction to sim- plicial sets”. The Rocky Mountain Journal of Mathematics (2012), pp. 353–423. arXiv: 0809.4221

    work page arXiv 2012

  18. [18]

    Directed hypergraphs and applications

    Giorgio Gallo, Giustino Longo, Stefano Pallottino, an d Sang Nguyen. “Directed hypergraphs and applications”. Discrete Applied Mathematics 42.2-3 (1993), pp. 177–201

    work page 1993

  19. [19]

    Finite sets and symmetric simplicial s ets

    Marco Grandis. “Finite sets and symmetric simplicial s ets”. Theory and Appli- cations of Categories 8.8 (2001), pp. 244–252

    work page 2001

  20. [20]

    Metric Structures for Riemannian and Non-Riemannian Space s

    Mikhail Gromov. Metric Structures for Riemannian and Non-Riemannian Space s. Birkhäuser Boston, 1999

    work page 1999

  21. [21]

    Convolution kernels on discrete structures

    David Haussler. Convolution kernels on discrete structures . Tech. rep. UCSC- CRL-99-10. University of California at Santa Cruz, 1999

    work page 1999

  22. [22]

    Graphs and homomorphisms

    Pavol Hell and Jaroslav Nešetřil. Graphs and homomorphisms . Oxford Univer- sity Press, 2004. REFERENCES 43

    work page 2004

  23. [23]

    Six theorems about injective metric sp aces

    John R. Isbell. “Six theorems about injective metric sp aces”. Commentarii Mathematici Helvetici 39.1 (1964), pp. 65–76

    work page 1964

  24. [24]

    Foundations of modern probability

    Olav Kallenberg. Foundations of modern probability . 2nd ed. Springer-Verlag New York, 2002

    work page 2002

  25. [25]

    Random measures, theory and applications

    Olav Kallenberg. Random measures, theory and applications . Springer, 2017

    work page 2017

  26. [26]

    Ma rginalized kernels be- tween labeled graphs

    Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi. “Ma rginalized kernels be- tween labeled graphs”. Proceedings of the 20th International Conference on Machine Learning. 2003, pp. 321–328

    work page 2003

  27. [27]

    Basic concepts of enriched category theory

    Max Kelly. Basic concepts of enriched category theory . Reprinted in Theory and Applications of Categories . Cambridge University Press, 1982

    work page 1982

  28. [28]

    Probability theory: A comprehensive course

    Achim Klenke. Probability theory: A comprehensive course . 2nd ed. Springer, 2013

    work page 2013

  29. [29]

    Joachim Lambek and Philip J. Scott. Introduction to higher-order categorical logic. Cambridge University Press, 1986

    work page 1986

  30. [30]

    Functorial semantics of algebrai c theories

    F. William Lawvere. “Functorial semantics of algebrai c theories”. PhD thesis. Columbia University, 1963

    work page 1963

  31. [31]

    Metric spaces, generalized logic , and closed categories

    F. William Lawvere. “Metric spaces, generalized logic , and closed categories”. Rendiconti del seminario matématico e fisico di Milano 43.1 (1973), pp. 135– 166

    work page 1973

  32. [32]

    Qualitative distinctions betwee n some toposes of general- ized graphs

    F. William Lawvere. “Qualitative distinctions betwee n some toposes of general- ized graphs”. Categories in Computer Science and Logic . Vol. 92. Contemporary Mathematics. American Mathematical Society, 1989, pp. 261 –299

    work page 1989

  33. [33]

    William Lawvere and Stephen H

    F. William Lawvere and Stephen H. Schanuel. Conceptual mathematics: A first introduction to categories . 2nd ed. Cambridge University Press, 2009

    work page 2009

  34. [34]

    Sheaves in geometry and logic: A first introduction to topos theory

    Saunders Mac Lane and Ieke Moerdijk. Sheaves in geometry and logic: A first introduction to topos theory . Springer, 1992

    work page 1992

  35. [35]

    Gromov–Wasserstein distances and th e metric approach to object matching

    Facundo Mémoli. “Gromov–Wasserstein distances and th e metric approach to object matching”. Foundations of Computational Mathematics 11.4 (2011), pp. 417–487

    work page 2011

  36. [36]

    Match- ing node embeddings for graph similarity

    Giannis Nikolentzos, Polykarpos Meladianos, and Mich alis Vazirgiannis. “Match- ing node embeddings for graph similarity”. Thirty-First AAAI Conference on Artificial Intelligence . 2017

    work page 2017

  37. [37]

    Computational optima l transport

    Gabriel Peyré and Marco Cuturi. “Computational optima l transport”. Foun- dations and Trends in Machine Learning 11.5-6 (2019), pp. 355–607. arXiv: 1803.00567

    work page arXiv 2019

  38. [38]

    Reyes, and Houman Zolfa ghari

    Marie La Palme Reyes, Gonzalo E. Reyes, and Houman Zolfa ghari. Generic figures and their glueings: A constructive approach to funct or categories . Poli- metrica, 2004. 44 REFERENCES

    work page 2004

  39. [39]

    Exact an d inexact graph matching: Methodology and applications

    Kaspar Riesen, Xiaoyi Jiang, and Horst Bunke. “Exact an d inexact graph matching: Methodology and applications”. Managing and Mining Graph Data . Springer, 2010, pp. 217–247

    work page 2010

  40. [40]

    Entropic optimal transport is maximum-likelihood deconvolution

    Philippe Rigollet and Jonathan Weed. “Entropic optima l transport is maximum- likelihood deconvolution”. Comptes Rendus Mathématique 356.11-12 (2018), pp. 1228–1235. arXiv: 1809.05572

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  41. [41]

    Optimal transport for applied mathematicians: Calculus of variations, PDEs and modeling

    Filippo Santambrogio. Optimal transport for applied mathematicians: Calculus of variations, PDEs and modeling . Birkäuser, 2015

    work page 2015

  42. [42]

    Probab ilistic subgraph matching based on convex relaxation

    Christian Schellewald and Christoph Schnörr. “Probab ilistic subgraph matching based on convex relaxation”. International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition . 2005, pp. 171–186

    work page 2005

  43. [43]

    Efficient graphlet kernels for large gra ph comparison

    Nino Shervashidze, S.V.N. Vishwanathan, Tobias Petri , Kurt Mehlhorn, and Karsten Borgwardt. “Efficient graphlet kernels for large gra ph comparison”. Ar- tificial Intelligence and Statistics . 2009, pp. 488–495

    work page 2009

  44. [44]

    Metric measure geometry

    Takashi Shioya. Metric measure geometry: Gromov’s theory of convergence an d concentration of metrics and measures . European Mathematical Society, 2016. arXiv: 1410.0428

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  45. [45]

    Convexity: An analytic viewpoint

    Barry Simon. Convexity: An analytic viewpoint . Cambridge University Press, 2011

    work page 2011

  46. [46]

    Higher-dimensional models of networks

    David I. Spivak. “Higher-dimensional models of networ ks” (2009). arXiv: 0909.4314

    work page internal anchor Pith review Pith/arXiv arXiv 2009

  47. [47]

    David I. Spivak. Category Theory for the Sciences . MIT Press, 2014. arXiv: 1302.6946

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  48. [48]

    On the geometry of metric measure spaces I

    Karl-Theodor Sturm. “On the geometry of metric measure spaces I”. Acta Math- ematica 196.1 (2006), pp. 65–131

    work page 2006

  49. [49]

    Optimal Transport for structured data with application on graphs

    Titouan Vayer, Laetitia Chapel, Rémi Flamary, Romain T avenard, and Nicolas Courty. “Optimal transport for structured data with applic ation on graphs” (2018). arXiv: 1805.09114

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  50. [50]

    Long history of the Monge-Kantorovich t ransportation prob- lem

    A.M. Vershik. “Long history of the Monge-Kantorovich t ransportation prob- lem”. The Mathematical Intelligencer 35.4 (2013), pp. 1–9

    work page 2013

  51. [51]

    Topics in Optimal Transportation

    Cédric Villani. Topics in Optimal Transportation . American Mathematical So- ciety, 2003

    work page 2003

  52. [52]

    Optimal transport: Old and new

    Cédric Villani. Optimal transport: Old and new . Springer, 2008

    work page 2008

  53. [53]

    Graph Kernels

    S.V.N. Vishwanathan, Nicol N. Schraudolph, Risi Kondo r, and Karsten M. Borgwardt. “Graph kernels”. Journal of Machine Learning Research 11.Apr (2010), pp. 1201–1242. arXiv: 0807.0093

    work page internal anchor Pith review Pith/arXiv arXiv 2010

  54. [54]

    Semigroups on spaces of measures

    Daniël Worm. “Semigroups on spaces of measures”. PhD th esis. Leiden Univer- sity, 2010

    work page 2010

  55. [55]

    Intertwinings of Bessel processes

    Marc Yor. Intertwinings of Bessel processes . Tech. rep. 174. University of Cali- fornia, Berkeley, Oct. 1988. REFERENCES 45

    work page 1988

  56. [56]

    Existence and application of optimal Ma rkovian coupling with respect to non-negative lower semi-continuous functions

    Shaoyi Zhang. “Existence and application of optimal Ma rkovian coupling with respect to non-negative lower semi-continuous functions” . Acta Mathematica Sinica 16.2 (2000), pp. 261–270

    work page 2000