GRANOLA: Adaptive Normalization for Graph Neural Networks

Authors: moshe  eliasof
beatrice  bevilacqua
carola-bibiane  schönlieb
haggai  maron
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 13:35:28

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).

Main paper: 
 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 of GNNs, such as limited expressive power [63, 41, 40] and oversmoothing [46] . Notably, analogously to architectures in other domains [30, 18] , these GNN layers are 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 normalization 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.Contributions. Our contributions are as follows: (1) We provide an overview of different normalization schemes in graph learning, outlining adaptivity as a 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.2 Normalization layers for GNNs 
basic setup and definitions: 
 Let G = (A, X) denote graph with N ∈ N nodes, where A ∈ R N ×N is the adjacency matrix and X ∈ R N ×C is the node feature matrix, with C ∈ N the feature dimension. Consider a batch of B ∈ N graphs encoded by the adjacency matrices {A b } B-1 b=0 , and, for simplicity, assume that all graphs in the batch have the same number of nodes N . We consider a model composed of L GNN layers, with L ∈ N. Each GNN layer is followed by a normalization layer NORM and an activation function ϕ. At any layer ℓ ∈ [L], the output of the GNN layer for a batch of graphs consists of (intermediate) node representations, which can be gathered in a matrix H(ℓ) ∈ R B×N ×C (since all graphs have the same number of nodes per our assumption 2 ). These undergo a normalization and an activation layer, resulting in node representations denoted by H (ℓ) ∈ R B×N ×C , which serve as input of the next GNN layer, with H (0) := X. 3 Throughout this paper, for any three-dimensional tensor, we use subscripts to denote access to a corresponding dimension. 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 the 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 asEQUATIONThen, the overall update rule for the batch of B graphs can be written asEQUATIONfor ℓ ∈ [L]. Equation ( 2) serves as a general blueprint, and in what follows we will show different ways to customize it in order to implement different existing normalization techniques.We consider normalization layers based on the standardization [38] of their inputs, as this represents the most common choice in widely used normalizations. Generally, a standardization-based normalization layer first shifts each element h(ℓ) b,n,c by some mean µ b,n,c , and then scales it by the corresponding standard deviation σ b,n,c , i.e., NORM( h(ℓ) b,n,c ; H(ℓ) , ℓ) = γ (ℓ)EQUATIONwhere γEQUATIONc ∈ R are learnable affine parameters, that do not depend on b nor n.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 H(ℓ) they are computed. We present them below, and visualize them in Figure 1 .BatchNorm. BatchNorm [34] computes the statistics across all nodes and all graphs in the batch, for each feature separately. Therefore, we haveEQUATIONwhich implies that µ b,n,c = µ b ′ ,n ′ ,c for any b ′ ∈ [B] and any n ′ ∈ [N ] (and similarly for σ 2 b,n,c ). Despite the widespread use of BatchNorm in graph learning [63] , it is important to recognize scenarios where alternative normalization schemes might be more suitable. A concrete example illustrating this need is 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, as standard practice [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 in Example C.1 in Appendix C, where it is demonstrated that relying on the affine parameter β LayerNorm. LayerNorm [3] can be defined in two ways in the context of graphs [24] . The first, which we call LayerNorm-node, behaves similarly to Lay-erNorm in Transformer architectures [59] , and computes statistics across the features for each node separately, that isEQUATIONand therefore µ b,n,c = µ b,n,c ′ for any c ′ ∈ [C] (and similarly for σ 2 b,n,c ). The second variant, which we call LayerNorm-graph, is similar to LayerNorm in Computer Vision [62] , and computes statistics across the features and across all the nodes in each graph, that isEQUATIONand therefore µ b,n,c = µ b,n ′ ,c ′ for any n ′ ∈ [N ] and any c ′ ∈ [C] (and similarly for σ 2 b,n,c ). Example C.5 in Appendix C presents a motivating example similar to Figure 2 for LayerNorm.Graph-Specific normalizations. Several normalization methods tailored to graphs have been recently 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 . DiffGroup-Norm [74] and GraphSizeNorm [21] normalize features considering nodes across different graphs, akin to BatchNorm. Similarly to InstanceNorm, PairNorm [72] and MeanSubtractionNorm [64] shift the input by the mean computed per channel across all the nodes in the graph, with differences in the scaling strategies. GraphNorm [11] extends InstanceNorm by incorporating a multiplicative factor to the mean. NodeNorm [75] behaves similarly to LayerNorm-node but only scales the input, without shifting it. We provide additional details in Appendices A and B, and include methods that normalize the adjacency matrix before the GNN layers, which, however, fall outside the scope of this work.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 no 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 (e.g., independence assumptions, noiseless settings, model well-specification, 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
method: 
 The following section describes the proposed GRANOLA framework. We start with identifying adaptivity as a desired property in a graph normalization layer. 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 a 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 in 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.In an adaptive normalization, instead of using the same affine parameters γ 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 of MPNNs [41, 63] , when designing GRANOLA, we advocate for using a normalization GNN with high expressiveness. Notably, most expressive GNNs come at 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.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.ℓ ∈ [L], for each graph b ∈ [B], we sample RNF R (ℓ) b ∈ R N ×K , K ∈ N, from some joint probability distribution, e.g., Normal, R (ℓ) b ∼ D. Then, we Algorithm 1 GRANOLA Layer Input: Node features H(ℓ) b ∈ R N ×C , obtained from GNN (ℓ-1) LAYER . Output: Normalized features per node n ∈ [N ] and channel c ∈ [C]. 1: Sample random node features R (ℓ) b ∈ R N ×K . 2: Compute Z (ℓ) b = GNN (ℓ) NORM (A b , H(ℓ) b ⊕ R (ℓ) b ). 3: Compute affine parameters: γ (ℓ) b,n = f (ℓ) 1 (z (ℓ) b,n ), β (ℓ) b,n = f (ℓ) 2 (z (ℓ)b,n ). 4: Compute mean and standard-deviation µ b,n,c and σ b,n,c ofH(ℓ) b . 5: Return γ (ℓ) b,n,c h(ℓ) b,n,c -µ b,n,c σ b,n,c + β (ℓ) b,n,c . concatenate R (ℓ)b with the intermediate node featuresH(ℓ) b obtained from GNN (ℓ-1)LAYER (Equation ( 1)), and pass the resulting feature matrix through an additional GNN, i.e.,EQUATIONwhere ⊕ denotes feature-wise concatenation, and GNNNORM is a shallow GNN architecture, with L (ℓ) NORM layers. The affine parameters are then computed fromEQUATION2 are learnable functions (e.g., MLPs), and γEQUATIONwhere µ b,n,c and σ b,n,c are the mean and std of H(ℓ) , 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, γ(ℓ) b,n,c , β (ℓ) b,n,cnot only depend on c, but they also have a dependency on b and n and indeed vary for different graphs and nodes. Notably, this is possible because our normalization is adaptive to the input graph. Methods that disregard this information are compelled to use the same learnable normalization values for all graphs, as they operate without knowledge of the specific input graph being considered.GRANOLA-NO-RNF. We consider a variant of GRANOLA that does not sample RNF and instead uses onlyH(ℓ) b to obtain Z (ℓ)b in Equation (8) , which therefore becomesEQUATIONWe refer to this variant as GRANOLA-NO-RNF, as it allows us 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-RNF, do not impact the asymptotic time and space complexity of standard MPNNs, which remains linear in the number of nodes and edges, as we show in Appendix G.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to 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. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
theoretical analysis: 
 In this section, we explain the main design choices taken in the development of GRANOLA. Specifically, we elaborate on 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 et 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 ability 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 + GRANOLA inherits the (ϵ, δ)-universal 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. Importantly, 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 parameters γ b,n,c , the same procedure can be applied without the use of RNF, a variant we denoted as GRANOLA-NO-RNF in Section 3 (Equation ( 11)). However, we theoretically demonstrate next that an MPNN + GRANOLA-NO-RNF 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 input domain consists of graphs of a specific size. For every MPNN with GRANOLA-NO-RNF (Equation (11)) there exits a standard MPNN with the same expressive power. Proposition 4.1 is proven by showing that an MPNN with GRANOLA-NO-RNF can be implemented by a 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 GRANOLA-NO-RNF. 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-RNF 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 expressiveness, 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 a 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 to 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 a survey on expressive methods. 
experimental results: 
 In this section, we evaluate the performance of GRANOLA. In particular, we seek to 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 variant GRANOLA-NO-RNF, 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://github.com/MosheEliasof/GRANOLA. b in Equation (8) . We denote this baseline by RNF-NORM and remark that it corresponds to a 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-expressive within the MPNN family. Furthermore, we compare GRANOLA to GNNs in the same complexity class and refer the reader to Appendix H.8 for additional comparisons. [58] 0.2984±0.017 GIN + LayerNorm-node [3] 0.1649±0.009 GIN + LayerNorm-graph [3] 0.1609±0.014 GIN + Identity 0.2209±0.018GRAPH NORMALIZATION LAYERS GIN + PairNorm [72] 0.3519±0.008 GIN + MeanSubtractionNorm [64] 0.1632±0.021 GIN + DiffGroupNorm [74] 0.2705±0.024 GIN + NodeNorm [75] 0.2119±0.017 GIN + GraphNorm [11] 0.3104±0.012 GIN + GraphSizeNorm [21] 0.1931±0.016 GIN + SuperNorm [12] 0.1574±0.018GIN + GRANOLA-NO-RNF 0.1497±0.008 GIN + GRANOLA 0.1203±0.006ZINC. We experiment with the ZINC-12K molecular dataset [57, 28, 21] , where the goal is to regress the solubility of molecules. As can be seen from Table 1 , GRANOLA achieves significantly lower (better) mean-absolute-error compared to existing standard and graph-designated normalization layers, while outperforming all its natural baselines. Moreover, GRANOLA emerges as the best-performing model with the same time complexity of a standard MPNN.OGB. We test our GRANOLA on the OGB collection [31] , and report its performance in Table 2. Notably, GRANOLA consistently improves over existing standard normalization methods while retaining similar asymptotic complexity. 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 normalization methods, GRANOLA also offers a consistent improvement. As an example, on MOLESOL we obtain a RMSE of (lower is bet- It 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 to its natural baselines, as well as standard and graph-designated normalization 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 a normalization layer, accelerated training convergence is also an important desired property [34, 11] . Figure 4 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 on 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] can also benefit from GRANOLA. To this end, we 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 normalization 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. Specifically, 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 on others. Notable examples are GraphNorm and PairNorm, which, despite offering improved performance compared to BatchNorm on most of the OGB datasets, show worse results on ZINC-12K. Furthermore, 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 on 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 a desirable property of graph normalization layers, namely adaptivity to the input graph, and argue that it can be obtained only with expressive architectures. To incorporate this property, we present GRANOLA, a 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 to reduce memory and time complexity (which are 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 a positive impact in domains such as drug discovery.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, 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 in the core of the paper to a 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, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification: All results (Section 5 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 error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• 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 or the standard error of the mean. Justification: Appendix F describes the type of GPUs used in the experiments, Appendix G provides a runtime comparison.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the 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 (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
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.• 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 a 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Not applicable.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing 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 as 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 in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as 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. 
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA]Justification: Not applicable.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on 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.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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. 
 
 Appendix: Standard normalization layers. BatchNorm [34] is arguably one of the most widely used normalization 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 BatchNorm 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 graphlearning, 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-graph [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 is that they were not originally designed with graph-learning in mind. Next, we discuss graph-designated normalization techniques.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 to anti-oversmooth during training. Based on this conclusion, the authors design MeanSubtractionNorm, which removes the mean from the inputs, without rescaling the features. When coupled with GCN [37] , MeanSubtractionNorm 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. DiffGroupNorm [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 a 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 a 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-specific factors, encompassing the number of nodes and the eigenvalues of the neighborhood-induced subgraph for each node. These subgraph-specific 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 works. Despite their wide use, especially on node-level tasks, these normalizations may fail to capture structural information and lead to 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 a 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 a 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 to 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 in 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 in StyleGANs.Random Node Features (RNF) in GNNs. Random input features were used in the context of GNNs to 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 et al. [51] , Abboud et al. [1] , a 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.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.e., BatchNorm, InstanceNorm, LayerNorm-node, LayerNorm-graph) 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:h(ℓ),center b,n,c = h(ℓ) b,n,c -µ b,n,c, where µ b,n,c is as in InstanceNorm (Equation ( 5)), while the scale operation can be written asEQUATIONwith s ∈ R a hyperparameter and the norm is∥ h(ℓ),center b,n ∥ 2 2 = C c=1 | h(ℓ),center b,n,c | 2 .MeanSubtractionNorm. MeanSubtractionNorm [64] is similar to InstanceNorm, but it simply shifts its input without dividing it by the standard deviation (and without affine parameters). That isEQUATIONand µ b,n,c as Equation (5) .MessageNorm. MessageNorm [39] couples normalization with the GNN layer. In particular, it defines the update rule of H (ℓ) as follows,h (ℓ) b,n = ϕ MLP h (ℓ-1) b,n + s∥h (ℓ-1) b,n ∥ 2 ∥m (ℓ-1) b,n ∥ 2 ∥m (ℓ-1) b,n ∥ 2 (14)where s ∈ R a hyperparameter and m(ℓ-1) b,n is the message of node n ∈ [N ] in graph b ∈ [B], which can be defined as m (ℓ) b,v,u = ρ (ℓ) (h (ℓ) b,v , h (ℓ) b,u ) m (ℓ) b,u = ζ (ℓ) ({m (ℓ) b,u,v |u ∈ N b v })with ρ (ℓ) , ζ (ℓ) learnable functions such as MLPs and N b v neighbors of node v in graph b.DiffGroupNorm. DiffGroupNorm [74] first softly clusters nodes and the normalizes nodes within the same cluster by means of BatchNorm. That is, for each graph b ∈ [B] in the batch, it computes a soft cluster assignment asS (ℓ) b = softmax( H(ℓ) b W (ℓ) )where W (ℓ) ∈ R C×D with D ∈ N the number of clusters, and thereforeS (ℓ) b ∈ R N ×D .Let us denote by S (ℓ) ∈ R B×N ×D the matrix containing the cluster assignments for all graphs in the batch, where the b-th row of S (ℓ) is S (ℓ) b . DiffGroupNorm computes a linear combination of the output of BatchNorm applied to each cluster (where the feature is weighted by the assignment value), and adds the result to the input embedding, that isEQUATIONwhere BATCHNORM leverages Equation ( 4), and λ ∈ R is a hyperparameter. Notably, the term h(ℓ) b,n,c in Equation ( 15) is similar to a skip connection, with the difference lying in the fact that skip connections usually add the output of the previous layer ℓ -1 after the norm instead of the output of the current layer before the norm.NodeNorm. NodeNorm [75] is similar to LayerNorm-node, but it simply divides its input by a root of its standard deviation, without shifting it and without affine parameters:EQUATIONwith σ as in Equation ( 6) and p ∈ N a hyperparameter.GraphNorm. GraphNorm [11] builds upon InstanceNorm by adding an additional learnable parameter α (ℓ) ∈ R C which is the same for all nodes and graphs. The equation can be written asEQUATIONand µ b,n,c , σ b,n,c as Equation (5) .GraphSizeNorm. GraphSizeNorm [21] normalizes the node features by dividing them by the graph size, before applying a standard BatchNorm:EQUATIONUnityNorm. UnityNorm [13] consists of a weighted combination of four normalization techniques, where the weightsEQUATIONwhere LAYERNORM-NODE, INSTANCENORM and BATCHNORM leverage respectively Equations (4) to (6) . ADJACENCYNORM computes the statistics for each node across all features of all its neighbors, that isµ b,n,c = 1 |N b n |C u∈N b n C c=1 h(ℓ) b,u,c , σ 2 b,n,c = 1 |N b n |C u∈N b n C c=1 ( h(ℓ) b,u,c -µ b,n,c ) 2 .SuperNorm. SuperNorm [12] embeds subgraph-specific factors into BatchNorm. First, for each node n in graph b it extracts the subgraph induced by its neighbors, denoted as S b,n . Then, it computes the so called subgraph-specific factors for each subgraph, which are the output of an hash function over the number of nodes in the subgraph and its eigenvalues. That is the subgraph-specific factor of S b,n isξ(S b,n ) = Hash(ϕ(|V S b,n |), ψ(Eig S b,n ))where |V S b,n | denotes the number of nodes in S b,n and Eig S b,n its eigenvalues, with ϕ and ψ injective functions.Subgraph-specific factors for all subgraphs in a graph b are collected into a vectorM G b ∈ R N ×1 M G b = [ξ(S b,1 ); ξ(S b,2 ); . . . ; ξ(S b,N )] which is used to obtain two additional vectors M SN b , M RC b ∈ R N ×1 defined as M SN b = ξ(S b,1 ) N n=1 ξ(S b,n ) ; ξ(S b,2 ) N n=1 ξ(S b,n ) ; . . . ; ξ(S b,N ) N n=1 ξ(S b,n ) M RC b = M G b ⊙ M SN b .where ⊙ denotes the element-wise product. Then, the normalization computes the segment average of H(ℓ) b for each graph b, denoted asH(ℓ),segment b ∈ R N ×C, where a row n is defined ash(ℓ),segment b,n = N n=1 h(ℓ) b,n .Then, the input H(ℓ) b is calibrated by injecting the subgraph-specific factors as well as the graph statistics obtained viaH(ℓ),segment b . That is, H(ℓ),calibration b = H(ℓ) b + W (ℓ) H(ℓ),segment b ⊙ (M RC b 1 ⊤ C )where 1 C ∈ {1} C×1 and W (ℓ) = 1 N w (ℓ)⊤ with 1 N ∈ {1} N ×1 and w (ℓ) ∈ R C×1 is a learnable parameter. After injecting subgraph-specific factors, the normalization layer performs BatchNorm on the calibration features, that ish(ℓ),CS b,n,c = BATCHNORM( h(ℓ),calibration b,n,c; H(ℓ),calibration )Finally, subgraph-specific factors are embedded after BatchNorm, by computingEQUATIONwhere γ (ℓ) , β (ℓ) ∈ R C×1 are learnable affine parameters, andP (ℓ)b ∈ R N ×C is a matrix where each entry is obtained asP (ℓ) b,n,c = (M RE b,n,c ) w (ℓ) RE,cwhere w(ℓ) RE ∈ R C is a learnable parameter and M RE b ∈ R N ×C is obtained as M RE b = M RC b N n=1 M RC b,n 1 ⊤ C .Equation (20) represents the output of SuperNorm, followed by an activation function ϕ.In the following we elaborate on the failure cases of existing normalization layers. Throughout this section, we will assume that all GNN layers are message-passing layers, and, in particular, we focus on the maximally expressive MPNN layers presented in Morris et al. [41] , which have been shown to be as expressive as the 1-WL test. In particular Equation ( 1) can be rewritten as follows,EQUATION)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 . 5 Assuming such graphs do not have initial node features, we follow standard practice [63] and initialize Hb for each graph b ∈ [B] as a vector of ones, i.e., H(0) b = 1 ∈ R N ×1. The output of the first GNN layer is already the degree of each node, or a function thereof:EQUATIONwhereEQUATION2 ∈ R 1×C , are learnable weight matrices, and C ∈ 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 = 1. Importantly, in our example, we have thatH (0) b W (0)1 is the same for all nodes in all graphs in the batch, becauseH (0) b and W (0)1 are the same for all nodes and graphs. Therefore, the termH (0) b W (0)1 acts as a bias term in Equation (22) . Thus, for each node, the output of the first GNN layer is simply a linear function of the node degree, which is computed by the termA b H (0)b 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 in 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. In 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 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 β (1) c that shifts the negative outputs before the ReLU, does not offer a definitive solution. Indeed, it is always possible to construct a test scenario where one graph has nodes with degrees significantly smaller than those seen while training, for which the learned shift β(1) c is not sufficiently large to make the output of the normalization layer positive.It is important to mention that the aforementioned example potentially serves as a failure case for other methods that are based on removing the mean µ b,n,c as calculated by BatchNorm in Equation (4). For instance, GraphSizeNorm [21] also suffers from the same issue, as 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 a subset of nodes has a degree less than the average within all the clusters to which it is (softly) assigned.Example C.1 can be easily adapted to represent a 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.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 a 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 (0) b = 1 ∈ R N ×1 . The output of the first GNN layer is already the degree of each node, or a function thereof. Now, consider the normalization layer NORM applied to 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 be 0 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 not sufficient to solve the problem.The aforementioned limitation extends directly to other graph-designed normalizations based on InstanceNorm, such as PairNorm and GraphNorm6 as they also shifts the input in the same way, based on the mean µ b,n,c as defined in Equation ( 5). Example C.5 (LayerNorm-node reduces GNN capabilities to compute node degree (Figure 5 )). Consider the following task: Given a graph G, for each node predict its degree. Consider a graph G consisting of a path of 3 nodes. Assuming the graph does not have initial node features, we initializeH (0) b = 1 ∈ R N ×1, with b = 0 as we only have one graph. We will assume that W (0) 1 = 0 (Equation ( 21)). Therefore, the output of the first GNN layer can be written as: (23) which, for each node, is a vector having at each entry the degree of the node multiplied by a learnable weight entry. Compare now one of the node having degree d ∈ N, denoted as v 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 v. Therefore, by subtracting the mean computed across the channel dimension, as per Equation ( 6), we obtainH (1) b = ϕ NORM A b H (0) b W (0) 2 ; ℓ ,h (1) b,u,c = h (1) b,v,cfor all c ∈ [C]. This implies that it is not possible to 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 W (ℓ-1) 1= 0 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 u will still be equal to two times the vector of node features in v, a difference that is removed by the subtraction of the mean computed per node.In the main paper, we have additionally considered GRANOLA-NO-RNF, a variant of GRANOLA that does not sample RNF and instead uses only H(ℓ) b (Equation ( 11)) . In the following, we present an additional variant. 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 ZEQUATION)We refer to this variant of Equation ( 10) which uses the pre-defined mean and standard deviation functions in Equation ( 24) for fEQUATION2 as GRANOLA-MS, where MS stands indeed for mean and standard deviation. The idea behind GRANOLA-MS is to explicitly align the node-wise mean and variance of H(ℓ) b to match those of Z (ℓ)b . Note that, while GRANOLA-MS follows a predefined realization of f 1 and f 2 by using the mean and standard deviation, it is still a learnable normalization technique, as Z (ℓ) b is learned in Equation (8) . In Appendix H.8, we provide empirical comparisons with this specialized case.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 f norm be the architecture obtained by adding InstanceNorm or BatchNorm without affine parameters. Then f norm is strictly less expressive than f . Proof. All non-isomorphic graphs that can be distinguished by f norm can clearly be distinguished by f as the normalization only shifts and scale its input. To show that f 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, as shown in Cai et al. [11, Proposition 4.1] . 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 norm , concluding our proof.Proposition E.2 (MPNN with GRANOLA can implement MPNN with RNF). Let f norm be a stacking of MPNN layers interleaved with GRANOLA normalization layers (Equation (10)), followed by activation functions. There exists a choice of hyperparameters and weights such that f norm 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 byW (0) 1 = ( I I ) and W (0) 2 = 0, with I ∈ {0, 1} C×C . With these choices, H(1) b in Equation (1) becomes H(1) b = H (0) b ⊕ H (0) b = X b ⊕ X b .b 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 GNN (1) NORM to be the identity function and to properly set the weights of GNN 2 (Equation ( 9)) such that the normalization layer returnsH (0) b ⊕R (1) b , with R (1) b ∈ R N ×K and K chosen such that K = C. For example, if GNN (1)NORM is composed by a single GraphConv layer [41] (with an identity activation function), we haveEQUATION1EQUATION= (HEQUATION1EQUATION, then for GNN , where I ∈ {0, 1} C×C is the identity matrix. For fEQUATIONits is sufficient to set f to always return a zero vector, and f (1) 2 to be the identity function. With these choices, Equation (2) becomesH (1) = ϕ H (0) b ⊕ R (1) b = ϕ X b ⊕ R (1) b, 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, ℓ > 1, it is sufficient to set GNN (ℓ) NORM (Equation ( 8)) and f(ℓ) 1 , f (ℓ) 2(Equation ( 9)) to return its input H(ℓ) ∈ R N ×C (while discarding R 1 to always return a zero vector, andf (ℓ)2 to be the identity function. With these choices, Equation (10) becomesNORM( h(ℓ) b,n,c ; H(ℓ) , ℓ) = h(ℓ) b,n,c. Therefore, these two steps imply that an MPNN with GRANOLA implements an MPNN with RNF.Let Ω N be a compact set of graphs with N ∈ N nodes and g a continuous permutation-invariant graph function defined over Ω N . Let f norm 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 a continuous bounded distribution with zero mean and finite variance, for all ϵ, δ > 0, there exist a choice of hyperparameters and weights such that, ∀G = (A, X) ∈ Ω,EQUATIONwhere f norm (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(ℓ) b ∈ R N ×K bis drawn from a 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-RNF (Equation ( 11)) there exits a standard MPNN with the same expressive power.Proof. The proof follows by showing that an MPNN with GRANOLA-NO-RNF can be implemented by a standard MPNN (without any normalization), which therefore represents an 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-RNF are ReLU activation functions. Since the convolution layers are the same in both f norm and f , we are only left to show that an MPNN (without normalization, with ReLU activations) can implement a layer of GRANOLA-NO-RNF. Recall that a single GRANOLA layer can be written asEQUATIONand, since we are not considering RNF, Zb is obtained with Equation ( 11), recalling that GNNNORM is also composed by MPNN layers interleaved by ReLU activation functions per our assumption. We denote the number of layers of this GNN by L (ℓ)NORM . We next show how to obtain Equation ( 26) using multiple layers of an MPNN which takes as input H(ℓ) . We will denote intermediate layers of this MPNN as Ĥ(t) , t ≥ 1. NORM . Since we will later need also H(ℓ) b , we will use the last feature dimensions in every layer representation to simply copy it in every subsequent layer. Importantly, however, simply copying H(ℓ) b 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(ℓ) b and -H(ℓ) b in the last dimensions, and at the end recoverH(ℓ) b as H(ℓ) b = ϕ( H(ℓ) b ) -ϕ(- H(ℓ) b ), with ϕ the ReLU activation.For t = 1, the MPNN layer is simply responsible of replicating its input H(ℓ) b , so that we can later use the first C channels to obtain Z (ℓ) b and the last to later recoverH(ℓ) b . Therefore, Ĥ(1) b = ϕ( H(ℓ) b Ŵ(1) 1 + A b H(ℓ) b Ŵ(1) 2 )with Ŵ(1) 1 = ( I I -I ) and Ŵ(1) 2 = 0, with I ∈ {0, 1} C×C the identity matrix, and ϕ is the identity activation function. This means thatĤ(1) b = H(ℓ) b ⊕ H(ℓ) b ⊕ - H(ℓ) b . For t > 1 and t ≤ L (ℓ) NORM + 1, we need to mimic GNN (ℓ)NORM from Equation ( 11) on the first C dimensions. This is achievable byĤ(t+1) b = ϕ( Ĥ(t) b Ŵ(t) 1 + A b Ĥ(t) b Ŵ(t) 2 )with Ŵ(t) (ℓ) NORM + 1 layers, we have Ĥ(L (ℓ) NORM +1) b = Z (ℓ) b ⊕ ϕ( H(ℓ) b )⊕ϕ(- H(ℓ) b )We can then use an additional MPNN layer t to recover H(ℓ) b by settingEQUATION) 2 = 0, and obtainĤ(L (ℓ) NORM +2) b = Z (ℓ) b ⊕ H(ℓ) bFinally, we rely on the ability of MLPs to memorize a finite number of input-output pairs (see Yun et al. [68] and Yehudai et al. [65, Lemma B.2] ) to implement Equation ( 26) given its input. This is achieved by making the three subsequent layers of the MPNN behave as a 3-layer MLP (with ReLU activations) by simply zeroing out Ŵ(t) 2 . In this way, we have obtained Equation ( 26) through MPNN layers only.We implemented GRANOLA using Pytorch [50] (BSD-style license) and Pytorch-Geometric [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(ℓ) b,n , that is K is equal to C 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 Z (ℓ) b (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 non-linearities. Our normalization network is kept small and comprises a number of layers tuned in {1, 2, 3} and an embedding dimension that is the same as its input H(ℓ) . 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.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, we used a 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 to 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 an embedding dimension tuned in {32, 64}.We consider the scaffold splits proposed in Hu et 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 in {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.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.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 GNN NORM to compute intermediate (expressive) features, which are then used to calculate the normalization statistics, as shown in 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, GNNNORM 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 in the number of nodes |V | and edges |E|. Since a single GRANOLA layer is composed by L In practice, L NORM is a hyperparameter between 1 to 3 and can therefore be considered a 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 a Nvidia RTX-2080 GPU. For a 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, it is still a fraction of the cost of more complex methods like Subgraph GNNs (5.2× faster than efficient expressive models like Subgraph GNNs), while yielding favorable downstream performance. These results indicate that GRANOLA offers a strong tradeoff between performance and cost. In this subsection, we evaluate the performance of GRANOLA when coupled with additional backbones beyond GIN and GSN as presented in Section 5. Specifically, we evaluate its integration with GCN [37] , GAT [60] , and GPS [53] , using GRANOLA as the normalization layer. Table 5 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.As explained in Sections 3.1 and 4, in this paper, we chose to use RNF within GRANOLA. Incorporating 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 GNN NORM , as in GRANOLA-NO-RNF. This is because GRANOLA-NO-RNF is not more expressive than an 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 as GNN NORM 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 a Subgraph GNN, namely DS-GNN [4] , as the GNN NORM , instead of an MPNN + RNF. We denote this variant as GRANOLA-SubgraphGNN. Table 6 shows that GRANOLA-SubgraphGNN behaves similarly to GRANOLA. However, employing a SubgraphGNN as the GNN NORM results in additional complexity coming from the Subgraph GNN itself (which is quadratic rather than linear). Thus, while enhanced expressivity in GNN NORM does not require employing RNF specifically, using an MPNN + RNF provides the advantage of linear complexity. As discussed in Section 3, in Equation ( 10), µ b,n,c and σ b,n,c are the mean and std of H(ℓ) computed per node across the feature dimension, exactly as in LayerNorm-node. This choice was dictated by the fact that we found LayerNorm-node to offer consistent performance across different benchmarks. However, it is also possible to compute µ b,n,c and σ b,n,c across different dimensions, resulting in a variant of GRANOLA that builds on top of other normalization layers rather than LayerNorm-node. In Table 7 we study the effectiveness of the variant of GRANOLA that builds on top of BatchNorm. As can be seen from the table, GRANOLA-BatchNorm outperforms BatchNorm, further highlighting the role of graph adaptivity in normalizations.In our experiments in Section 5, the additional normalization GNN layer, GNN (ℓ) NORM , had unique parameters per layer, as evidenced by the superscript ℓ. In Table 8 , we show that by using the same GNNNORM for all ℓ, that is by sharing the weights across all layers, which overall requires less parameters, our GRANOLA continues to offer competitive results, further highlighting its competitiveness also in cases where parameter budget is low.To better understand the contribution of GRANOLA, we provide results where we set the normalization term in GRANOLA to zero, leaving only the bias term to be learned. That is achieved by setting γ (ℓ) b,n,c = 0 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 in Table 9 , indicate that the normalization term in GRANOLA is significant, and cannot be replaced by a simple bias.GRANOLA benefits from (i) enhanced expressiveness, and (ii) graph adaptivity. Property (i) is obtained by augmenting our normalization scheme with RNF, as shown in Figure 3 . Therefore, it is important to ensure that the contribution GRANOLA does not stem solely from the use of RNF, but rather the overall approach and design of our method.To this end, in 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 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 in our GRANOLA.As discussed in Section 3, our GRANOLA utilizes a GNN to learn graph-adaptive normalization shift and scaling parameters, and we denote this GNN by GNN b ), thereby losing graph adaptivity. In Table 11 , we provide results on a varying number of layers, from 0 to 4. Our results suggest that there is a significant importance in terms of performance to having graph adaptivity in the normalization technique, as offered by our GRANOLA.In the main paper, in Section 5, we focused on providing a comprehensive comparison with directly comparable methods, i.e., 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 as positional encoding methods and Subgraph GNNs. Our additional comparisons on ZINC-12K, OGB, and TUDatasets are provided in Table 12 , Table 13 , and Table 14 , respectively.It is important to note, that while some of these methods achieve better performance than our GRANOLA, they are not within the same complexity class as GRANOLA, and specifically, they are not linear with respect to the number of nodes and edges in the graph, as discussed in Appendix G. For example, RFP-QR-L, Â, S learn -DSS [22] , which also utilizes the expressive power of RNF, achieves an MAE of 0.1106 on ZINC-12K, while our GRANOLA achieves 0.1203. However, the former is of quadratic complexity with respect to the number of nodes, while GRANOLA is linear, as standard MPNNs. On the other hand, the linear and thus directly comparable RFP -ℓ 2 -L, Â achieves a higher (worse) MAE of 0.1368. Similarly, while there are Subgraph GNNs that can outperform GRANOLA, these are at least a quadratic in the number of nodes. Therefore, we find that our GRANOLA offers a practical yet powerful approach for utilizing RNF.Additionally, we observe that in some cases, GRANOLA achieves similar or 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] on all considered datasets, despite DSS being quadratic in the number of nodes.Table 12 : Additional comparisons of GRANOLA with various baselines on the ZINC-12K graph dataset. All methods obey to the 500k parameter budget.MPNNS GCN [37] 0.321±0.009 PNA [15] 0.133±0.011POSITIONAL ENCODING METHODS GIN + Laplacian PE [22] 0.1557±0.012 RFP -ℓ2 -L, Â [22] 0.1368±0.010 RWPE [20] 0.1279±0.005 RFP-QR-L, Â, S learn -DSS [22] 0.1106±0.012GSN [10] 0.101±0.010 CIN [8] 0.079±0.006HIGHER ORDER GNNS PPGN [40] 0.079±0.005 PPGN++ (6) [52] 0.071±0.001GPS [53] 0.070±0.004 GRAPHORMER [66] 0.122±0.006 GRAPHORMER-GD [70] 0.081±0.009NGNN [71] 0.111±0.003 DS-GNN (EGO+) [4] 0.105±0.003 DSS-GNN (EGO+) [4] 0.097±0.006 GNN-AK [73] 0.105±0.010 GNN-AK+ [73] 0.091±0.011 SUN (EGO+) [25] 0.084±0.002 GNN-SSWL [69] 0.082±0.003 GNN-SSWL+ [69] 0.070±0.005 DS-GNN (NM) [5] 0.087±0.003GIN + BatchNorm + RNF-PE [56] 0.1621±0.014 GIN + RNF-NORM 0.1562±0.013 STANDARD NORMALIZATION LAYERS GIN + BatchNorm [63] 0.1630±0.004 GIN + InstanceNorm [58] 0.2984±0.017 GIN + LayerNorm-node [3] 0.1649±0.009 GIN + LayerNorm-graph [3] 0.1609±0.014 GIN + Identity 0.2209±0.018GRAPH NORMALIZATION LAYERS GIN + PairNorm [72] 0.3519±0.008 GIN + MeanSubtractionNorm [64] 0.1632±0.021 GIN + DiffGroupNorm [74] 0.2705±0.024 GIN + NodeNorm [75] 0.2119±0.017 GIN + GraphNorm [11] 0.3104±0.012 GIN + GraphSizeNorm [21] 0.1931±0.016 GIN + SuperNorm [12] 0.1574±0.018 GIN + GRANOLA-NO-RNF 0.1497±0.008 GIN + GRANOLA-MS 0.1238±0.009 GIN + GRANOLA 0.1203±0.006 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 in 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 as long as it is clear that these goals are not attained by the paper.Justification: The research conforms with the code of ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).It is always possible to meet this assumption by padding to the max number of nodes.For simplicity and without loss of generality, we assume that the feature dimension of all GNN layers is C.The node degree is a fundamental feature in graph-based methods, see for example Newman[45].This assumption is included only to simplify the notation, but can be removed without affecting the results.Assuming the learned shift parameter in GraphNorm is not all zeros. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

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.
 
W3. (This is a minor point). Code is not provided.
questions: 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?

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?
limitations: limitations: Please refer to weakness and questions.
paper_summary: paper_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.
strength_weakness: strength_weakness: **Reservations regarding claims and the selected way to present findings**. 
- 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. 
- 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. 
- 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. 
- 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. 
- 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.

**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.

**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). 

**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.
questions: questions: - Have the authors tried to modify a different normalisation technique, apart from LayerNorm? This might be an interesting ablation study.
- Do the authors need a GNN normalisation network for each layer of the GNN processing network?
limitations: 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). 

