Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper deals with unbalanced Gromov-Wasserstein (UGW)  to compare un-registered metric measure spaces not necessarily endowed with a probability distribution. It proposes the relaxation of the  usual marginal constraints using quadratic  divergences leading to  a new  divergence that can be used to compare metric measure spaces.  By  adding an adapted entropic regularization to  the UGW formulation, an alternate optimization scheme based on Sinkhorn iterations  is designed. The  paper also  introduces another conic  formulation for Unbalanced GW (CGW) that  defines a distance invariant to isometries. The former is shown  to upper-bound CGW which optimization procedure is computationally  heavy. Both CGW and UGW  are illustrated on simulated. Furthermore application of  UGW to PU  learning shows  the effectiveness  of the  proposed UGW divergence. 
main_review: - Overall, the paper is well written and well  organized. The rationale behind the proposed method is justified and the  novelty brought  by  the approach is stated clearly. Theoretical  analysis of the proposed unbalanced  GW formulations is  provided  along  with the strengths and  limitations of UGW and CGW. Optimization approach to compute both GW-based divergences is also given. Empirical evaluations support the  effectiveness of the  proposed methods. Hence,  the paper brings a significant and interesting contribution to the field of unbalanced Gromov-Wasserstein distance.
- The main novelty  of the paper is  the definition of Unbalanced GW based $\varphi$-quadratic divergences that allow to express a 2-homogeneous relaxation of  the  marginal constraints of balanced GW. The paper  should deserve a few lines to provide better intuition on the quadratic divergences.
- GW  discrepancy is  known to   isometry-invariant. Is it the  case for UGW? As a general comment, the theoretical properties (beyond existence and definiteness) of UGW discrepancy measure should be more discussed and  made clearer. 
-  Lemma 1  plays  a central role in connecting UGW to the conic formulation of GW. Such as presented, that Lemma is hard to handle with several dense  notations. The paper should improve the introduction and the comments of that Lemma for a better readability.
- Interestingly the conic formulation  (CGW) defines a distance up  to isometries, a desirable property for some practical applications.  Also a strong result  of the paper is that the CGW distance is upper-bounded by the UGW discrepancy measure. The latter being computationally more favorable, it offers a theoretically justified  way to approximate CGW. The paper investigates empirically  the tightness of the relation CGW $\leq$ UGW. Nevertheless the empirical analysis has to be extended to isometry-invariance framework.
- The  weak points  of the paper are related to the optimization  procedure. Indeed,  the more general setting of UGW is narrowed to some specific divergences (KL in fact) or map function $\lambda$  limiting the applicability scope of UGW. I guess such assumptions are unavoidable to allow competitive optimization schemes. The second remark is the use  of entropic regularization in order to elaborate an efficient  bi-convex relaxation  to solve UGW. Depending on the choice of the regularization parameter, the upper-bound on CGW  may be less tight as expected. Can the authors discuss that  ? Also, is there any result on the convergence of regularized UGW towards UGW when $\epsilon  \rightarrow  0$?
- The paper informs that CGW has a high computation burden. Can  the paper provide  some insights on the computational complexity or memory requirement to compute CGW?
- The empirical evaluations show the good behavior and  the benefits of the proposed unbalanced GW divergences. Especially the obtained results are impressive for some experimental setups (see Table 1) and  they illustrate the benefit of the proposed marginal constraint relaxation using quadratic-divergences. Compare to PGW  how  one can explain the effect of applying such quadratic-divergences in-lieu of  the  classical ones?
- In the robustness to imbalanced classes, it  might be interesting to  plot the matching suggested by PGW. 

After feedback
-------------------
I thank the authors for providing detailed responses to the raised points. I highly appreciate their endeavour to clarify most concerns, especially the  isometry-invariance property of UGW, the computational burden of UGW in the general setting or the convergence convergence of regularized UGW towards UGW when $\epsilon  \rightarrow  0$.  I expect the revision will improve on these points and on the dense notations. Hence, I still have a positive view of the paper and I keep my rating.

