Probabilistic Graph Rewiring via Virtual Nodes

[SN24]: Southern, J. et al. “Understanding Virtual Nodes: Oversmoothing, Oversquashing, and Node Heterogeneity”, arXiv 2024

[GR24]: Geisler, S. et al., “Spatio-Spectral Graph Neural Networks”, arXiv 2024

[GE23]: Gutteridge, B. et al., “DRew: Dynamically Rewired Message Passing with Delay”, ICML 2023

[BGN22]: Brüel-Gabrielsson, R. et al., “Rewiring with Positional Encodings for Graph Neural Networks”, TMLR 2023

[BA17]: Battaglia, P.W. et al., “Relational inductive biases, deep learning, and graph networks”, arXiv 2018

[BE23]: Banerjee, P.K. et al., “Oversquashing in GNNs through the lens of information contraction and graph expansion”, ALLERTON 2022

[KR22]: Karhadkar, K. et al., “FoSR: First-order spectral rewiring for addressing over-squashing in GNNs”, ICLR 2023

[ARZ22]: Arnaiz-Rodriguez, A. et al., “DiffWire: Inductive Graph Rewiring via the Lovász Bound”, LoG 2022

[VR23]: Velingker, A. et al., “Affinity-Aware Graph Networks”, NeurIPS 2023

[BO24]: Barbero, F. et al., “Locality-Aware Graph Rewiring in GNNs”, ICML 2024

[QN24]: Qian, C. et al., “Probabilistically-Rewired Message-Passing Neural Networks”, ICLR 2024

[PM17]: Pham, T. et al., “Graph Classification via Deep Learning with Virtual Nodes”, arXiv 2017

[LI17]: Li, J. et al., “Learning graph-level representations for drug discovery”, arXiv 2017

[CI23]: Cai, C. et al., “On the connection between MPNN and Graph Transformers”, ICML 2023

[GR19]: Gasteiger, J., Weißenberger, S., and Günnemann, S. "Diffusion improves graph learning." NeurIPS 2019.

[PI20]: Pei, H., et al. "Geom-gcn: Geometric graph convolutional networks." ICLR 2020.

[TG21]: Topping, J., et al. "Understanding over-squashing and bottlenecks on graphs via curvature." ICLR 2022.

[RK22]: Rampášek, L., et al. "Recipe for a General, Powerful, Scalable Graph Transformer." NeurIPS 2022.

[YG21]: Ying, C., et al. "Do Transformers Really Perform Bad for Graph Representation?" NeurIPS 2021.

[NS24-1]: NeurIPS 2024 Reviewer Guidelines

[NS24-2]: NeurIPS 2024 Call For Papers

Comparison with DiffWire [ARZ22] on molecular datasets:

Comparison with various methods (incl. DiffWire, SDRF) on the heterophilic WebKB datasets

Comparison with S2GCN [GR2024] and GatedGCN+VN$_G$ [SN2024] on the long-range peptides datasets.

Runtime comparison with the Drew rewiring method [GE23].

• Connections with [GR24, SN24]: We want to reiterate that [GR24, SN24] were not publicly available at the time of submission. Investigating the connections between IPR-MPNNs and these works would be very interesting. [GR24] is similar to IPR-MPNNs in its virtual node interpretation but differs fundamentally as it uses spectral layers to connect virtual nodes to the base graph, while we use a probabilistic, differentiable k-subset sampling approach to connect the base graph to the virtual graph in a data-driven manner. Our method is also similar to [SN24] since they also employ a form of heterogeneous message-passing. However, they do not use multiple virtual nodes and do not sparsify the connections between the original graph and the virtual nodes. Therefore, the theory in [SN24] is not directly applicable to our probabilistic approach.

We will update the manuscript with a discussion regarding our connections with the two papers.

