Learning to Pool in Graph Neural Networks for Extrapolation
Authors: Jihoon Ko
Taehyung Kwon
Kijung Shin
Juho Lee
Venue: ICLR 2022 Submitted (2022)
Keywords: Graph Neural Network
Pooling
Extrapolation

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^p$ 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 experimentally that simply using GNP for every aggregation and readout operation enables GNNs to extrapolate well on many node-level, graph-level, and set-related tasks; and GNP sometimes performs even better than the best-performing choices among existing pooling functions.



Under review as a conference paper at ICLR 2022
LEARNING TO POOL IN GRAPH NEURAL NETWORKS FOR EXTRAPOLATION
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks (GNNs) are of the most popular approaches using deep learning on graph-structured data, and they have shown state-of-the-art perfor- mances on a variety of tasks. However, according to a recent study, 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-distributinn data, while the number of possible choices grows exponentially with the number of layers. In this paper, we present GNP, 7,P 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, 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.
INTRODUCTION
Many 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 2017, Hamilton et al., 2017] Veličković (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 variety of tasks, including recommendation (Ying) ct al. 2018a), drug discovery (Stokes et al. 2020), and chip design (Mirhoseini et al. 2020).
An important design choice for 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 graph, and common choices are element-wiss summation (sum), maximum (max), minimum (min), or average (mear). Some recent works also proposed use parametric models and learn them from data well (Ying 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. (202T) studied the impact of the choice of pooling functions on the
ability of neural network to extrapolate. Specifically, [u et al. (202T) 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 -uitt--distribution data. As motivating example, consider the problem of counting the number of nodes in graph. If we are to solve this problem with 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 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 nut-of-distributio graphs
The findings in Xu et al. (202T) raise a natural question; which pooling functions should be used for given problem in order to make GNNs constructed with them successfully extrapolate for

---

Under review as a conference paper at ICLR 2022
out-of-distributtin data? Xu et al. (2021) did not present any guide but empirically showed that do have the "right" pooling function for each problem tested, and when a pooling function is not properly selected, GNNs completely fails 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 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 generic L 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-
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 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. naïve application of GNP to GNNs is likely to fail because of some difficulty in training. 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 (Kipt & Welling 2017). GAT (Veličković et al.] 2018). PNA (Corso et al. 2020 hicrarchical SAGPool (Lee et al. 2019b ASAPool (Ranjan et al. 2020), and MONSTOR (Ko et al. )020 and eight real-world
propose simple remedy to this. Using nine graph-level,
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.
2
RELATED WORK
Aggregation functions Various aggregation functions have been appeared to enhance the perfor- mance of GNNs. Hamilton et al. (2017) proposed GraphSAGE with four different aggregation methods; max, mean, GCN (Kipf & Welling 2017), and LSTM (Hochreiter & Schmidhuber 1997). Veličković et al. (0188) proposed Graph Attention ne' workss (GATs) including attention-base based aggre- gation functions (Vaswani et al. 2017). Xu et al. (2019) proposed Graph Isomorphism Networks (GINs) and proved that GNN can satisfy the 1- Weisfeiler-Lehmal (WI.) 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 hierarchical fashion (Ying) jet al. 20185; 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 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 al. (2014) proposed normalized learnable L" norm function that generalizes average pooling and max pooling, [ee et al, (2016) further extended those pooling functions with learnable tree-structured pooling filters.
2

---

Under review as a conference paper at ICLR 2022
Norm-based pooling functions There have been several works to employ bosn-based pooling functions. Gulcehre et al. (2014) proposed a learnable L norm function of the form
lv
1/p
ʃ(v) =
to substitute max pooling average pooling used in convolutional neural networks. Similar norm- based pooling functions were used for acoustic modeling (Swietojanski & Renals (0066) and text representation (Wu et al., 2020). Compared GNP, these pooling methods cannot express the sum pooling. et al. (2020) further generalized this by multiplying v/9 to include sum pooling as well, not considered the case where is positive and the case where p is negative at the same time. GNP is the most generic worm-basee 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. (0088) pointed out that most the feed-forwart neural networks fail 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 also important in the GNN context, for instance, many combinatorial optimization problems involving graphs often require extrapolation. Selsam et al. (201)); Prates et al. (2019) tackled the extrapolation problem by performing large iterations of message passing. Using various classical graph algorithms, Veličković et al. (2020) showed that the extrapolation performance of GNNs depends heavily on the choice of the aggregation function. Similarly, Xu et al. (202T) demonstrated that choosing the right non-linear function for both MIPs and GNNs is crucial for the extrapolation.
3 MAIN CONTRIBUTION: GENERALIZED NORM-BASED POOLING
In this section, we present our Generalized Norm- Pooling (GNP) and discuss its expressiveness. Then, we describe some difficulties in training GNP and our remedy. Lastly, we present task on which GNN with GNP can extrapolate, while that equipped with the basic pooling functions cannot.
3.1 GENERALIZATION OF BASIC POOLING FUNCTIONS
While GNP is motivated by the L2-norm function, which includes the smm and max functionn as special cases, further ingredients are added to make GNP more flexible than the L function. Specifically, we allow to be negative to let GNP express a wider class of functions than the previous norm-based or learning- barning-based pooling functions.
Let V = {vr)== be a set of node features with v; E Rd for 1,... I....,n. n. We define GNP to be an element-wise function where the output for each jth element is
1/P
GNP, (V)
Σ
7
where p R (0) and q R are learnable parameters. GNP includes the basic pooling functions (sum, mean, max, and mi n) as special cases.
Proposition 1. Suppose all the entries of v are non-negative in equation 3.1 Then, GNP includes sum, max, mean special cases. If we further restrict v to be positive, GNP includes min.
Proof. GNP, (V) is equivalent to elementwise sum when (p.g) q) = (1, 0) and elementwise mean when (p. (1, 1). When q O, we have
lim GNP, = max eú lim 400
Σ
Peyl maxx; [Us.s]
)")
1/P
max | -1 = max lur (1)
GNP converges Similarly, can obtain mi limit for

---

Under review as a conference paper at ICLR 2022
3.2 HANDLING OF NEGATIVE p
The GNP function in equation 3.1 is not continuous and even not defined at 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 value to a negative value. Instead, we suggest splitting the GNP function into two parts, GNP with positive p and GNP with negative and let the model choose the right balance between them. Specifically, define
1/p
1/pp"
GNP)
GNP, (V)
[G.5 P
12
72
where p+ > 0, 0.. pT
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 [NPP(()
GNP [d/2] (V) GNP d/2]++1 (V)
GNP (V)]
(3)
GNP(V) Wy -b, b,
(4)
where 1-] is the floor function, W E Rdddd and b E R' are learnable parameters. Note that widely- used GNN layers have linear layer or MLP after pessage-passingg 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 qt and gT) for each GNN layer of typical GNN architectures. With this design, GNP can easily switch between positive and negative p. choosing proper values according to tasks.
3.3 STABILIZATION OF TRAINING PROCESSES
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, will empirically demonstrate, GNP 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 ReLÚ before being fed into the pooling functions, in such case, we do not explicitly take the absolute values. not, we explicitly put the ReLU activation function before every GNP to make inputs non-nen non-negative.
For the positive part of GNP, when the inputs are close zero, the gradient w.r.t. the parameter p" may be exploded, as one can see from the following equation.
aGNP) GNP) (V) Opt
EL Lif log(ve.) GNP (V).t
- log(GNN + (V))
p+
Hence, we add small tolerance term e to every input element to prevent gradient explosion. This works well for positive p. but we need more care for negative p. When is negative, even small can be amplified by the term (va. + e) input vÚj is smaller than e, we replace it with 1/c to mask out the effect of that input for the output computation. An exceptional case is when every input element below e. For such case, we fix the output of GNP to be zero by default.
dominate the other values. Hence, when specific
Vi.j +e if Ui > 1/e
Üi
otherwise
{
if Ui. < for Iy...,m
GNP, (V)
1/8
EE
otherwise
no-
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,
exp(p* log(vis + (11) =1))
GNP (V)
= not
cxp
log
4

---

Under review as a conference paper at ICLR 2022
Table Extrapolation performance in terms of MAPE on large graphs with different structures. two tasks (invsize and ha harmonic,, GNP significantly outperformed the second best one.
invsize
heronic
maxdegree
Types
Best Baseline (sum, max)
Best Bascline (SAGPool)
Best Baseline (sum, max)
GNP
GNP
GNP
BA
0.3
10.5=
2.9
78.41140.8
2.1:1.11
0.0::0.0
Expander
1.
35,417.8
0.9
11.9118.6
2.3:1.11
0.0:10.0
4regular
0.3
205.6136.88
1.91:33
1179.3-310.6
3.443.7
0.0=0,00
Tree 0.3
202.3+11.9
14.7+16.3
149,4+34499
1.9+0.6
0.0::0.0
Ladder
0.3
593.41133.6
2.4:22.4
1138.41:23.3
30.7+16.99
0.1:10.1
2014), we reparameterized pt and pT with the softplus activation function, i.c., p² log(111 exp(t*))
Also, similar to Gulcehre et al.
)) for some t+ E I.
Another important trick was to use different learning rates for training (p*,p") and (at,0") (T) Since the parameters (q".9)) have much larger impact on the GNP, we use the same learning rates for (p+ ,PT) and (9*.))) the model can converge to unwanted local minimum that not faithfully tuned for (p*, ,p"). Hence, we used larger learning rates for (p* .p .p") to balance training.
3.4 EXTRAPOLATION ABILITY OF GNP
As stated in Theorem [ we prove that GNN equipped with GNP can extrapolate on the harmon 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 ha rmonic task function, and thus it can extrapolate.
Proof. See Appendix A for detailed analysis.
4
EXPERIMENTS
In this section, we review our experiments on various extrapolation tasks.
4.1 EXPERIMENTAL. SETUPS
Machines We performed all experiments on Linux server with RTX 3090 GPUs.
GNN models For graph-level tasks, we used one GIN (Xu et al. 2019 layer with 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 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, considered sum, max, mean, and mi n, 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 20 and Set2Set (Vinyals et al. 2013) as baseline readout functions, and we considered the hierarchical pooling version of SAGPool (Lee al., 2019b) whole 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) whole 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.
5

---

Under review as a conference paper at ICLR 2022
GNP (Proposed)
(sum, max)
(sum, mean)
SortPooling
SAGPool
100
100
MAPE
75-
Test MAPE
75-
Test
50
30
50-
60-
20
25-
50
60
70
80
90
100
50
60
70
80
90
100
50
60
70
80
90
100
Number of nodes
Number nodes
Number nodes
(a) Lnvsize
(b) harmonic
(c) maxdegree
Figure 1: Extrapolation performances depending on the number of nodes test graphs on three tasks
(invsize i harmon and ma maxdegree) Only GIN equipped with GNP performed consistently well on all the tasks. We tested 19 competitors and reported the results of the most successful ones.
4.2 EXTRAPOLATION PERFORMANCES ON GRAPII-LEVLL TASKS
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 (harmont rmonic). 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 max.ev (c)) where N()) 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 (Erev() (vve((ueN()))) - the reasonable combination of aggre- gation and readout functions are sum and GNP with (p, 1) (-1, 0). respectively. For i nvnode, whose objective (Eeev 1-1)-1 1111 any of mean, max, and m n is reasonable as the aggregation function, and GNP with (p.g) (-1,0) is reasonable as the readout function.
We trained all models for 200 epochs, and we compared their test MAPE for evaluation in Figure GIN with GNP showed near-perfect extrapolation performances all three tasks, and especially for harmniic c and invnode, GIN with GNP was the only successful model. Among the 16 combinations of sum, max, mean, and min, using sum and max the aggregation and readout functions, respectively, showed near-perfect extrapolation performance on ma 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 [ GIN with GNP showed near-perfee performance only except for harmony on random trees, and maxdegree on ladder graphs. Especially, on invs i ze and ha rmony, 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.I 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
4.3 EXTRAPOLATION PERFORMANCE ON NODE-LEVEL TASKS
We further evaluated the extrapolation performance of GNP on two node-level tasks considered in Veličković et al. (2020). The first task is to decide whether each node is within 3 hops from the within 3
target node or not (bfs). We formulate the task as a regression problem and the label 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 hops from the target node were taken into consideration. As discussed in (Veličković et al. 2020). one of the optimal models for the tasks imitates the parallel breadth- first search and the parallel Bellman-Fool algorithm (Bellman 1958) for bfs and shortest, respectively. In such cases, the reasonable aggregators for bfs and shortest. are max and min, respectively.
'APPE scales the error by the actual value, and it has been considered as proper measure of extrapolation
performance (u et al. 2021

---

Under review as a conference paper at ICLR 2022
Table 2: Extrapolation performances in terms of MAE on two node-level tasks (shortest and fs).
GNP and all baseline methods were near perfect on bfs; GNP was second best shortest.
Aggregation
sum
max
mear
min
GNP
bfs
0.000+0.000 0.000
1.000+0.000
0.000+0.000
0.000000.000
2.000+0.000
shortest
0.323+0. 162
0. 0.362
1.316
0.141 0.007
0.332++.1105
(a) Extrapolation Performance on Large Graphs with Homogeneous Structures.
b
shortest
Types
GNP
max
GNP
min
maxX
BA
0.001+0..00
0.000=0.000
0.5466+00.16
0.275=0.005
1.268=00642
Expander
0,00011.0000
0.000=10,000
0.159-10.068
0.019-0.004
0.33410.225
4regular
0.003-1:0003
0.000=10,000
1.0277
1.188=0.182
5.178=1.2118
Tree
0.003-4:00002 0.000=00000
1.579:1:0.899
1.657=0.256
4.584=00980
Laddex
0.002:+:0001
0.000=0.000
1.2177+0.278
0.701=0.160
3.400=110056
(b) Extrapolation Performance Large Graphs with Heterogeneous Structures.
Table 3: Extrapolation performance in terms of MAPE on set-related tasks. Only the basic model equipped with GNP performed consistently well on all tasks. Especially for post and MAP- significantly outperformed all competitors, including Set Transformer.
Model
Pooling
Mpust
post
ĀMAP
22 MAP
135.0 + 9.3
390.7 + 99.1
126.8 + 18.2
369.1 + 12.1
max
119.2 31.7
120.6 +: 4.0
118.6 08.6:316
108.8 + 2.0
Basic
1.9 0.2
134.2 1:.2::00 6.0
1.9 + 0.2
107.1 1: 2.2
m1 n
95.8 15.6
126.2 3.9
31.6
108.0 + 2.4
Set2Set
2.1
135.7 + 4.0
1.9 + 0.2
106.1 + 2.6
61mm
136.3 +
119.3 + 16.1
100.0 0.0
381.9 10.8
max
100.0 +: 0.0
123.8
98.9
109.6 +
Deep
mean
2.2
135.2 4.0
2.2 0.4
109.2 +
min
83.0 10.2
99.5
90.8 +0.8+6600 6.0
108.8 +
Set2Set
1.9
131.1
1.9 0.2
106.0 +
Set Transformer
1.9 + 0.2
25.0 1: 9.0
1.9 - 0.1
40.8 1: 9.5
Basic
GNP
1.5 0.6
0.7 0.3
1.5 + 0.6
3.1 0.5
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 MAI in Table 2 GNP and all baseline methods were perfect on bfs, regardless of graph types, and GNP was second best shortest. As expected, GIN with min performed best on shortest.
4.4 EXTRAPOLATION PERFORMANCE ON SET-RELATED TASKS
We also applied our proposed approach 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 Mpoost and 2 the MAP estimate ÁMAP of μ when o² is known, and the MAP estimate &aA o² when ja is known. Note that ground-truth values of upoa and MMAP identical, while 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 2019 (c) the basic and deep d models with one among smm, max, mean, mi n, and Set2Set (Vinyals 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 0ZAP cannot be exactly expressed by GNP, and was the only such model. For Mlposa 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.
MAPE was not applicable since the ground-truth value for some nodes can be 0.
"The deep model has an additional FC layer before the pooling function.
7

---

Under review as a conference paper at ICLR 2022
2.00
40
1.00
2.00
+ +1.00
50
1.75
0.4
1.75
0.75
40
Pr
0.75
p+ 1.50
1.25
qt p+ 20-
P
0.50 q+ p+
q
P-
20
30-
0.50
0.25 4
1.00
0.0
10
9r
0.25
1.25
0.25
10
0.00
0.75
0
0.00
1.00
0.00
100 150
200
50 100 150 200
100 200
300
50 100 150 200
Training Epoche
Training Epochs
Training Epochs
Training Epochs
(a) sum (maxdegree)
(b) max (maxdegree)
(c) mean (Mpost
(d) min (shortest)
Figure 2: Empirical behavior of GNP. We showed how the parameters p and of GNP changed
during training. For each task, GNP imitated the ideal pooling functions if such pooling functions exist. For example, for maxdegree, GNP as aggregation and readout functions approximated sum (i.e., p 1 and g² 0) and max (i.e., p* > and qt 0), respectively, which performed best.
Table 4: Effectiveness of GNP The extrapolation performance of GNP degraded without GNP
Tasks
GNP
GNP
Graphs
GNP
GNP
harmonic
1.1 + 0.8
2.1 + 0.6
RA
2.5 + 0.9
31.5 + 1.2
shortest
0.332 + 0.105
0.774 + 0.135
tree
14.7 + 6,3
26.1 + 7.4
pon
0.7 + 0.3
0.6 + 0.2
ladder
2.4 2.4
19.3 + 21.1
(a) Test Error on Erdös Rényi Random Graphs
(b) Test Error on harmonic Other Graphs
4.5
EMPIRICAL BEнAVIOR OF GNP
As we discussed in Section 3 GNP generalizes sum, max, mean, and min. In order to confirm the facts experimentally, we showed Figure how the learnable parameters p and q in GNP changed during training. For maxdegree, GNP aggregation and readout functions approximated sum (i.e., pt x 1 and gt 2 0) and max (i.e., p+ >> 1 and g+ Rs 0), respectively, which performed best on the task. For Mposa and shortest, GNP approximated mean (i.e., p² ~ 1 and q s 1) and min (i.e.. p > and q z 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
4.6 ABLATION STUDY: EFFECTIVENESS OF GNP"
In order to demonstrate the effectiveness of GNP for extrapolation, we compared the model equipped only with GNP and the model only with GNP* each of three tasks (harmony, shortest, and of ( in Table 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 Je The extrapolation performance of GNP degraded significantly without GNP on harmony and shortest.
4.7 EFFECTIVENESS OF GNP ON
TASKS
Graph classification We compared the graph classification accuracy of hierarchical SAGPool (Lee al. 2019b) and ASAPool (Ranjan 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 connecconeetted 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 Sher vashidze et al., 2011) and PROTEINS (Dobson & Doig, 2003; Borgwardt et al. 2005) contain protein-interaction graphs, and NCI1 (alee & Karypis 2006) contains the graphs representing chem- ical 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 [ SAGPool and ASAPool equipped with GNP consistently outperformed the original models with carefully chosen pooling functions.
8

---

Under review as a conference paper at ICLR 2022
Table 5: Graph classification accuracy. Replacing the carefully chosen pooling functions in SAGPool and ASAPool with GNP improved their accuracy on graph-classification tasks.
Model
Aggregation
Readout
D&D
PROTEINS
NCI1
SAGPool (original) SAGPool (with GNP)
GCN
mean, max
0.765 + 0,009
0.722 + 0.008
0.688 + 0.013
GNP
GNP
0.774 0.010
0.728 + 0.013
0.695 0.015
(a) SAGPool
Model
Aggregation
Readout
D&D
PRCTEINS
NCI1
ASAPool (original)
GCN GNP
mean, max
0.764 + 0.009
0.738 +t 0.008
0.711 + 0.004
ASAPool (with GNP)
GNP
0.772 + 0.007
0.739 +: 0.006
0.725 + 0.007
(b) ASAPool
Table 6: Influence maximization performance. The influences of 100 seed nodes produced by MONSTOR and its variants in graphs unseen during training are reported. The variant equipped with GNP outperforms original MONSTOR (with max) and the other variant (with sum).
Aggregation
ended JI
Kannatryy JI
Calebrity JI
3T
LF
BT
LP
BT
LF
max
1222.5++0.4
706.9 9..1 620776+-077 2746.5-t114 1646.64+2.1 9090,2+338 155. 1
140.5++0.0
5665.0+:11.4
sum
1216.6+1.7
3189.2+6.9 0:6.5 2742.6:0.9 1645.840022 9030.1+2.00
153.9:10.4
140.5:10.0
5666.9:10.6
GNP
1223.01:.3 7.7.31:022 3262.1 2753.410.1 1648.311..1 9098.412222 155.310.8
140.411.00
16...111.8
Influence maximization We compared the performance of MONSTOR (Ko al. 2020) and its variants with GNP on the influence maximization task (Kempe et al., 2003), which has been extensively studied due 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 (lebritt) 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 Ce 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 F
We performed three runs and reported the influence maximization performance with standard devia- tions in T As seen in the results with sum and max aggregations, the performances heavily depended on the choice the aggregation function. In most of the cases, MONSTOR equipped with GNP outperformed the original MONSTOR with max aggregation and also variant of MONSTOR with sum aggregation.
Two additional tasks The experimental results on node classification and graph regression are provided 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 PÑA (Corso et al. 2020 and its variants with GNP.
5 CONCLUSION
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-invaiinn 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.

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
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 our experiments.
REFERENCES
Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286 55439):009-51,, 1999.
Richard Bellman. On a routing problem. Quarterly of applied mathematics, 16(1):87-90, 1958.
Karsten M. Borgwardt, Cheng Soon Ong, Stefan Schönauer, S. V. N. Vishwanathan, Alex J. Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, (suppl 1): i47-i56, 2005.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. In NewrIPS, 2020.
Paul D Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-783, 2003.
Simon Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. In NeurlPS, 2019.
Paul Erdös and Alfréd Rényi. On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 5(1):17-60, 1960.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Hongyang Gao and Shuiwang Ji. Graph u-nets. In ICML, 2019.
Caglar Gulcehre, Kyunghyun Cho, Razvan Pascanu, and Yoshua Bengio. Learned-norm pooling for deep feedforward and recurrent neural networks. In ECML/PKDD, 2014.
William L Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. NeurIPS, 2017.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 98)) 1735-1780, 1997.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.0068) 2020.
John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. Zinc: free tool discover chemistry for biology. Journal of chemical information and modeling, 52(7): 1757-1768, 2012.
Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kerne:: Convergence and generalization in neural networks. In NeurlPS, 2018.
David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through social network. In KDD, 2003.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Jihoon Ko, Kyuhan Lee, Kijung Shin, and Noseong Park. Monstor: An inductive approach for estimating and maximizing influence over unseen networks. In ASONAM, 2020.
10

---

Under review as a conference paper at ICLR 2022
Chen- Yu Lee, Patrick W Gallagher, and Zhuowen Tu. Generalizing pooling functions in convolutional neural networks: Mixed, gated, and tree. In AISTATS, 2016.
Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: A framework for attention-based permutation-invaaiiat invariant neural networks. In ICML, 2019a.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In ICML, 2019b.
Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance. Cost-effective outbreak detection in networks. In KDD, 2007.
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need train deeper gens. arXiv preprini urXiv:2006.0773, 2020.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In NeurIPS, 2019.
Azalia Mirhoseini. Anna Goldie, Mustafa Yazgan, Joe Jiang, Ebrahim Songhori, Shen Wang. Young- Joon Lee, Eric Johnson, Omkar Pathak, Sungmin Bae, et al. Chip placement with deep reinforce- ment learning. arXiv preprint arXiv:2004. /0746, 2020.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In /CML Workshop on Graph Representation Learning and Beyond, 2020. URL www. wwwphrrapheeee wamphearringg
10
Marcelo Prates, Pedro HC Avelar, Henrique Lemos, Luis C Lamb, and Moshe Y Vardi. Learning to solve up-complete problems: A graph neural network for decision tsp. In AAAI, 2019.
Ekagra Ranjan, Soumya Sanyal, and Partha Talukdar. Asap: Adaptive structure aware pooling for learning hierarchical graph representations. In AAAI, 2020.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2009.
Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David Dill. Learning sat solver from single-bit supervision. In ICLR, 2019.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
Jonathan M Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz Nina M Donghia, Craig R MacNair, Shawn French, Lindsey Carfrae, Zohar Bloom-Ackerman et al. A deep learning approach to antibiotic discovery. Cell, 180(4):688-77) -028 2020.
Pawel Swictojanski and Steve Renals. Differentiable pooling for unsupervised acoustic model adaptation. JEEE/ACM Transactions on Audio, Speech, and Language Processing, 24(10):1773- 1784, 2016.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26-31, 2012.
Andrew Trask, Felix Hill, Scott E Reed, Jack Rae, Chris Dyer, and Phil Blunsom. Neural arithmetic logic units. NeurIPS, 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NIPS, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execution of graph algorithms. In ICLR, 2020.
11

---

Under review as a conference paper at ICLR 2022
Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence to sequence for sets. In ICLR, 2015.
Nikil Wale and George Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. In ICDM, 2006.
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: graph-centric, highly-performant package for graph neural networks. arXiv preprint arXiv: 10XXv11909001115. 2019.
Chuhan Wu, Fangzhao Wu, Tao Qi, Xiaohui Cui, and Yongfeng Huang. Attentive pooling with learnable norms for text representation. In ACL, 2020.
Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Inductive representa- tion learning on temporal graphs. In ICLR, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
Keyulu Xu, Mozhi Zhang, Jingling Li, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. In ICLR, 2021.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. KDD, 2018a.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William I. Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In NeurIPS, 2018b.
Hao Yuan and Shuiwang Ji. Structpool: Structured graph pooling via conditional random fields. In ICLR, 2020.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In AAAI, 2018
Chuan Zhou, Peng Zhang, Jing Guo, Xingquan Zhu, and Li Guo. Ublf: An upper bound based approach to discover influential nodes in social networks. In ICDM, 2013.
12

---

Under review as a conference paper at ICLR 2022
A THEORETICAL ANALYSIS (RELATED TO SECTION 3.4)
Similarly Xu et al. (2021). we present 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 the harmoiic task. Let s(O, G) be one-layer GNN defined follows:
5(0, G) W( GNP
Σ (EN(")
W
(5)
NEV
where P is the parameters of the GNN, G (V, E) is the input graph, Ty is the initial feature of node v E V, and (u)) S V is the set of the neighbors of node u E
When two graphs G' and G' are given, the Graph Neural Tangent Kernel (GNTK) (Du al. 2019 is computed as
GNTK(G, G') EB-N(O.))
K 00
{
@ G) 0f(o,
00
A. FEATURE MAP OF THE GNTK
We first compute the GNTK for the network defined as equation 5 and derive the corresponding feature map using general framework presented in Jacot et al. (2018) ; Du et al. (2019); Xu et al. (202T).
Let (1), (2) be the covariance for the first linear layer and the second linear layer, respectively. Also, let ( be the kernel value after the first linear layer, respectively.
From the framework, ()) and (1) are determined as follows:
(WGGG = [ wa!
= x. Cu.
Also, 2) can be computed as
()) G') = Burostt))-NNN000coo0..
GNP
Σ f(o)
vEN(u)
UEV
GNP
Σ flo')
v'EN(u')
wev
where
( [GG)))]s me (G', G)
[ G') (G G'
x xx
x x's x x.))
(G.
x x.
By simple algebraic manipulation, one can easily see that the feature map ((G) is computed as
[NNP (1u)(t) ho ( holo
((G)=C c
1
Σ (w)( hw) hew
Σ (wo(k)) )
3 (N) he > 0) O).bu....) hu.....
(6)
V
NEV
NEV
where (h) ~ NN(O c is a constant, and h, is the sum of the initial features of the neighbors ((u) of node i.e. EveN(a) Zy.
13

---

Under review as a conference paper at ICLR 2022
A.2 ANALYSIS ON THE HARMONIC TASK
We analyze the extrapolation ability of GNNs on the harmonic task, whose exact functional form given
(I)))
(')))
Σ
Σ
NEV
uEN(2)
Following Xu et al. (021). assume linear algorithmic alignment; if neural network can simulate a target function 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 can correctly learn the target function, and thus can extrapolate well. With this hypothesis,
proceed as follows. We assume that 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 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 c task (equation 7
We first state the following Lemma from Xu et al. (2021) showing that NTK kernel regression solution can be viewed as a constrained optimization problem in the feature space.
Lemma (Lemma in Xu et al. (202I)). Suppose NTK is the n x n kernel for training data, NTK(#, ax²) is the kernel value between test data æ and training data 2t and Y is the training labels. Let ((x) be feature map induced by a neural tangent kernel, for any x E RRd. The solution kernel regression
(NTK(2;, x æI),..., (TKK (æc x..))
NTK -1
equivalent to )(x) (( BNTK, where GNIK
min ||
3
s.t. (bx;) T3 3= y/: for = 1, ,,...,n.
(8)
Proof. See Xu et al. (2021).
Theorem 1. Assume all the nodes in G have the same scalar feature 1. Then, GNN defined as equation trained with squared loss in the NTK regime learns the harmonic task function (equation
Proof. Assume (p+ "0, "==,""*;-====0 (oo, 1, xc, 0). Then every output of GNP+ goes to zero regard- less of inputs and GNP aligns with the target function equation 7 The feature map of GNTK in this case can be simplified follows:
o(G)= c GNP (fwll ho holuev).
-2 (kw hu > 0) )
Σ (k) T had WEV
-2
(k)
h
DEV
By Lemma we know that in the NTK regime, the GNN f(e.C G) behaves the solution to the constrained optimization problem equation & with feature map o(G) and coefficients B. Let B., e R be a coefficient corresponding to GNP ( ha Joev) and 3' E RR be coefficient corresponding to the other term in @GG) 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 ~ (nit sphere), we can define B., and Be, as the total effect of weights in the same direction with considering scaling.
14

---

Under review as a conference paper at ICLR 2022
Bw
/ / BuI
w
u
P(u):
|
w
/ BBud
10
|
IP()).
[00
[|]
Since the dimension of the imput features is 1, we only need consider two directions of To get min-norm solution, we compute the Lagrange multiplier as
min / By + f (ww) 3,
-2 I(w hu > ()) B'n hT)P((w)
s.t. f |GNP ((w holvev) BB Σ E(w
hu) (w))a)=
Σ VEE
w ho
Σ hw
Vi [n],
where G2 (V, E,) is the i-th training data and (). By KKT condition, taking the derivative for each variable, we can get the following conditions:
3 0_
Σ LEVi
Σn
h
0
-2
B = c. Σ
A
Σ h
Σ h
1=1
NuEV Vi
LeVV
c
Ai
Σ h
1=1
NEV.
B = 0,
Σ hw
= B+
Σ h
+
B4
Σ NEV,
h
Vi E [n],
VEEV
NEV,
where 34. 3' are the combined weights of w's in the positive direction, B_, Br are the combined weights of u in the negative direction, and is constant.
The above conditions can satisfied with proper >; so the model can all training data. Moreover, is equivalent to the functional form of the target function equation GNN defined as in equation can learn the harmonic task.
since the solution of OG) [NTK (Ewev h -1
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 sum- aggregation 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
(*(G) = Σ
VEV
N
15

---

Under review as a conference paper at ICLR 2022
so in order for one-layer GNNs with sum-aggregation and max-readout of the form
MLP
max
hy 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, shown in et et (202T) MLP converges to 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/meean-rcadou cannot learn the target function for some domain, meaning that they cannot extrapolate.
B TRAINING DETAILS
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] (019)) 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., 3 (0.9, 0.999)) and | = (0.5, 0.999).
B.1 EXTRAPOLATION ON GRAPH-LEVEL. TASKS (RELATED TO SECTION
For each task, we generated Erdós Rényi (Erdós & Ré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 least 50 and at most 100 nodes, following the procedure in Xu et al. 2221). 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 as the node feature.
For further experiments with different structures, we generated 2, 500 graphs of each type among ladder graphs, 4-reqular random graphs random trees, expanders 5 and Barabási-Albert (BA) (Barabási & Albert 1999) random graph They all have at least 50 and at most 100 nodes.
Table 7 describes the hyperparameter search space for all graph-level tasks.
B.2 EXTRAPOLATION ON NODE-LEVEL TASKS (RELATED TO SECTION 4.3
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 larger with at least 50 and most 70 nodes. Target nodes is sampled uniformly at random among all nodes each graph.
For shortest, used the scalar 0 as the feature of the target node, and used the scalar 10 x V as the feature of the other nodes. The weight of each edge is drawn uniformly at random from U 5) in training and validation graphs, and from ((, 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 every node.
Tables & describes the hyperparameter search space for all node-level tasks.
"The degree of every node is 4.
'We created Frdos-Renyi random graphs with probability 0.8, following the procedure in Xu et al. 2021
TThe number of edges attach from node to existing nodes ranged from 0.05 x |V 0.4
16

---

Under review as a conference paper at ICLR 2022
Table Search space for maxdegree, harmonic, and invs i ze tasks
Hyperparameter
Selection pool
Optimizer
RMSprop 3e-2, le-2, 3e-3 3e-2, le-2, 3e-3, le-3 1e2, le4
Learning rate for
Learning rate for the other parameters
Norm clipping
(a) Search space for GIN with GNP
Hyperparameter
Selection pool
Optimizer
Adam, Adam with - (0.5. 0.999), RMSprop
Learning rate
3e-2, 1e-2, 3e-3, 1e-3
Norm clipping
le2, 1e4 1,2
Number of iterations (for Set2Set)
(b) Search space for GIN with baseline aggregation & readout functions
Hyperparameter
Selection pool
Optimizer
Adam, Adam with 0 = (0.5, 0.999), RMSprop
Learning rate
1e 3e-3, le-3, 3e-4
Norm clipping
1e2, le4
(c) Search space for SAGPool
Table 8: Search space for bfs, shortest tasks
Hyperparameter
Selection pool
Optimizer
RMSprop 3e-2, 1e-2, 3e-3 1e-2, 3e-3, le-3 1e2, le4
Learning rate for
Leariing rate for the other parameters
Norm clipping
(a) Search space for GIN with GNP
Hyperparameter
Selection pool
Optimizer
Adam, Adam with / = (0.5, 0.999), RMSprop
Learning rate
3e-2, le-2, 3e-3, 1e-3
Norm clipping
lc2, 1e4
(b) Search space for GIN with baseline aggregation functions
B.3 EXTRAPOLATION ON SET-RELATER TASKS (RELATED TO SECTION 4.4)
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 random from [20, 40) for training and validation sets, and from [50, 100) for test sets. For Mpuss, pooar and ÍMMP, we sampled el- ements from Wr, 12) where l (O0 12). For 0 MAP,
sampled elements (5, where ~ InyGamma( 1, 15). As loss functions, we used MSE for /'past and oz and used the negative logarithm of the produc the likelihood and the prior for ΩOMAP and 0 MAP-
Tables 9 describes the hyperparameter search space for set-related tasks.
B.4 GRAPH CLASSIFICATION (RELATED TO SECTION 4.7
For original SAGPool (Lee et al. 2019b), we used the optimal hyperparameter settings shared by the authors 18 For SAGPool equipped with GNP, we used gradient clipping with a maximum gradient norm of 1000 for the parameters of GNP, and used different learning rate for p of GNP, For DD PROTEINS, and NCI1, we used 1x, 20x, and 10x larger learning rates for p than the original learning rates, respectively.
7 This product is proportional to the posterior probability
https: wowg.e...csoooo...oooo....... htwp:///arraaaaaeeeee/aeaoeeeeen
17

---

Under review as a conference paper at ICLR 2022
Table 9: Search space for Mposts of poars MAP and 0
MAP
Hyperparameter
Selection pool
Optimizer
RMSprrp
Learning rate p
3e-2, 1e-2, 3e-3
Leurning rate for the other parameters
3e-2, 1e-2,
Norm clipping
(a) Search space for GNP
Hyperparameter
Selection pool
Optimizer Learning rate
Adam, Adam with (0.5, 0.999), RMSprop
3e-2, le-2, 3e-3, 1o-3
Norm clipping
le4
(b) Search space for basic operators
Hyperparameter
Selection pool
Optimizer
Adam, Adam with 8 (0.5, 0.999) RMSprop
Learning rate
le-2, 1c-3, lc-4
Norm clipping
1c4
Number of iterations (for Set2Sct)
1,2
Encoder design (for Set transformer)
SAB blocks, ISAB blocks
Search space for Set2Sct and Set Transformer
Table 10: Statistics woal-world datasets
Dataset
Number of graphs
Average number of nodes
Average number of edges
D&D
1178
284.3
715.7
PRCTEINS
1113
39.06
72.82
NCI1
4110
29.87
32.30
For original ASAPool (Ranjan et al. 2020), used the optimal hyperparameter settings shared by the a For ASAPool equipped with GNP, we used a different learning rate for and g of GNP. For DD and NCT1, we used 3e-2 and 3e-3 for the learning rate for p and q, respectively. For PROTEINS, we used le-1 for the learning rate for and le-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, used the RMSprop optimizer, and the learning rates were set to 3e-2 for p and 3e-3 for 4.
C ADDITIONAL EXPERIMENTS AND RESULTS
C.I GRAPH-LEVEL EXTRAPOLATION ON REAL-WORLD DATASETS (RELATED TO SECTION 4.2
We further tested the extrapolation performances of GNP and bascline approaches using real-world graphs. For real-world graphs, used D&D, PROTEINS, and NCI1, which were also used for graph classification tasks 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 Rénos-Rééni graphs described in Section 4.2 As seen in the Table GNP showed near- pear-perfect extrapolation performance only except for the maxdeg ree task on the NCT1 dataset. Even though the average number of nodes 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 NCII 1 dataset its extremely low average degree of nodes, which is roughly 2.17. Note that the training dataset contains Erdos Rényi random graphs with edge probabilities ranging from 0.1 to 0.9.
https:: http://tttttt...e com com/ma 11bb /c//////AA ASAP
18

---

Under review as a conference paper at ICLR 2022
Table 11: Extrapolation performances of GNP real-world datasets, Only except for the maxdegree task on the NC NCI1 dataset, GNP showed near- near-perfect performance.
Task
D&D
PROTEINS
NCI1
nvs ze
1.740.66
0.5+0..2
0.3+0.1
ha rmonic
3.4+1.1
2.3+-0.3
2,4+0.7
maxdeg ree
3.411.3
2.8
22.41124
Table 12: Extrapolation performance of baseline approaches on real-world datasets. Except for the maxdegree task, there was no combination of simple pooling functions that extrapolated well.
Task
D&D
PROTEINS
NCI1
i invei ze (best combination)
100.0+00.0 (SortPooling)
93.6+-2.8 2.8 (SAGPool)
37.9++0.0 (set2set)
harmonic L (best combination) maxdegree ee (ideal combination) maxdeg "ee (2nd best combination)
552.7+1012.44 (sum, mcan)
110.243.6 (sum, max)
39.5+1.. (sum. max)
0.0+:0.0 (sum, max)
0.0+:0.0 (sum, max)
0.0=00.0 (sum, max)
10.5+0.9 (sum, mean)
30.8+3.9 (sum, mean)
63.9+11.00 (sum, mean)
We also measured the test error of the baseline approaches, and we reported the test MAPE of the best- performing 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.
C.2 GRAPH-LEVEL EXTRAPOLATION ON GRAPHS WITH DIFFERENT STRUCTURE TYPES (RELATED SECTION 4.2)
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 one of the possible reasons why the model trained using 4regular, expander, tree, ladder graphs showed poor extrapolation performance.
C.3 GRAPH-LEVEL EXTRAPOLATION ON GRAPHS WITH DIFFERENT NODE FEATURE DISTRIBUTIONS (RELATED SECTION 4.2
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 graphs with different edge feature distributions for the shortest task.
We additionally performed geaph-level experiments for testing extrapolation to -fittr-distt 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 (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.
C.4 GRAPH-LEVEL EXTRAPOLATION WITH VARIOUS ACTIVATION FUNCTIONS (RELATED TO SECTION
We performed an additional graph-level experiment with variant GNP for handling negative inputs and 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 the activation function. We compared the extrapolation enror in each setting in Table [3] and GNP with the aforementioned changes showed performance comparable original GNP.
19

---

Under review as a conference paper at ICLR 2022
Table 13: Test error on heterogeneous structures. Each row denotes the test MAPES of the model trained using the same graph.
ER
BA
<regular
Expander
Tree
Ladder
1.220.3
0.92:0.3
0.820.3
1941.
0.840.3
0.820.3
BA
1.4+1.3
1.1+0.7
1.1+0.5
1.922.7
1.0+0,5
1.1+0,5
Aregular
9.5++33.7
6.0+8.66
0.6+0.4
15.8+222.9
0.8+0.2
0.7+0.3
Expander
1.240.4
1.3404
19218
1.040.5
5.847.3
2.822.8
Tree
6.145.9
3.743.7
0,940.4
11,2+10.5
0,940.4
0,9-0.4
Ladder
5.1+2.7
3.1+1.
1.4+0.5
7.0+5.1
2.7+3.0
1.1+06
(a) invsize
4regular
Expander
Tree
Ladder
ER 1.120.8
2.3
1.9113
0.920.5
14.726..
2.4=2.4
BA
8.0+22.2
2.9+0..5
2.7+0.66
13.7+4.0
7.243.1
2.8-2.0
4regular
80.4+0.88
62.1+0.8
1.51.6
92.5+0.7
165.3+19.2
39.2+5.2
Expander
162.3:62..
382.41152.9
1202.6=526.6
7,842.2
3218.241:191.6
1658.41741.2
Tree
119.5::57.8
116.4:66.7
66.7+22.5
126.0+61.7
4.1+5.0
45.0=15.1
Ladder
85.8+004
72.4+0.6
24.8=0.9
94.8+022
99.8+7.3
4.0=0.9
(b) harmonic
IR
BA
4regular
Expander
Tree
Lädder
2.520.4
2.11111
3.42377
2.311.1
1990.6
30.7=16.9
BA
3,9=2.0
2.0:
4.7=5.6
3.6+1.4
2.1+166
15.9=20.1
dregular
86.7+33.5
89.2-2.1
5.0=8.1
92.3+:3.3
15.5+1.5
38.8+8.5
Expander
13.2:19.2
23.524.6
238.6=138.7
7.42.66
131.6196.7
306.72174.7
Tzee
78.8-28.2
57.7421.3
41.3=13.2
126.9444.7
2.6+0.55
31.0=222
Ladder
91.2+-0.2
92.6=0.1
24.1+113
95.4+0.0
35.3+1.1
2.1+1.5
(c) maxdegree
Table 14: Test error on graph-level tasks with different node feature distributions.
Task
invs ze
harmonic
maxdegree
Test MAPE
0.8.0.66
2.411.7
4.7
C.5 TEST MAPE ON GRAPH-LEVEL TASKS (RELATED TO SECTION
In Table 16 we reported test MAPEs and standard deviations for all 19 competitors and GNP on the graph-level tasks.
C.6 BEHAVIORS 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+ GNP- tends to dominate the other side. To validate the observation, we masked the output of GNP+ and GNP for readout to O 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 the other tasks do not significantly affect the extrapolation performance. When 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 the model 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.
C.7 EFFECTIVENESS OF GNP ON NODE CLASSIFICATION AND GRAPH REGRESSION (RELATED SECTION 4.7)
Node classification To show the scalability of GNP to million-scale graphs, performed node
classification on the OGEN-Arxiv dataset (Hu et al. 2020). which contains 169, 343 nodes and 166, 243 edges. We compared the node classification accuracy of GCN (Kipf & Welling 2017
20

---

Under review as a conference paper at ICLR 2022
Table 15: Test error on graph-level tasks with different activation functions.
Task
invsize
harmonic
maxdegree
ReLU
0.7+0..5
5.1-0.9
7.3+2.1
Lea
0.3+0.2
4.6=1.4
1,4+:.6
ELU
0.2::..2
5.8=0.7
6.2:13.1
Table 16: Extrapolation performances on three graph-level tasks. We reported test MAPEs and standard deviations. Near-pent rear-perfect scores are in bold, and scores significantly better than those in completely failed cases are underlined.
Aggregation
Readout
Readout
Test MAPE
sum
max
mean
min
376.1+3778.0
257.1+331..3
257.1+3511,
257.1+351.3
SortPonl
100.0+0.0
101.0:7..6
149.1
179.1
179. +49.2
Ser2Set
198.8+00.5
116.9:16.6
179.9:144.7
179.1144.2
179.9:144.7
SAGPool
178.7:1004
min
139.61:54.2
179.1114..2
179.1144.2
179.11144.2
GNP
1.2:10.3
(a) invsize
Aggregation
Readout
Readout
Test MAPE
sum
mean
min
19.06+19.0
121.1+28.9
151.5+73.1
121.1+-28.9
SortPool
76.8+13.0
73.0+:2.3
76.0+3.6
76.4#3.5
76.0++:3.6
Sct2Set
78.2+44.0
95.7+99.
75.9+3.66
76.3+3.5
75.9++3.66
SAGPool
26.9+:21.0
91.1+12.2
76.0+3.6
76.3+3.5
76.0+:3.6
GNP
1.1+0.8
(b) harmonic
Aggregation
Readout
Readout
Test MAPE
mean
min
sum 60.5:122.1
50.5:12.11
49.9
50.54:2.1
SortPool
0.0:10.0
max 0.0:=0.0
59.7+10.3
59.7+0.3
59.74-0.3
Sc12Set
0.0:
mean 16.3+-2.4
59.7++0.3
59.7+0.3
59.74-0.3
SAGPool
51.4+11.8
min 25.5+3.2
59.7++0.3
59.7+0.3
59.74-0.3
GNP
2.5++04
(c) maxdegres
and GAT (Veličković et al. 2018). and their variants equipped with GNP. For implementations, used open source implementations: GCN+linear+label/ and GAT+FLAC For the ones with GNP, since those implementations do not contain 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 the total number of the parameters (see Table [8a 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 T8a GCN with GNP and GAT with GNP showed slightly better accuracy compared 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
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.
21

---

Under review as a conference paper at ICLR 2022
Table 17: Test error with different masking schemes
Task
without masking
masking GNP
masking GNP
invsize
1.2+0.3
1.I+0.1
99.6+1.0
reonnic
1.1+0.8
1.0+0.77
100.1+0.1
maxdegree 2.5
100.0
2.5+t0.4
Table 18: Node classification and graph regression performance. The values in parentheses are the reported test accuracies/MAES and the reported standard deviations.
Model
Test accuracy
Number of parameters
0.7310=0.0014
GCN (original)
238,632
(.73306:0.0024)
GCN (with GNP)
0.7324:0.0014
240,244
1.7366+0.0011
GAT (original)
1,628,440
(0.7371=00001.3)
GAT (with GNP)
0.7377=0.0019
521,084
(a) Node classification results on CGBN-Arxiv
Model
Test MAE
Number of parameters
0.3033+0.0116
PNA (without edge features, original)
433,395
(0.320+0.032))
PNA (without edge features, with GNP)
0.2857:0.0360
433,443
0,1843+0.009
PNA (with edge features, original)
95,111
(0.18800.004)
PNA (with edge features, with GNP)
0.1910#0.0122
95,163
(b) Graph regression results on N.
D CLOSED-FORM SOLUTIONS FOR SET-RELATED TASKS (RELATED TO SECTION 4.4)
In Table 19 provided the closed-form solutions for each task.
E DETAILS ABOUT INFLUENCE MAXIMIZATION AND MONSTOR (RELATED TO SECTION 4.7
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 given graph under 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 node u is newly activated and 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 dataset consisting of pairs of an input graph and set of randomly chosen seed nodes. To generate ground-truth answers, we ran 10, 000 Monte-Carlo simulations and recorded the probability Ta,; that each node is activated until the i-th step. We first trained the base model M to estimate n, given TT-1. -. MONSTOR constructed by stacking s times the base model M, and s is chosen to minimize squared loss between the ground- truuh influences and the estimated influences validation set. Since influence maximization is a submodular maximization problem, we used UBLF (Zhou al. (201)) or CELF (Leskovec et al. 2007) equipped with MONSTOR, which greedily selects seed nodes.
the
For the real-world datasets used, provided the statistics in Table 20
22

---

Under review as a conference paper at ICLR 2022
Table 19: closed-form solution for each task when the input set S (I1, 22, .. ,., given
Task
Closed form solution
Mpost
+ o²
Ei=ı 2:
60
o
post
05
+
MMAP
1 +
MAP
62
(a a ++1)
(8
E (2s ())
Table 20: Statistics of real-world social networks used for the influence maximization task.
Dataset
Number of nodes
Number of edges
Train
5636
31826
Extended
Test
5413
27146
Train
7848
28839
Celebrity
Test
27699 16246
7336
Train
84217
WannaCry
Test
19381
85202
CODE & DATA
All assets used in the paper, including the training/evaluutionn code and the trained models with GNP,
are contained in the supplemental material. All assets we used from DGI [3] (Wang et al. 2019)
and Pytorch Geometrid 14 (Fey & Lenssen 2019) are available under the Apache license
and
MIT license, respectively. Thhe implementation of Set Transforme (Lee et al. 2019a) that we used is available under the MIT License. The implementation of ASAPoo! [Ranjan et al. 2020 that 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. (20TT). and the MONSTOR (Ko et al. 2020) implementation in DGL, we used the code on the GitHub repositories 17 shared by the authors of the original papers. We accessed TUDatase (Morris et al. 2020) using PyTorch Geometric.
hattos//ggiiuub.cc///mm///gg
23


Reviews:
[{"review_id": "Ixn9lHB-ah", "reviewer": "Reviewer_NEG6", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe 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. \n\nThe 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.\n\nThe 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_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. ", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "IUo8xQegW6w", "reviewer": "Reviewer_oxmV", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nIt 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.\n\nIn 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-?\n\nThe 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.\n", "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.", "summary_of_the_review": "The GNP idea seems promising. Additional clarifications and experiments may strengthen the manuscript.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "4qTjNOVT4M", "reviewer": "Reviewer_17q4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n**Strengths**\n1. The paper is well written, with a clear description and proof of the GNP method.\n2. The design of GNP is simple but general, enabling the model to learn which aggregation and pooling method to use.\n3. The extrapolation performance of the GNP outperforms simple min, max, mean, and sum pooling methods. \n\n**Weakness**\n1. 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).\n2. 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.\n3. 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. \n4. 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.\n5. Node classification is another task that is good to see in the paper to demonstrate the effectiveness of using the GNP for aggregation.\n\n[1] U. Alon, and E. Yahav. On the Bottleneck of Graph Neural Networks and its Practical Implications. ICLR 2021.\n\n[2] F. Errica, M. Podda, D. Bacciu, and A. Micheli. A fair comparison of graph neural networks for graph classification. ICLR 2020.\n\n[3] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal Neighbourhood Aggregation for Graph Nets. NeurIPS 2020.\n\n[4] V. Thost, and J. Chen. Directed Acyclic Graph Neural Networks. ICLR 2021.", "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.", "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.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "41wpobrjd--", "reviewer": "Reviewer_hW8Y", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors propose GNP, a new pooling operation for GNNs, which subsumes max, min, mean and sum as special cases.\n\nThe 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.\n\nBased 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:\nTable 1: GNP is unable to match with (sum, max) on the maxdegree task for Ladder Graphs.\nTable 2: GNP is unable to match min on bfs.\nThis is disappointing considering that GNP has the upper hand in the # of learnable parameters\n\nThe 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.\n\nThe 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.\n\n", "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.\n\nThe 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.\n\nHowever, I feel that the paper falls a little short of delivering this.", "summary_of_the_review": "For an excellent version of this paper, I would recommend the following:\n- 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.\n- Add an ablation study with GNP+ with and without the additional linear layer.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

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