Year: 2021

Abstract:
Graph neural networks (GNNs) are one of the most popular approaches to using deep learning on graph-structured data, and they have shown state-of-the-art performances on a variety of tasks. However, according to a recent study, a careful choice of pooling functions, which are used for the aggregation and readout operations in GNNs, is crucial for enabling GNNs to extrapolate. Without proper choices of pooling functions, which varies across tasks, GNNs completely fail to generalize to out-of-distribution data, while the number of possible choices grows exponentially with the number of layers. In this paper, we present GNP, a L norm-like pooling function that is trainable end-to-end for any given task. Notably, GNP generalizes most of the widely-used pooling functions. We verify the effectiveness of GNNs on thirteen tasks using seven different GNN architectures and eight real-world graphs with up to one million edges. Specifically, we demonstrate that simply using GNP for every aggregation and readout operation enables GNNs to extrapolate well on many node-level, graph-level, set-related tasks; and GNP sometimes performs even better than the best-performing choices among existing pooling functions.

heading: 1 INTRODUCTION
text: Many real-world data, such as relationships between people in social networks or chemical bonds between atoms, can naturally be represented as graphs. Finding models with proper inductive biases to better describe such graph data has been a common goal for many researchers, and Graph Neural Networks (GNNs) (Scarselli et al., 2009; Kipf & Welling, 2017; Hamilton et al., 2017; Veličković et al., 2018; Xu et al., 2019; Maron et al., 2019; Xu et al., 2020) are considered to be the most successful model. They have proved effective for a variety of tasks, including recommendation (Ying et al., 2018a), drug discovery (Stokes et al., 2020), and chip design (Mirhoseini et al., 2020).
An important design choice for a GNN often overlooked is the specification of pooling functions, the functions used for the aggregation or readout operation in GNNs. They are usually required to be invariant w.r.t. the permutation of nodes in a graph, and common choices are element-wise summation (sum), maximum (max), minimum (min), or average (mean). Some recent works also proposed to use parametric models and learn them from data as well (Ying et al., 2018b; Lee et al., 2019b; Gao & Ji, 2019; Yuan & Ji, 2020).
While most of the previous works on this line focused on improving predictive performance for their own tasks, recently, Xu et al. (2021) studied the impact of the choice of pooling functions on the ability of a neural network to extrapolate. Specifically, Xu et al. (2021) highlighted the importance of the choice of pooling functions in order to make GNNs generalize over the data lying outside of the support of the training data distribution, and they argued that the specification of the pooling functions acts as an important inductive bias that can make GNNs either completely fail to extrapolate or gracefully generalize to out-of-distribution data. As a motivating example, consider the problem of counting the number of nodes in a graph. If we are to solve this problem with a single-layer GNN having one readout layer, probably the best pooling function would be sum, and the corresponding model will readily generalize to graphs with a much larger number of nodes than the ones seen during training. On the other hand, if we choose the pooling function as max instead, it may still fit the training data well but completely fail to predict the number of nodes in out-of-distribution graphs.
The findings in Xu et al. (2021) raise a natural question; which pooling functions should be used for a given problem in order to make GNNs constructed with them successfully extrapolate for
out-of-distribution data? Xu et al. (2021) did not present any guide but empirically showed that we do have the “right” pooling function for each problem tested, and when a pooling function is not properly selected, GNNs completely fails to extrapolate. The caveat here is that we do not know which pooling function is the right choice before actually training and validating the model.
To this end, in this paper, we present a generic learning-based method to find proper pooling functions for a given arbitrary problem. Our method, entitled Generalized Norm-based Pooling (GNP), formulates the pooling functions as a generic Lp norm-like function (including negative p as well), and learns the parameters inside the pooling functions in an end-to-end fashion. Unlike previous learning-based pooling methods that are usually tailored for specific tasks or focused on improving predictive performances, GNP can be applied to arbitrary tasks, and it improves the extrapolation ability of GNNs constructed with it. Also, GNP includes most of the pooling functions being used for GNNs as special cases. Despite the enhanced flexibility, GNP incurs minimal overhead in GNN in terms of the model complexity. A naı̈ve application of GNP to GNNs is likely to fail because of some difficulty in training, so we propose a simple remedy to this. Using nine graph-level, node-level, and set-related tasks, we demonstrate that GNNs with GNP trained by our training scheme extrapolate for out-of-distribution data comparably and sometimes even better than those with pooling functions that are carefully chosen among of widely-used ones. In addition, we demonstrate the effectiveness of GNP on four real-world tasks (graph classification, influence maximization, node classification, and graph regression) using six additional GNN architectures (GCN (Kipf & Welling, 2017), GAT (Veličković et al., 2018), PNA (Corso et al., 2020), hierarchical SAGPool (Lee et al., 2019b), ASAPool (Ranjan et al., 2020), and MONSTOR (Ko et al., 2020)) and eight real-world graphs. We summarize our contributions as follows:
• Generalized pooling function: We propose GNP, a simple yet flexible pooling function that can readily be applied to arbitrary tasks involving GNNs, with minimal parameter overhead. • Effective training methods: We propose effective training methods for GNP. • Extensive experiments: We empirically demonstrate that GNNs with GNP generalize to out-of-
distribution data on nine extrapolation tasks. We also show successful application of GNP to six GNN architectures on four real-world tasks in eight real-world graphs with up to one million edges.

