MLOT: Extending the Bipartite Structure towards Multi-Layered Structure for Optimal Transport

We sincerely appreciate your time and thorough review. We hope the following answers help clarify the points you raised.

Q1: Could you provide the wall-clock computation time for the Image-Text Retrieval task in Table 2? The proposed method is likely to be slower compared to the standard softmax operation.

A1: Thank you for the question. We conducted additional experiments to measure the wall-clock computation time for the Image-Text Retrieval task, and the results are provided in Appendix. F Table 4.

You are correct that formulating the retrieval task as an MLOT problem increases the inference time compared to directly using the standard softmax operation. However, it is important to emphasize that our proposed method is training-free, which only modifies the inference process and does not require any additional training to improve retrieval accuracy.

In comparison to other methods that also employ data augmentation to enhance CLIP’s performance, such as MixGen$^1$, CLIP-MedFake$^2$ etc., which require additional training, our algorithm does not involve any retraining of the model. We believe the extra time required by our algorithm in inference is a reasonable trade-off given the observed improvements in R@k.

Q2: In the Image-Text Retrieval task, the two couplings can indicate different image-caption pairings. How coherent are these two couplings?

A2: As shown in Appendix. F Table 3, we record the respective prediction results from 2 MLOT coulings (Since 3 layers in total) separately.

As shown in the darker rows of the first table, using individual OT predictions alone does not significantly improve accuracy; only when both are used in MLOT do we observe a noticeable improvement.

The second table shows how many predictions are identical among the 10 preidictions given by two couplings respectively. For Text$\Rightarrow$Image task, the overlap between the two coupling is relatively low, thus combining them (by averaging) leads to a more significant performance improvement. For Image$\Rightarrow$Text task, they are more coherent, and averaging them yields a less improvement.

Q3:In the Image-Text Retrieval task, the standard OT problem can be directly applied between the Query image and Caption using the same cost as in the MLOT, i.e., the negative cosine similarity between the normalized embeddings. Is there a meaningful difference in performance between the MLOT and OT frameworks (Table 2)?

A3: Thank you for your question. As shown in the above experiment tables, the darker rows in the first table indicate that using a single OT coupling prediction does not outperform the softmax-based approach. It is only when we leverage all the coupling information from MLOT, a significant performance improvement is achieved. This highlights the added benefit of considering multiple couplings in the MLOT framework.

1. https://openaccess.thecvf.com/content/WACV2023W/Pretrain/papers/Hao_MixGen_A_New_Multi-Modal_Data_Augmentation_WACVW_2023_paper.pdf
2. H. Chen et al., "Clip-Medfake: Synthetic Data Augmentation With AI-Generated Content for Improved Medical Image Classification," 2024 IEEE International Conference on Image Processing

Dear Authors,

Since the discussion phase has been extended and is now approaching its conclusion in the next eight days, I wanted to kindly follow up as I have not received any responses from you since the rebuttal period began.

Therefore, please submit your rebuttal at the earliest opportunity, allowing me sufficient time to review and provide my responses before the deadline.

Best regards,

We greatly appreciate your detailed review and the time you dedicated to evaluating our work. We have carefully considered your feedback and hope the following responses address your concerns.

Q1: My biggest question lies in the motivation for finding the OT distance between multiple distributions, which involves uncertain intermediate distributions, and only the source and the target distribution are known. And finding the OT distance between two distributions is not enough

A1: Thank you for the comments. The motivation behind MLOT comes from real-world problems, specifically cross-border e-commerce operations. In such scenarios, the source distribution (e.g., production capacity) and target distribution (e.g., market demand) are fixed and known, but the intermediate distributions—such as the transportation routes and transit stations—are uncertain and flexible. This uncertainty in the intermediate process inspired us to propose the MLOT problem, which captures the dynamic nature of transport processes that cannot be modeled by traditional optimal transport approaches with fixed marginals.

"Finding the OT distance between two distributions is not enough". You're right. That's why in our approach we not only compute the optimal transport distance but also derive the sequence of optimal transport couplings $(\mathbf{P}_k)_k$ between the source and target distributions. What's more, the intermediate distributions $(\mathbf{a}_k)_k$ at the optimal transportation are computed by the way.

Q2: The related works section doesn't mention any previous works on multiple distributions in optimal transport.

A2: We have discussed the topic of Optimal Transport with multiple marginals in the related work section (Line 113) in our submission. Previous works on multiple distributions, such as Multi-Marginal Optimal Transport(MMOT), was formulated as Eq. 3 (Line 116): $\min_{P} <\mathbf{C},\mathbf{P}>$, where $\mathbf{C},\mathbf{P}\in U((\mathbf{a}_k)_k)$ and $<\cdot,\cdot>$ represents element-wise product.

