Understanding Virtual Nodes: Oversquashing and Node Heterogeneity

## Abstract

Abstract Message passing neural networks (MPNNs) have been shown to have limitations in terms of expressivity and modeling 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 oversmoothing, oversquashing, and sensitivity analysis. First, in contrast to prior belief, we find that VNs typically avoid replicating anti-smoothing approaches to maintain expressive power. Second, 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. Finally, we highlight that, unlike Graph-Transformers (GT), 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 on graph-level tasks.

## 1 Introduction

Graph Neural Networks (GNNs) [, , ] are a popular framework for learning on graphs. GNNs typically adopt a message passing paradigm [], 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 [, , ] and cannot count certain substructures [, ]. Besides, the repeated aggregation of local messages can either make node representations indistinguishable—a process known as ‘oversmoothing’ [, ]—or limit the models’ ability to capture long-range dependencies—a phenomenon called ‘oversquashing’ [].

In particular, oversquashing strongly depends on the graph-topology, since it describes the inability of MPNNs to reliably exchange information between pairs of nodes with large commute time [].
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 message-passing [, , ], adding global descriptors [], or rewiring operations based on spatial or spectral quantities [, ]. A notable case is given by Graph-Transformers (GTs) [, ], where global attention is used to weight the messages of each node pair.

Virtual Nodes. While GTs incur a large memory cost, a 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 []. This is widely used in practice [, ] with empirical successes [, ]. However, besides recent work connecting VNs to GTs [, ], 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 VN through the lenses of oversmoothing, oversquashing and sensitivity analysis. Our analysis sheds light on the connection between VN and existing anti-smoothing techniques, the impact VN has on reducing oversquashing by affecting the commute time, and the gap between VN and GTs in terms of the sensitivity to other nodes’ features. Specifically, our main contributions are the following:

- •
In Section 3 we contest prior belief that a reason for the success of MPNN + VN is their ability to simulate methods which prevent oversmoothing. We tackle this point by comparing the expressivity of MPNN + VN and anti-smoothing techniques through polynomial filters.
- •
In Section 4 we provide the first, systematic study of the impact of VN on the oversquashing phenomenon. We show that, differently from more general rewiring techniques such as GTs, the improvement brought by VN 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 5 we find a gap between VN and GT in their ability to capture heterogeneous node importance. Our theory motivates a new formulation of MPNN + VN, simply denoted by MPNN + VNG, that better leverages the graph structure to learn a heterogeneous measure of node relevance, at no additional cost.
- •
Finally, in Section 6, 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.

## 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 $\textbf{A}\in\mathbb{R}^{n\times n}$, where $n=|V|$, and the 1-hop neighborhood of a node is $N_{i}=\{j\in V:(j,i)\in E\}$. Furthermore, node features $\{h_{i}:i\in V\}\subset\mathbb{R}^{d}$ are provided as input. Message passing layers are defined using learnable update and aggregation functions $\mathsf{up}$ and $\mathsf{agg}$ as follows

$$ $\displaystyle h^{(\ell+1)}_{i}=\mathsf{up}^{(\ell)}(h^{(\ell)}_{i},~{}\mathsf{ agg}^{(\ell)}(\{h^{(\ell)}_{j}:j\in N_{i}\})),$ (1) $$

