Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Authors propose GNP, a new pooling operation for Graph Neural Network which subsumes max, min, mean and sum as special cases.

The premise of the paper is promising - if a single layer can provide the performance of max, min mean and sum, through two new learning parameters, it would be a big win for research. On certain occasions, it is unclear which pooling function is the best and researchers resort to large grid searches to identify which ones work best. This could do away with that.

However, I feel that the paper falls a little short of delivering this.
main_review: The authors propose GNP, a new pooling operation for GNNs, which subsumes max, min, mean and sum as special cases.

The contribution to this paper is incremental. It builds on top of the well known L-p norm pooing function and extends it to allow negative values of p, and an additional learnable parameter q. However, this simple extension is not a well behaved function for gradient based optimization, hence the authors tweak the layer to behave better using techniques that are well known.

Based on the experimental results, it does look like GNP outperforms the baselines which is a plus. However, in some cases, despite being a more complex pooling layer with more learning parameters than the baseline pooling functions, it does not seem to offer enough gain in performance to justify its complexity. (Especially since in some of the experiments, the optimal baseline was part of the search space for GNP). For example:
Table 1: GNP is unable to match with (sum, max) on the maxdegree task for Ladder Graphs.
Table 2: GNP is unable to match min on bfs.
This is disappointing considering that GNP has the upper hand in the # of learnable parameters

The real world graphs used in the paper comprise a total of ~6k graphs. The heaviest of this dataset, D&D contains ~300 nodes on average. While GNP performs well on these graphs (except for maxdegree), I feel the datasets are not large enough to assert if GNP scales to very large graphs containing hundreds of thousands of nodes. Further, the synthetic datasets used contain only 50-100 nodes, and hence are also relatively small.

The ablation study was interesting. It is nice to see that in some cases GNP is able to find the optimum values of p and q, especially for maxdegree. For the GNP+ part of the ablation, do you still use the extra linear layer described in 3.2? I am curious about how the GNP+ model fairs with and without that extra linear layer.


summary_of_the_review: For an excellent version of this paper, I would recommend the following:
- Evaluate the models on more real world datasets with larger graphs - 100+ and 1000+ nodes and break down the performance of GNP based on the number of nodes in the graph. It is often the case that GNN architectures don't scale well on larger graphs.
- Add an ablation study with GNP+ with and without the additional linear layer.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes a learnable pooling method (GNP) for GNN based on $L^p$ norm, which is general to simulate the behavior of max, min, sum, and average. It performs well on many node-level, graph-level, and set-related tasks.
main_review: 
**Strengths**
1. The paper is well written, with a clear description and proof of the GNP method.
2. The design of GNP is simple but general, enabling the model to learn which aggregation and pooling method to use.
3. The extrapolation performance of the GNP outperforms simple min, max, mean, and sum pooling methods. 

**Weakness**
1. Though GNP can theoretically simulate the behavior of the max and min, I am concerning the $p\rightarrow \pm\infty$ may cause stability issues for computation. That might be the reason why GNP performs worse than (sum, max) on the max degree task in Figure 1(c).
2. The GNP requires the inputs to be non-negative so that the inputs should be the output of the ReLU function. It may cause information loss of the embeddings. It is a common practice in machine learning that the inputs of the pooling function should not be the output of the non-linear function. Therefore, it would be more convincing if the authors can show results on more real-world datasets, e.g. the ogb dataset.
3. The baseline results on the NCI dataset shown in the paper is not SOTA, as in the original paper $\text{SAGPool}_g$ achieves 0.742. Also, there are stronger baselines on that dataset, including [1, 2] which achieve 0.815. 
4. GNP is an interesting idea and performs well on small synthetic datasets, but it would be better to see how GNP works on state-of-the-art model architectures on real-world applications, like PNA[3] and DAGNN[4], instead of the vanilla GIN and GCN.
5. Node classification is another task that is good to see in the paper to demonstrate the effectiveness of using the GNP for aggregation.

[1] U. Alon, and E. Yahav. On the Bottleneck of Graph Neural Networks and its Practical Implications. ICLR 2021.

[2] F. Errica, M. Podda, D. Bacciu, and A. Micheli. A fair comparison of graph neural networks for graph classification. ICLR 2020.

[3] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal Neighbourhood Aggregation for Graph Nets. NeurIPS 2020.

