acceptodds
Under review as a conference paper at ICLR 2027

Scalable Optimal Transport via Sparse Edge Recombination

Abstract

In large-scale optimal transport (OT) between two equally sized, uniformly weighted discrete distributions, there are possible correspondences between source and target points, although an optimal assignment uses only 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 randomized partition trees produces multiple sparse candidate matchings, whose retained edges are recombined into a single candidate graph with at most edges. This reduces the candidate space from possible correspondences to at most 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.

Primary area:
optimization
Keywords:
Optimal Transport

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_BAToOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper introduces improvements to a recently proposed algorithm called BSP-OT to estimate the bijective optimal transport (monge) map between equally sized uniformly weighted point clouds. More specifically, starting with the original datasets as source and target partitions, BSP-OT recursively keeps projecting both source and target data partitions to random 1D spaces and use projections to subpartition both source and target such that corresponding source and target subpartitions are of same size, until all partitions are singleton. After that, the algorithm merges, singleton matches between source and target datapoints to create one possible bijective map between point clouds. Complete BSP-OT creates a list of multiple possible bijective maps using above mentioned procedure and then merges bijective maps in the list in a sequential fashion such that during each iteration of merging process only two solutions are merged to obtain a new bijection, which is then merged with another solution from the list to obtain another bijection and so on.

Proposed improvements in the papre are as follows: (1) Instead of random projections, paper proposes to use a pair of target data points to create a projection direction. (2) Run the BSP-OT recursion until Linear Assignment Problem (LAP) is sufficiently cheaper and then solve LAP directly, after that combine LAP solutions to obtain a bijection. (3) Solve LAP on union of larger list of possible bijection edges.

Proposed improvements are also test and compared with on origional BSP-OT and other methods on multiple assignment benchmarks.

Critical strengths
  1. Paper is generally well written and adresses an important problem in approximating better solutions of discrete optimal transport problem.
  2. Contributions of the paper are also clearly stated, which makes it easier to access and understand.
Critical weaknesses

One critical weakness, I see in the paper is that BSP-OT extends their methodology beyond uniformly sized source and targets, whereas the employment of exact LAP solvers in the improvements proposed in paper prohibit them to extend towards unequaly sized datasets. Another related concern is that in general, discrete optimal transport methods work on non-uniformly weighted masses also, BSP also considers that case too, whereas present paper does not consider that.

Questions for authors
  1. Authors should consider addressing the weaknesses mentioned above clearly.
  2. It can be observed from tables in paper that in almost all cases improvement proposed in paper (SER-OT) takes less time than BSP-OT, can you explain why?
  3. It is obvious that by increasing the number of possible bijections k, one can find better approximations. How does the parameter b effect approximations
3 comments

We thank the reviewer for the time and effort spent reviewing our paper.


Q1. Authors should consider addressing the weaknesses mentioned above clearly.

Reply:\color{red}{\textbf{Reply:}}

The Conclusion already states these weaknesses: SER-OT is limited to equally sized, uniformly weighted point clouds, and practical LAP solvers have super-linear worst-case guarantees. Since they may be easy to miss there, the revised version will use its additional page to describe them in a dedicated Limitations section, together with future work.

Q2. It can be observed from tables in paper that in almost all cases improvement proposed in paper (SER-OT) takes less time than BSP-OT, can you explain why?

Reply:\color{red}{\textbf{Reply:}}

Mainly because BSP-OT recomputes distances over all coordinates while merging tree matchings, whereas SER-OT reuses candidate costs from tree construction. Padding inputs to 1,024D leaves distances unchanged but slows BSP-OT merging by 28.53× and 10.56×, while SER-OT's global LAP time changes by only 1.03×. Conversely, BSP-OT is faster on low-dimensional hard geometric inputs.

Details:\color{red}{\textbf{Details:}}

Each distance computation in BSP-OT's merging reads all coordinates, so merging becomes expensive as the dimension grows. SER-OT's global LAP reuses costs computed during tree construction and avoids this.

To test this, we padded Torus–trefoil from 3 to 1,024 dimensions and Anisotropic from 64 to 1,024 with zero coordinates, keeping all distances unchanged. BSP-OT merged the same 64 tree matchings, and SER-OT used the same seeds. The table gives the ratio of stage times after and before padding.

