Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper deals with  non-rigid point set registration via partial
distribution matching. The problem is formulated as
computing partial Wasserstein-1 (PW) discrepancy between distributions of
the reference point set and of the transformed source point set.  As a
main feature, the paper derives the Kantorovich–Rubinstein dual form
of the PW problem hence, allowing to lift the method to a large scale
setting. Overall the proposed method results in a min-max
problem (similar to Wassertein GAN) to learn the transformation function which minimizes the PW
discrepancy. Empirical evaluations complete the paper. 
main_review:  ***Strengths***
- The paper  considers point set registration problem consisting in
 in learning a non-rigid transformation that matches a transformed
source set to a reference one while avoiding noisy points or outliers that do have
correspondences in the other set.  To ensure the robustness of the
matching a partial distribution matching is sought using partial
optimal transport.  Specifically the partial Wasserstein-1 (PW), where only a portion of the probability mass is moved,  is
considered.

- Two equivalent formulations are proposed, the plain PW problem
  coined $\mathcal{L}_{M,m}$ with explicitly mass constraint and the
  
relaxed version $\mathcal{L}_{D,h}$. The main results of the paper
  are the derivation of the Kantorovitch-Rubinstein dual of both
  problems. The dual is a constrained optimization problem
  that involves a potential function defined as a neural network (NN). By
  relaxation of the Lipschitz constraint on the NN, the dual  is amenable to a
gradient framework and hence, to a large scale computation. 

- Learning of $\mathcal{T}$ by minimizing the PW discrepancy with a
coherence regularization  leads to a min-max problem similar to  the
one of the Wasserstein GAN. The overall optimization algorithm is
given.

***Weaknesses***
- As stated in the appendix, the Kantorovitch-Rubinstein (KR)  dual of  $\mathcal{L}_{D,h}$ straightforwardly
derives from (Lellmann et al., 2014; Schmitzer & Wirth, 2019). 
By convexity argument, there exist $h \geq 0$ such that problem  

$\mathcal{L}_{D,h}$ yields to a solution of problem

$\mathcal{L}_{M,m}.$

Hence, the dual Kantorovitch-Rubinstein  form of
$\mathcal{L}_{M,m}$ should follow. In that regard, the KR dual
derivations of both PW problems appear issued directly from the
aforementioned works. This renders the main theoretical results of the
paper rather incremental. 

- The relaxation  of the Lipschitz constraint on the NN implies that
  the obtained dual objective function (even if the dual problem is
  optimized to fully convergence) no longer represents the PW
  discrepancy but an approximation. Hence, the gradient computation is biased and results in the loss of theoretical guarantees on the
retrieved solution $\mathcal{T}$ of the point set registration problem (3).

- The paper lacks theoretical analysis of the convergence rate, the time
  complexity of the PW computation.  In the same
  vein, it lacks the comparison of the primal and dual solutions
  (computation time, precision  of the PW losses) or the empirical convergence illustration of Algorithm 1.

- It is not explicitly stated that Algorithm uses stochastic
  gradient to gain in scalability. Nevertheless the paper does not
 discuss  reference  [1] dedicated to unbalanced minibatch optimal
  transport (UOT) that can be a good alternative to the proposed method. [1]
  established theoretical properties of UOT in presence of outliers,
  in terms of gradient regularity hence the convergence property. How
  the proposed method connects to [1]?

- The transformation $\mathcal{T}$ defined as an affine-like
  deformation model is not fully explained nor justified. 

***Other comments***
- How the final point set registration is obtained ? Does it require computing
  the optimal transport map ? If so, how is it derived from the
  prima-dual equation?
- Report the means and the variances of the performances (MSE, computation time)
  over the runs. That helps the reading of the results.
- In Eq. (9), write $\mathcal{T}_\theta(y_j)$ rather than $y_j$.
- In EQ. (19) $\mathbf{G}$ should rather be $\mathbf{G}_\rho$.
- In section 5.2 the number of samples is sufficiently reasonable to
allow to compare primal solutions to dual ones in term of performances
and computation time. This might highlight the efficiency brought by
the use of the dual form and better illustrates the trade-off
efficiency vs precision. 
  