where $h^{(\ell)}_{i}$ is the feature of node $i$ at layer $\ell$, $\mathsf{up}$ is a learnable update function (typically an MLP) and $\mathsf{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 [] are not universal [] and are at most as powerful as the 1-WL test in distinguishing graphs [, ].
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 []. In fact, oversquashing limits the MPNN’s ability to solve tasks with strong interactions among nodes at large commute time [, , ]. Finally, MPNNs may incur oversmoothing, whereby node features attain the same value as the number of layers increases [, , ].

Graph Transformers (GTs). An extension of the MPNN-class is given by Graph-Transformers (GTs) [, , , , , ], where a global attention mechanism connecting all pairs of nodes augments (or entirely replaces []) the 1-hop aggregation in MPNNs. GTs increase the expressive power of MPNNs by heavily relying on structural and positional encodings [], and entirely bypass the issue of oversquashing since the global attention breaks all potential bottlenecks arising from the graph topology. This comes at a price though, with GTs incurring quadratic memory cost and being sensitive to the choice of positional (structural) encodings.

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 [, ]. A standard formulation of message passing with virtual nodes [], referred to as MPNN + VN in the following, is:

$$ $\displaystyle h^{(\ell+1)}_{\mathsf{vn}}$ $\displaystyle=\mathsf{up}^{(\ell)}(h^{(\ell)}_{\mathsf{vn}},~{}\mathsf{agg}_{ \mathsf{vn}}^{(\ell)}(\{h^{(\ell)}_{j}:j\in V\})),$ (2) $\displaystyle h^{(\ell+1)}_{i}$ $\displaystyle=\mathsf{up}^{(\ell)}(h^{(\ell)}_{i},~{}\mathsf{agg}^{(\ell)}(\{h ^{(\ell)}_{j}:j\in N_{i}\}),h^{(\ell)}_{\mathsf{vn}}).$ $$

The class MPNN + VN extends MPNNs in (1) to a multi-relational graph $G_{\mathsf{vn}}$ obtained by adding a node VN connected to all $i\in V$, where any new edge is distinguished from the ones in the input graph.

Understanding VN: Open Questions and Challenges. Augmenting MPNNs with VN has often been shown to improve performance [, ]. Nonetheless, a careful analysis of how and when VN helps is still lacking. Key related work is Cai et al. [], which relied on the universal approximation property of DeepSets [] to show that MPNN + VN with hidden state dimensions of $O(n^{d})$ and $O(1)$ layers can approximate a self-attention layer. Their argument though discards the topology and holds in a non-uniform regime, raising questions about its practical implications. Additionally, Cai et al. [] conjectured that MPNN + VN benefits from being able to simulate strategies for mitigating oversmoothing such as PairNorm []. Crucially though, VN is mainly added to networks so to model non-local interactions, as follows from (2) where any node pair is separated by at most 2 hops through VN. Nonetheless, neither a formal analysis on the extent to which MPNN + VN mitigates oversquashing, nor a fine-grained comparison between GTs and MPNN + VN from the point of view of sensitivity analysis (i.e. interactions among node features in a layer), have been conducted so far.

Outline of This Work. We provide a systematic study of MPNN + VN through the lenses of oversmoothing, oversquashing, and sensitivity analysis. We show that: In contrast to prior belief, the ability of VN to emulate anti-smoothing approaches is likely not beneficial (§3); The improvement brought by VN in mitigating oversquashing depends on the spectrum of the graph (§4); Differently from GTs, 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 (§5); The framework VNG consistently improves over VN, closing the empirical gap with GTs (§6).

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. [] (§3). Graph-level benchmarks (both classification and regression) offer a comprehensive test bed to compare VN and GTs, which is aligned with similar evaluations [, ]. Nonetheless, we emphasize that the statements in Section 5 hold layerwise, and hence do not depend on whether the task is graph-level or not; additionally, we can extend the results in Section 4 to node-level tasks following [, Appendix E].

## 3 MPNN + VN and Smoothing

Despite the empirical success of MPNN + VN, the reasons behind these improvements still lack a thorough understanding. To this aim, Cai et al. [] postulated that MPNN + VN is also beneficial due to its ability to replicate PairNorm [], a framework designed to mitigate oversmoothing. In this section 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 [], 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 [, ]. To address the claims in Cai et al. [] and compare MPNN + VN and PairNorm, in this section we adopt the assumptions in [] and other theoretical works on oversmoothing [], and consider networks whose layers are linear. In particular, to assess advantages of MPNN + VN over PairNorm, we study their expressivity. Since aggregating $m$ linear layers yields a polynomial filter of the form $p(\mathbf{A})\mathbf{H}$, where $\mathbf{H}$ are the input node features, we choose as expressivity metric precisely the ability of a model to learn such polynomial filters.
In fact, under mild assumptions, polynomial filters are comparable to the 1-WL test []. Additionally, when the input features $\mathbf{H}$ are constant, polynomial filters (5) coincide with graph moments, a metric of expressivity studied in Dehmamy et al. [], further validating our approach.

Measuring Expressivity With Polynomial Filters. Since in this section we 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 a linear update with a residual connection:

$$ $\mathbf{H}^{(\ell+1)}=\mathbf{H}^{(\ell)}+\mathbf{A}\mathbf{H}^{(\ell)}\mathbf {W}^{(\ell)},$ (3) $$

where $\mathbf{W}^{(\ell)}$ is a $d\times d$ weight matrix and $\mathbf{H}^{(\ell)}$ is the $n\times d$ feature matrix at layer $\ell$. Similarly, for MPNN + VN, we consider a layer update with mean aggregation for VN, akin to Cai et al. []:

$$ $\mathbf{H}^{(\ell+1)}=\mathbf{H}^{(\ell)}+\mathbf{A}\mathbf{H}^{(\ell)}\mathbf {W}^{(\ell)}+\frac{1}{n}\mathbf{1}\mathbf{1}^{\top}\mathbf{H}^{(\ell-1)} \mathbf{Q}^{(\ell)},$ (4) $$

with $\mathbf{Q}^{(\ell)}$ a weight matrix and $\mathbf{1}\in\mathbb{R}^{n}$ the vector of ones. For simplicity, we assume that the output after $m$ layers $\mathbf{Y}_{m}$ also has dimension $d$ and choose a mean pooling operation in the final layer, so that given a weight matrix $\boldsymbol{\Theta}$ we have $\mathbf{Y}_{m}=\boldsymbol{\Theta}\mathsf{Mean}(\mathbf{H}^{(m)})$, with $\mathbf{H}^{(m)}$ computed by either (3) or (4). We can express $\mathbf{Y}_{m}$ as a graph-level polynomial filter in terms of $d\times d$ weight matrices $\{\boldsymbol{\Theta}_{k}\}$:

$$ $\mathbf{Y}_{m}=\mathsf{Mean}\big{(}\sum_{k=0}^{m}\mathbf{A}^{k}\mathbf{H} \boldsymbol{\Theta}_{k}\big{)}^{\top}.$ (5) $$

We note now that MPNN + VN (4) recovers PairNorm when $\mathbf{Q}^{(\ell)}=-\mathbf{I}$, with $\mathbf{I}$ the $d\times d$-identity matrix. We denote this special choice as MPNN - VN. The proof of the following Theorem and all subsequent results, can be found in Appendices B, C and D.

###### Theorem 3.1 .

There are polynomial filters (5) that can be learned by MPNN but not by MPNN - VN. Conversely, any polynomial filter learned by MPNN (3) can also be learned by MPNN + VN (4). Furthermore, there exist polynomial filters that can be learned by MPNN + VN but not by MPNN.

Theorem 3.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 3.1, we argue that, contrary to the claim in Cai et al. [], MPNN + VN generally avoids replicating PairNorm to maintain its greater expressivity. We empirically validate this statement in Section 6.1 and report the smoothing effects of VN on common benchmarks in Appendix F.1.

In summary, our analysis suggests that on graph-level tasks, benefits of MPNN + VN are independent of their ability to replicate methods such as PairNorm. In fact, for a graph-level prediction, whose output is computed using a global mean, some ‘smoothing’ is actually unavoidable. In particular, the mean pooling in (5) corresponds to projecting the final features precisely onto the subspace spanned by $\mathbf{1}\in\mathbb{R}^{n}$, i.e., the kernel of the (unnormalized) graph Laplacian associated with oversmoothing [, ]. This allows us to clarify a key difference when studying oversmoothing for node-level and graph-level tasks. In the former case, if two node features become indistinguishable, 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 B.1 in Appendix B for results relating VN to the choice of pooling and to ablations in Appendix F.1.

###### Theorem 3.1 .

## 4 MPNN + VN and Oversquashing

In Section 3 we used polynomial filters to show that, on graph-level tasks, MPNN + VN loses expressive power when it replicates anti-oversmoothing methods like PairNorm. Nonetheless, 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 VN to oversquashing has been derived thus far. In this section, we fill this gap in 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 oversquashing, we analyze general realizations of (2), whose layer updates have the form:

$$ $\displaystyle h_{\mathsf{vn}}^{(\ell+1)}$ $\displaystyle=\sigma\Big{(}\boldsymbol{\Omega}_{\mathsf{vn}}^{(\ell)}h_{ \mathsf{vn}}^{(\ell)}+\frac{1}{\tilde{n}}\sum_{j=1}^{n}\phi^{(\ell)}_{\mathsf{ vn}}(h_{\mathsf{vn}}^{(\ell)},h_{j}^{(\ell)})\Big{)},$ $\displaystyle h_{i}^{(\ell+1)}$ $\displaystyle=\sigma\Big{(}\boldsymbol{\Omega}^{(\ell)}h_{i}^{(\ell)}+\sum_{j= 1}^{n}\mathsf{A}_{ij}\psi^{(\ell)}(h_{i}^{(\ell)},h_{j}^{(\ell)})+\psi^{(\ell) }_{\mathsf{vn}}(h_{i}^{(\ell)},h_{\mathsf{vn}}^{(\ell)})\Big{)},$ (6) $$

where $\sigma$ is a pointwise nonlinear map, $\mathbf{\mathsf{A}}$ is a (potentially) normalized adjacency matrix, $\boldsymbol{\Omega}$ is a weight matrix, $\psi,\psi_{\mathsf{vn}},\phi_{\mathsf{vn}}$ are (learnable) message functions, and $\tilde{n}$ depends on our normalization choice (e.g. $\tilde{n}=1$ for sum, or $\tilde{n}=n$ for mean). A key observation is that (4) coincide with the MPNNs analyzed in Di Giovanni et al. [], but operating on the multi-relational graph $G_{\mathsf{vn}}$ with adjacency

$$ $\mathbf{A}_{\mathsf{vn}}=\begin{pmatrix}\mathbf{A}&\mathbf{1}\\ \mathbf{1}^{\top}&0\end{pmatrix},\quad\mathbf{1}=(1,\ldots,1)^{\top}\in\mathbb {R}^{n},$ (7) $$

where edges connecting VN to nodes in $G$ have different type. Di Giovanni et al. [], Black et al. [], Di Giovanni et al. [] have shown that oversquashing prevents the underlying model from exchanging information between nodes at large commute time $\tau$, where $\tau(i,j)$ measures the expected number of steps for a random walk to commute between $i$ and $j$. Accordingly, to assess if and how VN helps mitigate oversquashing, we need to determine whether the commute time $\tau_{\mathsf{vn}}$ of $G_{\mathsf{vn}}$ is smaller than the commute time $\tau$ of the original graph $G$. Below, we let $v_{\ell}$ be an orthonormal basis of eigenvectors for the graph Laplacian $\mathbf{L}=\mathbf{D}-\mathbf{A}$, with associated eigenvalues $0=\lambda_{0}<\lambda_{1}\leq\ldots\leq\lambda_{n-1}$.

###### Theorem 4.1 .

The commute time between nodes $i,j$ after adding a VN changes as

$$ $\tau_{\mathsf{vn}}(i,j)-\tau(i,j)=2|E|\sum_{\ell=1}^{n-1}\frac{1}{\lambda_{ \ell}(\lambda_{\ell}+1)}\Big{(}\frac{n}{|E|}\lambda_{\ell}-1\Big{)}(v_{\ell}(i )-v_{\ell}(j))^{2}.$ (8) $$

In particular, the average change in commute time is:

$$ $\frac{1}{n^{2}}\sum_{i,j=1}^{n}(\tau_{\mathsf{vn}}(i,j)-\tau(i,j))=\frac{4|E|} {n}\sum_{\ell=1}^{n-1}\frac{1}{\lambda_{\ell}(\lambda_{\ell}+1)}\Big{(}\frac{n }{|E|}\lambda_{\ell}-1\Big{)}.$ (9) $$

The result above highlights how a VN’s impact can be determined in terms of the spectrum of the input graph. While there are cases, e.g. when the graph is complete, where (9) is positive, for many real-world graphs adding VN reduces the overall commute time: We validate this claim in Section 6.1.

Di Giovanni et al. [] introduced the notion of mixing (see Appendix C), 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-prediction 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 C for details.

###### Theorem 4.2 (Adapted from Thm. 4.4 [ 15 ] ) .

There are graph-functions with mixing between nodes $i\neq j$ larger than some constant independent of $i,j$, such that for an MPNN of bounded weights to learn these functions, the number of layers $m$ must satisfy $m\geq\tau(i,j)/8$.

For real-world graphs like peptides, small molecules, or images, (8) is negative (see §6.1). In light of Theorem 4.2, this means that adding a VN should reduce the minimal number of layers required to learn functions with strong mixing between nodes. We make such connection explicit below:

###### Corollary 4.3 .

Given $G$ and nodes $i,j$ for which (8) is negative, there are graph-functions with mixing between $i\neq j$ larger than some constant independent of $i,j$, such that for an MPNN + VN of bounded weights to learn these functions, the minimal number of layers $m$ becomes

$$ $m\geq\frac{\tau_{\mathsf{vn}}(i,j)}{8}-\frac{|E|}{8}\cdot\sum_{\ell=1}^{n-1} \frac{1}{\lambda_{\ell}(\lambda_{\ell}+1)}\Big{(}\frac{n}{|E|}\lambda_{\ell}-1 \Big{)}(v_{\ell}(i)-v_{\ell}(j))^{2}.$ (10) $$

The result in Corollary 4.3 shows that for real-world graphs where adding a VN significantly reduces the commute time—i.e., (8) is negative—the minimal number of layers required by MPNN + VN to learn graph functions with strong mixing among $i,j$, is 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 Theorem 4.3, meaning that their efficacy is a 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 paying any additional computational price.

###### Theorem 4.1 .

###### Theorem 4.2 (Adapted from Thm. 4.4 [ 15 ] ) .

###### Corollary 4.3 .

## 5 Comparing MPNN + VN and GTs Through Sensitivity Analysis

In Section 4 we showed that MPNN + VN can mitigate oversquashing and the extent to which this is 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 as a more efficient alternative to GTs []. In this section we further compare MPNN + VN and GTs through sensitivity analysis and show that the single layer of a GT can learn a heterogeneous node scoring, while MPNN + VN generally cannot. In light of this analysis, we propose a simple variation of MPNN + VN, called $\text{MPNN}+\text{VN}_{G}$, which better uses the graph to learn a heterogeneous measure of node relevance while retaining the same efficiency as MPNN + VN.

MPNN + VN Layers Are Homogeneous. We start by reporting the layer update of the GPS architecture [], one instance of the GT class that encodes both local and global information:

$$ $h_{i}^{(\ell+1)}=f^{(\ell)}(h_{i,{\rm loc}}^{(\ell+1)}+\mathbf{Q}^{(\ell)}\sum _{k=1}^{n}a(h_{i}^{(\ell)},h_{k}^{(\ell)})h_{k}^{(\ell)}),$ (11) $$

where $f$ is an MLP, $h_{\rm loc}$ is the local update given by the choice of MPNN, and $a$ is the attention module. Depending on data and positional encoding, GTs can capture heterogeneous relations. We can quantify such heterogeneity via sensitivity analysis by deriving that the Jacobian $\partial h_{i}^{(\ell+1)}/\partial h_{k}^{(\ell)}$ is, in general, a function that depends on $k$, meaning that the state of node $i$ at layer $\ell+1$ 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 (4), where the VN update is

$$ $\displaystyle h_{\mathsf{vn}}^{(\ell+1)}$ $\displaystyle=\sigma(\boldsymbol{\Omega}^{(\ell)}_{\mathsf{vn}}h_{\mathsf{vn}} ^{(\ell)}+\mathbf{W}_{\mathsf{vn}}^{(\ell)}\mathsf{Mean}(\{h_{j}^{(\ell)}\})).$ (12) $$

Given a node $k$ at a distance larger than $2$ from node $i$, any message from node $k$ at layer $\ell-1$ is first received by node $i$ at layer $\ell+1$ through the VN.

###### Proposition 5.1 .

For MPNN + VN whose VN update is (12), the Jacobian $\partial h_{i}^{(\ell+1)}/\partial h_{k}^{(\ell-1)}$ is independent of $k$ whenever $k$ and $i$ are separated by more than 2 hops.

We see that node $i$ receives a global yet homogeneous update from VN, where each node $k$ at distance $>2$ contributes the same to its state (after two layers). This in stark contrast to the case of GTs.

$\text{MPNN}+\text{VN}_{G}$: A New Formulation Of VN. Inspired by frameworks such as (11),
to allow for more heterogeneous sensitivity through the VN, we propose $\text{MPNN}+\text{VN}_{G}$, a simple variation to MPNN + VN with the same computational complexity, whose layer updates have the form:

$$ $\displaystyle h^{(\ell+1)}_{i,{\rm loc}}$ $\displaystyle=\mathsf{up}^{(\ell)}(h^{(\ell)}_{i},\mathsf{agg}^{(\ell)}(\{h^{( \ell)}_{j}:j\in N_{i}\})),$ $\displaystyle h^{(\ell+1)}_{\mathsf{vn}}$ $\displaystyle=\mathsf{up}_{\mathsf{vn}}^{(\ell)}(h^{(\ell)}_{\mathsf{vn}}, \mathsf{agg}_{\mathsf{vn}}^{(\ell)}(\{h^{(\ell+1)}_{j,{\rm loc}}:j\in V\})),$ $\displaystyle h^{(\ell+1)}_{i}$ $\displaystyle=\widetilde{\mathsf{up}}^{(\ell)}(h^{(\ell+1)}_{i,{\rm loc}},h^{( \ell+1)}_{\mathsf{vn}}).$ (13) $$

Differently from MPNN + VN (2), we first compute local updates based on the choice of aggregation (i.e. the underlying MPNN model), then we compute a global update through VN using such local representations (as illustrated in Appendix H), and finally we combine the local and non-local representations. To justify how $\text{MPNN}+\text{VN}_{G}$ can assign more heterogeneous values to the global updates associated with the VN, we study the sensitivity of node features. Similarly to (4) and (12), we consider an instance of $\text{MPNN}+\text{VN}_{G}$ of the form:

$$ $h_{i}^{(\ell+1)}=h_{i,{\rm loc}}^{(\ell+1)}+\mathsf{Mean}(\{h_{j,{\rm loc}}^{( \ell+1)}\}),\,\,\,h_{j,{\rm loc}}^{(\ell+1)}=\sigma(\boldsymbol{\Omega}^{(\ell )}h_{i}^{(\ell)}+\sum_{j\in N_{i}}\psi_{ij}^{(\ell)}(h_{i}^{(\ell)},h_{j}^{( \ell)})).$ (14) $$

Differently from (2), two nodes now can exchange information after a single layer. Below, we let $z_{i}^{(\ell)}$ be the argument of $\sigma$ in (14), for each $i\in V$, and $\nabla_{s}$ be the Jacobian with respect to variable $s$.

###### Proposition 5.2 .

Given $i\in V$ and $k\in V\setminus N_{i}$, the Jacobian $\partial h_{i}^{(\ell+1)}/\partial h_{k}^{(\ell)}$ computed using (14) is

$$ $\frac{\partial h_{i}^{(\ell+1)}}{\partial h_{k}^{(\ell)}}=\frac{1}{n}\Big{(}{ \rm diag}(\sigma^{\prime}(z_{k}^{(\ell)}))(\boldsymbol{\Omega}^{(\ell)}+\sum_{ u\in N_{k}}\nabla_{1}\psi^{(\ell)}_{ku}(h_{k}^{(\ell)},h_{u}^{(\ell)}))+\sum_{ u\in N_{k}}{\rm diag}(\sigma^{\prime}(z_{u}^{(\ell)}))\nabla_{2}\psi_{uk}^{( \ell)}(h_{u}^{(\ell)},h_{k}^{(\ell)})\Big{)}.$ $$

We see that the sensitivity of node $i$ to the feature of $k$ is a function of the graph-topology, i.e., the message functions evaluated over the neighbors of $k$. In particular, our proposed variation $\text{MPNN}+\text{VN}_{G}$ uses the same message functions $\psi_{ij}$ to learn a heterogeneous global update. Related to recent advances in graph pooling [, , , ], we utilize the graph structure in the global aggregator; 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. We note that advantages of this approach depend on the choice of the underlying message function $\psi$ in (14) (see Table 8 in Appendix G).

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 heterogeneous 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 6.1.

###### Proposition 5.1 .

###### Proposition 5.2 .

## 6 Experiments

The purpose of this section is to first empirically verify the theoretical claims made in Sections 3, 4 and 5. Then, we evaluate our proposed MPNN + VNG on a diverse set of benchmarks (§6.2).

### 6.1 Ablations

Our ablations aim to validate the previous theoretical results, by answering the following questions:

- (Q1)
*To what extent does MPNN + VN replicate PairNorm on graph-level tasks? [§3]*
- (Q2)
*How does adding a VN affect the average commute time on real-world graphs? [§4]*
- (Q3)
*Which tasks show a gap between MPNN + VN and GT due to node heterogeneity? [§5]*

**Table 1: The effect of PairNorm and MPNN + VN on LRGB tasks.**
| Method | Peptides-Func ($\uparrow$) | Peptides-Struct ($\downarrow$) |
| --- | --- | --- |
| GCN | 0.5930 $\pm 0.0023$ | 0.3496 $\pm 0.0013$ |
| GCN + PairNorm | 0.4980 $\pm 0.0031$ | 0.3471 $\pm 0.0016$ |
| GCN + VN | 0.6623 $\pm 0.0038$ | 0.2488 $\pm 0.0021$ |
| GINE | 0.5498 $\pm 0.0079$ | 0.3547 $\pm 0.0045$ |
| GINE + PairNorm | 0.4698 $\pm 0.0053$ | 0.3562 $\pm 0.0007$ |
| GINE + VN | 0.6346 $\pm 0.0071$ | 0.2584 $\pm 0.0011$ |
| GatedGCN | 0.5864 $\pm 0.0077$ | 0.3420 $\pm 0.0013$ |
| GatedGCN + PairNorm | 0.4674 $\pm 0.0040$ | 0.3551 $\pm 0.0008$ |
| GatedGCN + VN | 0.6477 $\pm 0.0039$ | 0.2523 $\pm 0.0016$ |

Figure: Figure 1: Effect of adding a virtual node on the average commute time of four graph datasets.
Refer to caption: extracted/2405.13526v1/figures/commute_time_plot.png

To answer (Q1) and assess whether MPNN + VN behaves differently to PairNorm in practice, we evaluate both on two graph-level tasks from the Long-Range Benchmarks [] using three different MPNN architectures. It is clear from Table 1 that whilst PairNorm has a damaging impact on the results as hypothesized in Theorem 3.1, MPNN + VN achieves significant gains over the standard MPNN architecture. Further datasets and results using a GatedGCN can be found in Table 9. One explanation for the observed phenomenon is that, on these datasets, MPNN + VN favors alignment between the layerwise representations and the final output representation (a smoothing process). This phenomenon can be observed when comparing the cosine similarity of the pooled representations at each layer to the final pooled representation. Plots of this cosine similarity over the layers can be seen in Appendix F.1 and clearly show that the VN causes a smoothing effect in contrast to PairNorm.

For (Q2) we calculated Equation (9) 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 1 and highlights the tendency for this to be negative. This demonstrates that adding a VN is highly beneficial on real-world graphs since it significantly reduces their commute time, thereby increasing their mixing abilities as per Theorem 4.3.

Here, we aim to provide an empirical justification for the similar performances of MPNN and GT [] and answer (Q3). To measure the heterogeneity of node relevance in the global update, we look at the similarity between the rows of the attention matrix in a GT. In fact, similar rows in $a(h_{i}^{(\ell)},h_{k}^{(\ell)})$ in (11) correspond to assigning similar weights to each node representation, and hence less heterogeneity. To measure this, we calculate the mean standard deviation (std) of each column. We calculated this std on the first layer attention matrix, after training GPS with a GatedGCN as the base MPNN, on four real-world benchmarks from [] and []. In Table 2, we can see that for datasets where the std is small (Peptides-func, Peptides-struct, MNIST), using an MPNN + VN can match or even improve over the GPS implementation. On the other hand, CIFAR10 has a larger std, and we see that GPS outperforms the VN architecture. These results show that the performance gap between MPNN + VN and GTs is 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 5.1). To further show the differences in the attention matrices and the amount of homogeneity on these tasks, we have visualized them in Appendix I. Additionally, we 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 to be equal to their mean. We call this GPS + projection, and it forces the GPS model to become completely homogeneous. Again, we see that on datasets where the homogeneous GatedGCN+VN does well and the std of the attention matrix columns is low, we do not lose much performance with this mean projection. Whereas on CIFAR10, we find that the heterogeneity of nodes is important.