InputNDimension changeBSP-OT merge time ratioSER-OT global LAP time ratio
Torus–trefoil8,1923 → 1,02428.53×1.03×
Anisotropic2,04864 → 1,02410.56×1.03×

High-dimensional representations are common in machine learning, and on 4,096D Gaussian-to-image SER-OT is 2.1–2.3× faster than BSP-OT in total. On low-dimensional inputs, distances are cheap and the global LAP can dominate, so BSP-OT is faster on the hard geometric cases.

For more details, please see our reply to Q3 of Reviewer 78hV: https://openreview.net/forum?id=rtb7cFyBXb&noteId=dDYYIEDTwC

Q3. It is obvious that by increasing the number of possible bijections k, one can find better approximations. How does the parameter b effect approximations

Reply:\color{red}{\textbf{Reply:}}

Basically, a larger bb improves accuracy, but the improvement is not monotonic, and runtime rises once bb becomes large. bb is the maximum leaf size, and a larger bb lets exact leaf LAPs optimize more points jointly: with k=16k=16, increasing bb from 1 to 256 improves Gap in 13 of 14 settings and ties in one. However, a large bb raises runtime: b=256b=256 is up to 8.6× slower than b=64b=64. The effect on Gap is also not always monotonic, for example on 2D mixture between b=64b=64 and 256.

Details:\color{red}{\textbf{Details:}}

At b=1b=1, partitioning fixes every match. Each tree contributes NN edges for any bb, so bb does not change the kNkN bound on retained edges. Different values of bb give different, non-nested candidate graphs, so Gap need not decrease monotonically.

We fixed k=16k=16, as in the appendix, and varied bb over 1, 4, 16, 64, and 256 on all 14 settings. Values are means over three inputs; Gaussian-to-image uses three seeds on one input. The table reports mean Gap in percent.

