Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes an (approximation) algorithm to compute Gromov-Wasserstein (GW) distance, and called it Bregman Alternating Projected Gradient (BAPG) method. The author(s) claim that this is the first single-loop algorithm that has provable convergence guarantees. In particular, they provide an approximation bound for the distance between the fixed-point set of BAPG method and the critical point set of GW. Their analysis is based on the observation that the GW problem satisfies a so-called Luo-Tseng error bound condition, and the authors claim that they are the first to incorporate this idea in the GW literature. The paper complements their theoretical analysis with a few experiments comparing the performance of BAPG and other algorithms on graph alignment and partition tasks. They claim that BAPG achieves state-of-the-art results in terms of both wall-clock time and quality of solutions.


strength_and_weaknesses: Strengths:
-Technical details are easy to follow and verify
-BAPG involves only the matrix-vector or matrix-matrix operations at each iteration. Consequently, it has good properties such as being GPU implementation-friendly, robustness with respect to the step size, and low memory cost.
-The paper seems to be the first to incorporate the idea of Luo-Tseng error bound condition in the GW literature.
-While the idea of the algorithm is based on applying various known existing tricks and methods, the innovation lies in connecting them in novel ways. In particular, the authors decouple the Birkhoff polytope as simplex constraints for rows and columns separately, which is the key to enabling the projected gradient descent in an alternating fashion.

Weaknesses:
-One of the main claims of the paper is that their algorithm is provably single-loop, as compared to all-but-one algorithms in Table 1 which are classified as double-loop. However, we believe this single-loop vs double-loop terminology is neither standard in the literature nor explicitly defined in the paper. In particular, it wasn’t immediately clear why
 --being single-loop is an important performance measure (either in theory or in practice) that makes it preferable to double-loop; 
 --each algorithm in Table 1 is classified as double-loop or single-loop

-Author(s) claim that the infeasibility of the solution provided by their algorithm (BAPG) “does not matter at all” for graph alignment/partitioning, but provide little theoretical justification besides the indifference of these problems to the sharpness of the coupling. Moreover, there does not seem to be sufficient empirical evidence to support their claim. If the infeasibility does not matter at all, does that mean the graph tasks can be potentially solved using an easier formulation (i.e., one that does not require solving an GW problem)? This seems to suggest that the experiments chosen are unsuitable for the purpose of comparing the relative strength of GW algorithms. Also, the authors compared their graph alignment/partitioning performance with other GW-based algorithms. It will be much more meaningful to include comparisons with other non GW-based methods, especially those methods specialized in graph alignment/partitioning (e.g., Infomap for graph-partitioning), especially if the authors claim their method achieves state-of-the-art result
- Because the author(s) assume only that Dx and Dy are symmetric distance matrices, their algorithm could potentially be extended to a wider class of data/tasks, but they make little mention of this. Maybe include this in future work.
-Author(s) claim that their method is stable compared to existing methods, but provide no such notion of stability
-The accuracy of their algorithm in figure 2a seems a little suspicious

clarity,_quality,_novelty_and_reproducibility: -It is not apparent from the paper why being single-loop is important.
-There is no justification on why the two tasks chosen are suitable for the purpose of comparing the relative strength of GW algorithms
-For the two tasks chosen, they are compared only with other GW-based methods. The author(s) should also include performance of other non GW-based methods as benchmark, especially those methods specialized in graph alignment/partitioning (e.g., Infomap for graph-partitioning)
-It is not clear whether the proposed method works well for tasks beyond the two specific graph-based tasks. 
-Readers must refer to Xu 2018b to get a clear sense of how the noisy data is generated (not obvious from the contents of this paper)
-Naming conventions are inconsistent with standard literature. For example
   --The paper uses “adjacent matrices” instead of “adjacency matrices”; 
   --Using the step size rho as defined in the paper, asymptotic convergence is achieved when rho goes to infinity. Perhaps redefine step size to 1 / rho?
-The text contains several awkwardly phrased sentences and grammatical errors
   --“Arguably, one of the main drawbacks of the double-loop scheme is the computational burden, and not GPU friendly”. (pg. 3 )
   --“The performance of BAPG on the accuracy of mapping falls between {FW, BPG} and {eBPG, BPG-s} but the computational cost is sometimes comparable with BPG-S and FW, even faster in later graph alignment and partition tasks due to its GPU friendly property.” (pg. 6)
- There are some typos in the bibliography (e.g., Vayer Titouan -> Titouan Vayer, Lawrence Carin Duke -> Lawrence Carin)

