- 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
- Paper is generally well written and adresses an important problem in approximating better solutions of discrete optimal transport problem.
- 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
- Authors should consider addressing the weaknesses mentioned above clearly.
- 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?
- 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
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?
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.
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.
| Input | N | Dimension change | BSP-OT merge time ratio | SER-OT global LAP time ratio |
|---|---|---|---|---|
| Torus–trefoil | 8,192 | 3 → 1,024 | 28.53× | 1.03× |
| Anisotropic | 2,048 | 64 → 1,024 | 10.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¬eId=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
Basically, a larger improves accuracy, but the improvement is not monotonic, and runtime rises once becomes large. is the maximum leaf size, and a larger lets exact leaf LAPs optimize more points jointly: with , increasing from 1 to 256 improves Gap in 13 of 14 settings and ties in one. However, a large raises runtime: is up to 8.6× slower than . The effect on Gap is also not always monotonic, for example on 2D mixture between and 256.
At , partitioning fixes every match. Each tree contributes edges for any , so does not change the bound on retained edges. Different values of give different, non-nested candidate graphs, so Gap need not decrease monotonically.
We fixed , as in the appendix, and varied 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}$$
We thank the reviewer for the time and effort spent reviewing our paper.
Q1. Authors should consider addressing the weaknesses mentioned above clearly.
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.