\hline \strut & \text{Mean Gap} \cr \begin{array}{lr} \text{Input} & N \cr \hline \text{Synthetic (16D)} & 8{,}192 \cr \text{Synthetic (64D)} & 8{,}192 \cr \text{Synthetic (128D)} & 8{,}192 \cr \text{Synthetic (256D)} & 8{,}192 \cr \text{Synthetic (512D)} & 8{,}192 \cr \text{Synthetic (1024D)} & 8{,}192 \cr \text{Gaussian-to-image (4096D)} & 8{,}192 \cr \text{Nonlinear (16D)} & 2{,}048 \cr \text{Anisotropic (64D)} & 2{,}048 \cr \text{Multimodal (16D)} & 2{,}048 \cr \text{Manifold (16D)} & 2{,}048 \cr \text{Geometry mismatch (16D)} & 8{,}192 \cr \text{Torus–trefoil (3D)} & 8{,}192 \cr \text{2D mixture (2D)} & 8{,}192 \cr \end{array} & \begin{array}{rrrrr} b = 1 & b = 4 & b = 16 & b = 64 & b = 256 \cr \hline 3.356271 & 1.639820 & 0.256185 & 0.219538 & 0.178062 \cr 1.512855 & 0.536834 & 0 & 0 & 0 \cr 0.203901 & 0.098937 & 0 & 0 & 0 \cr 0.283666 & 0.043050 & 0 & 0 & 0 \cr 0.055636 & 0 & 0 & 0 & 0 \cr 0 & 0 & 0 & 0 & 0 \cr 0.011293 & 0.010226 & 0.006990 & 0.003852 & 0.001464 \cr 1.109158 & 0.124685 & 0 & 0.189312 & 0 \cr 0.670769 & 0.198157 & 0 & 0 & 0 \cr 0.317799 & 0.095476 & 0.017766 & 0.007452 & 0.007639 \cr 0.429344 & 0.504872 & 0.403913 & 0.334652 & 0.248075 \cr 2.311395 & 1.972859 & 1.200700 & 0.634020 & 0.340987 \cr 4.355149 & 4.347115 & 4.429198 & 3.763160 & 2.828863 \cr 0.403683 & 0.373331 & 0.376702 & 0.350342 & 0.363353 \cr \end{array} \cr \hline \end{array}$$ The runtime table, in seconds, uses the same 16-thread setup. Large leaves can cost more time, while intermediate values can be fastest because they reduce partitioning work without making leaf LAPs too large. The best $b$ depends on the dataset. $$\begin{array}{cc} \hline \strut & \text{Mean runtime} \cr \begin{array}{lr} \text{Input} & N \cr \hline \text{Synthetic (16D)} & 8{,}192 \cr \text{Synthetic (64D)} & 8{,}192 \cr \text{Synthetic (128D)} & 8{,}192 \cr \text{Synthetic (256D)} & 8{,}192 \cr \text{Synthetic (512D)} & 8{,}192 \cr \text{Synthetic (1024D)} & 8{,}192 \cr \text{Gaussian-to-image (4096D)} & 8{,}192 \cr \text{Nonlinear (16D)} & 2{,}048 \cr \text{Anisotropic (64D)} & 2{,}048 \cr \text{Multimodal (16D)} & 2{,}048 \cr \text{Manifold (16D)} & 2{,}048 \cr \text{Geometry mismatch (16D)} & 8{,}192 \cr \text{Torus–trefoil (3D)} & 8{,}192 \cr \text{2D mixture (2D)} & 8{,}192 \cr \end{array} & \begin{array}{rrrrr} b = 1 & b = 4 & b = 16 & b = 64 & b = 256 \cr \hline 0.057 & 0.038 & 0.031 & 0.063 & 0.298 \cr 0.068 & 0.045 & 0.044 & 0.076 & 0.242 \cr 0.075 & 0.047 & 0.054 & 0.086 & 0.280 \cr 0.130 & 0.073 & 0.068 & 0.120 & 0.384 \cr 0.168 & 0.085 & 0.080 & 0.165 & 0.529 \cr 0.258 & 0.123 & 0.112 & 0.220 & 0.762 \cr 1.452 & 0.965 & 0.977 & 1.683 & 4.149 \cr 0.014 & 0.010 & 0.013 & 0.013 & 0.043 \cr 0.019 & 0.013 & 0.011 & 0.015 & 0.035 \cr 0.015 & 0.011 & 0.011 & 0.025 & 0.215 \cr 0.075 & 0.069 & 0.074 & 0.093 & 0.297 \cr 1.893 & 2.096 & 2.418 & 2.736 & 3.297 \cr 1.897 & 1.663 & 1.694 & 2.372 & 3.191 \cr 4.490 & 5.018 & 5.114 & 4.673 & 6.151 \cr \end{array} \cr \hline \end{array}$$
Reviewer_78hVOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes SER-OT for large-scale optimal transport between equally sized, uniformly weighted point clouds. Building on BSP-OT’s paired partitioning framework, it introduces target-point-difference projection directions, exact assignment within small leaf subsets, and global recombination of matching edges across multiple randomized trees. The resulting candidate graph contains at most kNkN edges. Experiments include synthetic problems with over one million points, high-dimensional image latent features, and diverse geometric distributions. Comparisons with BSP-OT, HiRef, and HALO, alongside ablations and candidate-graph controls, show low transport-cost gaps and favorable runtime in many tested settings. On harder geometric instances, improved accuracy comes with greater runtime than BSP-OT.

Critical strengths

Clear and targeted design. It refines candidate edges using data-dependent directions and local LAPs, followed by a global LAP to jointly optimize matchings discovered by different trees; the candidate edge set is bounded by at most kN edges and always guarantees a feasible matching.

Critical weaknesses

1.The CPU-only evaluation may disadvantage GPU-oriented baselines. For example, HALO’s official implementation targets GPUs, HiRef’s PyTorch/JAX implementations support GPU acceleration, and BSP-OT also provides a CUDA implementation; reporting CPU-only runtimes without clarifying the baseline implementations and how they were adapted may underestimate their efficiency. GPU comparisons using official implementations should be included. 2. The million-scale validation is limited to structured synthetic instances. Million-scale results appear only in Table 1, where BSP-OT and SER-OT both frequently achieve cost gaps that round to zero, providing limited evidence of an accuracy advantage. Extending the image-latent and geometrically diverse benchmarks in Tables 2 and 3 to substantially larger sizes would help establish whether SER-OT maintains its accuracy and practical runtime on harder instances, particularly where global recombination is already more expensive than BSP-OT.

