Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: 
The paper presents an embedding method for graphs, denoted as WEGL. The method operates by first representing each graph as a set of vector representations of its nodes, secondly, an optimal transport map is computed with respect to a finite reference set of points and, finally, a fixed-size vector representation is computed from that map.
The result is an embedding into a Hilbert space, where the distance between two graph representations approximates the 2-Wasserstein distance between their respective node distributions.

The paper is partly inspired by WWL (Togninalli et al. 2019) and provides an explicit embedding map, hence improving in terms of computational performance. I have some comments and concerns about the experimental analysis, which does not seem to directly validate the paper claims. Overall, it is well written and clear in almost all its parts.

Comments.
1. The paper considers only the smallest of the datasets in OGB (Hu et al., 2020) for graph-level prediction, specifically ogbg-molhiv. I wonder if the proposed method, which is claimed to be computationally efficient, can handle also the other three.
2. Choice of the baseline methods. I expected comparisons with other (explicit) embedding methods (eg, Hu* et al. 2020, Kriege et al. 2014) both computationally and at the task. Since WEGL is somehow a variation of WWL, I would like to see its performance compared also in Section 5.1.
3. How performance has been assessed. The paper mention in the captions of Tables 1 and 2 that some of the results have been reported from already published papers. However, I couldn't find any details about the experimental settings of the other methods. Is the architecture of the GIN in Figure 3 the same as that in Tables 1 and 2? Are all the baseline methods operating on graphs with the "virtual node" variant (which is important for a fair comparison of the embedding capability)?

To further improve the paper, I suggest spending a few more words to
- clarify the use of the Jacobian and the approximation in points 1 and 3, Section 3.1;
- define the barycentric project and clarify why it is not invertible.

(Kriege et al. 2014) Kriege, Nils, et al. "Explicit versus implicit graph feature maps: A computational phase transition for walk kernels." 2014 IEEE international conference on data mining. IEEE, 2014.
review_title: The paper has merits, but I have a few concerns about the experimental analysis.

final_score: rating: 6: Marginally above acceptance threshold
review_content: Strengths:
* **Computational advantage**. The quadratic-to-linear complexity reduction for pairwise computation (each of them an LP) of LOT is clearly the main selling point of this paper, which makes it an appealing approach for comparing multiple graphs. 
* **Writing**. The paper is overall very clear, well-written, and engaging. 

Weaknesses:
* **Novelty**. The paper proposes a farily trivial combination of Wang et al's 'linear' OT with simple message passing on graphs. The main aspect where there could have been an interesting novel contribution, the computation of the reference embedding, is solved somewhat unsatisfactorily with a k-means embedding
* **Unexplained design choices**. The use of the 'virtual node' is not well motivated, nor its contribution evaluatued experimentally. In addition, it's not clear why it was decided to not implement/comparse the entropy-regularized version of the proposed method, given that this could hold the key to truly scalable graph comparison. In addition, entropy regularization has consistently shown to even *improve* performance compared to exact OT in many applications. Most OT libraries already include this variant, so there really seems to be no excuse not to incoporate it. 
* **Some important trade-offs brushed under the rug**. Equation (13) seems to suggest that a NxNxN tensor has to be stored in memory, which could be prohibitive in many settings. Is it fair to say that LOT is implicitly trading time by space complexity? In fact, one could argue that this not even entirely correct, as the LP solved in (13) is now cubic rather than quadratic on N, so it seems there is a trade-off in computation too: reducing the number of pairwise comparisons but making each individual LP problem larger. 
* **Experimental results raise questions**. There are many moving parts in the evaluation (e.g., the addition of the virtual node, different types of classifiers), so it's hard to disentangle the core effect of the proposed method. 
    * The results in Table 1 seem to indicate that the classifier at the end of the pipeline has a much stronger effect on performance than the proposed method. 
    * What kind of classifiers are used in the other GNN methods? Where these also optimized for performance? Why not using the same type of classifier on all methods for fair comparison?
    * All the baseline methods have a very strong degradation in performance between validation and test sets. For the proposed method, the degradation is much less signigicant, especially for the +AutoML classifier. How do the authors explain this? This seems to indicate that there is significant overfitting in all methods, and that proper regularization of the classifiers (e.g., via AutoML) is mitigating this for WEGL. This casts significant doubts on the results of this section in my opinion.
    * Again, for the results in Section 2, the classifier seems to have an important effect in the performance of the proposed methods, yet there is no discussion on the classifiers used in all the baselines. In addition, the standard errors are so large that pretty much all methods have overlapping confiedence intervals, so it's hard to draw a statistically significant conclusion from these results. 
    * The runtime comparison is also limited. First, it's not clear whether the runtimes shown for WEGL include the full pipeline (e.g., including the reference embedding computation). Second, one of the methods is run on GPU while the other two are run on CPU, so it's hard to put those two sets of results in direct comparison. 

