Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary and overall recommendation:

This paper introduces two generalizations of the Gromov-Wasserstein distance to the case where the measures are unbalanced (i.e., not necessarily probability measures). While one of these is a proper distance, it is computationally infeasible. The other one, an upper bound relaxation, is not a proper distance but is much more computationally feasible. The main contribution of the paper is to prove some fundamental properties of these objects: positivity and definiteness. The paper proposes an algorithm for solving the upper-bound version, and shows proof-of-point experiments on very simple 2D settings. 

Despite some shortcomings in novelty, experimental evaluation, and presentation detailed below, I find the theoretical contribution of this paper to be just enough to carry it, so I'm (weakly) recommending acceptance. 

Strengths:

1. Albeit relying on ideas that are already quite popular in the OT literature (Gromov-Wasserstein distance, Unbalanced OT), this paper manages to weave them together in a very compelling way 
2. The paper has sound theoretical footing, and a makes a solid theoretical contribution.
3. The writing and exposition are mostly clear, intuitive and well developed

Weaknesses:
1. The flip side of strength (1) is that the novelty of this paper is arguably limited, considering it builds on known techinques, and is addressing a problem that has been tackled in at least two recent works (De Ponti & Mondino 2020, Chapel et al. 2020).
2. Some of the assumptions and results are not discussed in enough detail
3. The experimental section is limited to very simple settings, that either conisder measures on the same space (defeating the purpose of GW) (Fig 1,2), or do so for very simple synthetic data (Fig3). In particular, none of the motivating applications mentioned in the introduction (NLP, chemistry, graph matching). 

Other comments:
1. It would be useful if the paper discussed the assumptions that go into Prop 1 (superlinearity, compact level sets) in more detail. What families of $\phi$-divergences satisfy these?
2. I understand that Lemma 1 is a tool to draw a connection between the two approaches, but I find its introduction dry and abrupt. It would help to provide some discussion on the intuition on introducing such a perspective transform.
3. The presentation of the conic formulation needs fmore hand-holding. What's the motivation for this cumbersome the conic formulation? Are there other prior examples of such conic distances (even if not on mm spaces)?
4. I would have appreciated a discussion on the tightness of the bound of Theorem 1. Without this, the purported possibility to use one as a computationally feasible drop-in for the other is not fully supported. 
5. I don't think $\gamma_1$ and $\gamma_2$ in page 6 were formally defined anywhere
6. There is no comparison to other unbalanced methods (either OT or GW) except for one setting in Fig 3. I suspect most of these alternatives would produce similar results in Fig 1, so what is the competitive advantage of this method? If it is complexity/runtime (vs other unbalanced GW methods), then there should be either a formal complexity analysis, or a empirical runtime comparison. Without these, the paper feels incomplete. 

Questions:
1. What is meant by the last sentence in the first paragraph? This reads to be as if this paper claims to propose the first distance between the objects tackled in those works, which is certainly not the case for all of those which use GW or variations of the Wasserstein distance. 
2. Is there a reference for the quadratic $\phi$ divergences introduced in 2.1?
3. Do any of the experiments use the debiased UGW mentioned in page 7?

Minor comments and typos:
* pg 3 shed some lights
* missing "is" in first line of Prop 1
* pg 8 "close to be isometric"
review_title:  A nice theoretical contribution that extends the Gromov-Wasserstein distance to the unbalanced setting, with limited experimental validation

final_score: rating: 7: Good paper, accept
review_content: The authors consider the Gromov Wasserstein (GW) problem for metric measure spaces having different masses (i.e., Unbalanced GW). Similar to the ideas of unbalanced optimal transport (UOT), they proposed to use a quadratic divergence to relax the marginal constraints (instead of divergence as in UOT). When divergence is KL, the authors derive a GPU-friendly algorithm for the UGW  which relies on the unbalanced Sinkhorn algorithm. Additionally, the authors also propose a variant of UGW, namely Conic Gromov-Wasserstein (CGW) to address the different masses of metric measure spaces. The authors propose that CGW has nice properties (Theorem 1). However, there is no algorithm to solve the CGW yet.

+ It is easy to follow the paper. The authors provide rigorous details for the unbalanced GW.

+ For the UGW with divergence, it seems that it is not surprised for this idea by extending the ideas of entropic OT for unbalanced OT into entropic GW for unbalanced GW (e.g., using Sinkhorn iterations).