heading: 2 RELATED WORK
text: Aggregation functions Various aggregation functions have been appeared to enhance the performance of GNNs. Hamilton et al. (2017) proposed GraphSAGE with four different aggregation methods; max, mean, GCN (Kipf & Welling, 2017), and LSTM (Hochreiter & Schmidhuber, 1997). Veličković et al. (2018) proposed Graph Attention neTworks (GATs) including attention-based aggregation functions (Vaswani et al., 2017). Xu et al. (2019) proposed Graph Isomorphism Networks (GINs) and proved that GNN can satisfy the 1-Weisfeiler-Lehman (WL) condition only with sum pooling function as aggregation function. Recently, Li et al. (2020) proposed a trainable softmax and power-mean aggregation function that generalizes basic operators. Compared to these methods designed to improve interpolation performance on specific tasks, ours can improve extrapolation performance for generic tasks.
Readout functions Zhang et al. (2018) suggested SortPooling that chooses top-k values from the sorted list of the node features to construct outputs. Another popular idea is hierarchical pooling, where outputs are obtained by iteratively coarsening nodes in graphs in a hierarchical fashion (Ying et al., 2018b; Gao & Ji, 2019; Lee et al., 2019b; Yuan & Ji, 2020). Although demonstrated to be effective for the tasks they have been designed for, most of these methods require heavy computation and it is not straightforward to extend them for aggregation functions. On the other hand, our GNP can be applied to both aggregation and readout functions with minimal overhead.
Pooling functions in generic context Vinyals et al. (2015) proposed Set2Set to get a representation of set-structured data with a LSTM-based pooling function. Lee et al. (2019a) proposed to use an attention-based pooling function to get summaries of set data. For convolutional neural networks, there were some approaches to generalize average pooling and max pooling widely used for many neural network architectures. Gulcehre et al. (2014) proposed a normalized learnable Lp norm function that generalizes average pooling and max pooling. Lee et al. (2016) further extended those pooling functions with learnable tree-structured pooling filters.
Norm-based pooling functions There have been several works to employ norm-based pooling functions. Gulcehre et al. (2014) proposed a learnable Lp norm function of the form
f(v) =
( 1
|v| |v|∑ i=1 |vi|p )1/p
to substitute max pooling or average pooling used in convolutional neural networks. Similar normbased pooling functions were used for acoustic modeling (Swietojanski & Renals, 2016) and text representation (Wu et al., 2020). Compared to GNP, these pooling methods cannot express the sum pooling. Li et al. (2020) further generalized this by multiplying |v|q to include sum pooling as well, but not considered the case where p is positive and the case where p is negative at the same time. GNP is the most generic norm-based pooling function, compared to all aforementioned approaches, and more importantly, no other works studied their usefulness in the context of learning to extrapolate.
Extrapolation Trask et al. (2018) pointed out that most of the feed-forward neural networks fail to extrapolate even for the simplest possible identity mapping, and suggested using alternative computation units mimicking the behavior of arithmetic logic units. The ability to extrapolate is also important in the GNN context, for instance, many combinatorial optimization problems involving graphs often require extrapolation. Selsam et al. (2019); Prates et al. (2019) tackled the extrapolation problem by performing large iterations of message passing. Using various classical graph algorithms, Veličković et al. (2020) showed that the extrapolation performance of GNNs depends heavily on the choice of the aggregation function. Similarly, Xu et al. (2021) demonstrated that choosing the right non-linear function for both MLPs and GNNs is crucial for the extrapolation.

heading: 3 MAIN CONTRIBUTION: GENERALIZED NORM-BASED POOLING
text: In this section, we present our Generalized Norm-based Pooling (GNP) and discuss its expressiveness. Then, we describe some difficulties in training GNP and our remedy. Lastly, we present a task on which a GNN with GNP can extrapolate, while that equipped with the basic pooling functions cannot.

heading: 3.1 GENERALIZATION OF BASIC POOLING FUNCTIONS
text: While GNP is motivated by the Lp-norm function, which includes the sum and max functions as special cases, further ingredients are added to make GNP more flexible than the Lp-norm function. Specifically, we allow p to be negative to let GNP express a wider class of functions than the previous norm-based or learning-based pooling functions.
Let V = {vi}ni=1 be a set of node features with vi ∈ Rd for i = 1, . . . , n. We define GNP to be an element-wise function where the output for each jth element is
GNPj(V) = 1
nq ( n∑ i=1 |vi,j |p )1/p ,
where p ∈ R \ {0} and q ∈ R are learnable parameters. GNP includes the basic pooling functions (sum, mean, max, and min) as special cases.
Proposition 1. Suppose all the entries of v are non-negative in equation 3.1. Then, GNP includes sum, max, mean as special cases. If we further restrict v to be positive, GNP includes min.
Proof. GNPj(V) is equivalent to elementwise sum when (p, q) = (1, 0) and elementwise mean when (p, q) = (1, 1). When q = 0, we have
lim p→∞ GNPj(V) = max i vi lim p→∞ ( n∑ i=1 ( |vi,j | maxi |vi,j | )p)1/p = max i |vi,j | · 1 = max i |vi,j |, (1)
so GNP converges to max. Similarly, we can obtain min as a limit for p→ −∞.
3.2 HANDLING OF NEGATIVE p
The GNP function in equation 3.1 is not continuous and even not defined at p = 0. Hence, directly learning GNP in the original form as in equation 3.1 (even with p = 0 ignored) can cause instability, especially when an algorithm is trying to move from a positive p value to a negative p value. Instead, we suggest splitting the GNP function into two parts, GNP+ with positive p and GNP− with negative p, and let the model choose the right balance between them. Specifically, define
GNP+j (V) = 1
nq+ ( n∑ i=1 |vi,j |p + )1/p+ , GNP−j (V) = 1 nq− ( n∑ i=1 |vi,j |−p − )−1/p− , (2)
where p+ > 0, q+, p− > 0, and q− are learnable parameters. Given a set of node features V, we first split the feature dimension into two, and compute the output from GNP+ for the first half and from GNP− for the second half. Then we mix two outputs with a single linear layer to get the final output.
y = [ GNP+1 (V) . . . GNP + bd/2c(V) GNP − bd/2c+1(V) . . . GNP − d (V) ] , (3)
GNP(V) = Wy + b, (4)
where b·c is the floor function, W ∈ Rd×d and b ∈ Rd are learnable parameters. Note that widelyused GNN layers have a linear layer or MLP after message-passing between nodes. Instead of using an additional linear layer, GNP concatenates the outputs of GNP+ and GNP− and passes them to the linear layer or MLP. Therefore, we have only four extra parameters (p+, p−, q+ and q−) for each GNN layer of typical GNN architectures. With this design, GNP can easily switch between positive p and negative p, choosing proper values according to tasks.

