# Quadratically-Regularized Optimal Transport on Graphs

arXiv: https://arxiv.org/abs/1704.08200 · HTML: https://mlsanity.com/paper/1704.08200/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Apr 2017.

## Built on by (most cited first, 19 of 19)

- [Neural Optimal Transport with General Cost Functionals](https://mlsanity.com/paper/2205.15403/) (2022)
- [On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error](https://mlsanity.com/paper/2202.03618/) (2022)
- [Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution](https://mlsanity.com/paper/2103.06263/) (2021)
- [Convergence Rates for Regularized Optimal Transport via Quantization](https://mlsanity.com/paper/2208.14391/) (2022)
- [Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More](https://mlsanity.com/paper/2107.06876/) (2021)
- [Submodular Framework for Structured-Sparse Optimal Transport](https://mlsanity.com/paper/2406.04914/) (2024)
- [Discrete Optimal Transport with Independent Marginals is #P-Hard](https://mlsanity.com/paper/2203.01161/) (2022)
- [Resistance Distance and Linearized Optimal Transport on Graphs](https://mlsanity.com/paper/2404.15261/) (2024)
- [Manifold Learning with Sparse Regularised Optimal Transport](https://mlsanity.com/paper/2307.09816/) (2023)
- [Adapting Language Models via Token Translation](https://mlsanity.com/paper/2411.00593/) (2024)
- [A Quasi-Wasserstein Loss for Learning Graph Neural Networks](https://mlsanity.com/paper/2310.11762/) (2023)
- [Statistical Inference for Optimal Transport Maps: Recent Advances and Perspectives](https://mlsanity.com/paper/2506.19025/) (2025)
- [Generalized Schr"odinger Bridge on Graphs](https://mlsanity.com/paper/2602.04675/) (2026)
- [Graph Fourier MMD for Signals on Graphs](https://mlsanity.com/paper/2306.02508/) (2023)
- [Quadratically Regularized Optimal Transport: Localization Bounds and Affine Case Analysis](https://mlsanity.com/paper/2605.24644/) (2026)
- [Your GFlowNet Secretly Learns an Optimal Transport Plan](https://mlsanity.com/paper/2606.06272/) (2026)
- [Generative Modeling on Metric Graphs via Neural Optimal Transport](https://mlsanity.com/paper/2606.16273/) (2026)
- [Accelerated Algorithm for Sparse Regularized Partial Optimal Transport](https://mlsanity.com/paper/2609.40075/) (2026)
- [Discrete Action Matching: Learning Stochastic Dynamics from Samples via State Graphs](https://mlsanity.com/paper/2610.05071/) (2026)

## Abstract (arXiv)

Optimal transportation provides a means of lifting distances between points on a geometric domain to distances between signals over the domain, expressed as probability distributions. On a graph, transportation problems can be used to express challenging tasks involving matching supply to demand with minimal shipment expense; in discrete language, these become minimum-cost network flow problems. Regularization typically is needed to ensure uniqueness for the linear ground distance case and to improve optimization convergence; state-of-the-art techniques employ entropic regularization on the transportation matrix. In this paper, we explore a quadratic alternative to entropic regularization for transport over a graph. We theoretically analyze the behavior of quadratically-regularized graph transport, characterizing how regularization affects the structure of flows in the regime of small but nonzero regularization. We further exploit elegant second-order structure in the dual of this problem to derive an easily-implemented Newton-type optimization algorithm.