Back to search

University of British Columbia

Virtual nodes for graph neural networks : techniques, impact, and theoretical analysis

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Deng, Ruochen
Contributors dc:contributor
  • Gao, Yong

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/92716

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Deng, Ruochen. Virtual nodes for graph neural networks : techniques, impact, and theoretical analysis. master's thesis, University of British Columbia, 2025. http://hdl.handle.net/2429/92716