Questions for authors
  1. Can authors provides results on low-dimensional tasks suited to f hierarchical baselines tailored for medium-to-high dimensions.
  2. Could the authors provide a component-wise ablation study on the data-dependent projection directions, exact local (leaf) LAP, and exact global LAP on the same set of hard instances under a unified setting, reporting both Gap and runtime? The current ablation and parameter sensitivity experiments do not yet fully disentangle the individual contributions of these three components.
  3. In Table 3, on the two harder instances at N=8,192 (Geometry mismatch and Torus–trefoil), SER-OT is approximately 39× and 72× slower than BSP-OT, respectively. Could the authors report a runtime breakdown across the different stages (e.g., projection, local leaf LAP, and global LAP) to explain the computational bottleneck and how it scales with problem size N?
  4. Also adrress the issue mentioned in critial weakness.
10 comments

We thank the reviewer for the time and effort spent reviewing our paper.


Q1. Can authors provides results on low-dimensional tasks suited to f hierarchical baselines tailored for medium-to-high dimensions.

Reply:\color{red}{\textbf{Reply:}}

The phrase "suited to f" appears incomplete, and we are unsure how low-dimensional tasks relate to baselines "tailored for medium-to-high dimensions." We read the question as a request for low-dimensional results, including comparisons with hierarchical baselines.

We tested 2D and 3D inputs at N = 2,048 and 8,192. SER-OT is more accurate than BSP-OT and HiRef in all four settings, while BSP-OT is fastest. HALO is the most accurate, with a Gap of essentially 0%, but is 52–97× slower than SER-OT. In low dimensions, hierarchical methods such as HALO are very accurate, but runtime becomes the problem.

Details:\color{red}{\textbf{Details:}}

We compare SER-OT, BSP-OT, HiRef, and HALO with its official SciPy/HiGHS backend. The table reports mean Gap (%) and time (s) over three independent inputs.

\begin{array}{c|c|c} \hline \strut & \text{2D Gaussian–mixture} & \text{3D Torus–trefoil} \cr \begin{array}{c} \strut \cr \begin{array}{l} \text{Method} \cr \hline \text{SER-OT} \cr \text{BSP-OT} \cr \text{HiRef} \cr \text{HALO} \cr \end{array} \cr \end{array} & \begin{array}{c|c} N = 2{,}048 & N = 8{,}192 \cr \begin{array}{rr} \text{Gap} & \text{Time} \cr \hline 0.103746 & 1.151 \cr 1.632793 & 0.027 \cr 1.867779 & 16.685 \cr 0.000000 & 59.853 \cr \end{array} & \begin{array}{rr} \text{Gap} & \text{Time} \cr \hline 0.079092 & 13.752 \cr 0.568279 & 0.054 \cr 0.573318 & 59.911 \cr 0.000000 & 1087.606 \cr \end{array} \cr \end{array} & \begin{array}{c|c} N = 2{,}048 & N = 8{,}192 \cr \begin{array}{rr} \text{Gap} & \text{Time} \cr \hline 0.207823 & 0.438 \cr 7.408971 & 0.035 \cr 12.530657 & 16.707 \cr 0.000000 & 27.337 \cr \end{array} & \begin{array}{rr} \text{Gap} & \text{Time} \cr \hline 0.608367 & 5.513 \cr 11.941501 & 0.075 \cr 6.880286 & 59.646 \cr 0.000001 & 537.329 \cr \end{array} \cr \end{array} \cr \hline \end{array}$$ BSP-OT is fastest, and SER-OT has lower Gap than BSP-OT and HiRef. HALO reaches a Gap of essentially 0% but is 52–97× slower than SER-OT with the same 16 CPU threads.

Q2. Could the authors provide a component-wise ablation study on the data-dependent projection directions, exact local (leaf) LAP, and exact global LAP on the same set of hard instances under a unified setting, reporting both Gap and runtime? The current ablation and parameter sensitivity experiments do not yet fully disentangle the individual contributions of these three components.

Reply:\color{red}{\textbf{Reply:}}

