Graph Neural Networks Need Cluster-Normalize-Activate Modules

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.

Q1 (Theoretical underpinnings):

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

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

Q2 (Scalability):

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

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

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

We 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].

Q3 (Parameter counts in Table 4):

The 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:

References

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

We thank the reviewer for the thoughtful comments and for finding the writing satisfying. We address your concerns next.

Q1 (Why CNA works):

We now provide theoretical underpinnings of why CNA works. Please have a look at the global response.

Q2 (Empirical evaluation):

We already provided empirical results on

• node classification,
• multi-scale node regression,
• oversmoothing,
• parameter parsimony,
• ablation experiments, and
• hyperparameter sensitivity.

We 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:

Here, 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.

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

Q3 (Effect of dataset properties):

We 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:

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

Q4 (Comparison to other normalization techniques):

Thank you for the question. We provide the new results. Please have a look at the global response.

Q5 (Ablation of activation function):

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

Please also have a look at our response to (Q2) of reviewer gBSJ.

Q6 (Statistical significance):

We kindly disagree and concur with the three other reviewers:

• “CNA module enhances the expressiveness and performance of GNNs” (Reviewer jRzY)
• “very strong improvement” (Reviewer gBSJ)
• “showing significant improvements” (Reviewer v2xE)

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

References

• Huang et al. Normalization Techniques in Training DNNs: Methodology, Analysis and Application. TPAMI 2023
• Morris et al. TUDataset: A Collection of Benchmark Datasets for Learning with Graphs. ICML 2020 Workshop
• Rusch et al. A Survey on Oversmoothing in Graph Neural Networks. arXiv 2023

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.

Q1 (Additional theoretical analysis and comparison to other normalization techniques):

Please see our general response/comment for more theoretical insights.

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

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

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

Q2 (Ablation study):

Much 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:

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

Q3 (Alleviating oversmoothing in deeper GNNs):

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

Moreover, 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.

Q4 (Stability of k-means):

Indeed, we can provide a more in-depth discussion of the properties of k-means to justify its use and good empirical performance.

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

We will add this discussion of the stability of k-means to the main paper.

References

(1) Ben-David et al. Stability of K-Means Clustering. Learning Theory 2007

(2) Cai et al. GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training. ICML 2021

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

(4) Rusch et al. A Survey on Oversmoothing in Graph Neural Networks. arXiv 2023

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

(5) Kaixiong et al. Towards Deeper Graph Neural Networks with Differentiable Group Normalization. NeurIPS 2020

Thank you for taking the time to provide the feedback on our rebuttal. In the following, we want to address both aspects you pointed out:

1. Expressive power of CNA

The expressive power of Rationals were studied by both Delfosse et al. (1) and Telgarsky (2). The author of (2) proven Rationals to be better approximants than polynomials in terms of convergence. All the while, Delfosse et al. (1), show in their that in actuality Rationals amplify a model with high neural plasticity. More to this point, they provided a proof that Rationals can dynamically make use of a residual connection: a Rational embeds a residual connection ⇔ m>n. See p. 4 of the paper (1) for the theorem and its proof. Throughout our experimental evaluations, we used m=5 and n=4, which answers where the expressive power of CNA modules stems from.

2. Role of Clustering in CNA

We agree with your intuition. More to the point, Shi at al. (3) demonstrate in their work that clustering minimizes redundant connectivity and so makes message passing more effective. And, as you are pointing out, normalization facilitates feeding the rewiring edge information to the nodes.

We will add these points to the paper. Thanks again, your inputs have helped to make our manuscript more clear. We hope we have addressed all your concerns and it will be great if you can reconsider your score

References

(1) Delfosse et al., Adaptive Rational Activations to Boost Deep Reinforcement Learning. ICLR 2024.

(2) Matus Telgarsky, Neural Networks and Rational Functions. ICLR 2017.

(3) Shi et al., ClusterGNN: Cluster-Based Coarse-To-Fine Graph Neural Network for Efficient Feature Matching. CVPR 2022.

Thank you for the comment!

