Virtual nodes for graph neural networks : techniques, impact, and theoretical analysis
department or school: Science, Irving K. Barber Faculty of (Okanagan)
department or school: Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)
data provider: DSpace
degree campus: UBCO
creator: Deng, Ruochen
issued: 2025-10-22T23:58:10Z
issued: 2025
related degree: Master of Science - MSc
degree grantor: University of British Columbia
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.
aggregated CHO: https://circle.library.ubc.ca/rest/handle/2429/92716
note: Virtual Nodes for Graph Neural Networks: Techniques,Impact, and Theoretical AnalysisbyRuochen DengB.Eng. in Software Engineering, Jilin University, 2022A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of ScienceinTHE COLLEGE OF GRADUATE STUDIES(Computer Science)The University of British Columbia(Okanagan)October 2025© Ruochen Deng, 2025The following individuals certify that they have read, and recommend to theCollege of Graduate Studies for acceptance, a thesis entitled:Virtual Nodes for Graph Neural Networks: Techniques, Impact, and Theoreti-cal Analysissubmitted by RUOCHEN DENG in partial fulfilment of the requirements of the de-gree of Master of ScienceDr. Yong Gao, Irving K. Barber Faculty of ScienceSupervisorDr. Shan Du, Irving K. Barber Faculty of ScienceSupervisory Committee MemberDr. Ifeoma Adaji, Irving K. Barber Faculty of ScienceSupervisory Committee MemberDr. Ying Zhu, Faculty of ManagementUniversity ExamineriiAbstractThis thesis investigates virtual nodes (VNs), a graph augmentation techniquethat improves the performance of Graph Neural Networks (GNNs). Although VNshave been widely used in practice, their theoretical foundations and systematicevaluation remain limited. To address this gap, we propose the concept of a pro-jection graph, which provides a unified framework for analyzing Message PassingNeural Network+VN, and introduce a taxonomy of virtual nodes along two dimen-sions: 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 levelcomparable with graph transformers. We further analyze how multiple VNs reducecommute times and mitigate over-squashing, thereby lowering the depth requiredfor long-range message passing. Extending these results, we demonstrate that mul-tiple VNs provide stronger improvements against over-squashing.To validate these insights, we conduct experiments on tasks such…
has type: Thesis/Dissertation
date issued: 2026-02
is shown at: 10.14288/1.0450541
language: eng
degree discipline: Computer Science
provider: Vancouver : University of British Columbia Library
publisher: University of British Columbia
rights: Attribution-NonCommercial-NoDerivatives 4.0 International
rights URI: http://creativecommons.org/licenses/by-nc-nd/4.0/
scholar level: Graduate
contributor: Gao, Yong
type: Text
identifier URI: http://hdl.handle.net/2429/92716