Each component contributes. Removing any one never lowers mean Gap in the 14 benchmark settings at the largest sizes, up to N = 1,048,576. Full SER-OT, labeled A, beats uniform random directions B in 6 settings, singleton leaves C in 8, and BSP-OT merging D in 6, and ties at 0% elsewhere. Global recombination matters most on hard inputs, for example 0.015% versus 9.55% on Manifold. In runtime, it is slower than BSP-OT merging on the four hard inputs with N ≤ 8,192, but up to 2.3× faster on million-point synthetic inputs.

Details:\color{red}{\textbf{Details:}}

We use all benchmark families at the largest sizes with reference assignments, including all six synthetic dimensions. All conditions use 64 trees. Results are means over three seeds; Gaussian-to-image uses one fixed input. B–D each change one component of A:

  • A: Full SER-OT: target-difference directions, 64-point leaf LAPs, and global recombination.
  • B: Replace target-difference directions with uniform random directions.
  • C: Replace 64-point leaves with singleton leaves.
  • D: Replace global recombination with official BSP-OT merging on the same 64 tree matchings.

Mean Gap (%):

DatasetNABCD
Synthetic (16D)1,048,5760.003350860.02298650.1331870.439086
Synthetic (64D)1,048,576000.006541560
Synthetic (128D)1,048,576000.002320060
Synthetic (256D)1,048,5760000
Synthetic (512D)1,048,5760000
Synthetic (1024D)1,048,5760000
Gaussian-to-image (4096D)131,0720.004822220.007368030.01129620.0111102
Nonlinear (16D)2,0480000
Anisotropic (64D)2,0480000
Multimodal (16D)2,0480000
Manifold (16D)2,0480.01488170.06422910.02127429.55401
Geometry mismatch (16D)8,1920.05638170.2982920.5032811.68279
Torus–trefoil (3D)8,1920.6083671.039450.7530497.0637
2D mixture (2D)8,1920.07909240.1037480.08069320.681577

Mean runtime (s):

DatasetNABCD
Synthetic (16D)1,048,57626.662831.618330.831434.0039
Synthetic (64D)1,048,57633.940334.102532.344650.8062
Synthetic (128D)1,048,57645.425647.251446.293375.1121
Synthetic (256D)1,048,57668.271270.827970.0258120.325
Synthetic (512D)1,048,57699.992497.8863102.407216.849
Synthetic (1024D)1,048,576160.351158.947168.719373.057
Gaussian-to-image (4096D)131,072123.675188.149199.133181.948
Nonlinear (16D)2,0480.04165390.05061660.0314060.161534
Anisotropic (64D)2,0480.0369980.04616870.0587490.133673
Multimodal (16D)2,0480.07725550.1027350.03895280.126924
Manifold (16D)2,0480.3414640.3816190.2949640.11752
Geometry mismatch (16D)8,1926.688336.178596.832210.468341
Torus–trefoil (3D)8,1925.936476.369755.869810.520101
2D mixture (2D)8,19212.677813.038513.45980.609762

A has lower mean Gap than B in 6 settings, than C in 8, and than D in 6. All other comparisons tie at 0%.

Q3. In Table 3, on the two harder instances at N=8,192 (Geometry mismatch and Torus–trefoil), SER-OT is approximately 39× and 72× slower than BSP-OT, respectively. Could the authors report a runtime breakdown across the different stages (e.g., projection, local leaf LAP, and global LAP) to explain the computational bottleneck and how it scales with problem size N?

Reply:\color{red}{\textbf{Reply:}}

In low dimensions, the global LAP is SER-OT's bottleneck. At N = 8,192, it takes 96% of the runtime on Geometry mismatch and 91% on Torus–trefoil, and total time grows about 10–14× when N quadruples. BSP-OT is faster here because its tree merging is cheap in low dimensions. This merging recomputes distances over all coordinates, so it becomes very heavy in high dimensions. The global LAP reuses costs from tree construction and stays much lighter. On 4,096D Gaussian-to-image at N = 8,192, BSP-OT merging takes 6.7 s, while SER-OT's global LAP takes 0.9 s. As a result, SER-OT is 2.1–2.3× faster than BSP-OT in high dimensions.

Details:\color{red}{\textbf{Details:}}

All experiments below use 64 trees, 64-point leaves, and 16 threads. Values are means over three inputs, or over three runs for Gaussian-to-image.

