Geometry of graph partitions via optimal transport

DOI10.1137/19M1295258MaRDI QIDQ5132020zbMATH OpenOpenAlexFDO

Authors Tara Abrishami, Nestor Guillen, Parker Rule, Zachary Schutzman, Justin Solomon, Thomas Weighill, Si Wu

Publication date 9 November 2020

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

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

zbMATH Keywords

convex optimizationnetwork flowsoptimal transport

Mathematics Subject Classification ID

Flows in graphs (05C21) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Optimal transportation (49Q22) Numerical optimization and variational techniques (65K10) Programming involving graphs or networks (90C35)

Abstract: We define a distance metric between partitions of a graph using machinery from optimal transport. Our metric is built from a linear assignment problem that matches partition components, with assignment cost proportional to transport distance over graph edges. We show that our distance can be computed using a single linear program without precomputing pairwise assignment costs and derive several theoretical properties of the metric. Finally, we provide experiments demonstrating these properties empirically, specifically focusing on its value for new problems in ensemble-based analysis of political districting plans.

Recommendations

• Hausdorff and Wasserstein metrics on graphs and other structured data
• Ground metric learning on graphs
• Optimal mass transport on metric graphs
• Quadratically regularized optimal transport on graphs
• A Generalized Distance in Graphs and Centered Partitions

Cites work

• A Continuous Model of Transportation
• A new transportation distance between non-negative measures, with applications to gradients flows with Dirichlet boundary conditions
• Applied multidimensional scaling
• Assessing significance in a Markov chain without mixing
• Comparing clusterings -- an information based distance
• Computational optimal transport. With applications to data sciences
• Coupling Lévy measures and comparison principles for viscosity solutions
• CVXPY: a Python-embedded modeling language for convex optimization
• Eulerian models and algorithms for unbalanced optimal transport
• Free boundaries in optimal transport and Monge-Ampère obstacle problems
• scientific article; zbMATH DE number 6378089 (Why is no real title available?)
• scientific article; zbMATH DE number 2062987 (Why is no real title available?)
• scientific article; zbMATH DE number 1909499 (Why is no real title available?)
• scientific article; zbMATH DE number 3099866 (Why is no real title available?)
• Network flows. Theory, algorithms, and applications.
• Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
• Quadratically regularized optimal transport on graphs
• Scaling algorithms for unbalanced optimal transport problems
• Scikit-learn: machine learning in Python
• The complexity of computing metric distances between partitions
• Unbalanced optimal transport: dynamic and Kantorovich formulations

Cited in

(7)

• Hausdorff and Wasserstein metrics on graphs and other structured data
• Three applications of entropy to gerrymandering
• Geometric Averages of Partitioned Datasets
• Reconfiguration of connected graph partitions via recombination
• Reconfiguration of connected graph partitions via recombination
• The (homological) persistence of gerrymandering
• Sequences of well-distributed vertices on graphs and spectral bounds on optimal transport

Describes a project that uses

Uses Software

• Scikit
• CVXPY
• GerryChain
• enumerator
• GitHub

This page was built for publication: Geometry of graph partitions via optimal transport

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