Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposed a relaxed version of the Gromov-Wasserstein (GW) distance between two probability distributions on (graph) structured data. The main idea of new divergence is to relax the target distribution via an optimization setting. Based on the proposed divergence, the paper also introduced new formulations for existing problems of learning with graphs such as graph clustering (partitioning), graph dictionary learning, clustering of the graph, and graph completion. The experimental results for those applications on graph data have shown the efficiency of the proposed divergence.
main_review: The idea of relaxing the histogram of one distribution in GW distance looks intriguing. Relaxed GW divergence leads to less constrained optimization problems which help to improve the computational challenges of the original GW distance. The existing problems of learning with graphs such as graph clustering (partitioning), graph dictionary learning can be interestingly reformulated using the newly proposed divergence. However, the contribution of the paper can be improved in several aspects:
 - Is the proposed 'divergence' truly a divergence, i.e. srG(p,q)=0 iff p=q?

 - What is the difference between the GW barycenter with one measure and the srGW? As if we consider the GW barycenter of measure p with fixed supports, we will solve the same problem with computing srGW. One is to estimate the minimizer while the other compute the distance.

 - On page 4 (third paragraph), the paper states that "A first interesting property of srGW is that since h is optimized ..., its optimal value h* can be sparse". What is the insight for the statement that its optimal value h* can be sparse? Is this property is proved theoretically or experimentally besides the experiments with the sparse regularization? If it is not proved yet, what is the intuition that leads to the property?

 - Will algorithm 2 for graph dictionary learning converge to a local solution?

 -Regarding computational complexity in Table 3, what are the settings (e.g. GPU or CPU implementations) for proposed and baseline methods? The details should be clarified to make sure that comparable settings are used.
 

summary_of_the_review: In short, the proposed GW-based divergence looks interesting in terms of computational and applicable aspects. However, srGW may be considered as a special case of GW barycenter (for one measure) except that the authors provide further insights.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper the authors propose a modification of the Gromov-Wasserstein problem for matching given matrices $C$ and $\bar{C}$ with its respective histograms $h$ and $\bar{h}$, relaxing the restriction on $\bar{h}$. The problem is then given in an equivalent formulation, which is solved via Conditional Gradient. 
The authors propose applications with graphs, such as graph partitioning, clustering, and completion via Graph Dictionary Learning.

main_review: The paper is well written in general, although there are some typos, missing words, or inconsistencies in the citation format, especially from Section 4 onwards. 
Also, the descriptions of the objectives in each part of Section 4 for instance, or the datasets and specific tasks in Section 5, are not complete.

I liked the proposed formulation, and especially the equivalent problem (3).

Regarding the Dictionary Learning section in page 6.
 - How do you select m? (or for a particular application)
 - The resulting matrix $\bar{C}$ is not binary, right? 
 - in particular for the graph completion, but also valid in general: when learning the structure $\bar{C}$, you are assuming that the graphs follow a certain distribution, right? Even if this is more general (and not particular for the paper), this should be clearly stated.

Regarding the results in Table 1. It seems like for the symmetric datasets, the specialized graph partitioning methods perform much better. Are there similar methods that take into account the directive graphs as well?

I think that the paper would have been much better if the space used for some applications in Section 5, was used to better explain the rest of the paper, or show some other images/interpretations.

Minor comments:
 - in Proposition 1, there is a $srGW_2(h,C,\bar{C})$, which has the arguments in a different order than the others.
 - In the third paragraph of page 3, please add the dimension of matrix $\bar{D}$ (m by m), because at first I thought that it was a block diagonal, similar to an SBM probability matrix let's say. It's clear afterward from Fig 2 in any case.
Summary of the Review
 - please check the consistency in the references. Michael Bronstein is written in two different ways for instance.

summary_of_the_review: The paper presents a good idea, in the form of a relaxation of GW, and its equivalent formulation, and promising results in real datasets. The presentation of the paper can be improved.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper:  The paper proposes to apply a version of Gromov-Wasserstein divergence to graphs. In particular, they relax the weight constraint of the second graph  and try to find a minimizer of the Gromov-Wasserstein distance. They named it Semi-relaxed Gromov Wasserstein distance (srGW) and apply it to solve some problems in graphs, namely, graph partition, graph clustering and graph completion. The experiments were carried out on synthetic data and real dataset such as: Wikipedia hyper link network, Amazon product network etc. The results show comparable and better performance over other methods such as  GW and spectral GW.
main_review: The GW distance between two graphs is based on two quantities: the distance of the inner structure of graph and the weight of graph. This work proposes to relax the weight on one graph and keep the matrix  distance of that graph, and then try to find the GW-distance between two graphs when the constraint on weight of one side disappears. In fact, it try to match the structure of two graphs by ignoring the weights of one graph. 

The first question, that is easily to have, is that what is the role and the effect of the weight of the first graph in the srGW? Does it affect the final result or not? In all three proposed applications, at the end, they are only concerned about  the inner structure of a graph and do not bother the weight? 

Another concern is that by relaxing the condition on the weight, we are not very sure what we obtain when minimizing the srGW function. It could be a hybrid structure of two graphs or something else. In the  third picture of Figure 1, in my opinion,  the orange points of graph on  the left should be matched to some more dimmed points which are close to the orange points of the graph on the right, rather than a few orange points. The same could be said for the green points. It is quite opposite in the middle illustration of Figure 1, when the graph on the left tries to match its clusters to  clusters of the right.  Do the authors have an explanation about that rather than the asymmetric property.  In the paper, they stated that the interesting property of weight is the sparsity, but they should have a better theoretical result than Proposition 1, since it only deals with the case of zero  srGW. 

