Scalable Optimal Transport via Sparse Edge Recombination

In large-scale optimal transport (OT) between two equally sized, uniformly weighted discrete distributions, there are $N^2$ possible correspondences between $N$ source and $N$ target points, although an optimal assignment uses only $N$ of them. This motivates constructing a small candidate edge set that still contains a low-cost perfect matching. BSP-OT offers one such approach: it constructs sparse approximate assignments through randomized paired partitions. However, its random directions in high dimensions, refinement to singleton pairs, and sequential merging can miss or discard useful candidate edges. To address these limitations, we propose *SER-OT* (Sparse Edge Recombination for Optimal Transport), retaining BSP-OT's paired-partitioning framework. SER-OT recursively partitions the source and target point sets using shared data-dependent projection directions formed from pairs of target points, and solves an exact linear assignment problem within each leaf. Repeating this procedure over $k$ randomized partition trees produces multiple sparse candidate matchings, whose retained edges are recombined into a single candidate graph with at most $kN$ edges. This reduces the candidate space from $N^2$ possible correspondences to at most $kN$ edges, while allowing edges discovered by different partition trees to be jointly optimized in the final assignment. Experiments show that SER-OT achieves small relative cost gaps across large-scale, high-dimensional, and geometrically diverse benchmarks while maintaining practical runtime and memory usage.