* **Misses importart related work**. E.g., 
    * [1] attempts to realize Characteristic (4) mentioned in Section 3
    * [2] also leverages generalized geodesic for comparison of multiple measures
    * [3] combines OT and WL Kernels and applies it to settings very similar to the ones tackled here. 

Other comments questions:
* It would be informative to see a discussion on how well LOT enfoces Characteristic 4, that is, what guarantees does one have on how close the l2 embedded distances is to the true wasserstein distance?

Missing references:
* [1] Courty et al., "Learning Wasserstein Embeddings", 2017
* [2] Seguy and Cuturi, "Principal Geodesic Analysis for Probability Measures under the Optimal Transport Metric", NeurIPS 2015. 
* [3] Bécigneul et al., "Optimal Transport Graph Neural Networks", 2020
review_title:  A simple but interesting combination of 'linear' OT and graph embeddings, with less than convincing evaluation

final_score: rating: 7: Good paper, accept
review_content: ##########################################################################

Summary:

This paper proposes to use a Wasserstein embedding to compare graph using also node embedding methods to convert graphs into vectors. While the elements are not new, the proposed method is new and is competitive with other classical methods (graph kernel and graph neural networks). 

##########################################################################

Reasons for score:

Overall, I vote for mild acceptation. The method is clearly new, but the ingredients are already new and the results are not godd but not exiting.

##########################################################################

Pros:

1. The combination of node embedding with Wasserstein distance is new and show pretty good results.

2. The method itself seems very flexible and effective compare to other state of art methods.

3. The presentation of the methods is rather clear and most of the technical details are available. As such the paper is self-contained.

##########################################################################

Cons:

1. The framework relies on a node embedding method. Seems the choice of the method could be crucial, we need some discussion on this point.

2. The proposed node embedding formula (equation 9) assumes that the information on the edge is a scalar. However previously in the paper the edge attributes are a vector, please give some slues on how to deal with such edges.

3. The section 4.2 is not clear for me. Is the zero distribution compute on the whole database? Or is it compute class by class? Both ways seems possible please clarify?
 
##########################################################################

Questions during rebuttal period:

Please address and clarify the cons above.

review_title: Promising but can be stenghten

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: # Synopsis of the paper

This paper presents WEGL ("Wasserstein Embedding for Graph Learning"),
a technique for embedding graphs for graph classification. The primary
novelty of the paper lies in their smart choice of embedding, which
combines the expressivity of optimal transport paradigms (i.e. the
Wasserstein distance, in this case) with improved computational
performance; more precisely, the embeddings permit the use of effective
classification algorithms, as opposed to scaling quadratically with the
number of samples.

# Summary of the review

This is a well-written paper with a powerful algorithm and a strong
experimental section. It will make an excellent contribution to the
conference, and I am excited to endorse it!

There are some issues with the current version of the write-up, though,
which, if fixed, will make this an even stronger publication. My primary
concerns at present are:

1. The paper spends a lot of space in outlining background information
   that is not pertinent to the method. I appreciate the amount of
   details that are being packed into Section 2.1, but as a reader of
   this paper, I would prefer a more in-depth discussion of the method
   rather than a discussion of GNNs, which are used as mere comparison
   partners here. My suggestion would be to put some of these
   information into the appendix.

2. The section on Wasserstein distances could be streamlined. At
   present, too many different concepts are introduced; I feel that
   a non-expert reader will just be deterred, even though the remainder
   of the paper is very hands-on. Maybe some additional intuition could
   be provided here?

3. On the other hand, Section 3 is *missing* important information; in
   this section, I would be very much interested in knowing more about
   the theoretical properties of the method (and its empirical
   performance). The characteristics mentioned on p. 4 are intriguing,
   but it would improve the paper if a more detailed write-up would be
   provided; a reference with proofs for these properties would be
   equally helpful. I am fully aware that it is hard to satisfy both
   theory and experiments in a paper; I have some more detailed comments
   about what could be added (potentially in the supplementary materials,
   if the authors think that it detracts from the flow).

# Detailed Comments

