# Understanding Virtual Nodes: Oversquashing and Node Heterogeneity arXiv: https://arxiv.org/abs/2405.13526 ยท HTML: https://mlsanity.com/paper/2405.13526/ ## Key facts - Cited by 14 papers in the map (data through 14 Oct 2026). - Builds on 48 of its 63 references that are in the map. - First posted on arXiv 22 May 2024. ## Builds on (most cited first, 30 of 48) - [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018) - [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017) - [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020) - [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018) - [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018) - [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022) - [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020) - [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020) - [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021) - [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021) - [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019) - [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018) - [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021) - [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020) - [PairNorm: Tackling Oversmoothing in GNNs](https://mlsanity.com/paper/1909.12223/) (2019) - [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022) - [Revisiting Graph Neural Networks: All We Have is Low-Pass Filters](https://mlsanity.com/paper/1905.09550/) (2019) - [A Note on Over-Smoothing for Graph Neural Networks](https://mlsanity.com/paper/2006.13318/) (2020) - [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020) - [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019) - [Representing Long-Range Context for Graph Neural Networks with Global Attention](https://mlsanity.com/paper/2201.08821/) (2022) - [Structure-Aware Transformer for Graph Representation Learning](https://mlsanity.com/paper/2202.03036/) (2022) - [Exphormer: Sparse Transformers for Graphs](https://mlsanity.com/paper/2303.06147/) (2023) - [How Powerful are Spectral Graph Neural Networks](https://mlsanity.com/paper/2205.11172/) (2022) - [On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology](https://mlsanity.com/paper/2302.02941/) (2023) - [ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representations](https://mlsanity.com/paper/1911.07979/) (2019) - [Graph Inductive Biases in Transformers without Message Passing](https://mlsanity.com/paper/2305.17589/) (2023) - [Global Self-Attention as a Replacement for Graph Convolution](https://mlsanity.com/paper/2108.03348/) (2021) - [Understanding Oversquashing in GNNs through the Lens of Effective Resistance](https://mlsanity.com/paper/2302.06835/) (2023) - [A Generalization of ViT/MLP-Mixer to Graphs](https://mlsanity.com/paper/2212.13350/) (2022) ## Built on by (most cited first, 14 of 14) - [Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning](https://mlsanity.com/paper/2505.15547/) (2025) - [Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Survey](https://mlsanity.com/paper/2411.17429/) (2024) - [Homomorphism Counts as Structural Encodings for Graph Learning](https://mlsanity.com/paper/2410.18676/) (2024) - [Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Models](https://mlsanity.com/paper/2510.17457/) (2025) - [Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNs](https://mlsanity.com/paper/2511.13010/) (2025) - [Short-Range Oversquashing](https://mlsanity.com/paper/2511.20406/) (2025) - [Position: Don't be Afraid of Over-Smoothing And Over-Squashing](https://mlsanity.com/paper/2601.07419/) (2026) - [GrapHist: Graph Self-Supervised Learning for Histopathology](https://mlsanity.com/paper/2603.00143/) (2026) - [Local Virtual Nodes for Alleviating Over-Squashing in Graph Neural Networks](https://mlsanity.com/paper/2508.20597/) (2025) - [Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Survey](https://mlsanity.com/paper/2605.00951/) (2026) - [RAwR: Role-Aware Rewiring via Approximate Equitable Partition](https://mlsanity.com/paper/2605.09457/) (2026) - [Graph Hierarchical Recurrence for Long-Range Generalization](https://mlsanity.com/paper/2605.18387/) (2026) - [Escaping Oversquashing: Addressable and Support-Aware Global Memory for Message Passing Networks](https://mlsanity.com/paper/2608.02709/) (2026) - [LEED: Local Embedding Evolution Distance for over-smoothing estimation and virtual node selection in GNN](https://mlsanity.com/paper/2608.09596/) (2026) ## Abstract (arXiv) While message passing neural networks (MPNNs) have convincing success in a range of applications, they exhibit limitations such as the oversquashing problem and their inability to capture long-range interactions. Augmenting MPNNs with a virtual node (VN) removes the locality constraint of the layer aggregation and has been found to improve performance on a range of benchmarks. We provide a comprehensive theoretical analysis of the role of VNs and benefits thereof, through the lenses of oversquashing and sensitivity analysis. First, we characterize, precisely, how the improvement afforded by VNs on the mixing abilities of the network and hence in mitigating oversquashing, depends on the underlying topology. We then highlight that, unlike Graph-Transformers (GTs), classical instantiations of the VN are often constrained to assign uniform importance to different nodes. Consequently, we propose a variant of VN with the same computational complexity, which can have different sensitivity to nodes based on the graph structure. We show that this is an extremely effective and computationally efficient baseline for graph-level tasks.