Graph Neural Networks Need Cluster-Normalize-Activate Modules
Authors: Arseny Skryagin
Felix Divo
Mohammad Amin Ali
Devendra Singh Dhami
Kristian Kersting
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Neural Networks
Deep Geometric Learning
Learnable Activation Functions
Oversmoothing
Primary area: graph_neural_networks
TL;DR: We propose Cluster-Normalize-Activate modules to improve expressivity of Graph Neural Networks.

Abstract: Graph Neural Networks (GNNs) are non-Euclidean deep learning models for graph-structured data. Despite their successful and diverse applications, oversmoothing prohibits deep architectures due to node features converging to a single fixed point. This severely limits their potential to solve complex tasks. To counteract this tendency, we propose a plug-and-play module consisting of three steps: Cluster→Normalize→Activate (CNA). By applying CNA modules, GNNs search and form super nodes in each layer, which are normalized and activated individually. We demonstrate in node classification and property prediction tasks that CNA significantly improves the accuracy over the state-of-the-art. Particularly, CNA reaches 94.18% and 95.75% accuracy on Cora and CiteSeer, respectively. It further benefits GNNs in regression tasks as well, reducing the mean squared error compared to all baselines. At the same time, GNNs with CNA require substantially fewer learnable parameters than competing architectures.

Graph Neural Networks Need Cluster-Normalize-Attiit Modules
Arseny Skryagin' Felix Divo'
Mohammad Amin Ali' Kristian Kersting!. 1.34.5
Devendra Singh Dhami
JAT MI. Group, TU Darmstadt 2TU Eindhoven
Hessian Center for AT (hessian.Al) German Research Center for Al (DFKI) *Centre for Cognitive Science, TU Darmstadt
skryagin,, felix. divo, kersting)@cs ieapriinnnnss..tddarmtttttteeeee tu-darmstadt.de ttw
amin. al @stud. tu-darmstadt. de d.s.dham Setaam@@tee.. nl
Abstract
Graph Neural Networks (GNNs) are non-Eucinne Son-Euulideen deep learning models for graph- structured data. Despite their successful and diverse applications, oversmoothing prohibits deep architectures due to node features converging to single fixed point. This severely limits their potential solve complex tasks. To counteract this tendency, we propose a plug-and-plas ter + Normalize - Activate (CNA). By applying CNA modules, GNNs search and form super nodes in each layer, which are normalized and activated individ- ually. We demonstrate in node classification and property prediction tasks that CNA significantly improves the accuracy over the state-of-the-arr Particularly, CNA reaches 94. 18% and 95.75% accuracy on Cora and CiteSeer, respectively. It further benefits GNNs in regression tasks well, reducing the mean squared error compared all baselines. the same time, GNNs with CNA require substantially fewer learnable parameters than competing architectures.
module consisting of three steps: Clus-
Introduction
Graph Neural Networks (GNNs) are promising ap- proach to leveraging the full extent of the geometric properties of various types of data in many different Bronstein et al.
Baseline
key domains [Zhou et al. 2020a
2021 Waikhom and Patgiri 2023
For instance, they are used to predict the stability of molecules Waag
al. 2023 aid in drug discovery [Askr al.
2023
Epoch
Epoch 50
Epoch 100
recommend new contacts in social networks (Zhang
CNA
and Chen 2018). identify weak points in electri-
cal power grids Nauck et al. 2002]]. predict traffic
volumes cities [Jang and Luo 2022 and much
more [Waikhom and Patgini 2023]. To solve such
tasks, one typically uses ressage-passingg GNNs, where information from nodes is propagated along outgoing edges to their neighbors, where it is aggre- gated and then projected by learned non-linear func- tion. Increasing the expressivity GNNs is crucial to learning more complex relationships and eventually improving their utility in a plethora of applications.
Epoch
Epoch 50
Epoch 100
Figure I: Evolution of node embeddings for the Cora dataset. The colors indicate membership of one of the seven target classes.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Bascline
Aggregate & Update
ReLU 7
CNA
Nomnliie
Aggregate, Update Cluster -
Act,
Act.
Nornallo
Acty
Novtiallee
Figure 2: CNA replaces the activation function in each iteration of any GNN architecture. When employing classical activations like ReLU to nodes undifferentiatedly.. we observe oversmoothing. With CNA, we cluster the node features and then normalize and project them with separate learned activation function each, effectively increasing their expressiveness even in deeper networks.
A natural approach to increasing expressivity is to increase depth, effectively enabling rurther-reaching and higher-level patterns to be captured. This combats neach-ne where information cannot propagate far enough. For example, this limits the effective radius of information on road crossings in traffic prediction tasks, where information on specific bottlenecks in road networks cannot propagate to the relevant k-hop neighbors. In practice, one wants increase the depth of the employed GNNs. However, this soon triggers phenomenon called oversmoothing, where node features are converging more and more to common fix-point with an increasing number of layers (NT and Maeharal 2019 Rusch et al. 2023a For example, in the specific task of node classification, node features different classes become increasingly overlapping and, thus, essentially indistinguishable. There many attempts to prevent this issue from occurring. Among them is Gradient-Gatine (G²), which gates updates to nodes once features start converging [Rusch et al. 2023b). However, G adaptively chokes message passing in each node right before oversmoothing can occur, effectively reducing the functionality of deeper GNN layers the flow of information in each node is still a very promising approach. But, instead of regulating adaptive node feature update. We argue that it crucial to ensure that while the node features are iteratively exchanged, aggregated, and projected, they stay sufficiently different from each other solve the eventual task, like classification regression. This has the benefit of maintaining effective information propagation even in deeper layers. Figure [ visualizes the final node features during training, showing how our method improves the separation of the learned classes over the oversmoothed baseline.
identity mapping. This idea of adaptively controlling
message passing, we propose learning
To ensure sufficiently distinct nodes, present Cluster Normalize Activate (CNA) modules specifically designed to improve the expressivity of GNNs:
Cluster Transformation of the node features should be shared and yet differ at the same time. For this reason, our first inductive bias is to assume several groups nodes with shared properties.
Normalize - Stabilization of training in deep architectures, including Transformers Vaswani et al. 2017], typically provided by normalization. By employing normalization, CNA effectively maintains beneficial numerical ranges and combats collapse tendencies.
Activate preserve distinct representations, the clusters must be transformed individually. By introducing learnable activation functions, we learn separate projections for each of them. This generalizes the typical affine transformation following the normalization to a general learned function that can better adjust the specific node features.
We use rational Activations MMoina et al. 2019 Delfosse et al., 2024 as powerful yet efficient point-wise non-linearities. The complete procedure is shown in Figure
Coode available httt:p///gttttooo.oo/arrereerrra

---

CNA modules can also be viewed as adding additional hierarchical structure to the problem: By grouping nodes into clusters of similar representations, we effectively introduce super-nodes with different non-linear activation functions. Each of their constituents shares the same activation function yet has distinct node property vectors and neighbors. Moreover, the node features in each super-node are less varied since the members of the clusters share some common characteristics. This divide- and-conquer approach breaks up the challenging task of transforming the node features into many smaller ones.
The presented work introduces the novel CNA modules which limit oversmoothing and thereby improve performance. They allow for many advancements, delivering better performance compared to the sante-of-the-ass in many tasks and datasets. In summary, we make the following contributions:
(i) We introduce the plug-and- and-alay play CNA modules for more expressive GNNs and motivate their construction.
(ii) We show that they empirically allow training much deeper GNNs.
(iii) Our experiments demonstrate the effectiveness of CNA in diverse node and graph-level classifi- cation, node-property prediction, and regression tasks.
(iv) Lastly, we show that architectures with CNA are parsimonious, achieving better performance than the state-of thrth-rrt with fewer parameters.
We proceed as follows: We next relate our work to the existing research on GNNs and their specific challenges (Section 2). We then describe and discuss our proposed solution CNA (Section (3) and conduct comprehensive evaluation in different scenarios (Section +. Finally, we conclude and suggest promising next steps for further improving the expressiveness of GNNs (Section 5
2 Related Work
Machine Learning on Graphs and its Challenges. Machine learning on graphs has long history,
with graph neural networks as their more recent incarnations Gori et al., 2005 [Scarselli et al.
2008 J. Since then, several new models like Graph Convolutional Networks (GCN) Kipp and Welling
2016), Graph Attention Networks (GAT) [Veličković et al.) 2018). and GraphSAGE [Hamilton ct al. 2017] have been proposed. Gilmer et al. [201]] then unified them into the Message Passing Neural Networks (MPNNs) framework, the most common type of GNNs (Battaglia et al. 2018) In addition to the typical machine learning pitfalls like overfitting and computationally demanding hyperparameter optimization, MPNNs pose some specific challenges: oversquasching is the effect of bottlenecks in the graph's 's topology, limiting the amount of information that can pass through specific nodes (Alon and Yahav 2020 Topping et al. 2021). The other widely studied challenge is oversmoothing, where the node features converge to a common fixed point with increasing depth of the MPNN [i al. 2018 NT and Machara 2019 Rusch et al.] 2023a This essentially equates to the layers performing low-pass filtering, which is harmful to solving the problem beyond some point. This phenomenon has also been studied in the context of Transformers [Vaswani et al. 2017)) where repeated self-attention acts similarly to an MPNN on fully connected graph [Shi et al. 2021a Different metrics have since been proposed to measure oversmoothing: cosine similarity, Dirichlet energy, and mean average distance (MAD). Rusch et al. [2023a] organize the existing mitigation approaches into three main groups. First, as discussed in more detail in the next paragraph, normalization and regularization are beneficial and are also performed by our CNA modules. Second, one can change the propagation dynamics, as done by GraphCON [McCallum et al. 22000, Gradient Gating RRusch et al., 2023b), and RevGNN [Li et al.) 2021). Finally, residual connections can alleviate some of the effects but cannot entirely overcome them. Solving these challenges is an open task in machine learning on graphs.
Normalization in Deep Learning. In almost all deep learning methods in the many subfields, normalizations have been studied extensively. They are used to improve the training characteristics of neural networks, making them faster to train and better at generalizing (Huang et al.) [2023]. The same applies to GNNs, where normalization plays a key role (Zhou et al., 2020a Cai et al. 2021 Chen et al.) 2022. Rusch et al. 2023a). However, selecting the correct reference group to normalize jointly is key. For example, a learnable grouping is employed in Deep Group Normalization (DGN), where normalization performed within each cluster separately [Zhou et al. 2020b). The employed soft clustering of DGN is only of limited suitability to fostering distinct representations of the node
3

---

Cluster
Normalize
Activate
Layer i-1
Layer
Figure 3: The components of CNA modules: They cluster node features without changing the adjacency matrix, normalize them separately, and finally activate with distinct learned functions.
features. Instead, we argue that simple hard clustering, for example, provided by the classic k-means algorithm, is sufficient and more desirable. Zhao and Akoglu (2020) suggest PairNorm, where
layerwise normalization ensures constant total pairwise squared distance of node features. Instead of adjusting the node features against collapse, Caso et al.) [2023) rewire the topology based on
clusters of node features. For the case of multi-graph datasets, Cai et al. [2021) provide a good overview of existing approaches, and argue that normalization shall be performed per graph.
Using non- non-polynomial activation functions is crucial for neural networks to be universal function approximators [Leshno et al.) 1993]. While most works use rectified-based functions like ReLU, GeLU, SiLU, etc., there are also attempts learning some limited shape parameters as in PReLU or Swish [Apicella et al. 202T There has since been further work learnable activations with reduced flexibility, namely LEAFS (Bodyanskiy and Kostiuk 2023]. a combination of polynomials and exponentials. However, one can even learn the overall shape of the activations, demonstrated by rational activation functions [Molina et al.) 2019 Boulle et al., 2020 TTrimmel et al. 2022]. They have proven to be very helpful in a diverse set of applications, particular, due their inherently high degree of plasticity during training (Delfosse et al. 2024
Learnable Activation Functions.
More importantly, rationals are smoothly differentiable universal function approximators Molina
al. 2019 Telgarsky 2017], for which reason we select them as flexible activation functions for CNA. Furthermore, changing the activation function has been found beneficial against oversmooting
by Kelesis al. (2023) too, which increased the slope of the classic ReLU activation reduce
oversmoothing in MPNNs. This further motivates taking a closer look at activations such as done by
Khalife and Basu 2024 and in this work.
3 Clsster-Normalie--Attiall Modules
This section will formally define CNA modules and discuss their design. Adaptive control of the information flow is promising approach to limit oversmoothing in GNNs. We, therefore, propose learning an adaptive node feature update, ensuring distinet node feature representations during the iterative exchange, aggregation, and projection. This benefits the maintenance of effective information propagation deeper layers. We start by introducing the notation used throughout this work, proceed to recall pessage-passing GNNs, and finally highlight the three main components of CNA. The overall module shown in Figure 3
Notation. We consider undirected graphs G = (V, E), where the edges & C V x V are unordered pairs {i.j} of nodes j E V. The set of neighbors of node V denoted as N, {j V]i E} C V. We additionally identify each node V with feature vector æ; Rd Together, these form the feature matrix X dx1 where each column represents the features of a single node. Similarly, depending on whether we model a node-level classification, property prediction, or regression task, we have corresponding target vectors y; E R with the special case of [V] vector for geaph-level. t = 1 for classification. The target matrix for all nodes is Y x
Message-Passing Neural Networks (MPNNs), The most prevalent type of GNNs are MPNNs, with GCN, GAT, and GraphSAGE as their best-known representatives. They iteratively transform
a graph by sequence of layers = dr.
Φ1, with Y Φ(G, X) (Zhou al. 2020a Lachaud et al. 2022 In cach layer f, two steps of computation are performed. First, the node

---

h, Aggregate( ((th |j M.))). Importantly, the Aggregate operation must be invariant to permutations of the neighbors. Popular choices include the point-wise summation or averaging of feature vectors across all neighbors of node. Second, these features h.") are projected jointly with the previous node features, as ( = Update(h ) The resulting node features h (++1) then form the input to the next layer. Both the Aggregate and the Update steps can be learned, where features h of the neighbors j E N, of each node E V are aggregated into single vector
the latter is often instantiated by Multi-layer Perceptrons (MLPs). Note that the features of the very first layer are simply the node features h2)) X, and the resulting last hidden representation our target output: (2) Y.
We propose improving the Update-step to elevate the effectiveness of the overall architecture. Usually, the learned projection ends with non-linear activation, like ReLU. Instead, propose performing the three steps of CNA, which we will outline below. We want to emphasize that our general recipe is applicable any MPNN following the above structure.
3.1 Step 1: Cluster
The node features of typical graph datasets can be clustered into groups of similar properties. In the case of classification problems, a reasonable clustering would at least partially recover class membership. Note that this unsupervised procedure does not require labels and is applicable to wide range of tasks. So, even in regression tasks, the target output for each node will usually differ; therefore, partitioning nodes into groups of similar patterns advantageous, too. We, therefore, cluster the nodes by their features Z; to obtain K groups ......, Cx at the end of each Update-step. This separation allows us to then normalize representations and learn activation functions that are specific to the characteristics of these subsets of nodes. It is important to note that the geometry, i.e., the arrangement of edges between nodes, does not change in the progression through GNN layers, while the features associated with each node do. Likewise, cluster membership does not necessarily indicate node adjacency and thus allows learning on heterophilic data as well. Note that this approach is, therefore, distinct from the graph partitioning often performed to shard processing of graphs based on its geometry [Chiang et al. 2019].
In principle, any clustering algorithm yielding a fixed number of clusters K can be used to group the node features. Popular choices include the classic k-means [MacQueen] [967] and Gaussian Mixture Model (GMM) algorithms [Bishop] [006]. which estimate spherical and elliptical clusters, respectively. However, we need to pay attention to the computational costs of such operations. Typical definitions of k-means run in ((V)d) per iteration [Manning et al. 2009] Expectation- maximization can be used to learn GMM clusters in ((V]Kd" df) per iteration Moore 1998]. We found that the more expensive execution of GMMs did not materialize in substantial improvements in downstream tasks. We, therefore, opted to use a fast implementation of k-means. This confirms that k-means often provides decent clustering in practical settings and is sufficiently stable (Ben-David et al., 2007]. In our work, we compared nodes by their Euclidean distance, which we found to work reliably in our experiments. However, CNA permits the flexible use of different and even comain-specifit data distances.
3.2 Step 2: Normalize
To ensure even scaling of the data across layers, we perform normalization per cluster C₁ and per feature j across all nodes E Cs separately:
Fig
Fig
pkj
μkj
Tpj.
t
(xip - 12z))
(1)
CC
C&
RJ
+E
PEC₂
PEC
where is introduced for numerical stability. We want to emphasize that this step similar to Instance Normalization, yet is nonparametric and does not apply the usual affine transformation to restore the unique cluster representation (Huang et al. 2023). Similarly, is not required to scale the mean we subtract as in GraphNorm (Cai et al. 2021]. Instead, we learn much more powerful transformation in the subsequent Activate step, which subsumes the expressivity of a normal affine projection and thus renders it redundant. The idea of normalizing per cluster Cs is related to GraphNorm. However, instead of normalizing per graph in the batch, we propose normalizing per cluster within each graph, yet with the same motivation of maintaining the expressivity of the individual node features.
5