summary_of_the_review: The algorithm proposed connects existing optimization ideas in a novel way, and the analysis seems technically sound. It is also expected to run faster than competing GW algorithms in practice. The author(s) claim that this the first single-loop GW algorithm that has provable convergence guarantees, though being single-loop was not a standard performance measure in the literature nor well explained in the paper. Finally, it wasn’t clear that the experiments chosen are suitable for the purpose of comparing the relative strength of GW algorithms.

Score increased after review.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This article proposes a new algorithm (BAPG) to estimate the GW distance between two discrete measured metric spaces $(X,d_X,\mu)$ and $(Y, d_Y, \nu)$. That is, it consider the following optimization problem  :
$$\min_{\pi} -Tr(D_X \pi D_Y \pi^T)$$
where $D_X = (d_X(x_i,x_j))_{ij}$ (and similarly for $D_Y$) and $\pi$ is constraint to have $\mu,\nu$ as marginals. 

The main idea is to consider a relaxation of the bilinear problem that naturally arise from this _quadratic_ optimization problem by minimizing instead 

$$F_\rho (\pi,w) = - Tr(D_X \pi D_Y w^T) + \rho D_h(\pi, w)$$

where $\pi$ is constrained to have $\mu$ as first marginal, $w$ is constrained to have $\nu$ as second marginal, $\rho$ is a regularization parameter and $D_h$ is the Bregman divergence associated to the convex map $h$ (in practice, the entropy, so that $D_h$ is the KL divergence, or the quadratic loss so that $D_h$ is the Euclidean distance). 

Akin to the usual derivations of the Sinkhorn algorithm as Iterative Bregman Projections [Benamou et al., 2015], authors propose an iterative algorithm (BAPG) to obtained minimizers of the proposed functional. 

Of crucial importance, authors show that : 
- [Theorem 3.6] Any accumulation point of the sequence $(\pi^k,w^k)_k$ must belong to a set of fixed-points for BAPG. 
- [Proposition 3.3] Any such fixed-point must satisfy $|\pi^\star - w^\star| = O(1/\rho)$, so that in particular in the regime $\rho \to \infty$, one expect to have $\pi^\star = w^\star$, and the middle-point $(\pi^\star + w^\star) / 2$ is close (as a $O(1/\rho)$) to an optimal solution of the original GW problem. 

Eventually, authors showcase their approach on a variety of numerical experiments, achieving good performances in terms of computational efficiency (running times) and utility (matching accuracy). 
strength_and_weaknesses: ## Strength

- Introduces an interesting algorithm to tackle an important problem in Computational OT and related fields. 
- Address both theoretical and numerical aspects of the problem. 
- Well-written paper. 

## Weaknesses 

- There are still few theoretical points that remain to be investigated/detailed. For instance: 
   - does Eq. (9) enables to get a convergence rate toward the fixed-point $(\pi^\star, w^\star)$? (if so, and provided a rounding scheme is valid there (see below), I think this would yield an overall approximation-rate for GW which may be of interest and could be compared with other benchmarks).
    - Why is it clear that a limit point $(\pi^\infty, w^\infty)$ exists? I guess this follow from some compactness arguments (i.e. the sequence shall be bounded thanks to $f$ being coercive), but this is not striking in the proof as far as I can tell.  
- [More a suggestion than a weakness] Experimental evaluation could be slightly extended as they suggest some interesting behavior. In particular, in the light of Fig 2. (b), it seems there is a (natural) tradeoff between convergence speed and the infeasibility error wrt the parameter $\rho$, so a possibly useful idea would be to start with a fairly high $\rho$ and progressively reduce it (as a sort of warm start). 
- I think some references are missing, in particular the work of _The unbalanced Gromov Wasserstein distance: Conic formulation and relaxation_ by Séjourné et al., 2021, which introduces a similar relaxation of the GW problem, and proves under specific condition that minimizers of $(\pi, w) \mapsto F(\pi,w)$ are the same as those of $\pi \mapsto F(\pi,\pi)$. 

