Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs
Authors: Chenxiao Yang
Qitian Wu
Jiahua Wang
Junchi Yan
Venue: ICLR 2023 poster (2023)
Keywords: Graph Neural Networks
Generalization

Abstract: Graph neural networks (GNNs), as the de-facto model class for representation learning on graphs, are built upon the multi-layer perceptrons (MLP) architecture with additional message passing layers to allow features to flow across nodes. While conventional wisdom commonly attributes the success of GNNs to their advanced expressivity, we conjecture that this is not the main cause of GNNs' superiority in node-level prediction tasks. This paper pinpoints the major source of GNNs' performance gain to their intrinsic generalization capability, by introducing an intermediate model class dubbed as P(ropagational)MLP, which is identical to standard MLP in training, but then adopts GNN's architecture in testing. Intriguingly, we observe that PMLPs consistently perform on par with (or even exceed) their GNN counterparts, while being much more efficient in training.

This finding provides a new perspective for understanding the learning behavior of GNNs, and can be used as an analytic tool for dissecting various GNN-related research problems including expressivity, generalization, over-smoothing and heterophily. As an initial step to analyze PMLP, we show its essential difference to MLP at infinite-width limit lies in the NTK feature map in the post-training stage. Moreover, through extrapolation analysis (i.e., generalization under distribution shifts), we find that though most GNNs and their PMLP counterparts cannot extrapolate non-linear functions for extreme out-of-distribution data, they have greater potential to generalize to testing data near the training data support as natural advantages of the GNN architecture used for inference.

Published as a conference paper at ICLR 2023
GRAPH NEURAL NETWORKS ARE INHERENTLY GOOD GENERALIZERS: INSIGHTS BY BRIDGING GNNS AND MLPS
Chenxiao Yang, Qitian Wu, Jiahua Wang & Junchi Yan"
Department of CSE & MoE Key Lab of Artificial Intelligence, Shanghai Jiao Tong University {chr26195, echo740, wangjiahua2000 yanjunchil | jtu. edu. on
ABSTRACT
Graph neural networks (GNNs), as the de-facto model class for representation learning on graphs, are built upon the multi-layer perceptrons (MLP) architecture with additional message passing layers to allow features to flow across nodes. While conventional wisdom commonly attributes the success of GNNs their advanced expressivity, we conjecture that this not the main cause of GNNs' superiority in node-level prediction tasks, This paper pinpoints the major source of GNNs' performance gain to their intrinsic generalization capability, by introducing intermediate model class dubbed PL which identical standard MLP in training, but then adopts GNN's ' architecture in testing. Intrigu- ingly, we observe that PMLPs consistently perform on par with (or even exceed) their GNN counterparts, while being much more efficient in training. Codes are available https: / / thub. com/ chr261 2615 /MMM...
This finding provides new perspective for understanding the learning behavior of GNNs, and can be used as an analytic tool for dissecting various GNN-related research problems including expressivity, generalization, over over-smoothn smoothio and het- erophily. As an initial step to analyze PMLP, we show its essential difference to MLP at infinite-wide Moreover, through extrapolation analysis (i.e., generalization under distribution shifts), find that though most GNNs and their PMLP counterparts cannot extrap- olate non-linear functions for extreme out-of- of-distriiuttion data, they have greater potential to generalize testing data near the training data support as natural advantages of the GNN architecture used for inference.
limit lies in the NTK feature map in the post-training stage.
INTRODUCTION
In the past decades, Neural Networks (NNs) have achieved great success in many areas. As classic NN architecture, Multi-Layer Perceptrons (MLPs) (Rumelhart et al., 1986) stack multiple Feed- Forward (FF) layers with nonlinearity universally approximate functions. Later, Graph Neural Networks (GNNs) (Scarselli et al., 2008b; Bruna et al., 2014; Gilmer et al., 2017; Kipf & Welling, 2017; Veličković et al., 2017: Hamilton et al., 2017: Klicpera et al., 2019; Wu et al., 2019) build themselves upon the MLP architecture, e.g., by inserting additional Message Passing (MP) operations amid FF layers (Kipf & Welling, 2017) to accommodate the interdependence between instance pairs.
Two cornerstone concepts lying in the basis of deep learning research are model's representation and generulization power. While the former is concerned with what function class NNs can approximate and to what extent they can minimize the empirical risk R(-), the latter instead focuses on the inductive bias in the learning procedure, asking how well the learned function can generalize to unseen in- and -itto---istribution samples, reflected by the generalization gap R(-)- R(-). There exist a number of works trying to dissect GNNs' representational power (e.g.. Scarselli et al. (2008a); Xu et al. (2018a); Maron et al. (2019); Oono & Suzuki (2019)), while their generalizability and connections with MLP are far less well-understood.
"Correspondence author is Junchi Yan who is also affiliated with Shanghai Al Laboratory. The work was in part supported by National Key Research and Development Program of China A NSFC (62222607), and STCSM (25111005100)

---

Published as a conference paper at ICLR 2023
MLP/
Piropagational MLP
GNN
PMP
hi
y:
Training
(n))
Loss
0.6
CNNN
0.4
PMIP
WIL
0.2
Training Daii
0.0
Range
Tet Nosuary
(d)
Tesfing
2: GNN
PMLP
MLP
MIPP
Seaal
MLP
PMIP
GNN
100 200 Epochs
300
Generalization Gap
(a)
(b)
(c)
Figure 1: (a) Model illustration for MLP, GNN (in GCN-style) and PMLP. (b) Learning curves for node classification on Cora that depicts typical empirical phenomenon. (c) Intrinsic generalizability of GNN reflected by close generalization performance of GNN and PMLP. (d) Extrapolation illustration: both MLP and PMLP linearize outside the training data support (o: train sample, o: test sample), while PMLP transits more smoothly and exhibits larger tolerance for OoD testing sample.
In this work, we bridge GNNs and MLPs by introducing an intermediate model class called Propaga- tional MLPs (PMLPs). During training. PMLPs are exactly the same as a standard MLP (c.g. same architecture. data for training, initialization, loss function, optimization algorithm). In the testing phase, PMLPs additionally insert non-parametric MP layers amid FF layers, as shown in Fig. 1(a), to align with various GNN architectures including (but not limited in) GCN (Kipf & Welling, 2017), SGC (Wu et al., 2019) and APPNP (Klicpera et al., 2019).
(Empirical Results and Implications) According experiments across sixteen node classification benchmarks and additional discussions on different architectural choices (i.e., layer number, hidden size), model instantiations (i.e., FF/MP layer implementation) and data characteristics (i.e., data split, amount of structural information), we identify two-fold intriguing empirical phenomenons:
Phenomenon 1: PMLP significantly outperforms MLP. Despite that PMLP shares the same weights (i.e., trained model parameters) with a vanilla MLP, it tends to yield lower generalization gap and thereby outperforms MLP by a large margin in testing, as illustrated in Fig. I(c) and (b) respectively. This observation suggests that the message passing / graph convolution modules in GNNs can inherently improve model's generalization capability for handling unseen samples.
The word "inherently" underlines that such particular generalization effects are implicit in the GNN architectures (with message passing mechanism) used in inference, but isolated from factors in the training process, such as: larger hypothesis space for representing a rich set of "graph-aware" functions (Scarselli et al., 2008a; Xu et al., 2018a), more suitable inductive biases in model selection that prioritize those functions capable of relational reasoning (Battaglia et al., 2018), etc.
Phenomenon 2: PMLP performs on par with or even exceed GNNs PMLP achieves close testing performance to its GNN counterpart in inductive node classification tasks, and can even outperform GNN by a large margin in some cases (i.e., removing self-loops and adding noisy edges). Given that the only difference between GNN and PMLP is the model architecture used in training and the representation power of PMLP is exactly the same with MLP before testing, this observation suggests that the major (but not only) source of performance improvement of GNNs over MLP in node classification stems from the aforementioned inherent generalization capability of GNNs.
(Practical Significance) We also highlight that PMLP, as a novel class of models (using MLP architecture in training and GNN architecture in inference), can be used for broader analysis purpose or applied simple, flexible and very efficient graph encoder model for scalable training.
PMLP as an analytic tool. PMLPs can be used for dissecting various GNN-related problems such as over-smoothing and heterophily (see Sec. 3.3 for preliminary explorations), and a broader sense can potentially bridge theoretical research in two areas by enabling us to conveniently leverage well-established theoretical frameworks for MLPs to enrich those for GNNs.
PMLP as efficient graph encoders. While being as effective GNNs in many cases, PMLPs are significantly more efficient in training (5 ~ 17x faster on large datasets, and 65 faster for very deep GNNs with more than 100 MP layers). In fact, PMLPs are equivalent to GNNs with all edges dropped in training, which itself (Rong et al., 2020) is a widely recognized way (i.c., DropEdge) for accelerating GNN training. Moreover, PML.Ps more robust against noisy edges, be trivially
2

---

