Graph Neural Networks Need Cluster-Normalize-Activate Modules

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.

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

Questions

See weaknesses.

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

2

Limitations

yes

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. This is essentially a batch norm with groups tailored for graphs. This 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. The authors then perform several experiments on node classification and regression tasks. The 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. Afterwards, some additional ablation studies are conducted, considering different subsets of the CNA components showing how the performance is affected.

Strengths

1. I see why the proposed method is reasonable for helping combat over-smoothing, at least in some scenarios. After all, enforcing normalization for nodes with similar features seems to be stronger than enforcing normalization for all nodes. 2. 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. 2. 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...) 3. The authors didn't examine how the dataset properties affect the effectiveness of CNA 4. The experiments do not convince why CNA is preferred over other normalization layers. 5. 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). 6. Some of the benchmark's improvements seem to be statistically insignificant (the improvement in the mean performance seems small compared to the stds).

Questions

Please see the "Weaknesses" section

Rating

5

Confidence

5

Soundness

2

Presentation

3

Contribution

2

Limitations

No potential negative societal impact is observed

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.

Strengths

1.The paper shows a clear structure of the new updating rules, the writing is clear and the presentation is easy to understand. 2.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. 3.The computation resources needed is suggested to be manageable compared with more complex architectures. 4. 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. 2. 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. 3. 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. 4. 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.

Questions

As suggested in the weakness. My most concern is on point 2 and 4.

Rating

5

Confidence

4

Soundness

2

Presentation

3

Contribution

2

Limitations

The author suggests the lack of large-scale dataset experiments and limited connection to oversmoothing.

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.

Strengths

1. Experiments and analysis are solid. Results show that the CNA module enhances the expressiveness and performance of GNNs, particularly in node classification and regression tasks. 2. The CNA module can be applied to various GNN architectures. 3. Incorporating the CNA module requires fewer or comparable parameters than existing SOTA methods.

Weaknesses

1. In 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. 2. Can the CNA module improve the performance in graph-level tasks?

Questions

See in Weaknesses.

Rating

6

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

N/A