I do not foresee any negative societal impact.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

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.
questions: 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: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: * 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.

* 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)?
questions: questions: See weaknesses
limitations: limitations: Yes

Comments: title: Recommendation
Official Review by Reviewer tP2u
Post-rebuttal follow-up (part 2)
Post-rebuttal follow up
Post-rebuttal
Rebuttal Follow-up
comment: My overall perspective on this work remains the same (lacking some level of maturity + unclear insights - see the review and post-rebuttal comments above). However, I acknowledge that the authors have made a substantial effort to deepen their evaluation of their work during the rebuttal period. Therefore I decided to increase my rating to 6 and anticipate that the manuscript will be revised according to the discussion with the reviewers.
Dear Reviewers,

We would like to extend our gratitude for your insightful and detailed reviews, as well as the post-rebuttal feedback and discussions. In our final version, we will include all the discussions and results presented in our rebuttal and follow-up discussions. 

With kindest regards,

The Authors.
Thank you for the detailed response. I raise the score to 6.
**Regarding GRANOLA as a practical way to utilize RNF:** We thank the Reviewer for the comment, which we fully agree with and discuss in our original submission (page 6, “Relation to expressive GNNs”). We made this discussion even clearer in the revision. 

We believe this additional perspective on our contribution (i.e., "improving GNNs with random features" rather than "designing effective GNN normalization schemes") strengthens our work rather than diminishes it. Multiple viewpoints often emerge in scientific research and tend to enrich the overall discussion.
**We thank the Reviewer for the discussion and the added comments.  We are also happy to read that the Reviewer finds our results convincing and deserving attention.**

