Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper introduces a semi-supervised OT formulation and its solutions and applied it to solving heterogeneous domain adaptation. The weak supervision comes from limited labeling of a set of key points in source and target domains. The authors constructed a key point-guided model by the doc product of the transport plan masked by the binary key point connection and a relation matrix between source and target. They then appended the model to the OT formulation as a weighted regularization term. Finally, they extended their model to partial OT problems. Experiments on Office-31 showed that the proposed model achieved better results overall than several existing methods.
strengths_and_weaknesses: + The formulations (11-13) are novel to the best of my knowledge.
+ Theorem 1 looks good. The authors solved their model on partial OT problems by adding dummy components to the formulation and later proved that solution to the original problem can be easily derived from the solution to the reformulated problem and the reformulated problem is solvable.

- The new formulation is quite expansive in memory (perhaps in time as well) because of additional pair-wise discrepancies and the authors didn't discuss that at all.
- The authors didn't discuss the difference between their key point-guided formulation and semi-supervised OT. I feel that $L_{kpg}$ can be directly incorporated into $L_{OT}$ by designing a more informative mask $M$ that directly encodes the "relation". It looks redundant to me that the authors had to design a binary mask but then treat it as a regularizer not a constraint. Perhaps it's a dead end but I feel in general the authors didn't clearly explain their motivation and ideas.
questions: ---
What's the difference between the idea of key point-guided OT and the idea of semi-surprised OT in OTDA by Courty et al. [9]?

---
Line 138: "If the paired key points (I,j) are matched, ... all mass of point $x_i$ must be transported to $y_j$ and $y_j$ can only receive the mass from $x_i$."

I miss the motivation of this idea. Since we're solving Kantorovich OT, how do we expect the connection between key points and non-key points are one-to-one?

---
Line 161: Why do we set it to $0.1 \times \max_{I,k}\{C_{I,k}^{s}\}$? Is $\tau$ tunable and thus cross-validated?

Where do $R_{k, i_u}^{s}$ and $G_{k,l}=d(R_k^s, R_l^t)$ come from? Why do we choose these discrepancies to construct the relation?

Plus, $G$ would take quite a lot of memory if $m$ and $n$ are large. What is the peak memory consumption during the experiments with Office-31?
limitations: No negative societal impact found. See above for limitations.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: Paper proposes to guide the optimal transport plan by imposing a priori some couplings between "keypoints" into the transport matrix. The relation to each keypoint is also used to define a "guiding" matrix that is considered as the cost matrix of the transport problem. Several variants are proposed, such as a GW- or a partial formulation of the problem. The experimental setup considers the Heteregeneous Domain Adaptation (HDA) scenario, in which it is assumed that some points (of all the classes) of the target distribution are labelled. 
strengths_and_weaknesses: Paper lies in a line of works that aims at constraining the OT problem to encode some extra information or to fasten the computation. Regarding the use of key points, it is quite common to use few anchor points to supervise some of the matching between points or distributions. From a computational point of view, the problem is rewritten by introducing a mask matrix and an algorithm is proposed to solve the problem. To my knowledge, introducing labeled key points to constrain the matching is original. In the context of HDA, experiments show that it is not enough to beat SotA methods. To improve the classification performances, a dedicated cost matrix is constructed. It is based on a function of the distance of each point to each key points within each domain. 
The methodology shares similarities with some OT variants, notably with hierarchical OT. In the latter, instead favoring matchings between some keypoints, a matching between subgroups (e.g. clusters) is sought. It also shares some similarities with TLB (« third lower bound » of Gromov-Wasserstein), in which each point of each domain is described as a set of distances to all the points of the same domain, and a « wasserstein of wasserstein » of these distances is computed. The originality and advantages of this « relation preservation » guiding matrix w.r.t. those alternatives is not discussed. No comparison of the performances is neither performed. This constitutes the main weakness of the paper as this guiding matrix seems to be the main ingredient to improve the performances. 
The experimental validation of the method is performed on a heterogeneous domain adaptation context. In this context, all the labels from the source distribution are known and only few of the target ones are provided. It is shown that adding only the keypoints to drive the matching is not enough to beat the SotA (10 point behind the best competitor) but that adding the guiding matrix improves the results. Additional experiment shows that performances increase when the number of keypoints. It is unclear if the competitors also use some labeled points to drive the learning, which makes the results with the proposed method and SotA difficult to compare. 