• Quadratic worst-case complexity: We acknowledge in our Supplementary that the worst-case complexity of our model is quadratic. However, it is quadratic only in the number of virtual nodes, thereby quadratic in the number of original nodes only if the number of virtual nodes is greater or equal to the number of original nodes. If the original graph is complete, MPNNs also have quadratic complexity in the number of nodes. Any rewiring method that might lead to a complete graph is potentially quadratic. This is an improbable scenario for both general rewiring methods and IPR-MPNNs. We demonstrate that using up to 8 virtual nodes provides state-of-the-art performance (Table A5) while remaining sub-quadratic in the number of original nodes. We also analyze performance for up to 30 virtual nodes in Table A9, showing runtime and memory improvements over Graph Transformers even in the worst-case scenario.

• Virtual nodes are bottlenecks: The primary motivation for our probabilistic layer that selectively connects the initial graph to the virtual nodes is to alleviate potential information bottlenecks between the base and virtual graphs. This acts as a sparsification operation, reducing the information transmitted to individual virtual nodes. This is different from [SN24] since they analyze a single virtual node connected to the entire original graph. Our hierarchical, heterogeneous message-passing scheme allows for bigger hidden dimensions for the virtual graph, which can also help alleviate bottlenecks. Empirically, we show that a low number of virtual nodes is sufficient for passing long-range information in most practical scenarios. For example, in the Trees-NeighborsMatch results (Figure A4), IPR-MPNNs perform as well as a Transformer up to a depth of 6, using only two virtual nodes.

We thank the reviewer for the question - this is a very good point, and we will add a more nuanced discussion about possible bottlenecks in the virtual graph in our next paper revision.

• No comparison with [ARZ22]: We compare with publicly available results of various rewiring approaches across multiple datasets: Drew, SPN, and PR-MPNN on QM9 (Table 2); Drew, PR-MPNN, and AMP on LRGB (Table 3); PR-MPNN on ZINC and OGB-Molhiv (Table 4); and FoSR (Table A6). Re-running all possible baselines is very expensive and time-consuming. [ARZ23] contains some results that we can compare with, and we have also performed new experiments with IPR-MPNNs on the heterophilic datasets reported in their paper.

As can be seen in the next official comment, we obtain significantly better results than DiffWire on the molecular and heterophilic datasets.

• No comparisons with [GR24, SN24]: The authors of the two parallel works, which became available after the NeurIPS submission deadline, also report results on peptides. As can be seen in the next official comment, our method obtains overall better scores on the Peptides datasets when compared with [SN24], and is competitive with [GR24], obtaining slightly worse results on func, and slightly better results on struct.

We will update the tables for the revision, including results from [ARZ22, SN24, GR24] in our paper.

• No runtime comparison with other rewiring methods: We compare with one rewiring method (PR-MPNN) in our extended runtime analysis (Table A9 in the Supplementary). Additionally, we include comparisons with the base GINE in both tables as a lower bound for required resources. In all scenarios, IPR-MPNNs' overhead over the base GINE model is generally low (see Table 1 and Table A9).

We have also performed an additional experiment comparing IPR-MPNNs with Drew [GE23]. We fix the same number of message-passing layers with a similar number of parameters, and we run the Drew model from the code provided by the authors on the same hardware. The two methods are comparable, with IPR-MPNNs being slightly faster, with slightly higher memory requirements (please see the next official comment).

We thank the reviewer for their feedback and detailed review.

Due to the space restrictions for the rebuttal, we address related work and novelty comments here, with the remaining concerns, additional results, and the bibliography in other official comments at the same level.

• Q: Related work.

• R: We thank the reviewer for the feedback on our related work sections. We agree that giving a comprehensive overview of current literature is essential. Based on the reviewer's comments, we will improve the related work sections for the final paper.

In the following, we discuss the related work that the reviewer has proposed in detail:

Missing concurrent related work:

• [SN24, GR24]: We would like to point out to the reviewer and the program committee that these are concurrent works that became publicly available on arXiv on 22 May and 29 May, respectively. The NeurIPS Main Conference Paper Submission deadline was 22 May, AoE, so it would have been impossible to include the papers in the related work section at submission time.

Related work proposals that have been discussed:

• [GE23]: This is a key work we compare with, citing and discussing it on lines 35, 101-102, and 253. We compare with Drew on the QM9 dataset (Table 2), where we outperform it on 12 out of 13 properties, and on Peptides-func and Peptides-struct (Table 3), where we outperform it on both datasets.

• [BGN22]: When discussing related rewiring approaches, the first work we mention is [BGN22] (lines 97-98).

• [BA17]: We include related work regarding Hierarchical MPNNs in our Supplementary Materials. We provide an extensive discussion on both hierarchical methods and virtual node-based methods, including Battaglia 2017 (lines 677-678).

• [BE23]: We cite this method on line 106.

• [KR22]: We cite this work on line 35 and briefly discuss it on line 105. We also compare with their FoSR method on the TUDataset collection in Table A6, where we achieve significantly better results on all datasets.

Missing related work:

• [ARZ22, VR23, BO24]: We thank the reviewer for pointing out that this related work is missing.

We will update our manuscript to include the concurrent works of [SN24, GR24] and comparisons with them on the peptides datasets. We will add the missing related work of [ARZ22, VR23, BO24] and expand the discussions on [BE23, KR22].

• Q: Methodology.

• R: We thank the reviewer for their suggestions; in the following, we try to respond to their concerns:

1. Novelty: While probabilistic rewiring [QN24] and the concept of virtual nodes [BA17] have been explored in the past, combining the two concepts is not trivial. As highlighted in our paper, the key difference between the present work and [QN24] is that, unlike [QN24], where the adjacency matrix is modified directly, we keep the original adjacency matrix fixed and "rewire" by learning a $k$-subset distribution from the original graph nodes to the virtual nodes. Moreover, the virtual nodes can have different dimensions, connecting our message-passing scheme to heterogeneous message-passing and hierarchical MPNNs. Unlike existing hierarchical MPNNs that employ virtual/super nodes, e.g., [BA17, PM17, LI17, CI23], our IPR-MPNNs uniquely leverage differential $k$-subset sampling and incorporate hierarchical message-passing in an end-to-end framework. We discuss our connection to hierarchical message-passing and virtual nodes-based methods in the Supplementary materials, lines 663-689.

2. Theoretical guarantees: Our primary goal is to improve the long-range capabilities of MPNNs while keeping complexity, memory usage, and runtimes low. Long-range dependency modeling is affected by over-squashing and under-reaching, but they are not our core theoretical concern. In our work, the theoretical guarantees of expressiveness, along with the over-squashing and under-reaching analyses, indicate where the performance gains might come from.

3. Empirical results might not be generalizable: Our experimental section offers a comprehensive comparison on both real-world molecular datasets (ZINC, OGBG-Molhiv, QM9, Peptides-struct, Peptides-func, PCQM-Contact, TUDataset) and synthetic datasets (Trees-LeafCount, Trees-LeafMatch, CSL, EXP), where we generally achieve state-of-the-art results. Our empirical evidence shows that our method is effective in addressing over-squashing through model sensitivity (Fig. 2), effective resistance (Fig. 3), and the Trees-NeighborsMatch dataset (Fig A4). We also outperform other rewiring methods (Drew, PR-MPNN, AMP) and graph transformers (GPS, Exphormer, GRIT, etc.) on long-range tasks (Table 3) and various molecular datasets (QM9 in Table 2, ZINC and OGB-Molhiv in Table 4, TUDataset in Table A6). Thus, we argue that IPR-MPNNs are an efficient, state-of-the-art class of MPNNs for both common molecular datasets and those requiring long-range interactions, with strong empirical evidence that indicates an alleviation of over-squashing.

4. The paper is not theoretical enough for NeurIPS: NeurIPS Reviewer Guidelines [NS24-1] state that "claims can be supported by either theoretical analysis or experimental results". NeurIPS has historically included many empirical works and remains a generalist conference, suitable for applications and general machine learning topics, as per the NeurIPS 2024 Call for Papers [NS24-2].

We continue addressing the raised methodology issues in the next official comment.

Dear Reviewer 5s4E,

Thank you for your time and efforts throughout the review period. Please read the authors' rebuttal as soon as possible and indicate if their responses have addressed all your concerns.

Best,

Area Chair

We thank the reviewer for their feedback on our work. In the following, we will try to address the concerns raised by the reviewer:

• W1: How are the unnormalized priors $\theta$ obtained? Is there any related optimization objective?

• RW1: The unnormalized priors are the output of the upstream MPNN. Specifically, after some message-passing steps, we use a shared linear readout layer for each node to obtain $\theta$. If we have $N$ virtual nodes, we obtain a $1\times N$ unnormalized prior $\theta$ for each of the original nodes. These priors are then sent to the sampling layer, ensuring exactly $k$ virtual nodes are selected for each original node. There is no related optimization objective for the priors; we estimate the gradients for the sampling layer using an exactly-$k$ gradient estimator (SIMPLE).

• W2: Gradient estimation for graph sampling is not a new topic.

• RW2: We agree that gradient estimation for graph sampling is not novel by itself. We discuss similar approaches in the “Graph Structure Learning” section of Related Work in the Supplementary Materials (lines 636-648). However, our work's novelty lies in leveraging differential $k$-subset sampling for probabilistic rewiring and incorporating hierarchical message passing in an end-to-end trainable framework. We show how this probabilistic framework increases model expressiveness and benefits modeling long-range interactions. Additionally, our work differs from previous approaches by using state-of-the-art $k$-subset sampling algorithms (SIMPLE), while most previous works use $1$-subset sampling and estimate gradients with the Gumbel-Softmax trick.

Regarding possible ablations - we show how the model sensitivity changes when different numbers of virtual nodes are used in Figure 2.

We also provide a new ablation for the number of virtual nodes and samples. Our approach treats the virtual nodes and original nodes as heterogeneous nodes, therefore, for fair comparison, we use the same heterogeneous MPNN on MPNN+VN experiments, without reducing the number of parameters.

In most practical scenarios that we have tested on, having more than 2 samples doesn’t positively affect the performance but can lower the standard deviation between runs. We see that using 4 samples decreases overall performance, but the standard deviation for the 5 runs is much lower.

• W3: Sensitivity analysis is unclear.

• RW3: We detail this on lines 756-758 of our Supplementary Materials. We compute the logarithm of the symmetric sensitivity between the most distant nodes $u$, $v$, i.e., $ln\left(\left| \frac{\partial \mathbf{h}^{l}_v}{\partial \mathbf{h}^{k}_u} \right| + \left| \frac{\partial \mathbf{h}^{l}_u}{\partial \mathbf{h}^{k}_v} \right|\right)$, where $k$ to $l$ represent the intermediate layers. We thank the reviewer for pointing out that this is unclear; we will move these details to the main text of our work for the final version of our paper.

• W4: Runtime comparisons for IPR-MPNN.

• RW4: The paper includes two comparisons. The first, in Table 1, is between the base GINE model, IPR-MPNNs, and the GPS Graph Transformer. We show that our method has similar inference times and memory consumption to the base model, while being significantly more efficient than GPS. The second comparison is in Table A9 in the Supplementary Materials, where we compare various configurations of IPR-MPNN with the base GINE model, variants of the SAT Graph Transformer, GPS, and variants of the PR-MPNN rewiring method. In most cases, we perform better than the other models while maintaining similar performance and memory consumption to the base GINE model.

• Q1: Algorithm table for training IPR-MPNN.

• RQ1: We thank the reviewer for their suggestion; we will include an algorithm table/pseudocode for IPR-MPNN in the final version of our paper.

We want to thank the reviewer for their suggestions and kindly ask the reviewer to increase their score if they are satisfied with our response. We are happy to answer any remaining questions!

[GR19]: Gasteiger, J., Weißenberger, S., and Günnemann, S. "Diffusion improves graph learning." NeurIPS 2019.

[PI20]: Pei, H., et al. "Geom-gcn: Geometric graph convolutional networks." ICLR 2020.

[TG21]: Topping, J., et al. "Understanding over-squashing and bottlenecks on graphs via curvature." ICLR 2022.

[ARZ22]: Arnaiz-Rodríguez, A., et al. "Diffwire: Inductive graph rewiring via the Lovász bound." LoG 2022.

[RK22]: Rampášek, L., et al. "Recipe for a General, Powerful, Scalable Graph Transformer." NeurIPS 2022.

[YG21]: Ying, C., et al. "Do Transformers Really Perform Bad for Graph Representation?" NeurIPS 2021.

[PV23]: Platonov, O., et al. "A critical look at the evaluation of GNNs under heterophily: Are we really making progress?", ICLR 2023

We thank the reviewer for their positive assessment of our work. In the following, we will respond to the raised issues:

• W1: Empirical and theoretical comparison with MPNN + VN.

• RW1: We thank the reviewer for the suggestion. The paper currently contains one such comparison in Table 2 - R-GIN-FA is a Relational GIN model with a fully-connected virtual node. Nevertheless, we also conducted the following experiments with the base model and a fully-connected virtual node, which we will include in the final version of our paper:

Our approach treats the virtual nodes and original nodes as heterogeneous nodes, therefore, for fair comparison, we use the same heterogeneous MPNN on MPNN+VN experiments, without reducing the number of parameters.

The advantages of having sparse, learnable connections over fully-connected virtual nodes are as follows:

• Bottlenecks - The network is less likely to suffer from information bottlenecks in the virtual graph since not all original nodes are connected to the virtual nodes.

• Expressiveness - adding virtual nodes connected to the entire base graph would not make the MPNN more powerful than 1-WL. Consider the following proof sketch:

Assume that we have a graph $G$ with some stable $1$-WL coloring. Now, for each node $v$ we recursively unroll the neighborhoods into a rooted tree of sufficient depth. The isomorphism type of this tree is $1$-to-$1$ to the stable color of node $v$. Now, if we consider all vertices, we have a forest of unrolling trees. We create a new vertex (the virtual node) and connect the roots of the trees in the forest to this new vertex. Then, the isomorphism type (of this forest) is $1$-to-$1$ to the isomorphism type of the original graph modulo $1$-WL; therefore, if some other graph with a virtual node has the same $1$-WL coloring, the two graphs remain indistinguishable.

On the other hand, we can attach the virtual node to the original graph and unrolling from the virtual node. However, this tree will be isomorphic to the above constructed tree (forest + root vertex). Therefore, the graphs remain indistinguishable.

We will add a more nuanced discussion regarding the comparison with other virtual node approaches in the final version of our paper.

• W2: Would the approach be practical for large graphs?

• RW2: We thank the reviewer for pointing out the inconsistency. We have performed new experiments on heterophilic datasets, which have a significantly greater number of nodes per graph. We report here the results:

Moreover, we also report results on the newly-introduced heterophilic datasets from [PV23]. These datasets contain more challenging scenarios and have a significantly higher number of nodes per graph (22K for roman-empire, 11k for tolokers, 24k for amazon-ratings, 10k for minesweeper). We can run all IPR-MPNN experiments with a memory consumption of at most 10GB.

• Q1: Why do we see improvements over GTs?

• RQ1: This is a great question. We posit that the improvements come from having a stronger graph inductive bias than most GTs, where the graph is assumed to be complete. By performing all of our computations using message-passing, we keep a strong inductive bias, while the virtual nodes with learnable connections act similarly to a hard, sparse attention mechanism, thereby allowing for long-range messages to be passed while still maintaining a strong locality bias. Graph Transformers might be able to replicate this method, assuming a sparsification of the attention matrix, with a bias towards the GT “latent graph” being more similar to the original graph, thereby maintaining a better graph bias.

• Q2: How many virtual nodes are used?

• RQ2: In Table A5 from the Supplementary Materials, we report the number of virtual nodes used for most experiments. A low number (2-8 virtual nodes) is effective for most tasks.

We want to thank the reviewer for their suggestions and kindly ask the reviewer to increase their score if they are satisfied with our response. We are happy to answer any remaining questions!

[GR19]: Gasteiger, J., Weißenberger, S., and Günnemann, S. "Diffusion improves graph learning." NeurIPS 2019.

[PI20]: Pei, H., et al. "Geom-gcn: Geometric graph convolutional networks." ICLR 2020.

[TG21]: Topping, J., et al. "Understanding over-squashing and bottlenecks on graphs via curvature." ICLR 2022.

[ARZ22]: Arnaiz-Rodríguez, A., et al. "Diffwire: Inductive graph rewiring via the Lovász bound." LoG 2022.

[RK22]: Rampášek, L., et al. "Recipe for a General, Powerful, Scalable Graph Transformer." NeurIPS 2022.

[YG21]: Ying, C., et al. "Do Transformers Really Perform Bad for Graph Representation?" NeurIPS 2021.

[PV23]: Platonov, O., et al. "A critical look at the evaluation of GNNs under heterophily: Are we really making progress?", ICLR 2023

Q1, Q2: New experimental results on the WebKB heterophilic datasets and on the heterophilic datasets proposed in [PV23]:

Q4: Reduced runtime report, also available in Table A9 of the Appendix:

Q6: Table comparing a virtual node connected to the entire graph (1VN - FC) with IPR-MPNN with two virtual nodes, one sample (2VN1S), two samples (2VN2S) and four samples (2VN4S)

We thank the reviewer for their assessment and feedback. In the following, we respond to the reviewer’s questions. Please note that the tables containing new experiments are in the next official comment and the pdf file attached to the “Global Response”.

• Q1, Q2: Do IPR-MPNNs increase the risk of over-smoothing? Experiments on node-level tasks would strengthen the paper.

• R1, R2: The reviewer raises a valid concern. Over-smoothing happens when nodes close to each other collapse to similar representations after several message-passing steps.

We provide intuitive arguments and empirical results showing our method does not increase the risk of over-smoothing:

• Over-smoothing is more likely if the virtual complete graph connects to the entire original graph since all nodes would get the same embedding from the virtual nodes during the final update. We sparsely connect original nodes to virtual nodes, which can be seen as a clustering step. This allows distant nodes of the same class to directly pass messages via the same virtual node, potentially reducing over-smoothing when compared to using virtual nodes connected to the entire graph. Therefore, it should be easier to find IPR-MPNN configurations that better handle heterophilic, long-range tasks.

• To empirically address the reviewers' concern and to verify whether IPR-MPNNs can deal with node classification, we perform experiments on the WebKB datasets and some newly-proposed heterophilic datasets [PV23], which contain node classification tasks in heterophilic scenarios. We generally outperform the methods we compare with. We leave the results in the next official comment.

Thank you for your question. We will update the manuscript to include a discussion on over-smoothing and the new experiments, showing improvements over baselines on heterophilic, node-level tasks.

• Q3: The benefits and drawbacks of sampling are unclear.

• R3: We thank the reviewer for raising the concern about clarity. In the following, we will try to highlight the benefits and drawbacks of sampling:

• Benefits: the main advantage of sampling is obtaining multiple virtual node assignments for the base nodes. They can then be used to obtain different final embeddings for the same graph. From an optimization perspective, sampling multiple configurations makes it easier for the upstream model to explore the combinatorial solution space. From a representation perspective, it effectively augments the data with multiple virtual node configurations. As the reviewer pointed out, this could function similarly to multi-head attention with shared parameters.

