A Novel Skip Orthogonal List for Dynamic Optimal Transport Problem

Xiaoyang Xu, Hu Ding

TL;DR

Recomputing Optimal Transport (OT) from scratch whenever a few data points move or change weights wastes massive computational effort ($\Omega(|V|^2)$ per update). This paper introduces the 2D Skip Orthogonal List, a dynamic data structure that maintains the simplex dual variables and reduced costs, slashing the per-iteration pivot time from $O(|V|^2)$ to an expected $O(|V|)$. For incremental changes requiring only a few pivots, this achieves speedups of up to $1000\times$ over static network simplex and $10\times$ over Sinkhorn.

What Problem Does This Paper Address?

Optimal Transport (OT) calculates the minimum cost to morph one discrete distribution into another and is widely used in domain adaptation, time-series analysis, and neuroimaging. In many realistic scenarios, datasets are not static:

  • Points slightly shift locations over time (e.g., continuous tracking, organ scans across months).
  • Sample weights change dynamically.
  • New points arrive or obsolete ones are deleted.

Standard OT algorithms (such as the Network Simplex or Sinkhorn algorithm) are inherently static. If even a single point moves or changes weight, these algorithms must scan the entire bipartite graph ($\Omega(|V|^2)$ operations). The authors tackle this by asking: Can we warm-start and dynamically repair the existing optimal transport plan in time proportional to the magnitude of the change rather than the size of the whole dataset?

Methods

The paper solves dynamic OT by combining the Network Simplex method with dynamic tree techniques and a novel multi-dimensional linked structure:

  1. Reduction to Simplex Pivoting:
  2. Moving a point breaks dual feasibility, handled via standard primal simplex pivoting.
  3. Adjusting point weights breaks primal feasibility, handled by sending flow along augmenting paths via dual simplex pivoting.
  4. Insertions and deletions are handled through a virtual zero-weight node pool.
  5. Euler Tour Technique: The basic feasible solution forms a spanning tree. The authors represent this tree using an Euler Tour sequence of edges ($|E_D| = O(|V|)$), reducing tree operations (cuts, links) to circular sequence operations.

  6. 2D Skip Orthogonal List: In conventional network simplex, each pivot step takes $O(|V|^2)$ brute-force time to find the minimum reduced cost $c_{uv}^\pi$ and update dual potentials. The authors introduce a 2D Skip Orthogonal List over $E_D \times E_D$:

  7. Orthogonal row and column circular pointers track elements across dimensions.

  8. Probabilistic skip list layers allow efficient "domination" of sub-rectangles.
  9. Lazy propagation enables block updates ($\pm c^\pi$ additions to submatrices) and range minimum queries.
  10. Tree cut and link updates run in expected $O(|V|)$ time, while querying the optimal variable to pivot into the basis takes expected $O(1)$ time.
       Tree Pivot (Cut/Link)
                 │
                 ▼
     Euler Tour 1D Circular Sets
                 │
                 ▼
 2D Cartesian Product (E_D × E_D)
                 │
                 ▼
  2D Skip Orthogonal List Updates
    [Expected O(|V|) per pivot]

Datasets

The authors evaluated their method against the static Network Simplex and Sinkhorn solvers from the Python Optimal Transport (POT) library using:

  • Synthetic Mixture of Gaussians: Two Gaussian distributions in $\mathbb{R}^{784}$ with sample sizes $|V|$ scaled up to $4 \times 10^4$.
  • MNIST: Partitioning handwritten digits into two label sets to compute transport distances between digit distributions.

Evaluated operations focused on Spatial Position Modification (adding Gaussian noise $\sigma^2 = 0.5$ to a point's coordinates) and Point Insertion (inserting an unseen point into the instance).

Key Insights and Ideas

  • Local perturbations require few pivots: When changes are small, the previous basis is almost optimal. It often takes only $s \ll |V|$ pivoting iterations to restore optimality.
  • The bottleneck was matrix maintenance, not the flow network: Link/Cut trees easily maintain flow in $O(\log |V|)$, but the simplex bottleneck has always been scanning the $|V| \times |V|$ matrix of adjusted costs ($C^\pi$).
  • 2D Domination via Skip Lists: While multi-dimensional search trees (like $k$-d trees) struggle with dynamic cyclic orderings, multi-layer 2D skip orthogonal lists naturally support circular sequences and lazy-tag block updates.

Key Results

  • Up to $1000\times$ faster than Static Network Simplex: On datasets scaled up to $|V| = 40{,}000$, updating the existing basis dynamically ran orders of magnitude faster than recomputing the exact solution.
  • Up to $10\times$ faster than the Sinkhorn Algorithm: Even compared against entropic regularization (Sinkhorn with $\lambda = 0.1$), the dynamic exact method was noticeably faster because Sinkhorn still requires several full matrix-scaling iterations upon cost alterations.
  • Scaling Behavior: While theoretical expectation is strictly $O(s|V|)$, experimental scaling showed a slight super-linear trend due to minor increases in required pivot iterations ($s$) and CPU cache misses at large $|V|$.

Limitations and Future Work

  • High Memory Footprint: Explicitly maintaining the 2D Skip Orthogonal List requires storing an $O(|V|^2)$ pointer structure, which limits its application to very large datasets.
  • Poor Cache Locality: As a pointer-heavy linked data structure, it suffers from reduced hardware cache hit rates compared to dense array-based vectorization.
  • Future Directions: Developing cache-aware, contiguous-memory data structures with comparable theoretical bounds to make dynamic simplex methods more hardware-friendly.

Summary updated

Abstract

Optimal transport is a fundamental topic that has attracted a great amount of attention from the optimization community in the past decades. In this paper, we consider an interesting discrete dynamic optimal transport problem: can we efficiently update the optimal transport plan when the weights or the locations of the data points change? This problem is naturally motivated by several applications in machine learning. For example, we often need to compute the optimal transport cost between two different data sets; if some changes happen to a few data points, should we re-compute the high complexity cost function or update the cost by some efficient dynamic data structure? We are aware that several dynamic maximum flow algorithms have been proposed before, however, the research on dynamic minimum cost flow problem is still quite limited, to the best of our knowledge. We propose a novel 2D Skip Orthogonal List together with some dynamic tree techniques. Although our algorithm is based on the conventional simplex method, it can efficiently find the variable to pivot within expected O(1) time, and complete each pivoting operation within expected O(|V|) time where V is the set of all supply and demand nodes. Since dynamic modifications typically do not introduce significant changes, our algorithm requires only a few simplex iterations in practice. So our algorithm is more efficient than re-computing the optimal transport cost that needs at least one traversal over all |E|=O(|V|^2) variables, where |E| denotes the number of edges in the network. Our experiments demonstrate that our algorithm significantly outperforms existing algorithms in the dynamic scenarios.
BibTeX
@inproceedings{xu2024novel,
  author = {Xiaoyang Xu and Hu Ding},
  title = {{A Novel Skip Orthogonal List for Dynamic Optimal Transport Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=v0JMuFfNe5},
}
Figure