+ The proposed conic GW is theoretically interesting since it comes up with no algorithm yet. The authors also draw a connection between CGW and UGW.

+ It seems that the experiments are quite simple (with some toy examples). It seems better if the authors use UGW in some applications (e.g., some motivating applications for the unbalance case).

Some of my other concerns are as follows:
+ The authors propose to use quadratic divergence in UGW. Could the authors give more motivation/explanation about this approach, why not just divergence as in unbalanced OT (Although the GW is a quadratic assignment, the unbalanced problem for GW comes from the marginal constraints, why not just simply use the divergence between the marginal and measures)?
+ The authors proved nice properties for the proposed CGW and draw its connection to UGW. However, CGW has no algorithm yet. I wonder whether there exist some special instances of UGW (with some specific divergence, e.g., total variation or KL), one may have some interesting properties as in CGW? 

Overall, I lean on the positive side. (i) The ideas of UGW may not be a surprise (together with its algorithm). (ii) The proposed CGW has good properties for GW problems for metric measure spaces having different masses, however, there is no efficient algorithm for it yet as (a trade-off). (iii) It seems better in case the authors improve experiments (e.g., use UGW in some motivating applications for the unbalanced case).

review_title: The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation

final_score: rating: 5: Marginally below acceptance threshold
review_content: In the paper, the authors propose two versions of Gromov-Wasserstein distance when the weights of measures do not need to sum up to one. The first version, named Unbalanced Gromov-Wasserstein (UGW), is a direct application of unbalanced optimal transport (UOT) to the setting of Gromov-Wassertstein. The second version, named Conic Gromov-Wasserstein (CGW), is an extension of the conic formulation of UOT to the setting of Gromov-Wasserstein. The authors also show that CGW is a distance in the metric-measure spaces and is an lower bound of the UGW. Finally, the authors also provide some experiments with their proposed divergences.

In my opinion, the two proposed versions of Gromov-Wasserstein are quite interesting but lack novelty. They are simply extensions of the framework of UOT to the framework of Gromov-Wasserstein. Here are my other comments with the paper:

(1) The CGW is introduced as a lower bound of UGW; however, it is computationally expensive and practically out-of-reach as the authors admitted in the paper. Therefore, I am a bit confused with the proposal of CGW in the paper as it is not useful in practice. The theory of CGW also does not appear deep enough for me to appreciate the contribution. Unless the authors can provide some thoughts on how to practically implement CGW in the rebuttal, I feel that the inclusion of CGW is quite weak and does not add extra practical value to the paper.

(2) Going back to the UGW, it is a direct extension of the framework from UOT to that of Gromov-Wasserstein. The theories (Proposition 1,2 and Lemma 1) are fine and not hard to obtain given those from UOT. In the revision, I think the authors should give some examples of $\varphi$ satisfying the assumptions in Propositions 1 and 2 to help the readers to understand these results better. In Lemma 1, the authors should provide some intuition about $L_{c}(a, b)$ as it is a key term used later to define the conic discrepancies $\mathcal{D}$ in the definition of CGW.

(3) There is an interesting algorithmic perspective of using unbalanced version over the balanced version. For the setting of OT, the recent paper of [1] shows that solving the UOT (by Sinkhorn algorithm) when the divergence is KL has the complexity of $n^2/ \varepsilon$, which is near optimal, where $\varepsilon$ denotes the desired accuracy to approximate the UOT by the entropic UOT. On the other hand, the complexity of using Sinkhorn algorithm for solving the OT is at the order of $n^2/ \varepsilon^2$. Therefore, by considering the relaxation over constraints, solving UOT is in fact algorithmically favorable than that of solving OT. 

Going back to the UGW, the relaxation of constraints, in my opinion, may also help the convergence of algorithm (specifically Algorithm 1 in the paper) comparing to that of the GW (via Sinkhorn algorithm) though the rigorous theoretical analyses of these algorithms can be very tricky in general. However, I think the authors also can provide some numerical experiments to see whether this phenomenon holds true. 

(4) The literature of using UOT as a robust version of OT in practical applications of deep generative models and domain adaptation has been considered recently; see for example the paper [2]. The authors may consider adding this reference in the related works and contributions.


References:

[1] K Pham, K Le, N Ho, T Pham, H Bui. On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm. ICML, 2020

[2] Y. Balaji, R. Chellappa, S. Feizi. Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptation. NeurIPS, 2020


