Optimal Multiple Transport with Applications to Visual Matching, Model Fusion and Beyond

**** Q1. how to build a cycle (ordering of measures for $K>2$) is not discussed in the paper

**** A1. For $K=3$, consider three sets: $A$, $B$, and $C$, with a mapping order defined as $A\to B$, $B\to C$, and $C\to A$, represented by matching matrices $\mathbf{P}_1$, $\mathbf{P}_2$, and $\mathbf{P}_3$. Consistency requires that $\mathbf{P}_1\mathbf{P}_2\mathbf{P}_3=\mathbf{I}$. If we switch the order to $A\to C$, $C\to B$, and $B\to A$, with matching matrices $\mathbf{P}_3^\top$, $\mathbf{P}_2^\top$, and $\mathbf{P}_1^\top$, the consistency becomes $\mathbf{P}_3^\top\mathbf{P}_2^\top\mathbf{P}_1^\top=\mathbf{P}_1\mathbf{P}_2\mathbf{P}_3=\mathbf{I}$. Therefore, for the case of three measures ($K=3$), switching the order (of Fig. 5) does not affect the problem formulation.We test the experiments on Willow_3GM with IPCA-GM as backbone and the results are given as follows. Although the problems with and without switching the order are equivalent, the results may differ slightly due to initialization and other factors.

As for $K>3$, switching the order does indeed impact the formulation of the problem. However, note our directed cyclical structure is essentially a subgraph of pairwise structure. When the latter is satisfied, the former is also satisfied, allowing our method to still improve the matching performance. We show the experiments of switching the second and third set order as follows:

It can be observed that the results with and without switching the order are actually very close to each other.

**** Q2. Justification for the alternating scheme. I think there might be connections to Generalized Conditional Gradients or Majoration-Minimization methods here.

**** A2. We initially proposed ROMT-Sinkhorn by referencing the computation and derivation of the Entropic Gromov-Wasserstein Distance. We are grateful to the reviewer for reminding us to understand our ROMT-Sinkhorn from the perspective of optimization algorithm frameworks. While we believe that ROMT-Sinkhorn does not seem to have a direct connection with Generalized Conditional Gradients or Majoration-Minimization, we have discovered that it can be associated with the Alternating Direction Method of Multipliers (ADMM). The outer loop of our algorithm essentially optimizes different variables $\{\mathbf{P}_k\}_k$, while the inner Sinkhorn iterative loop optimizes multipliers ${(f_k,g_k)}_k$. Once again, we appreciate the reviewer's reminder, which has provided further optimization potential for ROMT-Sinkhorn.

**** Q3. The existence to problem (8)

**** A3. Thanks to the reviewer for pointing out the limitation in the existence of problem (8) theoretically. The existence problem is both important and challenging, and currently, we are unable to provide proof of its existence. However, we firmly believe that in the matching setting (i.e., $\mathbf{a}^k=\mathbf{1}_n$), a solution to the problem (8) does exist.

In the general case, it seems to be related to the probability vectors ${\mathbf{a}^k}$ and the dimension numbers ${n_k}$. From the perspective of degrees of freedom, for any given $P_k$, assuming $\{P_s\}_{s\neq k}$,

there exist $n_k\times n_{k+1}$ variables and $n_k+n_{k+1}-1+n_1^2$ equations. This suggests that when $n_k>>n_1$ and $n_{k+1}>>n_1$, the equations have infinitely many solutions.

**** Q4. $K=2$ case. I believe that it might also be interesting. In the case where the number of samples (atoms) is the same in the two distributions (with uniform distributions), we have obviously that $PP^T=I$. When mass splitting occur, it is not always the case. What is then the impact of the regularization on the original sinkhorn problem ?

**** A4. We appreciate the reviewer for bringing up an interesting special case. In fact, for $K=2$, the consistency condition is not $PP^T=I$, but rather $diag(1/a)PP^Tdiag(1/b)=I$, where $a$ and $b$ are marginals. Additionally, when using entropic regularization for coupling, the consistency to $I$ is no longer satisfied because the coupling matrix is no longer sparse. This leads to the product of these matrices also being non-sparse.

Dear Reviewer,

Thank you very much for taking the time to review our paper. We appreciate the insightful comments and suggestions you provided. As the deadline for the discussion phase approaches, we have carefully considered your feedback and prepared a response to address the concerns raised. We kindly request your feedback on our response and welcome any further questions or suggestions you may have.

Once again, we would like to express our gratitude for your time and attention. Your expertise and guidance are invaluable to us in refining our research.

Best regards,

The authors