Strengths of the paper:
- the paper is really well written and easy to follow; figures illustrate clearly the proposed method.
- the methodology is sound and performs favorably in the considered HDA scenario.
- extensions with entropic regularization or partial OT is provided.

Weaknesses:
- insufficient comparison with similar OT variants such as hierarchical OT and TLB
- experimental setup that does not fit exactly the proposed method: while the hypothesis that we have access to labels of some of the target distribution makes sense, it is unclear how the method is sensitive to the choice of the keypoints within the source domain, or if it could be possible to use all the labeled information of this source domain.  
- it is unclear how the setting can be extended to deep method, where mini batches are used. 


Minor comments :
- «  Fuzzed OT » should read « fused OT »
- « Frank-Walfe » algorithm
- «  Offce 31 »

questions: Could you clarify 
- why one should use your method than hierarchical OT or TLB?
- could it be extended to the case where the number of keypoints in the source and target distributions are different?
limitations: n/a
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper utilizes annotated keypoints to tackle incorrect matchings of optimal transport models. First, the authors impose a mask-based constraint on the optimal transport problem to preserve the matching of keypoint pairs. Secondly, they propose to preserve the relation of each data to the keypoints by defining a new cost matrix. Their method, named KeyPoint-Guided model by ReLation preservation (KPG-RL), can be solved by the Sinkhorn’s algorithm and even supported in incomparable spaces. Furthermore, they extend KPG-RL to the partial OT setting. Finally, they verify the effectiveness of their proposal in the heterogeneous domain adaptation application, both close-set and open-set.
strengths_and_weaknesses: Though the mask-based constraint version of OT in this paper is not completely new (more details in the next section), the proposed solution, KPG-RL, in this paper is novel and interesting. In terms of the theoretical results, they are simply the extensions of previous works. Moving onto the experimental parts, KPG-RL shows a noticeable improvement over baseline methods in heterogeneous domain adaptation. In addition, the authors also conducted an ablation study to show the stability of their proposal for different choices of hyper-parameters. Overall, this paper is easy to follow with some good illustrations which are really helpful in explaining the concepts. Two major concerns include the lack of references to related works and experimental settings.
questions: I have the following questions:
1. **Related work**
* The OT problem in “Preservation of matching of keypoints in transport” is similar to the Masked Optimal Transport (Masked OT) [r1]. Please clarify the difference and contribution of this paper compared to the “previous” work.
* In the experimental part, a comparison with Masked OT and Masked GW [r1] can be conducted to illustrate the advantages of the proposed methods. For instance, KPG (w/dist) in Section 5.2 is a good candidate.  
[r1] Zhang, Jiying, et al. "Fine-tuning graph neural networks via graph topology induced optimal transport." arXiv preprint arXiv:2203.10453 (2022).

2. **Relation score.** What is the explanation/intuition/inspiration for defining the relation score in Equation 7? Because there are several forms that can satisfy the properties in L170-172. The authors should discuss the choice of the relation score in more detail because, in my opinion, it is one of the major contributions compared to Masked OT.

3. **Cost function.** An ablation study or an explanation for the choice of d, which is set to Jensen-Shannon in this paper, is recommended. 

4. **Reproducibility.** A lot of experimental settings are missing and there is no code for reproduction?
* The details of the kernel SVM are missing? 
* What is the value of $\alpha$ for each KPG-based method in Section 5.1?
* What is the value of hyper-parameters in Section 5.2?

5. **Experiments.** 
* *Sensitivity to $\epsilon$.* The range of $\epsilon$ in Appendix B.2 should be wider, e.g. $\epsilon = 0.001, 0.01, 0.1, 1, \ldots$.
* *Open-set HDA.* Does the set of common labels of the target domain contain or equal the label set of the source domain? If it is the case, it is reasonable to transport more than 1 - $\eta$-proportion (even all) of labeled source domain data. This could be a plausible explanation for the finding in L227-228 in Appendix B.3.
* *Sensitivity to hyper-parameters.* From Tables A-2, A-3, and especially A-5, it is difficult to conclude that KPG-RL is stable to different choices of hyper-parameters. 

**Minors**
* In Figure 2, the entry in row 3 and column 6 is 0, which is missing. 
* The line numbers in Checklist are outdated.

