Summary
This paper proposes an adaptive message passing scheme for Graph Neural Networks that is based on learnable "pseudonodes" which, to a certain extent, decouple the paths along which node features are propagated from the topology of the underlying graph. Both pseudonodes and regular nodes in the underlying graph are embedded in a common space, which allows to utilize the common embeddings to generate proximity-dependent relations between nodes and pseudonodes that are used for a sparse "global" message passing layer. The proposed method is evaluated in a node and graph classification experiment for several benchmark data sets and the authors find superior performance on several data sets.
Strengths
[S1] The authors propose a new adaptive message passing scheme that introduces learnable pseudo-nodes and pseudo-edges, thus introducing dynamic pathways for message passing that are independent of the graph topology and that can be trained for a given learning task. The specific combination of pseudonde message passing and the use of recurrent layers is - to the best of my knowledge - new and original.
[S2] The method is evaluated against several baseline methods for a node and graph classification task in 18 small and large-scale benchmark data sets. The experiments show superior performance for the proposed model in several of the data sets (all six data sets for graph classification, eight out of twelve data sets for node classification).
[S3] Addressing limitations of GNNs that are due to over-squashing and over-smoothing, the authors address an important open issue in deep graph learning.
Weaknesses
[W1] I did not find the motivation to add additional learnable parameters to Graph Neural Networks that decouple message passing pathways from the topology of the input graph convincing. The authors motivate their work based on over-smoothing and over-squashing in GNNs but in my view the paper lacks an intuitive explanation why the proposed dynamic messing passing scheme should mitigate those problems, especially since the architecture additionally includes regular (local) message passing. To this end, I think that the different, complex local and global components of the dynamic message passing - though formally defined - are not explained well in the paper and some of the design choices appear to be rather arbitrary.
[W2] I similarly could not follow the motivation for the addition of the recurrent layer, which the authors argue is added "to parameterize the displacements of embedded nodes" and to "revise the learned distribution [] of all embedded nodes and reshape the dynamic message passing pathways". A better explanation would be helpful.
[W3] The idea to add pseudonodes for neural message passing has been previously explored, e.g. in the form of a sparse attention mechanism with so-called "global nodes" in the Exphormer architecture (https://arxiv.org/pdf/2303.06147). A better explanation of the contribution of the authors would be helpful, especially since the experiments show that the performance is very close to this architecture in many of the experiments.
[W4] There are important details missing in the description of the experimental setup, namely whether hyperparameter tuning has been performed (i) for the proposed mod4el and (ii) for the baseline models. Moreover, in section B.2.2 the authors claim that "the detailed hyper-parameter settings on all benchmarks are reported in Tab. S6", however this table only includes hyperparameters for the proposed N2 model and not for baseline methods. I also checked the provided code, which does not cover the baseline experiments.
As it is - despite the claims made in the answer to Q4 in the checklist - I do not consider the results showing superior performance compared to the baseline models reproducible based on the information provided in the paper and in the supplementary material.
[W5] One could argue that the proposed approach to define pseudo-nodes and pseudo-edges that participate in the message passing could also be seen as a learnable graph pooling layer for GNNs, where pseudonodes take the role of supernodes. As such, I believe that the paper lacks a more detailed discussion of related works on (trainable) graph pooling operations (there is a single mention of graph pooling in the first paragraph of the related work section).
[W6] Similarly, while the paper briefly mentions hierarchical Graph Neural Networks as related work that combines local and global message passing to learn multi-scale features, no explicit comparison to such approaches is included in the experimental evaluation.
Questions
I kindly ask the authors to address the following questions, which emerged during my review of the work:
- Please provide more insights on the motivation behind the different ingredients of the dynamic message passing scheme, especially on (i) why the proposed local and global message scheme is supposed to address over-smoothing and over-squashing, and (ii) the motivation of the additional recurrent layer (see comments in [W1] and [W2]). For the first question, I see that there is an experimental analysis but I failed to see how this analysis supports the claims. For the latter question, it would be helpful to include an ablation study that removes the recurrent layer altogether. If I understood the ablation study correctly, currently only the influence of the number of recurrent layers is investigated. Or does the removal of the pseudo-code adaptation (Table 5) correspond to the removal of the recurrent layers?
- Please clarify your contribution over other approaches using adaptive message passing architectures that combine local and non-local message exchanges (see comments in [W3], [W5] and [W6]).
- Please provide details on the choice of hyperparameters and the use of hyperparameter tuning, both for the baseline methods and the proposed architecture (see detailed comments in [W3])
- Please add details on the ablation study results shown in Table 5, especially the number of experimental runs and the standard deviation of results.
- Please increase the font of the results in tables 1 - 4. The text is too small to be readable in a printed version. Please also increase the size of the figures, especially figure 5 and 6, which are way too small to be readable in a printed version.
During my review, I found the following typo:
- line 259: Complex_i_ty Analysis
Limitations
In light of the open questions outlined above, I consider the discussion of limitations in appendix E overly short and not complete.