**We would like to reply to your important comments one by one. We hope that you find them satisfactory, and we would like to receive your feedback. We implemented your comments and their follow-up discussions to the revised paper.**

***

**Regarding Subgraph-GNNs vs. GRANOLA:** The reviewer rightfully mentions that there are Subgraph-GNNs that can outperform GRANOLA, and this is also reflected in our results in Appendix in Tables 7, 8, and 9. **However**, it is important to note that our paper does not make claims about outperforming subgraph GNNs. Rather, it **focuses on GNNs with linear time complexity** 
Importantly, this experiment aims to demonstrate that effective graph normalization requires both **adaptivity** and **expressivity**. Our approaches achieve this combination using random features, which allows for implementation with linear time complexity.
Furthermore, please note that in the added  experiment following your questions, we used a DS-GNN [D1] with Ego-network subgraphs. This approach does not yield higher results on the tested datasets compared with our GRANOLA, as we show in the Table below:

| Method                  | ZINC-12k $\downarrow$ | OGBG-MOLHIV $\uparrow$ |
|-------------------------|-------------------------|--------------------------|
| DS-GNN (GIN) (Ego)      | 0.126±0.006             | 78.00±1.42               |
| GIN+GRANOLA-SubgraphGNN | **0.1186±0.008**            |  **78.62±1.31**               |