**Table 2: Effects of projecting the non-local part of GPS onto the mean and its comparison to using a VN. We also report the standard deviation of the column sums in the first attention layer.**
| Method | Pept-Func ($\uparrow$) | Pept-Struct ($\downarrow$) | MNIST ($\uparrow$) | CIFAR10 ($\uparrow$) |
| --- | --- | --- | --- | --- |
| GPS | 0.6534 $\pm.0091$ | 0.2509 $\pm.0014$ | 98.051 $\pm.126$ | 72.298 $\pm.356$ |
| GPS + projection | 0.6498 $\pm.0054$ | 0.2487 $\pm.0011$ | 98.176 $\pm.120$ | 71.455 $\pm.513$ |
| GatedGCN+PE+VN | 0.6712 $\pm.0066$ | 0.2481 $\pm.0015$ | 98.122 $\pm.102$ | 70.280 $\pm.380$ |
| std attention layer | 0.0011 | 0.0007 | 0.0006 | 0.0038 |

### 6.2 Evaluating Our Proposed MPNN + VN G MPNN subscript VN 𝐺 \text{MPNN}+\text{VN}_{G} MPNN + VN start_POSTSUBSCRIPT italic_G end_POSTSUBSCRIPT

We first evaluate $\text{MPNN}+\text{VN}_{G}$ on a diverse set of 5 graph-level datasets, comparing against classical MPNN benchmarks, Graph-Transformers [, , , , ], graph rewiring [], a random-walk based method [], and a generalization of ViT/MLP-Mixer []. Crucially, we also compare VNG with the standard implementation of VN [].