- The point about the 'true metric' in the introduction is slightly
  ambiguous. My understanding is that one obtains a metric between the
  embedded feature vectors. This does *not* constitute a metric on the
  graphs, though, unless the embedding is injective. I think the
  sentence means to say that one obtains a metric in an embedding space
  and this metric serves as a proxy for the Wasserstein distance.

- In the related work section, I would suggest citing other variants of
  the WL algorithm that have recently emerged:

    - Morris et al.: *Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks* (https://aaai.org/ojs/index.php/AAAI/article/view/4384) 
    - Morris et al.: *Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings* (https://arxiv.org/abs/1904.01543)
    - Rieck et al.: *A Persistent Weisfeiler-Lehman Procedure for Graph Classification* (http://proceedings.mlr.press/v97/rieck19a.html)

- The way a graph is defined in this paper could be misconstrued as
  *directed* upon first reading. Why not define edges in both directions
  by using a subset notation instead of a tuple notation?

- How are categorical attributes treated? In the supp. mat., the usual
  one-hot encoding is mentioned. This could be discussed earlier (i.e.
  on p. 2).

- When discussing the embedding, I would suggest briefly mentioning the
  concept of reproducing kernel Hilbert spaces (RKHS). Such a discussion
  will provide the relevant backdrop for this publication.

- As suggested above, I would shorten Section 2.1 somewhat (or put some
  of the text into the appendix). While it is good to provide some more
  details about the inner workings of GNNS, this is not required for the
  paper.

- Section 2.2 would benefit from more intuition; a lot of the
  terminology is introduced too tersely and not re-used. I fully
  appreciate that the paper is mathematically precise here, but at the
  same time, I would suggest a more streamlined introduction of the
  concepts that are necessary to define the embedding in the end.

- Section 3.1 and Figure 1 differ slightly in terms of their notation.
  I would suggest to harmonise the description here in order to be more
  consistent.

- For property 4 on p. 4, is it possible to quantify the strength of the
  approximation? How good is this approximation in practice, and what
  are the factors influencing it? I would suggest adding some more
  details here (or citations, if appropriate).

- To add to the previous point, I would in general like to know more
  about the stability properties of the full embedding. Can this easily
  be quantified? For example, what happens if I add some noise to the
  attributes? I would assume that stability is a function of the
  selected aggregation function *and* the Wasserstein embedding itself.
  Assuming that the former is fixed to be the function described by
  Togninalli et al., does the latter satisfy, for example, Lipschitz
  continuity? (I am asking this out of professional curiosity;
  understanding the inherent properties of the embedding seems key to me
  for us to understand better ways to generate such embeddings; the
  empirical performance of the proposed method speaks for itself, of
  course!)

- Section 3.2 is rather technical at present, making use of
  hitherto-undefined concepts. I would suggest improving this section
  by providing more intuition, relegating some of the more technical
  results to the appendix.

- Does the pseudo-invertibility of $\phi$ cause any problems in
  practice? It is my understanding that the embedding will not be
  injective in general anyway, or am I mistaken?

- How stable is the reference embedding? In Section 4.2, it is my
  understanding that the reference embedding is by default obtained from
  $k$-means, with $k$ being the average number of nodes. The appendix
  depicts the results for another data-independent reference embedding
  and states that there are no differences. Would this not suggest that
  the way the reference distribution is obtained is irrelevant? If so,
  why not use a normal distribution (which I would expect to be simpler
  to calculate than a $k$-means embedding) for all experiments?

  This point should be addressed somewhat better.

- Why is the virtual node inclusion necessary? Only for the
  simplification of the message passing itself? I am aware of this
  standard modification, but I do not see why the proposed algorithm
  could equally well work with the original graph.

- Why is the variance of the proposed method high for some of the data
  sets of the 'TUD' repository? Is this a consequence of the model that
  was picked for working with the embeddings?

# Style

This paper is well written; it was a pleasure to read and review. Here
are some minor suggestions to improve style/clarity:

- I would suggest so sort citations by some criterion (alphabetically,
  for example) when citing multiple authors.

- "See the recent survey" --> "see the recent survey"

- "such transport plan" --> "such a transport plan"
review_title: A smart, innovative embedding algorithm based on optimal transport

Meta-review: This paper proposes  a novel and interesting embedding of graphs emulating the Wasserstein distance. The experiments are good and the authors did a detailed answer taking into account the comments of the reviewer. The responses were appreciated and the AC recommends the paper to be accepted.
Decision: Accept (Poster)