[4] V. Thost, and J. Chen. Directed Acyclic Graph Neural Networks. ICLR 2021.
summary_of_the_review: The GNP idea proposed in the paper is interesting and works well on small tasks. However, the non-negative constraint of the inputs may be too strong and can cause information loss. Without state-of-the-art large-scale real-world experimental results, I am not fully convinced by the effectiveness of GNP.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper focus on the extrapolation ability of graph neural networks and propose a new pooling function for graph-level readout based on vector norm. The proposed method can be applied to replace the commonly used pooling function like max/mean/sum in GNNs and is proved able for extrapolation in a simple example. Experiments on several synthetic tasks and a few real-world datasets are conducted to verify the effectiveness of the proposed method. 
main_review: Endowing graph neural networks with extrapolation ability is a significant and challenging problem, as in many real cases the graph networks need to handle data within new environments during test time. This paper proposes to pursuit this goal via developing a new graph-level pooling function. The idea is very simple and straightforward and the proposed pooling function is a generalization of existing ones like max, sum, avg and min. Also, some theoretical analysis is provided to show that the new method can enable GNN for extrapolation in a simple example. To verify the approach, experiment results on nine different tasks, including graph-level, node-level and set-level, spanning from synthetic datasets to small real-world datasets, are conducted with comparison to existing models. The experiment designs are interesting and cover many diverse cases. However, there are some concerns as shown below.

The technical contribution of this paper is very weak. The proposed pooling function is a vector norm with the order coefficient as learnable parameters (i.e., only two for one pooling function). Then gradient method is considered for learning these parameters (4 in total) together with the GNN in an end-to-end manner. I doubt if this design could be applicable for large GNN models and would also suffer from serious optimization issue in practice. Although some practical tricks are proposed to avoid gradient explosion, it is not enough for guaranteeing a smooth training on large models and large real-world datasets. This concern is even amplified given the fact that the experiments mainly focus on synthetic datasets with unrealistic tasks and very small real-world datasets. 

The theoretical analysis is also limited in a very constrained setting. The model learning is limited with square loss in NTK regime and the task is limited in harmonic task function. With these strong assumptions, it is not surprising to arrive at a proof of construction that satisfy the goal as shown in Thm 1, and such a result has little significance and impact for GNN learning on real tasks. Besides, in order to make the gradient smooth for optimization, the authors propose to combine the positive and negative p's in one formulation , however, such a design is not intuitive and hard to understand the rationale.

The experiment results are also weak. Most of the experiments are considered on synthetic datasets with unrealistic tasks that are tailored for the proposed function. A few results on real-world datasets are reported, however, these datasets are very small and the improvement achieved is not statistically significant. I suggest the authors add more experiments with some common graph benchmarks such as node classification/regression, link prediction/classification and graph classification/regression and consider more GNN backbones (GCN, GraphSAGE, GAT, etc.) to calibrate the comparison results. That could help to evaluate the practical efficacy of the propose method with respect to real applications.
summary_of_the_review: I carefully read the maintext and quickly go through the proof in the appendix. I am not sure about the correctness of the theoretical proof, though most of them appear to be correct. It is possible that I miss some details.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper presents Generalized Norm-based Pooling (GNP), a L^p norm like pooling function with the trainable p for Graph Neural Network to achieve extrapolation. The authors also propose a training method that use a single linear layer to address the gradient exploding issue. Equally splitting the GNP function, the model can learn both positive and negative p. Experiments were done to demonstrate GNP at the node-/graph-/set- levels.
main_review: The trainable pooling function eliminate the need to manually try different pooling setting. The pooling function performs steady and well on set-level tasks.

It appears challenging for GNP to learn the min or max pooling functions. Table 2 shows that GNP underperforms the minimum pooling by a large margin. Also, GNP performs no better than the maximum pooling on large graphs with heterogeneous structures. Hence, the proposed training is not able to push p to reach +/- infinity.

In section 3.2, instead of directly concatenating two vectors, why the output is obtained by taking the first half of GNP+ and the second half of GNP-. What does it mean by ‘let the model choose between them’? Under which kind of condition will the model choose p+ or p-?

The proposed method contains a one-layer MLP, which introduces extra d*(d + 1) parameters of the GNP functions compared to traditional pooling functions. The evaluation of using one-layer MLP is missing in the ablation study part. It’s hard to conclude whether the improvement comes from the MLP or the GNP.

summary_of_the_review: The GNP idea seems promising. Additional clarifications and experiments may strengthen the manuscript.
review_title: null

Meta-review: This paper focuses on the extrapolation ability of graph neural networks and proposes a new pooling function based on vector norm. The proposed method can be applied to replace the commonly used pooling function like max/mean/sum, and is proved able for extrapolation in a simple example. 

Overall, all reviewers tend to reject this submission due to the following reasons
- The contribution to this paper is incremental. It builds on top of the well-known L-p norm pooing function and extends it to allow negative values of p and an additional learnable parameter q.
- However, this simple extension is not a well-behaved function for gradient-based optimization, which leads to unconvinced experiments, i.e., diverse performance compared with min/max.
- more recent baselines should be compared with and it would be better to see how GNP works on state-of-the-art model architectures on real-world applications
Decision: Reject