**Table 3: Test performance on two LRGB datasets [] and three other benchmarks from []. For Peptides-Func and Peptides-Struct, $\pm$ 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-Func ($\uparrow$) | Pept-Struct ($\downarrow$) | MNIST ($\uparrow$) | CIFAR10 ($\uparrow$) | MalNet-Tiny ($\uparrow$) |
| --- | --- | --- | --- | --- | --- |
| GCN | 0.5930 $\pm 0.0023$ | 0.3496 $\pm 0.0013$ | 90.705 $\pm 0.218$ | 55.710 $\pm 0.381$ | 81.0 |
| GINE | 0.5498 $\pm 0.0079$ | 0.3547 $\pm 0.0045$ | 96.485 $\pm 0.252$ | 55.255 $\pm 1.527$ | 88.98 $\pm 0.56$ |
| GatedGCN | 0.5864 $\pm 0.0077$ | 0.3420 $\pm 0.0013$ | 97.340 $\pm 0.143$ | 67.312 $\pm 0.311$ | 92.23 $\pm 0.65$ |
| GatedGCN+PE | 0.6765 $\pm 0.0047$ | 0.2477 $\pm 0.0009$ | - | 69.948 $\pm 0.499$ | - |
| GatedGCN+PE-ViT | 0.6942 $\pm 0.0075$ | 0.2465 $\pm 0.0015$ | 98.460 $\pm 0.090$ | 71.580 $\pm 0.090$ | - |
| GatedGCN+PE-Mixer | 0.6932 $\pm 0.0017$ | 0.2508 $\pm 0.0007$ | 98.320 $\pm 0.040$ | 70.600 $\pm 0.220$ | - |
| CRaWl | 0.7074 $\pm 0.0032$ | 0.2506 $\pm 0.0022$ | 97.940 $\pm 0.050$ | 69.010 $\pm 0.259$ | - |
| DRew | 0.7150 $\pm 0.0044$ | 0.2536 $\pm 0.0015$ | - | - | - |
| SAN+RWSE | 0.6439 $\pm 0.0075$ | 0.2545 $\pm 0.0012$ | - | - | - |
| EGT | - | - | 98.173 $\pm 0.087$ | 68.702 $\pm 0.409$ | - |
| GRIT | 0.6988 $\pm 0.0082$ | 0.2460 $\pm 0.0012$ | 98.108 $\pm 0.111$ | 76.468 $\pm 0.881$ | - |
| GPS | 0.6534 $\pm 0.0091$ | 0.2509 $\pm 0.0014$ | 98.051 $\pm 0.126$ | 72.298 $\pm 0.356$ | 93.50 $\pm 0.41$ |
| Exphormer | 0.6527 $\pm 0.0043$ | 0.2481 $\pm 0.0007$ | 98.414 $\pm 0.035$ | 74.690 $\pm 0.125$ | 94.02 $\pm 0.21$ |
| GatedGCN+PE+VN | 0.6712 $\pm 0.0066$ | 0.2481 $\pm 0.0015$ | 98.122 $\pm 0.102$ | 70.280 $\pm 0.380$ | 92.62 $\pm 0.57$ |
| GatedGCN+PE+$\text{VN}_{G}$ | 0.6822 $\pm 0.0052$ | 0.2458 $\pm 0.0006$ | 98.626 $\pm 0.100$ | 76.080 $\pm 0.330$ | 93.67 $\pm 0.37$ |

Experimental Details. We evaluated $\text{MPNN}+\text{VN}_{G}$ on the Long-Range Graph Benchmark using a fixed 500k parameter budget and averaging over four runs. These molecular datasets (Peptides-Func,
Peptides-Struct) 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 [], where we run our model over 10 seeds. We also used a code dataset MalNet-Tiny []. This dataset consists of function call graphs with up to 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 [], namely molhiv, molpcba and ppa. Details on datasets and training parameters used, can be found in Appendix E.

Discussion.
We can see from Tables 3 and 4 that our method performs well across a variety of datasets and achieves the highest performance on Peptides-Struct, MNIST, ogbg-molhiv and ogbg-ppa. Furthermore, $\text{MPNN}+\text{VN}_{G}$ improves over MPNN + VN on all tasks, with the largest percentage improvement being shown on CIFAR10 (8.25%). The latter is perfectly aligned with the discussion in Section 5 and 6.1, where we have described the importance of heterogeneity to the VN and justified how heterogeneity is particularly required on CIFAR10. Additionally, on the peptides datasets, which have small degrees but large diameters, we find that using $\text{MPNN}+\text{VN}_{G}$ can perform better than a variety of transformer-based approaches. Not only does this suggest that MPNN + $\text{VN}_{G}$ 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. [] where the lower performance of MPNNs compared to GTs was found to 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 [] on this task. However, we show that we can match the performance of the full transformer and still be more computationally efficient.

**Table 4: Test performance on graph-level OGB benchmarks []. Shown is the mean % $\pm$ 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 ($\uparrow$) | MolPCBA ($\uparrow$) | PPA ($\uparrow$) |
| --- | --- | --- | --- |
| GCN | 76.06 $\pm 0.97$ | 20.20 $\pm 0.24$ | 68.39 $\pm 0.84$ |
| GIN | 75.58 $\pm 1.40$ | 22.66 $\pm 0.28$ | 68.92 $\pm 1.00$ |
| DeeperGCN | 78.58 $\pm 1.17$ | 27.81 $\pm 0.38$ | 77.12 $\pm 0.71$ |
| CRaWL | - | 29.86 $\pm 0.25$ | - |
| SAN | 77.85 $\pm 0.28$ | 27.65 $\pm 0.42$ | - |
| GPS | 78.80 $\pm 1.01$ | 29.07 $\pm 0.28$ | 80.15 $\pm 0.33$ |
| GCN+VN | 75.99 $\pm 1.19$ | 24.24 $\pm 0.34$ | 68.57 $\pm 0.61$ |
| GIN+VN | 77.07 $\pm 1.49$ | 27.03 $\pm 0.23$ | 70.37 $\pm 1.07$ |
| GatedGCN+PE+VN | 76.87 $\pm 1.36$ | 28.48 $\pm 0.26$ | 80.27 $\pm 0.26$ |
| GatedGCN+PE+$\text{VN}_{G}$ | 79.10 $\pm 0.86$ | 29.17 $\pm 0.27$ | 81.17 $\pm 0.30$ |

## 7 Conclusion

In §3 we have highlighted how MPNN + VN may not emulate anti-smoothing approaches such as PairNorm to maintain expressive power and have shown in §6.1 that this holds in practice. In §4, 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 §6.1. In §5, we show that standard VN implementations cannot assign different scores to nodes in the global update. Consequently, we propose $\text{MPNN}+\text{VN}_{G}$, a variation of MPNN + VN sharing the same computational complexity, that uses the graph to learn heterogeneous node importance. We show that this outperforms MPNN + VN on a range of benchmarks, precisely corresponding to those where GTs outperform MPNN + VN by learning heterogenos node scores.

Limitations and Future Work. Our expressivity analysis in §3 relies on layers which are linear. Although our experiments in §6.1 show that it holds in practical, non-linear scenarios, understanding VN and oversmoothing in a non-linear setting will be interesting future work. Additionally, we have not empirically explored the change in commute time afforded by GT and rewiring-based approaches. Future work can compare these approaches and VN, to assess their mixing abilities.

## Appendix A Outline of the Appendix

We report proofs and additional details pertaining to Section 3 in Appendix B. In particular, we derive 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 C. Proofs for the sensitivity analysis results in Section 5 are finally reported in Appendix D.

Regarding additional ablations and experimental details, we comment on training details, hyperparameters, datasets, and hardware in Appendix E. Next, we describe additional experiments confirming that VN introduces smoothing on graph-level tasks in Appendix F, focusing on the impact of the final pooling. We further validate the role played by the underlying MPNN model in MPNN + VNG in Appendix G, propose a visualization of the framework in Appendix H, and finally report attention maps learned by Graph-Transformer on benchmarks—used as a proxy-measure for the heterogeneity required by the task—in Appendix I.

## Appendix B Proofs of Results in Section 3

###### Proof of Theorem 3.1 .

First, we note that similarly to Cai et al. [], the VN state is initialized to be zero, i.e., the first layer of Equation 4 is

$$ $\mathbf{H}^{(1)}=\mathbf{H}+\mathbf{A}\mathbf{H}\mathbf{W}^{(0)}$ (15) $$

