A Graph Theoretic Additive Approximation of Optimal Transport

Nathaniel Lahn, Deepika Mulchandani, Sharath Raghvendra

Abstract

Transportation cost is an attractive similarity measure between probability distributions due to its many useful theoretical properties. However, solving optimal transport exactly can be prohibitively expensive. Therefore, there has been significant effort towards the design of scalable approximation algorithms. Previous combinatorial results have focused primarily on the design of near-linear time multiplicative approximation algorithms. There has also been an effort to design approximate solutions with additive errors $\delta$ within a time bound that is linear in the size of the cost matrix and polynomial in $C/\delta$. We present an adaptation of the classical graph algorithm of Gabow and Tarjan and provide a novel analysis of this algorithm that bounds its execution time by $O(\frac{n^2 C}{\delta}+ \frac{nC^2}{\delta^2})$. Our algorithm is extremely simple and executes only $\lfloor \frac{2C}{(1-\varepsilon)\delta}\rfloor + 1$ iterations. We also provide empirical results that suggest our algorithm is competitive with respect to a sequential implementation of the Sinkhorn algorithm in execution time, particularly for very small values of $\delta$ where Sinkhorn slows down due to numerical instability.

Introduction

Optimal Transport (OT), often quantified via the Earth Mover's Distance or Wasserstein metric, provides a robust framework for comparing probability distributions. However, its exact computation is computationally intensive, scaling cubically with the number of points ($O(n^3)$). To address this, researchers have turned to approximation algorithms. While entropic regularization methods like the Sinkhorn algorithm are widely used, they face significant numerical instability when high precision (small additive error $\delta$) is required. This paper introduces a deterministic, graph-theoretic approach that maintains stability and efficiency even at high precision.

Combinatorial Algorithm for Optimal Transport

The proposed method moves away from continuous matrix-scaling techniques, instead adapting the classical Gabow-Tarjan graph algorithm for the assignment problem. The algorithm operates on a scaled version of the transportation problem and proceeds in phases. Each phase consists of two primary steps:

  1. Hungarian Search: A Dijkstra-type search updates dual weights and identifies a subgraph of "zero slack" (admissible) edges.
  2. Partial DFS: A Depth-First Search finds augmenting paths along these admissible edges to route supply to demand.

A key innovation is the use of a single-scale adaptation, which simplifies the application to unbalanced transportation problems. Furthermore, the algorithm is purely combinatorial, ensuring numerical stability regardless of the error parameter $\delta$.

Theoretical Contributions

The primary theoretical contribution is a novel diameter-sensitive analysis of the algorithm. By bounding the total length of all augmenting paths, the authors establish a deterministic time complexity of $O(n^2C/\delta + n(C/\delta)^2)$. As shown in the table below, this result improves upon or matches the best known bounds for additive $\delta$-approximation while avoiding logarithmic factors.

Comparison of time complexities for additive $\delta$-approximation of Optimal Transport.

Empirical Evaluation

The algorithm was evaluated on the MNIST dataset, treating images as discrete distributions. Experiments demonstrate that the combinatorial approach is highly competitive with Sinkhorn-based methods. Notably, as $\delta$ decreases, the algorithm remains efficient, whereas Sinkhorn's performance degrades due to numerical issues.

Performance metrics (Wall Clock Time, Iterations, and Total Augmenting Path Length) as a function of the error tolerance $\delta$.

The empirical results also highlight a gap between theory and practice: while the theoretical bound for augmenting path length is $O(n(C/\delta)^2)$, the actual time spent on augmentations in practice is less than 2% of total execution time, as paths often route multiple units of flow simultaneously.

Conclusion

The proposed graph-theoretic algorithm offers a robust, deterministic, and numerically stable alternative for computing additive approximations of Optimal Transport. While its sequential nature (due to Dijkstra's search) presents a challenge for GPU parallelization, its efficiency at high precision makes it a valuable tool for applications requiring accurate transport plans. Future work includes exploring parallel combinatorial variants and leveraging geometric data structures for further speedups.

Summary updated

Abstract

Transportation cost is an attractive similarity measure between probability distributions due to its many useful theoretical properties. However, solving optimal transport exactly can be prohibitively expensive. Therefore, there has been significant effort towards the design of scalable approximation algorithms. Previous combinatorial results [Sharathkumar, Agarwal STOC '12, Agarwal, Sharathkumar STOC '14] have focused primarily on the design of near-linear time multiplicative approximation algorithms. There has also been an effort to design approximate solutions with additive errors [Cuturi NIPS '13, Altschuler \etal\ NIPS '17, Dvurechensky \etal\, ICML '18, Quanrud, SOSA '19] within a time bound that is linear in the size of the cost matrix and polynomial in $C/\delta$; here $C$ is the largest value in the cost matrix and $\delta$ is the additive error. We present an adaptation of the classical graph algorithm of Gabow and Tarjan and provide a novel analysis of this algorithm that bounds its execution time by $O(\frac{n^2 C}{\delta}+ \frac{nC^2}{\delta^2})$. Our algorithm is extremely simple and executes, for an arbitrarily small constant $\varepsilon$, only $\lfloor \frac{2C}{(1-\varepsilon)\delta}\rfloor + 1$ iterations, where each iteration consists only of a Dijkstra-type search followed by a depth-first search. We also provide empirical results that suggest our algorithm is competitive with respect to a sequential implementation of the Sinkhorn algorithm in execution time. Moreover, our algorithm quickly computes a solution for very small values of $\delta$ whereas Sinkhorn algorithm slows down due to numerical instability.
BibTeX
@inproceedings{lahn2019graph,
  author = {Nathaniel Lahn and Deepika Mulchandani and Sharath Raghvendra},
  title = {{A Graph Theoretic Additive Approximation of Optimal Transport}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=LkBgj8r3S-},
}
Figure