Therefore, it is important to note that, despite us not claiming that GRANOLA is meant to compete with subgraph GNNs, it does offer better performance than the core subgraph GNN used in our added experiment. We added this important discussion to our revised paper.

[D1] Bevilacqua et al., 2022. Equivariant Subgraph Aggregation Networks.

***


**Regarding expressivity vs adaptivity:** Thank you for the comment. We kindly note that in our paper, we highlight the discussion of the desire to have **both expressivity and adaptivity** several times, and we verify these claims by extensive experiments. 

*We now list the discussions on this in the paper:*

1. Lines 35-40: We mention that full adaptivity can be obtained by combining an adaptive normalization method with expressive backbone networks. 

2. Figure 3 (caption): we discuss that full adaptivity can be obtained by incorporating RNF.

3. Section 3.1: We dedicate this subsection to discuss the design choices made in GRANOLA, and **emphasize the need for both expressivity and adaptivity**.

4. Proposition 4.1 and Lines 226-234: We discuss the necessity of expressiveness in addition to adaptivity.

5. Lines 929-932: We state that “GRANOLA benefits from (i) enhanced expressiveness, and (ii) graph adaptivity.”, and elaborate on this point within these lines.

*In terms of experiments, we have extensively shown that:*

1. Adaptivity in itself improves the baseline results, as consistently shown by the variant called GRANOLA-NO-RNF.