where $\mathbf{H}$ is matrix of input node features.
It is trivial to 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 $\{\mathbf{Q}_{\ell}\}$ to be zero in (4), then we recover the MPNN case in (3). Accordingly, to prove that MPNN + VN is strictly more expressive than MPNN when learning polynomial filters, we only need to show that there exist $m\in\mathbb{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 $\mathbf{H}^{(2)}$ explicitly as

$$ $\displaystyle\mathbf{H}^{(2)}$ $\displaystyle=\mathbf{H}+\mathbf{A}\mathbf{H}(\mathbf{W}^{(0)}+\mathbf{W}^{(1) })+\mathbf{A}^{2}\mathbf{H}\mathbf{W}^{(0)}\mathbf{W}^{(1)}+\frac{1}{n}\mathbf {1}\mathbf{1}^{\top}\mathbf{H}\mathbf{Q}^{(1)}.$ (16) $$

Recall that given the choice of global mean pooling, the final output is

$$ $\mathbf{Y}_{2}=\tilde{\boldsymbol{\Theta}}\mathsf{Mean}(\mathbf{H}^{(2)}).$ $$

Since $\mathsf{Mean}(\mathbf{H}^{(2)})=(\mathbf{H}^{(2)})^{\top}\mathbf{1}/n$, we find

$$ $\mathbf{Y}_{2}=\boldsymbol{\Theta}_{0}\mathsf{Mean}(\mathbf{H})+\boldsymbol{ \Theta}_{1}\mathsf{Mean}(\mathbf{A}\mathbf{H})+\boldsymbol{\Theta}_{2}\mathsf{ Mean}(\mathbf{A}^{2}\mathbf{H}),$ $$

where the weights characterizing the family of quadratic polynomial filters are defined by the system:

$$ $\displaystyle\boldsymbol{\Theta}_{0}$ $\displaystyle=\tilde{\boldsymbol{\Theta}}\Big{(}\mathbf{I}+(\mathbf{Q}^{(1)})^ {\top}\Big{)},$ (17) $\displaystyle\boldsymbol{\Theta}_{1}$ $\displaystyle=\tilde{\boldsymbol{\Theta}}\Big{(}(\mathbf{W}^{(0)})^{\top}+( \mathbf{W}^{(1)})^{\top}\Big{)},$ (18) $\displaystyle\boldsymbol{\Theta}_{2}$ $\displaystyle=\tilde{\boldsymbol{\Theta}}\Big{(}(\mathbf{W}^{(1)})^{\top}( \mathbf{W}^{(0)})^{\top}\Big{)}.$ (19) $$

Assume now that the class of polynomial filters we wish to learn, have a vanishing zeroth-order term, i.e., $\boldsymbol{\Theta}_{0}=\mathbf{0}$. For the MPNN not containing a VN, corresponding to $\mathbf{Q}^{(1)}=\mathbf{0}$ in (17), then we must have $\tilde{\boldsymbol{\Theta}}=\mathbf{0}$. Therefore, the only quadratic polynomial without a zeroth-order term that can be learned by a linear MPNN as in (3) of degree 2 is the trivial polynomial. Conversely, an MPNN + VN can, for example, learn the weights $\mathbf{Q}^{(1)}=-\mathbf{I}$ to ensure $\boldsymbol{\Theta}_{0}=\mathbf{0}$, and have non-trivial first and second-order terms using the $\mathbf{W}$-weight matrices.
This proves that on any 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., $\mathbf{Q}^{(\ell)}=-\mathbf{I}$ for $\ell\in\mathbb{N}$, after two layers, the term $\boldsymbol{\Theta}_{0}$ is always zero. Since MPNN after two layers can learn quadratic polynomial filters with non-trivial zero-th order terms, this completes the proof.
∎

###### Proof of Theorem 3.1 .

### B.1 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 an alternative global pooling, which instead of projecting the final features onto $\mathbf{1}/n$ (i.e. computing the mean), projects the final-layer features onto $\mathbf{v}\in\mathbb{R}^{n}$ satisfying $\mathbf{v}^{\top}\mathbf{1}=0,$

$$ $\mathbf{Y}_{m}^{\mathbf{v}}=\boldsymbol{\tilde{\Theta}}(\mathbf{H}^{(m)})^{ \top}\mathbf{v}=\sum_{k=0}^{m}\boldsymbol{\Theta}_{k}(\mathbf{A}^{k}\mathbf{H} )^{\top}\mathbf{v}.$ (20) $$

We can then show that there exist polynomial filters that MPNN + VN is no longer able to express when we replace mean pooling with $\mathbf{v}$-pooling.

###### Proposition B.1 .

Given $\mathbf{v}$ orthogonal to $\mathbf{1}$, a linear MPNN + VN of $m$ layers can generate weights $\{\boldsymbol{\Theta}_{k}\}$ in the output $\mathbf{Y}_{m}$ in (5) that cannot be generated by a linear MPNN + VN using a global pooling induced by $\mathbf{v}$, as in (20).

###### Proof of Proposition B.1 .

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 (17). However, since $\mathbf{1}$ and $\mathbf{v}$ are orthogonal, then there is no $\mathbf{Q}^{(1)}$-term in Equation 17. As such, we see that the quadratic polynomial $\mathbf{Y}_{2}^{\mathbf{v}}$ has zero-th order coefficient vanishing if and only if $\tilde{\boldsymbol{\Theta}}=\mathbf{0}$, i.e., the quadratic polynomial is trivial. Conversely, MPNN + VN can instead learn non-trivial quadratic polynomial without zero-th order term by simply setting $\mathbf{Q}^{(1)}=-\mathbf{I}$.
∎

A Fourier Perspective on Pooling. Proposition B.1 highlights that MPNN + VN may lose the ability to express polynomial filters when we no longer have alignment between VN and the global pooling. This result raises a an important question: What is the bias resulting from a certain choice of global pooling? Consider linear MPNNs as above where the global pooling is obtained by projecting onto some $\mathbf{v}\in\mathbb{R}^{n}$, with the case $\mathbf{v}=\mathbf{1}$ recovering the mean (sum) pooling. Given $\{\psi_{i}\}\subset\mathbb{R}^{n}$, a basis of orthonormal eigenvectors of $\mathbf{A}$, with eigenvalues $\{\lambda_{i}\}$, we write $\mathbf{v}=\sum_{i}c_{i}\psi_{i}$, where $\{c_{i}\}$ are the graph Fourier coefficients of $\mathbf{v}$. Given $1\leq r\leq d$, the channel $r$ of the final output as per (20) takes on the following form in the Fourier domain

$$ $y_{r}=\sum_{k=0}^{m}\sum_{p=1}^{d}(\Theta_{k})_{rp}\sum_{i=0}^{n-1}c_{i} \lambda_{i}^{k}\langle h^{p},\psi_{i}\rangle,$ (21) $$

where $h^{p}\in\mathbb{R}^{n}$ is the channel $p$ of the input features. Accordingly, the Fourier coefficients $\{c_{i}\}$ of $\mathbf{v}$ and the associated frequencies $\{\lambda_{i}\}$, determine which projection $\langle h^{p},\psi_{i}\rangle$ 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 B.1, highlights that the underlying tasks depend on the projection of the features onto those eigenvectors $\{\psi_{i}\}$ aligned with the vector $\mathbf{1}$.

###### Proposition B.1 .

###### Proof of Proposition B.1 .

## Appendix C Proofs of Results in Section 4

In this section, we report the proofs of the theoretical results in Section 4 along with additional details. We start by proving Theorem 4.1.

###### Proof of Theorem 4.1 .

We start by recalling that the effective resistance between two nodes $i$ and $j$, denoted by $R(i,j)$, can be computed as []:

$$ $R(i,j)=L_{ii}^{\dagger}+L_{jj}^{\dagger}-2L_{ij}^{\dagger},$ (22) $$

where $\mathbf{L}^{\dagger}$ is the pseudo-inverse of the graph Laplacian, i.e.,

$$ $\mathbf{L}^{\dagger}=\sum_{\ell=1}^{n-1}\frac{1}{\lambda_{\ell}}v_{\ell}v_{ \ell}^{\top}.$ (23) $$

Accordingly, we can write the effective resistance between two nodes $i$ and $j$ explicitly as

$$ $R(i,j)=\sum_{\ell=1}^{n-1}\frac{1}{\lambda_{\ell}}(v_{\ell}(i)-v_{\ell}(j))^{2}.$ (24) $$

Naturally, for the graph $G_{\mathsf{vn}}$ we obtain from adding VN, the formula changes as

$$ $R_{\mathsf{vn}}(i,j)=\sum_{\ell=1}^{n}\frac{1}{\lambda^{\mathsf{vn}}_{\ell}}(v ^{\mathsf{vn}}_{\ell}(i)-v^{\mathsf{vn}}_{\ell}(j))^{2},$ (25) $$

where $\mathbf{L}_{\mathsf{vn}}v^{\mathsf{vn}}_{\ell}=\lambda^{\mathsf{vn}}_{\ell}v^{
\mathsf{vn}}_{\ell}$. When we add the virtual node though, the adjacency matrix changes as in Equation 7, meaning that the graph Laplacian can be written as

$$ $\mathbf{L}_{\mathsf{vn}}=\mathbf{D}_{\mathsf{vn}}-\mathbf{A}_{\mathsf{vn}}= \begin{pmatrix}\mathbf{D}+\mathbf{I}&\mathbf{0}\\ \mathbf{0}^{\top}&n\end{pmatrix}-\begin{pmatrix}\mathbf{A}&\mathbf{1}\\ \mathbf{1}^{\top}&0\end{pmatrix}=\begin{pmatrix}\mathbf{L}+\mathbf{I}&-\mathbf {1}\\ -\mathbf{1}^{\top}&n\end{pmatrix}.$ (26) $$

We recall now that $v_{0}=\frac{1}{\sqrt{n}}\mathbf{1}$, i.e., $\mathbf{L}\mathbf{1}=\mathbf{0}$. Accordingly, we find that $v^{\mathsf{vn}}_{0}=\frac{1}{\sqrt{n+1}}\begin{pmatrix}\mathbf{1}\\
1\end{pmatrix}$, i.e., $\mathbf{L}_{\mathsf{vn}}v^{\mathsf{vn}}_{0}=\mathbf{0}$. Similarly, from the block decomposition of $\mathbf{L}_{\mathsf{vn}}$ we derive that

$$ $\mathbf{L}_{\mathsf{vn}}\begin{pmatrix}v_{\ell}\\ 0\end{pmatrix}=\begin{pmatrix}(\mathbf{L}+\mathbf{I})v_{\ell}\\ -\mathbf{1}^{\top}v_{\ell}\end{pmatrix}=(\lambda_{\ell}+1)\begin{pmatrix}v_{ \ell}\\ 0\end{pmatrix},$ (27) $$

where we have used that $v_{\ell}$ are orthogonal to $v_{0}=\frac{1}{\sqrt{n}}\mathbf{1}$ for all $\ell\geq 1$. Accordingly $\begin{pmatrix}v_{\ell}\\
0\end{pmatrix}$ are eigenvectors of $\mathbf{L}_{\mathsf{vn}}$ for all $1\leq\ell\leq n-1$ with eigenvalue $\lambda_{\ell}+1$. Finally we note that

$$ $\mathbf{L}_{\mathsf{vn}}\frac{1}{\sqrt{n^{2}+n}}\begin{pmatrix}\mathbf{1}\\ -n\end{pmatrix}=\frac{1}{\sqrt{n^{2}+n}}\begin{pmatrix}(\mathbf{L}+\mathbf{I}) \mathbf{1}+n\mathbf{1}\\ -\mathbf{1}^{\top}\mathbf{1}-n^{2}\end{pmatrix}=(1+n)\frac{1}{\sqrt{n^{2}+n}} \begin{pmatrix}\mathbf{1}\\ -n\end{pmatrix},$ (28) $$

which means that $\frac{1}{\sqrt{n^{2}+n}}\begin{pmatrix}\mathbf{1}\\
-n\end{pmatrix}$ is the final eigenvector of $\mathbf{L}_{\mathsf{vn}}$ with eigenvalue $n+1$.
We can then use the spectral decomposition of $\mathbf{L}_{\mathsf{vn}}$ to write the effective resistance between nodes $i$ and $j$ after adding VN as

$$ $\displaystyle R_{\mathsf{vn}}(i,j)$ $\displaystyle=\sum_{\ell=1}^{n}\frac{1}{\lambda^{\mathsf{vn}}_{\ell}}(v^{ \mathsf{vn}}_{\ell}(i)-v^{\mathsf{vn}}_{\ell}(j))^{2}=\sum_{\ell=1}^{n-1}\frac {1}{\lambda_{\ell}+1}(v_{\ell}(i)-v_{\ell}(j))^{2}+\frac{1}{n+1}\frac{1}{n^{2} +n}(1-1)^{2}$ $\displaystyle=\sum_{\ell=1}^{n-1}\frac{1}{\lambda_{\ell}+1}(v_{\ell}(i)-v_{ \ell}(j))^{2}.$ $$

Finally, we recall that on a graph, the commute time $\tau$ is proportional to the effective resistance [], i.e.,

$$ $\tau(i,j)=2|E|R(i,j).$ $$

Accordingly, we can use that on $G_{\mathsf{vn}}$ the number of edges is equal to $|E|+n$ and compare the commute time after adding VN with the baseline case:

$$ $\displaystyle\tau_{\mathsf{vn}}(i,j)-\tau(i,j)$ $\displaystyle=\sum_{\ell=1}^{n-1}\Big{(}\frac{2(|E|+n)}{\lambda_{\ell}+1}- \frac{2|E|}{\lambda_{\ell}}\Big{)}(v_{\ell}(i)-v_{\ell}(j))^{2}$ $\displaystyle=2|E|\sum_{\ell=1}^{n-1}\frac{1}{\lambda_{\ell}(\lambda_{\ell}+1) }\Big{(}\frac{n}{|E|}\lambda_{\ell}-1\Big{)}(v_{\ell}(i)-v_{\ell}(j))^{2},$ $$

which is precisely Equation 8. We can the sum over all pairs of nodes to obtain

$$ $\displaystyle\sum_{i,j=1}^{n}(\tau_{\mathsf{vn}}(i,j)-\tau(i,j))$ $\displaystyle=2|E|\sum_{i,j=1}^{n}\sum_{\ell=1}^{n-1}\frac{1}{\lambda_{\ell}( \lambda_{\ell}+1)}\Big{(}\frac{n}{|E|}\lambda_{\ell}-1\Big{)}(v_{\ell}(i)-v_{ \ell}(j))^{2}$ $\displaystyle=2|E|\sum_{\ell=1}^{n-1}\frac{1}{\lambda_{\ell}(\lambda_{\ell}+1) }\Big{(}\frac{n}{|E|}\lambda_{\ell}-1\Big{)}\sum_{i,j=1}^{n}(v_{\ell}(i)-v_{ \ell}(j))^{2}$ $\displaystyle=2|E|\sum_{\ell=1}^{n-1}\frac{1}{\lambda_{\ell}(\lambda_{\ell}+1) }\Big{(}\frac{n}{|E|}\lambda_{\ell}-1\Big{)}\sum_{i,j=1}^{n}\Big{(}v^{2}_{\ell }(i)+v^{2}_{\ell}(j)-2v_{\ell}(i)v_{\ell}(j)\Big{)}.$ $$

We now use that $v_{\ell}$ form an orthonormal basis, accordingly: $\sum_{i=1}^{n}v_{\ell}(i)^{2}=1$. Similarly, since $v_{\ell}$ is orthogonal to $v_{0}$ and hence to $\mathbf{1}$, we get $v_{\ell}^{\top}\mathbf{1}=\sum_{i=1}^{n}v_{\ell}(i)=0$. Therefore,

$$ $\sum_{i,j=1}^{n}\Big{(}v^{2}_{\ell}(i)+v^{2}_{\ell}(j)-2v_{\ell}(i)v_{\ell}(j) \Big{)}=2n-2\sum_{i=1}^{n}v_{\ell}(i)\sum_{j=1}^{n}v_{\ell}(j)=2n.$ $$

We finally obtain:

$$ $\frac{1}{n^{2}}\sum_{i,j=1}^{n}(\tau_{\mathsf{vn}}(i,j)-\tau(i,j))=\frac{4|E|} {n}\sum_{\ell=1}^{n-1}\frac{1}{\lambda_{\ell}(\lambda_{\ell}+1)}\Big{(}\frac{n }{|E|}\lambda_{\ell}-1\Big{)},$ $$

which completes the proof.
∎

Remark: We note that according to (8), we expect $\tau_{\mathsf{vn}}(i,j)<\tau(i,j)$ whenever the two nodes have large commute time on the input graph, i.e. due to the graph having a bottleneck where $\lambda_{1}$ is small and the Fiedler eigenvector is such that $v_{1}(i)\cdot v_{i}(j)<0$ since $i,j$ belong to different communities. As such, adding a VN should indeed beneficial for graphs with bottlenecks, while it may slightly increase the commute time between nodes that were well connected in the graph due to the addition of a VN spreading information out from the pair. This intuition is validated in Section 6.1, where we show that on real-world graphs adding a VN decreases the average commute time significantly.

###### Corollary C.1 .

If we let $\alpha:=1+n/|E|$, then

$$ $-\frac{4|E|\alpha}{\lambda_{1}(\lambda_{1}+1)}\leq\tau_{\mathsf{vn}}(i,j)- \alpha\tau(i,j)\leq-\frac{4|E|\alpha}{\lambda_{n-1}(\lambda_{n-1}+1)}.$ (29) $$

###### Proof.

From (8) and the proof above, we derive

$$ $\displaystyle\tau_{\mathsf{vn}}(i,j)-\alpha\tau(i,j)$ $\displaystyle=\sum_{\ell=1}^{n-1}\Big{(}\frac{2(|E|+n)}{\lambda_{\ell}+1}- \frac{2(|E|+n)}{\lambda_{\ell}}\Big{)}(v_{\ell}(i)-v_{\ell}(j))^{2}$ $\displaystyle=-2(|E|+n)\sum_{\ell=1}^{n-1}\frac{1}{\lambda_{\ell}(\lambda_{ \ell}+1)}(v_{\ell}(i)-v_{\ell}(j))^{2}$ $\displaystyle\geq-\frac{2|E|\alpha}{\lambda_{1}(\lambda_{1}+1)}\sum_{\ell=1}^{ n-1}(v_{\ell}(i)-v_{\ell}(j))^{2}=-\frac{4|E|\alpha}{\lambda_{1}(\lambda_{1}+1)}$ $$

where the last equality follows from

$$ $\displaystyle\sum_{\ell=1}^{n-1}(v_{\ell}(i)-v_{\ell}(j))^{2}$ $\displaystyle=\sum_{\ell=1}^{n-1}(v^{2}_{\ell}(i)+v^{2}_{\ell}(j)-2v_{\ell}(i) v_{\ell}(j))$ $\displaystyle=2\Big{(}1-\frac{1}{n}\Big{)}-2\sum_{\ell=0}^{n-1}v_{\ell}(i)v_{ \ell}(j)+2v_{0}(i)v_{0}(j)=2\Big{(}1-\frac{1}{n}\Big{)}+\frac{2}{n}=2,$ $$

where we have used the orthonormality of the eigenvectors for $i\neq j$. The upper bound can be proved in the same way using that $\lambda_{\ell}\leq\lambda_{n-1}$ for each $\ell$.
∎

###### Proof of Corollary 4.3 .

Consider an MPNN + VN. We recall that $\mathsf{mix}_{y}(i,j)$ is the mixing induced by a graph-level function among the features of nodes $i$ and $j$, and is defined as []

$$ $\mathsf{mix}_{y}(i,j)=\max_{\mathbf{H}}\max_{1\leq\alpha,\beta\leq d}\left| \frac{\partial^{2}y(\mathbf{H})}{\partial h_{i}^{\alpha}\partial h_{j}^{\beta} }\right|.$ $$

According to Di Giovanni et al. [], when the mixing induced by the MPNN after $m$ layers, denoted here as $\mathsf{mix}^{(m)}(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 necessary to solve the problem at hand. Since we can write the system in (4) as the system of MPNN analyzed in Di Giovanni et al. [], operating on the graph $G_{\mathsf{vn}}$, 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 a graph-level function $y$ with mixing $\mathsf{mix}_{y}(i,j)$ is

$$ $m\geq\frac{\tau_{\mathsf{vn}}(i,j)}{8}+\alpha_{\mathsf{vn}}\mathsf{mix}_{y}(i, j)+\beta_{\mathsf{vn}},$ $$

where the constants $\alpha_{\mathsf{vn}}$ and $\beta_{\mathsf{vn}}$ are independent of nodes $i,j$, and without loss of generality we have taken $c_{2}=1/2$ in Theorem 4.4 of Di Giovanni et al. []— clearly, the result generalize to any $c_{2}\leq 1$. As such, we see that a necessary condition for the family of graph-level functions with mixing $\mathsf{mix}_{y}(i,j)>-\beta_{\mathsf{vn}}/\alpha_{\mathsf{vn}}$ to be learned by MPNN + VN is that

$$ $m\geq\frac{\tau(i,j)}{8}\geq\Big{(}1+\frac{n}{|E|}\Big{)}\Big{(}\frac{\tau(i,j )}{8}-\frac{|E|}{2\lambda_{1}(\lambda_{1}+1)}\Big{)},$ $$

where we have used Equation 8 in the last inequality. This completes the proof.
∎

Accordingly, MPNN + VN can improve upon the minimal number of layers required to 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 C.1 of $\lambda_{1}$.

###### Proof of Theorem 4.1 .

###### Corollary C.1 .

###### Proof.

###### Proof of Corollary 4.3 .

## Appendix D Proofs of Results in Section 5

###### Proof of Proposition 5.1 .

Recall that we consider an MPNN + VN whose layer update is of the form

$$ $\displaystyle h_{\mathsf{vn}}^{(\ell+1)}$ $\displaystyle=\sigma\Big{(}\boldsymbol{\Omega}_{\mathsf{vn}}h_{\mathsf{vn}}^{( \ell)}+\mathbf{W}_{\mathsf{vn}}^{(\ell)}\frac{1}{n}\sum_{j=1}^{n}h_{j}^{(\ell) }\Big{)}$ $\displaystyle h_{i}^{(\ell+1)}$ $\displaystyle=\sigma\Big{(}\boldsymbol{\Omega}^{(\ell)}h_{i}^{(\ell)}+\sum_{j= 1}^{n}\mathsf{A}_{ij}\psi^{(\ell)}(h_{i}^{(\ell)},h_{j}^{(\ell)})+\psi^{(\ell) }_{\mathsf{vn}}(h_{i}^{(\ell)},h_{\mathsf{vn}}^{(\ell)})\Big{)}.$ $$

If $i,k\in V$ with $k$ outside the 2-hop neighborhood of $i$, then any message sent from $k$ to $i$ will arrive after 2 layers through the VN. Since the VN update is homogeneous though, node $i$ cannot distinguish which node $k$ sent the message. Explicitly, we can compute the derivatives and obtain

$$ $\displaystyle\frac{\partial h_{i}^{(\ell+1)}}{\partial h_{k}^{(\ell-1)}}=\frac {1}{n}\sigma^{\prime}(z_{i}^{(\ell)})\nabla_{2}\psi_{\mathsf{vn}}^{(\ell)}(h_{ i}^{(\ell)},h_{\mathsf{vn}}^{(\ell)})\sigma^{\prime}(z_{\mathsf{vn}}^{(\ell-1) })\mathbf{W}_{\mathsf{vn}}^{(\ell)},$ $$

where $z_{i}^{(\ell)}$ is the argument of the nonlinear activation $\sigma$, $\sigma^{\prime}(z)$ is the diagonal derivative matrix computed at $z$ and $\nabla_{2}$ 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 $k$ 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) to nodes. This completes the proof.
∎

###### Proof of Proposition 5.2 .

Consider an instance of $\text{MPNN}+\text{VN}_{G}$ whose layer updates have the form

$$ $\displaystyle h_{i}^{(\ell+1)}$ $\displaystyle=h_{i,{\rm loc}}^{(\ell+1)}+\mathsf{Mean}(\{h_{j,{\rm loc}}^{( \ell+1)}\}),$ $\displaystyle h_{j,{\rm loc}}^{(\ell+1)}$ $\displaystyle=\sigma(\boldsymbol{\Omega}^{(\ell)}h_{i}^{(\ell)}+\sum_{j\in N_{ i}}\psi_{ij}^{(\ell)}(h_{i}^{(\ell)},h_{j}^{(\ell)})).$ $$

Given $i,k\in V$ where node $k$ is outside the 1-hop neighborhood of $i$, any message sent from $k$ to $i$ will arrive after 1 layer through the VN—in other words, $\partial h_{i,{\rm loc}}^{(\ell+1)}/\partial h_{k}^{(\ell)}=0$. We can compute the derivatives and obtain

$$ $\displaystyle\frac{\partial h_{i}^{(\ell+1)}}{\partial h_{k}^{(\ell)}}$ $\displaystyle=\frac{1}{n}\sum_{j=1}^{n}\frac{\partial{h_{j,{\rm loc}}^{(\ell+1 )}}}{{\partial h_{k}^{(\ell)}}}$ $\displaystyle=\frac{1}{n}\sum_{j=1}^{n}\sigma^{\prime}(z_{j}^{(\ell)})\Big{(} \boldsymbol{\Omega}^{(\ell)}\delta_{jk}+\sum_{u\in N_{j}}\nabla_{1}\psi_{ju}(h ^{(\ell)}_{j},h^{(\ell)}_{u})\delta_{jk}+\nabla_{2}\psi_{ju}(h^{(\ell)}_{j},h^ {(\ell)}_{u})\delta_{uk}\Big{)}$ $\displaystyle=\frac{1}{n}\Big{(}\sigma^{\prime}(z_{k}^{(\ell)})\Big{(} \boldsymbol{\Omega}^{(\ell)}+\sum_{u\in N_{k}}\nabla_{1}\psi^{(\ell)}_{ku}(h_{ k}^{(\ell)},h_{u}^{(\ell)})\Big{)}+\sum_{u\in N_{k}}\sigma^{\prime}(z_{u}^{( \ell)})\nabla_{2}\psi_{uk}^{(\ell)}(h_{u}^{(\ell)},h_{k}^{(\ell)})\Big{)},$ $$

where $\delta_{pq}$ is the Kronecker delta with indices $p,q$ and in the last sum we have replaced the dumb index $j$ with $u$. This completes the proof.
∎

###### Proof of Proposition 5.1 .

###### Proof of Proposition 5.2 .

## Appendix E Experimental Details

In this section, we provide further details about our experiments.

### E.1 Hardware

All experiments were run on a single V100 GPU.

### E.2 Description of Datasets

Below, we provide descriptions of the datasets on which we conduct experiments.

MNIST and CIFAR10 (CC BY-SA 3.0 and MIT License) []. 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 (train/validation/test) splits; 55K/5K/10K for MNIST and 45K/5K/10K for CIFAR10.

ogbg-molhiv and ogbg-molpcba (MIT License) []. These are molecular property prediction datasets which use a common node and edge featurization that represents chemophysical properties. Ogbg-molhiv is a binary classification task, predicting the molecule’s ability to inhibit HIV replication and ogbg-molpcba is a multi-task binary classification where 128 bioassays are predicted.

ogbg-ppa (CC-0 License) []. 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) []. This is a 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-func and Peptides (CC-BY-NC 4.0) []. 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 a regression task involving 11 3D structural properties of the peptides.