On Expressive Power of Learnable Activations in Context of GNNs

To the best of our knowledge, our work is the first one using Rationals in the context of GNNs. On the other hand, research on learnable activation functions is limited, and our work contributes to this area by exploring the use of Rationals in GNNs.

Some papers do explore the effects of activation functions on the expressive power of GNNs:

Khalife and Basu (1) study the power of graph neural networks and the role of the activation function shows that changing the activation function can drastically change the power of GNNs.

Yu et al. (2) investigate in their work influences of different activation functions in GNNs and find that the choice of activation function can significantly affect the performance.

Although these studies do not specifically focus on learnable activation functions, they do highlight the importance of activation functions in determining the expressive power of GNNs. Both discuss the impact of activation functions on the expressive power of GNNs in the context of the Weisfeiler-Lehman (WL) test. More to this point, they do not specifically address how activation functions can help exceed the limit of the WL-test.

The first paper (1) proves that GNNs with piecewise polynomial activations cannot distinguish certain non-isomorphic graphs, while those with non-piecewise polynomial activations (like sigmoid, hyperbolic tan) can distinguish them in two iterations.

The second paper (2) investigates the expressive power of Graph Transformers with different activation functions (softmax, tanh, sigmoid) and finds that sigmoid is the most powerful, enabling the Graph Transformer to achieve the same level of expressiveness as the WL test.

Molina et al. (3) show that Rationals can approximate either tanh or sigmoid functions, allowing for end-to-end learning of deep networks without the need to manually select fixed activation functions. CNA builds upon these findings.

Neither (1) and (2) nor other related works explicitly discuss how activation functions can help exceed the limit of the WL-test. The focus is primarily on understanding how different activation functions affect the expressive power of GNNs within the bounds of the WL-test.

Role of Clustering and Normalization in CNA

Some papers do explore the concepts of normalization and rewiring in GNNs, providing empirical evidence:

Chen et al. (4) study on learning graph normalization for GNNs discusses the importance of normalization in improving the performance of GNNs.

Caso et al. (5) propose a novel graph rewiring approach to improve GNNs' performance on graph-related tasks.

Zhou et al. (6) offer a review of methods and applications of GNNs, highlighting the role of normalization and rewiring in enhancing the efficiency and effectiveness of GNNs.

Although these studies do not specifically address how normalization facilitates feeding rewiring edge information to nodes in combination with clustering, they do emphasize the importance of normalization and rewiring in improving the performance of GNNs. As far as we are aware, sadly, there are no dedicated theoretical studies on this particular question yet. We suggest that future research could investigate this topic further, potentially leading to new insights and improvements in GNNs.

As far as Shi et al. are concerned, we agree that there is no theoretical analysis there, but the reduction of redundancy is the whole motivation behind the paper, and the experimental results show that.

Conclusion

In conclusion, our proposed method, CNA, contributes to the current state of research on the expressive power of learnable activations in the context of GNNs. We have addressed the reviewer's concerns and provided an overview of the related works on this topic, in extension the theoretical analysis of the combined CNA modules in the global comment. While there are no dedicated theoretical studies on the specific role of clustering and normalization in CNA yet, we suggest that future research investigates this topic further.

References

(1) Khalife, S., & Basu, A.. On the power of graph neural networks and the role of the activation function. arXiv preprint arXiv:2307.04661.

(2) Yu et al., Activation Function Matters in Graph Transformers, ICLR 2024

(3) Molina et al., Padé Activation Units: End-to-end Learning of Flexible Activation Functions in Deep Networks. ICLR 2020.

(4) Chen et al., Learning Graph Normalization for Graph Neural Networks, Neurocomputing 2022

(5) Caso et al., Renormalized Graph Neural Networks, preprint on arXiv:2306.00707v1

(6) Zhou et al., Graph neural networks: A review of methods and applications, AI Open 2020

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.

Q1 (Results on SAGEConv and GCNConv):

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

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

Q2 (CNA on graph-level tasks):

We 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:

This confirms the effectiveness of CNA across a variety of tasks.

References

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