Published as a conference paper at ICLR 2023
combined with mini-batch training (and many other training tricks for general NNs), and help to quickly evaluate GNN architectures to facilitate model development. Notably, PMLPs can further be extended to transductive learning setting, and are compatible with many other GNN architectures with residual connections (e.g., GCNII (Chen et al., 2020b)) or parametric message passing layers (e.g., GAT (Veličković al., 2017)) with slight modifications as will be specified.
(Theoretical Results and Contributions) As mentioned above, our empirical finding narrows down many different factors between MIPss and GNNs to a key one that attributes to their performance gap, i.c., improvement in generalizability due to the change in network architecture. Then, a natural question arises: "Why this the case and how does the GNN architecture (in testing) helps the model to generalize?". We take an initial step towards answering this question:
Comparison of three classes of models in NTK regime. We compare MLP, PMLP, and GNN in the Neural Tangent Kernel (NTK) regime (Jacot et al., 2018), 8), where models are over- perappaameterizee and gradient descent finds the global optima. From this perspective, the distinction of PMLP and MLP is rooted in the change of NTK feature map determined by model architecture while fixing their minimum RKHS-norm solutions (Proposition 1). For deeper investigation, we first extend the definition of Graph Neural Tangent Kernel (GNTK) (Du et al., 2019) to the node regression setting (Lemma 2), and derive the explicit formula for computing the feature map for PMLP/GNN.
OoD generalization Extrapolation analysis for PMLPs and GNNs. We consider important (yet overlooked) aspect of generalization analysis, i.e., extrapolation for -ittr---Dittiiuttion (OoD) testing samples (Xu et al., 2021) where testing node features become increasingly outside the training data support. Particularly, we reveal that alike MIP, both PMLP and GNN eventually converge to linear functions when testing samples infinitely far away from the training data support (Theorem 4). Nevertheless, their convergence rates are smaller than that of MLP by a factor related to node degrees and features' cosine similarity (Theorem 5), which indicates both PMLP and GNN are more tolerant to OoD samples and thus have larger potential to generalize near the training data support (which is often the real-worke case). We provide an illustration in Fig. 1(d).
1.1 RELATED WORKS
Generalization, especially for feed-forward NNs (i.e., MLPs), has been extensively studied in the general ML field (Arora et al., 2019a; Allen et al., 2019; Cao & Gu, 2019). However for GNNs, the large body of existing theoretical works focus on their representational power(e.g.. Scarselli et al. (2008a); Xu et al. (2018a); Maron et al. (2019); Oono & Suzuki (2019)), while their generalization capability is less well-understood. For nove-level prediction setting, those works in generalization analysis (Scarselli et al., 2018; Verma & Zhang, 2019; Baranwal et al., 2021; Ma et al., 2021) mainly aim to derive generalization bounds, but did not establish connections with MLPs since they assume the same GNN architecture in training and testing. For theoretical analysis, the most relevant work is (Xu et al., 2021) that studies the extrapolation behavior of MLP. Their results will later be used in this work. The authors also shed lights on the extrapolation power of GNNs, but for graph-level prediction with max/min propagation from the perspective of algorithmic alignment, which cannot apply to GNNs with average/sum propagation in node-level prediction that are more commonly used.
Regarding the relation between MLPs and GNNs, there are some recent attempts boost the performance of MLP to approach that of GNN, by using label propagation (Huang et al., 2021), contrastive learning (Hu et al., 2021), knowledge distillation (Zhang et al., 2022) or additional regularization in training (Zhang et al., 2023). However, it is unclear whether these graph-enhanced MLPs can explain the success of GNNs since it is still an open research question to understand these training techniques themselves. There are also few works probing into similar model architectures as PMLP, e.g. Klicpera et al. (2019), which can generally be seen as special cases of PMLP. A concurent work (Han et al., 2023) further finds that PMLP with an additional fine-tuning procedure can be used to significantly accelerate GNN training. Moreover, a recent work (Baranwal et al., 2023) also theoretically studies how message passing operations benefit multi-layer networks in node classification tasks, which complements our results.
2 BACKGROUND AND MODEL FORMULATION
Assume a graph dataset G (V,E) where the node set V contains nodes instances {( Bw) } hee.. where H, E IRd denotes node features and yn is the label. Without loss of generality, yo can be a categorical variable or continuous one depending on specific prediction tasks (classification or
3

---

Published as a conference paper at ICLR 2023
regression). Instance relations are described by the edge set & and associated adjacency matrix A E {0, (0,1) In general, the problem is to learn a predictor model with 9 = f( 0, g for node-level prediction, where 9 denotes the k-hop ego-graph around z over G.
Graph Neural Networks and Multi-Layer Perceptrons. To probe into the connection between mainstream GNNs and MLP from the architectural view, re-write the GNN formulation in general form that explicitly disentangles each layer into two operations, namely a Message-Passing (MP) operation and then
(FF) operation:
(MP): h(-1) = E vEN.
=
ag(u, e) by-", (FF): h (500 (hg (n
(I)
where N₂. is the set of neighhored nodes centered at u, ag, v) is the affinity function dependent on graph structure G, w6th denotes a feature transformation mapping at the I-th layer, and h Zu is the initial node feature. For example, in Graph Convolution Network (GCN) (Kipf & Welling, 2017), ag(u, 2) = Aut/Vddd, where du denotes the degree of node u (with self-loop), and (i()) is a fully-connectee layer with non-linearity. For an L-layer GNN, the prediction is given by On = (h!
where wا(ا) is often set as linear transformation for regression tasks or with Softmax for classification tasks. Note that GNN models in forms of Eq. degrade to an MLP with a series of FF layers after removing all the MP operations:
Uu = (...)).....)))))))))))) (x.)) = <xx))
Typical Types of GNN Architectures. Besides GCN, many other mainstream GNN models can be written as the architectural form defined by Eq. whose layer-wise updating rule involves MP and FF operations, e.g., GAT (Veličković et al., 2017) and GraphSAINT (Zeng et al., 2019). Some recently proposed node-level Transformer models such as NodeFormer (Wu et al., 2022) and DIFFormer (Wu et al., 2023) also fall into this category. Furthermore, there are also other types of GNN architecture represented by SGC (Wu et al., 2019) and APPNP (Klicpera al., 2019) where the former adopts multiple MP operations on the initial node features, and the later stacks a series of MP operations at the end of FF layers. These two classes of GNNs are also widely explored and studied. For example, SIGN (Rossi al., 2020), S²GC (Zhu & Koniusz, 2021) and GBP (Chen et al., 2020a) follow the SGC-style, and DAGNN (Liu et al., 2020c), AP-GCN (Spinelli et al., 2020) and GPR-GNT (Chien al., 2020) follow the AspNe-
Bridging GNNs and MLPs: Propagational MLP. After decoupling the MP and FF operations from GNNs' layer-wise updating, notice that the unique and critical difference of GNNs and MLP lies in whether to adopt MP (somewhere between the input node features and output prediction). To connect two families, we introduce a new model class, dubbed as Propagational MLP (PMLP), which has exactly the same architecture as conventional MLP, namely, the same feed-forwarding network. During the inference/testing stage. PMLPGGN incorporates a message passing layer into each layer's feed-forwarding, PMLPsGe adds multiple MP layers in the first layer, and PMLPAPE adds them the last layer. For clear head-to-head comparison, Table 6 in the appendix summarizes the architecture of these models in training and testing stages.
Extensions of PMLP. The proposed PMLP is generic and compatible with many other GNN architectures with some slight modifications. For example, we extend the definition of PMLPs to GNNs with residual connections such as JKNet (Xu et al., 2018b) and GCNII (Chen et al., 2020b) by removing their message passing modules in training, and correspondingly. PMLPx.Net and PMLPGCNII become MLPs with different residual connections in training, which will be further discussed in the next section. For GNNs whose MP layers are parameterized such as GAT (Veličković et al., 2017), one can additionally fine-tune the PMLP model using the corresponding GNN architecture on top of pre-trained FF layers or training MP layers independently.
3 EMPIRICAL EVALUATION
We conduct experiments on a variety of node-level prediction benchmarks. Section 3.1 shows that the proposed PMLPs can significantly outperform the original MLP though they share the same weights, and approach or even exceed their GNN counterparts. Section 3.2 shows this phenomenon holds across different experimental settings. Section 3.3 sheds new insights some research
4

---

