- This event has passed.
Thesis Defence: Virtual Nodes for Graph Neural Networks: Techniques, Impact, and Theoretical Analysis
October 2 at 9:00 am - 1:00 pm
Ruochen Deng, supervised by Dr. Yong Gao, will defend their thesis titled “Virtual Nodes for Graph Neural Networks: Techniques, Impact, and Theoretical Analysis” in partial fulfillment of the requirements for the degree of Master of Science in Computer Science.
An abstract for Ruochen Deng’s thesis is included below.
Defences are open to all members of the campus community as well as the general public. Please email yong.gao@ubc.ca to receive the Zoom link for this defence.
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 MPNN+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-neighbour 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.
