Science, Irving K. Barber Faculty of (Okanagan)
Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)
DSpace
UBCO
Deng, Ruochen
Master of Science - MSc
University of British Columbia
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.
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 as tree-neighbormatching 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 em-pirical findings establish VNs as both a practical augmentation and a principledmechanism for addressing structural bottlenecks in GNNs.iiiLay SummaryGraphs are widely used to model relationships in domains such as social net-works, recommendation systems, and molecular biology. Graph Neural Networks(GNNs) learn from these structures, but their message-passing mechanism oftenstruggles with long-range dependencies, limiting performance.A promising remedy is to add âvirtual nodesâ that improve information flow bylinking distant parts of a graph. This thesis introduces the concept of a projectiongraph, which provides a unified way to analyze graphs with virtual nodes. Basedon this framework, we propose a taxonomy of virtual node designs along two di-mensions: effective density, reflecting how many new connections are created, andlocality, describing how broadly they link across the graph.We show theoretically that virtual nodes enhance the expressive power of GNNs,reduce over-squashing, and that multiple virtual nodes can be more effective than asingle one. Experiments on benchmark datasets confirm these findings and revealthat different connection strategies and numbers of virtual nodes are optimal fordifferent tasks.ivPrefaceThis thesis was completed independently by myself. All programming im-plementation, experimental design, and data analysis were conducted by me, and Imade the central contributions to the development and refinement of the theoreticalframework.I would like to express my heartfelt gratitude to my supervisor, Dr. Yong Gao,for his patient guidance, continuous encouragement, and insightful discussionsthroughout the research and writing process. His academic attitude and profoundinsights have played a crucial role in shaping and improving this work.All contents of this thesis are original research completed under Dr. Gaoâssupervision and have not been published or submitted to any journal or conference.During the writing process, I used the generative artificial intelligence toolChatGPT for language polishing and spell checking. Every revision suggested bythe tool was carefully reviewed by me to ensure that the text accurately conveyedmy intended meaning and introduced no ambiguity or misunderstanding.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Preliminary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Spectral Graph Theory . . . . . . . . . . . . . . . . . . . . . . . 62.3 Graph Neural Networks . . . . . . . . . . . . . . . . . . . . . . . 82.3.1 Message Passing Neural Networks . . . . . . . . . . . . . 92.3.2 Graph Convolutional Network . . . . . . . . . . . . . . . 102.3.3 From Transformer to Graph Transformer . . . . . . . . . 112.4 Graph Data Augmentation . . . . . . . . . . . . . . . . . . . . . 143 Graph Neural Networks: Challenges and Issues . . . . . . . . . . . 17vi3.1 Over-Squashing . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.2 Over-Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.3 Under-Reaching . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 MPNN + Virtual Nodes: An Overview of Key Techniques . . . . . . 224.1 Virtual Nodes and VN-Augmented Graph . . . . . . . . . . . . . 224.1.1 VN-Augmented Graph and VN-Augmented MPNN . . . . 234.2 Projection Graph: A Message Passing View of Virtual Nodes . . . 244.2.1 Effective Density of Virtual Nodes . . . . . . . . . . . . . 274.2.2 Locality of Virtual Nodes . . . . . . . . . . . . . . . . . . 284.3 Projection Graph-Based Taxonomy . . . . . . . . . . . . . . . . . 294.3.1 Dense Virtual Nodes . . . . . . . . . . . . . . . . . . . . 304.3.2 Sparse Virtual Nodes . . . . . . . . . . . . . . . . . . . . 324.3.3 Local Virtual Nodes . . . . . . . . . . . . . . . . . . . . 334.3.4 Non-local Virtual Nodes . . . . . . . . . . . . . . . . . . 344.4 Betweenness Centrality of Virtual Nodes . . . . . . . . . . . . . . 355 MPNN + Virtual Nodes: An Overview of Theoretical Result andGeneralization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.1 Expressive Power MPNN+VN . . . . . . . . . . . . . . . . . . . 405.2 Over-Squashing and MPNN+VN . . . . . . . . . . . . . . . . . . 456 MPNN + Virtual Nodes: Experiments . . . . . . . . . . . . . . . . . 536.1 Experiment Design and Methodology . . . . . . . . . . . . . . . 536.2 Experiment Setup . . . . . . . . . . . . . . . . . . . . . . . . . . 566.3 Models and Training Setting . . . . . . . . . . . . . . . . . . . . 566.4 Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 566.5 Alleviate Over-Squashing . . . . . . . . . . . . . . . . . . . . . . 596.6 Improve Performance of GNNs . . . . . . . . . . . . . . . . . . . 606.7 Optimal Number of Virtual Nodes . . . . . . . . . . . . . . . . . 627 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67viiList of TablesTable 6.1 Common hyperparameters for all GNN models. . . . . . . . . 57Table 6.2 Model-specific settings and total parameter count. . . . . . . . 57Table 6.3 Performance on Peptides-func with different v-r connectionmethods. Each model has 4 layers, 4 virtual nodes, and fullyconnected v-v connections. . . . . . . . . . . . . . . . . . . . 61Table 6.4 Performance on Peptides-struct with different v-r connectionmethods. Each model has 4 layers, 4 virtual nodes, and fullyconnected v-v connections. . . . . . . . . . . . . . . . . . . . 61viiiList of FiguresFigure 2.1 Graph Spectral Theory Example: the 2nd eigen value and as-sociated eigen vector. The height of the bars corresponds tothe magnitude of the nodeâs contribution to the graphâs spec-tral properties. . . . . . . . . . . . . . . . . . . . . . . . . . 6Figure 2.2 Graph Representation with Degree, Adjacency, and LaplacianMatrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8Figure 2.3 Design Process of Graph Neural Networks . . . . . . . . . . 9Figure 2.4 Comparison of CNN and GCN . . . . . . . . . . . . . . . . . 12Figure 2.5 The Architecture of Graph Transformer . . . . . . . . . . . . 13Figure 2.6 Graph topology comparison (a) before and (b) after rewiring. . 14Figure 4.1 Insert two virtual nodes into the graph, and each virtual nodeis connected to a distinct subgraph. . . . . . . . . . . . . . . 23Figure 6.1 The Framework of Experiments . . . . . . . . . . . . . . . . 54Figure 6.2 An Example of Tree Neighbor Matching . . . . . . . . . . . . 58Figure 6.3 Comparative Performance Before and After Adding VNs . . . 59Figure 6.4 Eigenvalue distributions of real-world graphs . . . . . . . . . 63Figure 6.5 Impact of the number of virtual nodes on average commute time 64ixAcknowledgmentsI want to thank my parents first. They encouraged me to study abroad and gaveme the chance to explore the world. Their love and support have always been withme, and I would not have reached this point without them.I am grateful to my supervisor, Dr. Yong Gao. It is with his guidance and helpthat this thesis could have such rich content. Under his mentorship, I grew froma student who could only write very simple ideas into someone with the ability tocarry out more serious research.I want to thank my girlfriend, Han Jingjing, for always being with me. Eventhough we are far apart, she has supported me through difficult times and given methe strength to continue.Finally, I thank all my friends who have encouraged me and shared this journeywith me. Their company and kindness made this time more meaningful.xChapter 1IntroductionGraphs are a powerful mathematical modeling for complex relationships andinteractions between entities. By capturing the intricate dependencies and interac-tions within data, graphs provide a flexible and expressive framework for represent-ing real-world problems. They have been widely used across various fields, suchas social networks, biological systems, and recommendation engines[9, 30, 35].Graph Neural Networks (GNNs) have emerged as a dominant framework forlearning meaningful representations from graph data, demonstrating versatility acrossapplications such as social networks, molecular biology, and recommendation systems[30,46]. Despite their remarkable success, there are several fundamental challengesthat limit their performance in certain scenarios. These challenges arise from theinherent complexity of graph data and the limitations of existing GNN architectures[31,42, 46, 55].Graph Neural Networks (GNNs) use a message passing mechanism, whereeach node updates its representation by gathering information from its neighborsstep by step. However, this process faces serious challenges when the graph islarge or when important information is spread far apart.One such challenge is under-reaching [31], which means a node can onlyaccess nearby information and fails to receive relevant signals from distant parts ofthe graph. This limits the modelâs ability to understand long-range dependencies.Another major issue is over-squashing [42], which arises when a large amountof information from distant nodes is aggregated into a fixed-size node representa-1tion. This bottleneck can lead to significant loss of important details.Among the solutions proposed to tackle these problems, one direction focuseson reducing the number of steps needed for information to travel between distantnodes. This can be achieved using models like Graph Transformers [27, 50] orattention-based networks [44], which allow nodes to directly exchange informationeven if they are far apart.Another approach involves changing the graph structure itself to make it easierfor information to flow. For example, some methods add new edges based oncertain geometric properties [42], helping the network better capture relationshipsbetween distant parts of the graph.A third strategy is to allow each node to gather information from neighborsthat are more than one step away [10]. This multi-hop aggregation helps the modelaccess broader context and improves its performance on tasks where long-rangeinformation is important.Together, these methods offer promising ways to overcome the limitations ofstandard GNNs in handling complex and large-scale graphs.In addition to these strategies, introducing virtual nodes has emerged as a par-ticularly effective method. Virtual nodes are abstract nodes that act as central-ized aggregators to facilitate information flow across distant parts of the graph,thereby reducing the effective communication path length between non-adjacentnodes [22]. These nodes help mitigate the limitations of traditional GNNs by glob-ally aggregating information from all other nodes [20, 34, 49], offering a flexiblemechanism to address both under-reaching and over-squashing in a unified frame-work. Extensive research has been conducted to explore the use of virtual nodesin GNNs from both practical and theoretical perspectives. From a modeling per-spective, the intuitive approach of adding virtual nodes has been widely adoptedto enhance GNN performance[23, 26, 34, 48, 52]. From a theoretical perspective,their impact has been analyzed to better understand their role in addressing keychallenges [6, 38], although some aspects remain underexplored.While these studies provide a comprehensive overview of the role of virtualnodes and related techniques, there remains a lack of a unified analytical frame-work that systematically connects their structural designs, theoretical foundations,and empirical performance. In this thesis, we aim to fill this gap by conducting2a comprehensive review of existing works and state-of-the-art techniques in thisarea:â¢ Taxonomy of Virtual Node Techniques: We propose a unified frameworkbased on the notion of projection graphs, which allows different virtual nodedesigns to be interpreted under a common lens. Within this framework, weintroduce a taxonomy of virtual nodes along two key dimensions: (i) effec-tive density, describing how intensively VNs connect to real nodes, and (ii)locality, describing whether the influence of VNs is global or confined topartition-based regions of the graph, such as communities or color classes.â¢ Theoretical Analysis: We revisit the expressive power and structural ef-fects of VNs in message-passing neural networks (MPNNs). Our analysisshows that VNs reduce commute times and mitigate over-squashing, effec-tively lowering the depth required for long-range information propagation.Extending prior work on single VNs [15], we further demonstrate that mul-tiple VNs provide stronger improvements in alleviating over-squashing.â¢ Empirical Evaluation: We conduct extensive experiments on both syn-thetic and real-world benchmarks. In particular, tree-neighbor matchingtasks and long-range graph benchmarks (Peptides-func and Peptides-struct)reveal that: (i) VNs consistently help alleviate over-squashing, (ii) coloring-based VN connections yield the best performance, and (iii) the optimal num-ber of VNs varies across tasks.The remainder of this thesis is organized as follows.Chapter 2 introduces the necessary background, including graph representa-tions, spectral graph theory, and various types of Graph Neural Networks (GNNs),with a particular focus on message passing mechanisms and data augmentationtechniques.Chapter 3 outlines key challenges faced by GNNs, such as over-squashing andunder-reaching, which motivate the introduction of virtual nodes.Chapter 4 provides a detailed analysis of virtual node techniques. We proposea unified framework to interpret them from the perspective of projection graphs,3and analyze their structural and functional properties across two dimensions, theeffective density and locality of virtual nodes.Chapter 5 presents the theoretical analysis of MPNNs with virtual nodes (VN).We show that the expressive power of MPNN+VN approaches that of Graph Trans-formers, and that adding virtual nodes helps alleviate the over-squashing problem.Furthermore, we prove that in the case of multiple virtual nodes, the mitigation ofover-squashing becomes even more effective.Chapter 6 presents comprehensive experiments on multiple benchmarks, eval-uating the empirical effectiveness of virtual nodes in mitigating over-squashing andimproving model performance.Finally, Chapter 7 summarizes the main findings and outlines potential direc-tions for future research.4Chapter 2Preliminary2.1 GraphsA graph is a collection of entities and relationships. The entities, referred tonodes or vertices, are connected by relationships, known as edges or links. Forexample, in a social network[32], users can be regarded as nodes, while interactionsbetween them are represented by edges. Formally, the graph is denoted by G(V,E),where V is the set of nodes and E is the set of edges. The number of nodes andedges are represented by n and m, respectively. An undirected edge between nodesu and v is denoted as {u,v}, where the order of the nodes does not matter. Adirected edge from node u to node v is denoted as (u,v), where the order indicatesthe direction from the source u to the target v.The relationships encoded in a graph G can be represented by its adjacencymatrix and degree matrix. The adjacency matrix A = [Ai j] â {0,1}nÃn is a squarematrix of size nà n, where each entry Ai j indicates whether there is an edge be-tween nodes ui and u j:Ai j =ï£±ï£²ï£³1, if there is an edge from vertex ui to vertex u j,0, otherwise.The degree matrix D = [Di j] â RnÃn is a diagonal matrix where each diagonalentry Dii represents the degree of node ui, i.e., the number of edges connected to5ui:Di j =ï£±ï£²ï£³ânk=1 Aik, if i = j,0, otherwise.2.2 Spectral Graph TheorySpectral graph theory studies the fundamental properties of graphs through thealgebraic properties of the graph Laplacian matrix and Adjacency matrix. Thismathematical framework provides powerful tools for understanding graph struc-ture, connectivity, and dynamics. The Laplacian matrix provides a mathematicalfoundation for many algorithms in graph analysis and machine learning.Figure 2.1: Graph Spectral Theory Example: the 2nd eigen value and associ-ated eigen vector. The height of the bars corresponds to the magnitudeof the nodeâs contribution to the graphâs spectral properties.6There are several commonly used forms of the graph Laplacian matrix:Combinatorial Laplacian: L = DâA (2.1)Normalized Laplacian: L = InâDâ 12 ADâ 12 (2.2)Random Walk Laplacian: Lrw = InâDâ1A (2.3)Studies on the Laplacian matrix primarily focus on its spectrum, namely the set ofeigenvalues and eigenvectors. The eigendecomposition of the Laplacian matrix isdefined as follows:L = UÎUâ¤ (2.4)Here, U= [u1, . . . ,un] is the matrix of orthonormal eigenvectors, andÎ= diag(λ1, . . . ,λn)is the diagonal matrix of the corresponding eigenvalues, ordered as 0 = λ1 â¤ λ2 â¤Â·Â· · â¤ λn. Since the Laplacian matrix L is symmetric and positive semidefinite, allits eigenvalues are guaranteed to be real and non-negative.The spectrum of the Laplacian matrix refers to the set of its eigenvalues andeigenvectors. The eigenvalues and eigenvectors of the Laplacian matrix reveal im-portant properties such as connectivity, clustering tendency, and diffusion char-acteristics. For example, the multiplicity of the zero eigenvalue of the Laplacianequals the number of connected components in the graph. In a connected graph, thesecond smallest eigenvalue λ2 measures how well the graph is connected. A largerλ2 indicates stronger connectivity, while a smaller value suggests the presence ofbottlenecks or weak links in the graph.Moreover, λ2 provides bounds on various graph parameters. For instance, wehaveλ2 â¤ nnâ1Îº(G) (2.5)where κ(G) is the vertex connectivity of the graph, defined as the minimum numberof vertices that must be removed to disconnect the graph [12, 17]. This inequal-ity shows only a boundary relation: algebraic connectivity is spectral in nature,whereas vertex connectivity is a structural notion. In particular, if a graph can bedisconnected by removing only a few nodes (i.e., it has low vertex connectivity),7Figure 2.2: Graph Representation with Degree, Adjacency, and LaplacianMatricesthen λ2 will also be small, indicating weak overall connectivity. However, the twoquantities are not logically equivalentâthey are related only through such bounds.2.3 Graph Neural NetworksAs a natural application of neural networks to graph data, Graph Neural Net-works (GNNs) demonstrate powerful learning abilities in extracting structural fea-tures and other graph learning tasks. Traditional deep neural network (DNN) mod-els struggle to effectively handle the complex topological structure of graphs andthe diverse relationships between nodes from different domains. In contrast, GNNsexcel at modeling both the structural information of the graph and the attributes ofthe nodes [36]. As a result, GNNs achieve superior performance on downstreamtasks such as node classification, link prediction, and graph classification.In most graph-based learning scenarios, each node in the graph is associatedwith a feature vector, and the entire graph can be represented by its adjacency ma-trix A and node feature matrix XâRnÃd , which contains the d-dimensional featurevectors for each node. This dual representation enables models to capture both thestructural relationships (via A) and the attribute information (via X) inherent ingraph data.For node-level downstream tasks, the node feature matrix X is often sufficient,as predictions are made individually for each node based on its attributes and neigh-borhood structure. But for edge-level or graph-level tasks, additional informationmay be required. Specifically, an edge feature matrix E â Rmà f can be introducedto encode f -dimensional feature vectors for each edge, capturing relationships be-8yond simple connectivity, such as weights, types, or temporal properties. Similarly,a graph feature vector g â Rh is often used to represent holistic properties of theentire graph, enabling models to make predictions at the graph level. Together,these representations allow graph-based models to flexibly address a wide range oftasks across different granularities.Figure 2.3: Design Process of Graph Neural Networks2.3.1 Message Passing Neural NetworksA widely adopted and general framework for GNNs is the Message PassingNeural Network (MPNN), introduced by Gilmer et al. [20]. The MPNN frame-work provides a unified perspective for understanding and designing various GNNarchitectures. In this framework, nodes in a graph communicate with their neigh-bors by exchanging and aggregating information, a process known as messagepassing. This allows the model to iteratively update node representations basedon both their own features and the features of their local neighborhood. The k-thmessage passing layer can be mathematically formulated as follows:x(k)i = Î³(k)(x(kâ1)i ,Ï jâN(i)Ï(k)(x(kâ1)i ,x(kâ1)j ,e j,i))(2.6)where x(k) and e represent node features and edge features, respectively, and γ ,Ï and Ï correspond to update, message and aggregation function. As (2.6) shows,the process of message passing could be divided into three steps: message, aggre-gate, and update. Message step Ï is to process nodesâ features into a state ready formessage passing. Aggregate step Ï aggregates the features of neighboring nodes toform a new feature set. Update step γ is to update the target nodeâs feature vector9based on the nodeâs original feature and the new feature set.Studies on GNNs primarily focus on designing functions for the three stagesof message passing [21, 25, 27, 44, 46]. Graph Convolutional Networks (GCNs)are one of the foundational models in this area, extending the concept of con-volution to graphs by aggregating information from local neighborhoods. Thisapproach has been proved to be effective in semi-supervised learning tasks [25].GraphSAGE introduces an inductive framework through neighborhood samplingand aggregation, enabling efficient handling of large-scale, dynamic graphs [21].Graph Attention Networks (GATs) leverage an attention mechanism that weightsneighbors based on their potential connection with the target node, enhancing thenetworkâs adaptability to heterogeneous graph structures [44]. Graph IsomorphismNetwork (GIN) adopts a design aligned with the Weisfeiler-Lehman test for graphisomorphism, ensuring the modelâs ability to distinguish subtle structural varia-tions, which is crucial for applications requiring precise structural understanding[47]. Graph Transformer Networks (GTNs) draw from the success of Transformerarchitectures, using self-attention mechanisms to capture long-range dependencies,and expand the modelâs capacity for global context awareness [18].2.3.2 Graph Convolutional NetworkGCN extends the principles of traditional convolutional neural networks onEuclidean data to non-Euclidean graphs. Each layer of the GCN model aggregatesinformation from neighboring nodes to learn the features of the target node. Ac-cording to the MPNN formula 2.6 , the three functions in GCN are the messagefunction Ï , the aggregation function Ï , and the update function γ in the MPNNframework for GCN are as follows:Message Function Ï : In GCN, the message function Ï (k) primarily gathersinformation from each nodeâs neighboring nodes. Since GCN typically does notuse edge features, the message function is simplified to pass the feature vector ofthe neighboring node, and thus the message function is defined as:Ï (k)(x(kâ1)i ,x(kâ1)j ,e j,i)= x(kâ1)j (2.7)Here, x(kâ1)j represents the feature representation of neighboring node j at layer10kâ1. GCN does not use edge features e j,i, so the message function simply returnsthe features of neighboring nodes.Aggregation Function Ï: The aggregation function Ï aggregates the informa-tion from the neighbors of the target node i. In GCN, the aggregation function is aweighted sum of the neighboring nodesâ features, typically including a normaliza-tion factor 1did j to balance the influence of nodes, defined as:Agg = Ï jâN(i)âª{i}Ï (k)(x(kâ1)i ,x(kâ1)j ,e j,i)= âjâN(i)âª{i}1âdid jx(kâ1)j (2.8)Here, N(i)âª{i} represents the set of neighboring nodes including the node it-self, and di and d j are the degrees of nodes i and j, respectively, to ensure symmet-ric normalization. This prevents high-degree nodes from overwhelming low-degreenodes during feature aggregation.Update Function γ: The update function γ combines the aggregated messagewith the current feature of the node and updates the nodeâs features through a lineartransformation and nonlinear activation. The update function in GCN is typicallydefined as:Î³(k)(x(kâ1)i ,Agg)= Ï(W (k) Â·Agg)(2.9)where Ï is a nonlinear activation function (such as ReLU), W (k) is the trainableweight matrix at layer k, and Agg is the output of the aggregation function. Thisupdate function uses a linear transformation and an activation function to updatethe node features, capturing more global information at the current layer.In summary, under the MPNN framework, the message function in GCN passesneighboring node features, the aggregation function performs normalized summa-tion of neighboring information, and the update function applies a linear transfor-mation followed by a nonlinear activation to generate new node features.2.3.3 From Transformer to Graph TransformerTransformer [43] was originally proposed for sequence modeling and has be-come a dominant architecture across various domains. Its success stems from the11(a) The Architecture of CNN (b) The Architecture of GCNFigure 2.4: Comparison of CNN and GCNself-attention mechanism, which enables each token to aggregate information fromall other tokens, weighted by learned attention scores. Formally, the attention-based update is defined as:Attention(Q,K,V ) = softmax(QKâ¤âd)V (2.10)where Q,K,V â RnÃd are the query, key, and value matrices obtained by lin-early projecting the input embeddings. Specifically, given input embeddings X =[x1, . . . ,xn]â¤ â RnÃd , we haveQ = XWQ, K = XWK , V = XWVwhere WQ,WK ,WV â RdÃd are learnable projection matrices. This formulationallows unrestricted information flow across all tokens, regardless of their position.However, unlike sequences data, graphs are unordered and irregular. ApplyingTransformer directly to graphs without modifications leads to a loss of structuralinductive bias. This motivates the design of Graph Transformers, which adaptthe attention mechanism to graph-structured data by incorporating graph-awarepositional encodings and masking strategies.12A typical architecture of a Graph Transformer is illustrated in Figure 2.5. Theinput graph is first encoded by a GNN, producing node-level representations. Theseembeddings are then flattened, optionally concatenated with a global token (e.g.,[CLS]), and passed into a Transformer encoder. The output embedding of the[CLS] token is used to represent the entire graph, enriched with global informa-tion aggregated via self-attention.Figure 2.5: The Architecture of Graph TransformerAlthough full attention offers strong modeling capacity, its quadratic complex-ity O(n2) with respect to the number of nodes makes it computationally expensivefor large graphs. Moreover, fully connected attention may ignore the sparse andstructured nature of real-world graphs. To address these issues, several attentionvariants have been introduced in Graph Transformers, falling into the followingcategories:Local Attention Mechanism Local attention restricts message passing to asubset of nodes, often corresponding to the nodeâs original graph neighbors or ak-hop neighborhood. This preserves local structural inductive bias and reducescomputational cost. Formally, for each node i, attention is computed only over asparse set N(i):αi, j = softmax jâN(i)((W Qxi)â¤(W Kx j)âd)(2.11)Global Attention Mechanism To enable long-range communication and im-prove global reasoning, some models introduce global attention tokens or designatecertain nodes as global aggregators. These nodes attend to all others and are alsoattended by all nodes, effectively acting as message hubs or virtual nodes. This13design is prominent in models like Graphormer [49].These architectural innovationsâranging from positional encoding to attentionsparsity and approximationâtogether form the backbone of modern Graph Trans-former designs. By flexibly combining local structure, global context, and scalablecomputation, these models extend the power of Transformers to the graph domainin an effective and principled way.2.4 Graph Data AugmentationGraph Neural Networks typically rely on the assumption that the input graphsare of reasonably high quality, with reliable structural information and informativenode and edge features [53]. However, in many real-world scenarios, graphs maybe noisy, incomplete, or constructed heuristically, which can significantly impactthe performance of GNNs.(a) Red edges indicate information overload within cliques (excessive redundant data).Blue edges show insufficient inter-clique flow with message compression.(b) Graph rewiring reduces clique density (removed some red edges) and adds green bridg-ing edges to optimize flow.Figure 2.6: Graph topology comparison (a) before and (b) after rewiring.From a modeling perspective, this performance decline can be attributed totwo main factors. Firstly, many existing GNN models are based on supervised or14semi-supervised learning methods, which heavily rely on the accuracy of labels.In real-world scenarios, however, data labeling is not only time-consuming andlabor-intensive but also often incomplete [39, 56]. This reliance on precise labelscontributes to the deterioration in GNN performance. Secondly, the graph dataused for GNN training are often extracted from complex real-world systems. Thisextraction process inevitably introduces issues such as missing, redundant, or du-plicated features and connections. As a result, the underlying graph structure maybe imperfect, which would affect the efficacy of GNN models [13, 24].To address these challenges, improving the quality of graphs in the training datais essentialâa process known as graph augmentation. Graph augmentation can bebroadly classified into three categories: structural augmentation, label augmenta-tion, and feature augmentation. Among these, structural augmentation, which isparticularly relevant to our thesis, focuses on modifying the fundamental compo-nents of graphsânamely, edges and nodes. This includes techniques such as edgedeletion and rewiring, as well as node deletion (also known as dropping) and nodeinsertion.The main purpose of node insertion is to increase the structural complexity ofthe graph, helping the model learn richer and more generalizable representations.By simulating potential node connections that may occur in real-world graphs, in-sertion enhances the graphâs expressiveness. Common insertion techniques includerandom node insertion, which places new nodes at arbitrary positions and connectsthem randomly to existing nodes, thereby introducing structural diversity; and tar-geted node insertion, which selects nodes to insert based on similarity metrics orfeature alignment, ensuring that the added nodes are representative of certain sub-groups within the graph.Node deletion (also known as dropping) improves the modelâs robustness tomissing or noisy information by intentionally removing certain nodes during train-ing. This simulates scenarios with incomplete graphs and encourages the model torely on broader structural patterns rather than specific nodes.Both node insertion and deletion are topology-level augmentation techniquesthat introduce structural perturbations to the graph. Although they operate in op-posite directions, they share the common goal of improving the modelâs gener-alization ability under distribution shifts and imperfect graph conditions. These15methods help prevent overfitting to specific structures and promote more robustlearning across varying graph topologies.16Chapter 3Graph Neural Networks:Challenges and IssuesGraph Neural Networks have shown remarkable success across a wide range ofgraph-related tasks. However, their performance is often hindered by several fun-damental limitations that arise from the underlying message passing mechanism.These limitations restrict the ability of GNNs to capture long-range dependencies,maintain expressive representations, and effectively utilize available label informa-tion. Understanding and addressing these issues is crucial for advancing the designand effectiveness of GNN models.In this chapter, we focus on three key challenges that significantly impactthe learning capability of GNNs: over-squashing, over-smoothing, and under-reaching. We begin by exploring the problem of over-squashing, where informa-tion from distant nodes becomes overly compressed during message passing. Wethen examine over-smoothing, which causes node representations to lose discrimi-native power as the number of layers increases.Finally, we analyze under-reaching, a phenomenon where sparse label distri-bution prevents other nodes from receiving useful supervision signals.For each issue, we explain its causes, describe how it affects the GNN perfor-mance, and summarize existing approaches designed to address issue.173.1 Over-SquashingOver-squashing poses a significant challenge to GNNs. It occurs when the fea-ture representation of a node becomes insensitive to information from distant nodesduring message passing. Increasing network depth causes messages from farawaynodes to travel through long and indirect paths, leading to potential over-squashing,while also expanding each nodeâs receptive field. This causes the information to beoverly compressed into fixed-size representations, leading to a significant loss ofrelevant context [1, 14]. While increasing the feature dimension or stacking morelayers are commonly adopted strategies to mitigate this issue, they offer some ben-efits but also introduce some other difficulties.The dimension of node feature vectors plays a complex role in this setting. Onthe one hand, increasing the feature dimension allows each node to encode andtransmit more information, helping to alleviate over-squashing; on the other hand,it increases the model complexity, which may lead to higher sensitivity to noiseand a greater risk of overfitting [14].Similarly, merely increasing the depth of an MPNN does not effectively resolvethe problem. In fact, deeper architectures often suffer from vanishing gradients,where gradients diminish exponentially as number of layers increase, hindering themodelâs ability to learn long-range dependencies [14]. This limitation highlightsthe need for architectural innovations that go beyond simply scaling width or depthto effectively capture long-range interactions.To combat over-squashing, researchers have proposed several types of strate-gies. Graph rewiring methods, such as DiffWire [2], dynamically modify thegraph topology during training by learning to add or remove edges, effectivelyreducing the graph diameter and enhancing message flow between distant nodes.Modified message passing techniques like LSGNN [10] mitigate over-squashingby restricting message passing within carefully selected local subgraphs, which en-larges the receptive field without increasing model depth and reduces informationcompression. Positional encoding approaches, exemplified by Graphormer [49],inject distance-aware structural biasâsuch as shortest-path distances and nodecentralitiesâinto node embeddings, enabling Transformers to capture long-rangedependencies more effectively despite operating with a limited receptive field of18information propagation. These strategies collectively offer promising directionsfor alleviating the limitations imposed by over-squashing in GNNs.In summary, over-squashing presents a substantial barrier to effective learningin MPNNs, significantly influenced by factors such as graph topology, networkwidth, and depth. Continued exploration of novel architectures and graph mod-ifications is essential to address this issue, thereby improving the capabilities ofgraph neural networks and their applications.3.2 Over-SmoothingOver-smoothing refers to the phenomenon where, as the number of layers inthe GNN increases, the representations of nodes in the graph become increasinglysimilar, leading to indistinguishable node embeddings, even across nodes belong-ing to different classes. This can severely degrade the performance of GNNs, es-pecially in tasks such as node classification, where it is critical to maintain distinctrepresentations for nodes of different classes [29].Over-smoothing is a natural consequence of the message-passing frameworkemployed by GNNs, where each node aggregates information from its neighborsin every layer with a shared update function. While this mechanism helps capturethe local structure and relations within the graph, it also causes node embeddingsto converge to similar values as layers increase, particularly in graphs with highconnectivity. Several studies have demonstrated that this convergence results in re-duced performance as deeper GNNs fail to maintain sufficient discriminative poweracross different node classes [8].Over-smoothing happens when the features of different nodes in a graph be-come too similar as more layers are added to a GNN. This is because, in eachlayer, nodes update their features by averaging with their neighbors. As this pro-cess repeats, the features gradually lose their uniqueness. Eventually, even nodesfrom different categories may look almost the same to the model, making it hardto distinguish between them [29]. Experiments have shown that deeper GNNstend to produce more similar node features across the graph, confirming that over-smoothing becomes more severe as GNN gets deeper [8].To reduce over-smoothing, researchers have explored several strategies. One19common method is to add a penalty during training that discourages node featuresfrom becoming too similar. Another approach is to adjust the graph structure, forinstance by modifying edges to reinforce beneficial relations and reduce noisy con-nections. These adjustments make it easier for the model to pass useful informationwhile limiting interference from unrelated parts of the graph [8]. Both techniqueshave been shown to improve the performance of GNNs by keeping node featuresmore distinguishable.3.3 Under-ReachingUnder-reaching refers to the failure of GNNs to propagate supervision signalseffectively to unlabeled nodes, especially when labeled data is sparse. This issuearises when the number of labeled nodes is small and the number of unlabelednodes is large, making it difficult for many unlabeled nodes to receive informativesignals during message passing. As a consequence, GNNs often fail to propagatesupervision signals to unlabeled nodes effectively, leading to suboptimal classifi-cation performance [31].This limitation is especially severe for nodes with few neighbors (i.e., low de-gree), which tend to be structurally distant from labeled nodes. Since GNNs pri-marily rely on local message passing, these nodes may not receive sufficient in-formation from the labeled parts of the graph during training. As a result, theyremain poorly informed, and the model fails to generalize well beyond the imme-diate vicinity of the labeled nodes [40].Research has shown that increasing the number of layers in a GNN could os-tensibly address the under-reaching problem by allowing nodes to gather infor-mation from more distant labeled nodes. However, this approach introduces twoadditional challenges: over-smoothing, which can result in indistinguishable noderepresentations [53], and over-squashing, where the messages exchanged betweendistant nodes become compressed, leading to information loss [1]. Therefore, sim-ply deepening GNN is not a viable solution for tackling under-reaching.To effectively mitigate under-reaching, techniques that strengthen the interac-tion between labeled and unlabeled nodes are essential. A promising solution isNodeMixup [31], which generates synthetic training examples by mixing features20and labels from both sets. This approach improves distribution alignment and fa-cilitates learning from unlabeled data, significantly enhancing node reachabilitywithout requiring architectural changes to the GNN.21Chapter 4MPNN + Virtual Nodes: AnOverview of Key TechniquesMessage passing neural networks face several well-known structural limita-tions, such as over-squashing, under-reaching, and over-smoothing, which funda-mentally constrain their capacity to capture long-range dependencies and preserveexpressive node representations. These issues, introduced in the previous chapter,have motivated a growing body of work that seeks architectural solutions to over-come them. Among these, the addition of virtual nodes (VNs) has emerged as aparticularly versatile and widely adopted technique.This chapter is organized into three main parts. Section 4.1 provides a intro-duction of virtual nodes and virtual nodes-augmented graph. In Section 4.2, weintroduce the concept of the projection graph, providing a unified framework toanalyze MPNN+VN. Finally, based on the projection graph, we present a taxon-omy of virtual node designs on two dimensions, effective density and locality.4.1 Virtual Nodes and VN-Augmented GraphIn the context of graph neural networks, a virtual node (VN) refers to an aux-iliary node that is explicitly added to the graph but does not correspond to anyreal-world entity. Virtual nodes are typically connected to a subset of real nodes,either globally or locally, and are treated in the same way as regular nodes during22message passing.Figure 4.1 shows an example of inserting two virtual nodes into an existinggraph. In the original graph (left), only real nodes and their edges are present.On the right, two virtual nodes (dark blue) are added, each connected to a distinctgroup of real nodes via dashed edges. These connections form two subgraphs, witheach virtual node associated exclusively with one subgraph. This setup reflects acommon design choice in which virtual nodes are used to introduce auxiliary edgeswithin subgraphs, without altering the original graph structure.Figure 4.1: Insert two virtual nodes into the graph, and each virtual node isconnected to a distinct subgraph.4.1.1 VN-Augmented Graph and VN-Augmented MPNNTo formally describe the addition of virtual nodes into a graph, we define theVN-augmented graph.Definition 1 (VN-Augmented Graph). Given an original graph G(V,E) and a setof additional nodes U, the VN-augmented graph by U is defined as the graphG(V âªU,E âª EË) satisfying the following properties:â¢ EË â©E = /0;â¢ each edge in EË involves at least one virtual node from U;â¢ For every v âV , there exists at least one u âU such that {v,u} â EË.In the VN-augmented graph G(V âªU,E âª EË), the set of additional nodes U arecalled the virtual nodes and the set of edges EË are called the virtual edges. When23an MPNN operates over a VN-augmented graph, we refer to it as a VN-augmentedMPNN. In this setting, both real and virtual nodes participate in the message pass-ing. Virtual nodes not only aggregate messages from real nodes but also sendmessages back to them.Definition 2 (VN-Augmented MPNN). A VN-augmented MPNN over a graphG(V,E) and a set of virtual nodes U is a message passing neural network definedon the VN-augmented graph G(V âªU,E âª EË), with the following update equation:x(k)v = Î³(k)(x(kâ1)v , Ï jâN (v)Ï (k)(x(kâ1)v ,x(kâ1)j)ï¸¸ ︷︷ ︸Real neighbor messages+ ÏuâNvn(v)Ï(k)(x(kâ1)v ,x(kâ1)u)ï¸¸ ︷︷ ︸Virtual node messages), âv âV ; (4.1)x(k)u = Î³(k)(x(kâ1)u , ÏvâN (u)Ï (k)(x(kâ1)u ,x(kâ1)v)), âu âU. (4.2)Here, N (v),N (u) â V denotes the set of real neighbors of real node v and vir-tual node u, and Nvn(v) âU denotes the set of virtual neighbors of v in the VN-augmented graph G(V âªU,Eâª EË). The function Ï (k) defines the message functionat layer k, shared across both real and virtual edges. The operator Ï denotes aggre-gation function, and γ(k) is the node update function.4.2 Projection Graph: A Message Passing View ofVirtual NodesTo capture how virtual nodes reshape message passing, we introduce the pro-jection graph, a message-passing view of the VN-augmented graph. It highlightswhich node pairs become newly connected through virtual-node-mediated interac-tions after multiple message-passing layers. It is important to note that the pro-jection graph is introduced solely as an analytical abstraction, rather than a newmodel or graph construction, serving to help understand the functional importanceof virtual nodes in message propagation. This view offers a unified perspective forunderstanding how virtual nodes can shorten propagation paths, serve as regionalcontext aggregators, and enrich the original graph structure with additional com-24munication routes.Definition 3 (Projection Graph). Given a VN-augmented graph G(V âªU,E âª EË),we define the projection graph GVN(V,Eproj) as a graph over the original node setV , with edge setEproj = E âª{(i, j) âV ÃV â£â£Nvn(vi)â©Nvn(v j) Ì¸= /0} ,The projection graph GVN is defined over the original node set V ; virtual nodesserve only as intermediate facilitators and do not appear in the final structure. Thisgraph reflects how messages are actually propagated between nodes during train-ing and thus reveals the effective topology shaped by virtual-node augmentation.The projection graph thus retains all original edges while incorporating new edgesinduced by high-scoring virtual-node-mediated interactions. It typically exhibitsthe following characteristics:â¢ Edge additions: Node pairs that were not directly connected in the inputgraph may become linked if they consistently communicate through virtual-node-mediated paths. These new edges reflect new relationships identifiedduring message passing that are not present in the original topology.â¢ Dense vs. sparse augmentation: Depending on how many VN-mediatededges are introduced, the projection graph can range from sparsely modified(with only a few added edges) to nearly complete (where almost every nodeis connected via VN-mediated path). Dense augmentation can significantlyalter the graphâs structure, while sparse augmentation preserves most of theoriginal topology.â¢ Local vs. non-local connections: Local edges connect nearby nodes andhelp preserve the original subgraph structure. Non-local edges link distantnodes and create shortcuts, which can change how information propagatesin the graph.We can interpret message passing by MPNN on the projection graph, and twolayers of message passing over a VN-augmented graph can be approximately ex-25pressed as one layer of message passing over the projection graph, when only two-hop paths through virtual nodes are considered.After two rounds of propagation, a real node v aggregates messages from allreal nodes that are two-hop reachable via virtual nodes. These nodes correspondto direct neighbors of v in the projection graph GVN. Specifically, if there exists avirtual node u such that i â u â v, then node i becomes a one-hop neighbor of vin the projection graph.Formally, the updates over the VN-augmented graph proceed as follows. Atlayer kâ1, a virtual node u âU aggregates messages from its real neighbors:x(kâ1)u = Î³(kâ1)(x(kâ2)u , ÏpâN (u)Ï (kâ1)(x(kâ2)u ,x(kâ2)p )), (4.3)whereN (u)âV denotes the set of real neighbors of virtual node u.At layer k, a real node v âV updates its feature as:x(k)v = Î³(k)(x(kâ1)v , Ï jâN (v)Ï (k)(x(kâ1)v ,x(kâ1)j )+ ÏuâNvn(v)Ï(k)(x(kâ1)v , x(kâ1)u)),(4.4)whereN (v)âV is the set of real neighbors, andNvn(v)âU is the set of virtualneighbors of v.By substituting x(kâ1)u into the above expression, we obtain:x(k)v = Î³(k)(x(kâ1)v , Ï jâN (v)Ï (k)(x(kâ1)v ,x(kâ1)j )+ ÏuâNvn(v)Ï(k)(x(kâ1)v , Î³(kâ1)(x(kâ2)u , ÏpâN (u)Ï (kâ1)(x(kâ2)u ,x(kâ2)p ))))(4.5)Assuming permutation-invariant aggregation functions, we can rearrange thenested virtual-node-mediated message passing into a direct aggregation over theprojection graph:x(k)v = Î³(k)(x(kâ1)v , Ï jâN (v)Ï (k)(x(kâ1)v ,x(kâ1)j )+ ÏpâNproj(v)N (v)Î¨(x(kâ1)v ,x(kâ2)p )),(4.6)where Ψ denotes a composite function that captures the two-hop information flow26via virtual nodesâfirst from a real node p to a virtual node, and then from thevirtual node to v.Therefore, the two-layer message passing process involving virtual nodes canbe approximated by a single-layer update over the projection graph:x(k)v = Î³Ë(k)(x(kâ2)v , ÏqâNproj(v)ÏË(k)(x(kâ2)v ,x(kâ2)q )), (4.7)where ÏË (k) and Î³Ë(k) are abstracted single-layer message and update functions de-fined over the projection graph, and Nproj(v) denotes the neighbors of v in theprojection graph.In the following two sections, we use several measurements to evaluate theimportance of virtual nodes under the view of projection graph.4.2.1 Effective Density of Virtual NodesDefinition 4 (Effective Density of Virtual Nodes). Given a projection graph GVN(V,Eproj),we define its density asδproj =2 · |Eproj E||V |(|V |â1) ,where |V | is the number of real nodes, and Eproj E denotes the set of newly addededges between real nodes induced by virtual-node-mediated paths.A projection graph with high-density virtual nodes introduces numerous newconnections, often resulting in near-complete graph or cliques, whereas a projec-tion graph with low-density virtual nodes retains most of the original topology, withonly a few added edges. This variation in edge density directly affects how effi-ciently information propagates through the graph and how features are aggregatedacross the graph.We consider two extreme cases to characterize the possible range of effectivedensity of virtual nodes:â¢ Maximum density: When the virtual nodes collectively induce a completegraph over the real nodes, the number of additional edges introduced is27bounded by the number of missing edges in the original graph. That is,δproj =2 Â·((|V |2)â|E|)|V |(|V |â1) = 1â2|E||V |(|V |â1) .â¢ Zero density: When the original graph is already a complete graph and nonew connections are introduced by virtual nodes (i.e., Eproj â E), we have:δproj = 0.These cases demonstrate that the projection graph density lies within the closedinterval:δproj â[0, 1â 2|E||V |(|V |â1)],reflecting the extent to which virtual nodes compensate for missing edges in theoriginal graph.4.2.2 Locality of Virtual NodesDefinition 5 (Locality of Virtual Nodes). Given a virtual-node-augmented graphG(V âªU,E âª EË), the locality of a virtual node u â U is defined as the averageclustering coefficient of the real nodes in Cu:â(u) =1|Cu| âvâCu2 · |{(i, j) â E : i, j âN (v)}||N (v)| · (|N (v)|â1) ,whereN (v) denotes the set of neighbors of node v in the original graph, Cu âV isthe subset of real nodes associated with u, Cuâ©Cuâ² =â âu Ì¸= uâ², and V =âuâU Cu.Based on the locality of virtual nodes, we distinguish the following cases:â¢ Local: if all subsets satisfy â(u)â¥ Ï , where Ï â [0,1] is a predefined localitythreshold. In this case, each Cu exhibits strong internal connectivity, oftencorresponding to a community-like structure.â¢ Non-local: otherwise. Here, Cu contain structurally distant nodes with weakinternal connectivity, resembling a coloring-based subgraph where nodes are28chosen to be far apart.In a local projection graph, projection edges are concentrated within denselyconnected subsets of nodes. These edges often reinforce existing structures suchas communities, preserving the original graph structure.In contrast, a non-local projection graph introduces edges that span distant partsof the graph. These connections typically link nodes that are structurally unrelatedin the original graph, resulting in a more dispersed pattern of connectivity. Ratherthan strengthening local substructures, they reshape the message propagation ofthe whole graph.We consider two extreme cases of the locality of virtual nodes:â¢ Local structure (clique): If each virtual node connects to a set of nodes thatforms a clique in the original graph, then â(Cu) = 1, achieving maximal lo-cality.â¢ Non-local structure (coloring): If Cu contains structurally distant nodesâsuchas those selected using a graph coloring strategy where nodes are chosen tobe far apartâthen typically â(Cu) â 0, representing a non-local projectionpattern.These cases demonstrate that the locality score satisfiesâ(Cu) â [0, 1],reflecting the extent to which virtual nodes preserve local structural connectivity orintroduce non-local shortcut connections in the original graph.4.3 Projection Graph-Based TaxonomyIn this section, we propose a taxonomy of virtual nodes based on two keydimensions of the projection graph: density and locality.â¢ Dense virtual nodes contain a large number of added edges, often formingnear-complete graphs or cliques. For example:29â A single virtual node connected to all real nodes yields a fully con-nected projection graph.â Multiple virtual nodes connected to disjoint or overlapping subsets ofreal nodes form multiple cliques.â¢ Sparse virtual nodes introduce only a small number of additional edges,preserving the original graphâs sparse structure and avoiding significant struc-tural change.â¢ Local virtual nodes add edges within highly clustered subsets of nodes inthe graph, forming cliques while maintaining the original graph structure.â¢ Non-local virtual nodes connect structurally non-adjacent nodes in the orig-inal graph and enhance original message passing.4.3.1 Dense Virtual NodesIn dense structures, the projection graph contains a large number of addededges, with original nodes forming a near-complete graph or multiple cliques. Theaverage node degree increases significantly, the graph diameter approaches 1, anddensely connected subgraphs frequently appear.Typically, multiple virtual nodes each connect to a different subregion of thegraph: every virtual node is linked to a set of real nodes. In the projection graph,this set forms a clique due to the presence of VN-mediated paths through the samevirtual node.In the extreme case where only a single virtual node is introduced and it is con-nected to all real nodes, the projection graph becomes a complete graph. Any tworeal nodes have a path of length 1, and the virtual node acts as a global broadcastand aggregation hub. This âsingle virtual node + full connectionâ design appearsin models such as the dummy super node in Neural Message Passing[20] and thespecial token node in Graphormer[49].If each subset of real nodes is assigned a virtual node, then the real nodes con-nected to the same virtual node will form a clique in the projection graph, becausethey all share the same virtual node. As such, the virtual node effectively com-30presses and connects a dense subgraph, serving as an aggregation center for thatregion.Graph-level Representation as a Pooling AlternativeSome models further exploit this aggregation mechanism by interpreting a sin-gle virtual node as the graph-level representation, which offers:1. A simpler architecture without the need for extra pooling modules or hyper-parameters;2. Reduced inference cost by eliminating the O(|V |) feature aggregation pass.In graph classification tasks, such designs have been empirically shown toachieve high accuracy with lower parameter and memory costs[23, 34].Shorten Propagation PathAlthough dense structures naturally facilitate feature aggregation, their abun-dance of connections allows almost any node pair to communicate indirectly viaa virtual node, reducing the average shortest path toward 1. This effectively al-leviates the under-reaching problem and improves information propagation. Bycollapsing multi-hop paths into a single VN-mediated step, dense projections candramatically expand the receptive field of each node without increasing the modeldepth.Virtual Node TuningBeyond structural augmentation, recent methods leverage dense virtual-nodeconnectivity in tuning GNN models. Virtual Node Tuning (VNT)[41] introduces asingle learnable virtual node embedding that functions as a task-adaptive prompt,inspired by prompt-tuning techniques in NLP[28, 54]. Instead of relying on mes-sage passing, the virtual node is concatenated to the input feature vector of everyreal node at the first layer. This forms a dense, implicit connection between thevirtual node and all real nodes without modifying the graph structure itself. In thecorresponding projection graph, this operation is equivalent to introducing a singlevirtual node connected to all real nodes, resulting in a complete projection graph.During fine-tuning, only the virtual node embedding and the final classificationhead are updated, while the parameters of the pretrained Graph Transformer remainfrozen. This design effectively turns the virtual node into a lightweight adaptationlayer.31The approach offers several benefits:1. Parameter efficiency: A single virtual node embedding replaces full-modelfine-tuning, drastically reducing the number of trainable parameters.2. Optimization stability: Keeping the backbone model fixed helps stabilizetraining and reduces the risk of overfitting, especially when only limitedtraining data is available.3. Inference simplicity: The final virtual node state serves directly as thegraph-level representation, eliminating the need for explicit pooling oper-ations.4.3.2 Sparse Virtual NodesSparse projection graph contains a relatively small number of added edges,typically connecting only select pairs of real nodes. The overall structure remainsclose to that of the original graph. The average node degree increases only slightly,as projection edges are selectively added between distant or weakly connected sub-graph of the graph.These sparse modifications are designed not to aggregate information broadly,but to enhance the graphâs long-range communication ability. Specifically, theyaim to address the under-reaching problem in standard message passing GNNs,where information from distant nodes cannot be effectively captured within a lim-ited number of layers [3].Shortening Propagation PathsSparse projection graphs are highly effective at compressing long-range prop-agation paths. When a virtual node u connects two distant nodes i and j, a shortcutedge (i, j) is added in the projection graph. These new edges do not aim for con-structing a clique, but rather for selective structural shortcuts that bridge otherwiseremote parts of the graph.This design significantly expands each nodeâs receptive field without increas-ing the depth of the GNN. Standard MPNNs aggregate information from a fixed-hop neighborhood, but sparse VN-mediated projection edges allow nodes to access32signals from distant regions via a single step. As a result, sparse projection graphsreduce the graphâs effective diameter while keeping GNN model unchanged.Such structures have been adopted in models like GNN-RM [14] and NodeAug-I/N/S [48], where virtual nodes are connected to only a subset of real nodes. Thesepartial connections avoid full connectivity but still introduce effective shortcuts be-tween distant regions, enhancing long-range communication while preserving theoriginal graph topology.Structural and Computational EfficiencyCompared to dense projection graphs, sparse ones introduce far fewer edgesand preserve the original graph structure. This makes them well-suited for large-scale scenarios, where memory and computational efficiency are crucial. The abil-ity to enhance connectivity with minimal structural changes offers a practical solu-tion.4.3.3 Local Virtual NodesLocal projection graphs are characterized by the fact that most of the newlyadded edges connect node pairs that originally belong to the same community butwere not directly linked in the original graph. These nodes often share strongsimilarity and are located within the same community. The virtual node bridgesthese nodes through two-hop paths, and these connections are made explicit inthe projection graph, forming cliques within each community. As a result, theprojection graph exhibits a structure composed of multiple cliques.Importantly, no new edges are introduced between communities; only edgesbetween communities from the original graph are preserved. This means that allstructural augmentation remains strictly in the community, avoiding the creation ofcross-community shortcuts and preserving the original graph structure.Functionally, this type of projection graph can be seen as a natural extensionand enhancement of the neighborhood aggregation in MPNNs. While MPNNs ag-gregate information from direct neighbors, local projection graphs effectively ex-pand the neighborhood definition by shortening the information propagation pathsin each community. Node pairs that previously required multiple hops to inter-act, even though they are in the same community, can now exchange information33through compressed paths enabled by virtual nodes. This facilitates faster featurepropagation and aggregation.The local projection graph is reflected in several recent models. NodeAug-C [48] leverages graph clustering to assign real nodes into real node subgraph, eachconnected by a virtual node. GNN-CM [22] similarly applies community detectionto construct virtual node connections. Although these models do not explicitlyconstruct a projection graph, their connection patterns implicitly form local cliquesin the projection graph, where added edges are confined within communities andno cross-community links are introduced.4.3.4 Non-local Virtual NodesIn contrast to local projection graphs, non-local projection graphs primarily in-troduce new edges between node pairs that are structurally distant in the originalgraph, such as those located in different community. These connections are in-duced by virtual-node-mediated two-hop paths and become explicit shortcut edgesin the projection graph. A key characteristic is that no additional edges are addedwithin communities; instead, new edges mostly link nodes across communities,resulting in a projection graph with widely distributed new edges.Rather than reinforcing existing local neighborhoods, this structure compresseslong paths by connecting distant nodes, thereby improving long-range informationpropagation. In shallow GNNs, this alleviates the problem of under-reaching.From the perspective of heterophilic graph learning, traditional MPNNs tendto aggregate information from neighbors with similar features, which works wellin homophilic graphs. However, in low-homophily settings, where neighboringnodes also have dissimilar features, this can lead to ineffective or misleading aggre-gation. Non-local projection graphs preserve local aggregation mechanisms whileintroducing remote nodes with dissimilar features as additional sources of infor-mation. This enables the model to incorporate heterogeneous signals and mitigatesthe reliance on homophily.To the best of our knowledge, no prior work has explicitly constructed suchnon-local projection graphs. We propose to use graph coloringâbased node parti-tioning to assign virtual-real connections that add long-range, cross-region projec-34tion edges. Experimental results demonstrate that this strategy effectively improvesthe modelâs ability to capture long-range dependencies.4.4 Betweenness Centrality of Virtual NodesWe consider a VN-augmented graph with multiple virtual nodes {u1,u2, . . . ,uk},where each virtual node u connects to a subset of real nodes Cu â V . We assumethere are no connections between virtual nodes. Each real node connects to exactlyone virtual node, forming a disjoint partition {Cu1 ,Cu2 , . . . ,Cuk} of the real node setV .Theorem 6 (Betweenness Centrality of a Virtual Node). Given a virtual-node-augmented graph GË(V âªU,E âª EË), the betweenness centrality of a virtual node uisg(u)=(âs,tâCusÌ¸=t,dG(s,t)=211+ |NG(s)â©NG(t)| + âs,tâCusÌ¸=t,dG(s,t)â¥31)ï¸¸ ︷︷ ︸intra-cluster pairs+ âsâCutâVCu,dG(s,t)â¥3I(u â SPst(GË))|SPst(GË)|ï¸¸ ︷︷ ︸cross-cluster pairs.â¢ NG(Â·): the neighbor set of a node in the original graph G.â¢ SPst: the set of all shortest paths between s and t in GË.â¢ I(u â SPst): equals 1 if u lies on at least one shortest path from s to t in GË,and 0 otherwise.â¢ dG(s, t): the shortest-path distance between s and t in the original graph G.Proof. By definition, the betweenness centrality of u in the augmented graph GË isg(u) = âs,tâVsÌ¸=tÏst(u)Ïst,where Ïst denotes the total number of shortest paths between s and t in GË, andÏst(u) is the number of those passing through u. We analyze this ratio dependingon whether s, t lie in the same cluster Cu or not.35(1) Intra-cluster case: let s, t âCu.- If dG(s, t) = 1, then (s, t) â E(G), so the shortest path has length 1, while anypath through u has length 2. Hence Ïst(u) = 0.- If dG(s, t) = 2, then every two-hop path from s to t in G corresponds exactlyto a common neighbor in NG(s)â©NG(t). In GË, the virtual node u provides oneadditional two-hop path sâ uâ t. Thus,Ïst = |NG(s)â©NG(t)|+1, Ïst(u) = 1,and consequentlyÏst(u)Ïst=11+ |NG(s)â©NG(t)| .- If dG(s, t) â¥ 3, then all shortest paths in G have length at least 3, while in GËthere is a path s â u â t of length 2, which is strictly shorter. Hence this is theunique shortest path, so Ïst = 1 and Ïst(u) = 1, givingÏst(u)Ïst= 1.Therefore, the total contribution of intra-cluster pairs can be written asâs,tâCusÌ¸=t,dG(s,t)â¥211+ |NG(s)â©NG(t)| .(2) Cross-cluster case: let s âCu and t âV Cu.- If dG(s, t)â¤ 2, then any path via u has length at least 3, which is strictly longerthan the shortest distance in G. Thus Ïst(u) = 0.- If dG(s, t)â¥ 3, then the shortest distance in G is at least 3. If there exists somer âCu with (r, t) â E(G), then the pathsâ uâ r â thas length 3, which may equal the shortest distance. In this case, u appears in some36but not all shortest paths, and its contribution isÏst(u)Ïst=I(u â SPst(GË))|SPst(GË)|.Combining the intra-cluster and cross-cluster contributions, we recover exactlythe expression for g(u) stated in Theorem 6.Using Theorem 6, we can study how different partition strategies lead to higheror lower betweenness centrality of virtual nodes.Corollary 7 (Betweenness Centrality under Clique Partition). In the virtual-node-augmented graph GË, if the cluster Cu forms a clique in the original graph G, thenthe betweenness centrality of the virtual node u isg(u) = âsâCutâVCu,dG(s,t)â¥3I(u â SPst(GË))|SPst(GË)|.Proof.â¢ Intra-cluster contribution: Since Cu is a clique, any two nodes s, t â Cuhave distance dG(s, t) = 1. Hence no intra-cluster pair satisfies dG(s, t)â¥ 2,and this part contributes nothing.â¢ Cross-cluster contribution: For pairs (s âCu, t â V Cu), the analysis fol-lows Theorem 6. If the virtual node u lies on at least one shortest path be-tween s and t with dG(s, t)â¥ 3, it contributes proportionally asI(u â SPst(GË))|SPst(GË)|.Combining the two parts gives the stated formula.Corollary 8 (Betweenness Centrality under Extreme Coloring Partition). In thevirtual-node-augmented graph GË, suppose the partition comes from an extreme37coloring: the cluster Cu is an independent set in the original graph G, and everynode in Cu is connected to all nodes in V Cu. Then the betweenness centrality ofthe virtual node u isg(u) = âs,tâCusÌ¸=t11+(nâ|Cu|) .Proof.â¢ Intra-cluster contribution: For any two nodes s, t âCu, since Cu is an in-dependent set, there is no edge between them. Both s and t are adjacentto every node in V Cu, hence dG(s, t) = 2. Their common neighbor set isV Cu, with size nâ|Cu|. Thus, by Theorem 6, the contribution of u to eachsuch pair is11+ |NG(s)â©NG(t)| =11+(nâ|Cu|) .Summing over all unordered pairs in Cu gives the total intra-cluster contri-bution.â¢ Cross-cluster contribution: For pairs (s â Cu, t â V Cu), there is alwaysa direct edge, i.e., dG(s, t) = 1. Since the formula in Theorem 6 requiresdG(s, t)â¥ 3, these pairs contribute nothing.In the above two extreme cases (clique partition and extreme coloring parti-tion), we obtained exact form expressions of the virtual-node betweenness central-ity. However, for general partition strategies, no such exact forms are available,and the analysis must rely on Theorem 6.Community-based Partition. When Cu is induced by community detection,clusters are dense inside and sparse across. The virtual node u contributes mainlythrough:â¢ Intra-cluster pairs with dG(s, t) = 2: u provides an additional two-hop path,but its contribution is shared with existing paths in G.â¢ Cross-cluster pairs with dG(s, t) â¥ 3: these are relatively rare, but in suchcases u may lie on shortest paths between clusters.38Coloring-based Partition. When Cu is induced by a coloring scheme, eachcluster forms an independent set and has abundant edges to other clusters. Themain contributions of u come from:â¢ Intra-cluster pairs with dG(s, t) = 2: in this case u often becomes the uniqueshortest-path bridge and receives full credit.â¢ Cross-cluster pairs with dG(s, t) â¥ 3: these are frequent in this setting, so uoften appears on shortest paths across clusters, yielding substantial between-ness centrality.39Chapter 5MPNN + Virtual Nodes: AnOverview of Theoretical Resultand GeneralizationEarly studies on virtual nodes largely regarded them as a practical data-augmentationmethod for improving graph neural network performance. More recently, researchershave begun to examine their theoretical aspects. In this section, we review theoreti-cal results on the expressive power of MPNNs with virtual nodes. We also broadenthe scope from the single-VN setting examined in previous studies to that withmultiple virtual nodes, outlining how existing findings extend to this more generalcase.5.1 Expressive Power MPNN+VNCai et al. [6] demonstrate that augmenting a Message Passing Neural Net-work (MPNN) with a virtual node is sufficient to match the expressive power ofGraph Transformers. This result establishes an expressivity equivalence betweenthe two architectures. Theorem 9 formalizes this finding, and the subsequent sub-sections elaborate on how different augmentation regimes contribute to achievingthis equivalence.Theorem 9 (Expressivity Equivalence of MPNN with Virtual Node). Let fSA :40RnÃd â RnÃdâ² be the self-attention map of a graph transformer with n tokens(nodes). For any compact domain X â RnÃd and any ε > 0, there exists a mes-sage passing neural network with a virtual node (MPNN+VN), denoted as fVN,such thatâ¥ fSA(X)â fVN(X)â¥â < ε.The construction of such an approximating fVN depends on different attentionmechanisms. Following Cai et al. [6], we distinguish two primary attention mech-anisms under which MPNN+VN architectures can approximate the expressivity ofGraph Transformers:â¢ Linear-attention mechanism: An MPNN+VN with constant depth = O(1)and constant width=O(1) is sufficient to approximate linear-attention GraphTransformers.â¢ Full-attention mechanism: More complicated MPNN+VN is required toapproximate full-attention Graph Transformers:â Width-scaling strategy: The MPNN maintains constant depth=O(1),while its width scales polynomially with the graph size, i.e., MPNNwidth = O(nd) for some constant d.â Depth-scaling strategy: The MPNN maintains constant width=O(1),while its depth increases linearly with the graph size, i.e., MPNN depth= O(n).Linear-Attention Mechanism: Constant Depth and WidthStandard self-attention has a computational cost of O(n2), but Performer [11]and Linear Transformer [27] reduce this to O(n). The linear attention update isgiven by:xi =Ï(qi)T ânj=1 Ï(k j)âv jÏ(qi)T ânj=1 Ï(k j), (5.1)where Ï(Â·) is a positive feature map that can be approximated by a shallowMLP.41To approximate such linear-attention-based Graph Transformers, Cai et al. [6]construct a two-layer MPNN with a single virtual node and constant-width hiddenfeatures. The approximation follows a four-step process:1. Encoding. Each real node j computes Ï(k j) and Ï(k j)â v j via a constant-width MLP and sends them to the VN.2. Aggregation at VN. The VN sums incoming messages:Sk =nâj=1Ï(k j), Skv =nâj=1Ï(k j)âv j.3. Broadcast. In the second layer, the VN broadcasts (Sk,Skv) to all nodes.4. Local combination. Each node i computesxËi =Ï(qi)T SkvÏ(qi)T Sk,using simple dot products and scalar division.This construction enables the VN to compute and distribute global summariesof key and value terms, thereby simulating the denominator and numerator of thelinear attention formula. The entire process uses constant depth (two layers) andconstant width (independent of n), achieving the O(n) complexity of linear atten-tion. This demonstrates that a single virtual node can serve as an efficient and ex-pressive aggregator, matching the expressive power of linear-attention-based graphtransformers.Full-Attention Mechanism via Width ScalingThe full-attention mechanism in Graph Transformers treats the input as an un-ordered set and is thus permutation-equivariant.42Definition 10 (Permutation Equivariance). A function f :RnÃd âRnÃdâ² is permutation-equivariant if for any permutation matrix P â RnÃn, we have:f (PX) = P f (X)for all X â RnÃd .DeepSets [51] shows that permutation-equivariant functions admit universalapproximators based on a simple sum-and-broadcast pattern:Definition 11 (Equivariant DeepSets Layer). Given an input matrix X âRnÃd withrows x j, an equivariant DeepSets layer can be instantiated asf (X) = XA + 1n 11â¤XB,where A,B â RdÃdâ² are learnable parameter matrices and 1 â Rn is the all-onesvector. This map is permutation-equivariant because the global term 1n 11â¤XB isconstant across rows and therefore commutes with any permutation of the inputrows.Theorem 12 (Permutation-Equivariant Universality [51]). For any continuouspermutation-equivariant map H : RnÃd âRnÃdâ² defined on a compact domain,there exists a finite-depth, finite-width stack of layers of the form Definition 11that approximates H arbitrarily well.To leverage this result, Cai et al. [6] construct an MPNN+VN architecture withconstant depth and polynomially increasing width to approximate full-attentionlayers. Their construction instantiates the equivariant DeepSets layer introducedin Definition 11, using message passing to realize both local transformation andglobal broadcasting.The MPNN+VN proceeds as follows:1. First layer. Each node computes the local terms XA and XB, then sends XB tothe virtual node (VN). The VN aggregates the average 1n ânj=1 XB j and storesthe result.432. Second layer. The VN broadcasts the aggregated message to all nodes. Eachnode adds it to its own XA, completing the equivariant transformation.This construction simulates the simplified DeepSets operation using a two-layer MPNN+VN. The VN aggregates global information and redistributes it, whileeach node handles its own local computation. By increasing the MPNNâs widthpolynomially with n, the architecture matches the expressivity of full-attention lay-ers under the width-scaling regime.Full-Attention Mechanism via Depth ScalingThe full-attention layer of a Graph Transformer computes:xi =nâj=1Î±i j v j, αi j = softmax j(qâ¤i k jâd),where qi, k j, and v j are the query, key, and value vectors of nodes i and j, respec-tively.We now describe the layer-by-layer construction of an MPNN+VN architecturethat approximates the full self-attention mechanism of a Graph Transformerâspecifically,the computation defined in Eq. (5.1)âusing constant width and linearly increasingdepth.1. First layer. Configure the virtual nodeâs attention so that it selects node featurex1. The VN stores x1 and broadcasts it to all real nodes.2. Second layer. Each node combines the received xË1 with its own key to computethe unnormalized attention score exp(qâ¤1 k j), and sends this scalar back to theVN. The VN aggregates these scores for query 1.3. Subsequent layers. Repeat the above two-layer procedure for each query xi,where i = 2, . . . ,n:â¢ Odd-numbered layer 2iâ1: The VN selects and broadcasts xËi.â¢ Even-numbered layer 2i: Each node returns its unnormalized score to theVN.44After 2n layers, the VN accumulates all pairwise attention scores.4. Final layer. The VN converts the unnormalized scores into normalized at-tention weights (via softmax), broadcasts them to all nodes, and each nodecomputes the final weighted sum ânj=1Î±i jv j, completing the approximation ofEq. (5.1).By treating the virtual node as a serial selector and global broadcaster, the ar-chitecture decomposes the dense all-pairs attention pattern into n sequential message-passing rounds. Each round handles one query, reducing the computation to localinteractions. This design trades width for depth and demonstrates that Transformer-style full attention can be emulated using constant-width MPNN+VN models undermild structural assumptions.5.2 Over-Squashing and MPNN+VNAlon et al. [1] identifies the issue of over-squashing as a significant problemaffecting the performance of Graph Neural Networks (GNNs). Over-squashing oc-curs when information is compressed into a fixed-length vector as the number ofGNN layers increases, leading to substantial information loss. This problem be-comes especially severe in long-range graphs, where information struggles to beefficiently transmitted to distant target nodes. Consequently, the model primarilylearns short-range information from training data, which results in poor general-ization performance during testing[15].To facilitate the analysis of over-squashing phenomenon, Black et al. [4] lever-age the commute time to measure the message passing steps required for informa-tion propagation and thereby quantify the extent of over-squashing in graph-basedmodels.Definition 13. In a graph G(V,E), the hitting time h(i, j) between two nodes i andj is the expected number of steps for a random walk to start from i and reaches j forthe first time. The commute time Ï(i, j) is defined to be h(i, j)+h( j, i)[7]. We useÏvn,k(i, j) to denote the commute time between nodes i and j in the VN-augmentedgraph of G by k virtual nodes, each of which is connected to all the real nodes.The following theorem is adapted from [7]:45Theorem 14. The commute time Ï(i, j) between nodes i and j can be expressed asÏ(i, j) = 2|E| Â·Ri, j = 2|E|(1iâ1 j)T Lâ (1iâ1 j)where Ri, j represents the resistance between nodes i and j for propagating infor-mation. 1v is the indicator vector of vertex v, and Lâ is the pseudoinverse of L.In following sections, we study the change of commute time by adding one ormultiple virtual nodes.Theorem 15. The change in commute time before and after adding a virtual nodecan be denoted as âÏcommute:âÏcommute = Ïvn(i, j)â Ï(i, j)= 2|E|nâ1ââ=11Î»â(Î»â+1)( n|E|Î»ââ1)(vâ(i)â vâ( j))2 (5.2)where Î»â and vâ denote the eigenvalues and eigenvectors of the normalized Lapla-cian of G, respectively.The average change in commute time for the entire graph can be expressed asâÏavg:âÏavg =1n2nâi, j=1(Ïvn(i, j)â Ï(i, j))=4|E|nnâ1ââ=11Î»â(Î»â+1)( n|E|Î»ââ1)(5.3)The observation that the average change in commute time is less than zerosuggests that adding a virtual node alleviates the over-squashing issue. However,in overly dense graphs, the average change in commute time may be greater thanzero. Despite this, Black et al. [4] confirm that in real-world graphs, adding avirtual node generally reduces commute time.Southern et al. [38] extends this to MPNN+VN, providing the minimal numberof layers m required to avoid over-squashing on MPNN+VN:46Corollary 16. Consider a graph G with nodes i and j where Equation (8) is neg-ative. In this case, there exist graph functions that depend on strong interactionsbetween different nodes i Ì¸= j, and the strength of these interactions remains abovea fixed constant that does not vary with the choice of i and j. As a result, foran MPNN with one virtual node and bounded weights to accurately learn suchfunctions, a greater number of message-passing layers m is required.mâ¥ Ïvn(i, j)8â |E|8·nâ1ââ=11Î»â(Î»â+1)( n|E|Î»ââ1)(vâ(i)â vâ( j))2 (5.4)This equation shows that after adding a virtual node, the minimum number ofMPNN layers required to avoid over-squashing decreases due to the impact on thecommute time of important components. This formula is constrained to graphswhere adding a virtual node reduces the commute time, where Southern et al. [38]states that such graphs are typical of many real-world scenarios. Corollary 16demonstrates that MPNN + VN can alleviate the over-squashing problem by en-hancing the capability of exchanging meaningful information between nodes. Ad-ditionally, it shows that the effectiveness of adding a virtual node is significantlyinfluenced by the graphâs spectrum. This implies that, compared to some graphrewiring techniques that can alter commute time, the advantage of a virtual node isthat they achieve this without incurring additional computational costs.We now extend this analysis to the case where multiple virtual nodes are in-serted. Specifically, we introduce k virtual nodes, each of which is fully connectedto all real nodes (but not to each other). By establishing this bipartite connectivity,the effective diameter of the graph is further reduced, enhancing information flowbetween distant nodes. This allows the model to capture more complex relation-ships among non-adjacent nodes.Theorem 17. Let G be a graph on n nodes, and GV N be the VN-augmented graphof G with k virtual nodes, each of which is connected to all real nodes. The changein commute time between nodes i and j is given by:Ïvn,k(i, j)â Ï(i, j) = 2|E|nâ1ââ=1kÎ»â(Î»â+ k)(n|E|Î»ââ1)(vâ(i)â vâ( j))2, (5.5)47where Î»â and vâ denote the eigenvalues and eigenvectors of the normalized Lapla-cian of G, respectively.The average change in commute time across all node pairs is:1n2nâi, j=1(Ïvn,k(i, j)â Ï(i, j)) = 4|E|nnâ1ââ=1kÎ»â(Î»â+ k)(n|E|Î»ââ1). (5.6)Proof. The effective resistance between two nodes i and j is given by the Laplacianpseudoinverse [19]:R(i, j) = Lâ ii+Lâ j jâ2Lâ i j=nâ1ââ=11Î»â(vâ(i)â vâ( j))2, (5.7)where Î»â denotes the nonzero eigenvalues of the Laplacian and vâ the correspond-ing eigenvectors.When k virtual nodes are added to form Gvn, the same formula holds with thespectrum of the new Laplacian Lvn:Rvn(i, j) =n+kâ1ââ=11Î» vnâ(vvnâ (i)â vvnâ ( j))2. (5.8)When we add k virtual nodes, the adjacency matrix changes asAvn =[A 1nÃk1kÃn 0],and the degree matrix isDvn =[D+ kIn 00 nIk].Therefore the Laplacian can be written asLvn =[L+ kIn â1nÃkâ1kÃn nIk].48From the block decomposition of Lvn, the eigenvalues and corresponding eigen-vectors can be described as follows:1. Zero eigenvalue. The normalized all-ones vectorvvn0 =1ân+k[1n1k]satisfies Lvnvvn0 = 0.2. Shifted eigenvalues from L. For each nonzero eigenvalue Î»â of L witheigenvector vâ (orthogonal to 1n), we haveLvn[vâ0]= (Î»â+ k)[vâ0].Thus, nâ1 eigenvalues of Lvn are obtained by shifting those of L by pulsingk.3. Eigenvalue n with multiplicity kâ 1. Any vector supported only on thevirtual nodes and orthogonal to 1k is an eigenvector:[0u], uâ¥ 1k,with eigenvalue n. This yields kâ1 linearly independent eigenvectors.4. Eigenvalue n+ k. There exists one eigenvector combining both real andvirtual nodes: [α1nβ1k], α =âkn(k+n) , β =âânk(k+n) ,corresponding to eigenvalue n+ k.By Theorem 14, commute time is proportional to the effective resistance:Ï(i, j) = 2|E|R(i, j).49In Gvn, the effective resistance satisfiesRvn(i, j) =n+kâ1ââ=11Î» vnâ(vvnâ (i)â vvnâ ( j))2.Among these eigenvalue and eigenvector components, the kâ 1 eigenvectorsassociated with eigenvalue n have zero entries on all real nodes, while the singleeigenvector associated with eigenvalue n+ k has constant entries (same value forevery real node, proportional to 1n). In both cases, the values at real nodes areeither all zero or all the same, so for any i, j âV ,vvnâ (i)â vvnâ ( j) = 0.Hence these terms vanish. Therefore only the nâ1 eigenvectors inherited from Gremain, with eigenvalues shifted to Î»â+ k, yieldingÏvn(i, j) = 2(|E|+nk)nâ1ââ=11Î»â+ k(vâ(i)â vâ( j))2.Subtracting the baseline commute time, we obtainÏvn(i, j)â Ï(i, j) =nâ1ââ=1(2(|E|+nk)Î»â+ kâ 2|E|Î»â)(vâ(i)â vâ( j))2. (5.9)Summing over all pairs of nodes:nâi, j=1(Ïvn(i, j)â Ï(i, j))= 2|E|nâ1ââ=1kÎ»â(Î»â+ k)(n|E|Î»ââ1) nâi, j=1(vâ(i)â vâ( j))2.(5.10)50Using orthonormality of the eigenvectors, we havenâi, j=1(vâ(i)â vâ( j))2 =nâi, j=1(vâ(i)2+ vâ( j)2â2vâ(i)vâ( j))= nnâi=1vâ(i)2+nnâj=1vâ( j)2â2( nâi=1vâ(i))2= 2nnâi=1vâ(i)2= 2n. (5.11)Therefore,1n2nâi, j=1(Ïvn(i, j)â Ï(i, j))=4|E|nnâ1ââ=1kÎ»â(Î»â+ k)(n|E|Î»ââ1). (5.12)This result reveals how the insertion of virtual nodes reduces average commutetime:â¢ Virtual node count k: The factor kÎ»â(Î»â+k) increases with k, implying astronger reduction in commute time when more virtual nodes are added.â¢ Spectral sensitivity: The summation weights each eigenvalueâs contributiondifferently, making the reduction depend on the graphâs spectral structure.â¢ Graph density: The factor n|E|Î»ââ1 emphasizes that sparse graphs tend tobenefit more from VN augmentation.The key insight here is that the cumulative effect of multiple virtual nodes cansignificantly reduce commute times, especially in graphs that initially suffer frompoor connectivity and over-squashing. However, adding too many virtual nodesdoes not necessarily bring positive effects. An excessive number of virtual nodesmay alter the original topology, making the graph overly dense, which reduces thedistinctiveness of information propagation paths and can even lead to decreased ef-ficiency. Therefore, the number of virtual nodes should be kept within a reasonable51range to strike a balance between improving information flow and preserving thegraph structure. We will empirically validate it in Section 6.7.Corollary 18. For a graph G with nodes i and j, and k virtual nodes added, ifthe change in commute time is negative, the minimum number of layers m requiredby a bounded-width MPNN to capture meaningful information exchange between iand j satisfies:mâ¥ Ï(i, j)8=Ïvn,k(i, j)8â 18(Ïvn,k(i, j)â Ï(i, j))=Ïvn,k(i, j)8â |E|4nâ1ââ=1kÎ»â(Î»â+ k)(n|E|Î»ââ1)(vâ(i)â vâ( j))2.(5.13)Proof. From the result of Di Giovanni et al. [14], the required number of layers islower bounded by commute time:mâ¥ Ï(i, j)8. (5.14)We decompose this using the commute time after adding virtual nodes:Ï(i, j)8=Ïvn,k(i, j)8â 18(Ïvn,k(i, j)â Ï(i, j)) . (5.15)Using the earlier expression for commute time change:Ïvn,k(i, j)â Ï(i, j) = 2|E|nâ1ââ=1kÎ»â(Î»â+ k)(n|E|Î»ââ1)(vâ(i)â vâ( j))2 . (5.16)Substituting this into the decomposition, we obtain:mâ¥ Ï(i, j)8=Ïvn,k(i, j)8â |E|4nâ1ââ=1kÎ»â(Î»â+ k)(n|E|Î»ââ1)(vâ(i)â vâ( j))2 .(5.17)This completes the proof.52Chapter 6MPNN + Virtual Nodes:ExperimentsPrevious studies have conducted experiments on virtual nodes across differentmodels and tasks, but lacked comparative experiments on this technique. In thissection, we will discuss the comparative experiments we have added to addressthis gap and the experiments are divided into two main parts. The first part in-volves evaluating the mitigation of the over-squashing problem in various GNNswith the addition of virtual nodes on synthetic neighbor matching tasks. The sec-ond part consists of experiments on real chemical analysis datasets, comparing theperformance of different GNNs under various virtual node initialization methods.6.1 Experiment Design and MethodologyAs shown in Figure 6.1, our experiments consist of four steps.53Figure 6.1: The Framework of Experiments(a) First, we obtain the original input graph. In this thesis, two types of datasetsare used. The first type involves tree-structured graphs from the tree neighbormatching problem, which will be introduced in detail in Section 6.4. Thesecond type is the peptide graphs, which are used for graph-level regressionand classification tasks.(b) In the second step, we preprocess the original input graph by adding virtualnodes. The algorithm for adding virtual nodes mainly involves two aspects:the number of virtual nodes, and the connection strategy between virtual andreal nodes. The resulting graph with virtual nodes is treated as the input for54the subsequent models.(c) Third, we run the corresponding graph models, which mainly include GCN,GGNN, GIN, and GAT. The specific configurations are described in Section6.3.(d) In the final step, the embedding vectors of nodes are used as inputs to task-specific heads to obtain the corresponding outputs. For the Tree NeighborMatching problem, the output is the node-level label of the root node. Forthe peptides-func task, the output is a graph-level multi-label classificationresult. For the peptides-struct task, the output is a graph-level predictionvalue.After determining the overall experimental workflow, we design two classesof connection strategies: (1) connections between virtual nodes and real nodes(VâR), and (2) connections among virtual nodes themselves (VâV). These twoaspects jointly determine how information is aggregated and propagated in a VN-augmented graph.(1) VirtualâReal (VâR) connections. We implement two main strategies forlinking virtual nodes to real nodesâneighboring and coloring.Neighboring method. We apply the Louvain community detection algorithm [5]to divide the graph into k communities, where k equals the number of virtual nodes.Each virtual node is then connected to all real nodes within one community. Thismakes each virtual node represent a specific part of the graph based on its commu-nity structure.Coloring method. We apply the WelshâPowell graph coloring algorithm [45]to assign different color labels to real nodes so that adjacent nodes have differentcolors. Each virtual node corresponds to one color and connects to all real nodesof that color. This ensures that all real nodes are linked to one virtual node in anon-overlapping way.(2) VirtualâVirtual (VâV) connections. We further consider three internalconnection types among virtual nodes:None connection. Virtual nodes are not connected to each other.55Circled connection. Virtual nodes are linked in a circular chain, forming aclosed loop that allows information to flow among them.Full connection. All virtual nodes are connected to each other, forming a com-plete subgraph that enables global information exchange.These connection strategies define the structure of VN-augmented graphs andserve as the basis for the experiments shown in Tables 6.3â??.6.2 Experiment SetupWe implemented our Graph Neural Network models using PyTorch Geometricand NetworkX libraries to evaluate GCN+VNs, GINE+VNs, and GatedGCN+VNson the Long Range Graph Benchmark[16]. Additionally, we conducted experi-ments on the Tree Neighbor Matching problem[1] to analyze the performance vari-ations of GCN, GatedGCN, GAT, and GINE when augmented with virtual nodes.All experiments were performed on a Linux system using the UBC ARC Sockeyecomputing resources with the following hardware specifications: 24 CPU coresand 192GB RAM (8GB per core), utilizing one NVIDIA Tesla V100 16GB GPUfrom the available four-GPU configuration, along with 1.9TB NVMe local scratchstorage.6.3 Models and Training SettingAll the GNN models considered in our experiments share a set of commonconfiguration parameters, such as the number of layers, the dimension of hiddenrepresentations, and the number of training epochs. Table 6.1 summarizes thesecommon hyperparameters used throughout all models.In addition to the shared settings, each model has its own controllable param-eters, such as activation functions or architecture-specific modules. Table 6.2 out-lines the individual configuration and total parameter count for each model.6.4 DatasetsTraditional message-passing-based GNNs typically exchange information be-tween first-order neighbors, making long-range information exchange difficult or56Table 6.1: Common hyperparameters for all GNN models.Parameter ValueNumber of layers 5 (for MP-GNNs), 4 (for Transformer models)Hidden dimension 128Batch size 128Learning rate 0.001Optimizer AdamDropout rate 0.1Maximum training epochs 100Weight initialization Xavier uniformTable 6.2: Model-specific settings and total parameter count.Model Layers Activation Special Modules ParametersGCN 5 ReLU â 508KGINE 5 ReLU Edge MLP 476KGatedGCN 5 ReLU Gating units 509KGAT 5 ReLU Multi-head attention (8 heads) 512KTransformer 4 ReLU Fully-connected attention layers 488Konly possible through multiple layers of GNNs. This can lead to issues such asunder-reaching and potential over-squashing. The Long Range Graph Benchmark(LRGB)[16] is a dataset designed to test the ability of GNN models to handlelong-range dependencies. In this thesis, we focus on conducting experiments usingPeptides-func and Peptides-struct to evaluate the performance changes in GNNsafter inserting virtual nodes.57Figure 6.2: An Example of Tree Neighbor MatchingFigure 6.2 shows an example of Tree Neighbor Matching of a depth-3 tree.The target node (?) is the root of this tree. Green nodes (A, B, C,...) show theirnumber of blue neighbors: A has 1, B has 2, C has 0, etc. The task is to predict?âs label based on its blue neighbors. The answer is C because ? has 2 blue neigh-bors, matching node B (marked C). The model must aggregate information fromall leaves to the target node and base its prediction on a single fixed-dimensionalvector encoding this information.Peptides-func is a multi-label graph classification dataset comprising 10 classesrelated to peptide functions such as Antibacterial, Antiviral, cell-cell communica-tion, among others. It is treated as a multi-label classification problem becausepeptides can belong to multiple classes concurrently, averaging 1.65 out of the 10classes per peptide. The dataset exhibits class imbalance, with only 16.5% of thedata belonging to the positive class. The distribution varies widely among classes,with the richest class having 62.7% positives and the poorest class having only581.9%.Peptides-struct is a multi-label graph regression dataset derived from the 3Dstructure of peptides. It shares the same graph structures as Peptides-func butserves a different purpose. Our objective here is to forecast aggregated 3D prop-erties of the peptides at the graph level. These properties, which have been nor-malized to zero mean and unit standard deviation, encompass Inertia mass, Iner-tia valence, Length, Sphericity, and Plane best fit.6.5 Alleviate Over-SquashingOver-squashing is a significant obstacle to the performance of GNN models.When downstream tasks involve dependencies between distant nodes and the graphdiameter exceeds the message-passing layers of an MPNN, information from dis-tant nodes becomes increasingly distorted during message passing, leading to poorperformance on downstream tasks. This issue, caused by excessive informationcompression, is referred to as âover-squashing.âFigure 6.3: Comparative Performance Before and After Adding VNsTo validate the existence of over-squashing, Alon et al.[1] proposes a contrivedproblem, named Tree-NeighborMatch. The setup involves a binary tree of a givendepth, where both the root and leaf nodes are labeled, and information is passed59from the leaf nodes to the root. The goal is to predict the root nodeâs label based onthe labels of the leaf nodes. By adjusting the treeâs depth, or effectively the graphradius, the severity of the over-squashing issue can be controlled.We conducted experiments on four models, including GGNN(Gated GraphNeural Network), GAT(Graph Attention Network), GIN(Graph Neural Networks),and GCN(Graph Convolutional Network), across various tree depths. For the hy-perparameter settings of virtual nodes, the number of virtual nodes equals the treedepth. V-R connections are initialized using the randomly connected method, whileV-V connections are initialized as fully connected. The Figure 6.3 primarily com-pares the performance of these models before and after adding virtual nodes.From the experimental results, it can be seen that an increase in the radius af-fects the modelâs performance, highlighting the exacerbation of the over-squashingproblem. When the radius is 1 or 2, the accuracy can reach perfection becausemost GNN models have 2 layers, and in this case, the compression of informa-tion is not severe. However, when the radius exceeds 5, the modelâs performanceis significantly impacted. In contrast, after adding virtual nodes, regardless of theseverity of over-squashing, all models show improvements compared to their origi-nal versions. Notably, GGNN shows a remarkable improvement, maintaining goodperformance even when the radius exceeds 5.6.6 Improve Performance of GNNsAdding virtual nodes leads to observable improvements in model perfor-mance. When we evaluate the performance of different methods for connectingvirtual nodes to real nodes (V-R) and to other virtual nodes (V-V), we can observethat the addition of virtual nodes generally improves model performance, particu-larly in terms of test accuracy (Test AP). Across all three models, the inclusion ofvirtual nodes shows a consistent upward trend in test performance, regardless ofwhether virtual-real (V-R) or virtual-virtual (V-V) connections are applied.60Table 6.3: Performance on Peptides-func with different v-r connection meth-ods. Each model has 4 layers, 4 virtual nodes, and fully connected v-vconnections.Model V-R Connection Train AP Test APâGCNNone 0.8840±0.0131 0.5930±0.0023Coloring 0.8907±0.0085 0.6637±0.0048Neighboring 0.9018±0.0098 0.6761±0.0036GINENone 0.7682±0.0154 0.5498±0.0079Coloring 0.9432±0.0050 0.6664±0.0032Neighboring 0.9796±0.0045 0.6496±0.0025GatedGCNNone 0.8695±0.0402 0.5864±0.0077Coloring 0.9259±0.0062 0.6857±0.0038Neighboring 0.9094±0.0081 0.5895±0.0050Table 6.4: Performance on Peptides-struct with different v-r connectionmethods. Each model has 4 layers, 4 virtual nodes, and fully connectedv-v connections.Model V-R Connection Train MAE Test MAEâGCNNone 0.2939±0.0055 0.3496±0.0013Coloring 0.2373±0.0021 0.2490±0.0009Neighboring 0.2377±0.0030 0.2524±0.0012GINENone 0.3116±0.0047 0.3547±0.0045Coloring 0.2470±0.0025 0.2556±0.0018Neighboring 0.2519±0.0021 0.2602±0.0019GatedGCNNone 0.2761±0.0032 0.3420±0.0013Coloring 0.2183±0.0015 0.2474±0.0020Neighboring 0.2343±0.0017 0.2556±0.001861The coloring method shows consistently observable improvements in modelperformance. The results presented in Table 6.4 and Table 6.3 show that the âcol-oringâ connection method leads to a consistent increase in performance acrossmetrics. For all three modelsâGCN, GINE, and GatedGCNâthe use of color-ing produces higher test scores than both the None and neighboring methods. Forexample, in the GCN model, the Test AP increases from 0.5930 to 0.6637 with col-oring; the GINE model also increases from 0.5498 to 0.6664; and the GatedGCNmodel reaches the highest observed Test AP of 0.6857.Different V-V connection methods show only small observable differencesin performance. As shown in Table ?? and Table ??, all V-V connection meth-ods slightly improve model performance, but the differences between them aresmall. For instance, the Test AP of the GCN model shows only a minor differencebetween the None Connection (0.6661) and Circled Connection (0.6674) meth-ods. The GatedGCN model achieves the highest Test AP of 0.6857 using the FullConnection method, but overall, the performance variations among V-V strategiesremain limited compared with those among V-R connection methods.6.7 Optimal Number of Virtual NodesTo further validate our theoretical analysis of Theorem 17, we conduct experi-ments on four real-world datasets: Cora and Citeseer [37], which are citation net-works with relatively dense structures, and Texas and Cornell [33], which are webpage networks characterized by sparser and more irregular connectivity. Note thatin the VN-augmented graph, each of virtual nodes is connected to all nodes. Thisis different from geenral connection pattern that we discussed in our taxonomy.As shown in Figure 6.4, the eigenvalue distributions of these graphs are highlyskewed: most eigenvalues are close to zero while only a few are relatively large.This spectral property makes the effect of virtual nodes more pronounced, sincesmall eigenvalues amplify the impact of the additional connections.Figure 6.5 further illustrates the change in average commute time âÏavg acrossdifferent values of k. All datasets exhibit a U-shaped curve: at first, adding asmall number of virtual nodes significantly improves connectivity and alleviatesstructural bottlenecks, which reduces commute times. For example, the optimal62Figure 6.4: Eigenvalue distributions of real-world graphsk is 3 for Cora, 4 for Citeseer, and 3 for both Texas and Cornell. However, as kcontinues to increase, the graph becomes excessively dense, leading to less efficientinformation flow and eventually an increase in average commute time.In summary, while inserting virtual nodes helps improve information pass-ing, adding too many may distort the original structure and diminish the benefits.Therefore, selecting an appropriate number of virtual nodes is crucial: it improvesconnectivity without distorting the graph.63Figure 6.5: Impact of the number of virtual nodes on average commute time64Chapter 7ConclusionsIn conclusion, this thesis presents a comprehensive review and systematic studyof the role of virtual nodes in Graph Neural Networks (GNNs). We propose theconcept of a projection graph, which serves as an analytical tool rather than amodel design, aiming to provide a theoretical perspective for understanding thefunctional importance of virtual nodes within message passing frameworks. Build-ing on this abstraction, we introduce a taxonomy of virtual node techniques alongtwo dimensions: effective density and locality. Based on this taxonomy, we furtheranalyze the importance of virtual nodes through their betweenness centrality.Our findings show that the performance of GNNs depends heavily on the num-ber of virtual nodes. Specifically, increasing the number of virtual nodes initiallyleads to improved performance by enhancing message passing and representationlearning. However, beyond a certain threshold, the performance begins to de-cline due to the introduction of redundant or noisy information, which hinders themodelâs ability to learn meaningful patterns.In addition to empirical studies, we extend the existing theoretical analysis onnode insertion and over-squashing from the single-node case to multiple virtualnodes. Our proof indicates that adding an appropriate number of virtual nodesfacilitates faster message propagation between distant nodes and helps reduce in-formation loss.While this thesis provides a systematic study of virtual nodes and their rolein message passing, several limitations remain. First, our experimental analysis is65restricted to medium-sized graph benchmarks such as Peptides-func and Peptides-struct. The scalability and behavior of VN-augmented models on large-scale ordynamic graphs remain unexplored. Second, the theoretical results are derivedunder simplified assumptions, such as fixed virtualâreal connectivity. Relaxingthese assumptions or extending the analysis to adaptive or learnable virtual nodeconnections may lead to different conclusions. Third, although the projection graphframework offers an analytical view of information flow, it abstracts away detailsof model optimization and learning dynamics. More work is required to see howthese structures affect model training and generalization.There are several directions worth exploring in future work. First, our currentstudy only considers a single layer of virtual nodes, where each virtual node di-rectly connects to a subset of real nodes. Introducing multiple layers of virtualnodes may allow the model to hierarchically capture graph structure, further im-proving performance. Second, we have not evaluated our method on heterophilicgraphs, where semantically similar nodes may not be connected. In such settings,using color-based or function-aware virtual-to-real connections may help discoveruseful long-range dependencies. Finally, our current virtual node connections arestatic. Dynamically re-connecting virtual nodes and real nodes during training,based on learned signals or structural feedback, may further enhance the flexibilityand effectiveness of virtual node-based GNNs.66Bibliography[1] U. Alon and E. Yahav. On the bottleneck of graph neural networks and itspractical implications. arXiv preprint arXiv:2006.05205, 2020. â pages18, 20, 45, 56, 59[2] A. Arnaiz-Rodrı´guez, A. Begga, F. Escolano, and N. Oliver. Diffwire:Inductive graph rewiring via the lov\u00E2asz bound. arXiv preprintarXiv:2206.07369, 2022. â page 18[3] P. Barcelo´, E. V. Kostylev, M. Monet, J. Pe´rez, J. Reutter, and J.-P. Silva.The logical expressiveness of graph neural networks. In 8th InternationalConference on Learning Representations, 2020. â page 32[4] M. Black, Z. Wan, A. Nayyeri, and Y. Wang. Understanding oversquashingin gnns through the lens of effective resistance. In International Conferenceon Machine Learning, pages 2528â2547, 2023. â pages 45, 46[5] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre. Fastunfolding of communities in large networks. Journal of StatisticalMechanics: Theory and Experiment, 2008(10):P10008, 2008. â page 55[6] C. Cai, T. S. Hy, R. Yu, and Y. Wang. On the connection between mpnn andgraph transformer. In International conference on machine learning, pages3408â3430, 2023. â pages 2, 40, 41, 42, 43[7] A. K. Chandra, P. Raghavan, W. L. Ruzzo, R. Smolensky, and P. Tiwari. Theelectrical resistance of a graph captures its commute and cover times.Proceedings of the twenty-first annual ACM symposium on Theory ofcomputing, pages 574â586, 1989. â page 45[8] D. Chen, Y. Lin, W. Li, P. Li, J. Zhou, and X. Sun. Measuring and relievingthe over-smoothing problem for graph neural networks from the topologicalview. In Proceedings of the AAAI conference on artificial intelligence, pages3438â3445, 2020. â pages 19, 2067[9] X. Chen, S. Jia, and Y. Xiang. A review: Knowledge reasoning overknowledge graph. Expert systems with applications, page 112948, 2020. âpage 1[10] Y. Chen, Y. Luo, J. Tang, L. Yang, S. Qiu, C. Wang, and X. Cao. LSGNN:Towards general graph neural network in node classification by localsimilarity. arXiv preprint arXiv:2305.04225, 2023. â pages 2, 18[11] K. Choromanski, V. Likhosherstov, D. Dohan, X. Song, A. Gane, T. Sarlos,P. Hawkins, J. Davis, A. Mohiuddin, and L. Kaiser. Rethinking attentionwith performers. arXiv preprint arXiv:2009.14794, 2020. â page 41[12] F. R. K. Chung. Spectral Graph Theory, volume 92. AmericanMathematical Society, 1997. â page 7[13] E. Dai, W. Jin, H. Liu, and S. Wang. Towards robust graph neural networksfor noisy graphs with sparse labels. In Proceedings of the 15th ACMInternational Conference on Web Search and Data Mining (WSDM), pages181â191, 2022. â page 15[14] F. Di Giovanni, L. Giusti, F. Barbero, G. Luise, P. Lio, and M. M. Bronstein.On over-squashing in message passing neural networks: The impact ofwidth, depth, and topology. In International conference on machinelearning, pages 7865â7885, 2023. â pages 18, 33, 52[15] F. Di Giovanni, T. K. Rusch, M. M. Bronstein, A. Deac, M. Lackenby,S. Mishra, and P. VelicËkovic´. How does over-squashing affect the power ofGNNs? arXiv preprint arXiv:2306.03589, 2023. â pages 3, 45[16] V. P. Dwivedi, L. Rampa´sËek, M. Galkin, A. Parviz, G. Wolf, A. T. Luu, andD. Beaini. Long range graph benchmark. Advances in Neural InformationProcessing Systems, pages 22326â22340, 2022. â pages 56, 57[17] M. Fiedler. Algebraic connectivity of graphs. Czechoslovak MathematicalJournal, 23(2):298â305, 1973. â page 7[18] J. Gasteiger, M. Lienen, and S. Gu¨nnemann. Scalable optimal transport inhigh dimensions for graph distances, embedding alignment, and more. InInternational Conference on Machine Learning, pages 5616â5627, 2021. âpage 10[19] A. Ghosh, S. P. Boyd, and A. Saberi. Minimizing effective resistance of agraph. SIAM Review, 50(1):37â66, 2008. â page 4868[20] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neuralmessage passing for quantum chemistry. In International conference onmachine learning, pages 1263â1272, 2017. â pages 2, 9, 30[21] W. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning onlarge graphs. Advances in neural information processing systems, 2017. âpage 10[22] E. Hwang, V. Thost, S. S. Dasgupta, and T. Ma. An analysis of virtual nodesin graph neural networks for link prediction. In The first learning on graphsconference, 2022. â pages 2, 34[23] K. Ishiguro, S.-i. Maeda, and M. Koyama. Graph warp module: an auxiliarymodule for boosting the power of graph neural networks in molecular graphanalysis. arXiv preprint arXiv:1902.01020, 2019. â pages 2, 31[24] W. Jin, Y. Ma, X. Liu, X. Tang, S. Wang, and J. Tang. Graph structurelearning for robust graph neural networks. In Proceedings of the 26th ACMSIGKDD International Conference on Knowledge Discovery and DataMining (KDD), pages 66â74, 2020. â page 15[25] T. N. Kipf and M. Welling. Semi-supervised classification with graphconvolutional networks. arXiv preprint arXiv:1609.02907, 2016. â page 10[26] L. Kong, Y. Chen, and M. Zhang. Geodesic graph neural network forefficient graph representation learning. Advances in neural informationprocessing systems, pages 5896â5909, 2022. â page 2[27] D. Kreuzer, D. Beaini, W. Hamilton, V. Le´tourneau, and P. Tossou.Rethinking graph transformers with spectral attention. Advances in NeuralInformation Processing Systems, pages 21618â21629, 2021. â pages2, 10, 41[28] B. Lester, R. Al-Rfou, and N. Constant. The power of scale forparameter-efficient prompt tuning. arXiv preprint arXiv:2104.08691, 2021.â page 31[29] Q. Li, Z. Han, and X.-M. Wu. Deeper insights into graph convolutionalnetworks for semi-supervised learning. In Proceedings of the AAAIconference on artificial intelligence, 2018. â page 19[30] H. Lin, M. Yan, X. Ye, D. Fan, S. Pan, W. Chen, and Y. Xie. AComprehensive Survey on Distributed Training of Graph Neural Networks.Proceedings of the IEEE, pages 1572â1606, 2023. â page 169[31] W. Lu, Z. Guan, W. Zhao, Y. Yang, and L. Jin. Nodemixup: Tacklingunder-reaching for graph neural networks. In Proceedings of the AAAIConference on Artificial Intelligence, volume 38, pages 14175â14183, 2024.â pages 1, 20[32] J. C. Mitchell. Social Networks. Annual Review of Anthropology, pages279â299, 1974. Publisher: Annual Reviews. â page 5[33] H. Pei, B. Wei, K. C.-C. Chang, Y. Lei, and B. Yang. Geom-GCN:Geometric graph convolutional networks. In Proceedings of the 8thInternational Conference on Learning Representations (ICLR), 2020. âpage 62[34] T. Pham, T. Tran, H. Dam, and S. Venkatesh. Graph classification via deeplearning with virtual nodes. arXiv preprint arXiv:1708.04357, 2017. âpages 2, 31[35] T. K. Rusch, M. M. Bronstein, and S. Mishra. A survey on oversmoothing ingraph neural networks. arXiv preprint arXiv:2303.10993, 2023. â page 1[36] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. Thegraph neural network model. IEEE transactions on neural networks, pages61â80, 2008. â page 8[37] P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad.Collective classification in network data. AI Magazine, 29(3):93â106, 2008.â page 62[38] J. Southern, F. Di Giovanni, M. Bronstein, and J. F. Lutzeyer. Understandingvirtual nodes: Oversmoothing, oversquashing, and node heterogeneity.arXiv preprint arXiv:2405.13526, 2024. â pages 2, 46, 47[39] K. Sun, Z. Lin, and Z. Zhu. Multi-stage self-supervised learning for graphconvolutional networks on graphs with few labeled nodes. In Proceedings ofthe AAAI Conference on Artificial Intelligence, volume 34, pages5892â5899, 2020. â page 15[40] Q. Sun, J. Li, H. Yuan, X. Fu, H. Peng, C. Ji, Q. Li, and P. S. Yu.Position-aware structure learning for graph topology-imbalance by relievingunder-reaching and over-squashing. In Proceedings of the 31st ACMInternational Conference on Information & Knowledge Management, pages1848â1857, 2022. â page 2070[41] Z. Tan, R. Guo, K. Ding, and H. Liu. Virtual node tuning for few-shot nodeclassification. In Proceedings of the 29th ACM SIGKDD Conference onKnowledge Discovery and Data Mining, pages 2177â2188, 2023. â page31[42] J. Topping, F. Di Giovanni, B. P. Chamberlain, X. Dong, and M. M.Bronstein. Understanding over-squashing and bottlenecks on graphs viacurvature. arXiv preprint arXiv:2111.14522, 2021. â pages 1, 2[43] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez,Kaiser, and I. Polosukhin. Attention is all you need. Advances in neuralinformation processing systems, 2017. â page 11[44] P. VelicËkovic´, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio.Graph attention networks. arXiv preprint arXiv:1710.10903, 2017. â pages2, 10[45] D. J. A. Welsh and M. B. Powell. An upper bound for the chromatic numberof a graph and its application to timetabling problems. The ComputerJournal, 10(1):85â86, 1967. â page 55[46] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu. A comprehensivesurvey on graph neural networks. IEEE transactions on neural networks andlearning systems, pages 4â24, 2020. â pages 1, 10[47] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neuralnetworks? arXiv preprint arXiv:1810.00826, 2018. â page 10[48] Y. Xue, Y. Liao, X. Chen, and J. Zhao. Node augmentation methods forgraph neural network based object classification. In 2021 2nd InternationalConference on Computing and Data Science, pages 556â561, 2021. âpages 2, 33, 34[49] C. Ying, T. Cai, S. Luo, S. Zheng, G. Ke, D. He, Y. Shen, and T.-Y. Liu. Dotransformers really perform badly for graph representation? Advances inneural information processing systems, pages 28877â28888, 2021. â pages2, 14, 18, 30[50] S. Yun, M. Jeong, R. Kim, J. Kang, and H. J. Kim. Graph transformernetworks. Advances in neural information processing systems, 2019. âpage 271[51] M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Poczos, R. R. Salakhutdinov, andA. J. Smola. Deep sets. Advances in neural information processing systems,2018. â page 43[52] W. Zhang, W. Ou, W. Li, J. Gou, W. Xiao, and B. Liu. Robust graphstructure learning with virtual nodes construction. Mathematics, page 1397,2023. â page 2[53] L. Zhao and L. Akoglu. Pairnorm: Tackling oversmoothing in gnns. arXivpreprint arXiv:1909.12223, 2019. â pages 14, 20[54] M. Zhao and H. Schu¨tze. Discrete and soft prompting for multilingualmodels. arXiv preprint arXiv:2109.03630, 2021. â page 31[55] Y. Zheng, J. Xu, and L. Chen. Learn from heterophily: Heterophilousinformation-enhanced graph neural network. arXiv preprintarXiv:2403.17351, 2024. â page 1[56] J. Zhou, G. Cui, S. Hu, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, andM. Sun. Graph neural networks: A review of methods and applications. AIOpen, 1:57â81, 2020. â page 1572
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Gao, Yong
Virtual nodes for graph neural networks : techniques, impact, and theoretical analysis
Text