Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper introduces a robust approach for dictionary learning on graphs. The method is based on a robust version of the Gromov-Wasserstein discrepancy, which involves a minimax optimization problem that is neither convex/concave. The authors proved several properties of the RGWD. The authors demonstrate the efficacy of their approach via experiments and simulations. 
strength_and_weaknesses: - Strengths: 

- The approach is well motivated and natural. The drawbacks (lack for robustness under noise) of the current GWD approach is stated, and then a solution that address the robustness drawback is proposed. 

- The paper is well-written. The background material on optimal transport and graph dictionary learning is presented clearly. 

- The proposed method is a very natural extension of GWD. 

- Some nice (although pretty basic) properties of the RGWD, such as triangle inequality is posed. 

- In experiments and simulations, RGWD appears to perform quite substantially better than competitors. 

- Weaknesses: 

- The comparison in the simulations is limited. In the simulations, the authors used RGWD with a wide variety of epsilon parameters and compare all of them against only GDL. While the performance of RGWD is good/better than GWD across a variety of epsilon choices, comparison against only one alternative (on a simulated graph clustering task, of which many alternatives should be available) does not convince the reader strongly enough that the RGWD is truly superior to a broad set of competitors. I highly suggest that the authors compare the performance of RGWD against a few other graph clustering methods to make their simulations more convincing. 

- With any distance/divergence or other tool for graph comparison, certain specific basic properties should be shown. Of particular importance is whether the divergence/distance etc is invariant to the representation of the graph. For example, If I am comparing graph G_s and G_t, would the resulting number/distance be invariant to vertex label permutations? I.e. distance(G_s, G_t) = distance(permutation1(G_s), permutation2(G_t))? I think this property is very important since it makes sures that the distance is comparing graph structure, not some arbitrary label/representation. As of now it is not clear whether the RGWD satisfies this property. If the property is satisfied, then it would be great to state it explicitly. If it is not satisfied, then at least the authors could mention/discuss it. 

Minor Points: 

There are some related work/references on comparing graphs of different sizes/number of nodes with no alignments that I think the authors could cite: 

Network Portrait Divergence: 
An information-theoretic, all-scales approach to comparing networks. James Bagrow and Erik Bollt

Embedded Laplacian Distance: 
Multiscale Graph Comparison via the Embedded Laplacian Distance. Edric Tam, David Dunson

Graph Diffusion Wasserstein Distance: 
Barbe et. al. Graph Diffusion Wasserstein Distances. ECML-PKDD 2020
clarity,_quality,_novelty_and_reproducibility: The paper is clearly written and presented. 

The idea appears to be novel and original, and tackles a known limitation of a very new/state of the art method. 


summary_of_the_review: I think overall the paper is well written, the approach is natural, and the contributions are sufficiently novel/original. However, there remains some areas for improvement that I think if addressed, would make the paper much stronger. In particular, if they could compare against more alternatives in their simulations, add the very related references that are suggested, and comment on whether their method satisfies the permutation invariance property which is very important and natural.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a robust graph dictionary learning algorithm based on a metric named robust Gromov-Wasserstein discrepancy (RGWD).  With the proposed method,  a set of atoms can be learned from noisy graph data. Experiments are conducted on synthetic datasets as well as public real-world datasets to evaluate the proposed method.
strength_and_weaknesses: Strengths
Theoretical analysis about the properties of the proposed RGWD is provided.

Weakness
1. Lacking the motivation of using the projected gradient to update the transport plan.
2. Insufficient experimental evaluation.

Detailed comments:
1. What’s the advantage of using the projected gradient to update the transport plan.? Can it be solved by employing the Sinkhorn algorithm? More theoretical or experimental evidence needs to be provided to compare their efficiency/convergence and results.
2. Three datasets named MUTAG, IMDB-B, and IMDB-M are used to evaluate the proposed method with the metric of ARI score. However, as these datasets are usually used for graph classification, it’s suggested to provide the classification performance on these datasets as well.
3. More graph learning methods could also be compared, e.g. graph kernel-based methods, other than only graph dictionary learning. Specifically, a deep graph dictionary learning method is proposed in [a] recently. It is suggested to compare this work by discussing the advantages and disadvantages, as well as comparing the performance.
[a] T. Zhang, et al. Deep Wasserstein Graph Discriminant Learning for Graph Classification. AAAI 2021. 

