Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes a new approximating algorithm for Gromov-Wasserstein distance with $L_2$-norm loss that runs in a linear time regarding the number of samples. This algorithm is rooted in the combination of two low-rank techniques: one is the speed-up on cost matrix computation using low-rank factorization, and the other comes from the additional low-rank constraints on the set of feasible couplings. They also provide a guarantee on the convergence to a stationary point of the algorithm. Furthermore, they experimentally show that the proposed algorithm can accurately compute GW distance compared to previous techniques while being significantly faster.
main_review: --- Strength:

The paper is well-written and easy to follow. The complexity notes on each algorithm make it easy to see which parts to improve next.

--- Weakness:

(1) The contribution is quite limited. To achieve linear computation, the author only combines existing techniques to improve different parts of an existing algorithm. While \textbf{Quad Entropic-GW} is just a result of matrix computation speed-up under low-rank assumption, \textbf{Lin GW-LR} is a straightforward extension of \cite{scetbon2021lowrank}.

(2) In experiments, $\varepsilon = 0$ for \textbf{Lin GW-LR} and \textbf{GW-LR}, and $\varepsilon = 1 / \gamma$ for others. It means that the objectives they compute are different: while \textbf{Lin GW-LR} and \textbf{GW-LR} compute the optimal unregularized GW objective with an additional constraint, \textbf{Quad Entropic-GW} and \textbf{Entropic-GW} compute the optimal regularized GW objective. Is it fair to put them in comparison, especially when $\gamma$ is small (i.e, $\varepsilon = 1 / \gamma$ is large)?

(3) Do the authors have insights into the optimal solution of $(5)$? What effects does the low-rank constraint have on the optimal GW solution (and consequently, the optimal correspondence between two marginals)?

--- Typos:

(1) The notation $A^{\odot2}$, which I believe to be $A \circ A$, i.e, Hadamard product, is not defined.

(2) Line 176 : satisfies $\to$ satisfy, $\alpha$ sufficient small $\to$ $\alpha$ being sufficient small.
    
(3) Double citation ([14], [15]); ([18], [19]).

--- References:

The references with the complexity of approximating optimal transport are very lacking. The authors need to include several more related references. Here are a few examples: [1] is for complexity of Greenkhorn algorithm, [2] is for the complexity of the acceleration of Sinkhorn and Greenkhorn algorithms, [3] and [4] are for the optimal complexity of approximating OT.

[1] T. Lin, N. Ho, M. I. Jordan. On efficient optimal transport: an analysis of greedy and accelerated mirror descent algorithms. ICML, 2019.

[2] T. Lin, N. Ho, M. I. Jordan. On the efficiency of the Sinkhorn and Greenkhorn algorithms and their acceleration for optimal transport. Arxiv preprint Arxiv: 1906.01437, 2020.

[3] J. Blanchet, A. Jambulapati, C. Kent, and A. Sidford. Towards optimal running times for optimal transport. ArXiv preprint Arxiv: 1810.07717, 2018

[4] K. Quanrud. Approximating optimal transport with linear programs. In SOSA, pages 61–69,2019.
limitations_and_societal_impact: I do not see any foreseeable limitations and negative societal impact of this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In general, computing GW distance exactly is NP-hard. To compute nonconvex approximations of it generally take time $O(n^3)$-$O(n^4)$, depending on if the loss is separable. This work follows a recent trend in works that use low-rank approximations to cost matrices and couplings that have been used in the optimal transport literature to develop a method that has linear scaling in n, the number of points. Experiments demonstrate the efficiency and accuracy of the proposed method on some baseline experiments. 
main_review: Upsides: 

+ The method successfully transfers low-rank ideas to the Gromov-Wasserstein setting. 
+ The method shows how low-rank approximations make all operations efficient, including the outer norms and linearization of the GW objective in Section 5.
+ All of the steps and approximations of the methods are clearly laid out and discussed.
+ This work achieves the fastest approximation of GW distance to date in terms of scaling with $n$. 
+ Despite the nonconvexity, the method performs well on a suite of examples, illustrating some sort of benign nonconvexity in practice.

Downsides:

- A lot of the method seems to be a combination of past low-rank approximations for each part of the pipeline, and the novelty lies in applying them all as a whole. 
- The method is built on top of nonconvex approximations that are still not guaranteed in general. It is hard to get a sense of the failure regimes of GW from this work in terms of the nonconvexity, as well as the additional nonconvexity added by the low-rank approximations. While it is a bit easier to see how the distance/kernel matrix can be well-approximate by a low-rank matrix, it is not as easy to see how the low-rank coupling constraint performs in practice.
- It is easy to get lost in the whole methodology, and it would be helpful for the reader to have a roadmap of the method as well as the low-rank approximations in place.
- In the experiments of Figure 1, why doesn’t error decrease with increasing rank?
- What practical guidance is there for choosing the ranks in practice?

Additional questions:

*Could one choose different ranks for each low-rank approximation, i.e., different ranks for the distance matrices and the couplings?


limitations_and_societal_impact: Societal impacts are adequately discussed in the sense that it develops a general purpose tool, and GW distance has the potential for applications in places like NLP and single-cell genomics. Limitations due to the nonconvexity are discussed. However, failure regimes due to this do not appear in the work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors proposed a new variant of GW distance with linear computational complexity. The proposed LinearGW-LR leverages the low-rank property of the distance matrices and the low-rank assumption imposed on the target optimal transport matrix, which combines the advantage of the quadratic entropic GW and that of the low-rank Sinkhorn factorization in [32]. In the experiments, the authors show the feasibility of the proposed method in various tasks, especially in the cases of low-dimensional data.
main_review: Pros:
1. The paper is well-written and organized clearly. The notations and symbols are defined well. 

2. I like the detailed computational complexity analysis provided by the authors, which seldom appears in NeurIPS and is valuable for the community.

3. Detailed analytic experiments on synthetic data are shown, which verifies the feasibility of the proposed method.

Cons:
1. The overall algorithm looks like a straightforward modification of the method in [32], and the feasibility of the proposed method is based on three conditions: (1) low-dimensional data; (2) Euclidean distance matrix; (3) the optimal transport has a good low-rank approximation. Requiring all the three conditions jointly may limit the application of the method in practice.

2. The experiments on real-world data are insufficient. Is it possible to apply LinearGW-LR to more practical tasks, e.g., 2D/3D point cloud alignment? (which I think is a potential application suitable for the proposed method)

3. In my opinion, the main limitation of the proposed method is whether the target optimal transport can be approximated well by a low-rank matrix. It would be nice if the authors can study and visualize more optimal transports learned by the LinearGW-LR and quantitatively analyze the degradation caused by the low-rank approximation.

4. As mentioned in Line 74, some methods [6, 40] apply recursive mechanisms to accelerate the computation of GW. For example, the S-GWL in [40] actually learns low-rank OT explicitly as the authors did, while it is from the viewpoint of GW barycenter. I think it is necessary to consider [6, 40] as baselines.
limitations_and_societal_impact: I don't think the proposed work has any negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents mainly two contributions around the computability/approximation of the Gromov-Wasserstein distance (NP-hard in general). The first contribution is to consider cost matrices that admit a low-rank approximation. This allows roughly to go from a cubic problem in complexity to a quadratic problem. The second contribution is to propose to optimize the couplings of the Gromov problem under low-rank constraints. Putting end to end these contributions allow to compute an approximation of GW in $O(n)$ (with respect to the number of samples).

main_review: - Pros:
	- The article is didactic and very well written
	- The problem addressed is important and far from trivial: the proposed method is interesting
- Cons:
	- The experiments are restricted to small toys which is a shame given that the overall message of the article is that it allows to scale GW. 
	- The theoretical and algorithmic contributions of this article are quite incremental: there is, in my opinion, a significant overlap between this article and [1] (ref [32] in the original article) 
	- Some experimental points seem to me rather curious.

Overall the article is well written, pleasant to follow and didactic (for example Figure 1  well illustrates the low-rank approach). I thank the authors for that. The proposed approach is interesting and the fact that it allows to compute a GW in $O(n)$ is of a certain interest. Below are my various comments:

- On the factorization of the costs by low-rank matrices

The idea of exploiting the low rank properties of cost matrices to go from a cubic to a quadratic cost evaluation is interesting. The first contribution ("Exact factorization of cost matrices") is more of an "observation": it proves that when the pairwise distance matrices are low-rank (as for a squared euclidean distance) then one can implement the Gromov cost in $O(n^2)$ instead of the "naive" cost $O(n^{3})$. However this is not true in the general case and requires a strong prior on the cost matrices. Consequently the authors propose an algorithm to approximate these distances in product of low-rank matrices, based on [5,21] (refs of the article).

This point, according to me, is one of the most interesting points of the article, in terms of applicability. Because it allows to define a general "low-rank" solver for Gromov with a quadratic evaluation cost. I think that this part would really deserve more details. Indeed, as it is, it is directly borrowed from [1, paragraph General Case: Distance Matrix] for the Wasserstein context and is almost identically rewritten. It would have been very interesting, for example, to understand whether, in the Gromov setting, one can quantify the approximation of GW with the low rank cost matrices to that of GW with the initial cost matrices. 

Can we prove, for example, that the approximated GW is approximately the true GW plus an error term (which depends, for example, on the $d$ arrival dimension and the singular values of the distance matrices)? In practice, is this approximation reasonable? For example, can we have an idea of the trade-off between the $d$ dimension of arrival and the GW approximation?

- On the low-rank approach on couplings: 