The author(s) apply the srGW to do graph partitioning and clustering. The reviewer finds that two tasks are similar. It is not clear for the reviewer how the author(s) choose the number of clusters, which is often important step in clustering method. For example, in the synthetic data, when we increase the value of $q$, we could obtain very different set of clusters, rather than small $q=3$ or $4$. In both graph partitioning and graph clustering, they use different measures to compare the performances between methods. Could we have both Adjusted Rand Index and AMI reported for both graph clustering and partitioning?

In the graph partition, could the authors compare the running time between methods? 
The reviewer believes that the complexity for srGW is of order $m^2n + n^2m$ and that of  Spectral GWL is only  $n^2\ln(n)$. Could author explain the better performance of the InforMap, FastGreedy and Louvain method over their method in the Amazon and Village datasets? 

In the graph completion, Figure 3, the reviewer did not find  the performance of all methods on MUTAG with $20\%$ imputed nodes?
summary_of_the_review: Positive: I find that the idea of applying the srGW divergence to the graph clustering is interesting.

Negative: There is a little understanding of the method (srGW),  other parts of the paper are entirely based on utilising  other existing works.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a semi-relaxed Gromov-Wasserstein (GW) dissimilarity for learning tasks on graphs. Here the "semi-relaxed" refers to removing one of the marginal constraints, with the practical effect that during GW graph matching, one is able to ignore some of the nodes in the source or target and thus obtain matchings that better respect the structure of the problem. What is quite interesting is that this simple relaxation immediately yields benefits in fundamental tasks such as graph partitioning, and the authors validate this observation with extensive experiments on graph datasets. The empirical results are strong, and show state-of-the-art performance compared to several recent baselines.
main_review: **Strengths:**

- The simple formulation of the srGW problem means that it fits nicely with prior GW literature, and can be implemented in existing codebases with minimal refactoring.

- The authors provide formulations of the standard srGW as well as entropy regularized and sparsity promoting variants, following the relevant literature. These formulations are not superfluous, as the authors demonstrate their use cases in the experiments (entropy regularization benefits graph partitioning, sparsity-promotion benefits clustering of graph datasets). I particularly liked Figure 2, as it helped me understand the strong performance of srGW in graph partitioning.

- srGW being a (possibly asymmetric) divergence is really quite interesting. Following up on Sturm's work, it seems then that the space of graphs equipped with srGW is a quasimetric space, which in turn leads to various questions about its metric structure. These theoretical questions are out of the scope of the current paper, but I would be curious to know if the authors had some potential use cases of this asymmetry in mind. E.g. with KL divergence, one often interprets KL(P||Q) to be the information loss in assuming a model Q of the data P. Can there be a similar interpretation of srGW in light of the single-atom dictionary learning method in Section 4?


**Neutral about:**

- On the note of the single-atom dictionary learning, it seems that this is a renaming of the Fréchet mean//GW barycenter problem. To their credit, the authors do not hide this fact, although it could be argued that casting this problem with a new name is a bit unnecessary. However, Sections 4.2 (graph completion theory) and 5.3 (empirical graph completion) do a good job of alleviating my concerns here, as they showcase a novel application of this technique.

**Weaknesses/points to clarify:**

- for Equation (3), could the authors clarify if there is any relation to the "Flexible Y-Marginals" formulation of ref. [A] below?

- In Section 3.1, I think it would help the reader if the authors clearly delineated between the metric measure space case and the graph case. Mémoli and Sturm proved their results for the mm space setting, and the theoretical results for the graph setting came a few years later. Alternatively, the authors could state up front that all their graphs are connected, which would mean that graph distances would always be well-defined.  

- In Section 3.2, I think the explanation of the CG method could be improved. $X$ in $\langle X,G\rangle$ seems to appear without introduction - it would be better to explain how we would like to project G onto the transport polytope, and that this corresponds to an OT problem with solution given by $X^*$. Also, I see that in the srGW setting, this problem becomes easier because one need not solve a full linear program, but the explanation here could be improved. Exactly what are the independent subproblems? Also, in "finding the minimum on the lines of G", I would replace "lines" by "rows" (as in Algo 1).

- Section 4.2, please add a few more lines about the use of the envelope theorem.

Refs:

[A] Schmitzer, Schnorr - Modelling Convex Shape Priors and Matching Based on the Gromov-Wasserstein Distance. JMIV 2013.
summary_of_the_review: The authors take the well-studied GW problem--which involves optimization over probability matrices satisfying row and column constraints--and consider a simple relaxation wherein the column constraints are removed. They also propose variations of the underlying optimization with respect to various regularizers. The usefulness of the core method and its variations are demonstrated on benchmark datasets and compared to relevant baselines, where the authors obtain SOTA performance. Additionally, the authors propose a novel application to graph completion and provide experiments in this regard. While it could be argued that the novelty scores should be between 2 and 3, I would lean toward 3 because I believe the authors have done their due diligence for each of their claims in the paper. Overall, I think this is a good paper, and I would favor acceptance.
review_title: null

Meta-review: This paper takes advantage of a well known fact in the OT literature: that relaxing either of the marginals of OT problems results in nearest neighbor assignments (as e.g. in k-means) or soft-assignments when using an entropic regularizer. The authors take advantage of this simple property (used e.g. in the first iterations of the word mover's distance) to speed up the inner iterations of the GW problem. As a result, theirs is a very simplified divergence that drops an important piece of info (the weights of the second measure) but which is illustrated on a few tasks dealing with graphs. Overall the paper has been appreciated by most reviewers, some criticizing the paper for its incremental nature but being overall pleased with the experimental validation.
Decision: Accept (Poster)