Understanding Virtual Nodes: Oversquashing and Node Heterogeneity
Authors: Joshua Southern
Francesco Di Giovanni
Michael M. Bronstein
Johannes F. Lutzeyer
Venue: ICLR 2025 Poster (2025)
Keywords: Graph Neural Networks
Message Passing
Virtual Nodes
Oversquashing
Graph Transformers
Primary area: learning on graphs and other geometries & topologies
TL;DR: We study the benefits of adding Virtual Nodes to Message Passing Neural Networks through the lenses of oversquashing and learning heterogeneous node importance.

Abstract: While message passing neural networks (MPNNs) have convincing success in a range of applications, they exhibit limitations such as the oversquashing problem and their inability to capture long-range interactions. Augmenting MPNNs with a virtual node (VN) removes the locality constraint of the layer aggregation and has been found to improve performance on a range of benchmarks. We provide a comprehensive theoretical analysis of the role of VNs and benefits thereof, through the lenses of oversquashing and sensitivity analysis. First, we characterize, precisely, how the improvement afforded by VNs on the mixing abilities of the network and hence in mitigating oversquashing, depends on the underlying topology. We then highlight that, unlike Graph-Transformers (GTs), classical instantiations of the VN are often constrained to assign uniform importance to different nodes. Consequently, we propose a variant of VN with the same computational complexity, which can have different sensitivity to nodes based on the graph structure. We show that this is an extremely effective and computationally efficient baseline for graph-level tasks.

Published as a conference paper at ICLR 2025
UNDERSTANDING VIRTUAL NODES: OVERSQUASHING AND NODE HETEROGENEITY
Joshua Southern' 1:s,, Francesco Di Giovanni 2 Michael Bronstein and Johannes F. Lutzeyer
Imperial College London University of Oxford AITHYRA 4 LIX, École Polytechnique, IP Paris
ABSTRACT
While message passing neural networks (MPNNs) have convincing success in a range of applications, they exhibit limitations such as the oversquashing problem and their inability to capture long-range interactions. Augmenting MPNNs with a virtual node (VN) removes the locality constraint of the layer aggregation and has been found to improve performance on range of benchmarks. We provide com- prehensive theoretical analysis of the role of VNs and benefits thereof, through the lenses of oversquashing and sensitivity analysis. First, we characterize, precisely, how the improvement afforded by VNs the mixing abilities of the network and hence mitigating oversquashing, depends on the underlying topology. We then highlight that, unlike Graph-Traae Traph-TTranformers (GTs), classical instantiations of the VN are often constrained to assign uniform importance to different nodes. Con- sequently, we propose variant of VN with the same computational complexity, which can have different sensitivity to nodes based on the graph structure. We show that this is an extremely effective and computationally efficient baseline for graph-level tasks.
INTRODUCTION
Graph Neural Networks (GNNs) (Scarselli et al., 2009; Gori al., 2005; Micheli, 2009) are popular framework for learning on graphs. GNNs typically adopt message passing paradigm (Gilmer et al., 2017), in which node features are aggregated over their local neighborhood recursively, resulting in architectures known as Message Passing Neural Networks (MPNNs). Whilst MPNNs have linear complexity in the number of edges and an often beneficial locality bias, they have been shown to have several limitations. In terms of expressivity, they are at most as powerful as the Weisfeiler- Leman test (Weisfeiler Leman, 1968; Morris al., 2019; Xu et al., 2018) and cannot count certain substructures (Chen et al., 2020; Bouritsas et al., 2023). Besides, the repeated aggregation of local messages can either make node representations indistinguishable-a process known as 'oversmoothing' (Nt & Maehara, 2019; Oono & Suzuki, 2020) or limit the models' ability to capture long-range dependencies a phenomenon called 'oversquashing' (Alon & Yahav, 2021).
In particular, oversquashing strongly depends the graph-topology. since describes the inability of MPNNs to reliably exchange information between pairs of nodes with large commute time (Di Giovanni al., 2024). To overcome this limitation, methods have moved away from only performing aggregation over the local neighborhood and instead have altered the graph connectivity to reduce its commute time. Common examples include variations of multi-hop mnessgee-psssngg (Nikolentzos et al., 2020; Wang et al., 2020; Gutteridge et al., 2023), adding global descriptors (Horn al., 2022), or rewiring operations based on spatial spectral quantities (Topping et al., 2022; Emaii-RRodiguu et al., 2022). A notable case is given by Graph-Transfome Transformers (GTs) (Kreuzer et al., 2021; Ying et al., 2021), where global attention used to weight the messages of each node pair.
"jks10icc. ac. uk I These authors contributed equally.

---