1. In low dimensions, the global LAP takes almost all of SER-OT's runtime.

We time each stage of SER-OT on Geometry mismatch and Torus–trefoil at N = 2,048, 8,192, and 32,768. The global LAP share grows with N to 95.8–98.6%, and the global LAP accounts for almost all of the runtime increase.

InputNTrees (s)Global LAP (s)Other (s)Total (s)LAP share (%)
Geometry mismatch2,0480.0650.3390.0080.41282.3
Geometry mismatch8,1920.2546.4520.0276.73395.8
Geometry mismatch32,7681.11889.4660.11890.70298.6
Torus–trefoil2,0480.1010.3290.0080.43875.1
Torus–trefoil8,1920.4855.0080.0205.51390.8
Torus–trefoil32,7682.20752.1280.10454.43995.8

2. Tree generation is minor.

On the same inputs, we split the time of each tree into projection and sorting, leaf cost construction, and leaf LAP. Leaf LAPs take most of each tree's time, but all trees together take at most 2.2 s, far less than the global LAP.

InputNProjection and sorting (s)Leaf cost construction (s)Leaf LAP (s)
Geometry mismatch2,0480.0017850.0012430.011437
Geometry mismatch8,1920.0102500.0048700.042402
Geometry mismatch32,7680.0583650.0199820.180802
Torus–trefoil2,0480.0016700.0010870.020217
Torus–trefoil8,1920.0096100.0042980.096875
Torus–trefoil32,7680.0527700.0168090.438119

3. The bottleneck shifts with dimension.

We compare the stage shares of both methods on low-dimensional, synthetic, and 4,096D inputs. In low dimensions, the global LAP dominates SER-OT, and BSP-OT is 74–117× faster. At 4,096D, merging takes about half of BSP-OT's time, and SER-OT is 2.1–2.3× faster.

Totals are in seconds; Merge and Global LAP are shares of the total in percent.

\hline \strut & \text{BSP-OT} & \text{SER-OT} \cr \begin{array}{lr} \text{Dataset} & N \cr \hline \rlap{\textit{Hard low-dimensional inputs}} & \cr \text{2D mixture (2D)} & 8{,}192 \cr \text{Torus–trefoil (3D)} & 8{,}192 \cr \text{Geometry mismatch (16D)} & 8{,}192 \cr \hline \rlap{\textit{Synthetic inputs}} & \cr \text{Nonlinear (16D)} & 2{,}048 \cr \text{Multimodal (16D)} & 2{,}048 \cr \text{Manifold (16D)} & 2{,}048 \cr \text{Anisotropic (64D)} & 2{,}048 \cr \hline \rlap{\textit{High-dimensional inputs}} & \cr \text{Gaussian-to-image (4096D)} & 2{,}048 \cr \text{Gaussian-to-image (4096D)} & 8{,}192 \cr \end{array} & \begin{array}{rr} \text{Total} & \text{Merge} \cr \hline & \cr \mathbf{0.108} & 22.0 \cr \mathbf{0.064} & 34.8 \cr \mathbf{0.081} & 35.3 \cr \hline & \cr 0.024 & 43.2 \cr 0.019 & 45.5 \cr 0.021 & 44.0 \cr 0.033 & 33.3 \cr \hline & \cr 2.238 & \mathbf{47.3} \cr 12.180 & \mathbf{54.8} \cr \end{array} & \begin{array}{rr} \text{Total} & \text{Global LAP} \cr \hline & \cr 12.617 & \mathbf{95.2} \cr 5.430 & \mathbf{90.6} \cr 6.023 & \mathbf{95.5} \cr \hline & \cr 0.035 & 0.8 \cr 0.070 & 2.4 \cr 0.258 & 57.4 \cr 0.035 & 0.7 \cr \hline & \cr \mathbf{1.047} & 4.7 \cr \mathbf{5.279} & 17.2 \cr \end{array} \cr \hline \end{array}$$
Reviewer_x6C3OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a heuristic algorithm for large-scale optimal assignment problems, primarily based on improvements to BSP-OT. The proposed method introduces three main modifications. First, it changes the strategy for selecting projection directions during tree construction. Second, it introduces a stopping criterion for recursive tree partitioning, allowing small leaf-level assignment problems to be solved exactly. Third, it adopts an improved recombination strategy that takes global information into account. The paper also provides some theoretical guarantees supporting these improvements. Experimental results show that, under the tested settings, the proposed method outperforms the original BSP-OT in both computational efficiency and approximation accuracy.