Our proposed Multi-Layered Optimal Transport (MLOT) approach introduces two key differences:

• In MMOT, all marginal distributions are deterministic, whereas in MLOT, only the source and target distributions are pre-defined. The intermediate distributions are dynamically computed as part of the optimization process.
• MMOT calculates a single coupling $\mathbf{P}\in {\mathbb{R}^+_{n_1\times n_2\dots n_K}}$ which simultaneously couples all distributions. In contrast, MLOT computes a sequence of coupling matrices $\mathbf{P}\in U((\mathbf{a}_k)_k)$

Q3: Comparison with other optimal transport (OT) methods of similar scope is missing. Specifically, the authors evaluated MLOT-Sinkhorn against non-OT methods, yet did not compare it with other OT-based approaches for finding optimal transport distances between multiple distributions.

A3: Thanks for your comment. Please refer to our reply to Q6. In this paper, we compared our method with three OT-based methods in three experiments respectively (Graph OT, CLIP with traditional OT, and Barycenter). We apologize for not expressing this more clearly in the paper, and we will improve the clarity of our expression in the paper.

Q4: How to compute the intermediate distributions as mentioned in the paper?

A4: In our paper, the intermediate distributions are denoted as $(\mathbf{a}_k)_k$, where $k=2,3,\dots,K-1$ (The source and target distributions $\mathbf{a}_1$ and $\mathbf{a}_K$ are given as inputs). These intermediate distributions are iteratively computed using Eq. 9 (Line 206):