## Other remarks/questions/suggestion
- If my understanding is correct, the output of BAPG is (approximately) a plan of the form $(\pi^\star + w^\star)/2$, which, if I am correct, does not exactly have the expected marginals $(\mu,\nu)$. Assuming this would be critical, could someone apply a `rounding` scheme in the vein of [Altschuler et al., 2018] ? 
- [suggestion for clarity] I think that in propositions statements, it may serve clarity to add quantifers "$\forall x,y$", or "$\forall \pi \in \mathbb{R}^{n \times m}$, and so on, to make clear on which parameter does the constant $M,\tau_1,\tau_2$ depend (or not). 
- [typo] In Remark 3.7, the ref to prop 3.4 should be 3.5 I think. 
- [typo] In proof of prop 3.1, $D_x$ should be $D_X$. 
clarity,_quality,_novelty_and_reproducibility: # Clarity

Well written work, quite clear overall. 

# Quality

From my understanding, this is a good paper that introduce a possibly impactful algorithm supported by relevant theory and appropriate experiments. 

# Novelty

To some extend, one could argue that BAPG is quite similar to standard techniques (in particular the Iterative Bregman Iterations interpretation of the Sinkhorn algorithm used in regular computational OT), but the proposed algorithm remains new to the best of my knowledge. 

# Reproducibility

Proofs have been (non-extensively) checked and no major flaw was identified (they are pretty well-written). Code to reproduce experiments has been provided with the paper (not tested) and it seems well organized at first sight.
summary_of_the_review: I think this is a good paper that introduce an interesting approach to address a difficult and important problem. It is supported by both theoretical and numerical claims.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a new method for computation of the Gromov-Wasserstein distance over graphs.  The GW distance is a measure distance between two distributions defined over different metric spaces. The authors give a list of existing algorithms for this problem which are either expensive computationally or do not have theoretical justification.  The present contribution is stated to be both, thus a breakthrough.  Computational results are provided for a set of different graph problems (alignment, partitioning, etc) which show the proposed scheme is indeed more efficient than existing methods.  The key idea is a surprising application of anold result (error bound condition of Luo & Tseng, 1992).
strength_and_weaknesses: 
Strength

o The paper is narrowly focused and laser sharp on what it aims to show

o GW distance on graphs is indeed a useful tool for analysis of large data

o There is a reasonable description of a highly specialized field for a non-expert to follow the main logic of the submission

Weakness

o The paper is highly specialized

o I'm not aware that anyone had previously complained that GW distance computation is a bottleneck is some key data science field
clarity,_quality,_novelty_and_reproducibility: 
Clarity and Quality.
The paper is well written and attempt is made to make it accessible to a more general audience than experts in numerical computation of graph distances.  The topic discussed is relevant to data science and by extension to ML community.  

Novelty.
If the main claim of this paper is correct -- the first theory-based single loop computation of GW distance -- then indeed the paper is quite novel and very useful.  

Reproducibility.
I do not know how to measure reproducibility.
summary_of_the_review: This is a very technical paper dealing with computation of the GW distance for graph data.  There is a strong theory component to the approach proposed and considerable computational work.  I did not see how the main theorem applied to the algorithm to be single loop but this could be due to my lack of expertise in this area.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this work, the authors propose an efficient single-loop iterative procedure to compute the Gromov Wasserstein (GW) distance between two sets. The GW distance can be formulated as a quadratic programming with a doubly-stochastic constraint. Many of the existing approaches for solving this optimization are double loop in nature, which involve solving another expensive sub-problem iteratively within a single iteration. In the proposed algorithm BAPG, a Bregman alternating projection step is performed with respect to the row and column stochastic constraints in each iteration. By alternatively projecting to polytopes with only row or column constraints, the projection attains a closed form update, thus attaining computational efficiency compared with other algorithms. For a theoretical understanding of the proposed algorithm BAPG, it has been shown that (1) BAPG converges to a fixed point asymptotically and (2) the distance between a fixed point of BAPG and the set of critical points of the original GW problem can be bounded, which is inversely proportional to the penalty parameter. The authors evaluate the algorithm on both synthetic and real datasets related to graph alignment and partition, and demonstrate the solution quality as well as the time efficiency.
strength_and_weaknesses: The main strength of this work is the splitting strategy for designing the algorithm and the analysis of the algorithm. The Luo-Tseng error bound is utilized to establish the distance between the fixed point of the algorithm and the critical set of the original GW problem. A few minor things in terms of technicality: (1) the algorithm itself is not stated with splitting, e.g., a single variable $\pi$ for the update; but the analysis uses two variables. Can the connection be explicitly stated in the main text? (2) Since the BAPG only returns a solution that is close to the critical set of the GW. Could it happen that some critical point has much worse value than the global min of the GW problem? (3) BAPG returns an infeasible solution in many cases. What if we want to return a feasible solution? 
clarity,_quality,_novelty_and_reproducibility: This paper is well-written and structured, with the motivation, as well as the comparison with the existing methods being clearly stated and referenced.
summary_of_the_review: This work improves the state-of-the-art for computing the GW distance by obtaining the first provable and efficient single loop algorithm. The analysis of the algorithm is based on the splitting strategy and the Luo-Tseng error bound. With the extensive experiments on both synthetic and real datasets, some of the theoretical claims are verified. It is seen that the proposed method attains good accuracy within less time for graph alignment and partition.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes a *convergent* single-loop algorithm for Gromov-Wasserstein in Graph Data. 