This paper proposes an improved version of BSP-OT with three main modifications. The experimental results demonstrate substantial improvements in both computational efficiency and accuracy over BSP-OT across all the reported cases. If the effectiveness of the method could be established across a broader range of settings, it would represent a valuable improvement. However, the method remains heuristic and lacks theoretical guarantees. Moreover, the paper does not provide sufficient analysis of failure cases, comprehensive ablation studies, or validation on a sufficiently diverse range of problems. Therefore, I find the current experimental evidence insufficiently convincing.

Critical strengths

The main strength of this paper is its clearly motivated and well-structured methodology, which offers substantial improvements over the original BSP-OT algorithm. These improvements are supported to some extent by both theoretical analysis and experimental results.

Critical weaknesses
  1. Regarding the theoretical analysis, the theorem associated with the first modification only guarantees that the selected projection direction is more aligned with the data distribution. However, this does not guarantee that partitioning along this direction will lead to a better approximation of the optimal OT solution. In fact, counterexamples can be constructed in which such a partitioning strategy performs worse than the original method. Therefore, the theoretical justification for this modification is relatively weak. Moreover, the experimental evaluation lacks sufficiently rigorous evidence to demonstrate that this modification consistently improves performance across a broad range of settings.
  2. Regarding the experiments, since the proposed method is heuristic and lacks a theoretical guarantee of convergence to the optimal solution of the original problem, it is important to provide an analysis of failure cases and discuss the conditions under which the method may fail.
Questions for authors
  1. Please provide failure cases and discuss the conditions under which the proposed method may perform worse than BSP-OT.
  2. Regarding the first modification, please clarify whether the proposed projection strategy could perform worse than the original strategy for certain distributions.
  3. Please provide ablation studies to evaluate the individual contributions of the three proposed modifications.
3 comments

We thank the reviewer for the time and effort spent reviewing our paper.

We answer Q2 first because it explains Q1. In a constructed case, the projection loses optimal matches, and this makes the whole method worse than BSP-OT.


Q2. Regarding the first modification, please clarify whether the proposed projection strategy could perform worse than the original strategy for certain distributions.

Reply:\color{red}{\textbf{Reply:}}

Yes, for some distributions. In a constructed 2D example, every direction defined by two target points separates one source group from its optimal target group, so their optimal matches are excluded from all trees. Uniform random directions reduce Gap on this example from 66.67% to 0%. On the 14 benchmark settings in Q3, however, the proposed directions were never worse: they were better in 6 settings and tied at 0% in 8. Proposition 1 describes this adaptation and does not guarantee lower OT error.

Details:\color{red}{\textbf{Details:}}

For Q2, we constructed a special case. It is a pair of discrete distributions built from the following configuration. Each cloud has 128 points in four groups of 32. Each group is 32 points spaced 0.001 apart along the xx-axis and centered at a point in the table below. For example, the source group centered at (0,1)(0, 1) consists of (−0.0155,1),(−0.0145,1),…,(0.0155,1)(-0.0155, 1), (-0.0145, 1), \dots, (0.0155, 1).

Source group centerTarget group center
(−1,1)(-1, 1)(−1,2)(-1, 2)
(0,1)(0, 1)(1,0)(1, 0)
(1,−1)(1, -1)(0,−2)(0, -2)
(2,1)(2, 1)(2,2)(2, 2)

For these distributions, the optimal solution matches each source group to the target group in the same row, with a mean cost of 1.5. In particular, the source group around (0,1)(0, 1) must be matched to the target group around (1,0)(1, 0). However, every direction obtained by connecting two target points puts these two groups into opposite halves at the root split. We checked all (1282)=8128\binom{128}{2} = 8128 pairs of target points. Since SER-OT allows matches only between corresponding halves, this optimal match never enters the candidate set, however many trees we build, and global recombination cannot recover it. With 64 trees and 64-point leaves as in the paper, SER-OT gives a mean cost of 2.5, a Gap of 66.67% in all three seeds. Uniform random directions give 0% Gap in the same seeds.

