A Graph Theoretic Additive Approximation of Optimal Transport

Nathaniel Lahn, Deepika Mulchandani, Sharath Raghvendra

Optimal Transport (OT), often conceptualized as the "Earth Mover’s Distance," provides a mathematically rigorous framework for measuring the similarity between probability distributions, such as images or point clouds. It calculates the minimum cost required to "transport" mass from a supply distribution to a demand distribution.

While theoretically elegant, exact OT solvers are computationally prohibitive for modern, large-scale machine learning datasets. To scale up, researchers typically rely on approximations. The most popular method, the Sinkhorn algorithm, utilizes entropic regularization to accelerate computation. However, Sinkhorn suffers from a significant "precision problem": as the desired error margin ($\delta$) decreases, the algorithm becomes numerically unstable and drastically slower.

This paper introduces a deterministic, graph-theoretic algorithm to solve the OT problem with an additive error $\delta$. By adapting the classic Gabow-Tarjan scaling algorithm and providing a novel "diameter-sensitive" analysis, the authors achieve a highly competitive time complexity that is numerically stable, particularly when high precision (small $\delta$) is required.

A Return to Combinatorial Roots

Moving away from the "soft" optimization of Sinkhorn, the authors return to the "hard" combinatorial roots of graph theory. Their approach adapts the Gabow-Tarjan algorithm, originally designed for the assignment problem, to the continuous domain of optimal transport.

Key technical steps include:

  1. Integer Scaling: Continuous demands and supplies are transformed into integers by scaling them by a factor proportional to $1/\delta$.
  2. Single-Scale Primal-Dual Approach: Instead of complex multi-scale cost-scaling, the algorithm uses a single scale, maintaining "dual weights" for each node to ensure "1-feasibility."
  3. Two-Step Iterations: Each iteration consists of a Dijkstra-type "Hungarian Search" to adjust dual weights and find "zero-slack" edges (the currently cheapest routes), followed by a partial Depth-First Search (DFS) to find "augmenting paths" that actually move supply to demand.
  4. Diameter-Sensitive Analysis: The core theoretical contribution is a novel method to bound the total length of all augmenting paths. This yields a time complexity bound of $\mathcal{O}(n^2C/\delta + n(C/\delta)^2)$, notably avoiding the logarithmic factors present in many state-of-the-art approximation algorithms.
Comparison of time complexities for additive approximation algorithms.

Empirical Performance and Key Insights

The algorithm was evaluated using the MNIST Handwritten Digits dataset, treating pixel intensities of $28 \times 28$ images as supply/demand and defining the transport cost as the squared Euclidean distance between pixel coordinates.

By treating OT as a graph problem rather than a regularized optimization problem, the proposed method completely avoids the numerical instability (overflow/underflow) that plagues Sinkhorn at small regularization parameters.

Performance metrics (Wall Clock Time, Iterations, and Total AP Length) as a function of the error parameter delta.

Key Results: * High Precision Stability: While Sinkhorn is exceptionally fast for coarse approximations, its iteration count explodes as $\delta$ decreases. The proposed combinatorial algorithm remains stable and finishes significantly faster than Sinkhorn, Greenkhorn, or APDAGD for very small values of $\delta$ (e.g., $\delta = 0.0001$). * Empirical Efficiency: In practice, the total length of augmenting paths was much smaller than the theoretical worst-case bound. The time spent actively moving mass (augmentations) accounted for less than 2% of the total execution time. * Simplicity: Relying only on standard graph traversals (Dijkstra and DFS), the algorithm is straightforward to implement and reason about compared to complex accelerated gradient methods.

Limitations and Future Directions

The primary limitation of this approach is its sequential nature. Because the algorithm relies heavily on Dijkstra’s search, it is inherently sequential and harder to parallelize on GPUs compared to Sinkhorn, which consists mostly of highly parallelizable matrix-vector multiplications.

However, the authors suggest promising avenues for future work. For geometric costs (like Euclidean distance), the "Hungarian Search" step could potentially be accelerated using Approximate Nearest Neighbor (ANN) or Dynamic Weighted Nearest Neighbor data structures. Furthermore, exploring parallel versions of this combinatorial approach could allow it to compete with Sinkhorn on modern hardware accelerators, combining theoretical stability with practical scalability.

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 $\BigO(\frac{n^2 C}{\delta}+ \frac{nC^2}{\delta^2})$. Our algorithm is extremely simple and executes, for an arbitrarily small constant $\eps$, only $\lfloor \frac{2C}{(1-\eps)\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