# Summary 
The GW problem is important and challenging (non-convex quadratic objective in space of n x n bistochastic matrices). 
This paper proposes a provably convergent (to local minimum) single loop approach, which could be of great practical interest, because single-loop algorithms are easier to tune (no need for inner loop's # of iterations, or tolerance). The non-asymptotic convergence theory that is provided is original, but some limitations:
- The authors mention at the end of their introduction, in Table 1 and elsewhere in the paper, that their algorithm does not always return a feasible solution for GW (e.g. a bistochastic matrix).
- The author mention in R.3.7 that the algorithm used in experiments is not provably convergent (theory supports a symmetric Bregman divergence, i.e. L2; their implementation uses KL). 
The authors show speed-ups as well as comparable or better performance (in accuracy) to other approaches in graph alignment /partitioning tasks.

# Process

The paper was supported by all reviewers during the rebuttal phase. After the rebuttal phase, AC and reviewers discussed shortcomings. This led to 2 reviewers (h6kQ and Jipi) lowering their grades. Because the system was locked, this is only reflected in messages to the authors ("Unfortunately have to lower my score", "Lower my score due to my misunderstanding"). Reviewer h6kQ communicated to me a new grade of 5. One reviewer participated in a discussion with the others but stopped participating. Another reviewer did not join the discussion after the rebuttal period. Some of the concerns were then discussed with the authors at a later date.

The AC and SAC now acknowledge that these discussions came late in the review process, and therefore did not let enough opportunity to the authors to effectively amend their paper, and address the late concerns.

# Summary of shortcomings discussed (with and without authors)

- The "provable" algorithm featured in {the title, the introduction, Table 1} is Eq.5 uses a sym. Bregman div. (a.k.a. L2). The algorithm used in experiments uses KL projections (Eq. 2). The authors argued during a discussion that these 2 algorithms were similar enough to conflate them, and use a single name ("BAPG"). I disagree. Projections onto the simplex are crucial, here they differ significantly.  While modifying the title could be easily fixed (e.g. "On the convergence of single-loop relaxations of GW for graph data"), significant parts of the paper need to be rewritten to lift that ambiguity.

- The feasibility issue has raised several questions from reviewers and AC. For instance, the only numerical evidence of (in)feasibility was Figure 2b, but it was reported by the authors to be wrong. To balance this, the authors argued that their contribution was to be understood as a relaxation of GW, tailored for graph data. Unfortunately, the paper is not written that way. The introduction mentions GW 13 times, provides shortcomings for existing GW approaches, and follows with *"To bridge the above theoretical-computational gap, we propose the first provable single-loop algorithm for the GW distance computation, which we call ..."*. Yet, a few sentences later, the authors write *"Nonetheless, the iterates generated by BAPG do not necessarily satisfy the Birkhoff polytope constraint"*. This contradiction appears in the paper: most comparisons focus on feasible solvers.

Comments on experiments:
- Hyperparameter search is mentioned in paper, but not in code, where they are are hardcoded. This is unreliable, given the amount of copy pasted code.
- No results for eBPG on "heat kernel" in Table 4. The argument that is mentioned (kernel sparse or dense) is unclear.
- BAPG (PyTorch) is compared to eBPG in POT (rather than reimplemented with PyTorch). The authors write "For eBPG, we use the official implementation in the PythonOTpackage, which supports running on GPU.". POT reads: "This function is backend-compatible and will work on arrays from all compatible backends. But the algorithm uses the C++ CPU backend which can lead to copy overhead on GPU arrays."
- In the "3-D space" of {accuracy /  speed / feasibility} the paper uses a partial view. A unified perspective is lacking. For instance, this could be corrected by adding the infeasibility of all solutions that are reported, along with time/accuracy.

# Decision after revision
After revision, SAC and PC agreed that above concerns are sufficiently adressed and that the paper is ready for acceptance.
Decision: Accept: poster