Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Authors introduce a new (pseudo) distance on attributed graphs, the Tree Mover's distance (TMD). They first introduce Then authors introduce a distance between trees (TD) which aims at recursively comparing their roots, through their respective attributes, and their subtrees using optimal transport (OT) to get hard assignments between these induced subtrees to pursue the recursion i.e comparing trees of smaller respective depth. TMD then naturally comes from TD by modeling graphs as multisets of trees rooted in each node of each graph. TMD is shown to define a proper pseudo-metric for which the axiom of discernability is closely related to the Weisfeiler-Lehman graph isomorphism test. After investigating the revelance of TMD for graphs classification, authors further study its relevance to quantify stability and generalization abilities of the well-known Graph Isomorphism Networks (GIN), being SOTA graph neural networks.
strengths_and_weaknesses: $\textbf{Strengths}$:

- Overall the paper is well-written and the design of TMD is elegant/original. The authors have managed to clearly address a wide variety of concepts, from kernels to GNNs. An obvious pedagogical effort has been made in several proofs of the results provided, which is appreciable.  

- TMD is interesting by its flexibility suggested by its dependencies to a depth-dependent weighting function and to cost functions inherent to used OT (on nodes). 

- TMD seems competitive as a kernel in graphs classification and mostly shines on the study of GIN.

$\textbf{Neutral about}$:

- Without a clear characterization of TMD balls in the space of attributed graphs (or at first, unattributed graphs), I find it difficult to envision how TMD can guide GNN to further improvements, but given the difficulty of this task, the empirical evidence provided in Sections 5 and 6 supports the relevance of TMD for this purpose.  

$\textbf{Weaknesses / points to clarify}$:

- Authors exploit specific properties of the Kantorovich formulation of OT (especially its relation to Monge's formulation) which are eluded in the paper and clearly not straightforward so, to improve the clarity of the document e.g the need for definitions 2 and 3, it would be good to mention them (Also the caption of figure 1 can be improved for this purpose).

- Theorem 7: From your proof I would say that the stated implication is actually an equivalence. Could you elaborate on this ?

- On the graphs classification benchmark : I am not sure to understand your validation scheme from your explanations. From my understanding you did a cross-validation for TMD, while e.g authors of FGW reported a 10-fold nested cross-validation in their paper  (Which better quantifies generalization abilities and is more natural for graph kernel methods as the computational bottleneck lies in the computation of the kernel matrix). Therefore I suggest harmonizing the validation scheme on kernel methods instead of just reporting the performance of the respective papers. Moreover, could you complete the benchmark on graphs classification with a benchmark in terms of runtimes ?

- On subsection 5.1: There is a difference between your formulation of message-passing and the one from GIN (see equation 4.1 of [48]), $\epsilon$ is not handled in the same way. As you set $\epsilon=1$ for your experiments they are still valid, but the implications of this change for the theoretical results in your paper and the ones in GIN's paper are not clear to me, even if it seems minor. Could you elaborate on this ?  

- There is no reference to the figure 4 and 5 in the main paper.

**Modification:** I increased my initial grade from 5 (borderline accept) to 6 (weak accept) after a convincing rebuttal and discussion by the authors.
questions: For clarity and conciseness my questions/doubts have been clearly stated in the "Strengths and weaknesses" section.


limitations: A few limitations of their work have not really been addressed as illustrated by my elaboration on the "weaknesses/points for clarification" paragraph. The authors have adequately addressed the potential negative societal impact of their work in the supplemental material.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: A metric on the set of graphs is defined using concepts from optimal transport.  It is shown both analytically and by experiment that graph neural networks define Lipschitz continuous functions in the metric.

strengths_and_weaknesses: Strength: The proposal is clear and well motivated, and has evident applications.  The evaluation is adequate for a first work.

Weakness: Graph metrics are a much studied field and there is little comparison with previous work.
questions: Let me check in an example that I understand how the definition works for graphs without features.  
Let T_N be the tree with a root and N children.  The distance TD(T_m,T_n)=|n-m| because
the distance between a blank tree (feature vector = 0) and a generic vertex (feature vector = 1) is 1.

If so then for graphs with features, the definition depends on the point 0 chosen for the blank tree feature.
This should be mentioned more explicitly.
limitations: Technical results with no immediate societal impact.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper introduces a graph pseudo-metric based on the hierarchical Optimal Transport , to understand the generalization of machine learning models on graphs. They show that the proposed TMD captures properties relevant to graph classification and can be related to generalization of GNNs under distribution shifts.  
strengths_and_weaknesses: Strengths:

1. The paper is well-written and easy to follow, although there exist some unclear descriptions.
2. This paper proposes a new OT distance for graphs. Using the computation trees of the graph to calculate the distance between two graphs is direct and reasonable.
3. The Lipschitz Constant and Stability analysis of GNNs seem to be useful and meaningful.

Weaknesses:

1. ”TMD can provably distinguish graphs that are identifiable by the (1-dimensional) Weisfeiler-Leman graph isomorphism test”. The authors say it can be further strengthened by augmenting node attributes e.g. with positional encodings, but they have not provided the details. Since expressive power is very important for graph representation learning.
2.  The computational complexity of TMD is high. The authors only implement it on CPU (POT package). It is unclear whether the method can be accelerated by GPUs.
3. Some baselines on graph OT are missing, for example, [1] [2] bellow.  


[1] GOT: An Optimal Transport framework for Graph comparison
[2] COPT: Coordinated Optimal Transport on Graph.

questions: 1. Can the authors provide an example regarding “the distance $TMDLw(Ga, Gb)$ can be zero even if $Ga = Gb$”.
2.  The notation in Definition 4 is confusing. What is the $OT_{TD_w}$?
3. The complexity of iteratively calculating the distance between the L-depth trees is high. The running time of baselines and the proposed methods shall be added.

limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors first propose TMD, a pseudometric for comparing graphs to each other. TMD compares graphs to each other by recursively solving a series of optimal transport problems which minimizes distances of subtree patterns. The proposed pseudometric is evaluated in graph classification (distances fed to an indefinite kernel and then to SVM). The results indicate that TMD performs on par with the best performing baselines. The authors also provide some theoretical results. First, they bound the Lipschitz constant of the GIN model with respect to TMD, and also analyze the stability of GIN under node deletions, edge deletions and perturbations of node features. Finally, they provide a result about the generalization error of GIN under distribution shifts.
strengths_and_weaknesses: Strengths:
- In my view, the originality of the paper is high. The proposed TMD distance is novel. Previous studies have applied optimal transport techniques on the labels produced by the WL algorithm, but in my understanding, the proposed recursive definition is different from previous work.

- I really like the results about the stability of graph neural networks. Most previous studies have focused on a different problem: whether a graph neural network can distinguish classes of non-isomorphic graphs or not. Not much work has been done on the distance between the graph representations. I am not thought sure how useful the experiments of subsection 5.3 are. What's the purpose of showing that the correlation between TMD and a graph neural network is high? Furthemore, does this hold for all datasets?

Weaknesses:
- The computational complexity of the proposed distance function is very high since it needs to solve a series of optimal transport problems. This renders the method practically infeasible for datasets that contain large graphs (such as REDDIT-BINARY) and datasets that contain many samples (such as the OGB graph property prediction datasets). Of course, for the optimal transport problem, one could use some approximate algorithm, but still I don't think the proposed method can be applied to large datasets.

- As one can see in Table 1, the proposed method provides only marginal improvements in accuracy over the baselines. Furthermore, TMD is not compared against several state-of-the-art graph neural networks. It is only compared against GIN and GCN which are at most as expressive as 1-WL. It would be nice if the authors could also report the running time of TMD and compare it against that of the Wasserstein WL function.

- The message passing scheme of GIN given in subsection 5.1 is different from the one provided in the original paper, i.e., $z_v^{(l)} = \phi^{(l)} ((1+\epsilon^{(l)})z_v^{(l-1)} +\sum_{u \in \mathcal{N}(v)} z_u^{(l-1)})$. Furthermore, both for the experiments and for the proof of Theorem 8, the authors set $\epsilon=1$. GIN is known to be less expressive than 1-WL when $\epsilon=1$. Furthermore, the message passing scheme of GCN given in Appendix B.1 is not correct. Thus, I wonder whether the Lipschitz constant of any message passing graph neural network can be bounded under TMD or are there some conditions that need to be satisfied?

- Even though TMD is sufficiently different from the Wasserstein WL pseudometric, I would suggest the authors provide more details about how the two methods differ from each other and also compare the complexities of the two approaches to each other.
questions: For the graph classification task, it is not clear to me why an SVM classifier with indefinite kernel is employed. Since TMD computes distances, the natural way to perform classification would be to employ the k-nn classifier. Did the authors experiment with that classifier and how does it compare to the SVM classifier?

Typos:\
l.205: "the empirically performance" --> "the empirical performance"

limitations: The authors discuss the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: metareview: This paper proposes a new similarity measure between graphs, based on computing optimal transport between distributions of trees extracted from graphs. The method benefit from the fast solvers of OT between trees and the proposed metric has been shown to be interesting for computing  a "Lipshitz" constant related to the generalization of message passing GNN. The experiments were appreciated but lack of comparison with existing graph distances and GNN was noted by the reviewers on the graph classification experiment.

The authors did a very good reply to the reviewers which was much appreciated. For instance the new experiments are very interesting and should be included in the paper or supplementary. The fact that the performance does not depend too much on the classifier (SVM VS KNN) is also interesting. During discussion the consensus was that the paper deserves to be published at NeurIPS but that the authors are requested to include the new results and discussions/clarifications in the paper and supp.
confidence: Certain
Decision: Accept