limitations_and_societal_impact: Unless I was mistaken, the paper does not discuss the broader impact of the proposed approaches. On my view the work does not raise specific issues except the computation burdent inheritent to  GW.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes two unbalanced Gromov-Wasserstein formulations, namely Unbalanced Gromov-Wasserstein (UGW) divergence and Conic Gromov-Wasserstein (CGW) distance. Both of them are positive and definite. UGW has a scalable and GPU-friendly algorithm, which is applicable to large learning problems. CGW is a distance between mm-spaces up to isometry. It is theoretically and empirically shown that UGW can be used as a surrogate upper-bounding CGW. The authors then apply UGW to positive unlabeled learning with Caltech office dataset and achieve comparable or better performance than Chapel et al., 2020. 
main_review: This paper flows well. That being said, I would strongly recommend the authors to simplify the notations and terminologies in the main paper, especially in the introduction section. This can make the work more accessible for general readers. Besides, notations like $\iota$ and $\bot$ lack proper definition.

It is an interesting idea to use a scalable divergence to surrogate a real distance. 

Although according to the algorithm the computation of UHW should be efficient and scalable, it would be better if the computation time is also reported.

I am curious that whether the plots for $\rho=1, 10$ will have the same trend as $\rho=0.1$ is the shift is larger.

Line 228 the code at https://github.com/anonymous-conference-submission does not exist (by July 16. This is just a minor point because there is code in the supplement material).

limitations_and_societal_impact: This paper considers the formulation of unbalanced Gromov-Wasserstein distance, and does not contain any specific applications that may have negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper extends the Gromov-Wasserstein (GW) distance framework to two novel relaxations, the unbalanced GW (UGW) and the conic GW (CGW), which both address the question of comparing arbitrary positive measures on different metric spaces. The paper also proves that CGW is upper bounded by UGW, and introduces an algorithm to compute UGW based on Sinkhorn iterations. Numerical experiments are presented to illustrate the performance of the new algorithm. 
main_review: The paper presents new results of theoretical and practical importance for the two proposed GW formulations. The text is well-written and streamline. Technical writing is also to a high standard, with clean notation and coherent proofs.

The results are quite strong, combining ideas from unbalanced optimal transport (UOT), conic optimal transport (COT) and GW. By choosing a specific divergence in the new formulations, the paper partly retrieves the well-known equality connecting UOT and COT. The tightness result based on maximization of convex functional furthers the theoretical understanding of GW and elucidates how to extend the Sinkhorn algorithm to the GW setting.

Some specific comments/concerns I have are as follows:
1. After Theorem 2 it is claimed that the kernel $|d_X-d_Y|^2$ is negative semi-definite. According to the proof of Theorem 2 it is supposed to be negative semi-definite on the set of all signed measures due to the unbalanced setting. (Vayer, Titouan, et al. "Sliced Gromov-Wasserstein”) show that it is negative semi-definite on the set of all couplings, thus accounting for the balanced GW distance. Do the authors have a reference/proof for this general claim? This is crucial for the usefulness of Theorem 2 and to applications of the proposed methods.

2. The paper would benefit from more account of theoretical aspects of CGW. The reviewer understands that this may exceed the scope of the current submission, but more results on, e.g., induced topology on mm-spaces and its relation to GW, would be a nice addition. The authors should at least consider mentioning such research trajectories as future directions.

3. The entropic regularization is standard, but in UGW setting it remains unclear whether all the nice properties (convergence, global optimality, stopping criterion, etc.) still hold. For completeness, these should be checked, in addition to just showing the computational cost of each step. The dependence of the entropic relaxation on $\epsilon$ should also be examined, e.g., if it converges to the UGW as $\epsilon\to 0$. In general the 'doubly entropic' GW is worth studying even for the balanced case.

4. The paper repeatedly claims that the regular GW is recovered as $\rho\to\infty$, which should also be verified rigorously as it is unclear whether it’s the distance or the optimal coupling that’s recovered, and 'recovered' in what sense.

5. The main theorem claims UGW $\geq$ CGW, and the paper only illustrates numerically how tight this inequality can be. Is it possible to bound the gap and to give criterions when they are equal?
limitations_and_societal_impact: None.
review_title: null

Meta-review: A standard approach for defining distances between metric measure spaces is to use the Gromov-Wasserstein distance. However this formalism is limited to settings where the metric measure space has an underlying probability distribution. The main contributions of this paper are in formulating unbalanced analogues of the Gromov-Wasserstein distance that work with general positive measures. The specific formulations adapt ideas from unbalanced and conic optimal transport. Furthermore they use entropic regularization to design a Sinkhorn-style iterative algorithm and give experimental results on synthetic data and for problems in domain adaptation. The paper is well-written and has a nice mix of contributions. The only weakness is that they specialize to KL divergences which seems to limit the scope and applicability. Furthermore, in their setup working with more general divergences appears to be much more computationally challenging. 
Decision: Accept (Poster)