GRANOLA: Adaptive Normalization for Graph Neural Networks
Authors: Moshe Eliasof
Beatrice Bevilacqua
Carola-Bibiane Schönlieb
Haggai Maron
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Neural Networks
Normalization Layer in GNNs
Primary area: graph_neural_networks
TL;DR: We study the effect of normalization layers in GNNs and propose a novel layer, called GRANOLA, that is expressive and graph adaptive.

Abstract: Despite the widespread adoption of Graph Neural Networks (GNNs), these models often incorporate off-the-shelf normalization layers like BatchNorm or InstanceNorm, which were not originally designed for GNNs. Consequently, these normalization layers may not effectively capture the unique characteristics of graph-structured data, potentially even weakening the expressive power of the overall architecture. 
While existing graph-specific normalization layers have been proposed, they often struggle to offer substantial and consistent benefits. In this paper, we propose GRANOLA, a novel graph-adaptive normalization layer. Unlike existing normalization layers, GRANOLA normalizes node features by adapting to the specific characteristics of the graph, particularly by generating expressive representations of its nodes, obtained by leveraging the propagation of Random Node Features (RNF) in the graph. We provide theoretical results that support our design choices as well as an extensive empirical evaluation demonstrating the superior performance of GRANOLA over existing normalization techniques. Furthermore, GRANOLA emerges as the top-performing method among all baselines in the same time complexity class of Message Passing Neural Networks (MPNNs).