### E.3 Dataset Splits and Random Seeds

All the benchmarks follow the standard train/validation/test 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 on the output of four runs.

### E.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 5 and 6 were obtained.

OGB datasets. For both ogbg-molpcba and ogbg-ppa we used the same hyperparameters as used in Rampášek et al. [] but the hidden dimension of the MPNN was adjusted so that we had a similar parameter budget. For ogbg-molhiv, we found it to be beneficial to reduce the number of layers to 4 to align with the number of layers used in Bouritsas et al. [] but kept the same parameters for the positional encoding and the optimization process.

Peptides-Func 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-Passing [1, 2, 3],

and we used the optimization parameters recently proposed by [] where they train for 250 epochs with an AdamW optimizer [], and a cosine annealing learning rate scheduler with a base learning rate of 0.001. When optimizing over the number of layers of message-passing, we changed the hidden dimension to ensure that the parameter budget was around 500K.

MNIST, CIFAR10, MalNet-Tiny. On these benchmarks, we used the same dropout, positional encondings and optimization parameters as used by Shirzad et al. []. The only parameter we optimised for was the number of layers in 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 et al. [].

**Table 5: Best performing hyperparameters for GatedGCN+PE+$\text{VN}_{G}$ in Table 3.**
| Hyperparameter | Peptides-Func | Peptides-Struct | MNIST | CIFAR10 | MalNet-Tiny |
| --- | --- | --- | --- | --- | --- |
| #Layers | 4 | 4 | 5 | 7 | 5 |
| Hidden dim | 136 | 136 | 46 | 40 | 72 |
| Dropout | 0.0 | 0.2 | 0.1 | 0.1 | 0.0 |
| Graph pooling | mean | mean | mean | mean | mean |
| FeedForward Block | False | False | True | True | True |
| Positional Encoding | RWSE-20 | LapPE-16 | LapPE-8 | LapPE-8 | None |
| PE dim | 16 | 16 | 8 | 8 | - |
| PE encoder | Linear | Linear | Linear | DeepSet | - |
| Batch size | 200 | 200 | 16 | 16 | 16 |
| Learning Rate | 0.001 | 0.001 | 0.001 | 0.001 | 0.0005 |
| #Epochs | 250 | 250 | 100 | 100 | 150 |
| #Parameters | 492,217 | 492,217 | 110,148 | 117,066 | 281,453 |