$$\mathbf{a}_k=\left\{
\begin{array}{cc}
      (\mathbf{u}_k\odot \mathbf{v}_{k-1})^{-\epsilon/\tau} &  \tau>0\\
     \big((\mathbf{S}_{k-1}^\top\mathbf{u}_{k-1})\odot (\mathbf{S}_{k}\mathbf{v}_{k})\big)^{1/2} & \tau=0
\end{array}
\right.$$

Upon convergence of the algorithm, the sequence $\mathbf{a_k}$ returned by the algorithm represents the intermediate distributions at the optimal transportation. (Or equivalently, $a_k = P_k \mathbf{1} = P_{k-1}^\top \mathbf{1}, ~k=2,\dots,K-1$ after convergence.)

We appreciate your valuable time and comments and we hope the following answers can address your concerns.

Q1: The theory part is just straight adaptation from known work of Sinkhorn algorithm. In proposition 4, convergence rate depends on γ, which is not easy to quantify.

A1: Thank you for pointing this out. At present, we have proven the global convergence of the algorithm, but a detailed analysis of the overall complexity remains as a future work.

Q2: For task of generating intermediate images, there is no baselines, or quantity to compare/assess the current method with others. This contribution is limited.

A2: Thank you for your comment. We present experimental results comparing the traditional approach of computing intermediate images via barycenter with our method using MLOT. As shown in the results, MLOT successfully performs this task and achieves slight improvements in smoothness.

However, the main contribution of our work is that, MLOT allows for the simultaneous computation of all intermediate images in a single step. In traditional methods via barycenter, it requires repeated computations for each intermediate image with varying $\lambda$ (For each image, we need set cost metric as $[\lambda D,(1-\lambda)D]$). In contrast, MLOT can solve all intermediates by setting cost metric as $[D,D\dots,D]$

The table below shows the time differences between the two methods for generating varying numbers of intermediate images. When $K=3$ (only 1 intermediate image needs to be generated), both methods demonstrate equivalent time complexity. However, when $K>3$, which requires generating more than one intermediate image, the time advantage of MLOT becomes significant.

Q3: It is not clear (theoretically, intuitively) that in text-image retrieval task, why do we need to use data augmentation to create another layer for OT?

A3: We apologize for not providing a clearer explanation. In previous works on CLIP, inference typically involves computing the predicted probabilities using softmax, then selects the most likely class with $\arg\max$.

Following the REOT NIPS23$^1$, classification (or matching) tasks can be viewed as a special case of OT. By introducing augmented data, we extend this view into the framework of Multi-layered OT.

What's more important is that, our method introduces data augmentation during inference. In contrasts, other augmentation-based methods, such as MixGen$^2$, CLIP-MedFake$^3$ etc., requires retraining to improve CLIP's performance. Our approach, by leveraging additional information, treats retrieval as a MLOT problem, and it's a training-free improvement.

As shown in figure below, we record the respective prediction results from 2 MLOT coulings (Since 3 layers in total) separately. As can be seen, using individual OT predictions alone does not significantly improve accuracy; only when both are used in MLOT do we observe a noticeable improvement.

1. Shi, Liangliang, Zhen, Haoyu, Zhang, Gu, and Yan, Junchi. "Relative Entropic Optimal Transport: A (Prior-aware) Matching Perspective to (Unbalanced) Classification." Advances in Neural Information Processing Systems (NeurIPS), 2023.
2. https://openaccess.thecvf.com/content/WACV2023W/Pretrain/papers/Hao_MixGen_A_New_Multi-Modal_Data_Augmentation_WACVW_2023_paper.pdf
3. H. Chen et al., "Clip-Medfake: Synthetic Data Augmentation With AI-Generated Content for Improved Medical Image Classification," 2024 IEEE International Conference on Image Processing

We appreciate your valuable time and comments and we hope the following answers can address your concerns.

Q1: The main problem I find in the paper is that the authors didn't answer the very question that they raised. Can MLOT help find the optimal routes and minimize the total cost?

A1: Thank you for your comment. We apologise for the potential misunderstanding. The real-world scenario (cross-border e-commerce) is the primary motivation for proposing our algorithm.

Similar to how traditional OT theory originated from the simple transportation problem (moving goods from sources directly to destinations), our algorithm originates from the more realistic and generalized scenario, since real-world transportation problems often involve intermediate stops, making them inherently multi-layered. Inspired by these complexities, we extend the classical OT framework to multi-layered framework.

As noted by works like Marco Cuturi's introduction of the Sinkhorn algorithm$^1$, which provides an efficient approximation for traditional OT problems, our algorithm similarly offers a computationally efficient approach to solving optimal transport in multi-layered scenarios.

Q2: In real-world problems, the intermediate distributions have certain constraints like the routes (cost matrix) and max capacity of the stops (intermediate distributions) in freight transportation example. The paper doesn't mention such constraints either in methodology or experiments.

A2: Thank you for your insightful suggestion. Our algorithm is designed to be flexible and can naturally handle such constraints.

For instance, when dealing with capacity constraints on the intermediate nodes, i.e. given constraints $\mathbf{s}_k$ on intermediates' distribution, $\mathbf{a}_k\leqslant\mathbf{s}_k,~k=2,3\dots K-1$. Our algorithm can easily incorporate this by adjusting the flow in each iteration: as long as $\mathbf{a}_k$ is computed during each iteration, we update it by $\mathbf{a}_k = \min(\mathbf{a}_k, \mathbf{s}_k)$.

To demonstrate our algorithm's effectiveness, we have conducted additional synthetic experiments, shown in papers' Appendix. F Table. 6. We randomly generate flow constraints for each layer (To increase the difficulty, the sum of the capacity constraints at each layer was set to 1, equaling to total transportation mass). Despite additional constraints, MLOT-Sinkhorn still provides highly accurate results compared to Gurobi, while maintaining efficient computation times.

Q3: In 4.2, MLOT was compared against softmax so it's not clear whether the gains were from OT or from the multi-layer formulation or both.

A3: Thanks for your giving us the opportunity for futher explanation. Our experiments are purely inference-based, with no retraining involved. The model used is the standard CLIP model$^2$.

Following the REOT NIPS23$^3$, classification (or matching) tasks can be viewed as a special case of OT. By introducing augmented data, we extend this view into the framework of Multi-layered OT.

What's more important is that, our method introduces data augmentation during inference. In contrast, other augmentation-based methods, such as MixGen$^4$, CLIP-MedFake$^5$ etc., requires retraining to improve CLIP's performance. Our approach, by leveraging additional information, treats retrieval as a MLOT problem, and it's a training-free improvement.

We conduct a new experiment, recording the respective prediction results from 2 MLOT coulings (Since 3 layers in total) separately, shown in Appendix. F Table. 3. As can be seen, using individual OT predictions alone does not significantly improve accuracy; only when both are used in MLOT do we observe a noticeable improvement.

1. Cuturi, Marco. "Sinkhorn Distances: Lightspeed Computation of Optimal Transport." Advances in Neural Information Processing Systems, vol. 26, 2013.
2. https://github.com/mlfoundations/open_clip
3. Shi, Liangliang, Zhen, Haoyu, Zhang, Gu, and Yan, Junchi. "Relative Entropic Optimal Transport: A (Prior-aware) Matching Perspective to (Unbalanced) Classification." Advances in Neural Information Processing Systems (NeurIPS), 2023.
4. https://openaccess.thecvf.com/content/WACV2023W/Pretrain/papers/Hao_MixGen_A_New_Multi-Modal_Data_Augmentation_WACVW_2023_paper.pdf
5. H. Chen et al., "Clip-Medfake: Synthetic Data Augmentation With AI-Generated Content for Improved Medical Image Classification," 2024 IEEE International Conference on Image Processing