***Reference***

[1] Fatras, Kilian, et al. "Unbalanced minibatch optimal transport; applications to domain adaptation." International Conference on Machine Learning. PMLR, 2021.

**After rebuttal**

I read authors rebuttal. They address some of the  raised points by  the review (use or not of stochastic gradient to gain in scalability, confidence interval of reported performances, better justification of the transformation $\mathcal{T}$, gradient computation when relaxing the Lipschitz constraint...). 

The strong point of the paper is the  KR dual form derivation of $\mathcal{L}_{M,m}$ and this is not sufficiently highligthed in the paper. The authors should consider emphasizing more on that and better  highlight the novelty of the theoretical  KR dual form. During the discussion, the authors clarify how their approach connects to mini-batch regularized Unbalanced OT as promoted in Fatras et al. (2021) that solves the UOT problem in the primal.  This is also a good point. 

Overall the paper is  rather dense with almost 46 pages, the appendices  included. Nevertheless, provided aforementioned facts, I update my rating of the paper from 5 to 6. 
 

summary_of_the_review: The paper proposes a theoretical and methodological framework to
achieve robust  point set registration using scalable partial
Wasserstein based on the dual formulation. Their derivations somehow
derive from existing works. To be efficient, the  algorithm
relaxes the
Lipschitz constraint hence, the overall algorithmic scheme lacks
theoretical  guarantees on the matched distribution. Also the paper
lacks convergence, time complexity analysis of computing PW. Finally
connections to works related to minibatch unbalanced optimal
transport that can be competitors of the method are missing.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper deals with the problem of non-rigid point set registration, where a method for large scale partial distribution matching (PDM) problem is proposed by utilizing the partial Wasserstein-1 (PW) discrepancy.  The paper theoretically derive the Kantorovich–Rubinstein duality for the PW discrepancy, and show its gradient can be explicitly computed. Based on these theoretical results, the paper proposed a partial Wasserstein adversaria network (PWAN), which approximates the PW discrepancy by a neural network, and learns the transformation adversarially with the network. Experimental results on point set registration tasks such that the proposed PWAN is robust, scalable and performs more favorably than the state-of-the-art methods.
main_review: Strengths:

+ The paper theoretically derives the Kantorovich–Rubinstein duality for two types of the PW discrepancy, i.e., the distance-type and the mass-type discrepancy

+ The paper propose PWAN, for large scale PDM problem. 

+ Experimental results on the point set registration task prove that the proposed PWAN is robust, scalable and performs more favorably
than the state-of-the-art methods

Weaknesses:

-  The paper is rather dense, which may to some extent not well self-contained.

-  The paper only evaluated on the point set registration task, other related task such as 2D shape matching could be exploited.
summary_of_the_review: The theoretical contributions are justified with experimental evaluation on the point set registration task. The experimental evaluations could be more extensive, for example, other related tasks.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Paper proposes PWAN, a method that can be seen as an extension of WGAN in the presence of noise.
It uses the partial formulation of the wasserstein metric, allowing discarding points that are noise or outliers. It relies on the dual formulation of the problem to derive an efficient algorithm to learn a transformation that maps the target points toward the source points. Extensive experiments on toy datasets and 3 point clouds show that the method performs well, even in the presence of noise. 
main_review: The paper is interesting and deals with an important problem: how to deal with outliers when registering 3d shapes. 
The transformation $\mathcal{T}_\theta$ is found by simultaneously find a global transformation and optimizing a partial optimal transportation distance.
I have few concerns that should be clarified:
- eq. (2) is a reformulation of eq. (1). If there is a reason to have the two formulations, it should be better highlighted. Otherwise, it would add some clarity to avoid considering equivalent formuations.
- the dual of the partial optimal transport problem is described in [1]. If there is some novelty here, it should be emphasized. Otherwise, appropriate references should be cited.
- the choice of the parameters $m$/$h$ is the key of the success of the method. It would be interesting to add a discussion about it. What happens if their values are under/over estimated? Is there any thumb rule to choose their values?
- Section 5.2 is unclear. Is there any reason that the translated dataset should not match the outliers when t is large? What prevent PWAN to align dataset Y to outliers?


