Geometry of graph partitions via optimal transport

DOI10.1137/19M1295258zbMATH Open1452.65107arXiv1910.09618OpenAlexW3094265067MaRDI QIDQ5132020FDOQ5132020

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)

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.

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

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

zbMATH Keywords

convex optimizationoptimal transportnetwork flows

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

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

Uses Software

• Scikit
• CVXPY
• GitHub
• enumerator
• GerryChain

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)