---

3.3 Step 3: Activate
Using an element-wise non- con-polynomial activation function crucial for MLPs be universal function approximators (Leshno et al., 1993]. To maintain distinct representations of node features at large depths. we employ learnable activation functions. Specifically, we use rational activations [Molina et al. 2019 of degree (m, n):
P(z) R(x) ((x) 1+ k= b
k ag.
Their purpose is twofold: Firstly, they act as non-polynomial element-wise projections to increase the representational power of the model. Secondly, they replace and subsume the affine transformation in the typical Instance Normalization formulation. Additionally, their strong adaptability allows for appropriate learnable adjustments in the dynamic learning of deep neural networks. This is in line with the findings of Kelesis et al. [2023], who increased the slope of ReLU activations to combat overfitting. Our rationals subsume their approach by further lifting restrictions on the activation function and tuning the slopes automatically while learning the network.
Removing activation functions from GNN layers altogether can surprisingly-impieeee overall per- formance due to reduced oversmoothing (Wu et al., 2019). Our CNA modules limit oversmoothing further, maintaining strong representational power even in deeper networks. We will demonstrate this in the next section.
3.4 Theoretical Underpinnings
We first show how previous proofs of the necessary occurrence of oversmoothing in vanilla GNNs are not applicable when CNA is used. Next, we explain why these proofs are not easily reinstated by illustrating how CNA breaks free of the oversmoothing curse.
Previous Theoretical Frameworks The Rational activations of CNA trivially break the assump- tions of many formalisms due to their potential unboundedness and not being Lipschitz continuous. This includes Prop. 3.1 of Rusch et al. [2023b], where, however, the core proofs on oversmoothing are deferred to Rusch et al. [022]]. Again, the activation is assumed to be point-wise and further narrowed to ReLU in the proof in Appendix C.3. Regarding the more recent work of Nguyen et al. [202]] we again note that CNA violates the assumptions neatly discussed in Appendix A. The CNA module can either be modeled as part of the message function th or as part of the aggregation c However, in both cases, the proof of Prop. 4.3 (which is restricted to regular graphs) breaks down. In the former case, there appears to be no immediate way to repair the proof of Eq. (15) in Appendix C.3. In the latter case, providing upper bounds in Appendix C.2 is much more difficult.
How CNA Escapes Oversmoothing Restoring the proofs for the occurence of oversmoothing is difficult because CNA was built precisely to break free of the current limitations of GNNs. This can be seen by considering two possible extremes that arise as special cases of CNA. Consider a graph with N nodes. On end of the spectrum, we can consider CNA with K N clusters and Rationals that approximate some common, fixed activation, such as ReLUU. This renders the normalization step ineffective and exactly recovers the standard MPNN architecture, which is known to be doomed to oversmooth under reasonable assumptions [Rusch et al.) 2022 Nguyen et al. 2023) The same holds with only a single cluster (K 1), i.e., MPNNs with global normalization [Zhou et al., 20206]. Conversely, we can consider K N clusters, but now with fixed distinct Rational activations given by (x) for each cluster E 1, ..... N. The Dirichlet energy of that output constant, lower- bounde,, and, therefore, does not vanish, no matter the number of layers. In practice, we employ, course, between K one and K N clusters and thereby trade off the degree to which the GNN is affected by oversmoothing. The following section will investigate this and other questions empirically.

---

