Hausdorff and Wasserstein metrics on graphs and other structured data

DOI10.1093/IMAIAI/IAAA025MaRDI QIDQ5033274zbMATH OpenOpenAlexWikidataFDO

Authors Evan Patterson

Publication date 22 February 2022

Published in Information and Inference: A Journal of the IMA (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.00257

zbMATH Keywords

Markov kernelsnetworksoptimal transportstructured dataWasserstein metric

Mathematics Subject Classification ID

Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Small world graphs, complex networks (graph-theoretic aspects) (05C82) General considerations in statistical decision theory (62C05) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Linear programming (90C05)

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.

Recommendations

• Gromov-Wasserstein distances and the metric approach to object matching
• Geometry of graph partitions via optimal transport
• Vector-valued optimal mass transport
• Quadratically regularized optimal transport on graphs
• Computing the Monge-Kantorovich distance

Cited in

(4)

• Metrization of D_E[0,1] by Hausdorff distance between graphs
• The Gromov–Wasserstein distance between networks and stable network invariants
• Geometry of graph partitions via optimal transport
• Hypergraph co-optimal transport: metric and categorical properties

This page was built for publication: Hausdorff and Wasserstein metrics on graphs and other structured data

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5033274)