Q1: In comparison with Sinkhorn's method, RMOT-Sinkhorn just has one more constraint for the last mapping. In fact, it is not much different from the one using Sinkhorn.

A1: We address the question with following three points: 1) Many experimental results demonstrate that our RMOT-Sinkhorn algorithm significantly improves upon the pairwise Sinkhorn algorithm which is evident in the enhanced performance of CR and CACC metrics and most cases in ACC evaluation. 2) There may exist some misunderstandings that RMOT-Sinkhorn is not only for the last mapping. All the mapping will be affected (e.g. results in Fig.3). 3) RMOT-Sinkhorn is an iterative Sinkhorn method, which is similar to calculating the entropic Gromov-Wasserstein Distance. The key lies in effectively and reasonably calculating the modification of the cost matrix, which is not a straightforward task.

Q2: I do not agree with other two metrics, i.e CR and CACC, assessing the performance of methods, since they favor the author's method.

A2: In fact, similar metrics to CR have been widely used in literature in terms of multiple objects matching, e.g. specifically in Fig. 4(e) of [1] and the reference therein e.g. [2] which could be regarded as a special case of ours when everytime the number of sets for consistency computing is three. Moreover, CR and CACC can be regarded as extensions and refinements of ACC for multiple sets. They have meaningful and interpretable implications. We can redefine ACC from a matrix computation perspective as follows:

$$ACC = \frac{1}{n} <\prod_{k=1}^2(\hat{\mathbf{P}}_k\odot \mathbf{Y}_k),\mathbf{I}_n>$$

where $\mathbf{Y}_k$ represents the ground truth as a one-hot matrix. $\hat{\mathbf{P}}_1$ is the probability matrix for matching from the first set of points to the second set, and $\hat{\mathbf{P}}_2$ is the probability matrix for matching from the second set to the first set. In this particular case, we have $\hat{\mathbf{P}}_1= \hat{\mathbf{P}}_2^\top$ and $\mathbf{Y}_1=\mathbf{Y}_2^\top$. From this perspective, we define the CR and CACC metrics, incorporating the concept of K-marginal transportation:

$$\text{CR} = \frac{1}{n}<\prod_{k=1}^K\hat{\mathbf{P}}_k,\mathbf{I}_n> \text{ and } \text{CACC}=\frac{1}{n}<\prod_{k=1}^K(\hat{\mathbf{P}}_k\odot \mathbf{Y}_k),\mathbf{I}_n>$$

Note that $CR$ refers to the accuracy of forming cycles through matching, capturing the ability to establish correct pairwise matches within the set of $K$ points. On the other hand, CACC represents the accuracy of correctly matching all $K$ points, taking into account the entire cycle instead of only considering pairs of points as in traditional ACC metrics.

Q3: I do not see that the method is natural application to those problems unless the data sets have cyclical structures (e.g. Switching the order of Fig. 5).

A3: #### A3: Our model can be applied to various datasets [3], particularly those involving multi-modal data for matching. The reviewer may be concerned about the choice of order because natural datasets often exhibit more of a pairwise structure rather than a directed cyclical structure. However, this does not affect the usability of our model. To illustrate, consider three sets: $A$, $B$, and $C$, with a mapping order defined as $A\to B$, $B\to C$, and $C\to A$, represented by matching matrices $\mathbf{P}_1$, $\mathbf{P}_2$, and $\mathbf{P}_3$. Consistency requires that $\mathbf{P}_1\mathbf{P}_2\mathbf{P}_3=\mathbf{I}$. If we switch the order to $A\to C$, $C\to B$, and $B\to A$, with matching matrices $\mathbf{P}_3^\top$, $\mathbf{P}_2^\top$, and $\mathbf{P}_1^\top$, the consistency becomes $\mathbf{P}_3^\top\mathbf{P}_2^\top\mathbf{P}_1^\top=\mathbf{P}_1\mathbf{P}_2\mathbf{P}_3=\mathbf{I}$. Therefore, for the case of three measures ($K=3$), switching the order (of Fig. 5) does not affect the problem formulation.

For $K>3$, switching the order does indeed impact the formulation of the problem for datasets that exhibit pairwise relationships. However, note our directed cyclical structure is essentially a subgraph of pairwise structure. When the latter is satisfied, the former is also satisfied, allowing our method to still improve the matching performance. Besides, we can select multiple directed cyclical structures for OMT to achieve equivalence of pairwise structure one.

Q4: the guideline for choosing the parameter $\delta$ and $\epsilon$.