**Table 6: Best performing hyperparameters for GatedGCN+PE+$\text{VN}_{G}$ in Table 4.**
| Hyperparameter | ogbg-molhiv | ogbg-molpcba | ogbg-ppa |
| --- | --- | --- | --- |
| #Layers | 4 | 5 | 3 |
| Hidden dim | 90 | 384 | 284 |
| Dropout | 0.0 | 0.2 | 0.1 |
| Graph pooling | mean | mean | mean |
| FeedForward Block | True | True | True |
| Positional Encoding | RWSE-16 | RWSE-16 | None |
| PE dim | 16 | 20 | - |
| PE encoder | Linear | Linear | - |
| Batch size | 32 | 512 | 32 |
| Learning Rate | 0.0001 | 0.0005 | 0.0003 |
| #Epochs | 100 | 100 | 200 |
| #Parameters | 360,221 | 7,519,580 | 2,526,501 |

## Appendix F Smoothing and the Importance of Graph Structure

In this section, we explore the performance on 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 7. 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 ogbg-molpcba. Subtracting the mean at each layer before using the mean pooling function in the final layer, means that we are ignoring the output of the message-passing layer which is aligned with the final representation. We can see this as a good measure of the importance of 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 7: Analyzing the performance of GatedGCN where we subtract or add the mean of the message-passing output at each layer.**
| Method | Peptides-Func ($\uparrow$) | Peptides-Struct ($\downarrow$) | ogbg-molhiv ($\uparrow$) | ogbg-molpcba ($\uparrow$) |
| --- | --- | --- | --- | --- |
| GatedGCN | 0.5864 $\pm 0.0077$ | 0.3420 $\pm 0.0013$ | 0.7827 $\pm 0.0111$ | 0.2714 $\pm 0.0014$ |
| GatedGCN + mean | 0.6692 $\pm 0.0042$ | 0.2522 $\pm 0.0012$ | 0.7677 $\pm 0.0138$ | 0.2569 $\pm 0.0034$ |
| GatedGCN - mean | 0.4675 $\pm 0.0040$ | 0.3566 $\pm 0.0007$ | 0.7594 $\pm 0.0096$ | 0.2866 $\pm 0.0016$ |