GNA- (lisar)
GUN
GrppSAGG (llace))
Crunfonttrr (linca)
GAT
GCN
GraphSAGG
Trandomeeeoo
Cura
ClicSeer
100%
100%
80%
805
Accuncy
60%
60%
40%-
40%
20%
27%
07%
Figure CNA limits oversmoothing and improves the performance of deep GNNs.
4 Experiments
To evaluate the effectiveness of CNA with GNNs, we aim to answer the following research questions:
(Q1) Does CNA limit oversmoothing?
(Q2) Does CNA improve the performance in node classification, node regression, and graph classifi- cation tasks?
(Q3) Can CNA allow for having fewer parameters while maintaining strong performance when scaling very large graphs?
(Q4) Model Analysis: How important are each of the three steps in CNA? How do hyperparameters affect the results?
Setup. We implemented CNA based on PyTorch Geometric (Fey and Lenssen 2019 to answer the above questions. We searched for suitable architectures among Graph Convolutional Network (GCN) (Kipf and Welling 2016). Graph Attention Network (GAT) (Veličković et al. 2018 Sam- ple and Aggregate (GraphSAGE) [Hamilton al. 2017). Transformer Convolution (Transformer- Conv) (Shi et al. [2021b] and Directional GCN (Dir-GNN) [Rossi et al.) [023]. They offer diverse approaches to information aggregation and propagation within graph data, catering to wide range of application domains and addressing specific challenges inherent to graph-based tasks. Details on the choice of hyperparameters and training settings are provided Appendix [A.2] Average performances and standard deviations are over 5 seeds used for model initialization for all results, except for Tables I and 6 where we used 20.
Since the phenomenon occurs only within deep GNNs, we systematically increased the number of layers in node classification. We mainly compare vanilla GNNs with ReLU to GNNs with CNA. To complete the analysis, we also consider linearized GNNs without any activation function, since they were found to be more resilient against oversmoothing at the expense of slightly reduced performance (Wu et al. 2019). Figure([shows the resulting accuracies for depths of to 96. We can confirm the strong deterioration of vaniTla GNNs at greater depths and the partial resilience of linearized GNNs. On the other hand, CNA modules limit oversmoothing drastically and are even more effective than linearized models. At the same time, they significantly alleviate the model's performance shortcomings, effectively eliminating the practical relevance of oversmoothing.
(Q1) Limiting Oversmoothing.
(Q2) Node Classification, Node Regression, and Graph Classification. We evaluated CNA by incorporating into existing architectures and compared the resulting performances with the unmodified variants. As the results in Table demonstrate, our CNA modules significantly improve classification performance on the Cora dataset [MeCallum et al.) 2000 by up to 13.53 percentage points. Moreover, this improvement shows across different architectures, highlighting CNA's ver- satility. Next, we extend our analysis to many more datasets and compare CNA to the best-known models from the literature. Specifically, we evaluate the performance on the following datasets: Cora,
7

---

Model Table 1: CNA consistently increases the
curacy (f) of each architecture on Cora.
Table CNA reduces the NMSE ()) on two
Architecture
Baseline
CNA
multiscale node regression datasets.
GCN
81.5910.43
93.66:10.48
GraphSAGE
80.58+0049
93.68++0.50
Chameleon
Squirrel
TransformerConv
79.97=0.78
93.50=0.558 92.94-0.771
GCN
0.207
0.143:10.039
GAT
80.57+0.81
GAT
0.207=000038
0.143:10.039
PairNorm
0.207=-0.038
0.140=10.040
Table 2: CNA systematically improves graph classification accuracy (f).
GCNII
0.170=#0.034
0.093=0.031
G2-GCN
0.137=0.033
0.070:100028
G²-GAT
0.136:10.029
0.069110.029
Graph Dataset
Baseline
CNA
Trans.
0.133+00033
0.072:10.025
Trans.Com++CNA 0.131+00.033 0.068:10.027
Mutag
78.4246.55 36.9713.08
81.60-
Enzymes
30.00-3.225
Proteins
72.72.12.60
24.44
Table 4: Comparison of our method CNA with the leaderboard on Papers with Code (PwC) as of writing diverse set of node classification datasets from five typical collections. CNA outper- forms the respective leaders, and thereby all compared methods, in eight out of eleven cases (73%). For some, it does by significant margin, e.g., on the popular Cora and CiteSeer datasets.
Best CNA Result
PwC Leaderboard
Dataset
Architecture
Accuracy (f)
Architecture
Accuracy (f)
Chameleon
Dir-GNN GAT
85.86:11.80
DJ-GNN [egga et al
2023
80.48
CiteSeer
95.75:10.58
ACMII- SCMIl-Snowball-22 Luan et al. 2022
82.07 1.04
Computers
TransformerConv
92.68-10.27
Exphormer (Shirzad
91.4711.11
Cora
Gra
94.18-10.33
SSP [Zad] 2202
90.16:10.59
CoraFull
TransformerComv
71.82++-0.25
DoLtnnDist Luo ef al. 2021
70.32
DBLP
GCN
86.90-10.45
GRACE 7hhu ct al. 2020
84.2++0.1
Photo
TransformerCom-
95.96+00.29
CGT (Hoang and Lee 2023
95.73
Pubmed
TransformerConv
90.16.10.13
ACM-Smowball-3 Luan el
2022
91.44.1..59
Squirrel
Dir-GNN
77.4711.22
Dir-GNN Rossi al. 202.3
75.31
Texas
GraphSAGE
90.00.13.65
2-HiGGN Huang el al
2024
92.45.1.733
Wisconsin
TransformerConv
89.29+2.26
5-HiGCN Huang ct al.
2024
94.99
#Wins
8/11
3/11
CoraFull Kipf and Welling 2016). CiteSeer [Bojchevski and Günnemann, 2018 PubMed (Sen et al. 2008). DBLP [Tagg et al. 2008], Computers and Photo [Shchur et al.) [019]. Chameleon, Squirrel, Texas, and Wisconsin Pei et al. 2020). The results in Table 4 demonstrate the effectiveness CNA. Out of 11 of those datasets, CNA outperforms the SOTA 8 of them. In particular, for CiteSeer, CNA achieves a classification accuracy of 95.75% compared to 82.07% for ACMII-Snowball-2 This suggests that CNA is particularly effective in dealing with the imbalanced class distribution in CiteSeer. The application of CNA is successful on the famous Cora dataset, achieving 94.18% accuracy compared to the 90.16% of SSP. Considering the results in relation the dataset properties listed in Appendix I we can see that CNA is particularly effective on larger datasets and such ones with many features. It largely unaffected by the usually detrimental degree of heterophily and the number of classes due to the clustering step being mostly independent of them.
Table 3 displays the comparison in performance in multi-scale node regression task as considered by Rusch et al. (2023b on the Chameleon and Squirrel datasets [Rozemberczki et al. 2021]. Here, multi-scale refers to the wide range of regression targets from 10 to 1. CNA modules consistently outperform alternative methods in terms of normalized mean squared error (NMSE) based upon the ten pre-defined splits by Pei al. 2020). This superior performance highlights the effectiveness of

---

Table 5 & Figure 5: CNA allows for (i) compact and (ii) accurate models: The separate treatment
of super-nodes boosts expressivity, making GNNs more compact.
Model
Accuracy
Params
GraphSAGE
59.97
34.8k
75
GCN
1..66+00.77
388k
GraphSAGE
71.49:10.27
219K
GENICNA
GCN
71.74:10.29
143k
(i) GraphSAGE=CNA
71.79::0.00
34,9k
Acsuner
DAGNN
72.09.10.25
43.9K
DeeperGCN
72.32:10.27
49
GCNII
72.74.10.16
72
RevGCN-Desp
73.01
262k
73.91+0.12
144M
GuAA&AGE-CAA
UniMP
73.97=0.15
687K
71
Wide
74.05 1:0.11
3.85M
RevGAT-
74.26110.17
2.10M
4.5
5.0
5.5
6.0
6.5
GCN+CNA
74.64:10.13
Compact
log y (parameters)
Colossal
Reproduced by ourselves with same hyperpurameters as and Other buselines taken from the literature.
approach in handling the complexities of node-level regression tasks. These results suggest that our approach has the potential to provide more accurate predictions in real-world scenarios.
To go beyond node-wise tasks on single graphs, we continue by evaluating CNA on graph- classification tasks. Namely, we compared CNA with ReLU on the Mutag (Debnath et al., 1991]. Enzymes [Borgwardt et al. 2005], and Proteins (Borgwardt et al. 2005] datasets from the Tataaset collection Morris al. [2020]. Table demonstrates that CNA boosts performance unanimously; for instance, achieving impressive improvement of 13 percentage points on Enzymes.
further comparison of CNA to other graph normalization techniques is provided in Appendix A.3 Summarizing the findings on node classification, node regression, and graph classification bench- marks, we can confidently answer (Q2) affirmatively.
(Q3) Parameter Parsimony. CNA creates super-nodes in graphs, each rescaled separately and governed by individual learnable activation function. This increased specificity and, in turn, expressivity might allow for more compact models. To investigate this, we use the ogbn-arxiv dataset from the Open Graph Benchmark (OGB) [Hu et al. 2020) and follow the setup of ei al. (021] We compare GNNs equipped with CNA to a set of baselines without it. The results in Table 5 first of all, clearly show how CNA outperforms range of existing GNN models (ii). It achieves test accuracy of 74.64% while estimating a modest number of learnable parameters (389.2k). This indicates that CNA can successfully capture the underlying patterns in the graph data while maintaining computationally efficient model. The baselines have varying levels of complexity, with some having more layers and/or channels per layer than others. However, CNA outperforms all competitors, even those with more complex architectures. Figure 5 shows that architectures coming close to the performance of CNA need far more parameters that require learning by gradient descent. Namely, improving GraphSAGE + CNA by 2.47 percentage points (the difference to RevGAT-SelfKDD results in model about 60x bigger. Similarly, the 2.85 percentage point improvement from GraphSAGE + CNA to GCN CNA is achieved with a model only about eleven times larger. Additional data, such as the underlying abstract texts originally used to generate the citation graph node features, has recently been used with LLMS to distill additional context (He et al.) 2023 Duan et al. 2023). We exclude them to maintain a level playing field, yet recognize it as an interesting avenue for future work. We argue that CNA modules pave the way for a desirable development of GNN modeling when increasing expressivity would not require an explosion in the number of learnable parameters.
(Q4) Model Analysis. We assess the contribution of each of the three operations Cluster, Normalize, and Activate. To this end, we tested GCN with different subsets of the three operations on the Cora dataset. Table demonnstraes that dropping even one of the operations results in minor or no improvement over the plain architecture using ReLU as activation. Cluster-Normalize already improves over the baseline, confirming the findings of Zhou et al. (2220)) To assess the sensitivity of CNA to the choice its hyperparameters, we compared the effect of the number of hidden features
and the number of clusters per layer the Cora dataset using GCN, as shown in Figure 6 We

---

Table 6: Ablation Study measured in accu- racy (f) on two datasets.
Cluster Normalize Activate
obgn arxiv
81.59:1043
69.65:10.19
81.25::0:64
69.65:1:.19
03.02:+0.36
69:47::0.36
81.64:00661
69:42::0.155
120
01.59
69.36:t00133
01.60:00772
69.66:1:0.11
Aneaonryy
81.60:00700
69:42:::0.13
93.66110.48
74.16::0.33
Figure 6: Hyperparameter sensitivity analysis.
find that CNA is very robust to the choice of these hyperparameters and works best with moderate numbers of features, as the results from (Q3) would suggest. Answering (Q4), we observed that all three operations of CNA are necessary for the method's efficacy, and it permits practitioners to choose hyperparameters flexibly.
Conclusions
In this work, proposed Claste--oomalize-Attiiaa modules drop-in method to improve the Update step in GNN training. The experimental results demonstrated the effectiveness of CNA modules in various classification, node-property prediction, and regression tasks. Furthermore, we found it to beneficial across many different GNN architectures. CNA permits more compact models on similar or higher performance levels. Although CNA does not entirely prevent oversmoothing, does considerably limit its effects in deeper GNNs. Our ablation studies have shown that each step in CNA contributes to the overall efficacy and its overall robustness. CNA provides a simple yet effective way to improve the performance of GNNs, enabling their use in more challenging applications, such traffic volume prediction, energy grid modeling, and drug design.
Limitations. We focused our evaluation on very popular architectures and datasets. While is likely that CNA is beneficial in many other configurations, we did not evaluate its effects GNNs that are not convolutional MPNNs. Similarly, while we did scale or method to the ogbn-arxiv dataset with about 169k nodes and more than a million edges, yet larger datasets might require further work on the speed of the clustering procedure. Our experiments suggest that oversmoothing is of limited practical relevance. Yet, did not scale this investigation to even greater depth or establish formal link to existing theories for oversmoothing.
Future Work. The presented results motivate further enhancing CNA in multiple ways. Notably, there are three possible directions. Firstly, regarding clustering, we investigated k-means and GMMs, yet it is important to consider other algorithms. For example, Differentiable Group Normaliza- tion [Zhou et al. 2020bb a promising direction for introducing learnable clustering step. Further, clustering algorithms need not only to yield fixed number of clusters A;, but should also produce equally sized clusters. Beyond discovering more stable super nodes, this is likely to improve well. Apart from representational power, investigating faster
learning of the rational projections clustering procedures paves the way toward scaling GNNs via CNA to dynamic and continuous training settings. Secondly, even more potential for improvement lies in combining CNA with other techniques. For example, representing the Aggregate step as learnable sequence models [Hamilton) et al.) 2017]. These can be beneficial to distill local information to a greater degree, which in turn could further improve performance and limit oversmoothing. Also, combining CNA with established methods like Edge Dropout or Global Pooling can yield compounding benefits. Finally, the abstract idea behind CNA, namely grouping representations and performing distinct updates, is more general concept and applicable beyond the architectures
have considered in this work. For instance, Transformers [Vaswani et al. 2017] are known to be equivalent to MPNNs on fully connected graphs and can similarly exhibit oversmoothing (Shi et al. [2021a], motivating closer look at this connec- tion. Unifying the theory about the different clustering- based normalization approaches and their effect on expressivity and phenomena such as oversmoothing might uncover further opportunities for improvements.
10

---

Acknowledgments and Disclosure of Funding
This research project was funded by the ACATIS Investment KVG mbH project "Temporal Machine Learning for Long-Term Value Investing" and the German Federal Ministry of Education and Research (BMBF) project KompAKI within the "The Future of Value Creation - Research on Production, Services and Work" program (funding number 02L19C150) 50) managed by the Project Management Agency Karlsruhe (PTKA). The Eindhoven University of Technology authors received support from their Department of Mathematics and Computer Science and the Eindhoven Artificial Intelligence Systems Institute. Authors thank Ponturo Consulting AG for their support.
References
Uri Alon and Eran Yahav. On the Bottleneck of Graph Neural Networks and its Practical Implications. In The Ninth International Conference on Learning Representations, 2020.
Andrea Apicella, Francesco Donnarumma, Francesco Isgrò, and Roberto Prevete. A survey on modern trainable activation functions. Neural Networks, 138:14-32, June 2021. doi: 10.1016/j. neunet. 1.0.0..........
Heba Askr, Enas Elgeldawi. Heba Aboul Ella. Yaseen M. M. Elshaier, Mamdouh M. Gomaa, and Aboul Ella Hassanien. Deep learning in drug discovery: an integrative review and future challenges. Artificial Intelligence Review, 56:5975-600 6037, July 2023. doi: 10.1007/114422--022 1
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre, Francis Song, Andrew Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks, October 2018. http:http//axiiii awrg/bbs/8000 01261
Ahmed Begga, Francisco Escolano, Miguel Angel Lozano, and Edwin R. Hancock. Diffusion-Jump GNNs: Homophiliation via Learnable Metric Filters, June 2023. URL http:///a/aaxi www.:y.rg/gbgo /bs//
2306. 16976
Shai Ben-David, Dávid Pál, and Hans Ulrich Simon. Stability of k-Means Clustering, In Nader H. Bshouty and Claudio Gentile, editors, Learning Theory, pages 20-34, Berlin, Heidelberg, 2007. Springer. ISBN 978-3-540-72927-33 doi: 10. 12.1007/978-3-540- 5-4----------777334444443 72927-3_4.
Christopher M. Bishop. Pattern recognition and machine learning. Springer, 2006.
Yevgeniy Bodyanskiy and Serhii Kostiuk. Learnable Extended Activation Function for Deep Neural Networks. International Journal of Computing, 22(3), October 2023. doi: 10.47839/ij..22.3. 22..3332222..32225..
Aleksandar Bojchevski and Stephan Günnemann. Deep Gaussian Embedding of Graphs: Unsu- pervised Inductive Learning via Ranking. In The Sixth International Conference on Learning Representations, 2018
Karsten M. Borgwardt, Cheng Soon Ong. Stefan Schönauer, S. V. N. Vishwanathan, Alex J. Smola, and Mate- Kriegel. Protein function prediction via graph kernels. Bioinformatics (Oxford, England), 21 Suppl 1:i47-56, June 2005. ISSN 1367-4803. doi: 10. (093/bioinformatic//hii
1007. 1007.
Nicolas Boulle, Yuji Nakatsukasa, and Alex Townsend. Rational neural networks. Advances in Neural Information Processing Systems, 2020.
Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges, May 2021. URL httpp:/aaxxiv.or org/ abs/ 2104.134788
Tianle Cai, Shengjie Luo, Keyulu Xu, Di He, Yan Liu, and Liwei Wang. GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training. In Proceedings of the 38th International Conference Machine Learning, 2021. ISSN: 2640-3498.

---

Francesco Caso, Giovanni Trappolini. Andrea Bacciu, Pietro Liò, and Fabrizio Silvestri. Renormal- ized Graph Neural Networks, June 2023.
Yihao Chen, Xin Tang, Xianbiao Qi, Chun-Guang Li, and Rong Xiao. Learning graph normalization for graph neural networks. Neurocomputing, 493:613-625, July 2022. ISSN 0925-2312.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-GNN) An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, July 2019.
Asim Kumar Debnath, Rosa L. Lopez de Compadre, Gargi Debnath, Alan J. Shusterman, and Corwin Hansch. Structure-activity relationship mutagenic aromatic and heteroaromatic nitro compounds. Correlation with molecular orbital energies and hydrophobicity. Journal of Medicinal Chemistry, 34(2):786-777, February 1991. ISSN 0022-2623. doi: 10. 0..101//m000106044.
Quentin Delfosse, Patrick Schramowski, Martin Mundt, Alejandro Molina, and Kristian Kersting, Adaptive Rational Activations to Boost Deep Reinforcement Learning. In The Twelfth International Conference on Learning Representations, 2024.
Keyu Duan, Qian Liu, Tat-Seng Chua, Shuicheng Yan, Wei Tsang Ooi, Qizhe Xie, and Junxian He. SimTeG: A Frustratingly Simple Approach Improves Textual Graph Learning, August 2023, URL fttp://arxiv .rg 2308 02565
Matthias Fey and Jan Eric Lenssen. Fast Graph Representation Learning with PyTorch Geometric. In Representation Learning on Graphs and Manifolds, 2019.
Justin Gilmer, Samuel S. Schoenholz, Patrick F, Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for Quantum chemistry. In Proceedings of the 34th International Conference Machine Learning, volume 70, August 2017.
M. Gori, Monfardini, and F. Scarselli. A new model for learning in graph domains. In IEEE International Joint Conference on Neural Networks, 2005.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive Representation Learning on Large Graphs. In Advances Neural Information Processing Systems, 2017.
Xiaoxin He, Xavier Bresson, Thomas Laurent, Adam Perold, Yann LeCun, and Bryan Hooi. Harness- ing Explanations: LLM-to-LM Interpreter for Enhanced Text-Attribttdd Graph Representation Learning. In The Twelfth International Conference on Learning Representations, 2023.
Van Thuy Hoang and O.-Joun Lee. Mitigating Degree Biases in Message Passing Mechanism by Utilizing Community Structures, December 2023. URL http:////axxvvv.rrreeee 2312
16788
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open Graph Benchmark: Datasets for Machine Learning on Graphs. In Advances in Neural Information Processing Systems, 2020.
Lei Huang, Jie Qin, Yi Zhou, Fan Zhu, Li Liu, and Ling Shao. Normalization Techniques in Training DNNs: Methodology, Analysis and Application. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(8):10173 - 10196, August 2023. doi: 10. 10.1109/TA 3250024..
Yiming Huang, Yujie Zeng, Qiang Wu, and Linyuan Lü. Higher-order Graph Convolutional Network with Flower-Petals Laplacians Simplicial Complexes. In The Thirty-Eighth AAAI Conference on Artificial Intelligence, January 2024.
Sergey loffe and Christian Szegedy. Batch normalization: accelcrating deep network training by reducing internal covariate shift. In Proceedings of the 32nd International Conference on International Conference on Machine Learning Volume 37, ICML 15, pages 448-456, Lille, France, July 2015. JMLR.org.
Mohammad Rasool Izadi, Yihao Fang, Robert Stevenson, and Lizhen Lin. Optimization of Graph Neural Networks with Natural Gradient Descent. In Proceedings of the IEEE International Conference Big Data (Big Data), 2020.
12

---

Weiwei Jiang and Jiayun Luo. Graph neural network for traffic forecasting: A survey. Expert Systems with Applications, 207, November 2022. doi: 10.1016gjeesaa2222.11999
Dimitrios Kelesis, Dimitrios Vogiatzis, Georgios Katsimpras, Dimitris Fotakis, and Georgios Paliouras. Reducing Oversmoothing in Graph Neural Networks by Changing the Activation Func- tion. In Kobi Gal, Ann Nowé, Grzegorz J. Nalepa, Roy Fairstein, and Roxana Rádulescu, editors, 26th European Conference on Artificial Intelligence ECAI 2023, 2023. doi: 10.3233/FAAA2304000
Sammy Khalife and Amitabh Basu. On the power of graph neural networks and the role of the activation function, May 2024.
Thomas N. Kipf and Max Welling. Sumi--Sperviied Classification with Graph Convolutional Networks. In 5th International Conference on Learning Representations, 2016.
Guillaume Lachaud, Patricia Conde- Cespedees and Maria Trocan. Mathematical Expressiveness of Graph Neural Networks. Mathematics. Mathematical Foundations of Deep Neural Networks, 10 (24):4770, January 2022. doi: 10.3390/math httpmmattht1444777 10244770.
Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with nonpolynomial activation function can approximate any function. Neural Networks, 6(6):861-867, January 1993. doi: 1011016650033300000055000133555
Guohao Li, Matthias Müller, Bernard Ghanem, and Vladlen Koltun. Training Graph Neural Networks with 1000 Layers. In Proceedings of the 38th International Conference on Machine Learning, 2021.
Qimai Li, Zhichao Han, and Xiao-ming Wu. Deeper Insights Into Graph Convolutional Networks for Semi- Suni--Spervised Learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32 of 1, April 2018. doi: 10.1609/aaai, v32il. 11604.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao- Xiao-Wen Chang, and Doina Precup. Revisiting Heterophily For Graph Neural Networks. Advances in Neural Information Processing Systems, 35: 1362-1375, December 2022.
Yi Luo, Aiguo Chen, Ke Yan, and Ling Tian. Distilling Self- Solf-Knowledge From Contrastive Links to Classify Graph Nodes Without Passing Messages, June 2021. URL http://arxiv. wwwpiiiioor//baaaa 2106.08541
J. MacQueen. Some methods for classification and analysis of multivariate observations. Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, 1, 1967.
Christopher Manning, Prabhakar Raghavan, and Hinrich Schuetze. Introduction to Information Retrieval. Cambridge University Press, 2009.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the Construction of Internet Portals with Machine Learning. Information Retrieval, 3:127-163, July 2000. doi: 10.1/// 11100//::110955::: 0009953814983
Alejandro Molina, Patrick Schramowski, and Kristian Kersting. Padé Activation Units: End-to- end Learning of Flcxible Activation Functions in Deep Networks. In The Eighth International Conference Learning Representations, 2019.
Andrew Moore. Very Fast EM-Based Mixture Model Clustering Using Multiresolution Kd-Trees. In Advances in Neural Information Processing Systems, 1998.
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. TUDataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop Graph Representation Learning and Beyond (GRL+ 2020), 2020. URL www. www. ww..graalaaainng.ooo.
Christian Nauck, Michael Lindner, Konstantin Schürholt, Haoming Zhang, Paul Schultz, Jürgen Kurths, Ingrid Isenhardt, and Frank Hellmann. Predicting basin stability of power grids using graph neural networks. New Journal of Physics, 24, April 2022. doi: 10. 10.11888/1367-2633/ccc///
13

---

Khang Nguyen. Hieu Nong, Vinh Nguyen, Nhat Ho, Stanley Osher, and Tan Nguyen. Revisiting over-smoothing and over-squashing using ollivier-ricii curvature. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of ICMIL'23, pages 25956-25979, Honolulu, Hawaii, USA, July 2023. orr.
Hoang NT and Takanori Maehara. Revisiting Graph Neural Networks: All We Have Low-Pass Filters, May 2019. URL http:://tas::i org/abs/ abss/195. 09550
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-GCN: Ge- ometric Graph Convolutional Networks. In The Eighth International Conference on Learning Representations. arXiv, February 2020.
Emanuele Rossi, Bertrand Charpentier, Francesco Di Giovanni, Fabrizio Frasca, Stephan Günnemann, and Michael Bronstein. Edge Directionality Improves Learning on Heterophilic Graphs, November 2023. http://raaxx org/ aba/2303 10498
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-Scale attributed node embedding. Journal of Complex Networks, 9(2), April 2021. doi: 10.109 1...093/comne//cnbbll4
T Konstantin Rusch, Benjamin P Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael M Bronstein. Graph-Coupled Oscillator Networks. In Proceedings of the 39th International Confer- ence on Machine Learning, volume 162, Baltimore, Maryland, USA, 2022. PMLR.
T. Konstantin Rusch, Michael M. Bronstein, and Siddhartha Mishra. A Survey on Oversmoothing in Graph Neural Networks, March 2023a. URL /tttp://aaxx org/ abs//aa////3 10993.
T. Konstantin Rusch, Benjamin Paul Chamberlain, Michael W. Mahoney, Michael M. Bronstein, and Siddhartha Mishra. Gradient Gating for Deep Multi-Rate Learning on Graphs, In The Eleventh International Conference on Learning Representations, February 2023b.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The Graph Neural Network Model. JEEE Transactions Neural Networks, 20(1):61 80, December 2008. doi: 10.1109TNNN 200.22008..0066
Prithviraj Sen, Galilco Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective Classification in Network Data. Al Magazine, 29(3), September 2008, doi: 10. 10.1169/aimag.x2999 21973.2157.
Oleksandr Shchur. Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of Graph Neural Network Evaluation, June 2019. httttttp//aai..org////////
05868
Han Shi, Jiahui Gao, Hang Xu, Xiaodan Liang, Zhenguo Li, Lingpeng Kong, Stephen M. S. Lee, and James Kwok. Revisiting Over-smoothing in BERT from the Perspective of Graph. In The Tenth International Conference on Learning Representations, 2021a.
Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjing Wang, and Yu Sun. Masked Label Prediction: Unified Message Passing Model for Semi- Supe-Super Classification. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, page 1548, 2021b. ISBN 1045-0823.
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J Sutherland, and Ali Kemal Sinop. Exphormer: Sparse Transformers for Graphs. In Proceedings of the 40th International Conference on Machine Learning, 2023.
Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. ArnetMiner: extraction and mining of academic social networks. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 2008
Matus Telgarsky. Neural Networks and Rational Functions. Proceedings of the 34th International Conference on Machine Learning, pages 3387-3393. PMLR, July 2017.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature, In The Fortieth International Conference Machine Learning, 2021.
14

---

Martin Trimmel, Mihai Zanfir, Richard Hartley, and Cristian Sminchisescu. ERA: Enhanced Rational Activations. In Shai Avidan, Gabriel Brostow, Moustapha Cissé, Giovanni Maria Farinella, and Tal Hassner, editors, Proceedings of the European Conference on Computer Vision, 2022.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is All you Need. In Advances in Neural Information Processing Systems, 2017.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In The Thirly-fifth International Conference on Machine Learning, 2018.
Lilapati Waikhom and Ripon Patgiri. A survey graph neural networks in various learning paradigms: methods, applications, and challenges. Artificial Intelligence Review, 56:6295-660 6364, July 2023. doi: 10. 10.10007/114422-022 103-11--
Yuyang Wang. Zijie Li, and Amir Barati Farimani. Graph Neural Networks for Molecules. Machine Learning in Molecular Sciences, 36:21-66, 2023.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simpli- fying Graph Convolutional Networks. Proceedings of the 36th International Conference on Machine Learning, 2019. ISBN 2640-3498.
Muhan Zhang and Yixin Chen. Link Prediction Based Graph Neural Networks. In Advances in Neural Information Processing Systems, 2018.
Lingxiao Zhao and Leman Akoglu. PairNorm: Tackling Oversmoothing in GNNs. In International Conference on Learning Representations (ICLR), 2020.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al Open, 1:57-81, January 2020a. doi: 10.
Kaixiong Zhou, Xiao Huang, Yuening Li, Daochen Zha, Rui Chen, and Xia Hu. Towards deeper graph neural networks with differentiable group normalization. In Proceedings the 34th International Conference on Neural Information Processing Systems, NIPS '20, pages 4917-4928, Red Hook, NY, USA, December 2020b. Curran Associates Inc. ISBN 978-1-71 1332--95-2-666
Yangiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep Graph Contrastive Representation Learning, 2020.
15

---

A Appendix
A.1 Details on the datasets
An overview of the datasets used in our evaluation is found in Tad in Table 8 In addition to the number of nodes, edges, features, and classes, we also provided the node homophily ratio and whether the classes are distributed uniformly, well number of graphs for graph-level datasets. The node homophily ratio measures how many a node's 's neighbors are members of the same class. It is computed as:
K(GJ EEIEEE = MjH
V
SEV
Table 7: The datasets used to evaluate CNA. The table contains statistics for the node classifica- tion and property prediction tasks. For regression, we used the Chameleon and Squirrel datasets, but with each page's log average web traffic as the target value.
Name
#Nodes
#Edges
#Features
#Classes
Homophily
Balanced
Chameleon
2.277
36,101
2,325
0.10
No
CiteSeer
3,327
9,104
3,703
6
0.71
No
Computers
13.752
491,722
767
0.79
No
Cora
2,708
10,556
1,433
7
0.83
No
CoraFull
19,793
126,842
8,710
70
0.59
No
DBLP
17,716
105,734
1,639
4
0.81
No
Photo
7,650
238,162
745
0.84
No
PubMed
19,717
88,648
500
3
0.79
No
Squirrel
5,201
217,073
2,089
5
0.09
Yes
Texas
183
309
1,703
5
0,07
No
Wisconsin
251
499
1,703
5
0.17
No
ogbn-arxiv
169,343
1,166,243
128
40
0.43
No
Table The graph-level datasets we used to evaluate CNA. The table contains statisties for the graph-level classification.
Name
#Graphs
Avg. #Nodes
Avg. #Edges
#Features
#Classes
Balanced
Mutag 188
~17.9
-39.6
7
No
Enzymes 600
-32.6
-124.3
Yes
Proteins 1,113
-39.1
-145.6
3
No
A.2
Details on hyperparameters and training
Throughout the implementation, we used the following software packages:
PoToc Geometric (PyG) [eyy and Lenssen 2019 is widely used for machine learning Graphs and was our first choice.
To implement the clustering step, we used Fast Py Torch Kmean GPU-based implemen-
tation of the renowned algorithm.
implement the activate step, we used rationals from the Activation Functions library
The degrees of freedom for the rationals were set to 5 for the numerator and m 4 for the denominator for all settings. For all experiments, we used the Adam optimizer with weight decay,
htttps://ww.pp: wwg..ygg..oo org/
http:///ggttthhaee/////eetrrrraa ammea kmeans
16

---

Table 9: Hyperparameters for node classification, node property prediction and graph-level classifi-
cation.
Dataset
Architecture Type
#Epochs
#Layers
#Clusters
#Hidden
Act.
Weight Decay
Chameleon
Dir-GNN
500
2
10
500
10a
10
5-10
CiteSeer
GAT
100
4
12
60
10a
10.
1-10-t
Computers
TransformerConv
100
2
10
20
10a
10Sh
5-10*
Cora
GraphSAGE
50
4
12
28
10a
10a
5-10%
CoraFull
TransformerConv
100
2
14
140
10a
10
1.10%
DBLP
GCN
100
4
12
60
10a
10a
5.10¹
Photo
TransformerConv
100
4
8
80
10a
10
5.102
PubMed
TransformerConv
100
2
12
60
10a
10SS
5.102
Squirel
Dir-GNN
500
2
10
500
10a
10
5.10-2
Texas
GraphSAGE
200
2
10
100
10
10
1-10a
Wisconsin
TransformerCov
200
2
10
500
10a
10
5-10
ogbn-arxiv
GCN
300
4
10
400
10
10
1-10"
ogbn-arxiv
GraphSAGE
1000
10
60
10a
10
1-10
Mutag
GCN
1000
8
128
10a3
10
1-10*
Enzymes
GCN
1000
4
8
128
10a
10
1-10*
Proteins
GCN
1000
4
8
128
10
10
1-10*
Table 10: Hyperparameters for node regression (TransformerCony) the ablation study (*), and
Table (*).
Architecture Type
#Epochs
#Layers
#Clusters
#Hidden
LR
LR Act.
Weight Decay
TransformerConv
300
2
64
2-10
1-10
1-10*
200
4
14
280
1-10-3
1-10
5-10
where we set 31 0.9 and Bg 0.999. We used summation the aggregation function due to its simplicity and widespread use. Table lists all relevant hyperparameters used for node classification, property prediction, and graph-level classification tasks. Table 10 provides the hyperparameters for Table [ for the node regression task, as well as for the ablation study. For the sensitivity test, the only difference from (*) in Table was the number of layers, which was set to 32. Regardless of the setting, each experiment was performed on one A A100 Nvidia GPU and took between five minutes and two hours, depending on the specific configuration.
A.3 Comparison to other graph normalization techniques
Table IT shows how CNA compares to other graph normalization methods proposed in the literature. The reference column indicates the origin of the performance indicators, with the remaining results stemming from Table Our method provides the best classification accuracy.
Table 11: Comparison of CNA to other graph normalization methods on the Cora dataset.
Architecture and Normalization
Reference
Accuracy (t)
GCN
Baseline
81.59+0.43
GCN + BatchNorm
loffe and Szegedy [2055
73.9
GCN + Diff. Group Norm.
Zhou et al. | 2020b
82.0
GCN + PairNorm
Zhao and Akoglu
2020
71.0
GCN + CNA
Ours
93.66:20.88
17

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our abstract summarizes the contributions of our paper. In particular, our claims about our method (ef. Section 3 are backed by the extensive experimental evaluation in Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We make assumptions and the focus of our work transparent throughout this manuscript. Additionally, discuss limitations explicitly in Section 5
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create 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 the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-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 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
18

---

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

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
We ensured the exclusive of open-source datasets and software to aid in reproducibility. Our code is available at htttps://githubt http://ttttuuc.oommllomosoe com cow/m/- modules.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https
/
CobmeSumbeesac /onii///u ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if' applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide all necessary details not listed Section in Appendix AA.2 like specific hyperparameters and the choice of optimizer. We matched the datasets and train/val/test splits as close to original publications as possible to maintain comparability to the existing literature and reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All experimental results presented in Section (except for the compute-intent intense hyperparameter sensitivity analysis) are run over multiple seeds, as stated there. We report means as well as standard deviations for all key results.
Guidelines:
The answer NA means that the paper does not include experiments.
20

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, 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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification:
This information is provided in the supplemental Appendix A.2
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well 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).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: tttttp:///nurippee cc/pubbiic/ttiicccidee.......
Answer:
[Yes]
Justification:
We ensured that our research aligns with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
New and improved machine learning models and architectures are inherently dual-use technologies. In particular, our work on CNA can be used for harmful purposes, like any other GNN deployed for surveillance, unfair social recommendations, etc. However, we did not identify socictal impacts specific to this work warranting dedicated discussion.
Justification:
21

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., denloymemt 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 intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
We did not identify any such high-risk aspects in the presented work.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere 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 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 acknowledge all immediately relevant third works and cite them in the ap- propriate sections (namely Section and Appendix AA.2. We ensured the legal compatibility of the employed datasets and software components. The datasets used are provided and publicly documented by PyTorch Geometric [Fey and Lenssen 2019
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
22

---

The authors should state which version of the asset is used and, if possible, include 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, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide the implementation of our method used for the experiments at httpp://github.
htwcchhcccaaaaaeeeeeeeeeeee santeearrchhnammmdllleee moduleoleees..e es It contains resources to get started with using the method and reproducing the results.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. 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 participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
We did not perform experiments with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: We did not perform experiments with human subjects
23

---

Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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 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 the institution conducting the review.
24


Reviews:
[{"review_id": "jMin6aJOdC", "reviewer": "Reviewer_jRzY", "summary": "This paper proposes a novel module, CNA (Cluster-Normalize-Activate), to address the oversmoothing problem in Graph Neural Networks (GNNs).  The CNA module operates in three steps: clustering node features, normalizing them within clusters, and applying learnable activation functions to each cluster.", "questions": "See in Weaknesses.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1.\tExperiments and analysis are solid. Results show that the CNA module enhances the expressiveness and performance of GNNs, particularly in node classification and regression tasks.\n\n2.\tThe CNA module can be applied to various GNN architectures.\n\n3.\tIncorporating the CNA module requires fewer or comparable parameters than existing SOTA methods.", "weaknesses": "1.\tIn Table 4, I would encourage to report the performance and parameter amount of SAGEConv and GCNConv baselines as well. It could help readers to have a clearer understanding of how many parameters are introduced by the proposed CNA module.\n\n2.\tCan the CNA module improve the performance in graph-level tasks?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments and for acknowledging that our experiments and analysis are solid and that our method is easily adaptable. We will address your concerns next.\n\n### Q1 (Results on SAGEConv and GCNConv):\nThank you for taking a closer look. We have now run new experiments using the same SAGEConv and GCNConv without CNA. Please find the results in the table below.  As it can be seen, the accuracy drops by a huge margin, whereas the change in the number of parameters is minimal. \n\n| Model    | Accuracy (↑) | Number of Parameters (↓) |\n| -------- | ------------ | ------------------------ |\n| SAGEConv | 59.97±0.33%  | 34780                   |\n| GCNConv  | 69.66±0.27%  | 388440                  |\n\nA Rational activation only introduces 10 learnable parameters, since the activation is performed pointwise on each entry of the node feature vector. This means that for 5 clusters and 20 layers, we add 5\\*20\\*10 = 1000 new learnable parameters.\n\n### Q2 (CNA on graph-level tasks):\nWe gladly extended our evaluation of CNA to graph-level learning, and report the results below. In particular, we ran GCNConv with ReLU and compared it with CNA (@ 10 clusters) on three datasets: MUTAG, ENZYMES, and PROTEINS [Morris et al., 2020]. Averaged over five seeds, CNA improves classification accuracy for all data sets:\n| Dataset  | Accuracy with CNA (↑) | Accuracy with ReLU (↑) |\n| -------- | --------------------- | ---------------------- |\n| MUTAG    | **81.60±4.18%**   | 78.42±6.55%            |\n| ENZYMES  | **50.01±3.25%**   | 36.97±3.08%            |\n| PROTEINS | **74.44±2.49%**   | 72.72±2.6%             |\n\n\nThis confirms the effectiveness of CNA across a variety of tasks.\n\nReferences\n\n(1) Morris, Christopher, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann (2020): TUDataset: A Collection of Benchmark Datasets for Learning with Graphs. Graph Representation Learning and Beyond (GRL+), ICML 2020 Workshop.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4JzAfXBLLh", "reviewer": "Reviewer_gBSJ", "summary": "The paper describes a new updating rule based on a sequence of operation clustering, normalization and a learnable activation to replace the original plain relu-like update message passing and empirically show that such learnable updating function gains large performance improvement on existing benchmark datasets. The author claims the new updating rule alleviates oversmoothing to some extent and has better expressive power from a learnable activation function. Compared with existing graph normalization, the learnable involved for normalization in this paper is postponed to the learnable activation stage to ensure a better expressivity. The clustering used here is a simple Kmeans clustering and the paper suggests that simple kmeans is sufficient to guarantee performance and save computation time.", "questions": "As suggested in the weakness. My most concern is on point 2 and 4.", "limitations": "The author suggests the lack of large-scale dataset experiments and limited connection to oversmoothing.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.The paper shows a clear structure of the new updating rules, the writing is clear and the presentation is easy to understand.\n2.The empirical experiments suggest a very strong improvement gain in terms of the baseline models, even compared with existing PWC leaderboard, somewhat indicate the effectiveness of the new updating method.\n3.The computation resources needed is suggested to be manageable compared with more complex architectures.\n4. The idea is simple and seems to be applicable universally to most MPNN structures.", "weaknesses": "1. Although the empirical results show a great performance gain on Cora and Citeseer dataset, this CNA module lacks theoretical analysis on why it works and where the performance gain comes from. It is very unintuitive to consider why normalization over a knn based cluster can show a much better performance, there lacks a comparison between existing graph normalization techniques and the proposed one for a better comparision.\n2. From the ablation study in Table 5, it suggests that simply with cluster and normalization gives most of the performance gain on Cora data, the   effect of learnable activation modules seems to be negligible. The author claims the expressive power is preserved in this learnable activation part. So why the performance gain mostly come from the first two part (from the results of Table 5)? This is somewhat contradict to the author's claim.\n3. To better reflect the method's ability of alleviating oversmoothing, the author should reflect the layer wise dirichlet energy plot for this method and also consider extend the layer number from 32 to at least 64, as produced from previous papers, like G2-gating.\n4. The lack of discussion on the clustering method (using only k-means) leads to concern about the stability of the method. K-means clustering is known to be not stable. It is weird there is no discussion about the sensitivity of the choice of cluster number, metric choice, etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments and for acknowledging our strong results, universality of the method, and clear writing. We will address the concerns next.\n\n### Q1 (Additional theoretical analysis and comparison to other normalization techniques):\nPlease see our general response/comment for more theoretical insights.\n\nRegarding the normalization techniques, there indeed are many methods specifically for GNNs, as also discussed in Section 2 on Related Work. In particular, GraphNorm for graph-level tasks (as opposed to node-level ones) provides partial normalization, where features are normalized across each separate graph [Cai et al., 2021]. PairNorm normalizes features to zero mean and constant total pairwise squared distance between nodes [Zhao and Akoglu, 2020]. However, **considering groupings of the nodes can further improve the effectiveness of normalization. This was also shown by Zhou et al. (2020), where learned soft-clustering was performed instead of nonparametric hard k-means as in our method.** Generally, one wants to not only normalize within clusters but also apply a learned transformation [Ioffe and Szegedy, 2015]. This makes the constituents of the cluster distinct from the other ones. \n\nWe further note that we replaced the affine transformation following most normalization techniques with a more expressive Rational activation. Overall, CNA proved to be highly effective. Please see comparisons to other normalization techniques in the global comment.\n\nWe further added a discussion of theoretical properties related to oversmoothing to the global comment above. We believe that reducing the impact of oversmoothing significantly contributes to the improved performance of CNA observed in our thorough empirical evaluation. See also our response to your third question (Q3) for deeper empirical insights.\n\n### Q2 (Ablation study):\nMuch like with other architectures, different components contribute to the overall performance to differing degrees, depending on the dataset. For example, if the ablation study is performed on the *ogbn-arxiv* dataset instead of on Cora, the necessity of the learned Activate step is much more visible:\n| Ablated variant | Accuracy (↑)        | \n| --------------- | ------------------- | \n| CNA             | **74.64±0.13%** |\n| CN + ReLU | 69.55±0.42% |\n\nThe table shows the results of training a GNN with GCNConv with cluster and normalize steps, but with (CNA) and without rational activations (CN+ReLU). We further note that full CNA improves the convergence speed of GNN learning over just CN, as shown in Figure 2 in the rebuttal PDF.\n\n### Q3 (Alleviating oversmoothing in deeper GNNs):\nThank you for this astute comment! Please have a look at top 2 graphs of Figure 1 in the rebuttal pdf. There, we reran and extended the results on Cora and CiteSeer beyond 32 layers to 64 and even 96 layers, again with five seeds. This further confirms that CNA maintains high performance even at great depths. Coming in second are again the models with removed activations (“linear”). Lastly, vanilla GNNs quickly deteriorate in performance at increasing depths.\n\nMoreover, we visualized the final Dirichlet energy (DE) of each of the models in the Fig 1 of rebuttal pdf, which is well-known to measure (over)smoothing [Rusch et al., 2023]. We see how the vanilla GNNs typically start in the undersmoothing regime with low DE, transition to an optimal region with elevated DE, and finally deteriorate due to oversmoothing with low DE again. A high DE is a necessary condition for good model performance, as all CNA models and the linearized GATConv and GCNConv prove. This shows that CNA inhibits oversmoothing at greater depths and thereby unlocks a large portion of its performance increase. The increased expressivity then allows it to achieve better accuracies than the linearized GNNs, combining the best of both worlds.\n\n### Q4 (Stability of k-means):\nIndeed, we can provide a more in-depth discussion of the properties of k-means to justify its use and good empirical performance.\n\nSince we were also interested in the sensitivity of CNA to the number of clusters, we performed a dedicated study showing that good configurations can easily be found by hyperparameter search. We describe those results in lines 300-304 and Figure 6. Overall, this confirms that k-means often provides decent clustering in practical settings and is sufficiently stable [Ben-David et al., 2007]. We also found that using much more computationally expensive Gaussian Mixture Models did not significantly improve the final performance of the GNNs. In our work, we compared nodes by their Euclidean distance, which we found to work reliably in our experiments. However, other applications might use different or even domain-specific distances. This flexibility is a benefit of CNA, allowing for more task context to be used in modeling.\n\nWe will add this discussion of the stability of k-means to the main paper.\n\nReferences\n\n(1) Ben-David et al. Stability of K-Means Clustering. Learning Theory 2007\n\n(2) Cai et al. GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training. ICML 2021\n\n(3) Ioffe et al. Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift. ICML 2015\n\n(4) Rusch et al. A Survey on Oversmoothing in Graph Neural Networks. arXiv 2023\n\n(4) Zhao et al. PairNorm: Tackling Oversmoothing in GNNs. ICLR 2020.\n\n(5) Kaixiong et al. Towards Deeper Graph Neural Networks with Differentiable Group Normalization. NeurIPS 2020", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "i96Jxz85HN", "reviewer": "Reviewer_swbi", "summary": "The authors propose a new normalization scheme they call \"CNA.\" They propose clustering the nodes according to their features and computing the normalization statistics for each cluster.\nThis is essentially a batch norm with groups tailored for graphs.\nThis normalization is then augmented with a learnable activation function. The three components above are fused together to a \"CNA\" block to be used after each message passing layer in an MPGNN.\nThe authors then perform several experiments on node classification and regression tasks.\nThe authors examine the effect of CNA on the performance of MPGNNs with numerous layers on the Citeceer and Cora datasets. They further perform benchmark experiments, showcasing impressive improvement on the Citeceer dataset.\nAfterwards, some additional ablation studies are conducted, considering different subsets of the CNA components showing how the performance is affected.", "questions": "Please see the \"Weaknesses\" section", "limitations": "No potential negative societal impact  is observed", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. I see why the proposed method is reasonable for helping combat over-smoothing, at least in some scenarios. \nAfter all, enforcing normalization for nodes with similar features seems to be stronger than enforcing normalization for all nodes.\n2. The presentation is neat, and the writing is satisfying.", "weaknesses": "1. Although the \"How\" is clear, I am not fully convinced by the \"Why\". The authors did not provide any theoretical insight into why CNA works.\n2. I also find the empirical experiments lacking. I would have expected to see many more experiments demonstrating why CNA helps combat over-smoothing, especially pricing analysis on different types of graphs (e.g., homophilic vs. heterophilic, inductive vs. transductive, etc...)\n3. The authors didn't examine how the dataset properties affect the effectiveness of CNA\n4. The experiments do not convince why CNA is preferred over other normalization layers.\n5. I do find the aggregation part of CNA slightly unrelated to the main purpose of the paper and incremental to the results (as clearly indicated by the ablation studies).\n6. Some of the benchmark's improvements seem to be statistically insignificant (the improvement in the mean performance seems small compared to the stds).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments and for finding the writing satisfying. We address your concerns next.\n\n### Q1 (Why CNA works):\n\nWe now provide theoretical underpinnings of why CNA works. Please have a look at the global response.\n\n### Q2 (Empirical evaluation):\nWe already provided empirical results on\n\n- node classification,\n- multi-scale node regression,\n- oversmoothing,\n- parameter parsimony,\n- ablation experiments, and\n- hyperparameter sensitivity.\n\nWe focused on transductive node property prediction, following the works of, for example, Zhao et al. (2020), Zhou et al. (2020), and Rusch et al. (2023). We see no fundamental issues with settings where graphs vary. For instance, CNA works well in graph-level tasks too:\n\n| Dataset  | Accuracy with CNA (↑) | Accuracy with ReLU (↑) |\n| -------- | --------------------- | ---------------------- |\n| MUTAG    | **81.60±4.18%**   | 78.42±6.55%            |\n| ENZYMES  | **50.01±3.25%**   | 36.97±3.08%            |\n| PROTEINS | **74.44±2.49%**   | 72.72±2.60%            |\n\nHere, we ran GCNConv with ReLU and compared it with CNA (@ 10 clusters) on three datasets: MUTAG, ENZYMES, and PROTEINS [Morris et al., 2020]. Results are averaged over five seeds. CNA improves classification accuracy for all data sets, confirming the effectiveness of CNA across various tasks.\n\nWe now extended the inspection of the occurrence of oversmoothing by visualizing the Dirichlet energy in shallow to even deeper GNNs, which is well-known to measure (over)smoothing [Rusch et al., 2023]. Please see Figure 1 in the rebuttal PDF. We see how the vanilla GNNs typically start in the undersmoothing regime with low DE, transition to an optimal region with elevated DE, and finally deteriorate due to oversmoothing with low DE again. A high DE is a necessary condition for good model performance, as all CNA models and the linearized GATConv and GCNConv prove. This strongly suggests that CNA inhibits oversmoothing at greater depths and thereby unlocks a large portion of its performance increase. The increased expressivity then allows it to achieve better accuracies than the linearized GNNs, combining the best of both worlds.\n\n### Q3 (Effect of dataset properties):\n\nWe are happy to shine more light on the details of our findings. Table 6 in the appendix can hereby help us to get an overview of the dataset properties and statistics. There are different aspects along which we can evaluate the effectiveness of CNA:\n\n- **Number of nodes and edges**: Since CNA increases the model expressivity and capacity, its performance benefit is stronger on larger datasets. In particular, if we look at the results of Tab. 3, classic methods work better on the rather small Texas and Wisconsin tasks. Furthermore, the original ablation study in Tab. 5 was run on Cora, which is only of medium size. If you look at our response to your (Q5), you can see that the benefits are much larger on the huge ogbn-arxiv.\n- **Degree of Homophily**: Our key ingredient CNA is not directly affected by a graph being homo- or heterophilic. This is because the clustering step and subsequent normalization and activation are invariant to the topology of the graph. Indeed, we see good performance on both homophilic graphs such as Cora, and heterophilic ones such as Chameleon. We had these degrees in our paper in Tab. 6 in the appendix.\n- **Number of features**: CNA appears to be able to better leverage large numbers of features. If again looking at Tab. 3, the difference due to CNA on Computers, Photo, and Pubmed is rather small, where the number of features is only moderate. Results tend to be better when more features are available, possibly due to easier clustering.\n- **Number of classes** (for node classification tasks): CNA can successfully be applied to small and large numbers of classes alike, as is apparent when comparing Cora with 7 and CoraFull with 70 classes (CoraFull) as seen in Tab. 3.\n\n### Q4 (Comparison to other normalization techniques):\n\nThank you for the question. We provide the new results. Please have a look at the global response.\n\n### Q5 (Ablation of activation function):\n\nMost commonly employed normalization techniques are followed by a simple scalar transformation, including the prolific BatchNorm, InstanceNorm, LayerNorm, and GroupNorm (see also Huang et al. (2023), specifically Tab. I). We extend this notion with much more powerful transformations, namely Rational activations, which are themselves universal scalar function approximators. This helps to further increase the expressivity of GNNs.\n\nPlease also have a look at our response to (Q2) of reviewer gBSJ.\n\n### Q6 (Statistical significance):\n\nWe kindly disagree and concur with the three other reviewers:\n- “CNA module enhances the expressiveness and performance of GNNs” (Reviewer jRzY)\n- “very strong improvement” (Reviewer gBSJ)\n- “showing significant improvements” (Reviewer v2xE)\n\nTable 1 shows that introducing CNA into existing architectures increases their classification performance by consistently more than an impressive 10%. Table 2 shows that CNA achieves the best overall results on regression tasks, too. In Table 3, we compare CNA to the state-of-the-art on an extensive collection of standard benchmark datasets. We find that CNA is the best architecture overall. \n\n### References\n- Huang et al. Normalization Techniques in Training DNNs: Methodology, Analysis and Application. TPAMI 2023\n- Morris et al. TUDataset: A Collection of Benchmark Datasets for Learning with Graphs. ICML 2020 Workshop\n- Rusch et al. A Survey on Oversmoothing in Graph Neural Networks. arXiv 2023", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NY5JbERlOo", "reviewer": "Reviewer_v2xE", "summary": "The paper  introduces a novel plug-and-play module named Cluster → Normalize → Activate (CNA) to enhance the performance of Graph Neural Networks (GNNs). The CNA module is designed to address the issue of oversmoothing, which occurs in deep GNN architectures and limits their ability to solve complex tasks. The module operates by clustering nodes into super nodes, normalizing them, and applying individual activation functions. The authors demonstrate the effectiveness of CNA through extensive experiments on node classification, property prediction, and regression tasks, showing significant improvements in accuracy and a reduction in mean squared error compared to existing methods.", "questions": "See weaknesses.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* The paper presents a creative solution to a well-known problem in GNNs, oversmoothing, by introducing the CNA module. This approach is a significant advancement in the field of deep learning on graph-structured data.\n\n* The authors provide a thorough empirical evaluation of the CNA module across various tasks and datasets, which substantiates the effectiveness of their proposed method.", "weaknesses": "* The paper lacks a theoretical analysis to support the empirical findings. A more rigorous theoretical underpinning could strengthen the claims made about the CNA module's effectiveness. Could the authors provide a theoretical analysis or proof that supports the empirical results?\n\n* The paper does not fully address the computational complexity added by the clustering step in the CNA module in theory or practice, which could be a concern for very large graphs or real-time applications, even with small number of parameters. Are there any optimizations or alternative clustering methods considered to address potential scalability issues?\n* In Table 4 why SageConv+CNA has less parameters than GraphSage But  GCNConv+CNA has more parameters than GCN? And the number varies a lot.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments and finding our method creative, a significant advancement, and empirical evaluation thorough. We address your concerns next. \n\n### Q1 (Theoretical underpinnings):\nWe agree that an improved understanding of the mechanisms driving CNAs strong empirical performance would be very helpful. Therefore, we added a discussion of the theoretical properties of CNA and its relation to oversmoothing to the global comment above. \n\nIn summary, we first show how existing proofs of the necessity of oversmoothing don’t apply to GNNs with CNA. We continue by arguing why they cannot trivially be repaired, since one can construct a hypothetical variant of CNA that certainly inhibits oversmoothing entirely. In practical settings, CNA takes a middle ground between classic oversmoothing GNNs and this potentially immune construction.\n### Q2 (Scalability):\nWe totally agree that scalability is an issue easily overlooked in GNNs. There are two possible approaches to this: (1) Asymptotic behavior and (2) practical scalability.\n\n(1): The runtime of k-means scales linearly with the size of the dataset, which here is the number of nodes in the graphs (cf. lines 187-191 in the submission). Its space requirement is favorable too. This is one reason we chose it over other methods, such as hierarchical clustering, since those methods typically require at least quadratic runtime. We did initially experiment with using Gaussian Mixture Models (which still do scale linearly in the dataset size), yet found their increased overall GNN performance to be insufficient to justify their high practical costs. This leads us to the next reason, its practical performance.\n\n(2): Interested in investigating the practical scaling properties of CNA, we applied it to the rather large *ogbn-arxiv* dataset (e.g., see Table 4). With 169k nodes and 1M edges, it shows that CNA can be applied to large-scale data.\n\nWe do recognize the pursuit of scaling to yet larger datasets as one key task for future work. Since the heuristic clusterings of k-means were already sufficient, we can be optimistic about significant further performance improvements. As perfect clustering does not seem to be necessary, subdividing the nodes into independent partitions in which we perform clustering might be feasible while maintaining good overall performance. This would allow for any clustering algorithm to get parallelized. Moreover, even faster procedures like random projections clustering might suffice [Fern et al., 2003].\n\n### Q3 (Parameter counts in Table 4):\n\nThe sole purpose of the experiment in Table 4 was to show that CNA allows for much smaller models at similar performance. To this end, for row (i), we trained a SAGEConv+CNA model to rival the results of SAGEConv without CNA. For a fair comparison, we also show the exact same configuration, but without CNA, in the table below. Similarly, row (ii) shows that GCNConv+CNA can similarly surpass the state-of-the-art with fewer parameters. We also present that model's performance without CNA:\n\n| Model    | Accuracy (↑) | Number of Parameters (↓) |\n| -------- | ------------ | ------------------------ |\n| SAGEConv | 59.97±0.33%  | 34780                   |\n| GCNConv  | 69.66±0.27%  | 388440                  |\n\n### References\n\n(1) Fern, Xiaoli Zhang, and Carla E Brodley (2003): Random Projection for High Dimensional Data Clustering: A Cluster Ensemble Approach. In Proceedings of the Twentieth International Conference on Machine Learning (ICML-2003). Washington DC.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
### Global Response/Comment
We want to thank all reviewers for their time and effort in improving this work. We particularly appreciate your acknowledgment of the relevance of the issue, the novelty of the approach, and the extensive and convincing experiments. Your comments and questions helped improve the paper, and we hope to have clarified all of them below.

Since there were multiple requests for theoretical analysis, we provide that one here in the global response. We wrote dedicated answers to all your other questions. Furthermore, please see the attached PDF.

**Theoretical Analysis**

It has been suggested to more formally discuss the relationship of CNA to oversmoothing. There are two directions in which we can tackle this. (1) We can show *how* previous proofs of the necessary occurrence of oversmoothing in vanilla GNNs are not applicable when CNA is used. (2) We can provide a reason for *why* these proofs are not easily repairable and how CNA breaks free of the oversmoothing curse.

**(1)** The Rational activations of CNA trivially break the assumptions of many formalisms due to their potential unboundedness and not being Lipschitz continuous. This includes Prop. 3.1 of Rusch et al. (2023), where, however, the core proofs on oversmoothing are deferred to Rusch et al. (2022). There, again, the activation $\sigma$ is assumed to be point-wise and further narrowed to ReLU the proof in Appendix C.3. Regarding the more recent work of Nguyen et al. (2023), we again note that CNA violates the assumptions neatly discussed in Appendix A. The CNA module can either be modeled as part of the message function $\psi_k$ or even as part of the aggregation $\oplus$. However, in both cases, the proof of Prop. 4.3 (which is restricted to regular graphs) breaks down. In the former case, there appears to be no immediate way to repair the proof of Eq. (15) in Appendix C.3. In the latter case, providing upper bounds in Appendix C.2 is not exactly straightforward.

**(2)** This begs the question of why that is difficult. The answer is that we specifically built CNA to break free of the current limitations of GNNs. Empirically, this indeed hurdled oversmoothing. In theory, this makes sense once we consider two possible extremes that arise as special cases of CNA. Consider a graph with $N$ nodes. On one end, we can consider CNA with $N$ clusters and Rationals that approximate some common activation, such as ReLU. This exactly recovers the standard MPNN architecture, which is known to be doomed to oversmoothing under reasonable assumptions (see above). We can alternatively consider the same setting with only one cluster, i.e., MPNNs with global normalization. It is also known to exhibit oversmoothing empirically [Zhou et al., 2020]. Conversely, we can consider $N$ clusters, with constant Rational activations given by $R_i (x) = i$ for each cluster $i \in \{1, \dots, N\}$. Obviously, the Dirichlet energy of that output is lower bounded and does not vanish no matter the number of layers. In practice, we employ, of course, between one and $N$ clusters, and thereby trade off the degree to which the GNN is affected by oversmoothing. Bounding this relationship goes far beyond the scope of the current work, and is definitely an interesting direction for future work.

**Overall motivation: why CNA works**

- Cluster: We first identify groups of nodes with similar properties. We later learn separate projections for each such group, ensuring distinct feature representations. It is reasonable to assume such a structure exists, especially in classification datasets.
- Normalize: To maintain good stability during the propagation through the layers, we normalize the features within each cluster.
- Activate: Finally, we project the nodes with separate learned activations per cluster. These expressive functions also take up the work of the usual learned transformation after normalization steps.

**Comparison to other graph normalization techniques**

We also provide a comparison of CNA to BatchNorm (5), Deep Group Normalization (4), and PairNorm (6):

| Model and Normalization | Accuracy on Cora (↑) |
| ----------------------- | -------------------- |
| GCNConv                 | 82.2%                |
| GCNConv + BatchNorm     | 73.9%                |
| GCNConv + DGN           | 82.0%                |
| GCNConv + PairNorm      | 71.0%                |
| GCNConv + CNA (ours)    | **93.66±0.48%**  |

Results for the other methods were taken from Zhou et al. (2020). You can find details on how other ablated variants of CNA than the ones shown here fare by consulting Table 5. We also note that Table 2 already compares PairNorm with CNA.

**References**

(1) Rusch, T. Konstantin, Benjamin Paul Chamberlain, Michael W. Mahoney, Michael M. Bronstein, and Siddhartha Mishra (2023): Gradient Gating for Deep Multi-Rate Learning on Graphs. ICLR 2023.

(2) Rusch, T Konstantin, Benjamin P Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael M Bronstein (2022): Graph-Coupled Oscillator Networks. ICML 2022. Baltimore, Maryland, USA.

(3) Nguyen, Khang, Hieu Nong, Vinh Nguyen, Nhat Ho, Stanley Osher, and Tan Nguyen (2023): Revisiting Over-Smoothing and over-Squashing Using Ollivier-Ricci Curvature. ICML 2023, 202:25956–79. Honolulu, Hawaii, USA.

(4) Zhou, Kaixiong, Xiao Huang, Yuening Li, Daochen Zha, Rui Chen, and Xia Hu (2020): Towards Deeper Graph Neural Networks with Differentiable Group Normalization. NIPS ’20. Red Hook, NY, USA.

(5) Ioffe et al. Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift. ICML 2015

(6) Zhao et al.  PairNorm: Tackling Oversmoothing in GNNs. ICLR 2020

Meta-review: The paper proposes a novel module for GNNs with the goal of overcoming oversmoothing. The new module is referred to as CNA , where "c" stands for clustering nodes according to their features, "n" stands for normalization applied to the clusters, and "a" stands for learnable activation functions. It is demonstrated empirically that the new model achieves new state-of-the art on Cora and Citeseer.

After rebuttal, in which authors provided a set of additional experiments, all reviewers votes were positive (3x5 and 1x6). The main remaining criticism is the missing theory to explain the success of the approach. Due to the great experimental results I nevertheless vote for acceptance.
Decision: Accept (poster)