clarity,_quality,_novelty_and_reproducibility: This paper is well-written and easy to read. It improves a previous work by adding the perturbation to the Gromov-Wasserstein metric to make it robust to noises, which is somehow marginally significant or novel. The code is provided in the supplementary material.
summary_of_the_review: The motivation of the way for optimizing the transport plan should be made clear, and more experimental results should be provided with a comprehensive comparison.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies the problem of dictionary learning for graphs. It proposed an improved graph dictionary learning algorithm based on a robust Gromov-Wasserstein discrepancy (RGWD). It also provided some theoretical results and numerical results. 
strength_and_weaknesses: Strengths:
1. Graph-level dictionary learning is a challenging problem and hasn't been well studied. The paper proposed an effective method called RGWD though heavily relying on previous work.

2. The authors provide some theoretical analysis including some properties of the proposed metric and the convergence of the optimization algorithm.

3. The numerical results especially those of the synthetic data showed the effectiveness of the proposed method in comparison to GDL.

Weaknesses:
1. In terms of the model, the contribution is not significant because compared with previous work of GWD, the proposed method only added an error term E. Thus RGWD can be regarded as a natural relaxation of GWD. The connection and difference should be highlighted. In the numerical results, what caused the improvement of RGDL over GDL? Is it the noise term E or optimization algorithm?

2. It seems that the time complexity is $O(n^4)$ and the authors did not discuss the time cost in the experiments.

3. The role and effectiveness of E are not clearly explained. Could one use other constraint on E instead of the infinity norm?

4. In Theorem 1, it is not clear why RGWD cannot reach zero.

5. Is RGWD symmetric?

6. In the experiments, are C_i similarity matrices? If yes, setting $\epsilon$ to large values such as 10 and 30 in Table 1 looks a little weird.

7. In Table 4, it seems that all methods failed in clustering IMDB-B and IMDB-M because the ARIs are less than 0.1, which makes the experimental results useless. The authors should consider more real datasets on which the proposed method can work well. One MUTAG dataset is not enough.

8. It is not clear why the authors did not show the influence of $\epsilon$ on the clustering performance of the real datasets.
clarity,_quality,_novelty_and_reproducibility: The clarity and quality can be improved. The novelty is not very significant when we consider the previous work GWD and GDL. The numerical results are not sufficient.
summary_of_the_review: Overall, the idea of robust dictionary learning is interesting though robust dictionary learning has been widely studied in many previous work of vector data. The novelty is fine and the experiments should be improved.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes an improved graph learning algorithm based on a robust Gromov-Wasserstein discrepancy (RGWD). Following the previous GDL by Vincent-Cuaz et al. 2021, the new method replaces GWD by a new RGWD which uses a minimax formulation. Moreover, robust graph dictionary learning algorithm is also proposed based on stochastic gradient descent. Overall, the paper has a certain novelty on designing a discrepancy form with theories, and the numerical experiements on synthetic and real-world data sets have shown the performance of the proposed algorithm. 
strength_and_weaknesses: Strengths:
1. A new robust variant of GWD is proposed with discussions on its properties such as asymmetry. 
2. A projected gradient descent algorithm for RGWD is provided with convergence guarantees. 
3. Performance of the proposed method on synthetic and real-world datasets is outstanding. 

Weaknesses:
1. In Sec 3.2, the Moreau envelope of the maximum function turns out to be a minimax problem, and the corresponding proximal operator is not straightforward. Some remarks about the role of this in Theorem 1 could be made. 
2. It's not clear why a negative quadratic term is necessary in eqn.(4), which also makes the objective nonconvex and may cause convergence issues. In addition, guidance on choosing the parameter $\lambda$ for some datasets could be given.

clarity,_quality,_novelty_and_reproducibility:  The quality, clarity and originality of the work is good. 
summary_of_the_review: The paper is interesting, reads well and has clear motivation and contributions.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Vincent-Cuaz et al. recently extended dictionary learning to graphs (GDL), where the topology of each graph is described with a pairwise relation matrix which are compared via the Gromov-Wasserstein discrepancy (GWD). A serious limitation of graph dictionary learning is the lack of robustness. This paper introduces a new scheme based on a robust variant of GWD which involves a minimax optimization problem that is neither convex nor concave. They establish some basic properties (e.g. triangle inequality). Finally they evaluate it experimentally, and indeed it outperforms ordinary GDL in a variety of settings. 
justification_for_why_not_higher_score: The running time is cubic, and it is not clear if these methods, or even GDL in general, can have broader applicability. 
justification_for_why_not_lower_score: This is a nice paper that articulates an important problem with graph dictionary learning and provides a natural solution.
Decision: Accept: poster