I am happy to increase my score if the above questions are adequately addressed.


limitations: The authors stated that the limitation of their method is in L184-185 but I think what they meant was L179-182. Other than that, one additional limitation of KPG-RL is the introduction of new hyper-parameters, which is the temperature $\tau$ and the dissimilarity function $d$. Together with $\epsilon$ in the entropic regularization, users have to tune a lot to find the best set of hyper-parameters.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper presents the KeyPoint-Guided model by ReLation preservation (KPG-RL), which allows to combine annotation information into many popular optimal transport (OT) models. The authors show the very competitive performance when integrating KPG-RL into the classical OT models, for the heterogeneous domain adaptation task.
strengths_and_weaknesses: The paper is well written and the authors have well illustrated the advantage and motivation of KPG-RL over the traditional GW and KP models.

However, I would say that the main contribution is mostly on the methodology, so more theoritical understand would be desirable. Apart from a few theoritical results which help validating the intuition and motivation, I think it is also necessary to convince that KPG-RL is a reliable divergence/metric (even though the empirical evidence suggests that it is). More precisely, given prior correct matching of keypoint pairs,

- In the setting of OT distance, where points lie on the same ground space, do we have that $L_{kpg} = 0$ (or $\text{KPG-RL-KP} = 0$) is equivalent to the equality of two reference measures $p$ and $q$?

- When KPG-RL is incorporated in the GW model (i.e. KPG-RL-GW), does it still preserve the isomorphism?, i.e. when the two graphs are isomorphic (in the usual sense of GW distance), do we have $\text{KPG-RL-GW} = 0$, and vice versa?

- Can we show that KPG-RL or any of its variations (GW and LP) defines a proper metric?

Moreover, while the usual GW model performs very poorly because it can not incorporate prior information, the fused GW model $[35]$ can and should be considered as competing method. For example, one can consider the fused GW model of the form: $\min_{\pi \in \Pi(p,q)}\alpha L_{gw}(\pi) + (1 - \alpha) L_w(\pi)$, where either $L_w(\pi) = \langle M, \pi \rangle$, or $L_w(\pi) = \langle M \odot G, \pi \rangle$.
questions: - I find the idea of introducing $G$ interesting and smart. So I am curious to see how would KPG-RL perform without $G$?, i.e. what if we only use $L_{kpg}(\pi) = \langle M, \pi \rangle_F$?

- Each entry in the matrix $G$ is the Jensen-Shannon (JS) divergence between two probability vectors. How does the choice of measure of similarity impact the performance of KPG-RL? Why JS divergence but not the KL divergence, or $L_2, L_1$ distances, or even Wasserstein distance (which is not computationally expensive in this case).

- Do the authors have the motivation to prefer the KPG-RL to the fused GW model above?

- What is the range of $\alpha$ in the equations $11$ and $12$? Is it $[0,1]$? Is it tuned during the training?

- The alignment in the Fig 4 is not very visible.

- In the experiment 5.2, how is the target data transformed for the GW model?

- In the Appendix, please provide more details on the barycentric mapping in $[48]$.
limitations: No, the authors do not discuss these points.
review_title: null

Meta-review: metareview: In this paper the authors propose a novel Optimal Transport problem that uses a small number of annotated  keypoints in both source and target domain to encode additional information and guide the OT plan in the problem. The authors propose a variant of the sinkhorn algorithm to solve the problem and show that it can be used to solve OT across different spaces with also an extension to Partial OT setting. Numerical experiments show the interest of the method on a difficult heterogeneous domain adaptation problem. 

The contribution was appreciated and all reviewers agree about the novelty of the method and the interest of the new model in practical applications. All experiments (in the paper, appendix and the new ones in reply) show that the method work better than existing approaches in semi-supervised HDA. Some concerns were raised by reviewers: missing discussion and citation of Masked OT and other approaches such as Fused GW but those were mostly addressed in the replies. The question of the choice of d was also well answered with new experiments.

The consensus between reviewers was that the replies were great and that the paper should be accepted an NeurIPS.  Nevertheless it was very clear from the discussion that the new results, discussion and positioning wrt the state of the art MUST be included in the final version and its supplementary.  The paper is also lacking a discussion about how to obtain keypoints pairs in practice (other than using existing labels) which is very important to ensure that the method can be used in practice.

confidence: Less certain
Decision: Accept