review_title: The paper is quite interesting but lacks novelty.

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper introduces a novel unbalanced Gromov-Wasserstein type problem. The Gromov-Wasserstein distance is very useful in practice for comparing probability distributions that do not lie in the same metric spaces. It has recently found several successful applications in ML for computational chemistry, graphs comparisons or NLP. Following previous works on unbalanced optimal transport (i.e. soft constraints over marginals enforcement of the coupling matrix), and the rationale that disposing of unbalanced versions of transport problems can alleviate in some ways presence of outliers or noise in the distributions, the authors propose two ‘unbalanced’ variants of the Gromov-Wasserstein (GW) problem, that allow comparison of metric spaces with arbitrary positive measures up to isometries (I.e. rigid transformations). 

The paper is fairly well written, original, and the related works is particularly complete. The theoretical part of the paper is sound, rigorous and well-motivated, and I learnt many things from it. The idea of using a quadratic \phi-divergence is neat and particularly clever. Yet, the paper requires, to some extent, very good notions in (unbalanced) optimal transport and probability, and I wonder, if some notations could have been eased a little bit (for instance, it seems that D_\phi is usually chosen as KL), but I guess the choice was made to be as general as possible.  While I did not check in details all the proofs in the appendix Section, I believe the work is solid. The algorithm parts is a little less satisfactory, as it amounts to optimize a upper bound  of the described problem, following existing work from [Mémoli11]. Though appealing, this upper bound is known to lose some properties of the original GW distance (for instance, two close points in the source can be matched to two distant points in the target if they share a very similar ‘distance profile’ or distance distributions wrt. the other samples). It seems that this effect is observable in Figure 2, where parts of a moon are ‘flipped’ in the matching. Combined with entropy and unbalanced formulation, I guess the final result can be very hard to interpret in a practical setting. 
Finally, the weakest part of the paper is the experimental Section. Only two toy examples are presented. While the method could have been used in many settings (graph classification, embedding matching in NLP or  even graph matching, for which many algorithms exist, etc.), it is very hard to conclude about the practical interest of the method. 
While I guess this is not a problem if one focuses on the original contribution of this novel unbalanced distance, it is more problematic, in the reviewers perception, for a machine learning venue such as ICLR.

For this reason, I will solely suggest a ‘weak accept’ decision, while I really believe the theoretical sections have a lot of merits. 

Minor comments.

- On page 1, it is said that « the paper defines for the first time a class of distances between the [aforementioned] objects ». This claim is a bit strong knowing that GW has already been used in several (cited) applications. I guess authors could be a little bit more precise on the meaning of this sentence;
- Page 4, just after definition 1, it seems (at least with my PDF reader), that there is a problem in the symbol used for \phi on the last line of the paragraph; 
- The claim that a cost of O(n^3) in time and O(n^2) in memory allows to scale to large problems is a bit strong. In practice, what is the maximum size of the problem that can be addressed in reasonable time with this method ? I expect that handling graphs that have more than 10k nodes for instance in very difficult. 
- The final rescaling of \gamma (line 8 of Algorithm 1), is a little bit difficult to understand from the alternating minimization point of view. 
- In the experimental Section, which algorithm is used to compute GW ? Also, I guess Figure 3 could present the original graphs (without scaling the dots), to gain a better understanding of the original problem


EDIT after rebuttal period
---------------------------------------
many thanks to the authors for taking into consideration my comments. I decided not to change my note because I still believe the paper lacks of a significative experimental Section.  
review_title: Nice theoretical results, poor experimental Section

Meta-review: This paper present novel formulations to address the problem of unbalanced Gromov. The Conic formulation is very interesting but stays theoretical until optimization algorithms are available. The Unbalanced Gromov is a nice extension of Gromov and comes with relatively efficient solvers. Some very limited numerical experiment show the proposed UGW used between 2D distributions (two moons) and graphs.

The paper had some mixed reviews with reviewers acknowledging the novelty of the approach (albeit an extension similar to unbalanced OT) and of the theoretical results. The detailed a very well written response to the reviewers comment has been appreciated. But all reviewers also noted a lack of numerical experiments outside of the very simple illustrations in the paper. This paper is a very nice contribution to the theory of optimal transport but fails at illustrating its relevance to the ML community.  Despite acknowledging the theoretical contributions of the paper, the  AC recommends a reject but strongly encourages the authors to complete the experimental section with some ML applications or at least proof of concepts (graph classification, domain adaptation, ...). 

Decision: Reject