2. Including RNF improves baselines results in many cases. (In particular the variants denoted by RNF-PE and RNF-NORM).

3. The combination of RNF and Adaptivity achieves the overall largest improvement compared to the baseline – this is our method GRANOLA.

For convenience, we also provide several key results from the paper that support our claims discussed above, and also mention whether each method is adaptive/expressive. As can be seen, all directions (adaptive/expressive) help to improve the baseline, and having both properties achieve the best performance among these variants.

| Method               | ZINC-12k $\downarrow$ | OGBG-MOLHIV $\uparrow$ | Adaptive | Expressive |
|----------------------|-----------------------|------------------------|----------|------------|
| GIN+BatchNorm        | 0.1630±0.004          | 75.58±1.40             | No       | No         |
| GIN+BatchNorm+RNF-PE | 0.1621±0.014          | 75.98±1.63             | No       | Yes        |
| GIN + RNF-NORM       | 0.1562±0.013          | 77.61±1.64             | No       | Yes        |
| GIN + GRANOLA-NO-RNF | 0.1497±0.008          | 77.09±1.49             | Yes      | No         |
| GIN + GRANOLA        | **0.1203±0.006**          | **78.98±1.17**             | **Yes**      | **Yes**        |

We understand that the Reviewer feels that this point might have not been stressed enough in the paper, and in our revised version we will ensure to further highlight it. We thank you for the invaluable guidance.
I thank the authors for their response and the additional experiments provided. As I mentioned in my initial review, combining adaptive normalisation with random features works well in practice, but Ι still find the underlying reasons behind this success unclear. 

