COT: Consistent Optimal Transport with Applications to Visual Matching and Travelling Salesman Problems

Q1: What is the practical difference between MMOT and COT?

A1: MMOT is a generalized form that indeed presents difficulties when it comes to solving specific problems. When attempting to solve a particular problem using MMOT, one is required to define a specific cost, as illustrated in Remark 10.2 (P160) of "Computational Optimal Transport" by G Peyré and M Cuturi. In contrast, for COT, the cost is defined between adjacent pairs of distributions and does not necessitate an additional, separate definition. This key distinction in cost definition between MMOT and COT has important practical implications. In situations where the problem at hand has a natural pairwise cost structure that can be directly exploited, COT provides a more straightforward and applicable solution. For example, in visual multi-point matching tasks, COT can directly utilize the cosine distance between learned features of points obtained from off-the-shelf graph matching neural networks as the pairwise cost, without the need for complex cost redefinition. On the other hand, MMOT might be considered in scenarios where a more generalized and elaborate cost structure needs to be incorporated, although this comes with the added complexity of formulating the appropriate cost function. However, in many practical applications, the pairwise cost nature of COT makes it a more convenient choice as it aligns well with the inherent relationships between data points or distributions in the problem domain.

Q2: Does the order of measures impact results?

A2: 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 have showed the experiments of switching the second and third set order in the ablation study. It can be observed that the results with and without switching the order are actually very close to each other in Table 4.

Q3: Is it generally true that the optimal $P_1, \dots, P_K$ are permutation matrices if we only assume that $P_k \in U(a_k, a_{k+1})$ in Eq. (8) rather than $P_k \in \{0,1\}^{N \times N}$?

A3: In the context of our matching problem, which is a special case of the transportation problem, we can use continuous values in $[0, 1]$ instead of the discrete values ${0, 1}$. In fact, in this problem, the solutions in both the discrete and continuous cases are equivalent.

Q4: In 1D case, cycle-consistency is automatically satisfied without enforcement, making the experiment in Figure 2 barely supporting the proposed approach.

A4: We must admit that, as you correctly pointed out, in the 1D case, the standard OT plan is monotone and cycle-consistency is automatically satisfied without explicit enforcement. We apologize for not clarifying this in the paper. However, in our actual computations, we consider arbitrary matrices and solutions under entropy regularization. The purpose of presenting this example in Figure 2 is to illustrate the solution and the satisfaction of consistency in a more general context that is relevant to our overall approach. We understand that this may have caused some confusion.

Q1: Does a solution to the Monge formulation in Eq. (6) exist?

A1: For the question about the existence of a solution to the Monge formulation in Eq.(6), a solution does exist. We can consider a feasible solution as follows: assume that $\{t_1, t_2, \dots, t_{K-1}\}$ are the solutions of the original MMOT problem. Then, given $x\in \mathcal{X_1}$ and $y=T_{K-1}T_{K-2}\cdots T_1(x)$, we can set $x=T_K(y)$. In this way, it satisfies the conditions and thus is a feasible solution.

Q2: Does the order of the probability measures $\alpha_k$ impact the results?

A2: 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 have showed the experiments of switching the second and third set order in the ablation study. It can be observed that the results with and without switching the order are actually very close to each other in Table 4.

Q3: At what rate is the Cycle-consistency achieved?

A3: In theory, the cycle-consistency should be exactly satisfied. However, after applying relaxation techniques in our approach, it is approximately achieved. The Consistent Rate (CR) metric, which we have defined in Eq.(18) , provides insights into how closely our solutions approximate the ideal cycle-consistency.

Q4: What are the "certain factors" in the ablation study in Section 4.3 ?

A4: We have now added a clear explanation of the "certain factors" in the updated paper. The factors we investigated mainly include switching the order of point sets in the matching process and applying Hungarian algorithm to P in Eq.16.

Q5: The setting of Hyper-parameter $\epsilon'$.

A5: We did not initially mention the setting of $\epsilon$ in the original paper. However, it can be tuned in a similar manner as $\delta'$. Specifically, one can replace $\lambda$ with $\epsilon$ in Algorithm 5 to perform the tuning process. We have now added the relevant description in the latest version of the paper to clarify this point. This way, readers can understand that the approach for adjusting $\epsilon$ is analogous to that of $\delta'$, providing a more comprehensive understanding of the hyperparameter settings in our methodology.

Q6: What is the connection to multimarginal OT? The authors mention briefly in Section 2 but do not elaborate.

A6: Both MMOT and COT involve k margins, which is a common aspect. However, there are notable differences. In MMOT, the cost requires a specialized design and is not straightforward to represent as a distance. In contrast, COT typically defines the cost as the pairwise distance matrix. Additionally, the solution in MMOT is a high-dimensional coupling in the form of an $(n_1, n_2, \cdots, n_K)$ tensor, while COT's solution is a collection of couplings between pairs with the shape of $(n_1, n_2), (n_2, n_3), ...$.

Q7: Some other issues.

A7: Regarding the issues you raised, we have made targeted revisions. We have modified the expressions of some sentences and added necessary explanations for some professional terms or abbreviations.

Thanks for reading our works and response. Shall we ask that do you have further concerns and we do hope we could resolve your potential questions!

Q1: How sensitive the results are with respect to the optimization parameters?

A1: Thank you for highlighting the importance of analyzing the sensitivity of results to optimization parameters. We have conducted comprehensive sensitivity experiments for $\delta$ and $\epsilon$. The results, presented in as follows, demonstrate the robustness of our method.

Q2: Some tyos and random capitalizations of words.

A2: Thank you for your careful review. We have gone through the paper and corrected all such errors.

Q1: Are there any other non-trivial connections between the multi-marginal OT problem and COT beyond the fact that both involve multiple probability measures?

A1: Both MMOT and COT involve K margins, which is a common aspect. However, there are notable differences. In MMOT, the cost requires a specialized design and is not straightforward to represent as a distance. In contrast, COT typically defines the cost as the pairwise distance matrix. Additionally, the solution in MMOT is a high-dimensional coupling in the form of a tensor with the shape of $(n_1, n_2, \cdots, n_K)$, while COT's solution is a collection of couplings between pairs with the shape of $(n_1, n_2), (n_2, n_3), ...$.

Q2: Please provide a few references for the computation of GW.

A2: Thank you for your suggestion. As you recommended, we have added appropriate reference in the updated version. This reference will enhance the comprehensiveness and credibility of our research, enabling readers to have a more in-depth understanding of the computation of GW and its connections to our work.

Q3: Can the authors say anything about the analytic convengence of their methods?

A3: Thank you for your question regarding the analytic convergence of our methods. Our algorithm is equivalent to the projection of the gradient descent algorithm. Please refer to the newly added reference in Section 4.2, where the convergence proof related to the our algorithm is discussed. This reference provides a comprehensive analysis that is applicable to our method and helps establish the analytic convergence properties. We believe this will address your concerns and further clarify the theoretical foundation of our approach.

Q4: Some Minor details.

A4: Thank you for your careful review. We have gone through the paper and corrected all such errors.

Thanks for reading our works and response. Shall we ask that do you have further concerns and we do hope we could resolve your potential questions!