GRANOLA: Adaptive Normalization for Graph Neural Networks
Moshe Eliasoff University of Cambridge me5320cam. ac. uk
Beatrice Bevilacqua" Purdue University bbevilacQpurdue edu
Carola-Bibiane Schönlieb University of Cambridge cbs318 @aam..cam..... ac uk
Haggai Maron
Technion & NVIDIA Research hmaron@nvidia com
Abstract
Despite the widespread adoption of Graph Neural Networks (GNNs). these models often incorporate off-the-shelf normalization layers like BatchNorm or Instan- ceNorm, which were not originally designed for GNNs. Consequently, these normalization layers may not effectively capture the unique characteristics graph-structured data, potentially overall architecture. While existing graph-specific normalization layers have been proposed, they often struggle offer substantial and consistent benefits. In this paper, we propose GRANOLA, novel graph-adaptive normalization layer. Unlike existing normalization layers, GRANOLA normalizes node features by adapting the specific characteristics of the graph, particularly by generating expressive rep- resentations of its nodes, obtained by leveraging the propagation of Random Node Features (RNF) in the graph. We provide theoretical results that support our design choices as well as an extensive empirical evaluation demonstrating the superior performance of GRANOLA over existing normalization techniques. Furthermore, GRANOLA emerges as the top-performing method among all baselines the same time complexity class of Message Passing Neural Networks (MPNNs).
weakening the expressive power of the
1 Introduction
Graph Neural Networks (GNNs) have achieved remarkable success in several application domains [35, 61], showcasing their ability to leverage the rich structural information within graph data. Recently, a plethora of different layer designs has been proposed, each tailored to address specific challenges in the context GNNs, such as limited expressive power [63, 41, 40] and oversmoothing [46]. Notably, analogously to architectures in other domains [30, 18], these GNN layers often interleaved with normalization layers, as the integration of normalization methods has empirically proven beneficial in optimizing neural networks, facilitating convergence and enhancing generalization [34, 7, 55].
In practice, most existing GNN architectures employ standard normalization techniques, such as BatchNorm [34], LayerNorm [3], or InstanceNorm [58]. However, these widely adopted normaliza- tion techniques were not originally designed with graphs and GNNs in mind. Consequently, they may not effectively capture the unique characteristics of graph-structured data, and can also hinder the expressive power of the overall architecture [11]. These observations highlight the need for graph-specific normalization layers.
'Equal Contribution
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Recent works have taken initial steps in this direction, mainly targeting oversmoothing [72, 64. 74] or the expressive power of the overall architecture [11, 14]. Despite the promise shown by these methods, consensus on a single normalization technique best suited for diverse tasks remains elusive, with no single normalization technique proving clearly superior across all benchmarks and scenarios.
Our approach. In this paper, we identify adaptivity to the input graph structure as a desirable property for an effective normalization layer in graph learning. Intuitively, this property ensures that the normalization is tailored to the specific input graph, capturing attributes such as the graph size, node degrees, and connectivity. Importantly, we claim and demonstrate that, given the limitations of practical GNNs, achieving full adaptivity requires expressive architectures that can detect and disambiguate graph substructures, thereby better adapting to input graphs.
Guided by this desirable property, which is absent in existing normalization methods, we introduce our proposed approach- GRANOLLA (Graph Adaptive Normalization Layer). GRANOLA aims at dynamically adjusting node features at each layer by leveraging learnable characteristics of the node neighborhood structure derived through the utilization of Random Node Features (RNF) [44, 1, 51, 56, 17J. More precisely. GRANOLA samples RNF and uses them in an additional normalization GNN to obtain expressive intermediate node representations. The intermediate representations are then used to scale and shift the node representations obtained by the preceding GNN layer.
We present theoretical results that justify the primary design choices behind our method. Specifically, we demonstrate that GRANOLA is fully adaptive to the input graph, which, in other words, means that GRANOL can predict different normalization values for non-isomorphic nodes. This property arises from the maximal expressive power of the normalization GNN we employ (MPNN augmented with RNF [1, 51). In addition, we show that our method inherits this expressive power. Lastly, we show that using standard MPNN layers without RNF within GRANOLA cannot result in a fully adaptive method or in any additional expressive power.
Empirically, we show that GRANOLA significantly and consistently outperforms all existing standard as well GNN-specific normalization schemes on variety of different graph benchmarks and architectures. Furthermore, GRANOLA proves to be the besf-performing method among all baselines that have the same time complexity as the most widely adopted GNNs, namely the family of MPNNs.
Contributions. Our contributions are as follows: (1) We provide an overview of different normaliza- desirable property of normalization layers that existing methods are missing, (2) We introduce GRANOLA, a novel normalization technique adjusting node features based on learnable characteristics of their neighborhood structure, (3) We present an intuitive theoretical analysis of our method, giving insights into the design choices we have made, and (4) We conduct an extensive empirical study, providing a thorough benchmarking of existing normalization methods and showcasing the consistently superior performance of GRANOLA.
tion schemes in graph learning, outlining adaptivity
2 Normalization layers for GNNs
2.1 Basic setup and definitions
Let G (A, X) denote graph with N N nodes, where A E NNN is the adjacency matrix and X E N is the node feature matrix, with C' E N the feature dimension. Consider a batch of
B-1 B E N graphs encoded by the adjacency matrices [As) and, for simplicity, assume that all graphs in the batch have the same number of nodes N. We consider model composed of L GNN layers, with L E N. Each GNN layer is followed by a normalization layer NORM and an activation function é. At any layer& & E [L]. the output of the GNN layer for a batch of graphs consists of (intermediate) node representations, which can be gathered in a matrix (0) E BxxN (since all graphs have the same number of nodes per our assumption2). These undergo a normalization and an activation layer, resulting in node representations denoted by ((²) E R B which serve as input of the next GNN layer, with Hi0) == X.² Throughout this paper, for any three-dimensional tensor, we use subscripts to denote access to a corresponding dimension. For example, we denote
the intermediate node representations of graph e [B] by H. NxC, and by h((0) the value of feature e E [C] in node n E [N] of graph b E [B].
It is always possible to meet this assumption by padding to the max number nodes. For simplicity and without loss of generality, assume that the feature dimension of all GNN layers is C.
2

---

InstanceNorm
BatchNorm DifiGroupNorm
PairNorm
LayerNorm-node
LayerNomm-raphh
MeanSSubractionNorm GraphNorm
NodeNorm
GraphSizeNorm
Figure I: Illustration of normalization layers. We denote by B, N and C' the number of graphs (batch size), nodes, and channels (node features), respectively. For simplicity of presentation, we use same number of nodes for all graphs. We color in blue the elements used to compute the statistics employed inside the normalization layer.
Formally, the intermediate, pre-normalized node features for the b-th graph in the batch are defined as
H GNN LAYER (As, H (
Then, the overall update rule for the batch of B graphs can be written as
H 1
NORM (HI(:))
for l E [T]. Equation (2) serves as a general blueprint, and in what follows we will show different ways to customize it in order implement different existing normalization techniques.
consider normalization layers based on the standardization [38] of their inputs, as this repre- sents the most common choice in widely used normalizations. Generally, standardization-bins based normalization layer first shifts each element bynn by some mean (*t,a,es and then scales by the corresponding standard deviation Dbnncc. i.e.
NORM (T (0,00)=
D,n.c
Ub..c
((())
Tb,n.c
where (0, (( E R are learnable affine parameters, that do not depend on nor n.
,
2.2 Current normalization layers for GNNs
The difference among different normalization schemes lies in the set of values used to compute the mean and standard deviation statistics for each element, or, more precisely, across which dimensions of (f) they are computed. We present them below, and visualize them in Figure
BatchNorm. BatchNorm [34] computes the statistics across all nodes and all graphs the batch, for each feature separately. Therefore, have
B
B
N
Σ b=1
e B.n.
Σ
(h (bb.n,e)
Pb, =
BN
BN
which implies that Pb.n.c n'c' for any V/ [B] and any n' [N] (and similarly for of BatchNorm in graph learning [63], it important recognize scenarios
Despite the widespread where alternative normalization schemes might be more suitable. concrete example illustrating this need presented in Figure 2, focusing on the task of predicting the degree of each node." 4 In this example, BatchNorm, by subtracting the mean computed across the batch, results in negative values for nodes with outputs below the mean. The subsequent ReLU application, [63, 37, 41], zeros out these negative values, leading to predictions of 0 for such nodes, irrespective of their actual degree. Additional insights are further discussed Example C. in Appendix C, where demonstrated that relying on the affine parameter (x()) to shift the negative output does not provide
standard practice
definitive solution, since 36 is the same for all graphs.
'The node degree fundamental feature in graph- based methods, for example Newman [45].

---

InstanceNorm. InstanceNorm [58] is simi- lar BatchNorm, but considers each graph separately, that is
N
1
(E)
Pb,
N
b.n.o
(5)
N
(a) Node degrees, computed by one message-passe layer.
( - pb,n,o)
b,n.c
n=1
which implies that Pb,n.c Pb,n'. for any n' E [N] (and similarly for m.m.)). No- tably, the example in Figure can be ex- tended to InstanceNorm by considering all
graphs in the batch as disconnected com-
(b) Subtraction of the mean node degree. The features
ponents in a single graph, as we show in Example C.4 in Appendix C.
nodes with degree less than average turn negative.
LayerNorm. LayerNorm [3] can be defined in two ways in the context of graphs [24]. The first, which we call LayerNorm-nu behaves similarly Lay- erNorm in Transformer architectures [59], and computes statistics across the features for each node separately, that is
(c) After ReLU, nodes with negative values mapped to the same value of 0, despite having different degrecs.
Figure 2: A batch of two graphs, where subtracting the mean of the node features computed across the batch, as in BatchNorm and related methods, results in the loss (6) of capacity to compute node degrees.
Pb,ncc 0
1
Σ
(E)
b.n.c
Σ (b - (b,,,,))
and therefore (b,,n Pb,a,e for any d' E [C] (and similarly for oi,,.). The second variant, which we call LayerNorm-graphh is similar to LayerNorm in Computer Vision [62], and computes statistics across the features and across all the nodes in each graph, that is
N
C
Pb,n,c NC
hon.e
o.n NC
ΣV n=1==
(b (b,,,))
n=1
and therefore ja,nne Pb,n'.e' for any n' [N] and any c' E [C] (and similarly for o,,,)) Example C.5 in Appendix C presents motivating example similar to Figure 2 for LayerNorm.
Graph-Specifie normalizations. Several normalization methods tailored graphs have been re- cently proposed. We categorize them based on which dimensions (the batch dimension B, the node dimension N within each graph, and the channel dimension C') are used to compute the statistics employed within the normalization layer. We illustrate this categorization in Figure 1. DiffGroop- Norm [74] and GraphSizeNorm [21] normalize features considering nodes across different graphs, akin to BatchNorm. Similarly to InstanceNorm, PairNorm [72] and MeanSSbrractionNomm [64] shift the input by the mean computed per channel across all the nodes in the graph, with differences the scaling strategies. GraphNorm [11] extends InstanceNorm by incorporating a multiplicative factor to the mean. NodeNorm [75] behaves similarly to LayerNorm-node
only scales the input, without shifting it. We provide additional details in Appendices A and B, and include methods that normalize adjacency matrix before the GNN layers, which, however, fall outside the scope of this work.
3 Method
The following section describes the proposed GRANOLA framework. We start with identifying adaptivity desired property in graph normalization layer.

---

Node Feature Extraction
GRANOLA
m
NONM
HG
I Pouturea
Inpact Gruphik, Mods Featuree 11""1
OhNV Festures
Nermaibation
Paramettrrs
Randoo
Figure 3: Illustration of a GRANOL. layer. Given node features H ((-1) and the adjacency matrix As. feed them to G) LAYER to extract intermediate node features H Then, predict normalization parameters using GNN NORM. which takes sampled RNF R, H As. Including R with As and H!) enhances the expressiveness of GRANOLA ensuring full adaptivity.
Motivation. In the previous section, we observed that current normalization schemes used within GNNs are mostly borrowed or adapted from other domains and that they possess two main limitations: (i) Using BatchNorm and InstanceNorm (as well as many methods derived from them, including graph-specific methods) can limit the expressive power of GNNs that use them, preventing them from being able to represent even very simple functions such as computing node degrees; (ii) As shown in previous works, as well as in our experiments in Section 5, these methods do not provide consistent benefit in downstream performance on different tasks and datasets.
One possible reason for these limitations is that the discussed methods use the same affine parameters in the normalization process, irrespective of the input graph. Crucially, unlike other more structured data types, such as images and time series, graphs do not differ merely in the values associated with each element or time step. Instead, graphs fundamentally vary the actual connectivity between the nodes. Therefore, it might make sense to employ different (adaptive) normalization schemes based on the features and the connectivity of the input graph. Next, we explore this concept and show that carefully accounting for the graph structure in the normalization process may enhance the expressive power of the GNN, overcoming the previously mentioned failure cases, and providing consistent experimental behavior and overall improved performance.
3.1 Design considerations and overview
In an adaptive normalization, instead of using the same affine parameters % and p! (Equation (3)) for all the nodes in all the graphs, the normalization method utilizes specific parameters conditioned on the input graph. Importantly, in other domains, adaptivity in normalization techniques has proven to be a valuable property [19, 33, 48, 76, 47, 49]. In GRANOLA, we achieve this property by generating affine parameters using an additional normalization GNN that takes the graph as input, similarly to Hypernetworks [29] that generate weights for another network. Importantly, for full graph adaptivity, where the network can assign different normalization parameters for every pair of non-isomorphic nodes, the normalization GNN should have maximal expressive power. Due to the limited expressive power MPNNs [41, 63), when designing GRANOLA, we advocate for using normalization GNN with high expressiveness. Notably, most expressive GNNs come the expense of significantly increased computational complexity [16. 71, 4, 69, 40, 43]. For this reason, we parameterize the normalization GNN using an MPNN augmented with Random Node Features (RNF), which provide strong function approximation guarantees [1, 51] while retaining the efficiency of standard MPNNs.
3.2 GRANOLA
We are now ready to describe our GRANOLA approach, which is based on the utilization of an additional GNN to compute the affine parameters and the integration of RNF [56]. These affine parameters are then used to normalize node representations obtained by the GNN layer preceding the normalization. An overview of GRANOLA is visualized in Figure 3 and described in Algorithm 1.
GRANOLA layer. At any given layer [4], for each graph E [B], we sample RNF R NNK K E N, from some joint probability distribution, e.g., Normal, R D. Then,
5

---

Algorithm GRANOLA Layer
Input: Node features H E TRNxC, obtained from GNN (t-1)
LAYER-
Output: Normalized features per node n E [N] and channel c E [C].
1: Sample random node features R
E IRNK
2: Compute Z GNN (A.. H
2 e
3: Compute affine parameters:
Th,n ( ())))
(6)
(Fb.n)
4: Compute mean and Hundard-deviation pb,nc and dnn.c of !
5: Return (2) Ta
Pb.n.e B Pb....
asm..c
concatenate R with the intermediate node features H obtained from GNN (C-) and pass the resulting feature matrix through an additional GNN, ie..
(Equation (1)),
GNN NORM (Ap. H + R
(8)
where @ denotes feature-wise concatenation, and GNN NORM is shallow GNN architecture, with LoOK layers. The affine parameters then computed from z,[) E ERNx that is
Th.n f( (Z
b,a f2 (2)
(9)
(0) where 8/9, are learnable functions (e.g., MLPs), and Tom is defined as
8 R Then, GRANOLA layer
(h bin H -b,ne Tb,n.c
(f)
(10)
where n., and dbn.c are the mean and std of ( computed per node across the feature dimension, exactly as in LayerNorm-node (Equation (6)). We highlight here a noticeable difference compared to standard normalization formulations, as presented in Equation (3): in GRANOLA, 7b.n e² a(O not only depend on c, but they also have dependency on b and n and indeed vary for different graphs and nodes. Notably, this is possible because normalization is adaptive to the input graph. Methods that disregard this information are compelled to use the same learnable normalization values for all graphs, they operate without knowledge of the specific input graph being considered.
We consider variant of GRANOLA that does not sample RNF and instead uses only H to obtain Z!") in Equation (8), which therefore becomes
GRANOLA-NO-RNE.
Z
GN
NORM (A, !
(11)
We refer to this variant GRANOLA-NO-RNE it allows to directly quantify the contribution of the expressiveness offered by augmenting it with RNF as in Equation (8).
Complexity. We conclude by remarking that both GRANOLA and its variant, GRANOLA-NO-RNY do not impact the asymptotic time and space complexity of standard MPNNs, which remains linear in the number of nodes and edges, we show in Appendix G.
4 Theoretical Analysis
In this section, we explain the main design choices taken in the development of GRANOLA. Specifi- cally, we elaborate the advantages obtained by utilizing RNF as part of the normalization scheme as opposed to relying solely on the node features. We assume all GNN layers, including those within GRANOLA (Equation (8)) are message-passing layers, as the ones in Xu al. [63], Morris et al. [41].
The advantages of using RNF-augmented MPNNs for normalization. We start by observing that the integration of our GRANOLA in an MPNN allows to easily default to an MPNN augmented

---

with RNF [56], as we formalize in Proposition E.2 in Appendix E. The idea of the proof lies in the abiliit of the first normalization layer to default to outputting its input RNF, enabling the rest of the architecture to function as an MPNN augmented with these RNF. The significance of this result lies in the fact that MPNN GRANOL. inherits the (c, 6) -univerrll approximation properties previously proved for MPNNs augmented with RNF [1, 51]. This naturally solves the limitations of existing normalizations identified in Section 2.2, as an MPNN + GRANOLA can leverage universality to approximate such functions. Importantl, the universality of MPNNs augmented with RNF further implies that GRANOLA is fully adaptive, as it can approximate any equivariant function on the input graph [1], and therefore can approximate functions returning different normalization values for non-isomorphic nodes.
Why RNF are necessary? While GRANOLA employs RNF to compute the normalization affine (E) parameters Th.m. and [.f] Pi the same procedure can be applied without the use of RNF, variant we denoted GRANOLA-NO-RNE in Section 3 (Equation (I))). However, we theoretically demonstrate next that an MPNN + GRANOLA-NO-
not only loses the universal approximation properties, but is also not more expressive than standard MPNNs.
Proposition 4.1 (RNF are necessary in GRANOLA for increased expressive power). Assume our imput domain consists of graphs of a specific size. For every MPNN with GRANOLA-NO-RNE (Equation (11)) there exists a standard MPNN with the same expressive power.
Proposition 4.1 is proven by showing that an MPNN with GRANOLA-NO-RNE can be implemented by standard MPNN, and, therefore, its expressive power is bounded by the expressive power of a standard MPNN. The proof can be found in Appendix E. This limitation underscores the significance of RNF within GRANOLA. Furthermore, our experiments in Section 5 show that omitting the RNF within the normalization results in degraded performance, as GRANOLA always outperforms TRANOLL--N-RRE- Finally, we remark that this theoretical result emphasizes the necessity of RNF for increased expressiveness and, consequently, for ensuring full adaptivity to the input graph. That is, any normalization generated by GRANOLA-NO -NO-RNN will be limited by the expressive power of standard MPNNs while GRANOLA does not have this limitation.
Relation to expressive GNNs. The results in this section highlight the connection between GRANOLA and expressive GNNs, as our method inherits enhanced expressiveness of MPNNs augmented with RNF Notably, while MPNNs with RNF have demonstrated theoretical improvements in expressive- ness, their practical performance on real-world datasets has not consistently reflected these benefits [22]. Our experimental results indicate that GRANOLA serves as a valuable bridge between theory and practice. Specifically, our findings address the gap between the theoretical expressiveness of MPNNs that use RNF, and their limited practical utility. This is achieved by effectively incorporating RNF within the normalization process rather than simply treating it as an additional input to the MPNN. Importantly. GRANOLA gives rise to method that is efficient, provably expressive, and performs well in practice, something that, to our knowledge, has never been accomplished by any previous architecture. This provides an additional perspective to our contribution: beyond designing an effective and efficient normalization layer, which is the main scope of our work, we offer a practical approach realizing the theoretical benefits of RNF. Finally, we conclude this section by remarking that GNN NORM in Equation (8) can be modified to be any other expressive architecture, and our design choice was mainly guided by the computational practicality of RNF, that allows GRANOLA to offer increased expressive power while retaining the linear complexity of MPNNs, as discussed in Appendix G. We refer the reader to Morris et al. [43] for survey on expressive methods.
Experimental Results
In this section, we evaluate the performance of GRANOLA. In particular, we seek address the following questions: (1) How does GRANOLA compare to other normalization methods? (2) Does GRANOLA achieve better performance than its natural baselines that also leverage RNF, that is, how important is the graph-adaptivity within GRANOLA? ? (3) How does GRANOLA compare to its which does not leverage RNF within the normalization, that is, how important are the RNF within GRANOLA? In what follows, we present our main results and refer to Appendices F to H for details and additional experiments, including timings and ablation studies. Our code is available at https: / //gi gighhb.bc... com www./oooo/ooooieee http///ohhheeasf//o. /Ro GRANOLA.
variant BRANOLA-NO-RYY
7

---

Table 2: A comparison to natural baselines, standard and graph normalization layers, demonstrating the practical advantages of GRANOLA. The top three methods are marked by First, Second, Third.
Method
MOLESOI. RMSE 4
MOLTOX21 ROC-AUC 1
MOLRACE ROC-AUC
ROC-AUC
NATURAL BASELINES
GIN + BatchNorm + RNF-PE [56]
1.022=0.041
75.14:10.67 75.12.10.92
74,28::3.80 77.96.14.6
75.98:11.63
GIN RNF-NORM
1.039.10.040
1 1.64
STANDARD NORMALIZATION
GIN + BatchNNomm [63]
1.173=0.057
74.91=0.51
72.97=4..00
75.58=1144
GIN + InstanceNorm [58]
1.09:=0.038
73.82:+0.96
3..86
76.88 1.93
GIN LayerNorm mode [3]
1.058.10.02
74.81 1:0.4
2.772
75.24 1.71
GIN + Laaerrorr-grapp [3]
0.004
75.03-11.24
76.49
76. 13- 1.84
Idenlity
1.164:10.059
7.034:11008
72.55
71.89 1.32
GRAPH NORMALIZATION LAYERS
GIN PairNorm [72]
1.84:10.031
73.27:1:.05
75.11 4:2.4
76.18:11.4 1.47
GIN + MeanSahtractionoom [64]
0.052.0.0055
74.98
76.36 4,47
76.37 1.40
NilIGrropNoomm [74]
1.87:10.063
04.48:10.76
75.96
74.37=1..68
GIN + NodeNorm [75]
1.068100.029
03.27
75.67 4.00
75.50 1.32
GIN + GraphNorm [I]]
1.044=0.027
0..54-10.80
73.2343.88
78.08-:11 1.16
GIN GraphSizeNorm [21]
1.121=0.051
74.07=00.30
76. 3.552
1..44=1.51
GIN + SuperNorm [12]
0.037:00004
75.08
3.312
76.55 1.76
GIN + GRANOLA-NO NO RNF
1,088 1: 0.032
:5087
76.23 2.006
77.09 1.449 1.49
GRANOLA
0.960=10.020
77.19:10.85
2.59
78.98.1 1.17
For each task, we consider the following baselines: (1) Standard normalization layers, (2) Graph-designated normalization layers and (3) Our natural baselines, namely: (i) GRANOLA-NO-RN which corresponds to the variant of GRANOLA that uses only the intermediate features, without RNF, inside the normalization (Equation (11)) to assess the practical importance of RNF for full graph-adaptivity; (ii) RNF as positional encoding (RNF-PF), where we augment only the initial input features with RNF, as in Sato et [56]; (iii) The normalization that uses only RNF, without any message passing layer inside the normalization, to compute the normalization affine parameters T.m.cc
Baselines,
and B/ This is achieved by considering g Rg in Equation (8). We denote this baseline by RNF-NORM and remark that it corresponds to version of GRANOLA without graph-adaptivity. For a fair comparison, in all the baselines, as well as in our method, we employ GIN [63] or GINE [32] layers, which are maximally-exprest compare GRANOLA to GNNs the same complexity class and refer the reader to Appendix H.8 for additional comparisons.
within the MPNN family. Furthermore, we
ZINC. We experiment with the ZINC-12K
Table 1: Comparison of GRANOLA with various baselines on the ZINC- 12k dataset. All methods obey the 500k parameter budget. The top three methods are marked by First, Second, Third.
molecular dataset [57, 28, 21]. where the goal is to regress the solubility of molecules. As can be seen from Table 1, GRANOLA achieves signif- icantly lower (better) mean-absollte--mre com- pared to existing standard and graph-designated normalization layers, while outperforming all its natural baselines. Moreover, GRANOLA emerges as the best- perfoorrrr model with the same time complexity of a standard MPNN.
Method
ZINC J)
NATURAL BASELINES
GIN + BatchNorm RNF-PE
0.1621
GIN + RNF-NORM
0.1562==0.013
STANDARD NORMALIZATION LAYERS
GIN + BatchNarm [63]
0.1630.10.000
OGB. We test our GRANOLA on the OGB col- lection [31], and report its performance in Ta- ble 2. Notably, GRANOLA consistently im- proves over existing standard normalization methods while retaining similar asymptotic com- plexity. For instance, on MOLBACE, we achieve an accuracy of 79.92% compared to 72.97% when using BatchNorm, an improvement of 6.95%. Compared with graph-designated nor- malization methods, GRANOLA also offers consistent improvement. As an example, on MOLESOL obtain RMSE of (lower is bet-
GIN InstanceNorm [58]
0.2984-:0.017
GIN + LayerNorm-sode [3]
0,1649:
+ LayerNorm-gran
0.1609::0.014
GIN Identity
0.2209=:0.018
GRAPH NORMALIZZTTION LAYERS
GIN + PairNorm [72]
0.3519=00008
+ MeunSubtrationNorm [64]
0.1632-:0.021
GIN DiffGroupNorm [74]
00.024
GIN + NodeNorm [75]
0.2119=00.017
GIN + GraphNorm [1]]
0.3104::..012
GIN + GraphSizeNorm [21]
0.1931-10.01
GIN SuperNorm [12]
0.1574100008
GIN + GRANOLA-NO-RNN
0.1497+40.008
GIN GRANOLA
0.0003
8

---

Training Loss
Training Loss
Training
Hardly tho hurts
Hardyy the
Hardly tho hurts
Epoch
Epoch
Epoch
(a) ZINC- 12K
(b) MOLHIV
(c) MOLTOX21
Figure Training convergence of GRANOLA compared with existing normalization techniques show that GR ANOLA achieves faster convergence and overall lower (better) MAE.
Table 3: Empirical results of GSN with GRANOLA show that GRANOLA can also improve the performance of expressive methods.
Method
ZINC MAE 4
MOLESOL RMSE 4
MOLTOX21 ROC-AUC 1
MOLBACE ROC-AUC
MOLHIV ROC-AUC 1
GSN [10]
0.1010:10.010 0.076620.008
1.03-10.037
76.08-10.79
77.40:12292
80.39-10.900
GRANOLA
0.9414
77.8440..3
80.4142.07
81.12:20.79
ter) 0.960, compared to the second best graph normalization layer, GraphNorm, that achieves 1.044. is also noteworthy to mention the performance gap between GRANOLA and its natural baselines, such as RNF-PE, which emphasizes the practical benefit of graph-adaptivity within GRANOLA.
TUDatasets. We experimented with popular datasets from the TUD [42] repository. Our results are reported in Table 14 in Appendix H.8, suggesting that GRANOLA consistently achieves higher accuracy compared
its natural baselines, as well as standard and graph- deep-ddeegn normaliza- tion techniques. For example, on the NCI109 dataset, GRANOLA achieves an accuracy of 83.7%, compared to the second-best normalization technique, GraphNorm, with an accuracy 82.4%.
Training convergence of GRANOLA. In addition to improved downstream task performance being one of the main benefits of normalization layer, accelerated training convergence is also important desired property [34, 1 11]. Figure shows that GRANOLA offers faster convergence and lower MAE compared to other methods.
Combining GRANOLA with expressive methods. Since our goal is to understand the impact of normalization layers, our experiments focus studying the benefit of augmenting standard and well-understood MPNNs with GRANOLA. However, it is also interesting to understand if expressive, domain- expert approaches such as GSN [10] also benefit from GRANOLA. To this end, augment GSN with GRANOLA, and report the results in Table 3. These results further underscore the versatility of GRANOLA, which can be coupled with any GNN layer and improve its performance.
Discussion. Our experimental results cover standard normalization layers, as well as graph nor- malization methods, evaluated on 11 datasets from diverse sources, and applied to various tasks. Throughout all experiments, a common theme is the performance consistency of GRANOLA. Specif- ically, GRANOLA always improves over its natural baselines and other normalization techniques across all datasets. In contrast, other existing methods exhibit less clear trends in their performance. While some methods achieve competitive results on certain datasets, they may struggle others. Notable examples are GraphNorm and PairNorm, which, despite offering improved performance compared to BatchNorm most of the OGB datasets, show worse results on ZINC- 12k. Further- more, standard normalization layers also lack consistency. As an example, consider InstanceNorm, which is beneficial in some OGB datasets, yet, it does not offer favorable results ZINC-12K.
Conclusions
In this paper, we discuss the existing landscape of feature normalization techniques in Graph Neural Networks (GNNs). Despite recent advances in designing graph normalization techniques, the optimal choice remains unclear, with methods not offering consistent performance improvements across tasks. To address this challenge, we identify desirable property of graph normalization layers, namely

---

adaptivity to the ipput graph, and argue that it can be obtained only with expressive architectures. To incorporate this property, we present GRANOLA, normalization layer that adjusts node features based on the specific input graph, leveraging Random Node Features (RNF). Our theoretical analyses support the design choices of GRANOLA, demonstrating its increased expressiveness. Empirical evaluations across diverse benchmarks consistently highlight the superior performance of GRANOLA over existing normalization methods, as well as other baselines with the same time complexity.
Limitations and impact. Although GRANOLA exhibits promising results, there are areas for potential
improvement in future research. For instance, investigating alternative designs for GNN NORM could further enhance the performance, as, in certain datasets, there is still a gap between GRANOLA and expressive GNNs. Additionally, exploring ways reduce memory and time complexity (which still linear in the number of nodes) represents an important avenue for future research. Furthermore, by improving the performance of GNN through GRANOLA we envision positive impact in domains such as drug discovery.
Acknowledgements
ME is funded by the Scientific Discovery, and the Maths4DL EPSRC Programme. HM is the Robert J. Shillman Fellow and is supported by the Israel Science Foundation through a personal grant (ISF 264/23) and an equipment grant (ISF 532/23).
fellowship, the Cambridge Accelerate Programme for
References
[1] Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The sur- prising power of graph neural networks with random node initialization. arXiv preprint arXiv:2010.01 179, 2020.
[2] Muhammad Awais, Md Tauhid Bin Igbal, and Sung- Ho Bac. Revisiting internal covariate shift for batch normalization. IEEE Transactions on Neural Networks and Learning Systems, 32(11): 5082-5092 2020.
[3] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint 1607. 06450, 2016.
[4] Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. International Conference on Learning Representations, 2022.
[5] Beatrice Bevilacqua, Moshe Eliasof, Eli Meirom, Bruno Ribeiro, and Haggai Maron. Efficient subgraph gnns by learning effective selection policies. arXiv preprint urXiv:2310.20082. 2023.
[6] Lukas Biewald. Experiment tracking with weights and biases, 2020. Software available from wandb.com.
[7] Nils Bjorck, Carla P Gomes, Bart Selman, and Kilian Q Weinberger. Understanding batch normalization. Advances neural information processing systems, 31, 2018.
[8] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Liò, Guido Montúfar, and Michael Bronstein. Weisfeiler and lehman go cellular: CW networks. In Advances in Neural Information Processing Systems, volume 34, 2021.
[9] Cristian Bodnar, Fabrizio Frasca, Yu Guang Wang, Nina Otter, Guido Montúfar, Pietro Lio, and Michael Bronstein. Weisfeiler and lehman go topological: Message passing simplicial networks. ICML, 2021.
[10] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEFE Transactions on Pattern Analysis and Machine Intelligence, 2022.
10

---

[11] Tianle Cai, Shengjie Luo. Keyulu Xu, Di He, Tie-yan Liu, and Liwei Wang. Graphnorm: A principled approach to accelerating graph neural network training. In International Conference on Machine Learning, pages 1204-1215. PMLR, 2021.
[12] Kaixuan Chen, Shunyu Liu, Tongtian Zhu, Ji Qiao, Yun Su, Yingjie Tian, Tongya Zheng, Haofei Zhang, Zunlei Feng, Jingwen Ye, et al. Improving expressivity of gnns with subgraph-speciffc factor embedded normalization. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 237-249, 2023.
[13] Yihao Chen, Xin Tang, Xianbiao Qi. Chun-Guang Li, and Rong Xiao. Learning graph normal- ization for graph neural networks. Neurocomputting. 493:613-660 625,1,6,,,, 2022.
[14] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances neural information processing systems, 33:10383-1000 10395, 2020.
[15] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Lio, and Petar Veličković. Principal neighbourhood aggregation for graph nets. In Advances in Neural Information Processing Systems, 2020.
[16] Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph representations. In NeurlPS, 2021.
[17] George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural networks for node disambiguation. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, pages 1126-2132 2021.
[18] Jacob Devlin, Ming-Wa Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In North American Chapter of the Association for Computational Linguistics, 2019.
[19] Vincent Dumoulin, Jonathon Shlens, and Manjunath Kudlur. A learned representation for artistic style. arXiv preprint arXiv: 1610.0769, 2016.
[20] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations, 2022.
[21] Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1-44 48, 2023.
[22] Moshe Eliasof, Fabrizio Frasca, Beatrice Bevilacqua, Eran Treister, Gal Chechik, and Haggai Maron. Graph positional encoding via random feature propagation. In International Conference on Machine Learning, pages
2023.
[23] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[24] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PoTch Geometric. In ICLR Workshop on Representation Learning Graphs and Manifolds, 2019.
[25] Fabrizio Frasca, Beatrice Bevilacqua, Michael Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetries. Advances in Neural Information Processing Systems. 35:31376-31399 2022.
[26] Golnaz Ghiasi, Honglak Lee, Manjunath Kudlur, Vincent Dumoulin, and Jonathon Shlens. Exploring the structure of real-time, arbitrary neural artistic stylization network. arXiv preprint arXiv: / 705.06630, 2017.
[27] Ian Goodfellow, Jean Pouget-Abadie Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in neural information processing systems, 27, 2014.

---

[28] Rafael Hemmez-Bombarelli, Jennifer N. Wei, David Duvenaud, José Miguel Hemández-Lobato Benjamín Sänchez-Lengelinng Dennis Sheberla, Jorge Aguilera-Iparragune Timothy D. Hirzel, Ryan P. Adams, and Alán Aspuru-Guzik. Automatic chemical design using data-driven continuous representation of molecules. ACS Central Science, 4(2):268-22 276, Jan 2018.
[29] David Ha, Andrew Dai, and Quoe V. Le. Hypernetworks, 2016.
[30] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In Computer Vision-ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 1 11-14, 2016, Proceedings, Part IV 14, pages 645. Springer, 2016.
[31] 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 In Advances in Neural Information Processing Systems, volume 33, 2020.
[32] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In International Conference on Learning Representations, 2020.
[33] Xun Huang and Serge Belongie. Arbitrary style transfer in real-time with adaptive instance normalization. In Proceedings of the IEEE international conference on computer vision, pages 1501-1510, 2017.
[34] Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pages 448-456. pmlr, 2015.
[35] John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ron- neberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Zídek, Anna Potapenko, al. Highly accurate protein structure prediction with alphafold. Nature, 596(7873):583-589, 2021.
[36] Tero Karras, Samuli Laine, and Timo Aila. A style-based generator architecture for generative adversarial networks. In Proceedings of the IÉEE/CVF conference on computer vision and pattern recognition, pages 4401-4411 2019.
[37] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. ICLR, 2017.
[38] Richard J Larsen and Morris L Marx. An introduction to mathematical statistics. Prentice Hall Hoboken, NJ, 2005.
[39] Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens, 2020.
[40] Haggai Maron, Heli Ben- Gam-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In NeurIPS, 2019.
[41] Christopher Morris, Martin Ritzert, Matthias Fey, William Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. Proceedings of the AAAI conference on artificial intelligence, volume 33, 2019.
[42] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020.
[43] Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so 2021.
far. arXiv preprint arXiv:21
[44] Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. International Conference on Machine Learning, pages 4663 4673. PMLR, 2019.
[45] Mark Newman, Nenworks: An Introduction. Oxford university press, 2010.
12

---

[46] Hoang Nt and Takanori Machara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv:1905.09550 2019.
[47] Eduardo Ogasawara, Leonardo C Martinez, Daniel De Oliveira, Geraldo Zimbrão, Gisele Pappa, and Marta Mattoso. Adaptive normalization: A novel data normalization approach for non-stationary time series. In The 2010 International Joint Conference on Neural Networks
(IJCNN), pages 1-8. IEFF, 2010.
[48] Taesung Park, Ming- Yu Liu, Ting-Chur Bin--Chn Wang, and Jun- Yan Zhu. Semantic image synthesis with apatiall--adapiin normalization. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 2337-2346, 2019.
[49] Nikolaos Passalis, Anastasios Tefas, Juho Kanniainen, Moncef Gabbouj, and Alexandros losifidis. Deep adaptive input normalization for time series forecasting, IEEE transactions on neural networks and learning systems, 3109):760-3375, 2019.
[50]
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024-8035. Curran Associates, Inc., 2019.
[51] Omri Puny, Heli Ben- Ben-Hamu, and Yaron Lipman. Global attention improves graph networks generalization. arXiv preprint arXiv:2006.077 07846, 2020.
[52] Omri Puny, Derek Lim, Bobak Kiani, Haggai Maron, and Yaron Lipman. Equivariant poly- nomials for graph neural networks. In International Conference on Machine Learning, pages 28191-28222. PMLR. 2023.
[53] Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35:14501-14515, 2022.
[54] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference Learning Representations, 2019.
[55] Shibani Santurkar, Dimitris Tsipras, Andrew Ilyas, and Aleksander Madry. How does batch normalization help optimization? Advances in neural information processing systems, 31, 2018.
[56] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM international conference on data mining (SDM), pages 333-341. SIAM, 2021.
[57] Teague Sterling and John J. Irwin. ZINC 15 - ligand discovery for everyone. Journal of Chemical Information and Modeling, 55(11):2324 223222322-33,, 11 2015. doi: 10. 00.1021/acs.cimm5500555.
[58] Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky. Instance normalization: The missing ingredient for fast stylization. arXiv preprint arXiv: 1607.0002,, 2016.
[59] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, tukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
(60) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[61] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic graph enn for learning on point clouds. ACM Transactions on Graphics (tog), 1-2, 2019.
13

---

[62] Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European conference on computer vision (ECCV), pages 3-19, 2018.
[63] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
[64] Chaoqi Yang, Ruijie Wang. Shuochao Yao, Shengzhong Liu, and Tarek Abdelzaher. Revisiting over-smoothing in deep gens. arXiv preprint arXiv:2003.136663 2020.
[65] Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, and Haggai Maron. From local structures size generalization in graph neural networks. In International Conference on Machine Learning, pages 1 11975-11988 PMLR, 2021.
[66] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie Liu. Do transformers really perform badly for graph representation? Advances in neural information processing systems, 34:28877-288888 2021.
[67] Jiaxuan You, Jonathan M Gomes-Selmant Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 10737-10745, 2021.
[68] Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small relu networks powerful memorizers: tight analysis of memorization capacity. Advances in Neural Information Processing Systems, 32, 2019.
[69] Bohang Zhang, Guhao Feng, Yiheng Du, Di He, and Liwei Wang. complete expres- siveness hierarchy for subgraph gnns via subgraph weisfeiler-lhmman tests. arXiv preprint vrXiv:2302.0009% 2023.
[70] Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of GNNs via graph biconnectivity. In The Eleventh International Conference Learning Representations, 2023.
[71] Muhan Zhang and Pan Li. Nested graph neural networks. Advances in Neural Information Processing Systems, volume 34, 2021.
[72] Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In International Conference on Learning Representations, 2020.
[73] Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. International Conference on Learning Representations. 2022.
[74] Kaixiong Zhou, Xiao Huang, Yuening Li, Daochen Zha, Rui Chen, and Xia Hu. Towards deeper graph neural networks with differentiable group normalization. Advances in neural information processing systems, 33:4917-4922 2020.
[75] Kuangqi Zhou, Yanfei Dong, Kaixin Wang, Wee Sun Lee, Bryan Hooi, Huan Xu, and Jiashi Feng. Understanding and resolving performance degradation in deep graph convolutional networks. In Proceedings of the 30th ACM International Conference on Information & Knowledge Managemeni, pages 2728-2732 2021.
[76] Peihao Zhu, Rameen Abdal, Yipeng Qin, and Peter Wonka. Sean: Image synthesis with semantic normalization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5104 514451177 13, 2020.
14

---

A Additional Related Work
Standard normalization layers. BatchNorm [34] is arguably one of the most widely used normaliza- tion schemes in deep learning. Despite its success, there is little consensus on the exact reason behind the improvements it generally yields. While some studies argue that the effectiveness of BotchNorm lies in its ability to control the problem of internal covariate shift [34, 2], other works [7, 55] attribute the success to the promotion of faster convergence. Similarly to the other domains, also in graph- learning. BatchNorm normalizes each channel (feature) independently by computing the mean and standard deviation across all the elements in the batch, i.e., across all the nodes in all the graphs in the batch. Another normalization approach that was adopted in graph-learning is InstanceNorm [58], which was originally introduced in image style-transfer tasks to remove image-specific contrast and style information. In the context of graphs, InstanceNorm normalizes each channel (feature) independently by computing the mean and standard deviation across all nodes within each graph separately. Additionally, LayerNorm [3] was originally proposed for recurrent models, and it is also widely used in Transformers architectures [59]. In the context of graph learning. LayerNorm can take two different versions: Layernorm-node and LayerNorm-grapp [23]. The former normalizes each node independently. by computing the mean and standard deviation across all channels within each node separately, while the latter uses the mean and standard deviation across all the channels of all nodes in the entire graph. We visualize these variants in Figure 1. The common theme of these three discussed methods that they were not originally designed with discuss heep-ddsignnted normalization techniques.
in mind. Next, we
Graph-designated normalization layers. PairNorm [72] was introduced to mitigate the issue of oversmoothing in GNNs, where repeated graph convolutions eventually make node representations indistinguishable from one and the other. The key idea of PairNorm is to ensure that the total pairwise feature distances remain constant across layers, preventing the features of distant nodes from becoming overly similar or indistinguishable. Yang et al. [64] proposed a different understanding of the oversmoothing issue in GNNs: the authors show that upon initialization GNNs suffer from oversmoothing, but GNNs learn anti-oversmooth during training. Based this conclusion, the authors design MlcanSubrractionNorm which removes the mean from the inputs, without rescaling the features. When coupled with GCN [37]. McanSubtractionNoorn leads to a revised Power Iteration that converges to the Fiedler vector, resulting in a coarse graph partition and faster training. To enhance the performance of GNNs on large graphs, Li et al. [39] propose MessageNorm, a method that normalizes the aggregated message for each node before combining it with its node features, demonstrating experimental benefits. DifiGroupNorm [74] was designed to alleviate oversmoothing by softly clustering nodes and normalizing nodes within the same group to increase their smoothness while also separating node distributions among different groups. Zhou et al. [75] explored the impact of transformation operators, such as normalizations, that transform node features after the propagation step in GNNs, and argue that they tend to amplify node-wise feature variance. This effect is shown to lead to performance drop in deep GNNs. To mitigate this issue, they introduced NodeNorm, which scales the feature vector of each node by a root of the standard deviation of its features. This approach also shares similarities with LayerNorm-node While the aforementioned normalization techniques have made significant strides in mitigating the oversmoothing phenomenon in GNNs, other normalization methods have been proposed to address problems beyond this specific concern. Cai et al. [11] showed that InstanceNorm serves as a preconditioner for GNNs, thus accelerating their training convergence. However, it also provably degrades the expressiveness of the GNNs for regular graphs. To address this issue, they propose GraphNorm, which builds on top of InstanceNorm by adding learnable multiplicative factor to the mean for each channel. GraphSizeNorm [21]
was proposed based on promising empirical results, and aims at normalizing the node features by dividing them by the graph size, before applying standard BatchNorm layer. UnityNorm [13]
was introduced to learn graph normalization by optimizing a weighted combination of existing techniques, including LayerNorm-node InstanceNorm, and BatchNorm. Finally, SuperNorm [12]
first computes subgraph-specifis factors, encompassing the number of nodes and the eigenvalues of the gigghorhood-inducee subgraph for each node. These cetogrraph-ppcciffe factors are then explicitly embedded at the beginning and end of a standard BatchNorm layer. This approach ensures that any arbitrary GNN layer becomes at least as powerful as the 1-WL test, while simultaneously mitigating the oversmoothing issue. We conclude this paragraph by acknowledging the existence of normalization techniques that focus on normalizing the adjacency matrix before the GNN layers. One common example is the symmetric normalization which is used in GCN [37] and subsequent
15

---

works. Despite their wide use, especially on node-level tasks, these normalizations may fail to capture structural information and lead less expressive architectures. For instance, a common practice of normalizing the adjacency matrix by dividing its rows by the sum of their entries is equivalent to employing mean aggregator over the neighbors, which has been shown to fail to distinguish certain non-isomorphic nodes [63]. For this reason, in this work, we consider only normalization layers applied to node features after every GNN layer.
AdaIN and StyleGANs. Adaptive instance normalization (AdaIN) [33, 19, 26] was originally proposed for real-time arbitrary style transfer. Given a content input and style input, AdaIN adjusts the mean and variance of the content input to match those of the style input. This allows for the transfer of stylistic features from the style input the content input in a flexible and efficient manner. Motivated by style-transfer literature, Karras et al. [36] introduced StyleGANs as a variant of GANs [27] which differs in the generator architecture. More precisely, the generator StyleGANs starts from a learned constant input and adjusts the "style" of the image at each convolution layer based on the latent code through the usage of AdaIN. Similarly to StyleGANs, we adjust node features at every layer through the usage of noise, i.e. random node features, akin to the role played by the latent code StyleGANs.
Random Node Features (RNF) in GNNs. Random input features were used in the context of GNNs
improve the expressive power of Message Passing Neural Networks (MPNNs) [44, 51, 1. 56, 17]. Importantly, MPNNs augmented with random node features have been shown to be universal (with high probability) in Puny al. [51], Abboud al. [1]. result we naturally inherit when GRANOLA defaults to simply utilizing random node features. Notably, despite the universality results, GNNs augmented with RNF do not consistently improve performance on real-world datasets [22]. We show instead that GRANOLA consistently leads to improved performances.
B Comparison of Different Normalizations
In this section we present the different normalization techniques that have been specifically proposed for graph data and highlight their connection to standard normalization schemes (i.c., BatchNorm, InstanceNorm, LayerNorm-noww LayerNorm-grajj whenever this is present.
PairNorm. PairNorm [72] first centers node features by subtracting the mean computed per channel across all the nodes in the graph, similarly to InstanceNorm. Then, it scales the centered vector by dividing it by the square root of the mean (computed across nodes) of the norm of each node feature vector, where the norm is computed over the channel dimension. That is, the center operation has equation:
center (1)) b,n.c
b,,,e Hb,n.e.
where Hb,n.e is in InstanceNorm (Equation (5)), while the scale operation can be written as
j ee)merr
(O p.n.ci
H0000)
b
(12)
center
b.a
with a hyperparameter and the norm
center
(e) 1 b,n.c
MeanSubtraattonNNrr.. MeanSSbrractionNorm [64] is similar to InstanceNorm, but it simply shifts its input without dividing it by the standard deviation (and without afline parameters). That is (0)
H (()))))
(e) -b..cc -b,,.e
(13)
and Mb,n, as Equation (5).
MessageNorm. MessageNorm [39] couples normalization with the GNN layer. In particular, it defines the update rule of (() as follows,
| (e-1) 1-11 112
n2.n = ④ MLP hb
(t-1) + s|ln
(e-))
(14)
(f-1)
|mmb,r
16

---

where R hyperparameter and (6-1) can be defined as
b.n is the message of node E [N] in graph & [B], which
(8) ( D
(0)
(0) (E) 5 (Im
with p())g())))))))))))))))) learnable functions such as MLPs and N neighbors of node v graph b.
DiffGroupNorm. DifiGrrupNNorm [74] first softly clusters nodes and the normalizes nodes within the same cluster by means of BatchNorm. That is, for each graph b E [B] in the batch, it computes a soft cluster assignment as
5 softmax H. w())
where W( E RCXD with E the number of clusters, and therefore S denote by ((0) E BXNxDD the matrix containing the cluster assignments for all graphs in the batch, where the b-th BatchNorm applied to each cluster (where the feature is weighted by the assignment value), and adds the result the input embedding, that is
RNXD, Let us
of ( is 5 DiffGroupNNrm computes linear combination of the output of
(h b.n.e H HO n.n.c + + BATCHNORM(
(())
10 (o H
(15)
where BATCHNNRRM leverages Equation (4), and E R hyperparameter. Notably, the term bb.n. in Equation (15) is similar to skip connection, with the difference lying in the fact that skip connections usually add the output of the previous layer ( after the norm instead of the output of the current layer before the norm.
7,())
NodeNorm. NodeNorm [75] similar to LayerNorm-node but simply divides input by a root of its standard deviation, without shifting it and without affine parameters:
(2)
B.n.c
NORM 10.0
(16)
b,n,c
with as in Equation (6) and p N hyperparameter.
GraphNorm. GraphNorm [11] builds upon InstanceNorm by adding an additional learnable parameter (4) RC which the same for all nodes and graphs. The equation can written as
(0) NORM on (0) 70 Aon - ac Pb,a.
+ +g000)
(17)
and Mbmnee Ob,n.e as Equation (5).
GraphSizeNorm. GraphSizeNorm [21] normalizes the node features by dividing them by the graph size, before applying a standard BatchNorm:
(()
( H9,0)
D.n.C
(18)
VN
Nnimy UnityNorm [13] consists weighted combination of four normalization techniques, where the weights λ1 X2, Ag. A4 E IR are learnable, That is
mai (0
(0))) = LAYERNORMNNOD (8)
(0,
b.n.a
AgADIACENCYNORM H()
(19)
AgINSTANCENORM(119 (0)
HO.
ABBTCHNORM :10.0)
17

---

where LAYERNORM-NODE, INSTANCENORM and BATCHNORM leverage respectively Equa- tions (4) to (6). ADJACENCYNORM computes the statisties for each node across all features of all its neighbors, that is
C EEO
Pb,
INNC
Σ KEND c=1
100 b.
WHC
E GEAT c=1
buue - Mb,n,)
SuperNorm. SuperNorm [12] embeds subgraph-specifie factors into BatchNorm. First, for each node n in graph it extracts the subgraph induced by its neighbors, denoted as St,n. Then, it computes the called cubgraph-specile factors for each subgraph, which are the output of hash function over the number of nodes in the subgraph and its eigenvalues. That is the subgraph-specific factor of n is
n(S)..)) = Hash D. (Eigs....)
where Vs.... denotes the number of nodes in St, and Eigs... its eigenvalues, with ø and & injective functions.
Suberaph-specifie factors for all subgraphs in graph b are collected into a vector M e g-
M (S..)):):
which is used to obtain two additional vectors M,,, M, E RRNx1 defined as
E(Sb,1)
E(S..2)
((So.N) M E(Sb,n)
M
Ea E(Sb.n)
Σn ((Sb,n)
N
M RC = M @ M
where O denotes the element-wiss product. Then, the normalization computes the segment average of H for each graph b, denoted as H segment
E NxC where a row n is defined as
N
h b,n.
segmen
(0)
b,n
1=
Then, the input H. is calibrated by injecting the subgraph-specifte factors as well the graph statistics obtained via H segmentt That is,
H calibratioo H + (()) H segment
3 (M RC 1C)
where 1c [1]cx1 and O = (OT with 1N E [1)Nx1 and (( E gCx1 is learnable parameter. After injecting subgraph-specific factors, the normalization layer performs BatchNorm on the calibration features, that is
(0,cs
BATCHNORM (1 calibbaatt H (O)aaaiiiaa)) b,n.e
Finally, phoggrap-sppecffe factors embedded after BatchNorm, by computing
H ( & H 00 c (1) + 1/2 IN
(20)
where (0,, E CR are learnable affine parameters, and P/D0 E IR NxC is a matrix where each entry is obtained as
(()) (MRE) wRRE. )
(2)
b,n.c
(8) where RRE
ICC is learnable parameter and MRE RRNNC is obtained
MRC
MRE
C-
MRC
Equation (20) represents the output of SuperNorm, followed by activation function é.
18

---

C Additional Motivating Examples
In the following we elaborate on the failure cases of existing normalization layers. Throughout this section, we will assume that all GNN layers on the maximally expressive MPNN layers presented in Morris et al. [41], which have been shown to be expressive as the 1-WL test. In particular Equation (1) can be rewritten as follows,
pesssage-passingg layers, and, in particular, we focus
H (1-1) w( (t-1) + Aa
(21)
Example C.1 (BatchNorm reduces GNN capabilities to compute node degrees (Figure 2)). Consider the following task: Given a graph G, for each node predict its degree. Assume that our batch contains B graphs, and, for simplicity, assume that they all have the same number of nodes N. Assuming such graphs do not have initial node features, follow standard practice [63] and initialize H for
each graph b [B] as a vector of ones, i.e., H = 1 E RN The output of the first GNN layer is already the degree of each node, or a function thereof:
H (1) = & (NORM ( (0) + A (0) :)):)))
(22)
where w E RIIC _ RICC are learnable weight matrices, and C' E N is the hidden feature dimensionality, Note that since the input is one dimensional, all output channels behave identically, We consider the case where C C= 1. Importantly, in our example, we have that H (0) 1 is the same
for all nodes in all graphs in the batch, because H and w are the same for all nodes and graphs. Therefore, the term H. (0) w(O) acts as a bias term in Equation (22). Thus, for each node, the output of the first GNN layer is simply linear function of the node degree, which is computed by the term
A (0) in Equation (22). Now, consider the normalization layer NORM applied to the output of this function, and assume for now that there are no affine parameters. First, the BatchNorm normalization layer subtracts the mean computed across all nodes in all graphs, as shown Equation (4). For all nodes having an output smaller than the mean, this subtraction returns a negative number, which is zeroed out by the application of the ReLU which follows the normalization. Therefore, assuming no further layers, for these nodes the prediction can only be 0 regardless of the actual degree, and therefore is incorrect. Figure 2, we provide a concrete example where this limitation occurs.
Remark C.2 (Deeper networks are also limited). It is important to note that even when the number of layers is greater than one, and assuming C 1 in all layers, the problem persists, because the analysis can be applied to every subsequent layer's 's output by simply noticing that subtracting the mean will always zero out features less than the mean.
Remark C.3 (BN with Affine transformation is also limited). We highlight that the inclusion of learnable affine parameters in BatchNorm, while potentially mitigating the problem during training
by means of a large affine parameter (²()) that shifts the negative outputs before the ReLU, does not offer a definitive solution. Indeed, it is always possible to construct test scenario where one graph has nodes with degrees significantly smaller than those seen while training, for which the learned shift a( (1) is not sufficiently large to make the output of the normalization layer positive.
It is important to mention that the aforementioned example potentially serves failure case for other methods that are based on removing the mean M,,,, as calculated by BatchNorm Equation (4). For instance, GraphSizeNorm [21] also suffers from the same issue, this normalization technique scales the node features by the number of nodes before applying BatchNorm. Furthermore, Example C.1 can be adjusted to induce a failure case for the normalization operation (excluding the skip link) in DiffGroupNorm [74], which is also based on BatchNorm. This can be achieved by ensuring that subset of nodes has degree less than the average within all the clusters to which it is (softly) assigned.
Example C. can be easily adapted to represent failure case for InstanceNorm. The adaptation involves treating the entire batch as a single graph, which can be further refined to avoid having disconnected components by adding a small number of edges connecting them.
*This assumption is included only simplify the notation, but can be removed without affecting the results.
19

---

Example C.4 (InstanceNorm reduces GNN capabilities to compute node degree (Figure 2 considering all graphs as disconnected components in a single graph)). Consider the following task: Given graph G, for each node predict its degree. Assuming the graph does not have initial node features, we follow standard practice [63] and initialize H 1 E RN*1, The output of the first GNN layer is already the degree of each node, or function thereof. Now, consider the normalization layer NORM applied the output of this function. First, the InstanceNorm normalization layer subtracts the mean computed across all nodes within each graph in the batch, as shown in Equation (5). For all nodes having an output smaller than the mean within their graph, this subtraction returns a negative number, which is zeroed out by the application of the ReLU activation function, applied following the normalization. Therefore, assuming no further layers, for these nodes the prediction can only regardless of the actual degree, and therefore is incorrect. Similarly to BatchNorm, the inclusion of learnable affine parameters as well as the stacking of additional single-channel layers is not sufficient to solve the problem.
The aforementioned limitation extends directly to other graph-designed normaliza- tions based on InstanceNorm, such as PairNorm and GraphNorm as they also shifts the input in the same way, based on the mean Pbm,. as defined in Equation (5).
Example C.5 (LayerNorm-node reduces GNN capabilities to compute node degree (Figure 5)). Consider the following task: Given graph G, for each node predict its degree. Consider graph G consisting of path of 3 nodes. Assum- ing the graph does not have initial node features, initialize (
R-Nx1 with b as we only have one graph. We will assume that w 0 (Equation (21)). Therefore, the output of the first GNN layer can be written as:
(a) Node degrees, computed by one message-passing layer.
20
H 0 = [NORM (A,H! (())) ()) (23)
which, for each node, is vector having each entry the degree of the node multiplied by learnable weight entry. Compare now one of the node having degree d E N, denoted as with the node having degree 2d, denoted as u. Clearly, we have that the vector of node features in u is equal to two times the vector of node features in Therefore, by subtracting the mean computed across the channel dimension, as per Equation (6), we obtain
(b) After removing the computed the feature dimension, all nodes are mapped to the same value despite having different degrees.
Figure 5: A graph, where subtracting the mean of the node features computed on the feature dimen- sion, in LayerNorm-node and related methods, results in the loss of capacity to compute node de- grees.
h = fbb.cc
for all e E [C]. This implies that it is not possi- ble then distinguish the degree of these two nodes.
Remark C.6 (Deeper networks are also limited). It is important to note that even when the number of
layers is greater than one, assuming wi(-1) in all GNN layers (Equation (21)), the problem persists. Indeed, in the next layer, both nodes v and u will aggregate neighbors having identical features. Therefore the vector of node features in will still be equal to times the vector of node features in u, a difference that is removed by the subtraction of the mean computed per node.
D Variants of GRANOLA
In the main paper, we have additionally considered GRANOLA-NO-RNE variant of GRANOLA that does not sample RNF and instead uses only (r) (Equation (11)) In the following, we present an additional variant.
AAssuming the learned shift parameter in GraphNorm is not all zeros.
20

---

GRANOLA-MS. Equation (10) can be specialized to the case where the affine parameters correspond to the mean and standard deviation computed per node across the feature dimension of 2 (8) That is,
1 C
(8) D,n.o
3,00 D,n.c
1 C
Σ
(2) bbm.c Tbmn...
(2) )
(24)
We refer to this variant of Equation (10) which uses the pre-defined mean and standard deviation
functions in Equation (24) for f( 12 as GRANOLA-MS, where MS stands indeed for mean and standard deviation. The idea behind GRANOLA-MS is explicitly align the node-wise mean and variance of H to match those of z,¹) Note that, while GRANOLA-MS follows a predefined realization of fi and f2 by using the mean and standard deviation, it is still a learnable normalization
technique, as z is learned in Equation (8). In Appendix H.8, we provide empirical comparisons with this specialized case.
E Proofs
Theorem E.1 (Existing normalization techniques limit MPNNs' expressivity), Let f be a stacking of GIN layers with non-linear activations followed by sum pooling. Let frome be the architecture obtained by adding InstanceNorm or BatchNorm without affine parameters. Then fromm is strictly less expressive than f.
Proof. All non- non-isomorphic graphs that can be distinguished by fror= can clearly be distinguished by f as the normalization only shifts and scale its input. To show that frorm is strictly less expressive than f. consider two CSL graphs with different numbers of nodes. These are distinguishable by f. However, applying InstanceNorm to the output of GIN results in a zero matrix, as shown in Cai et al. [11, Proposition J. Similarly, if the batch consists of these two graphs, applying BatchNorm results in zero matrix. Since the output of the normalization is zero matrix, they are indistinguishable by frorm, concluding our proof.
Proposition E.2 (MPNN with GRANOLA can implement MPNN with RNF). Let frore be stacking of MPNN layers interleaved with GRANOLA normalization layers (Equation (10)), followed by activation functions. There exists choice of hyperparameters and weights such that frorm defaults to MPNN + RNF [1].
Proof. We only need to show a choice of hyperparameters and weights that makes an MPNN + GRANOLA default to an MPNN RNF, which is the model obtained by performing message passing on the input graph where the initial node features are concatenated to RNF.
Since RNF in an MPNN + GRANOLA are introduced in the GRANOLA layer, we choose the first MPNN layer, which precedes any normalization (Equation (1)), to simply repeat its inputs using
additional channels. In the case of GraphConv layers, this is easily obtained by ((()) (11)
and w
(0) O. with I {0, 1]CxC_ With these choices, Hr()) (1) in Equation (1) becomes H. (1)
H H X, @ X., Notably, this concatenation is only introduced to make the dimension of H match the dimension of the concatenation of the initial node features with RNF having the same dimension.
Consider the first GRANOLA layer, 1. It is sufficient to set the activation functions inside GN)
NORM to be the identity function and to properly set the weights of GNN(1)
NORM (Equation (8)) and cR
f (l (Equation (9)) such that the normalization layer returns H. (0) (1) with R e NxK
(l))
and K chosen such that K = C. For example, if G) XORM is composed by a single GraphCony layer [41] (with an identity activation function), we have
z (1)
(H)
(1)
R (1)
W (1) + (FT
(1)
W. (1)
H
00)
R (1) W (1) + A H + R (1) W
NORM (1)
21

---

then for GN is sufficient to choose W () 0. woRM,,(1)
(10)
0 where I e
{0, 1)xx0 is the identity matrix. For fl") 'J2 its is sufficient to set f(") always return vector, and ( to be the identity function. With these choices, Equation (2) becomes
H = H b + DR - (x e
which represents the input of the next GNN layer, and matches the input of an MPNN + RNF, Therefore, we are only left to show that subsequent applications of GRANOLA layers behave as the identity function, since the GNN layers will instead behave as those in the MPNN RNF.
After the first GRANOLA layer, l > 1, it is sufficient to set GNN NORM (Equation (8)) and , p(()
(Equation (9)) to return its input (+ E NR (while discarding R (2) (R.N Assuming single
layer in it (with an identity activation function), this can be accomplished by setting 2 W.NORM.(0)
and W>NOMM((3) (.). ( f(() to always return zero vector, and f(()) be the identity function. With these choices, Equation (10) becomes
(2) NO byn.ec H0 (E) b.n.c
Therefore, these two steps imply that MPNN with GRANOLA implements an MPNN with RNF. A
Corollary E.3 (MPNN GRANOLA is universal with high probability). Let UN be compact of graphs with N E N nodes and a continuous
graph function defined over SNx- Let frome be a stacking of MPNN layers interleaved with GRANOLA normalization layers (Equation (10)) followed by activation functions. Then, if random node features inside GRANOLA are sampled from continuous bounded distribution with zero mean and finite variance, for all c, > 0, there exist a choice of hyperparameters and weights such that, VG = (A, X) E Ω
P(g((A,)) X) /norm (A, x) <e) 2 1 5
(25)
where (nora(A, X) is the output for the considered choice of hyperparameters and weights.
Proof. The proof follows by showing the choice of hyperparameters and weights which makes an MPNN augmented with GRANOLA satisfy the assumptions of Puny et al. [51, Proposition 1]. In all
our GRANOLA layers, R E RRNN is drawn from continuous and bounded distribution for any graph b in a batch of B graphs. Therefore, we only need to show that the overall architecture can default to an MPNN augmented with these RNF. This follows from Proposition E.2.
Proposition 4.1 (RNF are necessary in GRANOLA for increased expressive power). Assume our input domain consists of graphs of a specific size, For every MPNN with GRANOLA-NO-RNE (Equation (11)) there exists a standard MPNN with the same expressive power.
Proof. The proof follows by showing that an MPNN with GRANOLA-NO-RNE can be implemented by standard MPNN (without any normalization), which therefore represents upper-bound of its expressive power.
We assume that all the MPNN layers are maximally expressive MPNNs layers of the form of GraphConv [41], and that all activation functions inside GRANOLA-NO-RNE are ReLU activation functions. Since the convolution layers are the same in both from and f, we only left to show that an MPNN (without normalization, with ReLU activations) can implement a layer of GRANOLA- NO-RNF. Recall that single GRANOLA layer can be written as
Bon Mb,a.
(0) b.n.e HO (1
(=(9)c
(=(.))
(26)
Ob,.cc
and, since we not considering RNF, (000) is obtained with Equation (11), recalling that G is also composed by MPNN layers interleaved by ReLU activation functions per our assumption. We denote the number of layers of this GNN by ( We next show how to obtain Equation (26) using multiple layers of an MPNN which takes as input ((),, We will denote intermediate layers of this MPNN as (9) t > 1.
(
NORM
22

---

First Step, compute T00 The first layers of this MPNN are used to obtain z00) given H effectively mimicking GNN NORM. Since we will later need also H we will use the last feature dimensions in every layer representation simply copy it in every subsequent layer. Importantly, however, simply copying H in the last dimensions using an identity weight matrix may not be sufficient, as the application of ReLU non-linearity would clip negative entries to 0. Therefore, we copy both H()) and -H -
in the last dimensions, and at the end recover H. as H.!
((H)) 66-H, " with @ the ReLU activation.
Fort = 1, the MPNN layer is simply responsible of replicating its input H3 so that we can later use the first C channels to obtain z and the last later recover ( Therefore,
H (1) = o(H 10 w + , w
with w = (II -I) and W = 0. with I E {0. 1 the identity matrix, and e is the identity activation function. This means that H. H 2 H H For t and I I we need to mimic GN
NORM from Equation (11) on the first C dimensions. This is achievable by (
+ A )
with (
W Syroom
00 and w W NONOR, (1)
00
where (ORM.() WAORM.(C)) are
10
o
exactly the same the corresponding weights of GNN á is the ReLU activation. Therefore, after LOORN + 1 layers, we have
Hg L
( +1) = - @ )eo(
(66-- H
010) We can then use an additional MPNN layer to recover ! by setting w = ( [0_1) w = 0. and obtain
H NORN +2) = -z/ + !
Finally, we rely on the ability of MI.s to memorize a finite number of input-output pairs (see Yun et al. [68] and Yehudai et al. [65, Lemma B.2l) to implement Equation (26) given its input. This is achieved by making the three subsequent layers of the MPNN behave as a 3-layer MI. (with ReLU
activations) by simply zeroing out W(() In this way, we have obtained Equation (26) through MPNN layers only.
F Experimental Details
We implemented GRANOLA using Pytorch [50] (BSD-style license) and Pytorch-Geometrie [24] (MIT license). We ran our experiments on NVIDIA RTX3090 and RTX4090 GPUs, both having 24GB of memory. We performed hyperparameter tuning using the Weight and Biases framework [6]. To sample the random node features, we followed Abboud et al. [1] and used a standard Gaussian with mean 0 and variance 1, sampling random node features for each forward pass. For each node, we sample independently. a number of random features equal to the channel dimension of h 6, that is K is equal to in Equation (8). Recall that when augmenting a GNN architecture with GRANOLA. we have two types of networks: (i) the main downstream network, and (ii) the normalization network returning zz5 (e) (see Equation (8)) In both networks, and throughout all datasets that do not contain edge features (e.g., in TUDatasets), we employ GIN layers [63] to perform message passing. In case edge features are available, such as in ZINC. we use the GINE variant of GIN, as prescribed in Dwivedi et al. [21]. For brevity, we refer to both as GIN throughout the paper. Our MLPs are composed of two linear layers with ReLU oonelinaass Our normalization network is kept small and comprises a number of layers tuned in (1, 3} and an embedding dimension that is the same as its input (0) Each experiment is repeated for 5 different seeds, and we report the average and standard deviation result. Details of hyperparameter grid for each dataset can be found in the following subsections.
23

---

F1 ZINC-12K
We consider the dataset splits proposed in Dwivedi et al. [21], and use the Mean Absolute Error (MAE) both as loss and evaluation metric. For all models, used batch size tuned in {32, 64, 128). To optimize the model we use the Adam optimizer with initial learning rate of 0.001, which is decayed by 0.5 every 300 epochs. The maximum number of epochs is set 500. The test metric is computed at the best validation epoch. The downstream network is composed of a number of layers in (4, 6), with embedding dimension tuned in (32, 64).
F.2 OGB datasets
We consider the scaffold splits proposed in Hu al. [31], and for each dataset we used the loss and evaluation metric prescribed therein. In all experiments, we used the Adam optimizer with initial learning rate of 0.001. We tune the batch size in {64, 128. We employ a learning rate scheduler that that follows the procedure prescribed in Bevilacqua et al. [4]. We also consider dropout in between layers with probabilities (0, 0.5). The downstream network has the number of layers in {4, 6} with embedding dimensions in (32, 64, 128]. The maximum number of epochs is set to 500 for all models. The test metric is computed at the best validation epoch.
F33 TUDatasets
For all the experiments with datasets from the TUDatasets repository, we followed the evaluation procedure proposed in Xu et al. [63], consisting of 10-fold cross validation and metric at the best averaged validation accuracy across the folds. The downstream network is composed of a number of layers tuned in {4, 6} layers with embedding dimension in {32, 64). We use the Adam optimizer with learning rate tuned in {0.01, 0.001 We consider batch size in {32, 64, 128), and trained for 500 epochs.
G Complexity and Runtimes
Complexity. As described in Section 3, and specifically in Equation (10), our GRANOLA takes random node feature and hidden learned node features, and propagates them using a GNN backbone denoted by GNNNoRM to compute intermediate (expressive) features, which are then used to calculate the normalization statistics, as shown Equation (9). The calculation can be implemented either by considering their mean and standard deviation, as in GRANOLA-MS, or more generally by employing an MLP in GRANOLA, as described in Equation (24) and Equation (9), respectively. In
our experiments, G NORM in GRANOLA is also an MPNN, similar to the downstream backbone model. Therefore, including our GRANOLA layers does not change the asymptotic computational complexity of the architecture, which remains within the computational complexity of MPNNs (e.g., Morris et al. [41], Xu et al. [63]). Specifically, each MPNN layer is linear the number of nodes |V| and edges EE' Since a single GRANOLA layer is composed by L MPNN layers, assuming it the same for all E, has a time complexity of O ([V]+ |El)). Every downstream MPNN layer in our framework uses a GRANOLA normalization layer, and therefore, assuming L downstream MPNN layers, the overall complexity of an MPNN augmented with GRANOLA O ((L INORR)) ([VI + EE)). compared to the complexity of an MPNN without GRANOLA which amounts to (L- ([V) + [E])). practice, INNRR
hyperparameter between to 3 and can
therefore be considered constant.
Runtimes. While the asymptotic complexity remains linear with respect to the number of nodes and edges in the graph, as in standard MPNNs, our GRANOLA requires some additional computations due to the hidden layers in the normalization mechanism. To measure the impact of these additional layers, we measure the required training and inference times of GRANOLA, whose results are reported in Table 4. Specifically, we report the average time per batch measured on Nvidia RTX-2080 GPU. For fair comparison, in all methods, we use the same number of layers, batch size and number of channels. Our results indicate that while GRANOLA requires additional computational time, still a fraction of the cost of more complex methods like Subgraph GNNs (5.2x faster than efficient expressive models like Subgraph GNNs), while yielding favorable downstream performance. These results indicate that GRANOLA offers strong tradeoff between performance and cost.
24

---

Table 4: Average batch runtimes Nvidia RTX-2080 GPU of GRANOLA and other methods, with 8 layers, batch size of 128, and 128 channels on the OGBG-MOLHIV DATASET. For reference, we also include the measured metric, which is ROC-AUC.
Method
MOLHIV Inference (ms)
Training Time (ms)
ROC-AUCT
MPNN
GIN BatchNorn [63]
4.12
3.23
75.58=1.40
Subgraph GNNs
DSS-GNT (EGO+)
69.58
49.88
76.78 1.66
Natural Baselines
GIN BatchNorm RNF-PE [56]
5.16
4.54
75.98 1.63
RNF-NORM
5.59
77.61
GIN GRANOLA NO-RNF
10.82
9.21
77.09 1.49
GIN GRANOLA-MS
11.15
9.37
78.84
GIN GRANOLA
11.24
9.55
78.98:1..0 1.17
Table GRANOLA coupled with additional backbones. Incorporating GRANOLA enhances perfor- mance across all backbones.
Method
ZINC MAE
MOLHIV ROC-AUC
GCN
GCN GRANOLA
0.233=20.005
77.54=
GAT
0.004
76.0.10.80
CAT GRANOLA
0.254=200009
17.39:1.00
GPS
0.070=0.004
78.80=
GPS + GRANOLA
0.062:20.006
1.22
H Additional Experimental Results
H.1 GRANOLA Coupled with Additional Backbones
In this subsection, we evaluate the performance of GRANOLA when coupled with additional back- bones beyond GIN and GSN presented in Section Specifically, we evaluate its integration with GCN [37]. GAT [60], and GPS [53], using GRANOLA as the normalization layer. Table shows that adding GRANOLA results in improved performance regardless of the architecture. These results underscore the versatility of GRANOLA, which can be coupled with any GNN layer and improve its performance.
H.2
Using other Expressive Mechanisms in GRANOLA
As explained in Sections 3.1 and 4, in this paper, we chose to use RNF within GRANOLA. Incor- porating RNF into our GRANOLA allows it fully adapt to the input graph, providing different affine parameters for non-isomorphic nodes. Full adaptivity is lost when removing RNF and using a standard MPNN as GNNNORM. as GRANOLA-NO-RNE. This is because GRANOLA-NO-RNE is not more expressive than MPNN (Proposition 4.1), and thus, there exist non-isomorphic nodes that will get the same representation (and the same affine parameters). However, any other most expressive architecture used GNNNORM would achieve the same full adaptivity, and our choice of MPNN + RNF was motivated by its linear complexity.
To make this point clearer. in this subsection, we analyze the performance of a variant of GRANOLA that uses Subgraph GNN, namely DS-GNN [4], as the GNNNORM. instead of an MPNN + RNF. Table 6 shows that GRANOLA-Subee Suug----uuarapGNNN behaves similarly to GRANOLA. However, employing a SubgraphGNN as the GNNNORM results in additional complexity coming from the Subgraph GNN itself (which is quadratic rather than linear). Thus, while enhanced expressivity in GNNNORM does not require employing RNF specifically, using an MPNN RNF provides the advantage of linear complexity.
We denote this variant as SAANOLL-SuubgaphhHH
25

---

outperforms BatchNorm, further highlighting Table 6: Using RNF Subgraph GNN for Expressiveness in GRANOLA. While alternative expressive GNNs for GNNNORM result in comparable performance, the MPNN + RNF approach offers the benefit of retaining linear complexity.
Method
ZINC
MOLITV ROC-AUC
GuANoLLt-SugrraaGGNN
0.1186:000088
78.62=1.31
GIN GRANOLA (Using RNF)
0.1003::0.006
78198
Table 7: A comparison where we further modified BatchNorm to be graph adaptive using our GRANOLA design. GRANOLA- Nor surpasses BatchNorm, showcasing the importance of graph adaptivity across different normalization blueprints.
Method
ZINC-12K 4
MOLHIV f
GIN BatchNorm
0.1630 + 0.004
75.58 + 1.40
GIN LayerNomm-node
0.1649 + 0.009
75.24 + 1.71
GIN CLAANOLA-Batchoonn
0.1397 0.007
77.93 + 1.22
GIN GRANOLA (LayerNorm-node)
0.1203 0.006
78.98 = 1.17
H.3 GRANOLA building from BatchNorm
As discussed in Section 3, in Equation (10), Ab,a.e and db...e are the mean and std of H computed per node across the feature dimension, exactly in LayerNorm-nodee This choice was dictated by the fact that we found LayerNorm-node to offer consistent performance across different benchmarks. However, also possible to compute Pi.n..c and Tb.n.c across different dimensions, resulting in a variant of GRANOL. that builds on top of other normalization layers rather than LayerNorm-node. In Table we study the effectiveness of the variant of GRANOLA that builds on top of BatchNorm. As can be seen from the table, GRANOLA-BatchNon the role of graph adaptivity in normalizations.
H.4 Shared weights vs. Per Layer GNN(E)
(E) NORM
In our experiments in Section 5, the additional normalization GNN layer, G had unique parameters per layer, evidenced by the superseript É. In Table 8, we show that by using the same GNN for all f, that is by sharing the weights across all layers, which overall requires less param- eters, our GRANOLA continues to offer competitive results, further highlighting its competitiveness also cases where parameter budget low.
H.5
The role of GRANOLA Normalization
To better understand the contribution of GRANOLA, we provide results where we set the normal- ization term GRANOLA zero, leaving only the bias term be learned. That achieved by setting 7b. in Equation (10), By following this approach, we isolate the contribution of the normalization itself from the bias in the normalization process. Our results, shown Table 9, indicate that the normalization term in GRANOLA significant, and cannot be replaced by simple bias.
H.6 RNF PE Ablation Study
GRANOLA benefits from (i) enhanced expressiveness, and (ii) graph adaptivity. Property (i) is obtained by augmenting important to ensure that the contribution GRANOLA does not stem solely from the use RNF, but rather the overall approach and design of our method.
normalization scheme with RNF, as shown in Figure 3. Therefore, is
To this end, addition to the natural baseline of RNF-PE, which uses RNF as positional encoding combined with GIN + BatchNorm (as in [56]). we now provide results of RNF-PE when combined with GIN and different normalization layers. Specifically, we consider Identity (no normalization) and LayerNorm (both graph and node variants). The results are provided in Table 10, together with
26

---

Table 8: Comparison of GRANOLA with its variant sharing GNN NORM across layers (instead of having a different one for each layer), and BatchNorm and LayerNorm-node for reference. While using a GNN
obtained by
NORM per GNN layer leads to better results, sharing for all also offers significant improvements over baseline methods.
Method
ZINC-12K
MOLHIV 1
GIN BatchNorm
0.1630 1 0.004
75.58
1.40
GIN + LayerNorm-non
0.1649 + 0.009
75.24
1.71
GIN GRANOLA- GRANOLA-SHAREDGNT SHAREDGNN NORM
0.1293 + 0.009
78.47
1.20
GIN + GRANOLA
0.1203 + 0.006
78.98 + 1.17
(1) Table 9: Comparison of GRANOLA with its variant where
7b,
0 in Equation (10) shows the
importance of the normalization in GRANOLA.
Method
ZINC- 12K |
MOLHIV 1
GIN GRANOLA-
b.n.c -only
0. 10.0081
74.11111.39
GIN GRANOLA
0. 10000000.006
78.9811.17
the results of our GRANOLA, for reference and convenience of comparison. The results suggest that while the different variants of RNF-PE do not show significant improvement over the baseline of GIN + BatchNorm, our GRANOLA does. These results are further evidence that while RNF are theoretically powerful, they may not be significant in practice, as shown in Eliasof et al. [22]. Instead, it is important to incorporate them in a thoughtful manner, for example, to obtain graph adaptivity within the normalization layer, as our GRANOLA.
H.7 Normalization GNN depth ablation study
As discussed in Section 3, our GRANOLA utilizes GNN to learn graph-adaptive normalization shift and scaling parameters, and we denote this GNN by GNN Combined with the RNF as part of the imput (N NORM> we able to obtain both enhanced expressiveness (from RNF) and graph-adaptivity (by GNN NORM). ). It is therefore interesting to study the effect of the number of layers in GNN(() NORM on the downstream performance. Specifically, in the case where GN has 0 layers, the experiment defaults to a model very similar the RNF-NORM baseline (with the difference that
in RNF-NORM we have Z losing graph adaptivity. In Table 11, we provide results
(f) while in this case we have Z H + R thereby
varying number of layers, from
Our results suggest that there is significant importance in terms of performance to having graph adaptivity in the normalization technique, as offered by our GRANOLA.
H.8 Comparison with additional baselines
In the main paper, in Section we focused on providing a comprehensive comparison with directly comparable methods, i.c., standard normalization methods, graph normalization methods. as well as our own set of natural baselines. In this section, we provide additional comparisons with other expressive approaches, such positional encoding methods and Subgraph GNNs. Our additional comparisons on 12K, OGB, and TUDatasets are provided in Table 12, Table 13, and Table 14, respectively.
is important note, that while some of these methods achieve better performance than our GR CNOLA,,, they are not within the same complexity class as GRANOLA, and specifically, they are not linear with respect the number of nodes and edges in the graph, discussed in Appendix G. For example, RFP- RFP-QR-L. L, Á. _learn_ DDSS [22], which also utilizes the expressive power of RNE, QR-L, achieves an MAE of 0. 106 on ZINC- 12K, while our GRANOLA achieves 0.1303. However, the former is of quadratic complexity with respect the number of nodes, while GRANOLA linear, as standard MPNNs. On the other hand, the linear and thus directly comparable RFP - l2 L, A achieves higher (worse) MAE of 1368... Similarly, while there are Subgraph GNNs that can
27

---

Table 10: Ablation study of RNF-PE with GIN and various normalization methods.
Method
ZINC MAE
MOLHIV ROC-AUC
GIN BatchNorm [63]
0.1630+:0.04
75.58::
GIN BatchNorm RNF-PE [56]
0.1621
75.98 1.63
GIN LayerNorm-node- RNF-PE
0.1663=0.015
7..22441.58
GIN LayerNom-graph RNF-PE
0. 0.1624=0.0188
76.49:t: 644
GIN Identity + RNF-PE
0.2063=0.018
75.31=:2.04
GRANOLA
0.0203000000
78.98:b 1.17
Table 11: Ablation study of the depth (number of layers) of GNN NORM
Depth
ZINC (MAE J)
0.0013
0.121810.009
0.1203-0.000 0.006
0.120910.000
0.1224110008
MOLHIV (ROC-AUCC) t)
77.61 1.64
78.33411.44
78.98
78.86.1
1.33
outperform GRANOLA, these are at least quadratic the number of nodes. Therefore, we find that our GRANOLA offers practical yet powerful approach for utilizing RNF.
Additionally, observe that in cases, GRANOLA achieves similar better performance than other expressive and asymptotically more complex methods. For example, our results on TUDatsets in Table 14 show that GRANOLA offers better performance than DSS-GNN [4] all considered datasets, despite DSS being quadratic in the number of nodes.
28

---

Table 12: Additional comparisons of GRANOLA with various baselines on the ZINC- 12K graph dataset. All methods obey to the 500k parameter budget.
Method
ZINC
MPNNS
GCN [37]
0.001 0.133=20.011
PNA [15]
POSITIONAL ENCODING METHOSS
GIN + Laplacian PE [22]
1.0012
REP Eg L, Á (22)
0.000
RWPE (20)
0.007911.000
RFP-QR-L, A, glearn-DSS [22)
0.1106=0.012
DOMAIN-AWARE GNNS
GSN [10]
0.101 100010
[8]
0.079-0.006
HIGHER ORDER GNNS
PPGN [40]
0.07
PPGN++ (6) [52]
0.00110.001
GRAPH TRANSFORMERS
GPS [53]
0.070.10.004
GRAPHORMER [66]
0.122:10.006
GRAPHORMER GD [70]
0.001::0.009
SUBGRAPH GNNS
NGNN [71]
0.001
2S-GNN (EGO+)
0.0003
DSS-GNN (EGO+) [4]
0.097:10.006
GNN-AK [73]
0.001100.010
GNN-AK+ [73]
0.091 10.011
SUN (EGÔ+) [25]
0.084=00002
GNN-SSWL [69]
0.062
GNN SSWL+ [69]
0.000.10.005
DS-GNN (NM) [5]
0.0871000003
NATURAL BASELINES
GIN BatchNomn RNF-PE
0.1621=00014
GIN RNF-NORM
0.1562:10.013
STANDARD NORMALIZATION LAYERS
GIN BatchNomn [63]
1.300=000004
GIN InstanceNorm [58]
0.2984=0.017
GIN LayerNorm-nodee [3]
0.1649:10000M
GIN LayerNorm graph
0.0014
GIN Identity
0.2009
GRAPH NORMALIZATION LAYERS
GIN PaizNorm [72]
0.3519=0.008
GIN MeanSSbirtctionN [64]
0.003210.021
GIN DifIGroupNorm [74]
0.2705
NodeNomm [75]
0.2119
GIN GraphNorm [11]
0.3004
GIN GraphSizeNoon [21]
0.0016
GIN SuperNorm [12]
0.1574=0.018
GRANOLA-NO--E
0.1497=20.008
GIN GRANDLA MS
0.1233. 00.009
GRANDLA
0.000
29

---

Table 13:
Additional comparisons of GRANOLA natural baselines, standard and graph normaliza- tion layers, and subgraph GNNs, demonstrating the practical advantages of our approach. indicates the result was not reported the original paper.
Method J. Datasel
MOLESOL 4
MOLTOX21
MOLBACE
MOLHIV
MPNNS
GCN [37]
0.114 1.173=0.057
75.29=00.69 04.51
79.15 19.1511.44
76.06=0.977
GIN [63]
72.97=4.000
75.58 1.40
POSITIONAL ENCODING METHODS GIN + Laplacian PE [22]
77.88 1.82
REP- Sup-22-20 L, 122)
77.91 1.43
RWPE (20)
78.62 1.13
RFP-QR-L, A, -So (22)
80.58=1.222
EXPRESSIVE GNNS
GSN [10]
80.39 0.990
[8]
80.94-0.557
SUBGRAPH GNNS
RECONSTR. GNN [16]
1.026:0.033
75.15:::1.40
76.32
NGNN [71]
78. 34 1.86
(EGO+) [4]
76.39:
77 77.40-22.10
DSS-GNN (EGO+) [4]
77.95=20.40
78 1.66
GNN-AK+ [73]
79.61=1.119
SUN (GIN) (EGO+) [25]
80.03 0.55
GNN-SSWI.+ [69]
79.58-1..38
DS-GNN (NM)
0.847:100015
76.25:11.12
78.41:11.94
NATURAL BASELINES
GIN BetchNorm RNF-PE [56]
1.052:10.041
75.14:10.67
74.28:13.80
75 1.63
GIN + RNF-NORM
1.03910..000
75.12.10.92
77.96.14.36
77.61 1.64
STANDARD NORMALIZATION LAVERS
GIN BatchNorm [63]
1.173=0.057
74.91
72.97=44.00
75.58-114 1.40
GIN InstanceNorm [58]
1.099:0.0088
03.92:10.96
3.336
76.88 1.93
GIN + LayerNorm mode [3]
1.058 0.002
74.81 100.4
77.12.1.2 2.70
75.24 1.71
LayyerNorm--raphl
1.06120.043
75.03
76.49:14.07
GIN Identity
1.164:10.099
73.34.11.08
72.55
71.89 1.32
GRAPH NORMALIZATION LAYERS
GIN + PairNorm [72]
1.04420.031
73.27=+1005
75. 11:124
76. 18:2: 1.47
GIN McanSubbractoeNorm
1.062=0.045
74.96:10.22
76.36:24.47
76.37
GIN + DiIGGroupNerm [74]
1.06:10.063
74.76:00.66
75.96
74.37 1.68
NodeNorm [75]
73.27-10.83
75.50
GIN + GrapNNorm [11]
1.044-0.027
73.54=10.80
73.23
78 08 1.16
GIN + GraphSizzNorm [21]
1.121=0.051
74.07=00300
76.18-3.52
1.54
GIN SuperNorm [12]
1.037=0.044
75.08:1:0.98
75.12
7.76
76.23
77.09
GIN + GRANOLA-MS
0 000026
77.72-10.67
79. 18:42.2444
78.84-1 1.22
GRANOLA
0.960=0.020
77.19=00.85
79.92-22.56
78.98-1.11 1.17
30

---

Table 14: Additional Graph classification accuracy (%) 1 TUDatasets. indicates the result was not reported in the original paper.
Method // Datasst
MUTAG
PTC
PROTEINS
NCI1
NCT109
EXPRESSIVE GNNS
GSN [10]
92.24:.5
68.2:7.22
76.6=#5.0
83.5+:2000
82.712.11
CTN [8]
92.746.11
68.2:45.6
77.0=1433
83.6:1
84.0-1
SUBGRAPH GNNS
DROPEDGE [54]
91005377
64.5::2.6
73.5:245
82.0:22.6
82.2+:14
GRAPHCONV
[67]
65.4:17.1
83.4:12.
829112
DS DS-GNN (GIN) (EGO+) [4]
91.011.888
68.7-17.0
76.74444
82.0
80.3-0099
DSS-GNN (GIN) (EGO+) [4]
91.147.0
69.2:66.5
75.9-4.3
83.741.8
82.84122
GNN-AK+ [73]
91.377.0
67.8+8.88
77.1=5.7
85.0+2000
SUN (GIN) (BGO+) [25]
92.11:5.8
67.6:15.5
76.1
84.2:11.5
83,1
NATURAL. BASELINES
BatchNorm
[56]
74.1226
82.1
81341.1
GIN RNF-NORM
88.945.11
67.1
76.4448
81.8222
81.9
STANDARD
GIN + BatchNorm [63]
89.1...66
64.6.1..0
76.2.1288
82.7.117
82.2.1.6
InstanceNorm [58]
76.5439
GIN + LayerNorm-node [3]
90.1+5599
65,3+44.7
76,2=3.0
819915
82.0++2.1
GIN + Layernorm-graph [3]
90.4:6.1
66.4::6.5
76.1=499
82.0=116
815
GIN Identity
87.977.8
63.1
75.826633
81.342.11
1..6
NORMALIZATION
GIN + PairNorm [72]
87.8+7.1
67.1
76.7448
75.842.11
75.3+ 1
GIN + MenSSobractioaNorm [64]
90.1+:544
68.0=5599
76444466
79.2+1122
79.0+
GIN DiffGroupNorm
87.817666
67.41668
76.9-143
77.2426
77.1
GIN + NodeNorm [75]
88.3+7.00
65.1
74.5=4.6
81.21:4
1.04+
GraphNNoem
64.917755
77.4499
8144224
82.41177
GIN + GraphSSzeNNorm [21]
68.2.6..3
68.0.18.1
77.0.5.00
79.8.1.5
80.1
SuperNorm [12]
64.7139
76.1
83.021..
82.11177
GIN + GRANOLA-NO-RNIT
89.74:.44
658455.7
76.622.5
83.1::12
83.0
GRANOLA-MS
77.3:335
835118
GIN GRANOLA
92.2.14..6
69.9114.5
77.5:13.7
84.0.1..7
83.7.1666
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The contribution paragraph in the introduction (Section 1) explicitly describes the main contributions of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The conclusion section (Section 6) includes a separate paragraph discussing the limitations.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiiatinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
32

---

Answer: [Yes]
Justification: Section 4 presents our main theoretical results, and Appendix E contains the full set of assumptions well as the proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Section 3 fully describes our proposed method, and Appendix F contains all experimental details to reproduce our results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
33

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We offer comprehensive details regarding the implementation and evaluation of our method (Appendix F), our code is available.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
ieriiiissooPooli onPolicy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //tppp.cppppliiiiimmmm/tpppppppp wwtppccpppc///c/ct.ccccccccccclt wwtpc//gg///aeieeeceeoeeeess
wetbbbmmsssonPPee ssionnolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Appendix F contains all the details, including the hyperparameters and other experimental choices.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All results (Section and Appendix H.8) are accompanied by the corresponding standard deviation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
34

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Appendix describes the type of GPUs used in the experiments, Appendix G provides runtime comparison.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: httpps://eeet http:://eeuupppeeee
Answer: [Yes]
Justification:
The research conforms with the code of ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss potential societal impacts in Section 6.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
35

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We credited the owners of the assets and the licenses in Appendix F,
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
36

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/c datasttss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not introduce new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
37

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
38


Reviews:
[{"review_id": "wSPdNU4nEB", "reviewer": "Reviewer_vndL", "summary": "This paper proposes an adaptive normalization layer for GNNs. It first points out that the traditional normalization layer (BatchNorm, InstanceNorm)  are not specifically designed for graphs and thus may limit the expressive power of GNNs, and single normalization technique can not always be the best for all graphs. Therefore, it proposes the GRANOLA method which is a learnable normalization layer for GNNs, and justify its design with theories.", "questions": "Q1. The authors point out that the traditional normalization may not effectively capture the unique characteristics of graph-structured data. I am curious to see is there any empirical study or theoretical results to justify this point?\n\nQ2. Figure 2 provides an example to illustrate that BatchNorm may make the GNN less powerful. Is it possible to have something similar to visualize the performance of BatchNorm, InstanceNorm, LayerNorm, and GRANOLA?", "limitations": "Please refer to weakness and questions.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "S1. the paper is well-structured and easy to follow.\n\nS2. GRANOLA consistently bring performance improvement on all benchmark datasets.\n\nS3. Baselines are carefully selected and organized.", "weaknesses": "W1. GRANOLA involves an additional GNN module to learn the adaptive normalization, making it more costly and less scalable than its counterparts. It would be better if the authors could provide some experimental results to show how much additional time we will need when applying GRANOLA.\n\nW2. The proposed GRANOLA is only tested on GIN and GSN backbones. It would be better to check if it could be applied to more common backbone models such as GCN, GAT, etc.\n \nW3. (This is a minor point). Code is not provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive feedback. We are glad to see the reviewer has appreciated the presentation of our work, finding the paper well-structured and easy to follow. We proceed by answering each question in the following.\n\n**W1:** GRANOLA involves an additional GNN module to learn the adaptive normalization, making it more costly and less scalable than its counterparts. It would be better if the authors could provide some experimental results to show how much additional time we will need when applying GRANOLA.\n\n**A:**  We agree with the reviewer that our GRANOLA involves some additional computations due to the GNN layers in the normalization mechanism. However, this addition allows the normalization to adapt to the input graph and the task at hand, yielding significant performance improvements as reflected in our experiments. \nFurthermore, in our paper, we report and discuss the runtimes in Appendix G, as well as the computational complexity of our method (which is linear in the number of nodes and edges, as standard MPNNs). Our results indicate that while GRANOLA requires additional computations (3x slower than Batchnorm), it is still a fraction of the cost of more complex methods (5.2x faster than a scalable provably-powerful GNN), while yielding favorable downstream performance. We believe that finding good tradeoffs between computational complexity of methods and their accuracy is important. In our revision, we will ensure to highlight this point better in the main text.\n\n**W2:** The proposed GRANOLA is only tested on GIN and GSN backbones. It would be better to check if it could be applied to more common backbone models such as GCN, GAT, etc.\n\n**A:** As stated in our paper on Lines 267-268, our motivation for experimenting with GIN is that it is maximally expressive among standard MPNNs (i.e., it is as expressive as 1-WL). Additionally, we demonstrated that our GRANOLA method can be beneficial for methods that exceed 1-WL expressiveness, such as GSN. This shows that GRANOLA is beneficial for different kinds of GNNs with varying levels of expressiveness.\nNevertheless, we agree that experimenting with additional backbones is interesting and important. Therefore, we have now added results using GCN (Kipf et al., 2017), GAT (Veličković et al., 2018), and GPS (Rampášek et al., 2022) as backbones, combined with our GRANOLA method. Our results are provided in the table below and have been added to our paper. \nAs can be seen from the table, GRANOLA **consistently improves** these various backbones. These results further underscore the versatility of GRANOLA, which can be potentially coupled with any GNN layer and improve its performance.\n\n| Method             | ZINC-12k  $\\downarrow$  | OGBG-MOLHIV $\\uparrow$ |\n|--------------------|-------------|-------------|\n| GCN                | 0.367±0.011 | 76.06±0.97  |\n| GCN+GRANOLA (Ours) | 0.233±0.005 | 77.54±1.10  |\n|--------------------|-------------|-------------|\n| GAT                | 0.384±0.007 | 76.0±0.80   |\n| GAT+GRANOLA (Ours) | 0.254±0.009 | 77.39±1.03  |\n|--------------------|-------------|-------------|\n| GPS                | 0.070±0.004 | 78.80±1.01  |\n| GPS+GRANOLA (Ours) | 0.062±0.006 | 79.21±1.26  |\n\n\nKipf et al., 2017. Semi-Supervised Classification with Graph Convolutional Networks. ICLR 2017\n\nVeličković et al., 2018. Graph Attention Networks. ICLR 2018\n\nRampášek et al., 2022. Recipe for a General, Powerful, Scalable Graph Transformer. NeurIPS 2022\n\n**W3:** (This is a minor point). Code is not provided.\n\n**A:** We agree that making the code public is important. To this end, our submission includes a statement that upon acceptance, we will release our code on GitHub. We confirm that this is indeed the case.\n\n**Q1:** The authors point out that the traditional normalization may not effectively capture the unique characteristics of graph-structured data. I am curious to see is there any empirical study or theoretical results to justify this point?\n\n**A1:** Traditional normalization techniques may result in a loss of expressiveness (the ability to compute certain functions) due to their lack of consideration of the underlying graph. For example, as we show in our paper (Figure 2), normalizing an MPNN with BatchNorm, together with the choice of the ReLU activation function (which is a very common choice used in various papers, as discussed in Lines 112-113), might lead to the loss of the ability to compute node degrees, which is an essential feature in graph learning. \n\n**Q2:** Figure 2 provides an example to illustrate that BatchNorm may make the GNN less powerful. Is it possible to have something similar to visualize the performance of BatchNorm, InstanceNorm, LayerNorm, and GRANOLA?\n\n**A2:** In Appendix C, we present additional motivating examples representing failure cases for other normalization methods. However, we understand the importance of visualization, and we will include additional figures similar to Figure 2. Thank you for the suggestion.\n\n---\nWe sincerely appreciate the reviewer’s constructive feedback. We have made efforts to address their questions thoroughly, and have conducted the suggested experiments. We kindly ask them to reconsider their rating if they find our responses satisfactory.", "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": "", "extra_scores": {}}, {"review_id": "qd558e03O2", "reviewer": "Reviewer_Ao3Y", "summary": "The paper pertains to the problem of using normalisation techniques specifically designed for graph-structured data and Graph Neural Networks (GNNs). Using constructed illustrative examples, the authors claim that existing normalisation techniques (including others designed for graphs) may create expressivity issues to the GNNs to which they are applied. Motivated by these examples, they speculate that one possible reason is the lack of adaptivity of the normalisation (affine) parameters to the input graph. To that end, they propose to replace fixed normalisation parameters with adaptive ones, produced at each layer by an auxiliary GNN for each vertex of the input graph. Additionally (and probably crucially), the auxiliary GNNs do not only receive the current vertex features as inputs but also Random Node Features (typically sampled from a Gaussian). The last one is known to render GNNs universal, and so is the case here. Experimentally, the method is tested on a battery of tasks and ablated across several factors (training convergence speed, combined with more expressive architectures than plain MPNNs), showing consistently improved performance compared to other normalisation methods and competitiveness with the state-of-the-art in several cases.", "questions": "- Have the authors tried to modify a different normalisation technique, apart from LayerNorm? This might be an interesting ablation study.\n- Do the authors need a GNN normalisation network for each layer of the GNN processing network?", "limitations": "The authors have mentioned some limitations (mainly the gap in performance compared to state-of-the-art), but I think others should be discussed more extensively (e.g. efficiency - see weaknesses). \n\nI do not foresee any negative societal impact.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "**Clarity**. The paper is well-written, easy-to-follow and all the concepts are clearly explained. It can therefore be understood by a wider audience.\n\n**Contextualisation to related work**. An extensive review and comparisons with related works are provided, allowing the reader to grasp their differences and understand the innovation of the proposed approach.\n\n**Importance to the GNN community.** The techniques proposed by the authors are of general interest to the GNN community since they clearly and consistently improve current normalisation techniques and show good potential for adaptation in practice in various problems. Additionally, it is one of the few works showcasing the practical benefits of RNF (however see also weaknesses), which is a long-standing puzzle for GNN researchers.\n\n**Empirical results**. The proposed method appears to work quite well and consistently in practice, in terms of empirical generalisation. In particular, it provides improvements against all base architectures tested and against all competing normalisation techniques, while both methodological techniques proposed (adaptive normalisation + RNF) are sufficiently ablated and shown to be important to be combined to obtain the desired performance gains.", "weaknesses": "**Reservations regarding claims and the selected way to present findings**. \n- One of my main objections to the presented manuscript is the way the findings were selected to be presented. In particular, the authors present their work as a graph-oriented adaptive normalisation technique and motivate their approach by comparing it against other normalisation techniques, both intuitively using constructed counterexamples and empirically, showcasing consistent improvements. Nevertheless, it seems to me that the main reason behind the empirical success is the random features. For example, see Table 2, where the adaptive normalisation per se does not seem to provide any significant practical advantages. \n- However, as the authors correctly point out, random features are known to behave subpar in practice, despite their theoretical advantages. This leads me to believe that the authors have probably found a way to *improve the performance of random features*. To me, this is an important contribution per se, but the authors have chosen not to present their paper in that way, nor to sufficiently point out this takeaway in their paper. \n- On the other hand, the authors have devoted a substantial part of the paper to motivating adaptive normalisation and discussing other normalisation techniques. In my viewpoint, the intuitive explanations provided (the examples in sec. 2.2. and the last paragraph before section 3.1.) are speculative and do not seem to be the real reason behind the success of the approach. \n- Note also, that in several parts of the paper, the authors claim that existing normalisation techniques limit MPNNs’ expressivity, but I am not sure if this is the case. I think that if the authors choose to keep these claims, they should probably be provided with a more rigorous theoretical statement. \n- I think that the most important question that needs to be addressed is why incorporating RNF into a normalisation layer overcomes their current limitations in providing performance improvements. I recommend that the authors discuss this both in their rebuttal and the paper, as it will provide important insights.\n\n**Efficiency**. Another reservation I have about this work is that computational efficiency might be an issue, but is not adequately discussed.  For example, the runtimes provided by the authors in Table 4 in the appendix, show an almost 3-fold increase in both training and inference time. Although this might not be significant compared to other more expressive GNNs, the comparison between the performance-complexity trade-offs is not clear. Moreover, it is a limitation of this method and should be more clearly discussed in the main paper.\n\n**Limited evaluation against baselines**. Although as I mentioned before, the results are indeed convincing, both from a perspective of a normalisation technique and of a random feature technique, the authors have not sufficiently compared against the state-of-the-art. To their credit, they did include other baselines in the supplementary material and mentioned the gap in performance in their limitations section, but I think it would be fairer to discuss this more prominently (especially since this work can be perceived as an expressive GNN and not as a normalisation technique alone). \n\n**Limited technical novelty**: Finally, a minor weakness is that there is limited novelty from a technical perspective, since if I am not mistaken adaptive normalisation has been proposed before for other domains (e.g. AdaIN, Huang et al., ICCV’17 is a relevant example – discussed by the authors in the appendix) and random features are well-known in the GNN community.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback, and the recognition of the importance of this work for the GNN community. The reviewer also raised concerns, which we address below. \n\n**Q1:** ..it seems to me that the main reason behind the empirical success is the random features.\n\n**A1:** We found that the combination of RNF and graph adaptivity drives GRANOLA's success, as shown by the worse performance of RNF-PE and RNF-NORM (lines 263-266), which lack graph adaptivity, and GRANOLA-NO-RNF, which omits RNF, compared to GRANOLA.\n\n**Q2:** ..This leads me to believe that the authors have probably found a way to improve the performance of random features. To me, this is an important contribution per se.\n\n**A2:**  We agree that our method makes RNF practical and, thus, offering a contribution to RNF research. We discussed this in the paper (lines 235-245),  and we will make it more prominent.\n\nWe remark that other expressive GNNs can be used for the normalization function (lines 245-249). Thus, we have conducted an experiment, using DS-GNN [1] as our $\\text{GNN}\\_\\text{NORM}$, instead of an MPNN + RNF.\nThe table shows that GRANOLA-SubgraphGNN behaves similarly to GRANOLA,  but with additional complexity of the Subgraph GNN. This shows that the expressivity of $\\text{GNN}_\\text{NORM}$ does not necessarily need to be achieved by RNF, and our choice was motivated by the linear complexity of MPNNs + RNF.\n\n| | ZINC-12k $\\downarrow$ | OGBG-MOLHIV $\\uparrow$ |\n|--|--|--|\n| GIN+GRANOLA-SubgraphGNN | 0.1186±0.008 | 78.62±1.31  |\n| GIN+GRANOLA (Using RNF, as in the paper) | 0.1203±0.006 | 78.98±1.17 |\n\n[1] Bevilacqua et al., 2022. Equivariant Subgraph Aggregation Networks\n\n**Q3:** In several parts of the paper, the authors claim that existing normalisation techniques limit MPNNs’ expressivity, but I am not sure if this is the case.\n\n**A3:** This result is explained in Cai et al., 2021, and we provide a slightly more formal explanation, which we will expand in the paper.\n\nTheorem: Let $f$ be a stacking of GIN layers with non-linear activations followed by sum pooling. Let $f^{\\text{norm}}$ be the architecture obtained by adding InstanceNorm or BatchNorm without affine parameters. Then $f^{\\text{norm}}$ is strictly less expressive than $f$.\n\nProof Sketch: All non-isomorphic graphs that can be distinguished by $f^{\\text{norm}}$ can clearly be distinguished by $f$. To show that $f^{\\text{norm}}$ is strictly less expressive than $f$, consider two CSL graphs with different numbers of nodes. These are distinguishable by $f$. However, applying InstanceNorm to the output of GIN results in a zero matrix (Proposition 4.1 in Cai et al., 2021). Similarly, if the batch consists of these two graphs, applying BatchNorm results in a zero matrix. Since the output of the normalization is a zero matrix, they are indistinguishable by $f^{\\text{norm}}$.\n\nCai et al, 2021. GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training\n\n**Q4:** Why incorporating RNF into a normalisation layer overcomes their current limitations in providing performance improvements. \n\n**A4:** We agree with the reviewer that this corresponds to our main research question, and we will add a more thorough discussion. \n\nIncorporating RNF into our GRANOLA allows it to *fully adapt to the input graph*,  providing different affine parameters for non-isomorphic nodes. Full adaptivity is lost when removing RNF and using a standard MPNN as $\\text{GNN}\\_\\text{NORM}$, as in GRANOLA-no-RNF. This is because GRANOLA-no-RNF is not more expressive than an MPNN (Prop. 4.1), and thus, there exist non-isomorphic nodes that will get the same representation (and the same affine parameters).  However, any other most expressive architecture used as $\\text{GNN}_\\text{NORM}$ would achieve the same full adaptivity, and our choice of MPNN + RNF was motivated by its linear complexity.\n\n**Q5:** Another reservation I have about this work is that computational efficiency might be an issue, but is not adequately discussed. \n\n**A5:** We agree that the performance improvement of GRANOLA requires additional computations (Appendix G). However, the overall runtime remains a fraction of more expressive methods (5.2x faster than efficient expressive models like SubgraphGNNs).\n\nWe remark that practitioners often have different needs from their models. At times, they might prefer accuracy over efficiency (e.g., drug discovery). In such scenarios, GRANOLA offers a strong tradeoff between performance and cost. We will clarify this in the revision.\n\n**Q6:** … adaptive normalisation has been proposed before for other domains (e.g. AdaIN, Huang et al., ICCV’17 is a relevant example – discussed by the authors in the appendix) and random features are well-known in the GNN community.\n\n**A6:** Despite some similarities, GRANOLA differs significantly from AdaIN, which adjusts the content's mean and variance to match the *style input*. Additionally, GRANOLA employs RNF for full graph adaptivity, but other expressive methods could also be used as shown in A2.\n\n**Q7:** Have the authors tried to modify a different normalisation technique, apart from LayerNorm?\n\n**A7:** Thank you for the suggestion. We modified BatchNorm to be graph adaptive using our GRANOLA design. Table 1 in the additional PDF shows that GRANOLA-BatchNorm outperforms BatchNorm, highlighting the role of graph adaptivity in normalizations.\n\n**Q8:**  Do the authors need a GNN normalisation network for each layer of the GNN processing network?\n\n**A8:** We use a shallow GNN normalization network for each layer. We also tested a variant with a shared normalization GNN across all layers. Table 2 in the additional PDF shows that while per-layer normalization GNNs yield better results, sharing one still significantly improves over the baselines\n\n***\nWe sincerely appreciate the reviewer’s feedback. We have made efforts to address their questions thoroughly, and if they feel the same, we kindly ask them to reconsider their rating.", "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": "", "extra_scores": {}}, {"review_id": "cKCGmA6KJU", "reviewer": "Reviewer_tP2u", "summary": "This paper introduces GRANOLA (Graph Adaptive Normalization Layer), a novel normalization technique designed specifically for Graph Neural Networks (GNNs). The authors identify a critical gap in existing normalization methods for GNNs, which often fail to capture the unique structural characteristics of graph data or consistently improve performance across various tasks. GRANOLA aims to address these limitations by dynamically adjusting node features based on both the graph structure and Random Node Features (RNF). The key innovation lies in its use of an additional GNN (termed GNN_NORM) to generate normalization parameters that are adaptive to the input graph. The paper provides a comprehensive theoretical analysis of GRANOLA, demonstrating its ability to default to RNF-augmented Message Passing Neural Networks (MPNNs) and proving its increased expressive power compared to standard MPNNs. The authors also show that the use of RNF is necessary for this increased expressiveness. Empirically, the paper presents extensive evaluations across multiple graph benchmarks.", "questions": "The authors address some limitations of their work in the conclusion section. They could have elaborated more on the practical limitations of GRANOLA, such as potential challenges in implementing it in resource-constrained environments or its scalability to extremely large graphs. While the normalization GNN depth ablation study is available in Appendix H.2, a more detailed discussion on the choice of other hyperparameters for the normalization GNN, such as dimensions, would be beneficial. This is particularly important given that the normalization GNN is at the core of the GRANOLA framework.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "GRANOLA presents a novel approach to graph normalization by incorporating graph adaptivity and RNF, addressing a significant gap in existing methods.\n\nThe paper provides solid theoretical analysis, including proofs of GRANOLA's expressive power and its ability to default to RNF-augmented MPNNs.\n\nThe authors conduct extensive experiments across multiple datasets and tasks, demonstrating GRANOLA's consistent performance improvements over existing normalization techniques.\n\nThe paper effectively demonstrates how GRANOLA serves as a valuable bridge between the theoretical expressiveness of RNF-augmented MPNNs and practical performance improvements in graph learning tasks.\n\nGRANOLA maintains the same asymptotic complexity as standard MPNNs while offering improved performance, making it a practical solution for real-world applications.", "weaknesses": "GRANOLA's parameters (gamma and beta) are unique for each node, layer, and feature attribute. This fine-grained adjustment is significantly more detailed than most normalization methods, making GRANOLA resemble a new model architecture rather than a normalization technique. The motivation as a normalization method may be somewhat inappropriate given this level of detail.\n\nThe paper could benefit from additional experiments, such as removing the $\\gamma_{b,n,c}^{(\\ell)}$ term and retaining only the affine intercept term $\\beta_{b,n,c}^{(\\ell)}$. This would help determine whether the improved performance is due to the detailed internal model adjustments or the normalization concept itself.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are happy to see that the reviewer has appreciated the novelty of our approach, while finding our theoretical analysis solid and our empirical evaluation extensive. We would like to thank them for raising interesting points of discussion, which we address in the following.\n\n**Q1:** GRANOLA's parameters (gamma and beta) are unique for each node, layer, and feature attribute. This fine-grained adjustment is significantly more detailed than most normalization methods, making GRANOLA resemble a new model architecture rather than a normalization technique. The motivation as a normalization method may be somewhat inappropriate given this level of detail.\n\n**A1:** We agree with the reviewer that the gamma and beta are more refined than other standard normalization layers, but this level of detail is intrinsic to adaptive normalization layers. In an adaptive normalization, instead of using the same affine parameters $\\gamma_{c}^{(\\ell)}$ and $\\beta_{c}^{(\\ell)}$ (Equation (3)) for all the nodes in all the graphs, the normalization method utilizes specific parameters conditioned on the input graph. This adaptivity has proven to be a valuable property in other domains (for instance, Huang et al., 2017), and in our case is achieved by generating the affine parameters through the normalization GNN.\n\nHuang et al., 2017. Arbitrary style transfer in real-time with adaptive instance normalization. ICCV 2017\n\n\n**Q2:** The paper could benefit from additional experiments, such as removing the $\\gamma_{b,n,c}^{(\\ell)}$ term and retaining only the affine intercept term $\\beta_{b,n,c}^{(\\ell)}$. This would help determine whether the improved performance is due to the detailed internal model adjustments or the normalization concept itself.\n\n\n**A2:** Following your suggestion, we have included an additional experiment obtained by removing the $\\gamma_{b,n,c}^{(\\ell)}$ term by setting it to zero, while retaining only $\\beta_{b,n,c}^{(\\ell)}$. The following table shows that GRANOLA outperforms this method, highlighting the importance of the normalization concept.\n\n| Method                        | ZINC-12k  $\\downarrow$  | OGBG-MOLHIV $\\uparrow$ |\n|-------------------------------|--------------|-------------|\n| GIN+GRANOLA-$\\beta_{b,n,c}^{(\\ell)}$-only    | 0.1928±0.018 | 74.11±1.39  |\n| GIN+GRANOLA (As in the paper) | 0.1203±0.006 | 78.98±1.17  |\n\n**Q3:** The authors address some limitations of their work in the conclusion section. They could have elaborated more on the practical limitations of GRANOLA, such as potential challenges in implementing it in resource-constrained environments or its scalability to extremely large graphs. \n\n**A3:** Thank you for the suggestion. We agree that expanding on the practical limitations of GRANOLA is valuable. In practice, adding GRANOLA to standard MPNNs does not significantly impact memory usage (and it maintains the linear space complexity of MPNNs). Therefore, GRANOLA faces the same challenges of existing and widely-used GNN methods when dealing with extremely large graphs. We will elaborate on this point in the next revision.\n\n**Q4:** While the normalization GNN depth ablation study is available in Appendix H.2, a more detailed discussion on the choice of other hyperparameters for the normalization GNN, such as dimensions, would be beneficial. This is particularly important given that the normalization GNN is at the core of the GRANOLA framework.\n\n**A4:** Following the reviewer's suggestion, we will include a more thorough discussion of the hyperparameters for our $\\text{GNN}\\_{NORM}$. For completeness, we note that $\\text{GNN}\\_{NORM}$ maintains the same embedding dimensions as the outer GNN layer, and our hyperparameter search includes different choices for the number of layers within $\\text{GNN}\\_{NORM}$. While other configurations are possible, we found these choices to be effective in practice and help reduce the number of parameter choices.\n\n***\n\nWe are grateful to the reviewer for their feedback. We made efforts to address all the concerns raised, and, if they feel the same, we kindly ask them to reconsider their rating.", "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": "", "extra_scores": {}}, {"review_id": "VvFXpxWkEa", "reviewer": "Reviewer_PwFk", "summary": "The paper introduces a novel graph-adaptive normalization layer named GRANOLA for Graph Neural Networks (GNNs). The authors argue that existing normalization techniques, such as BatchNorm and InstanceNorm, are not well-suited for GNNs due to their design not considering the unique characteristics of graph-structured data. To address this, GRANOLA is proposed to normalize node features by adapting to the specific characteristics of the graph, using Random Node Features (RNF) to generate expressive node representations. The paper provides theoretical results supporting the design choices and demonstrates through empirical evaluation that GRANOLA outperforms existing normalization techniques across various graph benchmarks.", "questions": "See weaknesses", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper presents a novel normalization technique specifically tailored for GNNs, addressing a recognized gap in the field where traditional normalization layers do not capture the unique properties of graph data effectively.\n\n* The authors provide a solid theoretical basis for their method, including proofs that GRANOLA can achieve full adaptivity to the input graph, which is a significant contribution to the understanding of normalization in GNNs.\n\n* The paper offers extensive empirical results across multiple datasets and tasks, showing consistent performance improvements of GRANOLA over existing methods, which strengthens the credibility of the proposed technique.", "weaknesses": "* The work focuses on the normalization of GNNs for graph-level tasks. However, there is a type of model that dominates this field: Graph Transformers. I'm curious if this normalization would help with the graph transformers in graph-level tasks.\n\n* Implementation details are not so clear. Is the RNF sampled once and trained like other parameters or just randomly sampled at each mini-batch (or each epoch)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback, and we are glad to see they have recognized the significance of our contribution. They have nonetheless asked some questions, which we address below.\n\n**Q1:** The work focuses on the normalization of GNNs for graph-level tasks. However, there is a type of model that dominates this field: Graph Transformers. I'm curious if this normalization would help with the graph transformers in graph-level tasks.\n\n**A1:** Following the reviewer’s suggestion, we have conducted an additional experiment and coupled GRANOLA with the GPS graph transformer (Rampášek et al., 2022), as reported in the following table.\n\nAs can be seen from the table, GRANOLA improves the performance of the GPS transformer, further highlighting its versatility and ability to enhance the performance of various and diverse graph models.\n\n| Method             | ZINC-12k $\\downarrow$   | OGBG-MOLHIV $\\uparrow$ |\n|--------------------|-------------|-------------|\n| GPS                | 0.070±0.004 | 78.80±1.01  |\n| GPS+GRANOLA (Ours) | 0.062±0.006 | 79.21±1.26  |\n\nRampášek et al., 2022. Recipe for a General, Powerful, Scalable Graph Transformer. NeurIPS 2022\n\n**Q2:** Implementation details are not so clear. Is the RNF sampled once and trained like other parameters or just randomly sampled at each mini-batch (or each epoch)?\n\n**A2:** We follow the standard practice of RNF methods (Abboud et al., 2021, Sato et al., 2021), and sample RNF for each mini-batch. We thank the reviewer for pointing it out and we will make it clearer in the next paper revision.\n\nAbboud et al., 2021. The Surprising Power of Graph Neural Networks with Random Node Initialization. IJCAI 2021\n\nSato et al., 2021. Random Features Strengthen Graph Neural Networks. SDM 2021\n\n***\n\nWe are thankful to the reviewer for their constructive feedback. We made efforts to conduct the additional experiments they suggested. If they find our responses satisfactory, we kindly ask them to reconsider their rating.", "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": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all reviewers for their valuable comments and for their efforts in providing actionable feedback to enhance the quality of the submission. 

Overall, reviewers appreciated our novel adaptive normalization scheme for GNNs that maintains linear complexity and provides consistent improvements over all normalization schemes. We are glad to see that reviewers recognized the potential impact of the paper, found *“of general interest to the GNN community”* (**Ao3Y**), *“having good potential for adaptation in practice”* (**Ao3Y**),  being *“a practical solution for real-world applications”* (**tP2u**). The reviewers further highlighted the contribution of this work, deeming it *“significant”*  (**PwFk**), and our approach *“novel”* (**tP2u**, **PwFk**) .

Additionally, reviewers unanimously appreciated the experimental evaluation, finding it *“extensive”* (**tP2u**, **PwFk*), yielding *“consistent improvements”* (**vndL**, **Ao3Y**, **tP2u**) and recognizing its *“competitiveness with the state-of-the-art”* (**Ao3Y**). Additionally, we are glad to see reviewers **tP2u** and **PwFk** have both appreciated the theoretical analysis, finding it *“solid”* (**tP2u**, **PwFk**).

The paper presentation has also been particularly valued, with the paper described as  *“well-structured”* (**vndL**), *“well-written”* (**Ao3Y**),  and *“easy to follow”* (**vndL**, **Ao3Y**).

**New Experiments.** Several additional experiments were conducted following the reviewers’ comments:
1. An additional variant of our approach, where instead of using an MPNN + RNF as $\text{GNN}_\text{NORM}$, we employ a Subgraph GNN, showing that full-graph adaptivity can be obtained with any expressive architecture other than MPNN + RNF, and our choice was dictated by their linear complexity (**Ao3Y**);
2. A comparison of GRANOLA and standard normalizations using GAT as the GNN backbone, showing that GRANOLA is beneficial for different kinds of GNNs and consistently improves their performance (**vndL**);
3. A variant of our approach that uses the BatchNorm blueprint instead of the LayerNorm-node one, demonstrating that adaptivity is beneficial for different normalization blueprints (**Ao3Y**);
4. An additional analysis of the impact of the normalization term, achieved by removing the $\gamma_{b,n,c}^{(\ell)}$ term by setting it to zero, further highlighting the importance of normalizing (**tP2u**);
5. An evaluation of the performance of GRANOLA when coupled with graph transformers, demonstrating the versatility of GRANOLA, which can be coupled with any layer and improve its performance (**PwFk**).

If the reviewers find that we have adequately addressed their concerns, we would be grateful if they would consider reassessing their rating. We are also open to further discussion and welcome any additional input.

Meta-review: This paper proposes a new usage of RNF (random node features) for GNNs by not just concatenating the random features to node representations but using RNF + another MPNN to compute the affine parameters of LayerNorms in the main GNN, so that different nodes can be normalized differently. Empirically the new method shows improved performance compared to traditional normalization methods and the plain MPNN + RNF. Despite the uniform acceptance recommendations from reviewers, I would like to point out a few aspects to improve the paper: 1. RNF can only approximately maintain permutation equivariance with extensive training, and is thus less useful in practice. The authors could explain why RNF used for normalization can alleviate this issue. 2. The theoretical analysis is a bit trivial. I would expect a more in-depth analysis of the training dynamics with the proposed normalization.
Decision: Accept (poster)