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

Authors: Liangliang Shi, Duorui Li, Jiale Hong, Junchi Yan
Primary area: other topics in machine learning (i.e., none of the above)
Keywords: Optimal Transport, Entropic Regularization, Cycle-Consistency, Matching, Travelling Salesman Problems

Abstract:
This paper generalizes the vanilla Optimal transport (OT) to the so-called Consistent Optimal Transport (COT) accepting more than two measures as input with transport consistency. We formulate the problem as minimizing the transport costs between each pair of measures and meanwhile requiring cycle-consistency among measures. We present both the Monge and Kantorovich formulations of COT and obtain the approximate solution with added entropic and consistency regularization, for which an iterative projection (RCOT-Sinkhorn) algorithm is devised to improve the Sinkhorn algorithm. We show the superiority on the task of visual multi-point matching, in which our COT solver directly utilizes the cosine distance between learned features of points obtained from off-the-shelf graph matching neural networks as the pairwise cost. We leverage the algorithm to learn multiple matching and the experiments show a great improvement without more feature training. Furthermore, based on COT, we propose a new TSP formulation called TSP-COT and also adopt regularization to relax the optimization and use the modified RCOT-Sinkhorn algorithm to get the probability matrix of TSP routing. Then post-process search method  is adopted to get the TSP routs and the experiments show the superiority of our method. The code will be available.

Decision: reject
Reviewer scores: 10, 6, 5, 3

Reviews and discussion:
<thread>
creation date:
1730412010909

thread_type:
official_review

<thread_object>
creator: reviewer_5wsl

<content>
summary:
This paper introduces a "cycle-consistent" optimal transport (COT) formulation : given a sequence of (say, discrete) measures $\alpha_1,\dots,\alpha_K$, the goal is to minimize 
$$ (P_1,\dots,P_k) \mapsto \sum_{k=1}^K \braket{C_k, P_k}$$
where $C_k$ is a cost matrix, $P_k$ should be a transportation plan between $\alpha_k$ and $\alpha_{k+1}$ (with the convention that $\alpha_{K+1} = \alpha_1$, and the $(P_k)_k$ are related through the _cycle-consistency constraint_ $\prod_{k=1}^K P_k = I$.

Because the cycle consistency constraint is non-linear, solving the COT problem is harder than solving standard OT problems, and thus the authors propose to resort on two layers of regularization: relaxing the constraint $\prod_{k=1}^K P_k = I$ using a divergence term (here, a Froebenius norm) and add an entropic regularization term (a common idea in computational OT for the last decade). They derive an mirror descent like scheme to minimize their regularized problem. 

Eventually, they observe that their formulation may be adapted to resemble the celebrated Traveler Salesman Problem (TSP).

strengths:
The formulation of the COT problem is somewhat intriguing and I do believe that it may be of interest in some situations. 

The relation with the TSP is interesting. I appreciate that the authors acknowledge the limitations of their approach and do not "oversell" it.

weaknesses:
## 1. Clarity

Overall, the paper lacks clarity in its writing. Key issues include the following:

**Unclear or Misleading Statements:** Numerous sentences are either unclear or misleading. For example, in the abstract, it’s stated that the COT problem considers each pair of measures, which implies that one must compute the optimal transportation cost between all pairs, i.e., between each $\alpha_i$ and $\alpha_j$, for $1 \leq i, j \leq K$. However, the paper actually focuses only on transportation between adjacent measures, $\alpha_k$ and $\alpha_{k+1}$.

**Inconsistent and Incorrect Notation:** Mathematical notation is inconsistently and sometimes incorrectly applied. For instance, the scalar product is denoted by < x, y >, which should be written as \langle x, y \rangle or using the braket package for $\braket{x, y}$. Additionally, notations should be standardized—sometimes measures contain $N$ points, while other times they contain $n$. Such issues, though minor in isolation, collectively impede readability.

**Formatting of Proofs:** The proofs in the appendix are poorly formatted, with equations split across multiple lines without necessity (for example, $d P_k$ at the end of Eq. (25) and in Eq. (26)). This formatting makes it difficult to review the proofs accurately.

**Placement of Algorithms:** The algorithms are all placed in the appendix but are referenced in the main paper as if they were essential. While it’s acceptable to include optional material in the appendix, the main text should be self-contained. Therefore, the algorithms should either be included in the main paper if they are necessary or clearly marked as optional if they’re not.

**Lack of Informative Content in Some Sentences:** Some sentences add little information. For instance, the introductory sentence, "Optimal transport (...) is a tool to learn the optimal transportation between the source and target probability measures," requires prior knowledge of what optimal transportation means, offering minimal insight. Additionally, comparisons with the Gromov--Wasserstein (GW) problem are not particularly useful here, as the GW problem is fundamentally different and is not introduced in this work. Relaxing the cycling constraint to a penalty seems natural and doesn’t require extensive justification.

## 2. Motivation of the method, comparison with multi-marginal OT, soundness, and mathematical grasp on the problem. 

The motivation for introducing the COT problem is limited, and the authors seem to lack critical distance from their work. For example:

**Motivation of the approach and Comparison with multi-marginal OT (MMOT):** It is regularly said that the contribution of this paper is to "generalize the OT problem to more than two marginals " (abstract, contributions section, etc.), but this is precisely what multi-marginal OT is about. The paper mentions multi-maginal OT and, while I understand the formal difference between the two approach (they are different problems, for sure), I fail to see the practical difference: when should one use MMOT or COT? The paper does not give a proper answer to this central question in my opinion. 

**Dependence on the Order of Measures:** The formulation of the COT problem depends on the order of $\alpha_1, \dots, \alpha_K$, yet this is not discussed. This could be crucial; for example, if a user has a set of measures from an experiment, how should they be ordered? Is the solution permutation-equivariant? (in which case I would agree that the ordering does not matter)

**Applicability of Birkhoff’s Theorem:** The authors assume discrete uniform measures with $N$ points each, but it’s unclear whether Birkhoff’s theorem applies here. Specifically, 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}$? Understanding this is essential for motivating the adaptation to the Traveling Salesman Problem (TSP), the behavior of entropic regularization as $\epsilon \to 0$, and related points.

**1D Case in Figure 2:** In Figure 2, the measures are depicted in 1D. In this case, it’s known that the standard OT plan is monotone, involving matching quantiles. Unless something is overlooked, this suggests that cycle-consistency is automatically satisfied without enforcement, making this experiment barely supporting the proposed approach. Could this be confirmed?

### Note

Despite my negative rating, I want to stress that I do like the proposed problem, I just feel that in its current state, the work is not ready for publication and I encourage the authors to revise it, go deeper into their understanding of the COT problem to make it a good candidate in the computational OT community.

questions:
See Section 2. in the Weaknesses block.

Note : rating updated after rebuttal.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730489173092

thread_type:
official_review

<thread_object>
creator: reviewer_3aue

<content>
summary:
This paper addresses the challenge of computing consistent optimal transport across multiple measures. The authors propose a cycle-consistent version of the Monge formulation, which is then relaxed to the Kantorovich formulation. Finally, it is further relaxed into an optimization problem regularized by cycle consistency and entropy, solved using an iterative Sinkhorn-like algorithm. The approach is demonstrated on several problems, including consistent point matching in computer vision and approximating solutions for the combinatorial traveling salesman problem.

strengths:
- The problem of consistent multiway optimal transport is compelling, and the authors effectively demonstrate its relevance through several potential applications. To my knowledge, both the formulation and approach are new.
- The authors present a comprehensive approach that includes Monge and Kantorovich formulations, entropic relaxation, and optimization algorithms.
- The connection to the Traveling Salesman Problem (TSP) is a valuable addition.
- The experimental results, particularly in the point matching experiment, underscore the motivation for computing cycle-consistent optimal transport.

weaknesses:
- The exposition could be improved. Parts of the paper are challenging to read, especially for readers without prior familiarity with the subject. See below for concrete examples.
- The authors define "COT's Monge Formulation," "COT's Kantorovich," and then introduce relaxations in Section 3.2. While these formulations appear similar to the traditional Monge-Kantorovich formulations with entropic relaxation, it's unclear if similar properties apply. For instance, does a solution to the Monge formulation in Eq. (6) exist? In what sense is the Kantorovich formulation in Eq. (8) a relaxation of the Monge formulation in Eq. (6)? Could you please provide, if possible, a more detailed discussion of these formulations and any conditions needed?
- The author's definition of cycle-consistency seems to be order-dependent, relying on the order of the probability measures \alpha_k. It only accounts for consecutive pairs.  Although this is briefly mentioned for applications in point matching, it is not discussed in more detail. Could you please include a discussion on the implications of this order-dependency, address how this might affect the results, or whether there are ways to mitigate this dependency?
- The connection to the Traveling Salesman Problem (TSP), while intriguing. Could you please explain in more detail how the COT formulation is used to represent the TSP problem, and what can be said about the approximate solution it achieves (e.g., in comparison to other ensemble-based approach)?
- It’s difficult to assess whether cycle-consistency is achieved exactly or approximately, in theory and in experiments, and at what rate. Could you please discuss in more detail?
- The ablation study in Section 4.3 is unclear. What are the "certain factors"? Could you please clarify the setup and conclusions of this study, including a more thorough discussion of the results and their implications?


