Summary
The paper pertains to the problem of using normalisation techniques specifically designed for graph-structured data and Graph Neural Networks (GNNs). Using constructed illustrative examples, the authors claim that existing normalisation techniques (including others designed for graphs) may create expressivity issues to the GNNs to which they are applied. Motivated by these examples, they speculate that one possible reason is the lack of adaptivity of the normalisation (affine) parameters to the input graph. To that end, they propose to replace fixed normalisation parameters with adaptive ones, produced at each layer by an auxiliary GNN for each vertex of the input graph. Additionally (and probably crucially), the auxiliary GNNs do not only receive the current vertex features as inputs but also Random Node Features (typically sampled from a Gaussian). The last one is known to render GNNs universal, and so is the case here. Experimentally, the method is tested on a battery of tasks and ablated across several factors (training convergence speed, combined with more expressive architectures than plain MPNNs), showing consistently improved performance compared to other normalisation methods and competitiveness with the state-of-the-art in several cases.
Strengths
**Clarity**. The paper is well-written, easy-to-follow and all the concepts are clearly explained. It can therefore be understood by a wider audience.
**Contextualisation to related work**. An extensive review and comparisons with related works are provided, allowing the reader to grasp their differences and understand the innovation of the proposed approach.
**Importance to the GNN community.** The techniques proposed by the authors are of general interest to the GNN community since they clearly and consistently improve current normalisation techniques and show good potential for adaptation in practice in various problems. Additionally, it is one of the few works showcasing the practical benefits of RNF (however see also weaknesses), which is a long-standing puzzle for GNN researchers.
**Empirical results**. The proposed method appears to work quite well and consistently in practice, in terms of empirical generalisation. In particular, it provides improvements against all base architectures tested and against all competing normalisation techniques, while both methodological techniques proposed (adaptive normalisation + RNF) are sufficiently ablated and shown to be important to be combined to obtain the desired performance gains.
Weaknesses
**Reservations regarding claims and the selected way to present findings**.
- One of my main objections to the presented manuscript is the way the findings were selected to be presented. In particular, the authors present their work as a graph-oriented adaptive normalisation technique and motivate their approach by comparing it against other normalisation techniques, both intuitively using constructed counterexamples and empirically, showcasing consistent improvements. Nevertheless, it seems to me that the main reason behind the empirical success is the random features. For example, see Table 2, where the adaptive normalisation per se does not seem to provide any significant practical advantages.
- However, as the authors correctly point out, random features are known to behave subpar in practice, despite their theoretical advantages. This leads me to believe that the authors have probably found a way to *improve the performance of random features*. To me, this is an important contribution per se, but the authors have chosen not to present their paper in that way, nor to sufficiently point out this takeaway in their paper.
- On the other hand, the authors have devoted a substantial part of the paper to motivating adaptive normalisation and discussing other normalisation techniques. In my viewpoint, the intuitive explanations provided (the examples in sec. 2.2. and the last paragraph before section 3.1.) are speculative and do not seem to be the real reason behind the success of the approach.
- Note also, that in several parts of the paper, the authors claim that existing normalisation techniques limit MPNNs’ expressivity, but I am not sure if this is the case. I think that if the authors choose to keep these claims, they should probably be provided with a more rigorous theoretical statement.
- I think that the most important question that needs to be addressed is why incorporating RNF into a normalisation layer overcomes their current limitations in providing performance improvements. I recommend that the authors discuss this both in their rebuttal and the paper, as it will provide important insights.
**Efficiency**. Another reservation I have about this work is that computational efficiency might be an issue, but is not adequately discussed. For example, the runtimes provided by the authors in Table 4 in the appendix, show an almost 3-fold increase in both training and inference time. Although this might not be significant compared to other more expressive GNNs, the comparison between the performance-complexity trade-offs is not clear. Moreover, it is a limitation of this method and should be more clearly discussed in the main paper.
**Limited evaluation against baselines**. Although as I mentioned before, the results are indeed convincing, both from a perspective of a normalisation technique and of a random feature technique, the authors have not sufficiently compared against the state-of-the-art. To their credit, they did include other baselines in the supplementary material and mentioned the gap in performance in their limitations section, but I think it would be fairer to discuss this more prominently (especially since this work can be perceived as an expressive GNN and not as a normalisation technique alone).
**Limited technical novelty**: Finally, a minor weakness is that there is limited novelty from a technical perspective, since if I am not mistaken adaptive normalisation has been proposed before for other domains (e.g. AdaIN, Huang et al., ICCV’17 is a relevant example – discussed by the authors in the appendix) and random features are well-known in the GNN community.
Questions
- Have the authors tried to modify a different normalisation technique, apart from LayerNorm? This might be an interesting ablation study.
- Do the authors need a GNN normalisation network for each layer of the GNN processing network?
Limitations
The authors have mentioned some limitations (mainly the gap in performance compared to state-of-the-art), but I think others should be discussed more extensively (e.g. efficiency - see weaknesses).
I do not foresee any negative societal impact.