### F.1 Cosine Distance Plots

We analyzed the layerwise smoothing on the graph-level LRGB datasets [] using a GatedGCN with and without a 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.

Figure: (a) The cosine distance between the embedding at each layer and the final graph representation after training a GatedGCN, as well as with a VN and a transformer layer on Peptides-func.
Refer to caption: extracted/2405.13526v1/figures/peptides-func-cosine.png

## Appendix G 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 $\text{VN}_{G}$ when the base MPNN is a GCN or a GatedGCN. Whilst we generally see an improvement with our implementation, this improvement is much larger when we use a GatedGCN. As previously argued, this is due to the fact that in a GatedGCN, the aggregation weights each neighbor through a learnable gate and we can thus have a learnable node importance based on the graph topology. This is in contrast to a GCN where we have a homogeneous node update.

**Table 8: Performance of $\text{MPNN}+\text{VN}_{G}$ in comparison to virtual node with positional encodings.**
| Method | ogbg-molhiv ($\uparrow$) | ogbg-molpcba ($\uparrow$) | peptides-func ($\uparrow$) | peptides-struct ($\downarrow$) | CIFAR10 ($\uparrow$) |
| --- | --- | --- | --- | --- | --- |
| GCN+PE+VN | 0.7599 $\pm 0.0119$ | 0.2456 $\pm 0.0034$ | 0.6562 $\pm 0.0070$ | 0.2540 $\pm 0.0008$ | 68.957 $\pm 0.381$ |
| GCN+PE+$\text{VN}_{G}$ | 0.7678 $\pm 0.0111$ | 0.2481 $\pm 0.0032$ | 0.6537 $\pm 0.0026$ | 0.2497 $\pm 0.0008$ | 68.756 $\pm 0.172$ |
| GatedGCN+PE+VN | 0.7687 $\pm 0.0136$ | 0.2848 $\pm 0.0026$ | 0.6712 $\pm 0.0066$ | 0.2481 $\pm 0.0015$ | 70.280 $\pm 0.380$ |
| GatedGCN+PE+$\text{VN}_{G}$ | 0.7884 $\pm 0.0099$ | 0.2917 $\pm 0.0027$ | 0.6822 $\pm 0.0052$ | 0.2458 $\pm 0.0006$ | 76.080 $\pm 0.301$ |
| GCN % Increase | +1.04 | +1.02 | -0.38 | +1.69 | -0.29 |
| GatedGCN % Increase | +2.56 | +2.42 | +1.64 | +0.89 | +8.25 |

As an extension to Section 3, we compared the performance of GatedGCN with augmentations which involve adding a VN in Table 9. Additionally, we look at the effect of applying PairNorm on the datasets. We see that applying PairNorm to the GatedGCN, a 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 a 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-Func ($\uparrow$) | Peptides-Struct ($\downarrow$) | ogbg-molhiv ($\uparrow$) | ogbg-molpcba ($\uparrow$) |
| --- | --- | --- | --- | --- |
| GatedGCN | 0.5864 $\pm 0.0077$ | 0.3420 $\pm 0.0013$ | 0.7827 $\pm 0.0111$ | 0.2714 $\pm 0.0014$ |
| GatedGCN with PairNorm | 0.4674 $\pm 0.0040$ | 0.3551 $\pm 0.0008$ | 0.7645 $\pm 0.0128$ | 0.2621 $\pm 0.0026$ |
| GatedGCN + VN | 0.6477 $\pm 0.0039$ | 0.2523 $\pm 0.0016$ | 0.7676 $\pm 0.0172$ | 0.2823 $\pm 0.0026$ |

## Appendix H Visualization of MPNN + VN G MPNN subscript VN 𝐺 \text{MPNN}+\text{VN}_{G} MPNN + VN start_POSTSUBSCRIPT italic_G end_POSTSUBSCRIPT

Here we visualize the differences between our implementation of $\text{MPNN}+\text{VN}_{G}$ and a standard MPNN+VN. Our model uses the local MPNN acting on the original graph to weight the nodes based on their importance. This means that the VN can perform a heterogeneous global update.

Figure: Figure 3: Comparing MPNN+VN with our proposed $\text{MPNN}+\text{VN}_{G}$.

## Appendix I 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 5 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 CIFAR10 is less homogeneous, as measured by the standard deviation of the columns sums.

Figure: Figure 4: First layer attention maps of the self-attention matrix in the GPS framework for different datasets.

## Peer Reviews

confidence: 3
contribution: 4
initial_rating: 8
presentation: 3
questions: Beginning on line #1430 are what appear to be notes used to write Appendix C that were not removed. 

Line #373 refers to Theorem 3.4 and should instead be Corollary 3.4.

It would be nice to have the Jacobian of GT at least somewhere in the appendix.

In 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

I was not able to discern what the arrows in the heading of each of the tables indicated.

Appendix J seems unnecessary as Fig. 1 would be more useful in the main text, if it wasn’t so small.
soundness: 3
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.
Additionally, 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.
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}.
A 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.

However, 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.
This 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.

The 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.
In 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.

The 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.
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.

MPNN + 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.

I 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.

It 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.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
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?
- 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.
- Can you better articulate why MPNNs with virtual nodes are more effective than graph transformers?
- 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.
soundness: 3
strengths: + The problem of oversquashing has been less studied in the prior art, and this work makes an important contribution towards this area
+ 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.
+ The evaluation of performance compared to graph transformers is meaningful and shows how one can close the gap in performance.
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.
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.
- 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.
- The cost of adding a virtual node is apparently assumed to be negligible or at least it is not discussed.
- The performance gains do not seem significant enough

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: See the weaknesses.
soundness: 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.
2. 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.
3. 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.
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.
(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.
(3) This paper validates its insights through experiments, demonstrating that MPNN + VNG consistently outperforms 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?
2. 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.
3. ‘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.
4. ‘In our sensitivity analysis we will show MPNN + VNG to fall in between the fully homogeneous
MPNN + VN and the potentially fully heterogeneous GTs.’ Please give a brief explain for this claim.
5. ‘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?
6. The heterogeneity of nodes is important, for what kind of tasks?

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 4
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? 

Minor comment: equation 14: ": j \in V" missing. same below on line 311
soundness: 3
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. 

The experimental results align with the theoretical findings. The paper is also well written and easy to follow.
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. 

Oversquashing 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. 

Additionally, 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.
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. 

The 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. 

Overall, 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. 

Given 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.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: The MNIST and CIFAR10 datasets are both image datasets. Why are they being used in graph-related research or this paper?
soundness: 3
strengths: This paper provides a detailed theoretical analysis addressing the issues of "oversquashing and node heterogeneity". 
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.
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.
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?

2.The experimental results of this paper show almost no improvement compared to other methods (Tables 1-3).

3.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.

4.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.

Meta-review: This paper investigates how adding a virtual node affects MPNN regarding oversquashing and sensitivity to distant nodes. It provides a theoretical framework that relates commute times in graphs to the presence of VNs, offering precise spectral conditions under which VNs help reduce oversquashing. Authors propose also a variant of the VN mechanism that can exploit heterogeneous node importance without incurring extra computational cost, narrowing the gap with more complex graph transformer architectures.

Strengths:  The work gives an interesting interpretation of of virtual nodes in MPNNs, not only by confirming that they can mitigate oversquashing but also by characterizing when and why this occurs through spectral analysis. This contributes new insights into which kinds of graph topologies benefit most from VNs. The proposed VN variant outperforms standard baselines without increased complexity, showing that the insights from theory can translate into (potential) practical improvements. The paper is generally well-structured, with good evidence supporting its claims.

Weaknesses: Some reviewers considered the theoretical contributions more incremental than groundbreaking, noting that the results build closely on established concepts. I agree with them, but still feel that it a nice interpretation of hese results. Others felt that certain formulas and theoretical aspects were complex, offering limited practical guidance. I believe this is expected for this kind of work. Additionally, while the authors compared their approach to GTs, some found the comparison lacking in depth. The reported empirical gains, though consistent, are not dramatic, leading some to question the overall impact. This is true, but again, I don't think the main point of the paper is to provide SOTA results, as the title indicate: "Understanding Virtual Nodes". In this sense, I think the paper is well aligned with its objectives.

Overall, I believe that the paper makes a valuable contribution to the understanding of virtual nodes in MPNNs, and I recommend acceptance despite those concerns.

Decision: Accept (Poster)