• Costs: we add all of the sampled configurations to the same batch, feeding the batch to the downstream model. The sample embeddings are computed in parallel, and the downstream parameters are shared. The overhead for this is typically low. The computation times for multiple samples and multiple virtual nodes are available in Table A9 in our Supplementary material. We leave the tables in the next official comment for convenience.

In scenarios with 2-4 virtual nodes and 1-2 samples, our method greatly improves computation time over GraphGPS, with memory usage similar to GINE. Even with 30 virtual nodes and 20 samples, we remain faster and more memory-efficient than GraphGPS.

• Q3.2: It is unclear how to ensure that the union of the inverse assignments covers the entire set of original nodes.

• R3.2: We thank the reviewer for pointing out that this is unclear. When sampling virtual nodes, we sample exactly $k$ virtual nodes for each of the original nodes; therefore, each original node will have connections to exactly $k$ nodes in the virtual graph. We will clarify the text on lines 183-191 in the camera ready: “(...) where each original node $v\in V(G) := [n]$ is assigned to $k \in [m]$ virtual nodes, therefore, all of the nodes in original graph will have exactly $k$ edges connecting to the virtual graph.”

• Q3.3: The C(G) set of virtual nodes is not well defined.

• R3.3: Thank you for pointing to this unclarity. The virtual node set C(G) is a set of new nodes that form a complete virtual graph - we will expand the text on lines 183-191 for the next revision: “and a fixed, new virtual node set $C(G):=[m]$ of cardinality $m$”

• Q4: Runtimes with respect to the number of samples.

• R4: We report runtimes based on the number of samples and virtual nodes in Table A9 of our Supplementary materials. We will move some results from the Appendix to the main paper for the final revision.

• Q5: $H^{(q)}$ and $h^{(t)}$ are a confusing notation.

• R5: Thank you for highlighting the unclear notation. $H^{(q)}$ represents the matrix of new connections between original and virtual nodes, while $h^{(t)}$ represents the hidden embeddings of the original nodes after $t$ message-passing layers. We will clarify this in the final version.

• Q6: Optimal hyperparameters and ablation studies.

• R6: The hyperparameters used in our experiments are in Table A5 of the Supplementary materials. We also conducted new experiments with a virtual node connected to the entire virtual graph and with two virtual nodes, sampling one, two, or four configurations. Please see the next official comments for the results.

In most practical scenarios that we have tested on, having more than 2 samples doesn’t positively affect the performance but can lower the standard deviation between runs. We see that using 4 samples decreases overall performance, but the standard deviation for the 5 runs is much lower.

Once again, we thank the reviewer for their suggestions, and we kindly ask the reviewer to increase their score if they are satisfied with our response. We are happy to answer any remaining questions!

Dear Reviewer UsNW,

Thank you for your time and efforts throughout the review period. Please read the authors' rebuttal as soon as possible and indicate if their responses have addressed all your concerns.

Best,

Area Chair

We thank the reviewer for their suggestion.

While our method is not tailored to alleviate over-smoothing, we agree that having evidence that our model does not increase the phenomena of over-smoothing is beneficial.

We have measured the Dirichlet Energy of the final layer on the heterophilic WebKB Cornell, Wisconsin, Texas datasets and on the roman-empire dataset from [PV23]. We compare IPR-MPNN with the base GINE model.

The results are averaged for 5 runs, and we also report the standard deviations:

As can be observed, IPR-MPNNs have higher Dirichlet Energy on Cornell, Wisconsin, Texas and significantly higher on roman-empire, indicating that over-smoothing is alleviated for these datasets.

Please note that IPR-MPNN also obtains much better overall results on these datasets (see previous comment).

We will add these results to the final version of the paper. Overall, the empirical evidence indicates that IPR-MPNNs do not increase over-smoothing, but they rather slightly alleviate the phenomena.

Thank you for helping us improve our work. We kindly ask the reviewer to reconsider their assessment and increase their score if they find our response convincing. We are open to answering any remaining questions if time permits.