Adaptive Initial Residual Connections for GNNs with Theoretical Guarantees

• URL: http://arxiv.org/abs/2511.06598v1
• Date: Mon, 10 Nov 2025 01:08:37 GMT
• Title: Adaptive Initial Residual Connections for GNNs with Theoretical Guarantees
• Authors: Mohammad Shirzadi, Ali Safarpoor Dehkordi, Ahad N. Zehmakan,
• Abstract summary: We investigate an adaptive residual scheme in which different nodes have varying residual strengths.<n>We prove that this approach prevents oversmoothing; particularly, we show that the Dirichlet energy of the embeddings remains bounded away from zero.<n>This is the first theoretical guarantee not only for the adaptive setting, but also for static residual connections with activation functions.
• Score: 7.831509538890674
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• ANCRe: Adaptive Neural Connection Reassignment for Efficient Depth Scaling [57.91760520589592]
  Scaling network depth has been a central driver behind the success of modern foundation models.<n>This paper revisits the default mechanism for deepening neural networks, namely residual connections.<n>We introduce adaptive neural connection reassignment (ANCRe), a principled and lightweight framework that parameterizes and learns residual connectivities from the data.
  arXiv  Detail & Related papers  (2026-02-09T18:54:18Z)
• Optimal Depth of Neural Networks [2.1756081703276]
  This paper introduces a formal theoretical framework to address Determining the optimal depth of a neural network.<n>We model the layer-by-layer evolution of hidden representations as a sequential decision process.<n>We propose a novel and practical regularization term, $mathcalL_rm depth$, that encourages the network to learn representations amenable to efficient, early exiting.
  arXiv  Detail & Related papers  (2025-06-20T09:26:01Z)
• Residual Connections and Normalization Can Provably Prevent Oversmoothing in GNNs [30.003409099607204]
  We provide a formal and precise characterization of (linearized) graph neural networks (GNNs) with residual connections and normalization layers.<n>We show that the centering step of a normalization layer alters the graph signal in message-passing in such a way that relevant information can become harder to extract.<n>We introduce a novel, principled normalization layer called GraphNormv2 in which the centering step is learned such that it does not distort the original graph signal in an undesirable way.
  arXiv  Detail & Related papers  (2024-06-05T06:53:16Z)
• Deep Graph Neural Networks via Posteriori-Sampling-based Node-Adaptive Residual Module [65.81781176362848]
  Graph Neural Networks (GNNs) can learn from graph-structured data through neighborhood information aggregation. As the number of layers increases, node representations become indistinguishable, which is known as over-smoothing. We propose a textbfPosterior-Sampling-based, Node-distinguish Residual module (PSNR).
  arXiv  Detail & Related papers  (2023-05-09T12:03:42Z)
• Towards Practical Control of Singular Values of Convolutional Layers [65.25070864775793]
  Convolutional neural networks (CNNs) are easy to train, but their essential properties, such as generalization error and adversarial robustness, are hard to control. Recent research demonstrated that singular values of convolutional layers significantly affect such elusive properties. We offer a principled approach to alleviating constraints of the prior art at the expense of an insignificant reduction in layer expressivity.
  arXiv  Detail & Related papers  (2022-11-24T19:09:44Z)
• Universal Deep GNNs: Rethinking Residual Connection in GNNs from a Path Decomposition Perspective for Preventing the Over-smoothing [50.242926616772515]
  Recent studies have shown that GNNs with residual connections only slightly slow down the degeneration. In this paper, we investigate the forward and backward behavior of GNNs with residual connections from a novel path decomposition perspective. We present a Universal Deep GNNs framework with cold-start adaptive residual connections (DRIVE) and feedforward modules.
  arXiv  Detail & Related papers  (2022-05-30T14:19:45Z)
• Edge Rewiring Goes Neural: Boosting Network Resilience via Policy Gradient [62.660451283548724]
  ResiNet is a reinforcement learning framework to discover resilient network topologies against various disasters and attacks. We show that ResiNet achieves a near-optimal resilience gain on multiple graphs while balancing the utility, with a large margin compared to existing approaches.
  arXiv  Detail & Related papers  (2021-10-18T06:14:28Z)
• Layer Adaptive Node Selection in Bayesian Neural Networks: Statistical Guarantees and Implementation Details [0.5156484100374059]
  Sparse deep neural networks have proven to be efficient for predictive model building in large-scale studies. We propose a Bayesian sparse solution using spike-and-slab Gaussian priors to allow for node selection during training. We establish the fundamental result of variational posterior consistency together with the characterization of prior parameters.
  arXiv  Detail & Related papers  (2021-08-25T00:48:07Z)
• Non-Gradient Manifold Neural Network [79.44066256794187]
  Deep neural network (DNN) generally takes thousands of iterations to optimize via gradient descent. We propose a novel manifold neural network based on non-gradient optimization.
  arXiv  Detail & Related papers  (2021-06-15T06:39:13Z)
• Revisiting Initialization of Neural Networks [72.24615341588846]
  We propose a rigorous estimation of the global curvature of weights across layers by approximating and controlling the norm of their Hessian matrix. Our experiments on Word2Vec and the MNIST/CIFAR image classification tasks confirm that tracking the Hessian norm is a useful diagnostic tool.
  arXiv  Detail & Related papers  (2020-04-20T18:12:56Z)
• PushNet: Efficient and Adaptive Neural Message Passing [1.9121961872220468]
  Message passing neural networks have recently evolved into a state-of-the-art approach to representation learning on graphs. Existing methods perform synchronous message passing along all edges in multiple subsequent rounds. We consider a novel asynchronous message passing approach where information is pushed only along the most relevant edges until convergence.
  arXiv  Detail & Related papers  (2020-03-04T18:15:30Z)

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.