A4: We search for the optimal values of $\delta$ and $\epsilon$ in the validation dataset by maximizing the mean values of ACC and CACC metrics. Once determined, we apply these values to the testing data for evaluation.

Q5: it also appears to be a slightly different version of multi-OT problems, thus it looks like an incremental solution to some current methods.

A5: The key of Multi-marginal OT is the definition of cost tensor and if one can define the cost function among multiple marginals with consistency constraints, our OMT will become a subproblem of Multi-marginal OT. However, for the calculation, Multi-Marginal OT has an exponential increase in spatial complexity (N^K) as the number of marginals increases, while our method has a linear increase (NK), which is also a main difference.

Q6: In table 1, why does the Sinkhorn perform better than RMOT-Sinkhorn in PCA-GM in the ACC index?

A6: The regularization introduced by RMOT-Sinkhorn essentially increases the probability of forming cycles, ensuring that any given feature starts from the origin and returns to the origin. However, it does not guarantee an increase in the accuracy of each individual match within the cycle. For example, let's consider three sets: $A$, $B$, and $C$. Starting with the first feature $A[1]$, the prediction of Pairwise Sinkhorn is $A[1]\to B[2]$, $B[2]\to C[2]$, and $C[2]\to A[2]$. The modification introduced by RMOT-Sinkhorn could result in a change of matches to $A[2]\to B[2]$, $B[2]\to C[2]$, and $C[2]\to A[2]$. However, it is also possible for the modification to change the matches to $A[1]\to B[2]$, $B[2]\to C[2]$, and $C[2]\to A[1]$. The latter case actually decreases the evaluation of ACC.

Q7: In table 1, column NMGM, we have CR=100 but the ACC is only equal to 93.76. Does it mean that the consistent rate is not a good indicator of accuracy rate?

A7: $CR=100\%$ indicates that all the matches form cycles, but it does not guarantee that every individual match within the cycle is correct. On the other hand, a $CACC$ of $86.82$ means that there are errors in one or more nodes within $13.18$ of the cycles. Furthermore, one advantage of evaluating with $CR$ is that it does not require supervised data and it considers whether the predictions themselves are logically consistent, which is a strength of this evaluation metric.

BTW, it has been widely recognized that consistency has an empirically strong correlation to accuracy in many public benchmarks e.g. [1,2]. We will also add more references to support this point.

[1] Unifying Offline and Online Multi-Graph Matching via Finding Shortest Paths on Supergraph, IEEE TPAMI 2021 [2] Multi-Graph Matching via Affinity Optimization with Graduated Consistency Regularization, IEEE TPAMI 2016 [3] Artificial intelligence for multimodal data integration in oncology. Cancer cell 40, no. 10 (2022): 1095-1110.

Dear Reviewer,

Thank you for taking the time to review our paper. We greatly appreciate your valuable feedback and insightful comments. As the discussion deadline approaches, we would like to request your feedback on our response to address the concerns. We are also open to any further questions or suggestions that you may have.

Thanks for your time and attention. Your expertise and guidance are invaluable for our research.

Best regards,

The authors

Q1. The literature review for model fusion is not well-written.

A1: Thanks for your information and we will add these references. The revised literature review is uploaded in the new version.

Q2: My main concern is the scalability of OMT-Sinkhorn. All examples/experiments only consider three measures.

A2: We add visual matching experiments of four and five measures for OMT and the results(%) are shown as follows:

The experiment utilized IPCA-GM with VGG16 as the backbone and evaluated its performance on the WillowObject dataset. Besides, for four model fusion, the results(%) of MNIST+MLP (with fine-tuning) are given as follows :

Q2: Baseline for Multi-Marginal OT.

A2: We include Multi-Marginal OT as baselines in the visual matching experiments, where the cost tensor is defined as $C_{ijk} = C_{ij}+C'_{jk}+C''_{ki}$, with cost matrices $C, C', C''$. The Bregman iterative method [1] is employed for calculation. Following your advice, we utilize $\sum_k P_{ijk}$ as the probability for the transportation between $i$ and $j$, and similarly for $\sum_j P_{ijk}$ and $\sum_i P_{ijk}$. The experimental results are presented as follows:

The experimental setup for this experiment is the same as that described in Section A2. In terms of method comparison, Multi-Marginal OT has an exponential increase in spatial complexity ($O(N^2K)$) as the number of marginals increases, while our method has a linear increase ($O(N^2K)$). Note $N$ is the marginal dimension number (assuming the same) and $K$ is the number of marginal.

Q3: In Tab. 3, for CIFAR10 + VGG11, the finetuned accuracy is the same as the best pre-trained one, which raises concerns about efficiency.