Additional issues and comments:
- Abstract: Challenging to read.
- The first sentence of the introduction is incomplete.
- "introduce the entropic regularization transforming the hard cycle-consistency": the regularized version seems to seperately include an entropy term and a cycle-consistency term, so this statement may be inaccurate.
- "matrix-vector iterative method": unclear.
- Line 69: What is "MCTS"?
- "We generalize OT to the marginal consistent case": This is confusing since "multi-marginal" is later described as something related but different.
- "The Monge problem is exactly not easy to calculate and a popular improvement is the Kantorovich relaxation": please revise.
- "C is the cost matrix defined by the divergence": is it limited to this C?
- Line 138: What is "LAP"?
- "In contrast, our method employs a training-free approach that assumes consistency is satisfied on the test set, using this prior information to improve performance during inference." please clarify.
- Line 246: RCOT-PGD is mentioned but is not defined or explained (except in the Appendix).
- Line 248: What is "GW"?
- "RCOT-Sinkhorn achieves cycle-consistency results": Approximately or exactly cycle-consistent? Are there any guarantees?
- Figure 3: Somewhat unclear.
- "The setting of Hyper-parameter \delta'": What about the entropic regularization parameter \epsilon?
- Algorithms 1-5 are not included in the main text.

Typos:
- Line 47: "there calls"
- Line 52: "cost of three trasnsportation"
- Line 69: "we contribute"
- "is one of the simple but efficient methods"
- Eq (6): Summation should be over k.
- Line 345: "k<0" => "k<K"

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

============
post-rebuttal: Increasing my rating from 3->5
</content>
</thread_object>

</thread>
<thread>
creation date:
1730656810189

thread_type:
official_review

<thread_object>
creator: reviewer_ldtp

<content>
summary:
This paper extends the scope of Optimal Transport (OT) theory to cases involving more than two probability distributions, introducing a framework called Consistent Optimal Transport (COT). The authors explore transportation among three (or more) probability measures while enforcing cycle-consistency, which ensures that the transport plan respects consistency across the measures. Unlike the traditional OT problem, the COT's Kantorovich formulation becomes a nonlinear optimization problem due to these additional constraints. To address computational challenges, the authors propose a regularized version of COT using entropic and cycle-consistency regularization, which leads them to use the Sinkhorn algorithm for approximate solutions. As a by-product, this work offers a novel formulation for the Traveling Salesman Problem, offering insights into finding the shortest route that visits each city once and returns to the starting point.

strengths:
The paper is clear and well-written, with well-defined goals and contributions, including detailed algorithms. Additionally, the problem addressed is novel, and the authors highlight connections to other well-known problems, such as the Traveling Salesman Problem (TSP).

weaknesses:
The authors mention a connection to the multi-marginal OT problem, noting that both multi-marginal OT and COT involve multiple distributions. They state, "However, the multi-marginal OT primarily emphasizes learning the joint coupling among more than two distributions, whereas our focus is on learning the coupling between each pair of distributions and maintaining cycle-consistency constraints among these couplings". As a point of curiosity, are there any other non-trivial connections between the multi-marginal OT problem and COT beyond the fact that both involve multiple probability measures?

questions:
The authoirs are motived by the algorithms proposed for approximating the computation of GW. Please provide a few references in this regard.   

The authors include a section on the Numerical Convergence Analysis. Can the authors say anything about the analytic convengence of their methods? 

Minor details:

- Line 94: "The Monge problem is exactly not easy to calculate [...]" Add: "and an optimal T might not exists" (as is pointed out later in section 3.1)
- Line 188, eq (7): replace T_k by T_K, that is, capitalize the subindex 
- Use either "travelling" or "traveling" consistently through the paper, that is, pick one option.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730687747320

thread_type:
official_review

<thread_object>
creator: reviewer_8snv

