Open Collections

Abstract

This thesis investigates virtual nodes (VNs), a graph augmentation technique that improves the performance of Graph Neural Networks (GNNs). Although VNs have been widely used in practice, their theoretical foundations and systematic evaluation remain limited. To address this gap, we propose the concept of a projection graph, which provides a unified framework for analyzing Message Passing Neural Network+VN, and introduce a taxonomy of virtual nodes along two dimensions: effective density and locality. We review theoretical results on message-passing neural networks (MPNNs) with VNs, showing that even a single VN can enhance expressive power to a level comparable with graph transformers. We further analyze how multiple VNs reduce commute times and mitigate over-squashing, thereby lowering the depth required for long-range message passing. Extending these results, we demonstrate that multiple VNs provide stronger improvements against over-squashing. To validate these insights, we conduct experiments on tasks such as tree-neighbor matching and long-range graph benchmarks (Peptides-func and Peptides-struct). Our empirical study shows that (1) VNs consistently help alleviate over-squashing, (2) connecting VNs via the coloring strategy yields the best performance, and (3) the optimal number of VNs varies across tasks. Together, our theoretical and empirical findings establish VNs as both a practical augmentation and a principled mechanism for addressing structural bottlenecks in GNNs.