The authors provided in their rebuttal an additional experiment, replacing random features with Subgraph-GNNs (as an alternative to boost the expressivity of the function computing the normalisation parameters) obtaining similar results. Although this hints that adaptive normalisation can be successful with any technique that improves expressivity, it triggers an additional question: should we credit success to extra expressivity or adaptive normalisation? At this point, it should be noted that, if I am not mistaken, using Subgraph-GNNs alone performs better than GIN+GRANOLA-SubgraphGNN.

In any case, the overall picture remains a bit blurry: the authors put significant focus during their presentation on the adaptive normalisation perspective of their approach, yet this works well only when combined with more expressive functions computing the normalisation parameters. However, this, in turn, might be outperformed by more expressive architectures alone. I agree with the argument that the latter is not the case for random features, which brings me back to my initial observation that the authors have found a way to exploit the theoretical advantages of random features (along with their linear complexity). However, the rest of the claims need further work to be made more convincing.

Overall, my reservations do not concern the method (the results are convincing), but rather the explanations/insights provided w.r.t. its behaviour. In other words, I think the paper deserves attention due to its empirical findings, but to some extent lacks maturity. Therefore, I will keep my initial score and recommendation.
Dear Reviewers,

We sincerely appreciate your valuable feedback in your reviews, and thank Reviewer **PwFk** for raising their score following our rebuttal.

**We have made dedicated efforts to address all concerns raised by all reviewers in our rebuttal.
We look forward to receiving feedback from Reviewers vndL, Ao3Y, and tP2u, and hope that you will consider raising your scores as well based on our responses. We are also happy to discuss additional questions or suggestions you may have.**


Thank you for your time and consideration.

Best regards,

The Authors.
Thanks for the authors' responses. I'll raise my score to 6