<content>
summary:
The paper considers a generalized Optimal Transport (OT) problem that has pairwise transport between multiple distributions with an added constraint to ensure the formation of a closed cycle. The authors present an iterative Sinkhorn algorithm to solve the Kantorovich formulation of the above-mentioned problem.
I think the paper is well-written and well-motivated. In particular, the alternative formulation of the TSP is very interesting, especially when one takes into account the performance and computation time. The problem itself is well-motivated with multiple applications. The numerical results often outperform, or at least stay competitive, with the state-of-the-art in all the examples.

I think there is a strong case for the acceptance of this paper.

strengths:
- The quality of writing and presentation is high. Consequently, the results are presented in a clear and concise manner.
- While I do not think there is much originality/novelty (apart from the alternative TSP problem formulation) on the theoretical side, the improvements seen in the numerical simulations make a strong case for the significance of these results.

weaknesses:
Not weaknesses per se, but I would like to see the following information included:
- I would like to see how sensitive the results are with respect to the optimization parameters, such as $\delta$.
- Table 1 should have computation time. Line 471 says that running time is presented in Table 1, but I do not see it.

questions:
I don't have any questions in particular. However, I did notice a couple of typos (e.g., line 307 RCOT) and random capitalizations of words while reading, so I recommend that the authors perform thorough proofreading.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732701591462

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Any further questions?

comment:
Thanks again for your comments! Is there any remaining concerns about our paper? We are more thandelighted to address any concerns/questions you may have.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733209832400

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of Initial Reviews and Responses

comment:
We sincerely thank the reviewers for their time and valuable feedback. As the author-reviewer discussion wraps up, here's a summary of the reviews and our efforts during this phase:

| Reviewers' Concerns | Author Responses |
| --- | --- |
| How sensitive the results are with respect to the optimization parameters?    | We have conducted comprehensive sensitivity experiments for $\delta$ and $\epsilon$. The results are added to Table 6 in our paper, demonstrating the robustness of our method.                                                                                                                                                                                                                                                                                                                                                                                                                                      |
| Can the authors say anything about the analytic convengence of their 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.                                                                                                                                                                                                                                                                                                                                                                                                    |
| Does a solution to the Monge formulation in Eq. (6) exist?   | 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. |
| Does the order of the probability measures $\alpha_k$ impact the results?     | It is obvious that the order of measures has no impact when $K < 3$. For $K=3, 4$, as shown in Section 4.3, the results before and after switching the order of measures are almost the same, demonstrating that the order of measures has little impact on the results for $K=3, 4$. It is important to note that in both the datasets we utilized and the majority of practical applications within our research domain, the value of $K$ typically does not exceed $4$. This practical constraint implies that the scenarios we are primarily concerned with are well-covered by our existing experimental setup. |
| At what rate is the Cycle-consistency is achieved?  | 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.  |
| The setting of Hyper-parameter $\epsilon$. | 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.      |
| The connection between MMOT and COT.     | The solution in MMOT is 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), ...$. By the method newly added in Appendix H.2, MMOT can be transsformed to COT, which means that COT can leverage certain aspects of MMOT's framework while maintaining its own computational efficiency and applicability in the targeted problems.   |
| Are $(\mathbf{P_k})_{k=1}^K$ permutation matrices in Eq.(8)?                  | In our matching problem, the optimal $P_1,\dots,P_K$ are indeed permutation matrices. If the elements of $P_k$ were to be in the general range of $(0,1)$, the constraint $\prod P_k$ could not be satisfied. Only when $P_1,\dots,P_K$ are permutation matrices can this equality hold. The detailed proof has been added to Appendix A in our paper |
</content>
</thread_object>

</thread>


Metareview:
metareview:
The authors consider the optimal transport problem and extend it for multiple input distributions. Instead of formulating as the popular multi-marginal OT (MMOT), the authors consider a cycle of OT over a pair of adjacent distributions. The Reviewers have mixed opinions on the submission. The considered problem may be an interesting contribution to the computational OT computational. However, the Reviewers raised several concerns on the order of the cycle (or whether one can get invariant property on such order), the motivation of the proposed approach (why COT instead of MMOT), the hardness of the cycle-consistency constraint (only satisfying for the Monge problem) which leads to the question how to relax it appropriately to the Kantorovich problem as in standard OT. The Reviewers also raised concerns on the 1D illustration which may mislead the intuition into high-dimensional case where permutation is required for the cycle-consistency. Thus, we think a major revision and further development are required for the proposed approach to plug it into the picture of computational OT. The authors can consider the comments of the Reviewers to improve the submission.