Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work introduces TFGW, a novel graph embedding layer that describes a graph with its Fused-Gromov-Wasserstein distances from a set of learnt templates. TFGW is shown to exhibit strong discriminative power on a wide set of graph classification datasets. 
strengths_and_weaknesses: Overall, I found the paper to be clearly-written, well-motivated, and easy to follow. The experiments show meaningful improvements over existent baselines, and the sensitive analysis further substantiates the model's robustness. On the downside, there have been previous prototype-based graph embedding models (e.g. OT-GNN) that also learns the template in an end-to-end fashion, which somewhat limits the novelty of this work. In addition, I have some additional concerns that I hope the authors can clarify.



questions: 1. If my understanding is correct, the main novelty of TFGW in the context of OT-GNN is its use of the FGW distance instead of OT. In Lines 310-325, it is confirmed experimentally that the trade-off parameter $\alpha$ is not 0 or 1, so that the use of FGW is justified as it is not reduced back to OT. However, I'm wondering if an ablation study has been done to manually set $\alpha=0$ in TFGW, which reduces FGW back to OT, and compare its performance with that of learned $\alpha$? This should further cement the advantage of using FGW in place of OT, which I believe is an important point to make since FGW is more expensive to compute than OT. 

2. How does the practical runtime for TFGW compare with other GNNs? I understand that the OT solver used is only implemented on CPU, and TFGW has a competitive speed when benchmarked on CPU. I am wondering if the current TFGW implementation is reasonably efficient on the experimental datasets. 

3. The TFGW layer can serve as a drop-in for the global pooling step in any existing GNN model. However, it seems that TFGW is always used with GIN in this work. Have the authors tried TFGW with other GNN node embedding layers? Does TFGW interact better with some compared to others?

Misc.
1. Figure 1 can be seen from the web preview but cannot be displayed after the PDF file is downloaded and opened with Adobe. I am not sure if this is an issue on my side.
limitations: The authors have addressed the limitations of TFGW adequately.
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: The authors introduce a novel GNN construction by adding a new GNN layer that is called TFGW for Template-based FGW. FGW is Fused Gromov-Wasserstein distance and it shows the similarity and isomorphism between two graphs. The novel GNN consists of normal GNN layers, a TFGW layer, and an MLP layer, and its structure is shown in Figure 1 of the paper. Furthermore, the properties and the invariances are discussed in the paper. It is illustrated that the TFGW embeddings are invariant to strong isomorphism. The optimization strategy and graph templates relevant for the downstream task are also introduced. The trade-off parameter is learned in the model in a supervised way which appears first. In section 3, the experiment settings and results are shown. The performance of the TFGW is tested in synthetic datasets, several well-known graph classification datasets, and an ablation study.  The results of the sensitivity analysis and an ablation study could show the generalization of the parameters in the model. 
strengths_and_weaknesses: The language is very fluent and the expression is most appropriate in this paper. The proof and the illustration of the experiment details are very clear. The structure of the Template-based FGW layer is very novel and creative. The FGW distance could express the similarity and isomorphism between two graphs and it appears to be appropriate to construct a layer deeply related to it. The results of the ablation study could also show the outstanding performance of this novel layer. This paper is the first to learn the trade-off parameter in a supervised way. It is not required to adjust the parameter to obtain the best performance for other users and could guarantee the generalization of the proposed Template-based FGW model. In the numerical study in section 3, the authors compare the proposed model with several widely used GNN models. From the results in table 2 and table 4, we could find that the performance of the proposed model is distinguished and could do well in the downstream task.
questions: It is reported in the paper that for L=0, the TFGW with SP matrices outperforms TFGW with ADJ matrices while for L no less than 1, the TFGW with ADJ matrices shows better performance. Could a more specific explanation be given? Is this phenomenon related to the aggregation function of the GNN itself?

From section 2 in the paper, we could see that the trade-off parameter and the templates are learned from the data. Therefore, different templates could appear with different parameters. A direct problem might be how to deal with this phenomenon? 

limitations: From lemma 1 in this paper, we could know that for strong isomorphic graphs, the embeddings are invariant but there is not any description of the performance of the TFGW on weak isomorphic graphs. 

In this paper, the expressiveness of the TFGW is not derived. There should be a WL-test to show the expressiveness of this novel GNN structure.
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 study the problem of graph classification. They propose to use the Fused Gromov-Wasserstein (FGW) distance as features for the MLP classifier for graph classification. In the proposed framework, instead of computing pair-wise FGW distances between each pair of graphs, they propose to create some learnable 'templates', which are expected to carry discriminating information either in the features or in the structure of the graphs. Calculating the FGW distance to the templates forms the TFGW layer. The authors also added a GNN layer at the beginning for graph feature transformations. The authors performed various experiments, ablation studies and visualizations to show the superior performance of the proposed framework. 
strengths_and_weaknesses: The authors leveraged Fused Gromov Wasserstein distance for graph classification. The idea is intuitive, and the authors demonstrated the good performance of the model. However, some of the ideas presented can be better explained (see questions below)

questions: 1. I don't quite understand the function of h here. Particularly, it seems the h is used to decide the coupling function. How does the initialization of h change the results? Can you do an ablation study where node weights are not in the framework to see what role it plays?

2. The use of GNN at the beginning: the author chosed GIN as the first layer. GIN itself is very discriminative (expressive) of the graph structure. If I understand correctly, the authors didn't use the pooling layer to get an embedding of the whole graph from GIN, but just updated the features of each node based on message propagation? The authors can clarify better on the process. 
limitations: Would like to see a comparison of the computation time for the proposed method and other baselines too.
review_title: null

Meta-review: metareview: In this paper, the authors introduced a new GNN layer to represent a graph by the distances to template graphs. hey used the OT(FGW, used-Gromov-Wasserstein) distance as the metric. They showed good performance on several benchmark datasets.  Overall, the paper is very well written and motivated. The description of the methods and the presentation of the experiments are convincing. We also thank the careful and detailed rebuttal from the authors. This is a pleasant read paper. 

confidence: Certain
Decision: Accept