Adaptive Initial Residual Connections for GNNs with Theoretical Guarantees
Mohammad Shirzadi, Ali Safarpoor Dehkordi, Ahad N. Zehmakan · 2025
Read Adaptive Initial Residual Connections for GNNs with Theoretical Guarantees by Mohammad Shirzadi, Ali Safarpoor Dehkordi, Ahad N. Zehmakan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-06598.txt.
Introduction
Mohammad Shirzadi, Ali Safarpoor Dehkordi, and Ahad Zehmakan keep deep graph neural networks from washing out into sameness. Message passing lets each node blend neighbor information, but stacking many layers smooths embeddings until nodes look alike. Residual connections that remix the original features help, and this work lets each node keep its own residual strength.
The authors prove the adaptive scheme keeps the embeddings' Dirichlet energy away from zero, blocking oversmoothing. The guarantee is the first of its kind, covering even fixed residual strengths together with activation functions. Experiments favor the method over leading message passing designs, especially where neighbors carry different labels, and a hand-set variant matches the learned one at lower cost.
Catalog record
| CREATOR | Mohammad Shirzadi, Ali Safarpoor Dehkordi, Ahad N. Zehmakan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-06598
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Adaptive Initial Residual Connections for GNNs with Theoretical Guarantees Mohammad Shirzadi, Ali Safarpoor Dehkordi, Ahad N. Zehmakan Abstract Message passing is the core operation in graph neural networks, where each node updates its embeddings by aggregating information from its neighbors. However, in deep architectures, this process often leads to diminished expressiveness. A popular solution is to use residual connections, where the input from the current (or initial) layer is added to aggregated neighbor information to preserve embeddings across layers. Following a recent line of research, we investigate an adaptive residual scheme in which different nodes have varying residual strengths. We prove that this approach prevents oversmoothing; particularly, we show that the Dirichlet energy of the embeddings remains bounded away from zero. This is the first theoretical guarantee not only for the adaptive setting, but also for static residual connections (where residual strengths are shared across nodes) with activation functions. Furthermore, extensive experiments show that this adaptive approach outperforms standard and state-of-the-art message passing mechanisms, especially on heterophilic graphs. To improve the time complexity of our approach, we introduce a variant in which residual strengths are not learned but instead set heuristically, a choice that performs as well as the learnable version. Introduction Neural message passing ( Gilmer et al. 2017 ) serves as the foundation of modern graph representation learning, providing a core mechanism for aggregating neighborhood information in graph-structured data. This principle underlies Graph Convolutional Networks (GCNs) ( Kipf and Welling 2017 ) and their variants, such as GraphSAGE ( Hamilton et al. 2017 ) and Graph Attention Networks (GAT) ( Veličković et al. 2018 ) , which learn node embeddings through iterative feature aggregation and transformation. The versatility of graph neural networks (GNNs) has led to their successful deployment across numerous domains, for example, accurate traffic prediction in transportation systems ( Van Langendonck, Castell-Uroz, and Barlet-Ros 2024 ) , pandemic analysis in public health ( Panagopoulos, Nikolentzos, and Vazirgiannis 2021 ; Sehanobish, Ravindra, and van Dijk 2021 ) , economic forecasting ( Ye et al. 2021 ) , and social network analysis ( Hevapathige, Wang, and Zehmakan 2025 ; Hevapathige, Wijesinghe, and Zehmakan 2025 ; Dehkordi and Zehmakan 2025 ) . While powerful, these architectures face inherent challenges, such as oversmoothing, a phenomenon in which network propagation results in indistinguishable node embeddings ( Oono and Suzuki 2020 ) . This phenomenon may even occur in shallow networks ( Wu et al. 2022 ) . A common strategy to mitigate oversmoothing in GNNs is the use of residual connections ( Gasteiger, Bojchevski, and Günnemann 2019 ; Huang and Carley 2019 ; Chen et al. 2020b ) , a technique that adds the input from the previous layers to the aggregated neighbor information (e.g., through summation or concatenation) to preserve information across layers. This approach has been shown to improve training and performance in deep learning architectures such as ResNets ( He et al. 2016 ) . Residual connections may combine the current embeddings with the initial node embeddings, forming initial residual connections (IRC). More generally, they may combine the current embeddings with the outputs from previous layers, which we refer to as residual connections (RC). In this work, we focus on IRC. Earlier works on IRC typically treat the residual strengths as a fixed hyperparameter shared across all nodes, referred to as static IRC for simplicity (see, e.g., ( Chen et al. 2020b ; Scholkemper et al. 2025 ) ). To further unlock the power of IRC, some research has considered a more dynamic and adaptive approach, cf. ( Zhang et al. 2023 ) . Following this line of work, in this paper, we study the adaptive IRC , in which each node is permitted to have a personalized residual strength. Our primary goal is to theoretically and experimentally investigate the ability of adaptive IRC to preserve feature information across layers and achieve superior accuracy in downstream tasks. To assess whether a message passing mechanism retains the ability to distinguish node embeddings as the network depth increases, a popular choice is the rank of the node embedding matrix ( Daneshmand et al. 2020 ) . A higher rank indicates that the message passing mechanism preserves distinct information across nodes, enabling richer representations. However, we note that rank alone is insufficient to diagnose oversmoothing, even in oversmoothing regimes, because numerical rank may remain full due to infinitesimal differences (though the effective rank collapses). For a more reliable diagnosis, effective rank or energy decay of the embedding matrix must be used to complement standard rank analysis. Hence, we also use the Dirichlet energy (see mean average distance ( Chen et al. 2020a ) , spectral rank ( Zhang et al. 2025 ) , and normalized node similarities ( Chen et al. 2025 ) for alternative equivalent measures), which quantifies the smoothness of node embeddings. If it decays to zero with depth, the embeddings become indistinguishable, indicating a loss of expressiveness. Conversely, bounded energy implies that the mechanism maintains discriminative power. Unlike rank, energy is a continuous quantifier ( Horn and Johnson 2012 ) , making it robust for tracking the degree of smoothing. Now that our message passing mechanism and our measures of oversmoothing are established, we can summarize our main contributions as follows: • Theoretical Guarantee : We provide a theoretical analysis demonstrating that the adaptive IRC framework avoids oversmoothing, even in deep architectures. Specifically, we show that the Dirichlet energy of the node embeddings in the adaptive IRC remains bounded away from zero, ensuring that the embeddings retain their discriminative power. As a special case, we prove that static IRC with activation functions mitigates oversmoothing, extending the result of the prior work ( Scholkemper et al. 2025 ) , which considered only the linear case without activation functions. We also prove that, through the aggregation process, in the adaptive IRC mechanism, the rank of the embedding matrix is fully preserved. • Enhanced GNN Performance : Through extensive experiments on benchmark datasets, we demonstrate that our framework consistently outperforms state-of-the-art GNNs. Our results highlight the framework’s ability to learn robust and discriminative node embeddings while maintaining scalability, as the node-specific residual strength can be efficiently learned during training. • Adaptive IRC with Non-learnable Residual Strengths : To reduce the time complexity of our approach, we propose a variant of adaptive IRC where residual strengths are not learned, but instead assigned heuristically based on node centrality. In particular, we use PageRank scores to rank the nodes, assigning a higher fixed residual strength to a small fraction of top-ranked nodes and a lower fixed value to the rest. This simple PageRank-based strategy performs as well as the fully learnable variant while significantly reducing computational overhead. Preliminaries Let G=(V,E,\mathbf{A}) be an undirected weighted graph with a node set V of cardinality |V|=n , an edge set E , and a weight matrix \mathbf{A}\in\mathbb{R}^{n\times n} where [\mathbf{A}]_{ij}=a_{ij} represents the weight of the edge between nodes i and j . If no edge exists between nodes i and j , a_{ij}=0 . The node set is equal to V=\{1,2,\cdots,n\} , and the one-hop neighborhood of node i is denoted as N_{i}=\{j\in V\mid(i,j)\in E\} . Each node is associated with a feature vector of size 1\times