I find this part interesting in itself but rather incremental compared to [1]. The analysis of the convergence of the Mirror Descent is almost identical to the analysis done in [1] and does not bring any additional theoretical insight: the only change is the smoothness constant of the loss, for the rest the proof is very similar. It even seems to suggest that it is as simple to approximate the problem when it is quadratic as when it is linear, which is quite surprising. I think this part requires more discussions regarding the the differences between [1] and GW-LR w.r.t. the algorithmic solution. Overall it is difficult to consider this part as a strong contribution in itlself because most of the arguments of [1] are extended in a direct way to GW.

- About the experiments:

The experiments presented in the article focus on answering the following question: for a given operation budget, does the (double)low-rank approach achieve a reasonable distance for Gromov compared to the entropy solution. In this sense, I find the different experiments proposed to be relevant: they show the interest of GW-LR. However, there are some points that I find a bit unclear and that seem to me rather curious. 

First of all, the authors choose $\varepsilon= 0$ in their experiment which is quite confusing because it implies that there is, in the end, no entropic regularization. They justify the fact that for any choice of $\varepsilon$ the loss obtained is "small" and that "the choice of $\varepsilon$ depends highly on $\gamma$". So this suggests that the entropy regularization is not really useful, which is surprising compared to the global message of the article, or that it is difficult to tune the hyperparameters. Moreover, it seems to me in this case rather unfair to compare with the entropic GW with a choice $\varepsilon = 1/\gamma$ and not to show also this setting for GW-LR. In practice, is it interesting to consider for example the $\gamma$ defined by Proposition 2 and to leave tune only the $\varepsilon$ ? 

I think it would also have been interesting to see how the method performs against non-regularized GW solvers such as a conditional gradient [2] (since the setting chosen in the article is $\varepsilon=0$)

More generally, the proposed method introduces many hyperparameters: $\varepsilon,\gamma,r,\alpha$ and, given that it already seems difficult to tune $\varepsilon,\gamma$, in view of the previous discussion, I am quite skeptical about the applicability for concrete and big data sets. Especially since the experiments focus on toy datasets and do not show any application of (Lin)-GW-LR to concrete application cases. It would have been interesting to use this approach for analysis on large graphs or shape-matching where GW is not applicable because of the size of the data. As it is, I find that the experiments are insufficient to show the usefulness of (Lin)-GW-LR on real data sets. 

In conclusion, the article tackles an important problem and offers interesting solutions. However, considering that the experiments are not really convincing and that the article is very similar to [1] I would tend to recommend its rejection.

- Small remark:
	- It is not really clear to me why the low-rank procedure on the cost matrices cannot be used for the Single Cell experiment. After calculating the shortest-path why can't we precalculate the low-rank matrices and compute GW-LR this way?
	- Typo: (row 64) "sped" -> "speed"

[1] Meyer Scetbon, Marco Cuturi, and Gabriel Peyré. Low-rank Sinkhorn factorization, ICML 2021.

[2] Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, Ievgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica J. Sutherland, Romain Tavenard, Alexander Tong, Titouan Vayer. POT: Python Optimal Transport. JMLR 2021. 


---- After Rebuttal ----

I would like to thank the authors for their response. I am increasing my score to 6. I think this article proposes an interesting contribution to a difficult problem. I acknowledge, in terms of novelty, that the regularization scheme based on [32] should be interpreted similarly as adding the entropic reg to the GW problem. Yet, I think it would be valuable to specialize a little bit more the low rank approach to the GW setting. Even if the authors think that this is a minor result I believe that comparing GW-LR to GW in term of objective function could be interesting.

Moreover, I still think that the experiments should be improved and that, as it is, they are quite limited to toys: the low-rank regularization is proved to be useful on real data only for the single-cell genomics data (where $n,m$ are quite small) where it is only compared to entropic GW. I believe that more ambitious experiments should be done on real datasets in order to show the advantages of low-rank regularization for GW (large graphs matching/classification, 3D mesh comparison). Finally, I think that the double regularization should be more discussed and applied (it is not really used in the experiments since $\epsilon = 0$ is the default setting). As it is I think the paper does not really show the interest of adding the entropic regularization over the low-rank constraints. 


limitations_and_societal_impact: Authors did not provide any potential negative societal impact of their work however, it is difficult for me to foresee these impacts as the work is mostly an optimization paper.
review_title: null

Meta-review: The focus of the submission is speeding up the computation of the Gromov-Wasserstein (GW) distance (capable of capturing the discrepancy of distributions defined on different spaces) using a variant of the Sinkhorn technique. The approach improves the original cubic complexity (w.r.t. the sample size) of GW computation to quadratic or to linear depending on the low-rank structure imposed.

Estimating discrepancy measures is an important problem of the area. Unfortunately, as assessed by the reviewers the work and the overall methodology closely follow the ideas and implementation pushed forward in [32] which significantly limits the novelty of the current paper. In addition, the submission could be further improved by a more thorough review of approximation schemes for the base optimal transport problem.

More work is required before publication.
Decision: Reject