Research map / Graph learning / GNN architectures
Understanding Virtual Nodes: Oversquashing and Node Heterogeneity
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Theoretically analyzes how virtual nodes (VN) reduce commute time and oversquashing via the Laplacian spectrum, shows standard VN gives homogeneous node sensitivity, and proposes MPNN + VN_G, a graph-structure-aware VN variant that matches GT-like heterogeneity at the same O(|E|+n) cost.
Problem
Virtual nodes are widely used to mitigate oversquashing in MPNNs, but it was unclear how much they reduce commute time and how their sensitivity to node features compares with graph transformers.
Approach
Derives the exact change in commute time after adding a VN as a function of Laplacian eigenvalues and eigenvectors, shows the standard VN aggregates nodes uniformly (Jacobian independent of source node k), and proposes VN_G which aggregates local updates of nodes so that the global update is heterogeneous, at the same complexity.
Key results
- On real-world graphs from Peptides, small molecules and images, adding a VN typically reduces average commute time (change in commute time negative for most of 100 sampled graphs).
- GatedGCN+PE+VN_G reaches 0.6822 on Peptides-Func and 0.2458 on Peptides-Struct, improving over GatedGCN+PE+VN (0.6712 and 0.2481), and 98.626% on MNIST versus 98.122% for VN.
- On CIFAR10, GatedGCN+PE+VN_G improves from 70.280% to 76.080% over the VN baseline (about 8.25% relative), and it improves over MPNN+VN on all benchmarks reported.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace standard VN with VN_G | GatedGCN+PE · Peptides-Func | score: 0.6712 ± 0.0066 -> 0.6822 ± 0.0052 | Helped |
| Replace standard VN with VN_G | GatedGCN+PE · Peptides-Struct | score: 0.2481 ± 0.0015 -> 0.2458 ± 0.0006 | Helped |
| Replace standard VN with VN_G | GatedGCN+PE · MNIST | accuracy: 98.122 ± 0.102 -> 98.626 ± 0.100 | Helped |
| Replace standard VN with VN_G | GatedGCN+PE · CIFAR10 | accuracy: 70.280 ± 0.380 -> 76.080 ± 0.330 | Helped |
| Replace standard VN with VN_G | GatedGCN+PE · MalNet-Tiny | accuracy: 92.62 ± 0.57 -> 93.67 ± 0.37 | Helped |
| Replace standard VN with VN_G | GatedGCN+PE · ogbg-molhiv | score (%): 76.87 ± 1.36 -> 79.10 ± 0.86 | Helped |
| Replace standard VN with VN_G | GatedGCN+PE · ogbg-molpcba | score (%): 28.48 ± 0.26 -> 29.17 ± 0.27 | Helped |
| Replace standard VN with VN_G | GatedGCN+PE · ogbg-ppa | score (%): 80.27 ± 0.26 -> 81.17 ± 0.30 | Helped |
| Project the non-local attention rows onto their mean (ablation) | GPS · Pept-Func | score: 0.6534 -> 0.6498 | Hurt |
| Project the non-local attention rows onto their mean (ablation) | GPS · Pept-Struct | score: 0.2509 -> 0.2487 | Helped |
| Project the non-local attention rows onto their mean (ablation) | GPS · MNIST | accuracy: 98.051 -> 98.176 | Helped |
| Project the non-local attention rows onto their mean (ablation) | GPS · CIFAR10 | accuracy: 72.298 -> 71.455 | Hurt |
Surprising findings
- Adding a virtual node can increase commute time for some graphs (e.g. complete graphs), so the benefit is spectrum-dependent rather than universal.
- Standard MPNN+VN implementations are provably homogeneous in sensitivity to distant nodes, and MPNN-VN (PairNorm-like) loses expressivity for polynomial filters, contesting the belief that VN helps by emulating PairNorm.
Limitations
- Commute time of graph transformer and rewiring approaches was not empirically measured.
- Message-passing variants inside VN_G were left to future work.
- Theory for the linear setting; activation-free analysis does not fully capture nonlinear networks.
Experimental setup
Datasets: Peptides-Func Peptides-Struct MNIST CIFAR10 MalNet-Tiny ogbg-molhiv ogbg-molpcba ogbg-ppa
Benchmarks: Peptides-Func Peptides-Struct MNIST CIFAR10 MalNet-Tiny ogbg-molhiv ogbg-molpcba ogbg-ppa
Metrics: average precision mean absolute error accuracy average precision (OGB)
Baselines: GCN GINE GatedGCN GatedGCN+PE GatedGCN+PE+VN GPS GRIT Exphormer DRew CRaWl SAN
Builds on: GPS GatedGCN Topping et al. mixing analysis (oversquashing) PairNorm
Closest papers by meaning
- Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Models (NeurIPS 2025 · similarity 0.88)
- Probabilistic Graph Rewiring via Virtual Nodes (NeurIPS 2024 · similarity 0.87)
- Accurate and Scalable Graph Neural Networks via Message Invariance (ICLR 2025 · similarity 0.87)
- On Oversquashing in Graph Neural Networks Through the Lens of Dynamical Systems (AAAI 2025 · similarity 0.87)
- Multi-Track Message Passing: Tackling Oversmoothing and Oversquashing in Graph Learning via Preventing Heterophily Mixing (ICML 2024 · similarity 0.86)
- Deep Graph Neural Networks via Posteriori-Sampling-based Node-Adaptative Residual Module (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.