In the Q3 ablation, A uses target-difference directions and B uses uniform random directions. A has lower mean Gap in 6 settings, and both reach 0% in the other 8. The proposed directions thus help on these benchmarks, but the example above shows that an option to include uniform random directions is needed.


Q1. Please provide failure cases and discuss the conditions under which the proposed method may perform worse than BSP-OT.

Reply:\color{red}{\textbf{Reply:}}

SER-OT fails when an optimal source–target match crosses the split boundary in every tree. No tree then retains that match, and global recombination cannot recover it. The example in Q2 is such a case: the excluded match never enters SER-OT's candidate set, so SER-OT reaches a mean cost of 2.5 against the optimum of 1.5, a Gap of 66.67% in all three seeds. Official BSP-OT gives a mean Gap of 0.31% over ten runs, ranging from 0 to 3.06%. Such specially constructed cases may be rare in practice, but they show that the proposed partitioning is not always better and motivate also including uniform random directions.

Q3. Please provide ablation studies to evaluate the individual contributions of the three proposed modifications.

Reply:\color{red}{\textbf{Reply:}}

Each component contributes. Removing any one never lowers mean Gap in the 14 benchmark settings at the largest sizes, up to N = 1,048,576. Full SER-OT, labeled A, beats uniform random directions B in 6 settings, singleton leaves C in 8, and BSP-OT merging D in 6, and ties at 0% elsewhere. Global recombination matters most on hard inputs, for example 0.015% versus 9.55% on Manifold.

Details:\color{red}{\textbf{Details:}}

We use all benchmark families at the largest sizes with reference assignments, including all six synthetic dimensions. All conditions use 64 trees. Results are means over three seeds; Gaussian-to-image uses one fixed input. B–D each change one component of A:

  • A: Full SER-OT: target-difference directions, 64-point leaf LAPs, and global recombination.
  • B: Replace target-difference directions with uniform random directions.
  • C: Replace 64-point leaves with singleton leaves.
  • D: Replace global recombination with official BSP-OT merging on the same 64 tree matchings.

Mean Gap (%):

DatasetNABCD
Synthetic (16D)1,048,5760.003350860.02298650.1331870.439086
Synthetic (64D)1,048,576000.006541560
Synthetic (128D)1,048,576000.002320060
Synthetic (256D)1,048,5760000
Synthetic (512D)1,048,5760000
Synthetic (1024D)1,048,5760000
Gaussian-to-image (4096D)131,0720.004822220.007368030.01129620.0111102
Nonlinear (16D)2,0480000
Anisotropic (64D)2,0480000
Multimodal (16D)2,0480000
Manifold (16D)2,0480.01488170.06422910.02127429.55401
Geometry mismatch (16D)8,1920.05638170.2982920.5032811.68279
Torus–trefoil (3D)8,1920.6083671.039450.7530497.0637
2D mixture (2D)8,1920.07909240.1037480.08069320.681577

Mean runtime (s):

DatasetNABCD
Synthetic (16D)1,048,57626.662831.618330.831434.0039
Synthetic (64D)1,048,57633.940334.102532.344650.8062
Synthetic (128D)1,048,57645.425647.251446.293375.1121
Synthetic (256D)1,048,57668.271270.827970.0258120.325
Synthetic (512D)1,048,57699.992497.8863102.407216.849
Synthetic (1024D)1,048,576160.351158.947168.719373.057
Gaussian-to-image (4096D)131,072123.675188.149199.133181.948
Nonlinear (16D)2,0480.04165390.05061660.0314060.161534
Anisotropic (64D)2,0480.0369980.04616870.0587490.133673
Multimodal (16D)2,0480.07725550.1027350.03895280.126924
Manifold (16D)2,0480.3414640.3816190.2949640.11752
Geometry mismatch (16D)8,1926.688336.178596.832210.468341
Torus–trefoil (3D)8,1925.936476.369755.869810.520101
2D mixture (2D)8,19212.677813.038513.45980.609762

A has lower mean Gap than B in 6 settings, than C in 8, and than D in 6. All other comparisons tie at 0%.

Thank you for your response. My concerns have been addressed.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.