Published as a conference paper at ICLR 2025
Virtual Nodes. While GTs incur a large memory cost, significantly more efficient method that incorporates global information in each layer to combat oversquashing, is adding a virtual node (VN) connected to all nodes in the graph (Pham et al., 2017). This is widely used in practice (Gilmer et al., 2017; Battaglia et al., 2018) with empirical successes (Hu et al., 2020; Hwang et al., 2022). However, besides recent work connecting VNs to GTs (Cai et al., 2023; Rosenbluth al., 2024), few efforts have been made to analyze in what way and to which extent VN improves the underlying model.
Contributions. We propose a theoretical study of VNs through the lenses of oversquashing and sensitivity analysis and highlight how they differ from approaches based on Graph- ToaphhTTranfffmmrss Our analysis sheds light on the impact VNs have on reducing oversquashing by affecting the commute time, and the gap between VNs and GTs in terms of the sensitivity to the features of other nodes. Specifically, our main contributions are the following:
In Section 3 we provide the first, systematic study of the impact of VNs the oversquashing phenomenon. We show that, differently from more general rewiring techniques such as GTs, the improvement brought by VNs to the mixing abilities of the network, can be characterized and bounded in terms of the spectrum of the input graph.
Relying on sensitivity analysis of node features, in Section we find a gap between VNs and GT's in their ability to capture heterogeneous node importance. Our theory motivates a new formulation of MPNN + VN, denoted by MPNN VNg. that better leverages the graph structure to learn heterogeneous measure of node relevance, at no additional cost.
Finally, in Section 5, we first validate our theoretical analysis through extensive ablations and experiments. Next, we evaluate MPNN VNG and show that it consistently surpasses the baseline MPNN + VN, precisely on those tasks where node heterogeneity matters.
We moreover want to remark that in Appendix we make a further contribution, where we compare the expressivity of MPNN + VN and anti-smoothing techniques through polynomial filters. This allows us to contest prior belief that a reason for the success of MPNN + VN is their ability to simulate methods that prevent oversmoothing and to observe cases of 'beneficial smoothing' of node representations towards the final pooled representation. Since, this study could be considered to be of limited impact due to it being conducted in a linear setting, i.c., in absence of activation functions in the MPNN, we have chosen to not focus on this aspect of our work in this paper and only provide it in the appendix for especially interested readers.
2 PRELIMINARIES AND RELATED WORK
Message Passing Neural Networks. Let G = (V, E) be an unweighted, undirected and connected graph with node set V and edge set E. The connectivity of the graph is encoded in the adjacency matrix A E g=*n, where = [V], and the l-hop neighborhood of a node is N; (i E V (j, e E}. Furthermore, node features {h, : : E V) C Rdd are provided as input. Message passing layers are defined using learnable update and aggregation functions up and agg as follows
(C-1) u0 (n agg! (14)))
(f) :j E N,))),
where (1()) is the feature of node at layer l, up is learnable update function (typically an MLP) and agg is invariant to node permutations. Below, we refer to models described as in (1) as MPNNs
Limitations of MPNNs. Aggregating information over the 1-hop of each node iteratively, leads to systematic limitations. MPNNs without node identifiers (Loukas, 2019) are not universal (Maron et al.. 2018) and are at most as powerful as the 1-WL test in distinguishing graphs (Morris et al., 2019; Xu et al., 2018). Additionally, when the task depends on features located at distant nodes (i.e. long-range interactions), MPNNs suffer from oversquashing, defined as the compression of information from exponentially growing receptive fields into fixed-size vectors (Alon & Yahav, 2021). In fact, oversquashing limits the MPNN's ability to solve tasks with strong interactions among nodes at large commute time (Di Giovanni et al., 2023a; Black et al., 2023; Di Giovanni et al., 2024). Finally, MPNNs may incur oversmoothing, whereby node features attain the same value as the number of layers increases (Nt & Maehara, 2019; Oono & Suzuki, 2020; Cai & Wang, 2020).
Graph Transformers (GTs). An extension of the MPNN-class is given by Graph-Treee Transformers (GTs) (Kreuzer et al., 2021; Rampášek et al., 2022; Ying et al., 2021; Hussain et al., 2022; Wu et al.,
2

---

Published as a conference paper at ICLR 2025
2021; Chen et al., 2022), where a global attention mechanism connecting all pairs of nodes augments (or entirely replaces (Ma et al., 2023)) the I-hop aggregation in MPNNs. GTs increase the expressive power of MPNNs by heavily relying structural and positional encodings (Dwivedi et al., 2021), and entirely bypass the issue of oversquashing since the global attention breaks all potential bottlenecks arising from the graph topology. This comes price though, with GT's incurring quadratic memory cost and being sensitive to the choice of positional (structural) encodings. Furthermore, removing the locality constraint of MPNNs can cause GTs lack strong inductive bias which can lead poor performance (Ma et al., 2023). To overcome this, Rampášek et al. (2022) combined a global attention mechanism with local message passing which led to improvements across multiple benchmarks. Their results suggest that maintaining the local inductive bias within message-passing is critical but that self-attention can improve performance further by capturing long-range interactions.
MPNNs With Virtual Nodes. An alternative approach to enhancing MPNNs without leading to the significant memory costs of GTs, consists in introducing a virtual node (VN) connected to all other nodes in the graph (Gilmer et al., 2017: Battaglia et al., 2018). A standard formulation of message passing with virtual nodes (Cai et al., 2023), referred to as MPNN + VN in the following, is:
A up ( aggun tn (9 j
n. (t-1) (n agg 10 (()))
(1)
:j jE E (
The class MPNN + VN extends MPNNs (1) to a multi-relational graph Gyn obtained by adding a VN connected to all E V, where any new edge is distinguished from the ones in the input graph.
Understanding VN: Open Questions and Challenges. Augmenting MPNNs with VNs has often been shown to improve performance (Hwang et al., 2022; Sestak et al., 2023). Nonetheless, careful analysis of how and when VNs help is still lacking. Key related work was done by Cai et al. (2023), which relied the universal approximation property of DeepSets (Segol & Lipman, 2020) to show that MPNN + VN with hidden state dimensions of (nn)) and (1) layers can approximate a self-attention layer. Their argument though discards the topology and holds in non-uniform regime, raising questions about its practical implications. Crucially, VNs are mainly added to networks so as to model non-local interactions, as follows from (2) where any node pair is separated by most hops through the VN. Nonetheless, neither a formal analysis on the extent to which MPNN + VN mitigates oversquashing, nor tine-grained comparison between GTs and MPNN VN in terms of sensitivity analysis (i.e. interactions among node features in a layer), have been conducted so far.
Outline of This Work. We provide systematic study of MPNN + VN through the lenses of oversquashing and sensitivity analysis. We show that: The improvement brought by VN in mitigating oversquashing depends on the spectrum of the graph (Section 3); Differently from GT's, the sensitivity of VN to distinct node features is often uniform, and hence we propose VNg. a new formulation of VN that can learn heterogeneous node importance at no additional cost (Section 4); The framework VNG consistently improves over VN, closing the empirical gap with GTs (Section 5).
Graph-Level Tasks. In this work, we focus on graph-level tasks; this way, we can compare the mixing abilities of MPNN + VN with that of MPNN, as per the graph-level analysis in Di Giovanni et al. (2024). Graph-level benchmarks (both classification and regression) offer a comprehensive test bed compare VN and GTs,, which is aligned with similar evaluations (Gutteridge et al., 2023; Barbero et al., 2024). Nonetheless, we emphasize that the statements in Section 4 hold layerwise, and hence do not depend on whether the task is graph-level or not; additionally, we can extend the results in Section 3 to node-level tasks following (Di Giovanni et al., 2024, Appendix E).
3 MPNN VN AND OVERSQUASHING
VNs are often added to alleviate oversquashing, by reducing the diameter of the graph to 2. However, no formal analysis on the improvement brought by VNs to oversquashing has been derived thus far. In this section, we fill this gap in the literature and characterize how the spectrum of the input graph affects the impact of VN to commute time and hence the mixing abilities of the network. To study
3

---

Published as a conference paper at ICLR 2025
oversquashing, analyze general realizations of (2), whose layer updates have the form:
h(+11 o
Σ
dle (h (om.hhn))) n)
+
ñ
10) 4 ((+1)) (
Σ A A0 ( (1 + u (1 (1))))))))))
+
(3)
where is a pointwise nonlinear map, A (potentially) normalized adjacency matrix, Z2 is weight matrix, v, viv Ovn are (learnable) message functions, and á depends on our normalization choice (e.g. ń for sum, ñ n for mean). A key observation is that (3) coincide with the MPNNs analyzed in Di Giovanni et al. (2024), but operating on the multi-relational graph Gvn with adjacency
A A. = T 1).
1- (1, 1)T E ERR
where edges connecting VN to nodes in have different type. Di Giovanni et al. (2023a); Black et al. (2023); Di Giovanni et al. (2024) have shown that oversquashing prevents the underlying model from exchanging information between nodes at large commute time r, where r(i, measures the expected number of steps for random walk to commute between and j. Accordingly, to assess if and how a VN helps to mitigate oversquashing, we need to determine whether the commute time Tun of Gwn is smaller than the commute time of the original graph G. Below, we let Us be orthonormal basis of eigenvectors for the graph Laplacian L = D A, with associated eigenvalues 0= Ao < \1 ... An-1. The proof of the following Theorem and all subsequent results, can be found in Appendices E and F.
Theorem 3.1. The commute time between nodes i.j after adding a VN changes as
R-1
- ((..) = 2 2|
Σ
( de - 1) (ve(1) - ve)
n
(5)
xe(Ae +
In particular, the average change in commute time is:
n
4 Σ
FE d - 1).
(6)
2
n de(Ae + 1)
1
The result in Theorem 3.1 highlights how the impact of adding a VN can be determined in terms of the spectrum of the input graph. While there are cases, e.g. when the graph is complete, where (6) is positive, for many real-world graphs adding a VN reduces the overall commute time: We empirically validate this claim in Section 5. Note that we prove Theorem 3.1 by calculating the explicit analytical form of the effective resistance between two nodes in Gvn We then exploit the fact that the commute time between nodes proportional their effective resistance. So, Theorem 3.1 can be trivally extended to make equivalent statements about the effective resistance between nodes instead of their commute time.
In our subsequent analysis we will make use of the notion of mixing, which was introduced by Di Giovanni et al. (2024). We begin by recalling its formal definition in Defintion 3.2.
Definition 3.2 (Di Giovanni et al. (2024)). The quantity (ix is the mixing induced by graph-level function among the features of nodes i and j. and is defined as
8 (H)
mix, = max max H 15a.85d
ahş
Di Giovanni et al. (2024) made use of the mixing notion to formally assess the amount of interactions between i and j required by the underlying task, and compared it to the mixing induced by the MPNN prredcttni after m layers. In particular, they proved that oversquashing prevents MPNNs of bounded depth from solving tasks with required strong mixing between nodes at large commute time. Below, 'bounded weights' means that weight matrices and message functions derivatives have bounded spectral norms see Appendix E for details.
4

---

further compare Published as a conference paper at ICLR 2025
Theorem 3.3 (Adapted from Thm. 4.4 (Di Giovanni al., 2024)). There graph-ffnctions with mixing between nodes + j larger than some constant independent i. such that for an MPNN of bounded weights to learn these functions, the number of layers must satisfy m 7(i.5)/8.
For real-world graphs like peptides, small molecules, or images, (5) is negative (see Section 5.1). In light of Theorem 3.3, this means that adding VN should reduce the minimal number of layers required to learn functions with strong mixing between nodes.
According to Di Giovanni et al. (2024), when the mixing induced by the MPNN after m layers, denoted here as mix (). is smaller than the one required by the downstream task, then we have an instance of harmful oversquashing which prevents the network from learning the right interactions necessary to solve the problem at hand. We make this connection explicit in Corollary 3.4, in which we use Theorem 3.1 to characterize the improvement brought by a VN in terms of the spectrum of the Laplacian.
Corollary 3.4. Given G and nodes i, for which (5) is negative, there are graph-functions with mixing between i + j larger than some constant independent j. such that for an MPNN + VN of bounded weights to learn these functions, the minimal number of layers m becomes
Tun (1,
|
Σ t=1 de
Y1 do
>e (v=(() -o(i))²
1)
m
8
E
The result in Corollary 3.4 shows that for real-world graphs where adding VN significantly reduces the commute time-i.e., (5) is negative-the minimal number of layers required by MPNN + VN to learn graph functions with strong mixing among j. smaller than that of MPNN. This is the first result showing the extent to which MPNN + VN alleviates oversquashing by increasing the mixing abilities of the network. Crucially, MPNN + VN cannot do better than Corollary 3.4, meaning that their efficacy is function of the spectrum. While this implies that MPNN + VN may be sub-optimal, when compared to graph rewiring techniques such as GTs which can modify the commute time arbitrarily, the overall benefits of VN stem from their ability to reduce the commute time and hence mitigate oversquashing at very limited memory cost. We discuss next how we can further refine the formulation of VN to further close their gap with GTs, without increasing the computational complexity.
4 COMPARING MPNN + VN AND GTs THROUGH SENSITIVITY ANALYSIS
In Section 3 we showed that MPNN + VN can mitigate oversquashing and the extent to which this possible. Another successful approach for combating oversquashing is given by Graph Transformers (GTs), that can entirely rewire the graph through the attention module. In fact, MPNN + VN are often used more efficient alternative to GTs (Cai et al., 2023). In this section MPNN + VN and GT's through sensitivity analysis and show that the single layer of a GT can learn heterogeneous node scoring, while MPNN + VN generally cannot. In light of this analysis, propose a simple variation of MPNN + VN, called MPNN + VNG. which better uses the graph to learn heterogeneous measure of node relevance while retaining the same efficiency as MPNN + VN. In our sensitivity analysis we will show MPNN + VNg to fall inbetween the fully homogeneous MPNN VN and the potentially fully heterogeneous GTs.
MPNN + VN Layers Are Homogeneous. We start by reporting the layer update of the GPS architecture (Rampášek al., 2022), one instance of the GT class that encodes both local and global information:
h
((-1) - ((0 (e+1) + Q Σ aa( 10 )6())
(8)
where ʃ is an MIP, Moc is the local update given by the choice of MPNN, and a is the attention module. Depending on the available data and the chosen positional encoding scheme, GT' can capture heterogeneous relations. We can quantify such heterogeneity in sensitivity analysis by deriving that the Jacobian oh ( /ah( is, in general, function that depends on k, meaning that the state of node at layer l + is affected by the state of a node k at the previous layer, as a function varying with k. Conversely, MPNN + VN depends on different nodes more uniformly. Explicitly, consider an MPNN + VN as in (3), where the VN update is
A (E+1) = a (S2(() (1) (0 + w(( Mean ((hg)((h)))) (6)4)) (1(00) {)). pn
(9)
5

---

Published as a conference paper at ICLR 2025
To exemplify the standard definition of VNs, now provide the model equations of a GCN + VN.
1(++1 = ( (
w vn
+
1=1
n ((+1) = [
+ E JEN,
w + k
(10)
ddzdz
where di denotes the node degree of node and 2 W W(O denote trainable weight matrices. Given node i at a distance larger than 2 from node i, any message from node k at layer & - 1 is first received by node: at layer l + through the VN.
Proposition 4.1. For MPNN + VN whose VN update (9), the Jacobian δh (++1) / /an(-1) is independent of k whenever k and i are separated by than 2 hops.
(f-1)
We see that node i receives a global yet homogeneous update from the VN, where the feature each node & at distance greater than 2 contribute the same node i's representation (after two layers). This in stark contrast to the case of GTs.
MPNN + VNG: A New Formulation Of VN. Inspired by frameworks such as (8), allowing for more heterogeneous sensitivity through the VN, we propose MPNN + VNg. a simple variation to MPNN VN with the same computational complexity, ( + n). with layer updates of the form:
(f+1) h i,oe = up (f agg (0 ((h) (1) : E N,))),
(11)
((+1) = up ( (1 aggvn (1) (f+1)
([",,
: E V))),
(12)
1 (e+1) up (n (e+1)
(nie Nn (6+1)).
(13)
Differently from MPNN VN in (2), we first compute local updates based the choice of aggrega- tion (i.e. the underlying MPNN model) in (11), then we compute a global update through VN using such local representations in (12) (as illustrated in Appendix J), and finally we combine the local and non-local representations in (13). This asynchronous interleaving between a local and global update was previously shown have a practical performance improvement over combining these updates in parallel (Rosenbluth et al., 2024; Yin & Zhong, 2023). To theoretically justify this improvement in our setting, we show how MPNN + VNG can assign more heterogeneous values the global updates associated with the VN, by studying the sensitivity of node features. Similarly to (3) and (9), we consider an instance of MPNN + VNg of the form:
1 V,
(f+1)
= (12 (
+
Σ
00 11)))
JEN;
n (++1) = h i,Jo Mean( (ean((Q(e (++
(e+1)
(ean(((((+)))))) jo 1).
(e+1))
(14)
To further exemplify our MPNN + VNG model, and in direct correspondonce to (10), we provide the explicit model equations for GCN+VNg model now. Please note that in our experiments in Section 5 mostly work with the GatedGCN+VN and GatedGCN+VNc models. We provide the corresponding, slightly more complex, model equations in Appendix F.
((+1) h ileee = a
Σ
1
w(0)
dad,
JEN,
ng ((+1)
11 (e+1) Mean (
((22))))
j,uc
Differently from (2), two nodes now can exchange information after a single layer. Below, we let 2 be the argument of a in (14), for each E V, and V. be the Jacobian with respect to variable s.
Proposition 4.2. Given E V and k V \ Nr, the Jacobian oh (L+1)
ahe(t)) johl computed using (14) is
oh 1 (dagg(o(2)) (z ())) (2) n ah
Avie (1 (9) (() diaag(o (=())) V2 (n())
N

---

Published as a conference paper at ICLR 2025
Peptides-Func
Normalized Densiyy
-400 Averaçe Change Commute Time
-800
-600
Average Change Commute Time
MNIST
CIFARID
Normal aed Denily
-35
-10
-25
-20
-10
3-100
-90
-50
-00
Average Change Commute Time
Average Change Commute Time
Figure 1: Effect of adding virtual node the average commute time of four graph datasets.
We that the sensitivity of node to the feature of l is function of the graph-topology. i.e., the message functions evaluated over the neighbors k. In particular, our proposed variation MPNN VNg uses the same message functions bay learn heterogeneous global update. Related to recent advances in graph pooling (Ranjan et al., 2020; Lee et al., 2019; Grattarola et al., 2022: utilize the graph structure in the global aggregator; nodes that are more
Bianchi Lachi, 2023), relevant to each of their neighbors, are more likely to contribute more to the global update, instead of weighting each node the same as for MPNN VN. We note that advantages of this approach depend on the choice of the underlying message function và in (14) (see Table 8 in Appendix I).
interesting to note that the derivative in Proposition 4.2 does not depend on the index i of the central node. If such dependence was present, we would be working with model that was essentially equivalent to a GT since the derivative of given node depended both on i and the currently considered neighbor & (as shown in Proposition F.1 in Appendix F).
In light of our sensitivity analysis, we argue that for those tasks where an empirical gap between MPNN VN and GT can be found, this is due to the latter leveraging its ability to assign heteroge- neous node scores in its global update. Conversely, when no significant gap arises, we claim this is due to the task not requiring heterogeneous node scores. We validate these points in Section 5.1.
EXPERIMENTS
The purpose of this section to first empirically verify the theoretical claims made in Sections 3 and 4. Then, we evaluate our proposed MPNN VNg diverse set of benchmarks in Section 5.2.
5.1 ABLATIONS
Our ablations aim validate the previous theoretical results, by answering the following questions:
Q1) How does adding a VN affect the average commute time on real-world graphs? [$3]
(Q2) Which tasks show gap between MPNN + VN and GT due node heterogeneity? [$4]
To answer (Q1) we calculated (6) on 100 graphs from four commonly used real-world datasets covering peptides, small molecules and images. The distribution of the change of commute time across these four datasets is shown in Figure/ and highlights the tendency for this change to be negative. This result demonstrates that adding VN is highly beneficial real-worlh graphs since it significantly reduces their commute time, thereby increasing their mixing abilities as per Corollary 3.4.
7

---

Published as a conference paper at ICLR 2025
Table Effects of projecting the non-local part of GPS onto the mean and its comparison to using VN. Arrows indicate if the performance improves with higher (t) or lower (1) scores. We also report the standard deviation of the column sums in the first attention layer.
Method
Pept-Func (1)
Pept-Struct (4)
MNIST (1)
CIFARTO (1)
GPS
0,6534 = 000011
0.2509 +. 4.0014
98.051
#.126
72.298 2.356
GPS projection
0.6498 +.0054
0.2487 4.0011
98.176 120
71,455 1.513
GatedGCN+PEAAVN
0.6712 0000
0.2481 4.0015
98.122 101
70.280 2.380
std attention layer
0.0011
0.0007
0,0006
0.0038
We next aim to provide an empirical justification for the similar performances of MPNN+ and GT (Cai et al., 2023) and answer (Q2). To measure the heterogeneity of node relevance in the global update, we look at the similarity between the rows of the attention matrix in GT. In fact, similar rows in a(h; h
(6)
(8) correspond to assigning similar weights each node representation. and hence less heterogeneity. To measure this, we calculate the mean standard deviation (std) of each column in a(h! (4) n)2). We calculate this std on the first layer attention matrix, after training GPS with a GatedGCN as the base MPNN, on four real-world benchmarks from (Dwivedi et al., 2022) and (Dwivedi et al., 2023). In Table 1, we can see that for datasets where the std is small (Peptides-fune Peptides-struct, MNIST), using an MPNN + VN can match or even improve over the GPS implementation. On the other hand, CIFARIO has larger std, and we see that GPS outperforms the VN architecture. These results show that the performance gap between MPNN + VN and GT' related to whether node heterogeneity is used by the GT on the benchmark, considering that MPNN VN assigns equal sensitivity to different node features (Proposition 4.1). To further show the differences in the attention matrices and the amount of homogeneity on these tasks, we have visualized them in Appendix K. Additionally,
can measure the importance of heterogeneity for the task by removing the heterogeneity in the GT and seeing if we lose performance, We can do this in the GPS framework by setting all the rows of the attention matrix be equal to their mean. We call this GPS + projection, and it forces the GPS model to become completely homogeneous. Again, we that datasets where the homogeneous matrix columns is low, we do not lose much performance with this mean projection. Whereas on CIFARIO 10, we find that the heterogeneity of nodes important.
CatedGCN+VN does well and the std of the attention
5.2 EVALUATING OUR PROPOSED MPNN + VNG
We first evaluate MPNN + VNG on diverse set of 5 graph-level datasets, comparing against classical MPNN benchmarks, Graph-Trame Transformers (Ma et al., 2023; Shirzad et al., 2023; Rampášck et al., 2022; Kreuzer et al., 2021; Hussain et al., 2022), graph rewiring (Gutteridge et al., 2023), random- walk based method (Tönshoff et al., 2023b), and generalization of ViT/MLP-Mixe (He et al., 2023). Crucially, we also compare VNG with the standard implementation of VN (Cai et al., 2023).
Experimental Details. We evaluated MPNN + VNG on the Long-Range Graph Benchmark using fixed 500k parameter budget and averaging over four runs. These molecular datasets (Peptides-Func, Peptides-Struce have been proposed to test a method's ability to capture long-range dependencies. Additionally, we used two graph-level image-based datasets from Benchmarking GNNs (Dwivedi et al., 2023), where we run our model over 10 seeds. We also used a code dataset MalNet-Tiny (Freitas et al., 2020) consisting of function call graphs with up 5,000 nodes. These graphs are considerably larger than previously considered graph-level benchmarks and showcase our model's ability to improve over MPNN baselines on a large dataset. We then evaluated our approach on three graph-level tasks from the Open Graph Benchmark (Hu et al., 2020), namely molhiv, molpeha and ppa. Details on datasets and training parameters used, can be found Appendix G.
Discussion.
We can see from Tables 2 and 3 that MPNN + VNG performs well across variety of datasets and achieves the highest performance on Peptides- Struct, MNIST, ogbg-molhiv and ogbg-ppa. Furthermore, MPNN + VNG improves over MPNN VN on all tasks, with the largest percentage improvement being shown on CIFAR 10 (8.25%) The latter is perfectly aligned with the discussion in Sections 4 and 5.1, where have described the importance of heterogeneity to the VN and observed that heterogeneity is particularly required on CIFARIO. 10.. Additionally, on the peptides datasets, which have small degrees but large diameters, find that using MPNN VNG can perform better than
8

---

Published as a conference paper at ICLR 2025
Table 2: Test performance on two LRGB datasets (Dwivedi et al., 2022) and three other benchmarks from (Dwivedi et al., 2023). For Peptides-Fumn Func and Peptides-Stren = std is shown over 4 runs whilst the remaining datasets are over 10 runs (missing values from literature are indicated by "')). The first, second and third best results for each task are color-coded.
Method
Pept--unc (1)
Pept-Struct (L)
MNIST (t)
CIFAR10 (t)
MalNet- (f)
GCN GINE
0.5930 =0.0023
0.3496 40.0013
90.705 +00218
55.710 +0.381
$1.0
0.5498 =0.0079
0.3547 +0.0045
96.485 20.252
55.255 1.5527
88.98 10.56
GaledGCN
0.5864 =0.0077
0.3420
+0.0013
97.340
1:01433
67.312 +0.311
92.23 10.65
GatedGCN+PE
0.6765 =0.0447
0.2477
+0.0009
69.948
+0,499
GatedGCN+PEE PE-
0.6942 -0.0075
0.2465
+:0.0015
98.460
+:0.090
71,580
+=0.090
GatedGCN+PE-Min
0.6932 =0.0017
0.2508
+0.0007
98.320
+00040
70.600
+0.220
CRaWI
0.7074 =0.0032
0.2506
40.0022
97.940
+0.050
69.010
20.259
DRew
0.7150 =0.0044
0.2536 +0.0015
SAN+RWSE
0.6439 =0.0075
0.2545
+0000T2
EGT
98.173
+0.087
68,702
+0.409
GRIT
0.6988 =0.0082
0.2460
+000012
98.108
+0.111
76.468
+:0.881
GPS
0.6534 =0.0091
0.2509
+0.0014
98.051
+-0.126
72.298
+-0.56
93.50 +:141
Exphormer
0.6527 =0.0043
0.2481
10.0007
98.414
1:0.03
74.690
125
94,02 4:0.1
GatedGCN-PE-VN
0.6712 =0.0066
0.2481
10.0015
98.122
10.
70.280
10.380
92,62 00.57
GaNsGGCN+PE-VNG
0.6822 =0.0052
0.2458 +0.0006
98.626 100
76.080 +0.330
93.67 40.37
Table 3: Test performance graph-level OGB benchmarks (Hu et al., 2020). Shown is the mean % + std of 10 runs (missing values from literature are indicated with '-"). The first, second and third best results for each task are color-coded.
Method
MolHIV (1)
MolPCBA (1)
PPA (1)
GCN
76.06 0.97
20.20 +0024
68.39 -0.84
GIN
75.58 11.4
22.66 +0.28
68.92 +1.00
DeeperGCN
78.58 =1.17
27.81 +0.38
77.12 #0.71
CRaWL
29.86
+0.25
SAN
77.85 -0.28
27.65
+0.42
GPS
78.80 =1.01
29.07
+0.28
80.15 10.33
GCN+VN
75.99 =1.19
24.24
10.34
68.57 10.61
GIN+VN
77.07 11.49
27.03
+0.23
70.37 #1.07
GaIedGCN+PE+VN
76.87 L.36
28.48
10.26
80.27 10.26
79.10 00.6
29.17
L0.27
81.17 10.30
variety of transformer based approaches. Not only does this suggest that MPNN + VNG works well in practice but that complex long-range dependencies might not play a primary role for these tasks. This was also supported by Tönshoff et al. (2023a) where the lower performance of MPNNs compared to GTss was found be caused by insufficient hyperparameter tuning. We also show strong performance on the larger MalNet-Tiny dataset. Previous work has shown that using a full transformer outperforms linear attention- based methods (Rampášek et al., 2022) on this task. However, we show that we can match the performance of the full transformer and still be more computationally efficient.
6 CONCLUSION
In Section 3, we characterize how the spectrum of the input graph affects the impact of VN on the commute time and hence to oversquashing. We have also evaluated this on real-world benchmarks in Section 5. In Section 4, we show that standard VN implementations cannot assign different scores to nodes in the global update. Consequently, we propose MPNN + VNg. a variation of MPNN + VN sharing the same computational complexity, that uses the graph to learn heterogeneous node impor- tance. In Section 5, we show that this outperforms MPNN + VN on a range of benchmarks, precisely corresponding to those where GT's outperform MPNN + VN by learning heterogenos node scores.

---

Published as a conference paper at ICLR 2025
Limitations and Future Work. We have not empirically explored the change in commute time afforded by GT and rewiring-basee approaches. Future work can compare these approaches and VN, to assess their mixing abilities. We furthermore relegate the comparison of different message passing mechanisms in the VNg to future work since this would unduly extend the scope of our work.
ACKNOWLEDGMENTS
J.S. supported by the UKRI CDT in AI for Healthcare heellthcarehttp://aaaaaaa httttp::/aiiheaatht.ho (EP/S023283/1). M.B. is supported by EPSRC Turing AI World-Leading Research Fellowship No. EP/X040062/1 and EPSRC AI Hub on Mathematical Foundations of Intelligence: An "Erlangen Programme" " for No. EP/Y028872/1. J.L. is supported by the French National Research Agency (ANR) via the "GraspGNNs" JCJC grant (ANR-24-CE23-388))
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations. 2021.
Adrián AmaizzRRdrrígue, Ahmed Begga, Francisco Escolano, and Nuria Oliver. Diffwire: Inductive graph rewiring via the lovász bound. In The First Learning on Graphs Conference, 2022,
Federico Barbero, Ameya Velingker, Amin Saberi, Michael M Bronstein, and Francesco Di Giovanni. Locality-aware graph rewiring in gnns. In The Twelfth International Conference on Learning Representations, 2024.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 1006.020660000 2018.
Filippo Maria Bianchi and Veronica Lachi. The expressive power of pooling in graph neural networks In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Mitchell Black, Zhengchao Wan, Amir Nayyeri, and Yusu Wang. Understanding oversquashing in gnns through the lens of effective resistance. In International Conference Machine Learning, pp. 2528-2547. PMLR, 2023.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Patter Analysis and Machine Intelligence, 55(1))657-666 January 2023. ISSN 1939-3539. doi: 10.1 10,10099mmm12222355553311
Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. arXiv preprint arXiv:2006. 13318, 2020.
Chen Cai, Truong Son Hy, Rose Yu, and Yusu Wang. On the connection between mpnn and graph transformer. In International Conference on Machine Learning, pp. 3408-3430 PMLR, 2023.
Dexiong Chen, Leslie O' O'Bray, and Karsten Borgwardt. Structure-aware transformer for graph representation learning. In International Conference on Machine Learning. pp. 3469-3489. PMLR, 2022.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 33:10383-10393 10395, 2020.
Nima Dehmamy, Albert-László Barabási, and Rose Yu. Understanding the representation power of graph neural networks in learning graph topology. Advances in Neural Information Processing Systems, 32, 2019.
F Di Giovanni, TK Rusch, MM Bronstein, A Deac, M Lackenby, S Mishra, and P Velickovic. How does over-squashing affect the power of gnns? Transactions on Machine Learning Research, 2024.
Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pictro Lio, and Michael M Bronstein. On over-squashing in message passing neural networks: The impact of width, depth, and topology. In International Conference on Machine Learning, pp. 7865-7885. PMLR, 2023a.
Francesco Di Giovanni, James Rowbottom, Benjamin Paul Chamberlain, Thomas Markovich, and Michael M Bronstein. Understanding convolution on graphs via energies. Transactions on Machine Learning Research, 2023b.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations, 2021.
Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. Advances in Neural Information Processing Systems, 35:22326-22333 2022.
11

---

Published as a conference paper at ICLR 2025
Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24 (43):1-48, 2023.
Scott Freitas, Yuxiao Dong, Joshua Neil, and Duen Horng Chau. A large-scale database for graph representation learning. arXiv preprint arXiv:2011.0768% 2020.
Arpita Ghosh, Stephen Boyd, and Amin Saberi. Minimizing effective resistance of a graph. SIAM review, 50(1):37-66) 2008.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp- 1263-1272. PMLR, 2017.
M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume pp. 729-734 vol. 2, 2005. doi: 10. WTW09/UICNN..0..155555553
Daniele Grattarola, Daniele Zambon, Filippo Maria Bianchi, and Cesare Alippi. Understanding pooling graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, pp. 1-11, 2022. ISSN 2162-2388. doi: 10.1 1092mn1s..2222.33 1909222.
Benjamin Gutteridge, Xiaowen Dong, Michael M Bronstein, and Francesco Di Giovanni. Drew: Dynamically rewired message passing with delay. In International Conference on Machine Learning, pp. 12252-12267. PMLR, 2023.
Xiaoxin He, Bryan Hooi, Thomas Laurent, Adam Perold, Yann LeCun, and Xavier Bresson. A generalization of vit/mlp-mixer to graphs. In International Conference on Machine Learning, pp- 12724-12745. PMLR, 2023.
Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borgwardt. Topological graph neural networks. In International Conference Learning Representations, 2022.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. Advances in neural information processing systems, 33:22118 1222113,,, 2020.
Md Shamim Hussain, Mohammed J. Zaki, and Dharmashankar Subramanian. Global self-attention as replacement for graph convolution. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '22. ACM, August 2022. doi: 10.1 (0.1145/3534678. 3539296.
EunJeong Hwang, Veronika Thost, Shib Sankar Dasgupta, and Tengfei Ma. An analysis of virtual nodes in graph neural networks for link prediction. The First Learning on Graphs Conference, 2022.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 191 2014.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34:21618-21629, 2021.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. International conference on machine learning, pp. 37734-3743, PMLR, 2019.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations, 2019.
László Lovász. Random walks graphs. Combinatorics, Paul erdos is eighty, 2(1-46):4, 1993.
Liheng Ma, Chen Lin, Derek Lim, Adriana Komero-Sorianoo Puneet K Dokania, Mark Coates, Philip Torr, and Ser-Nam Lim. Graph inductive biases in transformers without message passing. In International Conference Machine Learning, pp. 23321-23337. PMLR, 2023.
12

---

Published as a conference paper at ICLR 2025
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2018.
Alessio Micheli. Neural network for graphs: A contextual constructive approach. IEEE Transactions Neural Networks, 20(3):498 511, 2009. doi: 10.1 10.1009//NN220882000033.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference artificial intelligence, volume 33, pp. 1602-4609 2019.
Giannis Nikolentzos, George Dasoulas, and Michalis Vazirgiannis. K-hop graph neural networks. Neural Networks, 130:195-22 205, 2020.
Hoang Nt and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv:1905.0900 2019.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020.
Trang Pham, Truyen Tran, Hoa Dam, and Svetha Venkatesh, Graph classification via deep learning with virtual nodes. arXiv preprint arXiv:1708.04333. 2017.
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 15:14501-14515 2022.
Ekagra Ranjan, Soumya Sanyal, and Partha Talukdar. Asap: Adaptive structure aware pooling for learning hierarchical graph representations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3470-5477, 2020.
Eran Rosenbluth, Jan Tönshoff, Martin Ritzert, Berke Kisin, and Martin Grohe. Distinguished in uniform: Self-attention vs. virtual nodes. In The Twelfth International Conference on Learning Representations, 2024.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2009. doi: 10.1 109/109.NNNN WWN.N.20...200 200...005505.
Nimrod Segol and Yaron Lipman. On universal equivariant set networks. In International Conference on Learning Representations, 2020.
Florian Sestak, Lisa Schneckenreiter, Sepp Hochreiter, Andreas Mayr, and Günter Klambauer. Vn-egnn: Equivariant graph neural networks with virtual nodes enhance protein binding site identification. In NeurlPS 2023 Workshop: New Frontiers in Graph Learning, 2023.
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. In International Conference Machine Learning, pp. 31613-31632. PMLR, 2023.
Jan Tönshoff, Martin Ritzert, Eran Rosenbluth, and Martin Grohe Where did the gap go? reassessing the long-range graph benchmark. In The Second Learning on Graphs Conference, 2023a.
Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Walking out of the weisfeiler leman hierarchy: Graph learning beyond message passing. Transactions on Machine Learning Research, 2023b.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over- ever-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations, 2022.
Guangtao Wang, Rex Ying, Jing Huang, and Jure Leskovec. Multi-hop attention graph neural network. arXiv preprint 2009 /4332, 2020.
Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. International Conference Machine Learning, pp. 23341-23366 PMLR, 2022.
13

---

Published as a conference paper at ICLR 2025
Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. nti, Series, 2(9):12-16, 1968.
Zhanghao Wu, Paras Jain, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and Ion Stoica. Representing long-range context for graph neural networks with global attention. Advances in 2021.
Neural Information Processing Systems,
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2018.
Shuo Yin and Guoqiang Zhong. gti Graph transformers with local and global operators interleav- ing. In IJCAI, pp. 4504 4512, 2023.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tin-Yan Liu. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, 34:28877-28888, 2021.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In International Conference on Learning Representations, 2020.
14

---

Published as a conference paper at ICLR 2025
A OUTLINE OF THE APPENDIX
In Appendix we study VNs in the context of the oversmoothing problem and for better readibility we provide the proofs of the theoretical statements in Appendix C. Then Appendix D contains further theoretical results connecting VN and the choice of global pooling. Next, we report the analysis on commute time and oversquashing when adding a VN in Appendix E. Proofs for the sensitivity analysis results in Section 4 are finally reported in Appendix F.
Regarding additional ablations and experimental details, we comment on training details, hyperparam- eters, datasets, and hardware in Appendix G. Next, we describe additional experiments confirming that VN introduces smoothing on graph-level tasks in Appendix H. focusing on the impact of the final pooling. We further validate the role played by the underlying MPNN model in MPNN + VNG in Appendix I. propose a visualization of the framework in Appendix J, and finally report attention maps learned by Graph- Grash-rrrnsformrr on benchmarks uused as proxy-measie for the heterogeneity required by the task Appendix K.
B MPNN + VN AND SMOOTHING
Despite the empirical success of MPNN + VN, the reasons behind these improvements still lack thorough understanding. To this aim, Cai et al. (2023) postulated that MPNN + VN is also beneficial due to its ability to replicate PairNorm (Zhao & Akoglu, 2020), a framework designed mitigate oversmoothing. In this appendix we provide theoretical arguments against this conjecture, proving that MPNN + VN loses expressive power when it emulates PairNorm.
Comparison to PairNorm. Methods such as PairNorm (Zhao & Akoglu, 2020), aim at mitigating
oversmoothing, which occurs when the node representations converge to the same vector in the limit of many layers, independent of the task (Nt & Maehara, 2019; Oono & Suzuki, 2020). To address the this section we adopt the
claims in Cai et al. (2023) and compare MPNN + VN and PairNorm, assumptions in Zhao & Akoglu (2020) and other theoretical works on oversmoothing (Di Giovanni et al., 2023b), and consider networks whose layers are linear. In particular, to assess advantages of MPNN + VN over PairNorm, we study their expressivity. Since aggregating linear layers yields a polynomial filter of the form p(A) HH where H are the input node features, we choose as expressivity metric precisely the ability of model to learn such polynomial filters. In fact, under mild assumptions, polynomial filters are comparable to the 1-WL test (Wang & Zhang, 2022). Additionally, when the input features H are constant, polynomial filters (17) coincide with graph moments, metric of expressivity studied in Dehmamy et al. (2019), further validating our approach.
Measuring Expressivity With Polynomial Filters. Since in this section restrict the analysis to models that have linear layers, we introduce a simple MPNN baseline. which is obtained from (1) by choosing a sum aggregation and linear update with a residual connection:
(15) where ( is a d x d weight matrix and H() is the n x d feature matrix at layer f. Note that the the MPNN, i.e., the occurence of A (15) and the subsequent
(e+1) H + AH
choice of the sum aggregation analysis, is made without loss of generality and our analysis applies to any other message passing operator used instead of A. Similarly, for MPNN + VN, we consider a layer update with mean aggregation for VN, akin to Cai et al. (2023):
(t+1) = H(0 + AH W(O + 11 ((1))Q(0)
(16)
with Q(9) weight matrix and 1 E E the vector of ones. For simplicity, we assume that the output after m layers Y,,, also has dimension d and choose mean pooling operation in the final layer, so that given weight matrix O we have Y,, i ((m)), with H (m)) computed by either (15) or (16). We can express Y, as a graph-level polynomial filter in terms of d x d weight matrices (O+}:
Y, Mean
A H
(17)
We note now that MPNN + VN (16) recovers PairNorm when Q(1) = -I, with I the d x d-identity matrix. We denote this special choice as MPNN - VN.
15

---

Published as a conference paper at ICLR 2025
Theorem B.1. There are polynomial filters (17) that can be learned by MPNN but not by MPNN VN. Conversely, any polynomial filter learned by MPNN (15) can also be learned by MPNN + VN (16). Farthermore, there exist polynomial filters that can be learned by MPNN VN but not by MPNN.
Theorem B.1 implies that the ability of an MPNN- VN to replicate PairNorm comes at the cost of expressivity. Conversely, MPNN VN (when they do not replicate PairNorm) are more expressive than MPNN when learning polynomial filters. In light of Theorem B.I, we argue that, contrary to the claim in Cai et al. (2023), MPNN VN generally avoids replicating PairNorm to maintain its greater expressivity. We empirically validate this statement in Appendix H.l and report the smoothing effects of VN on common benchmarks in Appendix H.2.
In summary, our analysis suggests that on graph-level tasks, benefits of MPNN + VN are independent of their ability to replicate methods such PairNorm. In fact, for graph-level prediction, whose output is computed using a global mean, some 'smoothing" is actually unavoidable. In particular, the mean pooling in (17) corresponds to projecting the final features precisely onto the subspace spanned by E RR", i.e., the kernel of the (unnormalized) graph Laplacian associated with oversmoothing (Cai & Wang, 2020; Di Giovanni et al., 2023b). This allows to clarify key difference when studying oversmoothing for node-level and graph-level tasks. In the former case, if two node features become indistinguishall, then they will be assigned the same label, which is often independent of the task, thereby resulting in harmful oversmoothing. Conversely, in the latter case, even if the node features converge to the same representation, this behavior may result in beneficial oversmoothing if such common representation is controlled to match the desired, global output. We argue that for this reason, oversmoothing has hardly been observed as an issue on graph-level tasks. We refer to Proposition D.1 in Appendix C for results relating VN to the choice of pooling and to ablations in Appendix H.2.
C PROOFS OF RESULTS IN APPENDIX B
Proof of Theorem B.I. First, we note that similarly to Cai al. (2023), the VN state initialized to be zero, i.e., the first layer of Equation (16) is
H H + (HW(
(18)
where H is matrix of input node features. It is trivial to check that any polynomial filter that can be learned by MPNN can also be learned by MPNN VN, considering that if we set the additional weight matrices { {Qr} } to be zero in (16), then we recover the MPNN case in (15). Accordingly, to prove that MPNN VN is strictly more expressive than MPNN when learning polynomial filters, only need to show that there exist m E N and polynomial filters of degree m that can be learned by an MPNN VN of m layers, but not by MPNN. We show that such a polynomial can already be found when m = 2. Namely, given a linear 2-layer MPNN + VN, we can write the 2-layer representation (22) explicitly as
H () H+ AH(W + w + A H ( w + -11 THQO)
(19)
Recall that given the choice of global mean pooling, the final output is
Y2 @Mean (2)..
(20)
Since Mean (2) = (2) T1/n, we find
Y, = Mean H) + Mean (AH) + OeMaen(APH))
where the weights characterizing the family of quadratic polynomial filters are defined by the system:
O é I (Q)))
(21)
θ é (Wil)))= + (W())))
(22)
2₂ = é
(23)
16

---

Published as a conference paper at ICLR 2025
Assume now that the class of polynomial filters we wish to learn, have vanishing zeroth-order term, i.e., , = 0. For the MPNN not containing VN, corresponding to Q(1) 0 in (21), then we must have θ = O. Therefore, the only quadratic polynomial without a zeroth-order term that can be learned by a linear MPNN as in (15) of degree 2 is the trivial polynomial. Conversely, an MPNN + VN can, for example, learn the weights Q(1) = -I to ensure O = O, and have non-trivial first and second-order terms using the W-weight matrices. This proves that on ant given graph there exist polynomial filters that can be learned by MPNN VN but not by MPNN.
To conclude the proof, we now need to show that MPNN + VN loses expressive power when it emulates PairNorm. We observe that for the case of MPNN- VN, i.e., Q -I for & E N, after two layers, the term O always zero. Since MPNN after two layers can learn quadratic polynomial filters with non-trivial zero-th order terms, this completes the proof.
We want to remark that MPNN-VN is a slight simplification of PairNorm since firstly, does not include the scaling factor that is present in the originally proposed PairNorm method and secondly, does not use the updated hidden representations in the substracted mean at every later. However, the PairNorm scaling factor can be absorbed into @ in (20). We furthermore observe that when using the original PairNorm normalisation, then every layer (by design) has zero mean, which in particular implies that no graph moment of order m can be learned after m layers, i.e., the m-th coefficient always vanishes. Hence, our statements also extend to the originally proposed PairNorm.
Note further that Theorem B.1 can be extended to apply to MPNNs with an linear embedding layer, i.., MPNNs where (15) becomes
H HW AHOWO) H ( + ("(00)) for E > 1.
(24)
Theorem C.1. There are polynomial filters (17) that can be learned by MPNN with embedding layers as defined in (24) but not by MPNN VN. Conversely, any polynomial filter learned by MPNN (24) can also be learned by MPNN VN with analogous embedding layer the initial node features. Furthermore, there exist polynomial filters that can be learned by MPNN + VN but not by MPNN when both models have linear embedding layer the initial node features.
Proof. The structure of this proof follows the Proof of Theorem B.I.
Again, it is trivial check that any polynomial filter that can be learned by an MPNN can also be learned by MPNN + VN, considering that if we set the additional weight matrices {Q²) to be zero, then we recover the MPNN case in (24).
If we consider the MPNN in (24) then the system of equations in (21) becomes
i é((W) + +QQ (Q)))(W)))
θ ((W + (W (W))))(W)?))
2₂ ((W"))((())))))))
If we now consider polynomial filters with vanishing first-order term and an invertible second-order term, we obtain (W(0lyr" =(WW())"' " Consequentl,, for an MPNN without VN, we have
( (wW)) (WW).
(W)T.
Hence,
del((O.)) = =(11)dde(
(25)
Therefore, the polynomial filters an MPNN can learn are constrained, since the sign of the determinant in (25) is fully determined by the hyperparameter d. Without loss of generality, for even d an MPNN cannot learn the polynomial Ô, Q = I and é, 0. On the other hand, this polynomial can be learned by MP by learning é 1, (W(")r = -(w())", (W)" (- (W()) and (Q (I W)T
17

---

Published as a conference paper at ICLR 2025
D ADDITIONAL RESULTS ON THE ROLE OF POOLING
In this section we discuss how the choice of the global pooling affects the benefits of VN. Consider alternative global pooling, which instead of projecting the final features onto 1/n (i.e. computing the mean), projects the final-layer features onto V E IR" satisfying v = 0,
YY m ((H (m))
Σ k=0
Oa(A H))
(26)
We can then show that there exist polynomial filters that MPNN VN is no longer able to express when we replace mean pooling with v-pooling.
Proposition D.1. Given v orthogonal to 1, a linear MPNN + VN of m layers can generate weights {O&} in the output Y in (17) that cannol be generated by linear MPNN + VN using global pooling induced by v, as in (26).
Proof of Proposition D.I. Once again, we show that it suffices to consider the case of quadratic polynomial filters, i.e., m = 2 given in the system of equations in (21). However, since 1 and v are orthogonal, then there is no Q(1-ttem in Equation (21). As such, we see that the quadratic polynomial Y has zero-th order coefficient vanishing if and only if é = O, i.c., the quadratic polynomial is trivial. Conversely, MPNN + VN can instead learn non-trivial quadratic polynomial without zero-th order term by simply setting Q(1) II
A Fourier Perspective on Pooling, Proposition D. highlights that MPNN + VN may lose the ability express polynomial filters when we no longer have alignment between VN and the global pooling. This result raises important question: What is the bias resulting from certain choice of global pooling? Consider linear MPNNs as above where the global pooling is obtained by projecting onto some v E RR, with the case v = 1 recovering the mean (sum) pooling. Given [v:) C IK" a basis of orthonormal cigenvectors of A, with eigenvalues { we write v = E; c, where {c;} are the graph Fourier coefficients of Given 1 S r S d, the channel of the final output per (26) takes on the following form in the Fourier domain
yr
Σ
a (hP (h).
(27)
where h² E RT is the channel p of the input features. Accordingly, the Fourier coefficients {ee} of v and the associated frequencies { determine which projection (h?, vhi) affects the output the most. The fact that on many datasets mean (sum) pooling is beneficial, and hence adding VN is mostly advantageous as per Proposition D.I, highlights that the underlying tasks depend on the projection of the features onto those eigenvectors (1/) aligned with the vector 1.
E PROOFS OF RESULTS IN SECTION 3
In this section, we report the proofs of the theoretical results in Section 3 along with additional details. We start by proving Theorem 3.1.
Proof of Theorem 3.1. We start by recalling that the effective resistance between two nodes and j.
denoted by R(i, can be computed as (Ghosh al., 2008):
R(i.j) = L,, + 4), 21
(28)
where L is the pseudo-inverse of the graph Laplacian, i.e.,
L
veuT
(29)
Accordingly, we can write the effective resistance between two nodes and explicitly
n-1
R(i,)) = Σ
(vz(1)
2
(30)
E=1
18

---

Published as a conference paper at ICLR 2025
Naturally, for the graph Gvn obtain from adding VN, the formula changes
Rin ()
(1) - ()))
(31)
where Lun u = oz When we add the virtual node though, the adjacency matrix changes as in Equation (4), meaning that the graph Laplacian be written
D ++ 0
0
A 1
L
+ 1
Lyn = Dmn Aun
n n+1
1
1
(32)
vn+T (1)
1
We recall now that Vo Lin 0. Similarly, from the block decomposition of Lun we derive that
Va i.e., L1 Accordingly, we find that v8"
i.e.,
Lun
(6)-(1))
1/6 ( (L D) De
(Ae+
ve 0
(33)
where we have used that ve are orthogonal to up eigenvectors of Lun for all 1 S e with eigenvalue de + 1. Finally we note that
1 for all l 2 1. Accordingly
6e are (o)
vn
L 1
(L + 111 111+11 m1
1
-11 n² = (1 (1+n) Vn²
(34)
2 + n
-n)
Vn² +n
-72
1
which means that
the final eigenvector of Lvn with eigenvalue We can then
Vx
-n
use the spectral decomposition of Lyn to write the effective resistance between nodes and j after adding VN
Ryn (i.
n
(1) -z
Σ de + (ve(i) ve(
1 1 + n2 + n
1)²
Σ E=1 A +1 (ve(1) vz(i))²
Finally, we recall that on a graph, the commute time r is proportional to the effective resistance (Lovász, 1993), i.e.,
-(,j)) = 2|
Accordingly, we can use that on Gm the number of edges equal to |E| + n and compare the commute time after adding VN with the baseline case:
2(
+
2| (ve(() ve(i))²
-((,))
Σ t=1
de
n-1
F
Σ
n A - 1) (ve(1) v)))))
NeAee11
[E)
which is precisely Equation (5). We can the sum over all pairs of nodes to obtain
((c.))
n de
1) (ve(1) - nx(i))²
de(Ae +1)
[
2
de -
Σ
(uz(i) - vx(i))²
Xe(Ae + 1) (15
1,j=1
= 2
nl
dι --1 1)
Σ
(Z(()) + +0(() 2ve())ol())
Ae + +1
E
1-=1
19

---

Published as a conference paper at ICLR 2025
We now use that by form orthonormal basis, accordingly:
Σ == 2z(2)2 1. Similarly, since by is
orthogonal to vo and hence to 1, we get 0z 1 Li=1 ve(i) = 0. Therefore,
+ - 20e()) = 2n 2 Σ
(x( ve(i) = 2n.
i=1
j=1
We finally obtain:
1
1
4| n-1
(
(mm de -1). 1).
n
n t=1
de + 1) [E]
1,j=1
which completes the proof.
Remark: We note that according to Equation (5), we expect Fun(i.)) < T(i,j) whenever the two nodes have large commute time the inpul graph, i.e. due to the graph having a bottleneck where d1 is small and the Fiedler eigenvector is such that vi(ū) v,(j) < 0 since i. belong to different communities. As such, adding VN should indeed beneficial for graphs with bottlenecks, while may slightly increase the commute time between nodes that were well connected in the graph due the addition of VN spreading information out from the pair. This intuition is validated in Section 5. where we show that on real-world graphs adding a VN decreases the average commute time significantly.
Corollary E.1. If we let 1 n/BBBB then
4 EEa
4|Ela
(1 +1 I Tml(i,] aT((i))
(35)
An 2n-1 (m-
Proof. From (5) and the proof above, we derive
- -i((,)) =
2( 2( +
2([ + n))
(ve(1) - ())
v()))
de +1
de
t=1
2 + n
de(he + 1) (oe(1) - 2t(
B|
n-1
4/Elo
(vr(1) vx(i)²== A1 +1)
A1(A1 +1)
where the last equality follows from
Σ (vx(1) - vo(i)) Σ + (700)))))))((())m
= 2 1 2 Σ (1 200(0))00)))) = 2111_
- n
2 n
+ 2,
E=0
where we have used the orthonormality of the eigenvectors for + j. The upper bound can be proved in the same way using that d & An-1 for each l.
Proof of Corollary 3.4, Consider an MPNN VN. We recall that mix, (i, is the mixing induced by a graph-level function among the features of nodes and j. and is defined as (Di Giovanni et al., 2024)
8 y H
(i, = max max H ISo
Ohe an
According to Di Giovanni et al. (2024), when the mixing induced by the MPNN after m layers, denoted here as (ix (i.j). is smaller than the one required by the downstream task, then we have an instance of harmful oversquashing which prevents the network from learning the right interactions
20

---

Published as a conference paper at ICLR 2025
necessary to solve the problem hand. Since we write the system in (3) the system of MPNN analyzed in Di Giovanni et al. (2024), operating on the graph Gvn. we can extend their conclusions in Theorem 4.4. Namely, using their notations, we find that given bounded weights and derivatives for their network, the minimal number of layers required to learn graph-level function y with mixing mixy(i,)) is
(i, + avn mix,,i,,,)) (i,5) + 8vn- 8
where the constants avn and Sun are independent of nodes i. and without loss of generality we have taken C2 = 1/2 in Theorem 4.4 of Di Giovanni et al. (2024)- clearly, the result generalize to any C2 I 1. As such, we see that a necessary condition for the family of graph-level functions with mixing mixy
Bun/ / Ovvn be learned by MPNN VN is that
[(t m
π
(i.j)
E
Z
1
8
E
8
2
+1)
where we have used Equation (5) in the last inequality. This completes the proof.
Accordingly, MPNN VN can improve upon the minimal number of layers required learn functions with strong mixing between nodes (i,j). when compared to the baseline MPNN. In fact, such improvement can be characterized precisely in terms of spectral properties of the graph Laplacian, and in light of Corollary E.1 of A1
F PROOFS OF RESULTS IN SECTION
We begin by providing the analytical model equations for the GatedGCN+VN model that we experi- ment with in Section 5.
n w(
((++)) -
(e+1) = 0 (2 (
(n (6) (1) o w w + m1)
JEN;
where @ denotes the element-wise product and 17 (1 (0) = sigmoid W M + W (9)) And correspondingly now write the analytical model equations for the GatedGCN+VNG model.
h (E+1) 1,00 = (9)
Σ
w/
JEN;
(Q (++ (1+1)))))) (4+1) jo0c where v (n)) n0 = sigmoid( A n
11 ((+1) = 1ooc + Mean
We now continue with the proof of the theoretical statements made in Section 4.
Proof of Proposition 4./. Recall that we consider an MPNN + VN whose layer update is of the form
(f+1) oQmm (1) + (
1
h2
72
j=1
h ((+1) (2((0) +
Agz (n (o,,,n())) + (0 (n .12))
21

---

Published as a conference paper at ICLR 2025
if E V with & outside the 2-hop neighborhood of i, then any message sent from & to i will arrive after 2 layers through the VN. Since the VN update is homogeneous though, node i cannot distinguish which node & sent the message. Explicitly, we can compute the derivatives and obtain
oh ah (e+1) 1 ohg (t-1) n
== (h)) h (2(6 W
vn
where =(00) is the argument of the nonlinear activation a, o'(z) is the diagonal derivative matrix computed at and V2 denotes the Jacobian w.r.t. the second variable. As we can see, the derivative is independent of k and is the same for each node outside the 2-hop neighborhood of i, which shows that the layer of MPNN + VN is typically homogeneous and hence fails to assign different relevance (sensitivity) nodes. This completes the proof.
Proof of Proposition 4.2. Consider instance of MPNN VNG whose layer updates have the form
((+1) h 1,,cc a (6)
+
Σ
2 (0)
(hg
)),
JEN;
((+1) 1i,ooc + ((
Given i, V where node is outside the 1 -hhop neighborhood of i, any message sent from to i
will arrive after 1 layer through the VN-in other words, ab (++1) /ah O. We can compute the derivatives and obtain
ah (e
Oh
(E+1)
jo
an
th
(2)
j=1
k
Σ o' (z(2) (110
Σ (1 1o + Venbjuh,9,n (019))99)
MEN,
1 (d'(2()) (1 (2(0
E
Viell
Σ
uEN,
ueN,
where 5pg is the Kronecker delta with indices p. q and in the last sum we have replaced the dumb index j with This completes the proof.
L
For completeness, we also provide corresponding sensitivity analysis of the global attention mechanism now, that at the heart of the different GT variants. particular, we will be analysing the following global attention mechanism,
H (E+1) softmax att
(V H Oll (HO)) T H
1
(36)
w(O V (( of w(() Ki
where (1())
denote trainable weight matrices and de+1 denotes the number of columns
Proposition F.1. Given i, V the Jacobian ah aiee- yan
computed using (36) is
ah an((+)) an(
(ale1 (1 T (1 (W (W
1
w
softmax
+ softmax'
(n
( TT()
(1 Wi())
)
(w())
Tw("
(det1
Vde+1
Proof. We begin by reformulating the global attention mechanism equation in (36) to reflect the update of the hidden representation katt.s of node i,
h (1+1) att.i
Σ
softmax
(V (n)9) TwT
(W
w(
22

---

Published as a conference paper at ICLR 2025
Now the Jacobian can be relatively simply derived using the product rule follows,
dh ((+1)
(4) softmax
(Vāem
(n
(
)
w
Q
+ softmax'
1 ( (de+1
T (Wk) Tw
vd++
where softmax' denotes the derivative of the softmax(1) function.
We can hence conclude that hidden states obtained in the global attention mechanism, that is used in most GTs without modification, depend on both the hidden state of the central node h and the hidden state of any other given node h/g This dependence arises rather trivally as a result of the fully connected attention scheme, in which any two nodes can exchange information.
G EXPERIMENTAL DETAILS
In this section, we provide further details about our experiments.
G.1
HARDWARE
All experiments were run on single V 1000 GPU.
G.2 DESCRIPTION OF DATASETS
Below, we provide descriptions of the datasets on which we conduct experiments.
MNIST and CIFARIO (CC BY-SA 3.0 and MIT License) (Dwivedi et al., 2023). These datasets test graph classification on the popular image classification datasets. The original images are converted to graphs using super-pixels which represent small regions of homogeneous intensity in the images. They are both 10-class classification tasks and follow the original standard (trin//aliddation/tess) splits; 55K/5K/10K for MNIST and 45K/5K/10K for CIFAR10.
ogbg-molhiv and ogbg-molpeba (MIT License) (Hu et al., 2020). These are molecular property prediction datasets which use common node and edge featurization that represents chemophysica properties. Ogbg-molhiv is a binary classification task, predicting the molecule's ability to inhibit HIV replication and ogbg-molpcha is multi-task binary classification where 128 bioassays predicted.
ogbg-ppa (CC-0 License) (Hu al., 2020). This dataset consists of protein-protein interaction networks derived from 1581 species and categorized into 37 taxonomic groups. Nodes represent proteins and edges encode the normalized level of 7 different associations between proteins. The task is to classify which of the 37 groups the network belongs to.
MalNet- Tiny (CC-BY License) (Freitas et al., 2020). This subset of MalNet which contains function call graphs (FCGs) derived from Android APKs. There are 5,000 graphs with up to 5,000 nodes with each graph coming from a benign software. The goal is to predict the type of software from the structure of the FCG. The benchmarking version of this dataset typically uses Local Degree Profile as the set of node features.
Peptides-fune and Peptides (CC-BY-NC 4.0) (Dwivedi et al., 2022). These datasets are composed of atomic peptides. Ppetides-func is a multi-label graph classification task where there are 10 nonexclusive peptide functional classes. Peptides-struct is regression task involving 11 3D structural properties the peptides.
Sparsity of Graphs and Complexity of VN. The real-world benchmarks used in this paper are generally very sparse. For instance, ogbg-mo molhi (mean number of nodes: 25.5, mean number of edges: 27.5), Peptides (mean number of nodes: 150.9. mean number of edges: 307.3), MNIST (mean number of nodes: 70.6, mean number of edges: 564.5), CIFARIO (mean number of nodes:
117.6, mean number of edges: 941.1), MalNer-Tiny (mean number of nodes: 1,410.3, mean number
23

---

Published as a conference paper at ICLR 2025
of edges: 2,859.9). The computational complexity of an MPNN is O(EE) and of an MPNN+VN is [ + n). Given that, on these datasets, the order of magnitude n is similar to E the complexity of MPNN+VN can be written ((en) where e small constant. This is significantly better than the computational complexity a Graph Transformer which is (n?²) on these datasets.
G.3 DATASET SPLITS AND RANDOM SEEDS
All the benchmarks follow the standard train/validationntess splits. The test performance at the epoch with the best validation performance is reported and is averaged over multiple runs with different random seeds. All the benchmarking results, including the extra ablations, are based on 10 executed runs, except for Peptides-func and Peptides-struct which are based the output of four runs.
G.4 HYPERPARAMETERS
Considering the large number of hyperparameters and datasets, it was not possible to do an exhaustive grid search and to find the optimal parameters. Here we describe how the final hyperparameters shown in Tables and 5 were obtained.
Hyperparameters in Table 1. For the GPS model and its projection, we used the hyperparameters as described in the original work Rampášek et al. (2022). For GatedGCN+PE++VN and other trained models, we outline our hyperparameter optimization process for different datasets in the following subsections.
OGB datasets. For both ogbg-molpctte and ogbg-ppa we used the same hyperparameters as used in Rampášek et al. (2022) but the hidden dimension of the MPNN was adjusted so that we had a similar parameter budget. For ogbg-molhiv, we found to be beneficial reduce the number of layers to align with the number of layers used in Bouritsas et al. (2023) but kept the same parameters for the positional encoding and the optimization process.
Soptides-Fune and Peptides-Struct. For these datasets we optimized the hyperparameters over the following ranges:
Dropout [0, 0.1, 0.2].
FeedForward Block (True, False],
Depth [4, 6, 8, 10].
Positional Encoding [none, LapPE, RWSE),
Layers Post Message-Pasiing [1, 3].
and we used the optimization parameters recently proposed by (Tönshoff et al., 2023a) where they train for 250 epochs with an AdamW optimizer (Kingma & Ba, 2014), and cosine annealing learning rate scheduler with a base learning rate of 0.001. When optimizing over the number layers of message-passing, changed the hidden dimension to ensure that the parameter budget was around 500K.
MNIST, CIFARIO, MalNet-Tiny. On these benchmarks, we used the same dropout, positional encondings and optimization parameters as used by Shirzad et al. (2023). The only parameter we optimised for was the number of layers the range [3, 5, 7]. Additionally, we changed the hidden dimension in accordance with the number of layers to match the number of parameters that were used in Shirzad al. (2023).
24

---

Published as a conference paper at ICLR 2025
Table 4: Best performing hyperparameters for GatcdGCN++E++NN in Table 2.
Hyperparameter
Peptides:Fun Fune
Peprides- Struct
MNIST
CIFARIO
MaiNet- Tmy
#Layers
4
5
7
Hidden dim
136
136
46
40
72
Dropout
0.1
0.1
Graph pooling
mean
mean False
moca
mean
mean
FeedFoorwar Block
True
Positional Encoding
RWSE-20
LapPE-16
LapPE-8
LapPE-8
None
dim
16
8
PE encoder
Linear
Linear
Linear
DcepSet
Batch size
200
200
16
16
16
carning Rate
0.001
0.001
0.001
0.001
0.0005
#Epochs
250
250
100
100
150
#Parramtters
492,217
492,217
110,148
117,066
281,453
Table 5: Best performing hyperparameters for GatedGCN+PE+-NG in Table 3.
Hyperparameter
aghg malhiv
oghg- molpcha
oghg-ppu
#aayers
5
Hidlen dim
90
384
284
Drepout
Graph pooling
mean
meam True
meam True
FeedForward Block
True
Positional Encoding
RWSE-16
RWSE 16
None
PE dim
16
PE encoder
Linear
Lineur
Batch size
32
512
32
Learning Rate
0.0001
0.0005
0.0003
#Epochs
100
200
#Panameters
360,221
7,519,580
2,526.501
H SMOOTHING AND THE IMPORTANCE OF GRAPH STRUCTURE
In this section, explore the performance various benchmarks of adding or removing the current pooled representation at each layer. We take the pooling function to be the mean and at each layer we either subtract or add this from the output of the message passing layer. Adding the mean increases the smoothness of the representations and we see that this leads to performance improvements on the LRGB tasks in Table 6. Again, this highlights the benefits of smoothing on some graph-level tasks. On the other hand, we see that subtracting the mean is beneficial for booggmolppbb. Subtracting the mean at each layer before using the mean pooling function the final layer, means that we are ignoring the output of the message-passinn passing layer which is aligned with the final representation. We can see this as good measure of the importance the graph structure as we are removing any locally aggregated updates. This suggests that it is beneficial to ignore the graph topology for ogbg-molpcba.
Table 6: Analyzing the performance of GatedGCN where we subtract or add the mean of the message- passing output at each layer.
Mothod
Poptides-Func (?)
Poptidos-Struct (1)
ogbg-molhiv (f)
ogbg-molpcba (1)
GatedGCN
0.5864 1000077
0.3420 20.0013
0.7827 10.01
0.2714 +0.0014
GatedGCN mean
0.6692 +:0 00-12
0.2522 =0. 00.0012
0.7677 +0.0138
0,2569 +0 0034
GatedGCN mean
40.0040
0.3566 =0.0007
10.0096
0.2866 1.0001
H.1 EMPIRICAL COMPARISON OF MPNN + VN AND PAIRNORM
We now study the question to what extent MPNN + VN replicates PairNorm on graph-level tasks. To answer this question and assess whether MPNN + VN behaves differently to PainNorm in practice, we evaluate both on two graph-level tasks from the Long- Range Benchmarks (Dwivedi et al., 2022) using three different MPNN architectures. It is clear from Table 7 that whilst PairNorm has damaging impact on the results as hypothesized in Theorem B. MPNN + VN achieves significant gains over the standard MPNN architecture. Further datasets and results using GatedGCN can be found in
25

---

Published as a conference paper at ICLR 2025
Table 9. One explanation for the observed phenomenon is that, these datasets, MPNN VN favors alignment between the layerwise representations and the final output representation (a smoothing process). This phenomenon representations at each layer to the final pooled representation. Plots of this cosine similarity over the layers can be seen in Appendix H.2 and clearly show that the VN causes smoothing effect in contrast to Poir
be observed when comparing the cosine similarity of the pooled
Table 7: The effect of PairNorm and MPNN VN LRGB tasks.
Method
Peptides-Funee (1)
Peptides-Struce (L)
GCN
0,5930 +0.0022 0002
0.3496 +0.0013
GCN PairNorm
0.4980 -0.0031
0.3471 #0.0016
GCN VN
0.6623 +0.0038
0.2488 00.0021
GINE
0.5498 +:00079
0.3547
1:0.0045
GINE PairNorm
0.4698 + 00033
0.3562 #0.0007
GINE VN
0.6346 #0.0071
0.2584 +0.0011
GatedGCN
0.5864 +0.0077
0.3420
+0.0013
GatedGCN + PairNorm
0.4674 +0.0040
0.3551 +0.0008
GatedGCN VN
0.6477 +000039
0.2523 +0.0016
As argued before, this further supports that these tasks, the alignment between the VN and the choice of global pooling means that the task depends on feature information associated with the frequency components of the subspace spanned by 1.
H.2 COSINE DISTANCE PLOTS
We analyzed the layerwise smoothing on the graph-level LRGB datasets (Dwivedi et al., 2022) using GatedGCN with and without VN/attention layer. To do this, we measured the cosine distance between the representations at each layer and the final pooled graph representation. We found that using a VN or an attention layer reduced the distance between the earlier layer representations and the final pooled representation and that this lead to an improvement in performance. This suggests that these approaches can cause a beneficial smoothing towards the final representation.
26

---

Published as a conference paper at ICLR 2025
Cosine Distance to Final Embedding
GPS
GatedGCN
0.0
Figure 2: The cosine distance between the embedding at each layer and the final graph representation after training GatedGCN, well with VN and a transformer layer on Peptides-fune.
Cosine Distance Final Embedding
0.6
0.4
G
GPS
GatedGCN
0.3
0.1
Layer
(a)
Figure 3: The cosine distance between the embedding each layer and the final graph representation after training a GatedGCN, as well as with a VN and a transformer layer on Peptides-struct.
27

---

Published as a conference paper at ICLR 2025
1 ADDITIONAL ABLATION STUDIES
In this section, we explore additional ablations to improve our understanding of virtual nodes and our heterogeneous extension. In Table 8, we look at the performance improvement of our heterogeneous VNg when the base MPNN is a GCN or a GatedGCN. Whilst we generally see an improvement with our implementation, this improvement much larger when we use GatedGCN, As previously argued, this is due to the fact that in a GatedGCN, the aggregation weights each neighbor through learnable gate and we can thus have a learnable node importance based on the graph topology. This is in contrast to GCN where we have homogeneous node update.
Table 8: Performance of MPNN + VNg in comparison to virtual node with positional encodings.
Method
ogbg-molhiv (1)
ogbg-molpeha (f)
poptides-fone (t)
peptides-struct (.)
CIFARIO (t)
GCN+PE+VN
0.7599 #0.0119
0,2456 #0.0031
0.6732 +0.0068
0.2475
0000009
68.957 +0.381
GON+PE+VNG
0.7678 10.0111
0,2481 1.00032
0.6862
0.2456 1:000110
68.756 10.172
GatedGCN+PE-VN
0.7687 40.0136
0.2848 +0.0026
0.6712 -000066
0.2481 00.0
70.280 + 380
VEN
0.7884 +0.0099
0.29 00.002
0.6822 #0.0052
0,2458 #0.0006
76.080
+0.301
GCN
1,93
-0.29
GatedGCN % Increase
+2.56
+2.42
+1.64
+0.89
+8.25
As extension to Section B, we compared the performance of GatedGCN with augmentations which involve adding VN in Table Additionally, we look at the effect of applying PairNorm on the datasets. We see that applying PairNorm to the GatedGCN, common technique to mitigate oversmoothing, actually reduces performance on all of these datasets. Moreover, using a virtual node always outperforms using PairNorm. This further implies that VN is not recreating PairNorm and suggests that, on these graph-level tasks, smoothing may be beneficial.
Table 9: Performance of GatedGCN and its extensions on four benchmark tasks.
Method
Peptides-Fuut Funcc (t)
Peptides Struct (1)
ogbg-molhiv (t)
ogbg-molpcha (t)
GatedGCN
0.5864 10.0077
0.3420 +0.0013
0.7827 10.0111
0.2714 10.0014
GatedGCN with PairNorm
0.4674 10.0040
0.3551 10.0008
0.7645 10.0128
0.2621 10.0026
GatedGCN + VN
0.6477 +0.0039
0.2523 +0.0016
0.7676 +0.0172
0.2823 +0.0026
J VISUALIZATION OF MPNN + VNG
Here we visualize the differences between our implementation of MPNN + VNG and standard MPNN+VN. Our model uses the local MPNN acting the original graph to weight the nodes based on their importance. This means that the VN can perform a heterogeneous global update.
MPNN NN
MPXX VNg
MPNA
MPNN
Figure 4: Comparing MPNN+VN with our proposed MPNN + VNG.
28

---

Published as a conference paper at ICLR 2025
K ATTENTION MAPS
In order to get a better understanding of the homogeneity of the attention layer in the GPS framework, we visualized the first layer attention matrices for various datasets. This complements our analysis in Section 4 where we relate the gap in performance between a MPNN + VN and GPS to the level of homogeneity of these attention patterns. The attention pattern for CIFARIO is less homogeneous, as measured by the standard deviation of the columns sums.
CIFAR1O
0m3
0.4
0.0
MNIST
0.250
0 0.225
00200
00175
00230
AAB
00100
00375
Figure 5: First layer attention maps of the self-attention matrix in the GPS framework for different datasets.
29


Reviews:
[{"review_id": "dgbaDM3hhq", "reviewer": "Reviewer_JV8P", "summary": "The paper contains a theoretical examination of VNs and their ability to counteract the oversquashing frequently present in MPNNs and a juxtaposition with GT methods, leading to a justification for an intermediate heterogeneous VN approach, VN_\\textit{G}.\nA novel analysis shows that VNs impact on the commute time between nodes of a graph, as a function of the graph spectrum, can reduce oversquashing. Empirically, VNs are shown to reduce commute time compared to MPNNs on real graphs, though is possible for it to increase. Commute time in turn affects mixing a model can induce after \\textit{m} layers with mixing being the number of interactions between nodes needed to solve a task. When VNs reduce commute time, it is shown that strong mixing increases, reducing the size of \\textit{m} and reducing oversquashing.\n\nHowever, GTs can arbitrarily change commute time and further exceed the previous improvement, though they do incur significant overhead when compared to VNs. A novel sensitivity analysis of GTs and VNs follows which examines the Jacobian of both methods, showing that GTs allow for global heterogeneity via attention as each node depends on non-uniform functions of the values of all nodes at the previous layer. Contrary to this, VNs are independent for nodes further than 2 hops away and thus global information is applied homogeneously. It is worth noting that a full examination of the impact of GTs on commute time is left as a future research direction.\nThis leads to the proposal of VN_\\textit{G} to bridge the gap between VNs and GTs. This takes the form of sequential updates. First a local update on nodes, then VN update leveraging the previous nodes, and a final node update as a function of both local and VN updates for each node. An examination of the Jacobian shows that the sensitivity of each node to non-neighbors becomes a function of the topology while appearing to maintain local bias.\n\nThe need for heterogeneity in VN_\\textit{G} is empirically shown by examining the similarity of the attention matrix of a trained GT model on the nodes of several graphs. An increase in similarity implies reduced heterogeneity and therefore a reduced gap between the performance of GT and the (less) heterogeneous methods. The performance of models during experiments matches this observation.\nIn line with the discussion of the paper, experiments to compare MPNN + VN_\\textit{G} with other baselines for graph-level tasks demonstrates improved performance over MPNN + VN on tasks requiring heterogeneity and matching performance of GT methods, which has some implication for the impact of long-range dependencies for tasks.\n\nThe appendix of the piece also includes an examination of MPNN + VN with PairNorm and demonstrates that, for the linear case, the benefits of MPNN + VN are not due to its ability to produce the results of PairNorm to reduce oversmoothing. In fact, when MPNN + VN replicates PairNorm, its expressivity is reduced.", "questions": "Beginning on line #1430 are what appear to be notes used to write Appendix C that were not removed. \n\nLine #373 refers to Theorem 3.4 and should instead be Corollary 3.4.\n\nIt would be nice to have the Jacobian of GT at least somewhere in the appendix.\n\nIn Table 1 what is the PE in GatedGCN+PE+VN? Also, in the text of 5.1 it is only referred to as GatedGCN+VN\n\nI was not able to discern what the arrows in the heading of each of the tables indicated.\n\nAppendix J seems unnecessary as Fig. 1 would be more useful in the main text, if it wasn’t so small.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The piece does an excellent job of addressing a shortcoming in the literature on when and why Virtual Node are helpful from a theoretical perspective. It provided an extensive juxtaposition with a competing method and identified a key component of the performance gap between the two in specific settings (graph-level tasks). An incremental approach that has begun to appear in other works is further discussed and the piece contains the first theoretical analysis to justify its use.\nAdditionally, with minimal additional work an appendix of the paper proving the benefit of VNs does not come from their ability to replicate PairNorm for the linear case, which is rather a hindrance.", "weaknesses": "I do not believe that there are any significant weaknesses to this paper and find it to be acceptable. Minor changes may improve the piece, but also to an undue amount of additional work and conflict with length requirements.\n\nMPNN + VN can beat GTs as shown in Tables 1 and 3 with the observation that long-range dependencies may not play as large of a role for these tasks. This leads me to wonder about the role of the inductive bias from the locality of MPNN’s, though this is addressed Rampášek et al. which instead leads be to the impact of VN_\\textit{G} on mixing.\n\nI do not have a better alternative, but the empirical analysis to answer Q2 of Section 5.1 oddly seems self-justifying to me. In addition, GatedGCN+PE is shown in Table 2. to have superior performance to all the methods of Table 1. For Pept-Func while remaining competitive for Pept-Struct.\n\nIt seems that Appendix C concludes the proof of Theorem B.1 but only proves that there are filters which can be learned by MPNN but not MPNN-VN. The remainder in this seems mostly to be contained in Theorem C.1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "61k9M6iRoW", "reviewer": "Reviewer_cijV", "summary": "The goal of this paper is to exploit the use of a virtual node to improve the performance of graph neural networks. The focus is specifically on the problem of oversquashing brought forward by the use of message passing neural networks (MPNNs). The authors first analyze the performance of MPNNs when virtual nodes are used and, then, they propose a new approach that can help improve performance and address the oversquashing problem.", "questions": "- What is the cost of adding a virtual node? Are there hidden computing or performance costs? Can you provide concrete run-time or memory usage results while comparing the cases with and without virtual nodes?\n- How do you justify the significance of your final results given that the performance is very close to state of art? For example, can you discuss the practical implications of the performance improvements that you achieved.\n- Can you better articulate why MPNNs with virtual nodes are more effective than graph transformers?\n- What is the main theoretical contributions when it comes to your proofs? How does it differ from the papers from which you adapted the theory? Please provide a point-by-point comparison between your theoretical results and the most closely related prior works.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The problem of oversquashing has been less studied in the prior art, and this work makes an important contribution towards this area\n+ The analysis of oversquashing and the use of virtual nodes is important. The result connecting improvements to the graph spectrum is meaningful and helps in improving designs of graph neural networks.\n+ The evaluation of performance compared to graph transformers is meaningful and shows how one can close the gap in performance.", "weaknesses": "- The theoretical results, while relevant, seem to follow directly from prior works. It is not clear whether the contribution is significant theoretically, as opposed to being a merger of known prior results like those from Di Giovanni et al.\n- The argument for using MPNNs with virtual nodes compared to graph transformers is rather weak. I believe graph transformers may in fact remain the architecture of choice. The authors' discussion on this issue is not very convincing.\n- The cost of adding a virtual node is apparently assumed to be negligible or at least it is not discussed.\n- The performance gains do not seem significant enough", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bij3GcWXqu", "reviewer": "Reviewer_rwJ9", "summary": "(1) This paper studies the impact of Virtual Nodes (VNs) on oversquashing, showing that their improvements in network mixing can be bounded by the graph's spectrum.\n(2) This paper identifies a gap between VNs and GTs in capturing heterogeneous node importance, leading to the proposal of MPNN + VNG, which effectively learns heterogeneous node relevance without extra cost.\n(3) This paper validates its insights through experiments, demonstrating that MPNN + VNG consistently outperforms MPNN + VN, particularly in tasks where node heterogeneity is crucial.", "questions": "See the weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Theoretical Contributions are good: (1) It offers the first comprehensive study of the impact of Virtual Nodes (VNs) on the oversquashing phenomenon, providing a foundational understanding of their role in enhancing network performance. (2) By employing sensitivity analysis of node features, the study identifies a significant gap between VNs and GTs regarding their ability to capture heterogeneous node importance, leading to deeper insights into their comparative strengths.\n2. It introduces a novel MPNN + VNG method, that effectively utilizes graph structure to learn a heterogeneous measure of node relevance without incurring additional computational costs.\n3. The paper validates its theoretical insights through extensive ablations and experiments, demonstrating that MPNN + VNG consistently outperforms the MPNN + VN, particularly in tasks where node heterogeneity is crucial.", "weaknesses": "1. ‘To assess if and how a VN helps to mitigate oversquashing, we need to determine whether the commute time of Gvn is smaller than the commute time of the original graph G.’ So which Theorem below can prove this?\n2. Theorem 3.1 highlights how the impact of adding a VN can be determined in terms of the spectrum of the input graph. According to Theorem 3.1, how can it derive the claim of ‘adding a VN reduces the overall commute time’? Theoretically prove this is important.\n3. ‘The result in Corollary 3.4 shows that for real-world graphs where adding a VN significantly reduces the commute time—i.e., (5) is negative’. Please further explain this claim.\n4. ‘In our sensitivity analysis we will show MPNN + VNG to fall in between the fully homogeneous\nMPNN + VN and the potentially fully heterogeneous GTs.’ Please give a brief explain for this claim.\n5. ‘nodes that are more relevant to each of their neighbors, are more likely to contribute more to the global update, instead of weighting each node the same as for MPNN + VN.’ Which part of MPNN + VNG shows this property?\n6. The heterogeneity of nodes is important, for what kind of tasks?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "17kec04V21", "reviewer": "Reviewer_aG7n", "summary": "Message passing neural networks (MPNNs) are known to be limited in their capability to capture long-range interactions between nodes, a problem known as oversquashing. This paper studies the effect of adding a virtual node (VN) on over-squashing, giving an exact characterization in terms of spectral properties of the network. \n\nOversquashing is the problem of fitting information in a constant-sized embedding vector from a neighborhood growing exponentially in terms of radius. This problem is known to occur between nodes at a high commute time from each other. The paper calculates the change in commute time from adding a virtual node, as a function of eigenvectors of the network Laplacian. The change in commute time is verified empirically. \n\nAdditionally, the paper does a brief comparison of MPNN + VN to Graph Transformers (GTs). In light of this comparison, the authors give (formalize) a slightly different VN architecture with interleaved node and VN updates. This architecture is claimed to be better because it incorporates graph structure before aggregating messages at the virtual node. This model is also tested in practice.", "questions": "While the runtime of MPNN + VN_G is the same as MPNN + VN, could there be problems with vanishing gradients since the depth is essentially doubled? \n\nMinor comment: equation 14: \": j \\in V\" missing. same below on line 311", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 1, "strengths": "The paper gives a precise characterization of the difference in commute time when a virtual node is added. Combined with the results on commute time from previous work, this gives a clear insight into how VNs mitigate oversquashing. The difference in commute time is given for pairwise commute time, as well as the average commute time over the network. The result is also connected to the concept of mixing from earlier work, showing that MPNNs with a virtual node can require fewer layers to represent functions that require high mixing. \n\nThe experimental results align with the theoretical findings. The paper is also well written and easy to follow.", "weaknesses": "The comparison of MPNN + VN to Graph Transformers (Section 4) feels somewhat superficial and does not offer significant new insights. The main observation is that graph transformer layer allows for heterogeneous node importance, while MPNN+VN treats nodes with homogeneous importance. \n\nThe authors propose MPNN + VN_G, a formulation with node updates interleaved with the VN update. This formulation is not new, and the authors also say it has been previously shown to improve performance in practice. The claim is that the update allows heterogeneous attention to different nodes, but this seems like a questionable claim. Heterogeneity is due to the different graph topologies: high-degree nodes affect a different number of neighbors proportional to their degree, before new states are aggregated to the VN. This is different from heterogeneity in GTs via the attention mechanism, where different importances can be learned. There is a note about this on line 349, but I feel like the section is still overselling its results. It is also worth mentioning that a traditional MPNN + VN is also capable of heterogeneous node importance in the weaker sense, just with at least 3 layers. \n\nOverall, the primary contribution of the paper seems to be Theorem 3.1. A downside of this theorem is its practical application. The authors mention that the change in commute time from adding a virtual node can sometimes be negative (e.g. in a complete graph). The experiments show significant avereage commute time reduction for some graph datasets, but the paper does not make it clear whether these experimental results can be reliably generalized in practical applications. \n\nGiven that commute time was already introduced in previous work, all we have now seems to be a formula. The formula is complicated and without real practical use. Theory is best if it is actually usable, but I don't know how to use this theory.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6M14J1TPBp", "reviewer": "Reviewer_kkhT", "summary": "This paper provides a comprehensive theoretical analysis of the role of virtual nodes in message passing neural networks, specifically addressing the oversquashing problem and long-range interaction limitations. The authors characterize how virtual nodes improve network mixing abilities and mitigate oversquashing based on underlying network topology. Additionally, they propose a variant of virtual nodes that can assign different importance to nodes based on graph structure, offering a more effective and computationally efficient solution for graph-level tasks compared to traditional approaches.", "questions": "The MNIST and CIFAR10 datasets are both image datasets. Why are they being used in graph-related research or this paper?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper provides a detailed theoretical analysis addressing the issues of \"oversquashing and node heterogeneity\". \nEach chapter of this paper presents a detailed problem statement, followed by a comprehensive theoretical analysis and the design of corresponding algorithms to tackle these issues.", "weaknesses": "1.Although this paper provides a lot of theoretical analysis and derivation, the conclusions are unclear. For example, Theorem 3.1. The conclusion is a complex expression. Can the author further simplify it through approximation or other means?\n\n2.The experimental results of this paper show almost no improvement compared to other methods (Tables 1-3).\n\n3.Although the content of this paper is substantial, it lacks a framework diagram. Readers find it difficult to intuitively understand what contributions this paper has and the relationships between the various contributions.\n\n4.This paper attempts to highlight its experimental results through bright colors, but the bright green color makes readers uncomfortable. In addition, the excessive use of different colors makes the experimental results appear somewhat messy, for example in Table 2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)