heading: 3.3 STABILIZATION OF TRAINING PROCESSES
text: Unfortunately, even with the above design to split the positive and negative parts, GNP still suffers from a training instability issue. In this section, we introduce our remedy for such an issue. With our remedy, as we will empirically demonstrate, GNP can be applied to arbitrarily complex deep GNNs as a drop-in replacement for the existing pooling functions.
Negative or near-zero inputs GNP first processes inputs to be non-negative values by taking absolute values. In practice, in many GNN architectures, inputs are passed through ReLU before being fed into the pooling functions, so in such a case, we do not explicitly take the absolute values. If not, we explicitly put the ReLU activation function before every GNP to make inputs non-negative.
For the positive part of GNP, when the inputs are close to zero, the gradient w.r.t. the parameter p+ may be exploded, as one can see from the following equation.
∂GNP+j (V) ∂p+ = GNP+j (V) p+ − log(GNP+j (V)) + ∑ni=1 vp+i,j log(vi,j)GNP+j (V)p+  .
Hence, we add a small tolerance term to every input element to prevent gradient explosion. This works well for positive p, but we need more care for negative p. When p is negative, even small can be amplified by the term (vi,j + )p − to dominate the other values. Hence, when a specific input vi,j is smaller than , we replace it with 1/ to mask out the effect of that input for the output computation. An exceptional case is when every input element is below . For such a case, we fix the output of GNP to be zero by default.
ṽi,j = { vi,j + if vi,j > 1/ otherwise ,
GNP−j (Ṽ) =
{ 0 if vi,j < ε for i = 1, . . . , n
1 nq− (∑n i=1 ṽ p− i,j )1/p− otherwise
.
Even with these treatments, still, the algorithm can diverge especially when p is large. To resolve this, we clipped all p values to be contained in [0, 50] and used the log-sum-exp trick. That is,
GNPp + j (V) = 1
nq+ exp
( 1
p+ log ( n∑ i=1 exp(p+ log(vi,j + )) )) .
Also, similar to Gulcehre et al. (2014), we reparameterized p+ and p− with the softplus activation function, i.e., p+ = 1 + log(1 + exp(t+)) for some t+ ∈ R. Another important trick was to use different learning rates for training (p+, p−) and (q+, q−). Since the parameters (q+, q−) have much larger impact on the GNP, if we use the same learning rates for (p+, p−) and (q+, q−), the model can converge to unwanted local minimum that are not faithfully tuned for (p+, p−). Hence, we used larger learning rates for (p+, p−) to balance training.

heading: 3.4 EXTRAPOLATION ABILITY OF GNP
text: As stated in Theorem 1, we prove that a GNN equipped with GNP can extrapolate on the harmonic task, which we define in Section 4.2. However, that equipped with the basic pooling functions cannot extrapolate on the task, as we show empirically in Section 4.2 and theoretically in Appendix A.
Theorem 1. (Informal) Assume all the nodes in G have the same scalar feature 1. Then, a one-layer GNN equipped with GNP and trained with squared loss in the NTK regime learns the harmonic task function, and thus it can extrapolate.
Proof. See Appendix A for detailed analysis.

heading: 4 EXPERIMENTS
text: In this section, we review our experiments on various extrapolation tasks.

heading: 4.1 EXPERIMENTAL SETUPS
text: Machines We performed all experiments on a Linux server with RTX 3090 GPUs.
GNN models For graph-level tasks, we used one GIN (Xu et al., 2019) layer with a hidden dimension of 32 and two FC layers as MLP, and we fed only the outputs of the GIN layer into the readout function. Note that this simple model is expressive enough for obtaining exact answers to all considered graph-level tasks. For node-level tasks, we used three of the aforedescribed GIN layers, without readout functions, so that nodes at most three hops away from the target node can be taken into consideration. For set-level tasks, we used one FC layer with a hidden dimension of 32 before the pooling function and used another FC layer for the final output after the pooling function.
Baseline Commonly for all tasks, we considered sum, max, mean, and min, all of which are generalized by GNP, as baseline aggregation and/or readout functions. For graph-level tasks, we additionally considered SortPooling (Zhang et al., 2018) with k = 20 and Set2Set (Vinyals et al., 2015) as baseline readout functions, and we considered the hierarchical pooling version of SAGPool (Lee et al., 2019b) as a whole as a baseline model. For set-level tasks, we additionally considered Set2Set (Vinyals et al., 2015) as a baseline pooling function and Set Transformer (Lee et al., 2019a) as a whole as a baseline model.
Evaluation We compared evaluation metrics on the test set when validation loss was minimized, and in each setting, we reported mean and standard deviation over 5 runs, unless otherwise stated.

heading: 4.2 EXTRAPOLATION PERFORMANCES ON GRAPH-LEVEL TASKS
text: In this section, we consider three graph-level tasks. Given a graph, the first task is to find the maximum node degree (maxdegree), and the second task is to compute the harmonic mean node degree divided by the number of nodes (harmonic). The last task is to compute the inverse of the number of nodes (invnode), which does not depend on the topology of the given graph. For details of the synthetic datasets we used, see Appendix B.1.
For maxdegree, whose objective is maxv∈V (∑ u∈N(v)1 ) , where N(v) is the set of neighbors of v, the reasonable choice is to use sum and max as aggregation and readout functions, respectively, For harmonic, whose objective is ( ∑ v∈V ( ∑ u∈N(v)1)
−1)−1 the reasonable combination of aggregation and readout functions are sum and GNP with (p, q) = (−1, 0), respectively. For invnode, whose objective is ( ∑ v∈V 1
−1)−1, any of mean, max, and min is reasonable as the aggregation function, and GNP with (p, q) = (−1, 0) is reasonable as the readout function. We trained all models for 200 epochs, and we compared their test MAPE1 for evaluation in Figure 1. GIN with GNP showed near-perfect extrapolation performances on all three tasks, and especially for harmonic and invnode, GIN with GNP was the only successful model. Among the 16 combinations of sum, max, mean, and min, using sum and max as the aggregation and readout functions, respectively, showed near-perfect extrapolation performance on maxdegree. For the same task, another combination (mean,max) showed reasonably good performance. For the other tasks, however, none of the 16 combinations was successful. SortPool and Set2Set as the readout function were tested, while fixing the aggregation function to the aforementioned reasonable one for each task. While they performed almost perfectly for maxdegree, they failed at the other tasks. Lastly, SAGPool was not successful in any of the tasks.
We also tested the extrapolation performance using large test graphs with distinctive structures. As seen in Table 1, GIN with GNP showed near-perfect performance only except for harmony on random trees, and maxdegree on ladder graphs. Especially, on invsize and harmony, it significantly outperformed the best baseline. We further tested the extrapolation performance of GNP and the baseline approaches using real-world graphs in Appendix C.1, graphs with different structures in Appendix C.2, graphs with different node feature distributions in Appendix C.3, and various activation functions in Appendix C.4.

heading: 4.3 EXTRAPOLATION PERFORMANCE ON NODE-LEVEL TASKS
text: We further evaluated the extrapolation performance of GNP on two node-level tasks considered in Veličković et al. (2020). The first task is to decide whether each node is within 3 hops from the target node or not. (bfs). We formulate the task as a regression problem and the label is 1 within 3 hops and 0 outside 3 hops. The second task is to find the minimum distance from each node to the target node on a graph with non-negative weights (shortest). Only the nodes within 3 hops from the target node were taken into consideration. As discussed in (Veličković et al., 2020), one of the optimal models for the tasks imitates the parallel breadth-first search and the parallel Bellman-Ford algorithm (Bellman, 1958) for bfs and shortest, respectively. In such cases, the reasonable aggregators for bfs and shortest are max and min, respectively.
1MAPE scales the error by the actual value, and it has been considered as a proper measure of extrapolation performance (Xu et al., 2021).
We considered five GINs equipped with sum, max, mean, and min, and GNP, respectively, as aggregation functions. Note that the readout operation is not used for node-level tasks. For description of the datasets, see Appendix B.2. We trained all of them for 100 epochs for bfs and for 200 epochs for shortest; and we compared their test MAE2 in Table 2. GNP and all baseline methods were near perfect on bfs, regardless of graph types, and GNP was second best on shortest. As expected, GIN with min performed best on shortest.

heading: 4.4 EXTRAPOLATION PERFORMANCE ON SET-RELATED TASKS
text: We also applied our proposed approach to three set-related tasks. They are all related to estimating posterior distributions when the likelihood function is Gaussian. Specifically, the tasks are to find closed-form posterior hyperparameters µpost and σ2post, the MAP estimate µ̂MAP of µ when σ
2 is known, and the MAP estimate σ̂2MAP if σ
2 when µ is known. Note that ground-truth values of µpost and µ̂MAP are identical, while we used different loss functions for them. For description of the datasets, see Appendix B.3.
We trained for 300 epochs (a) the basic model (see Section 4.1) with GNP, (b) Set Transformer (Lee et al., 2019a) (c) the basic and deep3 models with one among sum, max, mean, min, and Set2Set (Vinyals et al., 2015). We compared their MAPE in Table 3. The basic model equipped with GNP showed near-perfect extrapolation performance on all four tasks, even though the formula for σ̂2MAP cannot be exactly expressed by GNP, and it was the only such model. For µpost and µ̂MAP, whose ground-truth values are approximated by the average of the elements, Set Transformer and those equipped with mean or Set2Set were comparable to the basic model with GNP, while they were not on the other tasks.
2MAPE was not applicable since the ground-truth value for some nodes can be 0. 3The deep model has an additional FC layer before the pooling function.

heading: 4.5 EMPIRICAL BEHAVIOR OF GNP
text: As we discussed in Section 3, GNP generalizes sum, max, mean, and min. In order to confirm the facts experimentally, we showed in Figure 2 how the learnable parameters p and q in GNP changed during training. For maxdegree, GNP as aggregation and readout functions approximated sum (i.e., p+ ≈ 1 and q+ ≈ 0) and max (i.e., p+ 1 and q+ ≈ 0), respectively, which performed best on the task. For µpost and shortest, GNP approximated mean (i.e., p+ ≈ 1 and q+ ≈ 1) and min (i.e., p− 0 and q− ≈ 0), respectively, which were the best performing baseline for the tasks. To sum up, empirically, GNP imitated the ideal pooling functions for each task if such pooling functions exist. We also observed that either GNP+ or GNP− tends to dominate the other side in all considered graph-level tasks. Detailed results are provided in Appendix C.6.

heading: 4.6 ABLATION STUDY: EFFECTIVENESS OF GNP−
text: In order to demonstrate the effectiveness of GNP− for extrapolation, we compared the model equipped only with GNP and the model only with GNP+ on each of three tasks (harmony, shortest, and σ2post) in Table 4. The detailed settings for each task were the same as in previous experiments. The model only with GNP+ performed well only on the task for σ2post. The extrapolation performance of GNP degraded significantly without GNP− on harmony and shortest.

heading: 4.7 EFFECTIVENESS OF GNP ON REAL-WORLD TASKS
text: Graph classification We compared the graph classification accuracy of hierarchical SAGPool (Lee et al., 2019b) and ASAPool (Ranjan et al., 2020), and their variants with GNP. For the variant of SAGPool, we replaced all pooling functions before, inside, and between graph pooling operations. For the variant of ASAPool, we replaced all pooling functions except for those inside LEConv. Since we used GNP, instead of the concatenation of global average pooling and max pooling functions, the input dimension of the first fully-connected layer after them was reduced by half. For the variants, except for the additional hyperparameters of GNP, all hyperparemters were set the same.
We used three datasets from TUDataset (Morris et al., 2020). D&D (Dobson & Doig, 2003; Shervashidze et al., 2011) and PROTEINS (Dobson & Doig, 2003; Borgwardt et al., 2005) contain protein-interaction graphs, and NCI1 (Wale & Karypis, 2006) contains the graphs representing chemical compounds. For consistency with the original SAGPool, we performed 10-fold cross validation with 20 different random seeds. For ASAPool, we performed 10-fold cross validation with the 20 random seeds specified in its implementation. We report the test accuracy with standard deviation in Table 5. SAGPool and ASAPool equipped with GNP consistently outperformed the original models with a carefully chosen pooling functions.
Influence maximization We compared the performance of MONSTOR (Ko et al., 2020) and its variants with GNP on the influence maximization task (Kempe et al., 2003), which has been extensively studied due to its practical applications in viral marketing and computational epidemiology. The objective of the task is to choose a given number of seed nodes so that their collective influence (i.e., degree of spread of information through a given social network) is maximized.
For experimental details, we followed (Ko et al., 2020): (a) we used three real-world social networks with up to 85, 202 edges (Extended, WannaCry, and Celebrity) with three kinds of realistic activation probabilities (BT, JI, and LP), (b) we used the same training methods and hyperparameters except for the additional parameters of GNP, and (c) we compared MONSTOR and its variants in an inductive setting. For example, we used the model trained using the Celebrity and WannaCry datasets to test the performance on the Extended dataset. For details of the influence maximization problem, MONSTOR, and the real-world social networks that we used, see Appendix E.
We performed three runs and reported the influence maximization performance with standard deviations in Table 6. As seen in the results with sum and max aggregations, the performances heavily depended on the choice of the aggregation function. In most of the cases, MONSTOR equipped with GNP outperformed the original MONSTOR with max aggregation and also a variant of MONSTOR with sum aggregation.
Two additional tasks The experimental results on node classification and graph regression are provided in Appendix C.7. For node classification, we used a real-world graph with over one million edges and compared the accuracy of GCN and GAT, and their variants with GNP. For graph regression, we compared the MAE of PNA (Corso et al., 2020) and its variants with GNP.

heading: 5 CONCLUSION
text: In this work, we proposed GNP, a learnable norm-based pooling function that can readily be applied to arbitrary GNNs or virtually to any neural network architecture involving permutation-invariant pooling operation. The key advantages of GNP are its generality and ability to extrapolate. We showed that GNP includes most of the existing pooling functions and can express a broad class of pooling functions as its special cases. More importantly, with various synthetic and real-world problems involving graphs and sets, we demonstrated that the networks with GNP as aggregation or readout functions can correctly identify the pooling functions that can successfully extrapolate. We also introduced some non-trivial design choices and techniques to stably train GNP. The limitation of our work is that, although we have empirically demonstrated the excellent extrapolation performance on various tasks, we have not developed theoretical arguments regarding under what condition models constructed with GNP will extrapolate well. It would be an interesting future work to rigorously study the class of problems that GNP can solve.

heading: REPRODUCIBILITY STATEMENT
text: We provided the source code used in our experiments in main paper, including the implementations of GNP and the GIN model, in the supplementary materials. The provided supplementary matarials also include example synthetic datasets and the pretrained weights used in our experiments.

heading: A THEORETICAL ANALYSIS (RELATED TO SECTION 3.4)
text: Similarly to Xu et al. (2021), we present an analysis of the extrapolation ability of GNNs with our GNP pooling function. Specifically, we show that a one-layer GNN with the GNP pooling function can extrapolate on the harmonic task. Let f(θ, G) be a one-layer GNN defined as follows:
f(θ, G) = W (2) GNP  ∑ v∈N(u) W (1)xv  u∈V  , (5) where θ is the parameters of the GNN, G = (V,E) is the input graph, xv is the initial feature of node v ∈ V , and N(u) ⊆ V is the set of the neighbors of node u ∈ V . When two graphs G and G′ are given, the Graph Neural Tangent Kernel (GNTK) (Du et al., 2019) is computed as
GNTK(G,G′) = Eθ∼N (0,I) [〈 ∂f(θ, G)
∂θ , ∂f(θ, G′) ∂θ
〉] .

heading: A.1 FEATURE MAP OF THE GNTK
text: We first compute the GNTK for the network defined as equation 5 and derive the corresponding feature map using a general framework presented in Jacot et al. (2018); Du et al. (2019); Xu et al. (2021). Let Σ(1), Σ(2) be the covariance for the first linear layer and the second linear layer, respectively. Also, let Θ(1) be the kernel value after the first linear layer, respectively.
From the framework, Σ(1) and Θ(1) are determined as follows:[ Σ(1)(G,G′) ] uu′ = [ Θ(1)(G,G′) ] uu′ = x>u xu.
Also, Σ(2) can be computed as
Σ(2)(G,G′) = E(f(v),f(v′))∼N(0,[Λ(1)(G,G′)]vv′)
[ GNP  ∑ v∈N(u) f(v)  u∈V  GNP
 ∑ v′∈N(u′) f(v′)  u′∈V ′ ], where
[Λ(1)(G,G′)]vv′ =
( [Σ(1)(G,G)]vv [Σ (1)(G,G′)]vv′
[Σ(1)(G′, G)]v′v [Σ (1)(G′, G′)]v′v′
) = ( x>v xv x > v x ′ v
x′>v xv x ′> v x ′ v
) .
By a simple algebraic manipulation, one can easily see that the feature map φ(G) is computed as
φ(G) = c · ( GNP ( {w(k) > hv}v∈V ) ,
1 |V |q ∑ u∈V (w(k) > hu) p−1 (∑ v∈V (w(k) > hv) p ) 1 p−1 I(w(k) > hu > 0) · hu, . . . ) , (6)
where w(k) ∼ N (0, I), c is a constant, and hu is the sum of the initial features of the neighbors N(u) of node u, i.e. ∑ v∈N(u) xv .
A.2 ANALYSIS ON THE HARMONIC TASK
We analyze the extrapolation ability of GNNs on the harmonic task, whose exact functional form is given as
f?(G) = (∑ v∈V ( ∑ u∈N(v) 1 )−1)−1 . (7)
Following Xu et al. (2021), we assume linear algorithmic alignment; if a neural network can simulate a target function f by replacing MLP modules with linear functions, (i.e., the nonlinearities of the neural network is well matches with the target function, so the neural network only has to learn the linear (MLP) part), than it can correctly learn the target function, and thus can extrapolate well. With this hypothesis, we proceed as follows. We assume that a GNN is in the NTK regime, that is, the GNN is initialized in a specific way called NTK parameterization, trained via gradient descent with small step size, and the widths of the network tend to infinty. In such case, the GNN behaves as a solution to kernel regression with GNTK kernel. Then we convert the kernel regression problem into a constrained optimization problem in the feature space induced from GNTK kernel, and show that the solution for the constrained optimization problem aligns with the functional form of the harmonic task (equation 7).
We first state the following Lemma from Xu et al. (2021) showing that a NTK kernel regression solution can be viewed as a constrained optimization problem in the feature space.
Lemma 1 (Lemma 2 in Xu et al. (2021)). Suppose NTKtrain is the n × n kernel for training data, NTK(x,xi) is the kernel value between test data x and training data xi, and Y is the training labels. Let φ(x) be a feature map induced by a neural tangent kernel, for any x ∈ Rd. The solution to kernel regression
(NTK(x,x1), . . . ,NTK(x,xn)) · NTK−1trainY
is equivalent to φ(x)>βNTK, where βNTK is
min β ‖β‖2
s.t. φ(xi)>β = yi, for i = 1, . . . , n. (8)
Proof. See Xu et al. (2021).
Theorem 1. Assume all the nodes in G have the same scalar feature 1. Then, a GNN defined as equation 5 trained with squared loss in the NTK regime learns the harmonic task function (equation 7).
Proof. Assume (p+, p−, q+, q−) = (∞, 1,∞, 0). Then every output of GNP+ goes to zero regardless of inputs and GNP− aligns with the target function equation 7. The feature map of GNTK in this case can be simplified as follows:
φ(G) = c · ( GNP ( {w(k) > hv}v∈V ) ,
∑ u∈V (w(k) > hu) −2 (∑ v∈V
1
w(k) > hv
)−2 I(w(k) > hu > 0) · hu, . . . ) .
By Lemma 1, we know that in the NTK regime, the GNN f(θ, G) behaves as the solution to the constrained optimization problem equation 8 with feature map φ(G) and coefficients β. Let β̂w ∈ R be a coefficient corresponding to GNP({w>hu}u∈V ) and β̂′w ∈ R be a coefficient corresponding to the other term in φ(G). Similar to Lemma 3 in Xu et al. (2021), we can combine the effect of coefficients for w’s in the same direction. For each w ∼ Unif(unit sphere), we can define βw and β′w as the total effect of weights in the same direction with considering scaling.
βw = ∫ βuI ( w>u
‖w‖‖u‖ = 1 ) · ‖u‖ ‖w‖ P(u),
β′w = ∫ β′uI ( w>u
‖w‖‖u‖ = 1 ) · ‖u‖ ‖w‖ P(u).
Since the dimension of the input features is 1, we only need to consider two directions of w. To get min-norm solution, we compute the Lagrange multiplier as
min β̂,β̂′
∫ β̂2w + β̂ ′2 wdP(w)
s.t. ∫ GNP ( {w>hv}v∈V ) · β̂w + ∑ u∈V (w>hu) −2 (∑ v∈V 1 w>hv )−2 I(w>hu > 0) · β̂′w · hudP(w)
= (∑ u∈Vi h−1u )−1 ∀i ∈ [n],
where Gi = (Vi, Ei) is the i-th training data and w ∼ N (0, 1). By KKT condition, taking the derivative for each variable, we can get the following conditions:
β̂+ = c · n∑ i=1 λi · (∑ u∈Vi h−1u )−1 ,
β̂− = 0 β̂′+ = c · n∑ i=1 λi · (∑ u∈Vi h−1u ) · (∑ v∈Vi h−1v )−2
= c · n∑ i=1 λi · (∑ u∈Vi h−1u )−1 ,
β̂′− = 0,(∑ u∈Vi h−1u )−1 = β̂+ · (∑ u∈Vi h−1u )−1 + β̂′+ · (∑ u∈Vi h−1u )−1 ∀i ∈ [n],
where β̂+, β̂′+ are the combined weights of w’s in the positive direction, β̂−, β̂ ′ − are the combined weights of w’s in the negative direction, and c is a constant.
The above conditions can be satisfied with proper λi’s, so the model can fit all training data. Moreover, since the solution φ(G)>βNTK = (∑ u∈V h −1 u )−1 is equivalent to the functional form of the target function equation 7, GNN defined as in equation 5 can learn the harmonic task.
Below, we prove GNNs with sum-aggregation and max-readout trained with squared loss in the NTK regime cannot extrapolate well on the harmonic task. Theorem 2. Assume all nodes have the same scalar feature 1. Then, one-layer GNNs with sumaggregation and max-readout trained with squared loss in the NTK regime do not extrapolate well in the harmonic task.
Proof. The target function of harmonic task is
f?(G) = (∑ v∈V ( ∑ u∈N(v) 1 )−1)−1 ,
so in order for one-layer GNNs with sum-aggregation and max-readout of the form
MLP ( max
∑ v∈V hv
) , hv is the hidden vector for the node v,
to match the target function, MLP must learn some non-linear transform between max and the inverse function. However, as shown in Xu et al. (2021), MLP converges to a linear function along directions from the origin. Hence, there always exist domains for which the GNN cannot learn the target function.
Similarly, we can show that one-layer GNNs with sum-aggregation and min/sum/mean-readout cannot learn the target function for some domain, meaning that they cannot extrapolate.

heading: B TRAINING DETAILS
text: We used the open-source implementations of Set Transformer provided by the authors. We used the open-source implementation of SAGPool in Pytorch Geometric (Fey & Lenssen, 2019) provided by the authors with the reported hyperparameter settings. For all other models, we used the open-source implementations provided by the DGL framework (Wang et al., 2019).
For all models, we used the mean squared loss (MSE) as training and validation loss functions, unless otherwise stated. We performed a grid search to find the combination of hyperparameters that minimize the validation loss. In all experiments, we used the RMSprop optimizer (Tieleman & Hinton, 2012) to train all models with GNP, and for all baseline models, we additionally considered the Adam optimizer (Kingma & Ba, 2015) with default parameters (i.e., β = (0.9, 0.999)) and β = (0.5, 0.999).

heading: B.1 EXTRAPOLATION ON GRAPH-LEVEL TASKS (RELATED TO SECTION 4.2)
text: For each task, we generated Erdős–Rényi (Erdős & Rényi, 1960) random graphs with probabilities ranging from 0.1 to 0.9. We trained and validated our model using such graphs with at least 20 and at most 30 nodes, and we tested on such graphs with at least 50 and at most 100 nodes, following the procedure in Xu et al. (2021). We generated 5, 000 graphs for training, 1, 000 graphs for validation, and 2, 500 graphs for test. For all nodes, we used the scalar 1 as the node feature.
For further experiments with different structures, we generated 2, 500 graphs of each type among ladder graphs, 4-regular random graphs,4 random trees, expanders,5 and Barabási–Albert (BA) (Barabási & Albert, 1999) random graphs6. They all have at least 50 and at most 100 nodes.
Table 7 describes the hyperparameter search space for all graph-level tasks.

heading: B.2 EXTRAPOLATION ON NODE-LEVEL TASKS (RELATED TO SECTION 4.3)
text: We created 5, 000 graphs for training, 1, 000 graphs for validation, and 2, 500 graphs of each type for test in the way described in Section 4.2. Graphs for training and validation have at least 20 and at most 40 nodes, while those for test are larger with at least 50 and at most 70 nodes. Target nodes is sampled uniformly at random among all nodes in each graph.
For shortest, we used the scalar 0 as the feature of the target node, and used the scalar 10× |V | as the feature of the other nodes. The weight of each edge is drawn uniformly at random from U(0, 5) in training and validation graphs, and from U(0, 10) in test graphs. For bfs, we used the scalar 1 as the feature of the target node and used the scalar 0 as the feature for the other nodes. For both tasks, we added self-loop with edge weight 0 to every node.
Tables 8 describes the hyperparameter search space for all node-level tasks. 4The degree of every node is 4. 5We created Erdos-Renyi random graphs with probability 0.8, following the procedure in Xu et al. (2021). 6The number of edges to attach from a new node to existing nodes ranged from 0.05× |V | to 0.4× |V |.

heading: B.3 EXTRAPOLATION ON SET-RELATED TASKS (RELATED TO SECTION 4.4)
text: For each task, we generated 4, 000 sets for training, 500 sets for validation, and 500 sets for test. For each set, the number of elements is sampled uniformly at random from [20, 40) for training and validation sets, and from [50, 100) for test sets. For µpost, σ2post, and µ̂MAP, we sampled elements from N (µ, 12) where µ ∼ N (0, 12). For σ̂2MAP, we sampled elements N (5, σ2) where σ ∼ InvGamma(1, 15). As loss functions, we used MSE for µpost and σ2post and used the negative logarithm of the product7 of the likelihood and the prior for µ̂MAP and σ̂2MAP.
Tables 9 describes the hyperparameter search space for all set-related tasks.

heading: B.4 GRAPH CLASSIFICATION (RELATED TO SECTION 4.7)
text: For original SAGPool (Lee et al., 2019b), we used the optimal hyperparameter settings shared by the authors8. For SAGPool equipped with GNP, we used gradient clipping with a maximum gradient norm of 1000 for the parameters of GNP, and we used a different learning rate for p of GNP. For DD , PROTEINS, and NCI1, we used 1×, 20×, and 10× larger learning rates for p than the original learning rates, respectively.
7This product is proportional to the posterior probability 8https://docs.google.com/spreadsheets/d/1JXGNOCQkRHDCQqNarteYpEuWnkNzNq_
WFiQrIY276i0/edit?usp=sharing
For original ASAPool (Ranjan et al., 2020), we used the optimal hyperparameter settings shared by the authors9. For ASAPool equipped with GNP, we used a different learning rate for p and q of GNP. For DD and NCI1, we used 3e-2 and 3e-3 for the learning rate for p and q, respectively. For PROTEINS, we used 1e-1 for the learning rate for p, and 1e-2 for the learning rate for q.
B.5 INFLUENCE MAXIMIZATION (RELATED TO SECTION 4.7)
For original MONSTOR (Ko et al., 2020), we used the optimal hyperparameter settings provided in the paper. For the parameters of GNP, we used the RMSprop optimizer, and the learning rates were set to 3e-2 for p and 3e-3 for q.

heading: C ADDITIONAL EXPERIMENTS AND RESULTS

heading: C.1 GRAPH-LEVEL EXTRAPOLATION ON REAL-WORLD DATASETS (RELATED TO SECTION 4.2)
text: We further tested the extrapolation performances of GNP and baseline approaches using real-world graphs. For real-world graphs, we used D&D, PROTEINS, and NCI1, which were also used for graph classification tasks in the paper. Table 10 describes statistics of datasets. For evaluation, we ignored graphs with nodes with zero in-degrees.
In this experiment, we used a model trained using the Erdos–Rényi graphs described in Section 4.2. As seen in the Table 11, GNP showed near-perfect extrapolation performance only except for the maxdegree task on the NCI1 dataset. Even though the average number of nodes in the D&D dataset is approximately 10 times larger than that of the training dataset, the models trained with GNP performed well. One of the possible reasons for the relatively high MAPE on the NCI1 dataset is its extremely low average degree of nodes, which is roughly 2.17. Note that the training dataset contains Erdos–Rényi random graphs with edge probabilities ranging from 0.1 to 0.9.
9https://github.com/malllabiisc/ASAP
We also measured the test error of the baseline approaches, and we reported the test MAPE of the bestperforming one in Table 12. Except for the maxdegree task, there was no combination of simple pooling functions that extrapolated well. These results are consistent with the experiment results in the paper. On the maxdegree task, the second best combination (among the 16 combinations of sum, max, mean, and min) showed significantly worse extrapolation performance than the GIN model equipped with GNP.

heading: C.2 GRAPH-LEVEL EXTRAPOLATION ON GRAPHS WITH DIFFERENT STRUCTURE TYPES (RELATED TO SECTION 4.2)
text: We trained a GNN using graphs of one structure type at a time then measured extrapolation error on the other structure types. In Table 13, each row denotes the test MAPEs of the model trained using the same graph. While the model trained using ER graphs or BA graphs extrapolated well on all three tasks, the model trained using the other graphs showed poor extrapolation performance. According to Xu et al. (2021), the distribution of training graphs can affect the extrapolation performance, and this can be one of the possible reasons why the model trained using 4regular, expander, tree, ladder graphs showed poor extrapolation performance.

heading: C.3 GRAPH-LEVEL EXTRAPOLATION ON GRAPHS WITH DIFFERENT NODE FEATURE DISTRIBUTIONS (RELATED TO SECTION 4.2)
text: In the paper, we investigated the extrapolation performances in graph-level and node-level tasks on graphs with different sizes and structures. We also performed experiments on graphs with different edge feature distributions for the shortest task.
We additionally performed graph-level experiments for testing extrapolation to out-of-distribution node features. As in Xu et al. (2021), 3-dimensional node features drawn from U(0, 5) were used in training and validation data, and those drawn from U(0, 10) were used in test data.
We reported the test error in Table 14. As shown in the table, the error was slightly larger than that in the original settings without node features. However, the error was still reasonably low, and GNP outperformed baseline approaches especially on the invsize and harmonic tasks.

heading: C.4 GRAPH-LEVEL EXTRAPOLATION WITH VARIOUS ACTIVATION FUNCTIONS (RELATED TO SECTION 4.2)
text: We performed an additional graph-level experiment with a variant of GNP for handling negative inputs and a wider range of activation functions. Since the original GNP can only take non-negative inputs, we replaced ReLU to the absolute function for processing the inputs and then used an activation function. We considered ReLU, ELU, and LeakyReLU as the activation function. We compared the extrapolation error in each setting in Table 15, and GNP with the aforementioned changes showed performance comparable to original GNP.

heading: C.5 TEST MAPE ON GRAPH-LEVEL TASKS (RELATED TO SECTION 4.2)
text: In Table 16, we reported test MAPEs and standard deviations for all 19 competitors and GNP on the graph-level tasks.
C.6 BEHAVIORS OF GNP+ AND GNP− FOR GRAPH-LEVEL TASKS (RELATED TO SECTION 4.5)
We analyzed the behavior of the negative GNP on three graph-level tasks that we performed in the paper. In all experiments, we found that either GNP+ or GNP− tends to dominate the other side. To validate the observation, we masked the output of GNP+ and GNP− for readout to 0 on the graph-level tasks.
As seen in Table 17, masking the output of GNP− on the maxdegree task and masking the output of GNP+ on the other tasks do not significantly affect the extrapolation performance. When we masked the opposite part of GNP, however, the test MAPE was near 100. These results imply that the effect of the dominated part on the output of the model is negligible. That is, when the optimal pooling function is max, the negative GNP has almost no effect on determining the output. Similarly, when the optimal function is GNP with (p, q) = (−1, 0), the positive GNP has almost no effect on determining the output.

heading: C.7 EFFECTIVENESS OF GNP ON NODE CLASSIFICATION AND GRAPH REGRESSION (RELATED TO SECTION 4.7)
text: Node classification To show the scalability of GNP to million-scale graphs, we performed node classification on the OGBN-Arxiv dataset (Hu et al., 2020), which contains 169, 343 nodes and 1, 166, 243 edges. We compared the node classification accuracy of GCN (Kipf & Welling, 2017)
and GAT (Veličković et al., 2018), and their variants equipped with GNP. For implementations, we used open source implementations: GCN+linear+labels10 and GAT+FLAG11. For the ones with GNP, since those implementations do not contain a linear layer after the last message-passing between the nodes, we used an additional linear layer only for the last GNN layer. The increase in the number of parameters is negligible compared to the total number of the parameters (see Table 18a). For GAT with GNP, we reduced the hidden dimension from 256 to 128.
We performed 10 runs for each model with the designated train/val/test split and reported the test accuracy and the standard deviation. As seen in Table 18a, GCN with GNP and GAT with GNP showed slightly better accuracy compared to the original models.
Graph regression We compared the graph regression performance of PNA (Corso et al., 2020) and its variant with GNP. We replaced all max, sum, mean and min aggregation in PNA with GNP. We used the ZINC (Irwin et al., 2012) dataset and performed experiments with and without edge features. For the implementation and the hyperparameters, we followed the implementation by the authors.12
We performed 5 runs for each model with the designated train/val/test split and reported the test MAE and the standard deviation in Table 18b. Without edge features, PNA equipped with GNP outperformed the original model. With edge features, however, the original model showed slightly lower test MAE than PNA equipped with GNP.
10https://github.com/dmlc/dgl/tree/master/examples/pytorch/ogb/ogbn-arxiv 11https://github.com/devnkong/FLAG 12https://github.com/lukecavabarrett/pna

heading: D CLOSED-FORM SOLUTIONS FOR SET-RELATED TASKS (RELATED TO SECTION 4.4)
text: In Table 19, we provided the closed-form solutions for each task.

heading: E DETAILS ABOUT INFLUENCE MAXIMIZATION AND MONSTOR (RELATED TO SECTION 4.7)
text: Influence Maximization (IM) (Kempe et al., 2003) is one of the most extensively studied NP-hard problems on social networks due to its practical applications in viral marketing and computational epidemiology. The goal of the problem is to choose a given number of seed nodes (i.e., a set of initially activated nodes) that maximize the influence through a given graph under a diffusion model. In this experiment, we used the Independent Cascade (IC) model as the diffusion model. In the IC model, each link (u, v) has an activation probability puv. When a node u is newly activated and a neighbor v is not activated yet, the node u has exactly one chance to activate the node v with the probability puv, and the diffusion process ends when every activated node fails to activate any new node. In the model, the influence is the number of activated nodes after the diffusion process ends.
MONSTOR estimates the influence given a graph and a seed set. To train the model, we generated a dataset consisting of pairs of an input graph and a set of randomly chosen seed nodes. To generate ground-truth answers, we ran 10, 000 Monte-Carlo simulations and recorded the probability πu,i that each node u is activated until the i-th step. We first trained the base model M to estimate πi given πi−1, . . . , πi−d. MONSTOR is constructed by stacking s times the base model M , and s is chosen to minimize squared loss between the ground-truth influences and the estimated influences on the validation set. Since influence maximization is a submodular maximization problem, we used UBLF (Zhou et al., 2013) or CELF (Leskovec et al., 2007) equipped with MONSTOR, which greedily selects seed nodes.
For the real-world datasets we used, we provided the statistics in Table 20.

heading: F CODE & DATA
text: All assets used in the paper, including the training/evaluation code and the trained models with GNP, are contained in the supplemental material. All assets we used from DGL13 (Wang et al., 2019) and Pytorch Geometric14 (Fey & Lenssen, 2019) are available under the Apache license 2.0 and MIT license, respectively. The implementation of Set Transformer15 (Lee et al., 2019a) that we used is available under the MIT License. The implementation of ASAPool16 (Ranjan et al., 2020) that we used is available under the Apache license 2.0. For the other assets, we were unable to find their licenses. For the SAGPool (Lee et al., 2019b) implementation in Pytorch Geometric, the dataset generators for the graph-level and node-level tasks (Xu et al., 2021), and the MONSTOR (Ko et al., 2020) implementation in DGL, we used the code on the GitHub repositories17,18,19 shared by the authors of the original papers. We accessed TUDataset20 (Morris et al., 2020) using PyTorch Geometric.
13https://github.com/dmlc/dgl 14https://github.com/rusty1s/pytorch_geometric 15https://github.com/juho-lee/set_transformer 16https://github.com/malllabiisc/ASAP 17https://github.com/inyeoplee77/SAGPool 18https://github.com/jinglingli/nn-extrapolate 19https://github.com/jihoonko/asonam20-monstor 20https://chrsmrrs.github.io/datasets/

Review summaries:
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.

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. 

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.