A3: In Table 3, our OMT fusion method is compared to the OTfusion method, and it achieves better performance. However, it should be noted that not all fusion methods result in improved performance compared to the original models. It is normal for the fused model to have lower accuracy than the original model, especially in the case of multi-model fusion. The same accuracy between our method and the original one is actually a coincidence, as their actual prediction results are different.

Q4: Minors and typos

A4: Thank you for the reminder. We have made the corrections in the new PDF version. Thanks again.

[1] Benamou, Jean-David, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyré. "Iterative Bregman projections for regularized transportation problems." SIAM Journal on Scientific Computing 37, no. 2 (2015): A1111-A1138.

Dear Reviewer,

  Thank you for your valuable response. As the discussion deadline approaches, we would like to request your feedback on our response to address the concerns. We are also open to any further questions or suggestions that you may have.

Thanks for your time and attention. Your expertise and guidance are invaluable for our research.

Best regards,

The authors

Q1: I don’t find much novelty in the idea of minimizing the transportation costs between each pair of distributions and using the constraint $\prod_k \tilde{P}_k=I$. It’s also quite common to apply entropy regularization and transform the cycle-consistency into a regularizer.

A1: We have to feel sorry that you (and perhaps also other readers) think the constraint $\prod_k \tilde{P}_k=I$ for OMT not sufficiently novel, which is worth our further expaination. Specifically, we would like to clarify the following points: 1) Adding this constraint to OT is not an easy task for solving, and adopting the F-norm for relaxation might be the most straightforward computational approach. We have also experimented with alternative norms/divergences, all of which failed with the iterative Sinkhorn method. 2) Our main objective is to achieve consistency among multiple OT solutions, and the mentioned constraint is just one way of achieving this goal. Previous works have not explored this aspect. 3）Transportation consistency has strong implications. In addition to the connection with the Traveling Salesman Problem (TSP) mentioned in the paper, we believe it is also related to the Dynamic Formulation of OT, which describes the OT between two measures as a curve linking with fluid dynamics.

Q2: What about the runtime efficiency of OMT? It would be nice if the authors could show the convergence curve of the proposed algorithm.

A2: The time complexity of ROMT-Sinkhorn is $L$ times that of the pair-wise Sinkhorn, where $L$ represents the number of iterations. The convergence curve is presented in the new paper version in the Fig. 6 in Appendix, where the error is defined as the mean of the L2 norm between the couplings of two iterations. As for the runtime, the results are given as follows:

Q3: What about the stability of OMT? Given K sample sets/distributions, the method requires organizing the sets as a loop. Is it robust to the order of the sets? An analytic experiment should be added.

A3: About the order of sets, we first consider three measure case with $A$, $B$, and $C$, with a mapping order defined as $A\to B$, $B\to C$, and $C\to A$, represented by matching matrices $\mathbf{P}_1$, $\mathbf{P}_2$, and $\mathbf{P}_3$. Consistency requires that $\mathbf{P}_1\mathbf{P}_2\mathbf{P}_3=\mathbf{I}$. If we switch the order to $A\to C$, $C\to B$, and $B\to A$, with matching matrices $\mathbf{P}_3^T$, $\mathbf{P}_2^T$, and $\mathbf{P}_1^\top$, the consistency becomes $\mathbf{P}_3^\top\mathbf{P}_2^\top\mathbf{P}_1^\top=\mathbf{P}_1\mathbf{P}_2\mathbf{P}_3=\mathbf{I}$. Therefore, for the case of three measures ($K=3$), switching the order (of Fig. 5) does not affect the problem formulation. We test the experiments on Willow_3GM with IPCA-GM as backbone and the results are given as follows. Although the problems with and without switching the order are equivalent, the results may differ slightly due to initialization and other factors.

As for $K>3$, switching the order does indeed impact the formulation of the problem. However, note our directed cyclical structure is essentially a subgraph of pairwise structure. When the latter is satisfied, the former is also satisfied, allowing our method to still improve the matching performance. We show the experiments of switching the second and third set order as follows:

It can be observed that the results with and without switching the order are actually very close to each other.

Dear Reviewer,

Thank you for taking the time to review our paper. We greatly appreciate your insightful comments and suggestions, which have helped us improve the quality of our work. As the deadline for the discussion phase approaches, we have carefully considered your feedback and prepared a response to address the concerns raised. We kindly request your feedback on our response and welcome any further questions or suggestions you may have.

Once again, we would like to express our gratitude for your time and attention. Your expertise and guidance are invaluable to us in refining our research.

Best regards,

The authors