[1] Caffarelli, L. A., & McCann, R. J. (2010). Free boundaries in optimal transport and Monge-Ampere obstacle problems. Annals of mathematics, 673-730.
summary_of_the_review: An interesting paper deals with an important problem but lacks some appropriate references.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a method for registration of two point sets by formulating the problem as partial distribution matching problem. The authors utilise the partial Wasserstein (PW) discrepancy, and show how its gradient can be computed. They further propose a partial Wasserstein adversarial network that approximates the PW discrepancy. The authors evaluate the method against four method against two artificial datasets in which the method shows good results.
main_review: As to the strengths of the paper, the authors are able to make a novel contribution to a classic problem. It is pleasing that the point sets are modelled as discrete distributions without the need of making smoothing like GMM based methods for instance do. The theoretical part of deriving the KR duality for the two types of chosen discrepancies is clearly a strength of the paper even though it is a harder part of the paper to read.
 
As to the weaknesses, the paper is generally relatively easy to read, however the toughest part in math could be improved for clarity to help the reader with the intuition what is going on. Especially the part related to the adversarial learning and the approximation of PW discrepancy could be described better. The experimental evaluation is performed with rather simplistic datasets for which more realistic data set could be used to improve the presentation.
summary_of_the_review: In summary, the work can be seen as well founded paper with clear theoretic contribution equipped with a practical method based on neural formulation of the registration problem. Good results on the selected datasets, though an evaluation with a more complicated datasets would improve the presentation.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a partial Wasserstein adversarial network to register two non-rigid point clouds.

The major contribution is deriving a dual optimization objective to avoid the computation of a dense matching matrix.

Experiments on toy/synthetic datasets and one small-scale real-world face dataset show the effectiveness of the proposed method.
main_review: Strengths:

1) It's very nice to have a method to avoid the computation of dense matching matrix in an optimal transport framework;
2) The mathematical derivations are extensive and seem to be correct.

Weaknesses:

I would say the experiments are only validated on very small-scale synthetic and real-world datasets. I would expect the following experiments:

1) Experiments on the 3D Human dataset [Section 4.3, Non-rigid Point Set Registration with Global-Local Topology Preservation]

2) For synthetic experiments, it would be better to use the modelnet40 dataset, which contains many different shapes. Only using three shapes [bunny, armadillo and monkey] to train and validate methods has the risk of over-fitting.

3) For the limited real-world experiment on the face dataset [E.10], it would be better to give more details. For example, what's the overlapping ratio between pairwise point clouds? How does the proposed method perform under different overlapping ratios? 

4) It's unclear whether the proposed method would be open-sourced. Since this paper contains many equations, re-implementing it would be very hard.
summary_of_the_review: Overall, It's very nice to have a method to avoid the computation of dense matching matrix in an optimal transport framework. However, the limited experiments have not convinced me of its effectiveness on real-world datasets.
review_title: null

Meta-review: In this paper the authors proposes to use partial optimal transport to align point cloud in the presence of noise and partially observed data. To this end they express the partial Wasserstein Kantorovich-Rubinstein duality and use it to adapt the classical WGAN loss to partial OT. The optimal alignment between point clouds is then done by minimizing their proposed loss where the dual potential are modeled as deep neural network hence approximating the partial Wasserstein while being solved using mini-batches. Experiments show the interest of the method on a few well understood examples with ground truth from the Stanford repository. 

The paper had originally borderline scores with some reviewers concerned about the theoretical contribution. The authors did a very good reply that that greatly appreciated by the reviewers, the one with the lowest score deciding to increase it. The new numerical experiments on the 3D human dataset were also appreciated. The consensus during the discussion was that the paper is worth accepting but that the authors should take into account the comments form the reviewers and better explain their contribution on the KR duality.

For these reason the AC recommends to accept the paper but urges the authors to take into account the comments from the reviewers. In particular the authors should better highlight their theoretical contribution and explain the link and differences with unbalanced minibtach OT.
Decision: Accept (Poster)