Published as a conference paper at ICLR 2023
Table I: Mean and STD of testing accuracy on node-level prediction benchmark datasets.
Datasct #Nodes
Cora 2,708
Citeseer 3,327
Pubmod
A-Photo 7,650
A- A-Computer
Coantber-CS
Coauthor-Paysics
19.717
13,752
18,333
34,493
GNNs
GCN
74.82
1.00
67.60
0.96
76.56 + 0.85
50.69 0.87
78.79 1.62
91.79
0.35
91.22 0.18
SGC
73.06
0.59
67.34
0.54
76.00 4: 0.59
83.42 4. 2.47
77.10 2.54
91.24 4. 0.50
89.18
0.46
APPNP
75.02
2.17
66.58
0.77
76.48 a 0.49
89.51
0.86
78.29
0.55
91.64
0.34
91.80 0.77
MLP
55,30
0.58
56:20
1.27
70.76 4: 0.78
75.61 +: 0.63
63.07
1.67
87.51
0.51
85,09 4.11
PMLPGON
75.86
1: 0.93
68.00
1: 0.70
76.06 +: 0.55
89.10 1: 0 0.88
78.05
0::5::1 1.21
91.76
0.27
91.35
0.82
AGNN
+1.39%
+0059%
-0.66 -0.65%
-0 00.66%
-0.941%
-0.03%
+0.141%
MLPP
AMEP
+37.18%%
+-21,00%
477 49%
+17.84%
+-23755%
+4.86%
+7.36%
PMLPsco
75.04+ 0.95
67. 66 + 0.64
76.02 + 0.67
86.50 + 1.40
74.72+ 3.86
91. 09 0.50
89.34 + 1.40
AGNN
+11.6%
:0.48%
10.03%
3..9%
3..9%%
0.16%
+0.18%
+35.70%
+ +20.39%
+7.43%
+14.40%
+ +18.47%
+4.09%
+4.99%
PMLPAPP
75.84
67.52 0.82
76.30
1.44
1.64
78.07
0.46
91.96
0.51
DONN
+1 +1.09%
+1 +11%
-0.2 0..24%
-1 1.16%
-0 -0.88%
+0.00%
+0. +0.17%
DULP
+.3.144%
+-2014%%
+7.83%
+17.01%
+23.788
44.72%
+8.07%
Table 2: Mean and STD of testing accuracy on three large- datasets.
GCN
SGC
APPNP
MLP
PMLP
PMLPsoc
PMPPAPP
OGBN-Arxiv
69.04 + 0.18
08.56 +: 0.14
68:19 0.32
53.80 4 0:28
28
62 65 0:35
63 0.17
LO480
L.0306
1.5917
1.5917
1.5917
Train time
63.48 ms
90.50 ms
87.24 ms
7.78 ms
7.78 ms
7.78 ms
7.78 ms
OGBN-Products
71.35 0.19
71.17
70.41 0.07
56.21 4: 0.10
69.77 13
0.13
65. 09
3075 22
11.52%/424..800
(-6 1-0-6600/110
Train loss
0.4013
0.4018
0.4311
1.0841
1.0841
1.0841
1.0841
Train time
288 61 ms
665.06 ms
627.26 ms
39.73 ms
39.73 ms
39.75 ms
39,73 ms
Hiikrr
49.66 0.57
50:93
45.31 0.22
0:14
50. 90
50
191 24
(Sens /Bare))
[-0 2.0.22%//-6.77 6.
(+-0. 12%./29.900//
[-2 23.11%/-- 2223%/4400 4.599%
Train loss
1.1422
1,4030
0.7449
1.3344
1.3344
1.3344
1.3344
Train time
36.82 ms
50.42
163.82
7.44 ms
7.44 ms
7.44 ms
7.44
problems around GNNs including over-smoothing, model depth and heterophily. We present the key experimental results in the main text and defer extra results and discussions to Appendix F and G.
We consider sixteen node classification benchmarks involving different types of networks. For fair comparison, we set the layer number and hidden size to the same values for GNN, PMLP and MLP in the same dataset. We basically use GCN convolution for MP layer and ReI.U activation for FF layer for all models unless otherwise stated. PMLPs use the MLP architecture for validation. For SGC, we use MLP instead of one FF layer after linear message passing, and for APPNP, we remove the residual connection (i.e., a = 0) such that the MP layer is aligned with other models. More details about implementation, datasets and hyperparameters are deferred to Appendix F.
We adopt inductive learning setting as the evaluation protocol, which is a commonly used benchmark setting by the community, and guarantee fair comparison between PMLP and its GNN counterpart by ensuring the information of validation/testing nodes is not used in training for all models. Specifically, for node set V = Ver U Vie where Var (resp. Vie) denotes training (resp. testing) nodes, the training process is only exposed to G,, = (Vr.. & J. where E C V,, x Ver only contains edges for nodes in VA, and the trained model tested with the whole graph & for prediction on Vie.
3.1 MAIN RESULTS
How do PMLPs perform compared with GNNS and MLP on common benchmarks? The main results for comparing the testing accuracy of MLP, PMLPs and GNNs on seven benchmark datasets are shown in Table. 1. We found that, intriguingly, three variants of PMLPs consistently outperform MLP by large margin on all the datasets despite using the same model with the same of trainable parameters. Moreover, PMI.Ps are as effective as their GNN counterparts and can even exceed GNNs in some cases. These results suggest two implications. First, the performance improvement brought by GNNs (or more specifically, the MP operation) over MLP may not purely stem from the more advanced representational power, but the generalization ability. Second, the message passing can indeed contribute to better generalization ability of MLP, though it currently remains unclear how it helps MLP to generalize on unseen testing data. We will later try to shed some light on this question via theoretical analysis in Section 4.
How do PMLPs perform on larger datasets? We next apply PMLPs to larger graphs which can be harder for extracting informative features from observed data. As shown in Table 2, PML.P still
5

---

Published as a conference paper at ICLR 2023
PM
Pulaned
Claser
Palued
75
70
40
Number
Numbhrr
Nurther
Sio oididdee
Sioe haddee
of hidde
(a) Number of layers
(b) Size of hidden states
Figure 2: Performance variation with increasing layer number and size of hidden states. (See complete results in Appendix G).
OCN
PMLP
MLL
GCN
PMIL
XLP
100
Chrerer
100
Pchered
100
Clecert
100
Pidered
80
A.15%
301
80
00
90
40
40
40
20
du Ida
Lab
sola
20
Rea Rr.
20
Pip
(a) Activation functions
(b) Transition matrix
Figure 3: Performance variation with different activation functions in FF layer and different transition matrices in MP layer. (See complete results in Appendix G)
85 3t 18
90
PMIL-PoO
PML. OcX
Avp
Aug.
+26.41%
75
70
occh
Ang 3.46%
+52
Accuracy
70
65
GCN
MLP
65
60
&
Avg. A GNN:1 0.15%
60
55
ML.2
Avg. A MLP: 18.15%
0.0
0.2
12 Additional noise ratio
Tmining proportion
Sparsifying ratio
Figure 4: Impact of graph structural information by changing data split, sparsifying the graph, adding random structural noise on Cora. (See complete results in Appendix G)
considerably outperforms MLP. Yet differently, there is a certain gap between PMLP and GNN. We conjecture that this is because in such large graphs the relations between inputs and target labels can be more complex, which requires more expressive architectures for learning desired node-level representations. This hypothesis is further validated by the results of training losses in Table 2, which indeed shows that GNNs can yield lower fitting error on the training data.
3.2 FURTHER DISCUSSIONS
We next conduct more experiments and comparison for verifying the consistency of the observed phenomenon across different settings regarding model implementation and graph property. We also try to reveal how PMLPs work for representation learning through visualizations of the produced embeddings, and the results are deferred Appendix G.
What is the impact of model layers and hidden sizes? In Fig. 2(a) and (b), we plot the testing accuracy of GCN, PMLPGCN and MLP w.r.t. different layer numbers and hidden sizes. The results show that the observed phenomenon in Section 3.1 consistently holds with different settings of model depth and width, which suggests that the generalization effect of the MP operation insensitive to model architectural hyperparameters. The increase of layer numbers cause performance degradation for all three models, presumably because of fittiniting. We will further discuss the impact of model depth (where layer number exceeds 100) and residual connections in the next subsection.
Q1:
Q2: What is the impact of different activation functions in FF layers? As shown in Fig. 3(a), the relative performance rankings among GCN, PMLP and MLP stay consistent across four different activation functions (tanh, cos, ELU, ReLU) and in particular, in some cases the performance gain of PMLP over GCN is further amplified (e.g., with cos activation).

---

Published as a conference paper at ICLR 2023
Q3: What is the impact of different propagation schemes in MP layers? We replace the original transition matrix P. sym D ADD= used in the MP layer by other commonly used transition matrices: 1) Pno-lapp- = D AD 2, i.e., removing self-loop; 2) Prw = D- i.e., random walk 1 (D-1 A) , i.e., heat kernel diffusion matrix. The results are presented in Fig. 3(b) where we found that the relative performance rankings of three models keep nearly unchanged after replacing the original MP layer. And, intriguingly, the performance of GNNs degrade dramatically after removing the self-loop, while the accuracy of PMLPs stays at almost the same level. The possible reason is that the self-loop connection plays an important role in GCN's training stage for preserving enough centered nodes' information, but does not affect PMLP.
matrix; 3) Pa = -k=n e-K!
Q4: What is the impact of training proportion? We use random split to control the amount of graph structure information used in training. As shown in Fig. 4(left), the labeled portion of nodes and the amount of training edges have negligible impacts on the relative performance of three models.
Q5: What is the impact of graph sparsity? As suggested by Fig. 4(middle), when the graph goes sparser, the absolute performance of GCN and PMLP degrades yet their performance gap remains unchanged. This shows that the quality of imput graphs indeed impacts the testing performance and tends to control the performance upper bound of the models. Critically though, the generalization effect brought by PMLP is insensitive to the graph completeness.
Q6:
What is the impact of noisy structure? As shown in Fig. 4(right), the performances of both PMLP and GCN tend to decrease as we gradually add random connections to the graph, whose amount is controlled by the noise ratio (defined as # noisy edges/(El), while PMLP shows better robustness to such noise. This indicates noisy structures have negative effects on both training and generalization of GNNs and one may use PMLP to mitigate this issue.
3.3 OVER-SMOOTHING, MODEL DEPTH, AND HETEROPHILY
We conduct additional experiments to shed lights on broader aspects of GNNs including over- smoothing, model depth and graph heterophily. Detailed results and respective discussions are deferred to Appendix E. In nutshell, we find the phenomenon still holds for GNNs with residual connections (i.e., JKNet and GCNII), very deep GNNs (with more than 100 layers) and heterophilic graphs. This indicates that both over-smoothing and heterophily failure cases of GNN generalization, and can be mitigated by using MP layers that are more suitable for the data or backbone MLP models with better generalization capability, aligning with some previous studies (Battaglia et al., 2018; Cong et al., 2021).
problems closely related to
3.4 EXTENSION TO TRANSDUCTIVE SETTINGS
Notably, the current training procedure of PMLP does not involve unlabeled nodes but can be extended to such scenario by combining with existing semi-supervised learning approaches (Van Engelen & Hoos, 2020) such as using label propagation (Zhu et al., 2003) to generate pseudo labels for unlabeled nodes, or additionally using the GNN architecture for fine-tuning, which is still shown to be more efficient than training GNNs from scratch (Han et al., 2023).
THEORETICAL INSIGHTS ON GNN GENERALIZZATION
Towards theoretically answering why "GNNs are inherently good generalizers" and explaining the superior generalization performance of PMLP and GNN, next compare MLP, PMLP and GNN from the Neural Tangent Kernel (NTK) perspective, derive the formula for computing Graph Neural Tangent Kernel (GNTK) in node regression, and then the results examine their extrapolation behaviors, i.e., generalization under distribution shifts. Note that our analysis focuses on the model architecture used in inference, and thus the results presented in Sec. 4.2 are applicable for both GNN and PMLP in both inductive and transductive settings.
4.1 NTK PERSPECTIVE ON MLP, PMLP AND GNN
Linearization of Neural Networks. For a neural network f(x; : + R with initial parameters Oo and a fixed input sample æ, performing first-order Taylor expansion around Og yields the linearized form of NNs (Lee al., 2019) as follows:
p (x:; 0)
f(a;; 0o) + Vol 0o) (0 00))
7

---

Published as a conference paper at ICLR 2023
where the gradient Vef(=; 0g) could be thought of as feature map d(x) : - R depending on the specific initialization. As such, when 8g is initialized by Gaussian distribution with certain oc, where m denotes the layer width), the
scaling and the network width tends infinity (i.e., feature map becomes constant and is determined by the model architecture (e.g. MLP, GNN and CNN), inducing kernel called NTK (Jacot al., 2018):
NTK(E, m.)) = (as)(a,) (x)))(;)) = (V,f(z;;)) Vof(=;;))
Kernel Regression with NTK. Recent works (Liu et al., 2020b;a) show that the spectral norm of Hessian matrix in the Taylor series tends zero with increasing width by (11//m) and hence the linearization becomes almost exact. Therefore, training an over-parameterized NN using gradient descent with infinitesimal step size is equívalent kernel regression with NTK (Arora al., 2019b):
f(x; w) = w T (x)) [(w) Σ y: w Brick(x)))
(5)
We next show the equivalence of MLP and PMLP in training at infinite width limit (NTK regime). Proposition 1. MLP and its corresponding PMLP have the same minimum RKHS-norm NTK kernel regression solution, but differ from that of GNNs, i.e., mmip pmmip o w "gnnn
Implications. From the NTK perspective, stacking additional message passing layers in the testing phase implies transforming the fixed feature map from that of MLP @mip(z) (z) to that of GNN dgnn(22 while fixing w. Given mmpp w pmipp the superior generalization performance of PMLP (i.e., the key factor of performance surge from MLP to GNN) can be explained by such transformation of feature map from @m)p(2)) ) to Φgnn (x) in testing:
fmip((2 (x) = Wmlp @mlp(z)) fpmlp(z) Wmip (x)) fg)n(x)) = wgnn (x))
(6)
This perspective simplifies the subsequent theoretical analysis by setting the focus the difference of feature map, which is determined by the network architecture used in inference, and empirically suggested to be the key factor attributing superior generalization performance of GNN and PMLP. To step further, we next derive the formula for computing NTK feature map of PMLP and GNN (i.e., oynn (x)) in node regression tasks.
GNTK in Node Regression. Following previous works that analyse shallow and wide NNs (Arora al., 2019a, Chizat & Bach, 2020; Xu et al., 2021), we focus two-layer GNN using average aggregation with self-connection. By extending the original definition of GNTK (Du et al., 2019) from graph-level regression node-level regression as specified in Appendix. C, we have the following explicit form of Φgnn (x) for a two-layer GNN.
The explicit form of GNTK feature map for a two-layer GNN dgnn with average aggregation and ReLU activation in node regression is
Lemma 2.
øynn (x,)
Σ jEN(U(S)
TT, aj I+ (w(())
(k) X xTa,), (1) aTa I+ (wi() x X a. aaa....... (7)
where c O(d-1) is a constant proportional to the inverse of node degree, X E Raxd is node features, a, E F. denotes adjacency vector of node i, ( ~ NNO0, Ia) is a random Gaussian vector in 1Rd, two components in the brackets repeat infinitely many times with k ranging from 1 to o0, and I is an indicator function that outputs 1 if the input is positive otherwise O.
4.2 MLP V.S. PMLP IN EXTRAPOLATION
As indicated by Proposition 1, the fundamental difference between MI.P and PMLP at infinite width limit stems from the difference of feature map in the testing phase. This reduces the problem of explaining the success of GNN to the question that why this change is significant for generalizability.
Extrapolation Behavior of MLP. One important aspect of generalization analysis is regarding model's 's behavior when confronted with OoD testing samples (i.e., testing nodes that are considerably outside the training support), a. k.k.a. extrapolation analysis. A previous study on this direction (Xu et al., 2021) reveal that a standard MLP with ReLU activation quickly converges to a linear function as the testing sample escapes the training support, which is formalized by the following theorem.
8

---

Published as a conference paper at ICLR 2023
Theorem 3. (Xu et al., 2021). Suppose fmmp(2)) is an infinitely-wide two-layer MLP with ReLU trained by square loss, For any direction IR and step size At >> 0, let 2o tv. we have
(fmtp(xo + A - fmlp( At O
(8)
Gp
where Co is constant linear coefficient. That is, as t - 0o, m converges to a linear function.
The intuition behind this phenomenon is the fact that ReLU MLPs learn piece-wise linear functions with finitely many linear regions and thus eventually becomes linear outside training data support. Now naturally arising question is how does PMLP compare with MLP regarding extrapolation?
Extrapolation Behavior of PMLP. Based on the explicit formula for Ognn (x) in Lemma 2, we extend the theoretical result of extrapolation analysis from MLP to PMLP. Our first finding is that, as the testing node feature becomes increasingly outside the range of training data, alike MLP, PMLP (as well GNN) with average aggregation also converges linear function, yet the corresponding linear coefficient reflects its ego-graph property rather than being a fixed constant.
Theorem 4. Suppose fpmip(x) is an infinitelywwide two-layer MLP with ReLU activation trained using squared loss, and adds average message passing layer before each fach feed-forward layer in the testing phase. For any direction a E Rd and step size At O, let Do = tv, and as + 0O, we have
(Jymlp(ay + Alv) (pmp At
Co
Σ (d (d.
VENGULO}
where is the same constamt in Theorem 3, do = d is the node degree (with self-connection) of and d, is the node degree of its neighbors.
Remark. This result also applies to infinitely wiide two-layer GNN with ReLU activation and average aggregation in node regression settings, except the constant Co different from that of MLP.
Convergence Comparison. Though both MLP and PMLP tend to linearize for outlier testing samples, indicating that they have common difficulty extrapolate non-linear functions, we find that PMLP in general has more freedom to deviate from the convergent linear coefficient, implying smoother transition from in-distribution (non-linear) out- -fi-triiiiiiiitoonnn (linear) regime and thus could potentially generalize to
samples near the range of training data.
Theorem 5. Suppose all node features are normalized, and the cosine similarity of node æ; and the average of its neighbors is deonoted a4 [0, 1]. Then, the convergence rate for f (x) is
(ppmip (Zo Alv) Spmilp (2x0)) /
1+ (dmex
1Iv1 amin
(10)
Co EiENouRO1 (d d:)-1
t
where amin minfaa, ass IseNouo E [0, 1]. and dmaz 2 denotes the maximum node degree in the testing node No 's neighbors (including itself).
This result indicates larger node degree and feature dissimilarity imply smoother transition and better compatibility with OoD samples. Specifically, when the testing node's 's degree is 1 (connection to itself), PMLP becomes equivalent to MLP. As reflection in Eq. 10, dmaa 1, and the bound degrades to that of MLP in Eq. 8. Moreover, when all node features are equal, message passing will become meaningless. Correspondingly, ōmin 1, and the bound also degrades to that of MLP.
5 MORE DISCUSSIONS AND CONCLUSION
We defer more discussions other sources of performance gap between MLP and GNN, our current limitations and outlooks to Appendix A.
Conclusion. In this work, we bridge MLP and GNN by introducing an intermediate model class called PMLP, which is equivalent to MLP in training. but shows significantly better generalization performance after adding unlearned message passing layers in testing and can rival with its GNN counterpart in most cases. This phenomenon is consistent across different datasets and experimental settings. To shed some lights this phenomenon, show despite that both MLP and PMLP cannot extrapolate non-line -ineir functions, PMLP converges slower, indicating smoother transition and better tolerance for -itto--distriuutionn samples.

---

Published as a conference paper at ICLR 2023
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. Advances neural information processing systems, 32, 2019.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332. PMLR, 2019a.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances in Neural Information Processing Systems, 32, 2019b.
Ascem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi- supervised classification: Improved linear separability and out-of-distribution generalization. arXiv preprint arXiv:2102.06966, 2021.
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Effects of graph convolutions in multi-layer networks. In International Conference on Learning Representations, 2023.
Peter Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanzhez-Gonzalez, Vinicius Zambaldi. Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 2018.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. Advances in Neural Information Processing Systems, 32, 2019.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. ICLR, 2014.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in neural information processing systems, 32, 2019.
Ming Chen, Zhewei Wei, Bolin Ding. Yaliang Li, Ye Yuan, Xiaoyong Du, and Ji-Rong Wen. Scalable graph neural networks via bidirectional propagation. Advances in neural information processing systems, 11144-5656666 2020a.
Ming Chen. Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pp. 1725-1735. PMLR, 2020b.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006.07988, 2020.
Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference Learning Theory, pp. 1305-1338. PMLR, 2020.
Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On provable benefits of depth in training graph convolutional networks. Advances in Neural Information Processing Systems, 34:9936-9949 2021.
Simon S Du, Kangeheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels, Advances in neural information processing systems, 32, 2019.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1272-1272. PMLR, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
10

---

Published as a conference paper at ICLR 2023
Xiaotian Han, Tong Zhao, Yozen Liu, Xia Hu, and Neil Shah. Mlpinit: Embarrassingly simple gnn training acceleration with mlp initialization. In International Conference on Learning Representa- tions, 2023.
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. NeurIPS, 33:22118 22133, 2020.
Yang Hu, Haoxuan You, Zhecan Wang, Zhicheng Wang, Erjin Zhou, and Yue Gao. Graph-mlp: node classification without message passing in graph. arXiv preprint 1rXiv:2/06.0444 2021.
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin Benson. Combining label propagation and simple models out-performs graph neural networks. International Conference Learning Representations, 2021.
Like Hui and Mikhail Belkin. Evaluation of neural architectures trained with square loss vs cross- entropy in classification tasks. arXiv preprint urXiv:2006.03322 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Katarzyna Janocha and Wojeiech Marian Czarnecki. On loss functions for deep neural networks in classification. arXiv preprint
2017.
Thomas N Kipf and Max Welling. Semi-super classification with graph convolutional networks. ICLR, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. ICLR, 2019.
Jachoon Lec, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. Advances in neural information processing systems, 32, 2019.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Toward theory of optimization for over- over- parameterizee systems of non-linear equations: the lessons of deep learning. arXiv preprint arXiv:2003.00307, 2020a.
Chaoyue Liu, Libin Zhu, and Misha Belkin. On the linearity of large non-linear models: when and why the tangent kernel constant. Advances in Neural Information Processing Systems, 33: 15954-1.5964, 2020b.
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 338-348, 2020c.
Jiaqi Ma, Junwei Deng, and Qiaozhu Mei. Subgroup generalization and fairness of graph neural networks. Advances in Neural Information Processing Systems, 34: 14410-18861, 2021.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image- based recommendations on styles and substitutes. In Proceedings of the 38th international ACM SIGIR conference on research and development in information retrieval, pp. 43-52, 2015.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 2000.
Galileo Namata, Ben London, Lise Getoor, Bert Huang, and UMD EDU.
Query-driven active surveying for collective classification. In International Workshop Mining and Learning with Graphs, 2012.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. arXiv preprint arXiv: 1905. 2019.

---

Published as a conference paper at ICLR 2023
Hongbin Pei, Bingzhe Wei, Kevin Chen- Chean Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. International Conference on Learning Representations, 2020.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph con- volutional networks on node classification. International Conference on Learning Representations, 2020.
Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004.11199 7:15, 2020.
David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning representations by back-propagating errors. nature, 323(6088);533-556, 1986.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. Computational capabilities of graph neural networks. IEEE Transactions on Neural Networks, 20 (1):81-102, 2008a.
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, 2008b.
Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The vapnik-chervonenkis dimension of graph and recursive neural networks. Neural Networks, 108:248-22 2018.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 2008
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arviv: 181 1.05668, 2018.
Arnab Sinha, Zhihong Shen, Yang Song, Hao Ma, Darrin Eide, Bo-June Hsu, and Kuansan Wang. An overview of microsoft academic service (mas) and applications. In Proceedings of the 24th international conference on world wide web, pp. 243-24422422 226,2466222 2015.
Indro Spinelli, Simone Scardapane. and Aurelio Uncini. Adaptive propagation graph convolutional network. IEEE Transactions on Neural Networks and Learning Systems, 32(10):455-4466) 2020.
Jesper E Van Engelen and Holger H Hoos. A survey on semi-supervised learning. Machine learning, 109(2)3373-440, 2020.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
Saurabh Verma and Zhi-Li Zhang. Stability and generalization of graph convolutional neural networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & 2019.
Data Mining, pp.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference on machine learning, pp. 6861-681 PMLR, 2019.
Qitian Wu, Wentao Zhao, Zenan Li, David Wipf, and Junchi Yan. Nodeformer: A scalable graph struc- ture learning transformer for node classification. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Qitian Wu, Chenxiao Yang, Wentao Zhao, Yixuan He, David Wipf, and Junchi Yan. Difformer: Scalable (graph) transformers induced by energy constrained diffusion. ICLR, 2023.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural 201 8a.
networks? arXiv preprint 1rXivv1810.000
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks, In International conference on machine learning, pp. 5453-5462, PMLR, 2018h.
12

---

Published as a conference paper at ICLR 2023
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. ICLR, 2021.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Raigopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. arXiv preprint arXiv:1907.04931, 2019.
Hengrui Zhang. Shen Wang, Vassilis loannidis, Soji Adeshina, Jiani Zhang, Xiao Qin, Christos Faloutsos, Da Zheng, George Karypis, and Philip S Yu. Orthoreg: Improving graph-regularized mlps via orthogonality regularization. arXiv preprint arXiv:2302.00109, 2023.
Shichang Zhang, Yozen Liu, Yizhou Sun, and Neil Shah. Graph-less neural networks: Teaching old mlps new tricks via distillation. In International Conference Learning Representations, 2022.
Hao Zhu and Piotr Koniusz. Simple spectral graph convolution. In International Conference Learning Representations, 2021.
Jiong Zhu. Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances Neural Information Processing Systems, 33:7793-7804, 2020.
Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of the 20th International conference on Machine learning (ICML-03), pp. 912-919, 2003.
13

---

Published as a conference paper at ICLR 2023
A MORE DISCUSSIONS
Other sources of performance gap between MLP and GNN When PMLP fails? Besides the intrinsic generalizability of GNNs that is revealed by the performance gain from MLP PMLP in this work, we note that there are some other less significant but non-negligible sources that attributes the performance gap between GNN and MLP in node prediction tasks:
Expressiveness: While our experiments find that GNNs and PMLPs can perform similarly in most cases, showing great advantage over MLPs generalization, in practice, there still exists a certain gap between their expressiveness, which can be amplified in large datasets and causes certain degrees of performance difference. This reflected by our experiments on three large-scale datasets. Despite that, we can see from Table 2 that the intrinsic generalizability of GNN (corresponding to Amip) is still the major source of performance gain from MLP.
As our default experimental setting, inductive learning ensures that testing samples are unobserved during training and keeps the comparison among models fair. However in practice, the ability to leverage the information of unlabeled nodes in training a well keolnnnowwn advantage of GNN (but not the advantage PMLP). Still, PMLP can be used in transductive setting with training techniques described in Sec. 3.4.
Semi-Supervised Transductive Learning:
Current Limitations and Outlooks. The result in Theorem 5 provides a bound to show PMLP's better potential in OoD generalization, rather than guaranteeing its superior generalization capability. Explaining when and why PMLPs perform closely to their GNN counterparts also need further investigations. Moreover, following most theoretical works on NTK, consider the regression task with squared loss for analysis instead of classification. However, as evidences (Janocha & Czarnecki, 2017; Hui & Belkin, 2020) show squared loss can be competitive as softmax cross-entropy loss, the insights obtained from regression tasks could also adapt to classification tasks.
B PROOF FOR PROPOSITION
To analyse the extrapolation behavior of PMLP and compare with MLP, As mentioned in the main text, training infinitely wide neural network using gradient descent with infinitesimal step size is equivalent to solving kernel regression with the so-called NTK by minimizing the following squared loss function:
f(x; w) = w T (x)( ((w)
Σ (y: w (occ((x))) = 2 i=1
(11)
Let us now consider an arbitrary minimizer w E H in NTK's reproducing kernel Hilbert space. The minimizer could be further decomposed as w" = - w1, where v" lies in the linear span of feature mappings for training data and wi is orthogonal to u" i...
Σ di (2:), (w" wiTH = O.
(12)
One observation is that the loss function is unchanged after removing the orthogonal component wi:
2
C(w")
Σ
yi
d (x;) + wT Pnek (x:))
(13)
2
yi >a (nnt(( Ontk (2:)) = L(wZ)).
2
This indicates that úh is also a minimizer whose H-norm is smaller than that of w", i.e., || [| S [[w*[|x It follows that the minimum H-norm solution for Eq. 11 can be expressed as a linear combination of feature mappings for training data. Therefore, solving Eq. 11 boils down to solving a linear system with coefficients [A,}3 Resultingly, the minimum H H-norm solution is
w = Σ [ 'I
(14)
1=1
14

---

Published as a conference paper at ICLR 2023
where K IR=x is the kernel matrix for training data. We see that the final solution is only dependent on training data {a,, yr and the model architecture used in training (since it determines the form of (2;)) It follows immediately that the min-norm NTK kernel regression solution is equivalent for MLP and PMLP (i.e., w mll w pmitp) given that they are the same model trained on the same set of data. contrast, the architecture GNN is different from that of MLP, implying different form of feature map, and hence they have different solutions in their respective NTK kernel regression problems (i.e., W miy # w gman).
C PROOF FOR LEMMA 3
C.I GNTK FOR GRAPH-LRVEL. REGRESSION
Graph Neural Tangent Kernel (GNTK) (Du et al., 2019) natural extension of NTK graph neural networks. Originally, the squared loss function is defined for graph-level regression and the kernel function is defined over pair of graphs:
GNTK 9ÿ) = Φgnn (9:) 8gnn (Gz) = (Vef(9:0), Vof(C;:0))
(15)
((0) 2
(y/- f(;;
(16)
where ((;;; 0) yields prediction for graph such as the property molecule. The formula for calculating GNTK is given by the following (where we modify the original notation for clarity and alignment with our definition of GNTK node-level regression setting):
GNTK (0) (G., Gb) use
(200) (G,, Gi)
x Lu's
(17)
where a. E V., V/.
The message passing operation in each layer corresponds
EX mp (9s, Gj)
Σ
Σ
I (9,, 93)
= Cu
VEN. (u) of ('ENN
(18)
G (O) ma
(Gr.
Σ
E
(NTK(()) (Gr,9)) wv
= Cu
uu
vEN.U( of (ENNU
where Gu denotes a scaling factor. The calculation formula of feed-forward operation (from
GNTK((-1) map (Gi, G,) to GNTK( (Gi, Gj)) is similar to that for NTKs of MLP (Jacot et al., 2018). The final output of GNTK (without jumping knowledge) is calculated by
GNTK (9,,9)) =
Σ WEV,,W'EV,
(LTK(4-1) 9,)
(19)
C.2 GNTK FOR NODE-LEVEL REGRESSION
We next extend the above definition of GNTK to the node-level regression setting, where the model
fæ; 0,9 9) outputs prediction node, and the kernel function is defined over pair of nodes in single graph:
GNTK GNTK(x,, D 2,) = Φynn (xx;) Dgnn (I,) = (Vof(z,;099) Vof(z,;
(20)
a (u: f(x;; 0z);
((0)
(21)
Then, the explicit formula for GNTK in node-level regression is as follows.
GNTK (0) (x,, = x (0) (ær,, 2.)) = xx. xz
(22)
15

---

Published as a conference paper at ICLR 2023
Without loss of generality, we consider using random walk matrix as implementation of message passing. Then, the message passing operation in each layer corresponds to:
I mp (I), x3))
E
Σ
( (zp)
(I 1)(IN) +1)
REMUU) J'NNJUU
(23)
GNTK (I), (W + 11 KEMUU) J'N,
E
E
GNTK( (zg,3y),
Moreover, the feed-forward operation in each layer corresponds to:
Σ (z), = M.
[o(u)o(v)),
E
[o(u)d(v)}
(24)
GNTK (z., = GNTK (xx n.2))
(1) (2), 1)j) + Σ (z)),
mp
I(l-1) (at,
Σ (L-1) (z;)
where
A
2mp
mmp
D(e"") (z), xx))
Empp (z., 2b3)
Suppose the GNN has L layers and the last layer uses linear transformation that is akin MLP, the final GNTK in node-level regression is defined as
GNTK(E,, 2T) GNTK
(EETTK(L-""aa " (zy)
(25)
C.3 GNTK AND FEATURE MAP FOR A TWO-LAYER GNN
We next derive the explicit NTK formula for a two-layer graph neural network in node-level regression setting. For notational convenience, we use a, E R to denote adjacency, i.e.,
1/((AG 1) if (i.j) $ E
if (i.j) E
(a:);
(26)
0
and G = XX E Rxnn to denote the Gram matrix of all nodes. Then we have
(First message passing layer)
GNTK (0) (I,, = (0) (0;, GNTK (0)
x Tjj mp (I,, xz) = E(0) (I,, D.y = a. Gaj.
(27)
(First fordarorward layer)
{(1) (z), =
E
(o(u)o())),
(0.A0)
( (o; 20)) = c.
E
(o(u)ō(U)
(..AN(O.AC))
(28)
a Ga; a Ga;
T xTa, aj
(
a
Xaa
a, Ga, a Ga.
By noting that a. Ga, = (XT a.) x aj and substituting alk) k. (k), o (k) 1, (k), where
T_ (k) is an indicator function that outputs if is positive otherwise 0, we have the following equivalent form for the covariance
(1) (x),
E (o.aa.
[w [ X ((w X a.) w X a, (w x {a,)),
(29)
(1) (æ,, 1z)) =c: c.
[L Tx
x a.) xTa)) (w x a,)]
w~N(0,,1))
Hence, we have
GNTK (x; = (NNK())
(1) (x; 1z,) + (1) (zi, 2;))
[a Ga. (w x a.) I (w x xT a,)
=c. w..(
(30)
+ c.
(w0 T a; T. (w T x a,) w x aj I x &aa)]]
16

---

Published as a conference paper at ICLR 2023
(Second message passing layer / The last layer)
Since the GNN uses a linear transformation on top of the (second) message passing layer for output, the neural tangent kernel for two-layer GNN is given by
GNTK(E;; k,) = GNTK (1) mp (ai, 2.5)
Σ
Σ
GNTK()) 2zp)
(IWG) + 1)(1 +1)
(31)
-(1o (11). ... 0 (cn))
as (()))))).,..)((())))))))))
aj
H
where K(1) E R and d(')) Rd + H. the kernel matrix and feature map induced by GNTK(),
By Eq. 31, the final feature map 9gnn (x) is
(x;) (x) (() a,
(32)
Also, notice that in Eq. 30,
a Gaj T4 x a:) 1 (w (w) x a;) 01 db.
w X a. T4 (w x a:) w X aj I+ w X a,) = =(w (1) T Φ5
(33)
where oi = a; (w
(w x a:).
Then, the feature map (2) can be written as
(x:) = x a I+ (w())* x a.) (1))" x a; I4 (w())xX x xTai),
x a, TTa
1l+ xx( w0 x a; 11 (w( xTa: aai),
(34)
x a. .. w (oc)T x as)) w (00) x ai I4 (wolo)) xTa:) ]
where (k) / (0, Ia) is random Gaussian vector in Rd with the superscript (k) denoting that is the kitth sample among infinitely many i.i.d. sampled ones, e' is constant. We write Eq. 34 in short as
(m.) (.x)) -d [x a.. I
(<) x aa) w (k) x a, I+ (wilt) x RTai) ......
(35)
Finally, substituting Eq. 35 into Eq. 32 completes the proof.
D PROOF FOR THEOREM 4 AND THEOREM 5
To analyse the extrapolation behavior of PMLP along certain direction v in the testing phase and compare it MIP, we consider newly arrived testing node wo lv, whose degree (with self-connection) is d and its corresponding adjacency vector is E B=+ where (a); 1/d if (i, 0) E & otherwise 0. Following (Xu et al., 2021; Bietti & Mairal, 2019), we consider a constant bias term and denote the data plus this term & [< [1. Then, the asymptotic behavior of f(-) at large distances from the training data range can be characterized by the change of network output with length step At along the direction v, which is given by the following in the NTK regime
At (fmlp (0) fmmpp (tt))
1
1
w T win (0mipp - 0mip (20))
(36)
At
At (Fpmip (i)) Spmml (λt0) At winp T
1
1
winip(@gnn (x) yynn (zo)
(37)
where x = 2o + At v = (t + At) ã = [ [1] and ao = [1 As our interest is in how PMLP
extrapolation, use f(-) to refer fpmip()) in the rest of the proof. By Lemma. the explicit formula for computing this node's feature map is given by
Dynn (0o) = (o0), Φ (1) (xx (x)11)11; k0), ,1)) (x0; 20)
(38)
17

---

Published as a conference paper at ICLR 2023
where
(50) d. (100. x|aaaxa II_ (wolkT [#n: x[Ta). a):
(39)
w(l) (00, X] -1+ (w
(20, X a) .......
xTaaaaa
and similarly
(2;; =c' _c.(i0. xfo,)""aa a; 11+ (wo [ x] xJaa).
[[00.x]
(40)
(R)) [2. X
I+ (t) [o. X [Taa)) a.) .........
w (8) (O, Ia), with & going to infinity, e' is constant, 1+ is an indicator function that outputs 1 if k is positive otherwise O, and (a.)ı = 1/([] + 1) if á is connected to the new testing node. follows from Eq. 37 that
1
(ā) - (20))
At
mip (+)) - (to), ... ",""""""""""" (xni 200] a
Whlp
(41)
Al
1
Whlp (o(1)()) -(0(())) +
1
wmip (z11)();;)) 20 (z:;;
dAl
dA
ieNo
mlp (+) ((1)) (ázo) Recall that w mlp from infinite dimensional Hilbert space, and (k) is drawn from Gaussian with k going to infinity in Eq. 39 and Eq. 40, where each (*) corresponds to some certain dimensions of w indp Let us denote the part that corresponds to the first line in Eq. 39 as (a)()) and the second line in Eq. 39 as Yook)) Consider the following way of rearrangement for (the first element in) ()))))))))))))))))))())) - (20)
Now, let us consider wiip
[ x|aa a 1+ (A)
a - [ X|TC a 1+ (w) [20. [ xJTa) c X
=[2; x T a (I+ (A)
[ X
a
- I+ (w)(k) [20. X| a))
(42)
d Atv [0] 11 w (k)
1
100 x a):
where (Ato 0] is obtained by subtracting [0o, X] from ( X] a. Then, can re-write mip (x) (((((())))) into more convenient form:
1
w mlp (z))) (12) (io)
(43)
At
B 1 0] I (w [0o, X| a) dl(ww)
(44)
e /
At,
X/At]
(I+ (w
[ X a) I4 (w [ x a)) dP(w)
(45)
j Yow w T( 0 4
T T X
a) dl(w)
(46)
/ ww [&/AI,
X/A
(I+ (w
Ø X T a) -14 (w [2oo X]_ a)) dP(w)
(47)
w Remark. For other components in Eq. 41, i.e., At mlp (zx; - 2(11) (2;;; 2n)) where E Ng. the corresponding result of the expansion in Eq. 43 is similar, which only differs by scaling factor (since the first element in both and a; indicating whether the current node is connected to the new testing node non-zero) and replacing a with a, Therefore, in the following proof we focus on Eq. 43 and then generalize the result other components in Eq. 41.
18

---

Published as a conference paper at ICLR 2023
D.1 PROOF FOR THEOREM 4 (CONVERGENCE TO LINEAR FUNCTION)
We first analyse the convergence of Eq. 43. Specifically, for Eq. 44:
G I (w a.g X a) dP(w)
G L |0] 14 w / X/t| a) dl(ww
(48)
/ B v [0] 14 (w
c
lo 0l) (w) d
as 00
where the final result is constant that depends on training data, direction and node degree d. Moreover, the convergence Eq. 45 is given by
B X/At)
[I+
w
X
a)
- I+ (w)
[o X]
TTTaa a))
dP(ww)
f / X I+
w T
[
1
X
a -+
w [ | 1 Ta)
1) dF(ww
+ At
+ At
tt
- f at At a (I+ (w T [ 0])
I+
ww
T
0])
dP((w)
0, as + 0c
(49)
The similar results in Eq. 48 and Eq. 49 also apply to analysis of Eq. 46 and Eq. 47, respectively. By combining these results, we conclude that
At mipp (x)) -6(1
as t
(50)
d'
follows that
1 At
(J J (Xo)) c
Σ SENo
d
1 0o.
(51)
In conclusion, both MLP and PMLP with ReLU activation will eventually converge to a linear function along directions away from the training data. In fact, this result also holds true for two-layer GNNs with weighted-sum style message passing layers by simply replacing "hip by ygn. in the proof.
However, a remarkable difference between MLP and PMLP is that the linear coefficient for MLP constant Go that is fixed upon a specific direction and not affected by the inter-connection between testing node and training data {z);,))) In contrast, the linear coefficient for PMLP (and GNN) is also dependent on testing node's degree and the degrees of adjacent nodes.
Moreover, by Proposition. 1, MLP and PMLP share the same w winlp (including Bw and Yw), and thus the constant C₂ in Eq. 51 is exactly the linear coefficient of MLP. This can also be verified by setting x to be an isolated node, in which case /-1 Eie d. = and PMI.P is equivalent to MLP. Therefore, we can directly compare the linear coefficients for MLP and PMLP. As an immediate consequence, if all node degrees of adjacent nodes are larger than the node degree of the testing node, the linear coefficient will become smaller, vice versa.
D.2 PROOF FOR THEOREMS 5
We next analyse the convergence rate for Eq. and Eq. 49 to see to what extent can PMLP deviate from the converged linear coefficient as an indication of its tolerance to out-of-distributi sample. For Eq. 48, we have
/
B 0]. (I+ (w
[ x] a) - I4 (w [v ())) dP(w)
d / I. (w [ x a) 1 (w T lo 01) dP(ww
(52)
$
/
11 (w [ x|] T a) + (w [20 0)) dP
19

---

Published as a conference paper at ICLR 2023
(wwwTv) Based on the observation that the integral of [[+(w v1) non-overlapping part of two half-balls that are orthogonal to di and 02. which grows linearly with the angle between i and U2 denoted by & (v1, Therefore, we have
[w T2)] represents the volume of
/ [++ (w | I], X] a) - -I+ (w [xc [0) dlP(w)
d
(53)
< ([1r
x] a (z 0])
d
Note that the first term the angle can be decomposed
d [20 1]. x T a = aco 0) + 1
Σ Di- iEN(()
(54)
Suppose all node features are normalized, then we have
- (1 11, x] a, [zo, 0]) s (1r0, 0] (20. 11) + <(00 20 Σ x;)
iEN(0)
= arctann 7) + arctan (d- 1)a V1=+1
(d-1)vi a²
(55)
=0 1 + (d 1)V1 a?
t
where a denotes the cosine similarity of the testing node and the sum of its neighbors. The last step obtained by noting arctan(z) < x. Using the same reasoning, for Eq. 49, we have
If B /A, X A (I++ (w [c0, X] a) 1 (w
L X
dl((w)
< B [X, al / [1+ (w
@ X X]Ta) a) - -I (w
( X
a)l dP(ww
19/(//1, al //11. (1/"1
(To [20
1]. x
T
a
I+
w
T
[
x
a)
dPP(w)
t At
++ At
X/A/ a < ((10)) 1J, x
T
[wo
t
t
T a
a,
1+
Al
I+
X
(56)
Note that the second term in the angle can be re-written as
[
X a
t
[
11,x
At
[ 00.0 a.
(57)
t + t At
+ At
+ At
and hence the angle is at most At/(t + At) times of that in Eq. 53. It follows that
/f
B /Tl//A x/ At a (T+ ww T [ X
x]Ta) a)
T++ (wr
[ x T dP())
= 0 + At
0 + (d 1) a²
At
0 1 A
(58)
0 1 + (d 1)vI-a
di
For Eq. 46 and Eq. 47, similar results can be derived by bounding w with standard concentration techniques. By substituting the above convergence rates to Eq. 43, and dividing by the linear coefficient in Eq. 50, the convergence rate for Eq. 43 is
Ar w mip (o()(() (())) co/d
= 0 1+ (d 1)VI a²
(59)
co/d
1 I+|dmas - 1) 11) where dmaz denotes the
follows that the convergence rate for Eq. 37 is O maximum node degree in the testing node" neighbors (including itself) and
O'minn mnin(a:)ieNouy denotes the minimum cosine similarity for the testing node' neighbors (including itself). This completes the proof.
(60)
20

---

Published as a conference paper at ICLR 2023
E WVER-SMOOTHING, DEEP GNNS, AND HETEROPHILY
Over-Smoothing and Deep GNNs. To gain more insights into the over-smoothing problem and the impact of model depth, we further investigate GNN architectures with residual connections (including GCN-style ones where residual connections are employed across FF layers, e.g., JKNet (Xu et al., 2018b) and GCNII (Chen et al., 2020b), and SGC/APPNP-styl ones where the implementation of MP layers involve residual connections, e.g.. APPNP with non-zero a). Table. 3 and Table. 4 respectively report the results for SGy/APPNP-style and GCN-style GNNs on Cora dataset. Similar trends are also observed on other datasets, some of which are plotted in Fig. 5.
As we can see, the performances of PMLPs without residual connections (i.e., PMLP PMLPsGC and PMLPAPP exhibit very similar downward trends with their GNN counterparts w.r.t. increasing layer number (from 2 to 128). Such phenomenon in GNNs is commonly thought to be caused by the oversmoothing issue wherein node features become hard to distinguish after multiple steps of message passing. and since PMLP immune from such problem in the training stage but still perform poorly in testing, may conclude that oversmoothing is more of a problem related failure modes of GNNs' generalization ability, rather than impairing their representational power, which is somewhat in alignment with (Cong et al., 2021) where the authors theoretically show very deep GNNs that are vulnerable to oversmoothing can still achieve high training accuracy but will perform poorly in terms of generalization. We experimental results further suggest the reason why additional residual connections (either in MP layers, e.g., ResAPPNP/SGC, or across FF layers, e.g., GCNII and JKNet) are empirical effective for solving oversmoothing is that they can improve GNN's generalization ability according to results of PMLPECNII PMLP PMLPRessGe ResSGC and PMLP ResAPP where model depth seems to have less impact on their generalization performance.
Graph Heterophily. We further conduct experiments six datasets (i.e., Chameleon, Squirrel, Film, Cornell, Texas, Wisconsin (Pei et al., 2020)) with high heterophily levels, and the results are shown in Table. 5. As can see, PMLP achieves better performance than MLP when its GNN counterpart can outperform MLP, but is otherwise inferior than MLP. This indicates that the inherent generalization ability of certain GNN architecture also related whether the message passing scheme is suitable for the characteristics of data, which also partially explains why training more dedicated GNN architectures such as H2GCN (Zhu et al., 2020) helpful for improving model's generalization performance on heterophilic graphs.
21

---

Published as a conference paper at ICLR 2023
Table 3: For SGC and APPNP styles, layer number denotes the number of MP layers. The number of FF layers and hidden size are fixed as 2 and 64. 'Res' denotes using residual connection in the form of X (8) (1 a) MP (X 1) tax (0).
# Layers
16
128
MLP
52.56 +: 32.56 +: 0.41 52.56 0.41
52.56
0.41
52.56 +:
32.56
0.41
52.56 0.41
SGC
T3.12 + 1.20
75.36 + 1.40
76.78
1.63
75.22
2.75
64.70
4.14
47.64
3.09
PMLPsee
T3.48 + 1.30
75.38 + 1.73
76.20
2.16
73.60
3.07
67.76 +: 4.38
53.64
6.35
SGC+Res
71.56 + 1.11 73.98 + 1.16
75.02
1.28
75.50 1.05
75.40
1.05 75.38 + 1.05
75.38 1.05
(Converged)
(Converged)
PMLP PMLPsGC+Rae Rec Res
72.80 +: 0.67
75.08 4: 1.14
76.06
1.13
76.22
76.20 +: 1.23
76.14 d: 1.14
76.14 1.14 (Converged)
MLP
52.56 +: 0.41
52.56 +: 0.41
52.56
52.56 0.41
52.56 1: 0.41
52.56 +: 0.41
52.56 0.41
APPNP
73:30 + 1.39
76.14
1.07
77.32
0.55
76.42
0.65
75.46 + 0.92
70.38 + 1.03
52.24 2.46
PMLPAPP
74.58 +: 0.58
77.08 + 0.77
77.56 + 0.60
76.68
+ 0.77
75.18 + 0.83
71.00 + 0.85
51.00 + 6.58
APPNP+Res
72.28 + 1.50
74.82 # 1.31
75.78 = 1.18
76.18
1.11
75.98 + 1.01
76.04 + 0.92
76.04 0.92 (Converged)
(Converged)
PMLP Rea
72.96 +: 0.75
75.66 + 1.05
76.68
0.82
76.82
0.81
76.86 + 0.87 76.86 + 0.87
76,86 0.87
(Converged)
Table 4: Layer number denotes the number of MP+FF layers, and the number of FF layers is fixed 2.
The hidden size is fixed as 64, For GCNII, ( = a<((1 az) oo; (11-(3))1 I
3e ()))), we set 0.1, 3g = D. ResNet here denotes MLP with residual connections (or equivalently, GCNII without MP operations). For JKNet, we use concatenation for layer aggregation. MLP+JK denotes MLP with jumping knowledge (or equivalently, JKNet without MP operations)
# Layers
2
8
16
32
64
128
w/o res.
MLP
52.56 = 0.41
48.18
+ 4.17
32.26 = 5.66
30.64 = 0.75
27.60 +: 0.76
19.86 + 3.25
20.14 + 2.01
GCN
73.84
1.49
74.86 + 3.03
45.52
6.10
33.50
:::0::::: 5.23
24.08 + 6.90
27.82 : 2.76
19.60 +: 9.52
PMLPocN
73.96 + 0.78
74.56 + 2.94
44.98
# 6.51
29.58 + 10.74
26.66 +: 5.31
27.10 + 8.63
27.76
with res. with res.
ResNet
53.08 + 1.15
53.68 + 0.52
53.12
1.57
52.70
2.16
49.96 + 1.70
45.74 + 1.54
40.74 + 2.39
GCNII
67.36 + 1.57
74.54 + 1.02
76.00
0.62
76.28
0.68
75.42 + 1.65
75.18 + 0.87
68.24 + 1.89
PMLPGGNU
69.08 +: 0.80
74.98
4: 0.51
75.26
1.29
75.62
1.48
75.12 +: 1.38
72.64 :: 2.24
68.52 4: 1.47
MLP+JK
52.76 = 1.38
53.46
+: 1.29
54.48
= 1.19
56.
0.73
63.
1.30
49.38 + 1.96
30.40
1.63
JKNet
65.50 +: 0.78
72.02
4: 1.15
72.22
1.08
71.50
0.83
71.38 1: 1.61
60.66
:: 2.63
51.52 4.00
PMLP3RNN
67.82 = 0.78
72.76
+ 1.59
74.02
0.53
73.92 1.04
72.76 :: 1.28
67.70 + 0.83
14.70
Table 5: Mean and STD of testing accuracy on datasets with high heterophily level.
Dataset
Chameleon
Squireel
Film
Cornell
Texas
Wisconsin
GNNs
GCN
56.27 + 1.60
41.21
0.48
29.88 = 0.56
67.03 +:: 4.44
63.24 + 8.02
63.92 + 4.51
SGC
58.73 1 2.00
43.73
1.95
30.92
0.68
58.92 1 10.54
62.70 1 7.00
66.67 1 4.60
APPNP
57.98 + 3.70
41.59 + 1.50
32.20
1.37
65.95
+ 3.08
65.95 + 2.42
66.27 :: 2,56
MLP
49.61 1 1.36
29.20
2.32
36.43
2.21
78.92 1: 6.73
76.76
3.08
83.53 1. 3.28
PMLPGON
57.02 + 3.74
36.39
3.28
29.75 = 1.16
65.41 + 8.20
62.70 + 11.04
66.67 + 2.77
AGNN
+1.33%
-11.70%
-0.44%%
-2.42%
-0.85%
+4..30%
MLPS
AMEP
+14.94%
+24.62%
-18.34%
-17.12%
-1.322%
-00.18%
PMIP SOLPsOC
55.83 + 2.51
39.44 1.93
28.66 0.61
55.14 + 9.09
62.70 + 4.44
62.35 + 3.26
AGNN
-4.94%
-9.81%
-7.31%
-6.42%
0.00%
-6.48%
AMEP
+12.54%
+35.07%
-21.33%
-30.13%
-18.32%
-25.6%%
PMLP APP
57.28 + 2.25
39.73 1.85
31.54
0.74
68.11 +.1+666.0 6.16
65.95 + 8.24
67.45 4.51
AGNN
-1.21%
-4.47%
-2.05%
+3.28%
0.00%
+1.78%
AMEP
15.46%
36.06%
13.42%
13.70%
14.08%
19.25%
22

---

Published as a conference paper at ICLR 2023
GCN
PMLP GCN
MLP
Carn
Citesear
Pubmed
Aceurcy
20
30
10
20
4
16
32
64
128
2
128
Number of Layers
Number of layers
Nomber of layers
GCNI
PMLPPONT
ResNet
Cor
Citeseer
Pubmed
80
80
Accoracy
700
60
70
50
16
32
64
128
2
8
16
32
64
128
128
layers
Number layers
Number layers
JKNet
PMLP KNNs
MLP+JK
Cora
Citeseer
Pubmed
70
Acquracy
70
60
70
40
60
50
2
16
32
64
128
2
16
32
128
Number of Layers
Number of layers
Number of layers
APPNP
PMLP
MLP
Cora
Citeseer
Pubmod
80
80
Accaracy
60
70
500
2
4
8
16
32
64
128
2
4
8
16
32
64
128
8
128
Number of Layers
Number layers
Namber layers
ResAPPNP
PMLP RHAFP
MLP
Com
Citesear
Pubmed
80
Acegracy
75
70
65
75
60
55
70
2
16
32
64
128
2
16
32
128
128
Number of Layers
Number of layers
Nomber layers
SGC
PMLP
MLP
Cora
Citescor
Pubmod
80
70
80
Accurey
60
70
50
60
4
8
16
32
64
128
2
4
8
16
32
64
128
128
Number of Layers
Number of layers
Number layers
RasSGC
PMLPResuc
MLP
Pubmod
80
Anquaey
75
70
63
75
55
60
55
70
2
32 Number of Layers
16
64
128
2
16
32
128
128
Number of layers
Nomber layers
Figure 5:
Performance variation of different GNN architectures with (GCNII, JKNet, Re- SAPPNP/SGC) or without (GCN, APPNP/SGC) residual links w.r.t. increasing layer number (from 2
128).
23

---

Published as a conference paper at ICLR 2023
Table 6: Head-to-head comparison of three proposed PMLP models (PMLP PMLPsGe and PMLPAM APP) and the standard MLP.
Model
Train und Valid
Inference
GNN Counterpart
MLP
yu (x..)
N/A
PMLPGON
hu ( (MP( "aampnhl"""esssuae "HCAAGL())))
GCN (Kipt & Welling, 2017)
v(xx)
PMLPseC
8. (MMultiiMP(( ((x.
SGC (Wu al., 2019)
PMLPAPP
%, Multi-MP (xx
APPNP (Kliepera al., 2019)
Table 7: Statistics of datasets.
Dataset
Classes
# Nodes
# Edges
# Node features
Cora (McCallum al., 2000)
2,708
5,278
1.433
Citeseer (Sen et al., 2008)
3,327
4,552
3,703
Pubmed (Namata et al., 2012)
19,717
44,324
500
A-Photo (McAuley et al., 2015)
7,650
119,081
745
A-Computer
10
13,752
245,861
767
Coauthor- CS (Sinha et al., 2015)
15
18,333
81,894
6,805
Coauthor- Physsccs
34,493
247,962
8,415
OGBN-Arxiv (Hu et al., 2020)
40
169,343
1,157,799 799
128
47
2,449.029
61,859,076
100
Flickr (Zeng al., 2019)
89,250
449,878
500
F IMPLEMENTATION DETAILS
We present implementation details for our experiments for reproducibility. We implement our model well the baselines with Python 3.7, Pytorch 1.9.0 and Pytorch Geometric 1.7.2. All parameters are initialized with Xavier initialization procedure. We train the model by Adam optimizer. Most of the experiments are running with NVIDIA 2080Ti with IIGB memory, except that for large-scale datasets we use NVIDIA 3090 with 24GB memory. Table 6 summarizes the architecture of PMLPs adopted in training and testing stages for clear head-to-heed to-head comparison.
F.1 DATASET DESCRIPTION
We use sixteen widely adopted node classification benchmarks involving different types of networks: three citations networks (Cora, Citeseer and Pubmed), product co-occurrency networks (Amazon- Computer and Amazon-Photor two coauthor-ship networks (Coauthor- CS. Coauthor- Coauthor-Compus Computer). and three large-scale networks BGGBN-Arxis OGBN-Produce and Flickr). For Cora, Citeseer and Pubmed, we use the provided split in (Kipf & Welling, 2017). For Amazon-Come Comzunn-Compute, Amazon-Phot Coauthor- and Coauthor- Comphtrr,,, we randomly sample nodes from each class labeled nodes, 30 nodes for validation and all other nodes for test following (Shchur et al., 2018). For two large-scale datasets, we follow the original splitting Hu et al. (2020) for evaluation. For Flickr, we use random split where the training and validation proportions are 10%. The statistics of these datasets are summarized in Table. 7.
F.2 HYPERPARAMETER SEARCH
We use the same MIP architecture (i.e., number of FF layers and size of hidden states) as backbone for models the same dataset, same GNN architecture (i.e., number of MP layers) for PMLP and its GNN counterpart, and finetune hyperparameters for each model including dropout rate (from {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9)), weight decay factor (from {0, 0.0001, 0.001, 0.01, 0.1)), and learning rate (from {0.0001, 0.001, 0.01, 0.1)) using grid search.
For model architecture hyperparameters (i.e., layer number, size of hidden states), we fix them as reported in Table. instead of fine-tuning them in favor of GNN PMLP for each dataset which might introduce bias into their comparison. By default, we set (FF and MP) layer number as 2, and hidden size 64, but manually adjust in case the performance of GNN is far from the optimal.
24

---

Published as a conference paper at ICLR 2023
Table 8: Summary of model architectures.
Cora
Citeseer
Pubmed
Photo
Computer
CS
Physics
Arxiv
Products
Flickr
Hidden Size
64
64
64
32
256
128
128
64
64
64
GCN
MP Layer
2
2
2
2
2
2
2
2
FF Layer
2
2
2
2
2
2
2
2
PMLP
Hidden Size
64
64
64
32
64
64
64
MP Layer
2
2
2
2
2
2
2
2
FF Layer
2
2
2
2
2
2
2
2
SGC
Hidden Size
64
64
64
32
256
128
128
64
64
64
MP Layer
2
2
2
2
2
2
2
2
FF Layer
2
2
2
2
2
PMLP
Hidden Size
64
64
64
32
256
128
128
64
64
64
MP Layer
2
2
2
2
2
2
2
2
FF Layer
2
2
2
2
2
APPNP
Hidden Size
64
64
64
32
256
128
128
64
64
64
MP Layer
2
2
2
2
2
FF Layer
2
2
2
2
2
2
2
2
PMLP opp
Hidden Size
64
64
64
32
256
128
128
64
64
64
MP Layer
2
2
2
2
FF Layer
2
2
2
2
2
2
2
2
MLP
Hidden Size
64
32
256
64
64
64
MP Layer
/
1
/
/
/
/
/
FF Layer
2
2
2
2
2
2
2
2
Furthermore, we have discussed different settings for these architecture hyperparameters and find the performance of PMLP is consistently close to its GNN counterpart.
For other hyperparameters (i.e., learning rate, dropout rate, weight decay factor), finetune them separately for each model on each dataset based on the performance on validation set. For PMLP, we use the MLP architecture for validation rather than using GNN since we find there is only slight difference in performance. In that sense, all PMLPs share the same training and validation process as the vanilla MLP, making them exactly the same model before inference.
25

---

Published as a conference paper at ICLR 2023
G ADDITIONAL EXPERIMENTAL RESULTS
We supplement more experimental results this section including extensions of the results in the main text and visualizations of the internal representations of nodes learned by 2-layer MIP, GNN, and PMLP on Cora and Citeseer datasets.
from Fig. 1-14, both PMLPs and GNNs show better capability for separating nodes of different classes than MLP in the internal layer, despite the fact that PMLPs share the same set of weights with MLP. Such results might indicate that the superior classification performance of GNNs mainly stem from the effects of message passing in inference, rather than GNNs ability of learning better node representations.
As
90
PMLPPEN POEN
PMLP pCN
Avg.
0.40%
PMLP OCN
Avg.
75
Avg. A MLP: +24.41%
70
Avg. A MLP: +22.65%
Accuracy
GCN
7.
65
GCN
70
MLP
65
60
60
Avg. A MLP: +18.15%
Avg.
0.45%
55
MLP
55
MEP
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 Training proportion
0.0
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
0.0
0.2 0.4 0.6
0.8
1.0 1.2 1.4 1.6 1.8
2.0
Sparsifying ratio
Additional noise ratio
GCN v.s. PMLP v.s. MLP
PMLPs0c Sodc
80
PMT PMLPsscC
Avg. GNN: + 0.42%
75
PMLP SGC
Avg. & GNN: + 3.54%
85
Avg. +23.09%
Avg.
Accuracy
SGC
70
SGC
65
SGC
70
MLP
Avg. GNN: 0.89%
60
MLP
55
MLP
Avg. 18..22%
55
0.3
0.8
0.9
Training proportion
Sparsifying ratio
Additional noise ratio
(b) SGC v.s. PMLPsGC v.s. MLP
90
APENE
PMLP APP
Avg. A GNN:- 0.02% Avg. A MLP: +23.97%
PMLP APP
Avg. & GNN: 5.09%
75
70
Avg. A MLP: 19.38%
Accuracy
APPNP
75
APPNPI
APPN2
MLP
65
55
Avg. A GNN: 0.05%
MLP
50
MLP
Avg. A MLP: 16.68%
55
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 Training proportion
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Sparsifying ratio
0.0 0.2 0.4 0.6 0,8 1.0 1.2 144 1.6 1.8 2.0
Additional noise ratio
(c) APPNP v.s. PMLPAPP v.s. MLP
Figure 6: Impact of graph structural information by changing data split, sparsifying the graph, adding random structural noise on Cora.
26

---

Published as a conference paper at ICLR 2023
GCN
PMLP
Corn
Citeseer
Pubmed
70
80
Aceurcy
70
70
50
40
60
30
50
2
3
4
5
6
7
8
2
3
4
7
Number of layers
Number layers
Number of layers
SGC
PMLP
MLP
Cora
Citeseer
Puhmed
80
Accuracy
75
65
70
75
60
70
N Number of layers
N Numbber of layers
Number of layers
APPNP
PMLP APP
70
80
Apcaney
75
75
63
60
35
70
2
3
4
5
6
7
8
2
3
4
5
6
7
Number of layers
Number layeess
Number of layers
Figure 7: Performance variation with increasing layer number (from 2 to 8). Layer number here denotes number of FF and MP layers for GCN, and number of MP layers for SGC and APPNP.
GCN
PMLP GEN
MLP
Cora
Citeseer
Pubmed
Acquney
-70
70
60
Size of hiddem states
Size of hidddn states
Size of hhildden states
SGC
PMLP
MLP
Coraa
Citeseur
Pubmed
70
80
Apcuacy
70
60
60
70
50
50
8
16
32
64
128
256
8
16
32
64
128
256
16
32
64
128
256
hidden
Size hiddenn states
Size hidden
APPNP
PMLP
MLP
Cora
Citeseer
Pubmed
Apeuracy
70
70
60
16
32
64
128
256
128
Size of hidden states
Size hiddden states
Size of hidden states
Figure 8: Performance variation with increasing size of hidden states.
27

---

Published as a conference paper at ICLR 2023
GCN
PML
MLP
Puhmed
-0.20%
0.43%
ACGEN
10.08%
-0.55%
+13.72%%
60
ACFEN
60
+1.58%
40
40
20
20
1anhh
clu
sclu
1anh
clu
sclu
tarth
ctu
rela
(a) GCN PMLP GGN MLP
PMLPssc
MLP
+1 +1.00%
ASOC
ASGC
+0.77%
ASOC
+1.22%
ASOC
-0.50%
ASOC
ASOC -1.95%
-1.71%
ASOC
+1 +1.36%
ASGC
-2. 2..8%%
60
ASGC
40
40
40
20
20
SGC V.s. PMLPsGC V.S. MLP
APPNP
100
^APPNP +1.00%
AAPENP -0.6%%
Cora
AAPENP +0,35%
-0,35%
AAPEN2
100
AAPPNP -1.73%
Citeseer
AAPEN -1.10%
AAPENP 11.08%
100
AA7РNP
-0.6 60.6699
Pubmed
AAMIN
AAWPNI
MAPEN2 11.08%
20
20
(c) APPNP v.s. PMLPAPP V.S. MLP
Figure 9: Performance variation with different activation functions FF layer.
PMLPacs
100
AGON
AGON
Cora
ACON
AGON
80
-0.13%
AGON
AGUN
Citeseer
-0.5%
AGCN
-0.55%
AGCN
100
AGCN
AGON
Pulmed
AGON +0.1155
AGON
60
40
Pes
Fm
Par
Fxz
Fr
Par
Pys
Pr:
Par
(a) GCN v.s. PMLPGCN V.s. MLP
PMLPspc
120
Clesser
120
Pohmed
100
50%
+0.70%
ASGC
ASGC
ASGC
ASGC
100
+0.03%
8696
+0.05%
+0.67%
10.46%
60
20
P....
P,-
P.
P
Par
P
P,-
P.t
(b) SGC PMLP SGC
MLP
AP7NP
PMLP
MLP
Puhmed
100
AAPPNT
AAPYNP
SAPPNT
AAPYNE
100
AAMPNP
AAPPNT
AAMYN
+40.35%
+63.75%
11.08%
+41.44%
-0.09%
-0.15
60
20
P...
P..
P
Pan
PAm
APPNP PMLP APP MLP
Figure 10: Performance variation with different transition matrices in MP layer.
28

---

Published as a conference paper at ICLR 2023
(a) GCN
(b) PMLPGON
(c) MLP
Figure 1I: Visualization of node embeddings (2-D projection by t-SNE) in the internal layer for two-layer MLP, GCN and PMLP on Cora.
(a) SGC
(b) PMLPsGG
(c) MLP
Figure 12: Visualization of node embeddings (2-D projection by t-SNE) in the internal layer for two-layer MLP, SGC and PMLP on Cora.
(a) GCN
(b) PMLPPONN
(c) MLP
Figure 13: Visualization of node embeddings (2-D projection by t-SNE) in the internal layer for two-layer MIP, GCN and PML. on Citeseer.
(a) SGC
(b) PMLPsGC
(c) MLP
Figure 14: Visualization of node embeddings (2-D projection by t-SNE) in the internal layer for two-layer MLP, SGC and PMLP on Citeseer.
29


Reviews:
[{"review_id": "WQuWuEkIMH7", "reviewer": "Reviewer_Hjsm", "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": "", "summary_of_the_paper": "This paper claims the statement that using message passing after propagating MLP can achieve comparable performance to using ordinary graph neural networks. By showing various empirical results, using P(ropagational) MLP and GNNs shows similar performance, and using PMLP is much more efficient than using GNNs. Furthermore, by proposing the theorems about the behavior of PMLP and MLP, authors claim that the ability of extrapolating the samples in PMLP can be treated as a useful property.", "summary_of_the_review": "I vote to reject this paper because of the novelty of the proposed methods.", "strength_and_weaknesses": "**Pros:**\n\nP1. Using PMLP which is much more efficient than ordinary GNNs achieves comparable results, and carry out extensive experiments.\n\n**Cons:**\n\nC1. The proposed methods (PMLP) is already used in APPNP. PMLP might not be a novel approach, and it could be just an extended version of APPNP from transduction to inductive setting.\n\nC2. Since the performance of PMLP is similar to ordinary GCNs, the advantage of using PMLP is not significant. It would be better to specify much more persuasive property of the advantage of using PMLP.\n\nC3. The propose theoretical results is far from the practical scenarios, and the claims in the theorem is ambiguous. Especially, I wonder it is effective to claim the extrapolation behavior of PMLP in inductive setting.\n\nC4. In my knowledge, the authors does not specified how may ML operations are performed during the propagation steps. Because of the over-smoothing problem which is a well-known problem in GNN community, it would be better to specify the numbers. Furthermore, in my opinion, showing the results of using MP operations with residual connection would be important.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "UfFF3psQ4x", "reviewer": "Reviewer_nT54", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper presents an efficient model, PMLP, which achieves the GNN-level generalization and accuracy at the cost of training an MLP (which is much cheaper than training a GNN). Specifically, the training of PMLP is identical to that of a normal MLP, where edge information in the graph is completely ignored. During inference, PMLP adds the message passing operation to the MLP model obtained during training. Thus, the inference of PMLP is similar to that of a normal GNN. The authors empirically show that PMLPs achieve similar test time accuracy as GNNs. PMLPs even achieve better robustness than GNNs when introducing structural noise to the graph. Theoretical analysis is also presented by analyzing the NTK of MLP, PMLP and GNN. It is shown that the message passing operation makes PMLPs and GNNs generalize differently from MLPs on out-of-distribution test data: while all models degrade to linear extrapolation on OOD data, PMLPs and GNNs have their linear coefficients depend on the node degree to preserve more information from the data. ", "summary_of_the_review": "Overall, I think this is a good paper. It is a simple model both revealing useful insights and enabling efficient practical deployment. The theoretical results seem correct (need some clarification from the authors). Yet there are some limitations of the analysis as I mentioned above. I vote for acceptance. ", "strength_and_weaknesses": "## Strengths\n+ The proposed is a simple model capturing some fundamental aspects of the learning process. The model computation process is very easy to understand and efficient to execute. Surprisingly, it achieves very promising empirical results. The fact that we can understand its extrapolation behavior under the lens of NTK is also very interesting. \n+ The paper is novel. While there have been a few tricks in the literature to push GNNs towards MLPs by decoupling the message propagation from the feature transformation, most of them still require the message passing operation during training (e.g., by treating it as preprocessing). PMLP is different from them as the training is equivalent to a vanilla MLP. Theoretical analysis on generalization via NTK also brings some new aspects. \n+ The paper is clearly written and I enjoy reading it. It shows a good mixture of empirical and theoretical studies. \n\n## Weaknesses\n- The proof can be written with more care. I have read most of the proof in detail. I do find some key steps hard to process during my first pass, due to missing details. I still have the following questions:\n    - What does the superscript in $w^{(k)}$ mean? I suppose it denotes the dimension of $w$, and when $k\\rightarrow \\infty$, $w$ corresponds to an infinitely wide network. Is this correct?\n    - What is the dimension of $\\phi^{(1)}$? From the NTK definition, I think it should be a vector so that $(\\phi^{(1)})^T \\phi^{(1)}$ is a scalar. However, from Equation 33, it seems $\\phi^{(1)}$ is a matrix (if $[\\cdot,\\cdot]$ denotes concatenation). \n    - What does $...$ mean in the square brackets of Equation 33? In general, can you please clarify how to derive Equation 33 from Equation 30?\n- It seems Theorem 4 and 5 apply to both PMLP and the original GNN. Therefore there is still a gap to explain why PMLPs achieve performance close to GNNs. Specifically, I think it is an important question why replacing the GNN weights with MLP weights does not hurt accuracy. This question is not addressed by Theorem 4 and 5 – basically they don’t care about what the weights look like. \n- The setup of the theoretical analysis does not describe a realistic graph OOD scenario. When the test node $x_0$ is far away from the training nodes ($t\\rightarrow \\infty$), it likely won’t have any direct connections with the training nodes. i.e., it may have some multi-hop connections to the training nodes via other test nodes not too far away from the training nodes. In summary, I agree that the linear coefficient of extrapolation will depend on graph structure, but I don’t think $\\tilde{d}\\cdot \\tilde{d_i}$ will be the realistic coefficient. Note that such concern does not apply to Theorem 3 on MLPs, since edges don’t exist in that case. \n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "HGwDhYzILA", "reviewer": "Reviewer_JEyU", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "The paper presents an analysis targeting the generalization in graph neural networks. The key idea is to decouple the node's information processing from the message passing operations. To this aim, it is introduced a new neural network paradigm, called PMLP, such that the weight values of a GNN are trained in the MLP form, and then only at inference stage the message passing operations are introduced. The approach is assessed in several tasks for node classification. To shed light on the reasons behind the good performances found in practice, the authors elaborate on the connections between MLP, PMLP, GNN and their respective neural tangent kernels equivalent.\n\nUpdate after rebuttal: I thank the authors for addressing my concerns on the submitted version of the paper. I am happy to confirm my positive score.", "summary_of_the_review": "In my view, the paper seems novel and interesting enough.\nA few more details on the experimental settings (as specified above) can confirm the relevance of the achieved results.", "strength_and_weaknesses": "Strengths\n* Novelty: the paper brings a new perspective in the analysis of GNN architectures (to the best of my knowledge)\n* The mathematical analysis and the links to the NTK seem sound and interesting\n* The experimental analysis seems comprehensive and relevant for the purposes of the paper\n\nWeaknesses:\n* Despite the paper is clear and the analysis interesting, I find surprising that the weights trained in the MLP work so well in most cases. Does this aspect mean that essentially to achieve a good classification it is sufficient to consider local nodes' information, and structural information encoding can be somehow neglected. It would be interesting to see a discussion on this aspect.\n* Model selection and fine-tuning is not completely clear. In particular, it is not clear to me how the number of layers and neuron per layers are chosen, and if the hyper-parameters are tuned (on the validation set?) individually per each model and per task. Please clarify on this aspect for the sake of reproducibility of the results.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster