Local Virtual Nodes for Alleviating Over-Squashing in Graph Neural Networks

• URL: http://arxiv.org/abs/2508.20597v1
• Date: Thu, 28 Aug 2025 09:39:32 GMT
• Title: Local Virtual Nodes for Alleviating Over-Squashing in Graph Neural Networks
• Authors: Tuğrul Hasan Karabulut, İnci M. Baytaş,
• Abstract summary: Over-squashing is a challenge in training graph neural networks for tasks involving long-range dependencies.<n>This study presents Local Virtual Nodes (LVN) with trainable embeddings to alleviate the effects of over-squashing.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Over-squashing is a challenge in training graph neural networks for tasks involving long-range dependencies. In such tasks, a GNN's receptive field should be large enough to enable communication between distant nodes. However, gathering information from a wide range of neighborhoods and squashing its content into fixed-size node representations makes message-passing vulnerable to bottlenecks. Graph rewiring and adding virtual nodes are commonly studied remedies that create additional pathways around bottlenecks to mitigate over-squashing. However, these techniques alter the input graph's global topology and disrupt the domain knowledge encoded in the original graph structure, both of which could be essential to specific tasks and domains. This study presents Local Virtual Nodes (LVN) with trainable embeddings to alleviate the effects of over-squashing without significantly corrupting the global structure of the input graph. The position of the LVNs is determined by the node centrality, which indicates the existence of potential bottlenecks. Thus, the proposed approach aims to improve the connectivity in the regions with likely bottlenecks. Furthermore, trainable LVN embeddings shared across selected central regions facilitate communication between distant nodes without adding more layers. Extensive experiments on benchmark datasets demonstrate that LVNs can enhance structural connectivity and significantly improve performance on graph and node classification tasks. The code can be found at https://github.com/ALLab-Boun/LVN/}{https://github.com/ALLab-Boun/LVN/.

Related papers

• Understanding Virtual Nodes: Oversquashing and Node Heterogeneity [4.59357989139429]
  Augmenting MPNNs with a virtual node (VN) has been found to improve performance on a range of benchmarks.<n>We provide a comprehensive theoretical analysis of the role of VNs and benefits thereof.<n>We propose a variant of VN with the same computational complexity, which can have different sensitivity to nodes based on the graph structure.
  arXiv  Detail & Related papers  (2024-05-22T10:51:12Z)
• Graph Elimination Networks [8.806990624643333]
  Graph Neural Networks (GNNs) are widely applied across various domains, yet they perform poorly in deep layers. We show that the root cause of GNNs' performance degradation in deep layers lies in ineffective neighborhood feature propagation. We introduce Graph Elimination Networks (GENs), which employ a specific algorithm to eliminate redundancies during neighborhood propagation.
  arXiv  Detail & Related papers  (2024-01-02T14:58:59Z)
• Degree-based stratification of nodes in Graph Neural Networks [66.17149106033126]
  We modify the Graph Neural Network (GNN) architecture so that the weight matrices are learned, separately, for the nodes in each group. This simple-to-implement modification seems to improve performance across datasets and GNN methods.
  arXiv  Detail & Related papers  (2023-12-16T14:09:23Z)
• Collaborative Graph Neural Networks for Attributed Network Embedding [63.39495932900291]
  Graph neural networks (GNNs) have shown prominent performance on attributed network embedding. We propose COllaborative graph Neural Networks--CONN, a tailored GNN architecture for network embedding.
  arXiv  Detail & Related papers  (2023-07-22T04:52:27Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• DOTIN: Dropping Task-Irrelevant Nodes for GNNs [119.17997089267124]
  Recent graph learning approaches have introduced the pooling strategy to reduce the size of graphs for learning. We design a new approach called DOTIN (underlineDrunderlineopping underlineTask-underlineIrrelevant underlineNodes) to reduce the size of graphs. Our method speeds up GAT by about 50% on graph-level tasks including graph classification and graph edit distance.
  arXiv  Detail & Related papers  (2022-04-28T12:00:39Z)
• Graph Neural Diffusion Networks for Semi-supervised Learning [5.836987579515698]
  Graph Convolutional Networks (GCN) is a pioneering model for graph-based semi-supervised learning.<n>We propose a new graph neural network called neural-Nets (for Graph Neural Diffusion Networks) that exploits the local and global neighborhood information.<n>The adoption of neural networks makes neural diffusions adaptable to different datasets.
  arXiv  Detail & Related papers  (2022-01-24T14:07:56Z)
• Local Augmentation for Graph Neural Networks [78.48812244668017]
  We introduce the local augmentation, which enhances node features by its local subgraph structures. Based on the local augmentation, we further design a novel framework: LA-GNN, which can apply to any GNN models in a plug-and-play manner.
  arXiv  Detail & Related papers  (2021-09-08T18:10:08Z)
• Integrating Network Embedding and Community Outlier Detection via Multiclass Graph Description [15.679313861083239]
  We propose a novel unsupervised graph embedding approach (called DMGD) which integrates outlier and community detection with node embedding. We show the theoretical bounds on the number of outliers detected by DMGD. Our formulation boils down to an interesting minimax game between the outliers, community assignments and the node embedding function.
  arXiv  Detail & Related papers  (2020-07-20T16:21:07Z)
• Graph Highway Networks [77.38665506495553]
  Graph Convolution Networks (GCN) are widely used in learning graph representations due to their effectiveness and efficiency. They suffer from the notorious over-smoothing problem, in which the learned representations converge to alike vectors when many layers are stacked. We propose Graph Highway Networks (GHNet) which utilize gating units to balance the trade-off between homogeneity and heterogeneity in the GCN learning process.
  arXiv  Detail & Related papers  (2020-04-09T16:26:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.