  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.
