Efficient Approaches to Deal with Oversmoothing in Deep Graph Neural Networks

Abstract

Graph Neural Networks (GNNs) have achieved remarkable success in a wide range of tasks involving relational data, yet their performance deteriorates as depth increases due to the phenomenon known as oversmoothing, where node representations become indistinguishable across layers. This thesis presents a systematic investigation into the oversmoothing problem and proposes novel theoretical and empirical approaches for mitigating it, thus enabling deeper and more expressive GNN architectures. We first introduce a novel layer-wise metric to quantify oversmoothing, providing theoretical bounds and practical detection tools. We show that oversmoothing is exacerbated when the number of weight matrices is coupled with the depth of message passing, and propose G-Reg, a regularization strategy that preserves representational diversity. Next, we study residual connections and analyze their limitations in enabling long-range node interactions. Our analysis shows that while residual-based models (e.g., APPNP, GCNII) resist oversmoothing on standard benchmarks, they fail in settings requiring deep and expressive propagation. To highlight this, we introduce a synthetic dataset tailored to evaluate the capability of a GNN to capture long-range dependencies. We then explore partial training in GNNs, where only a single layer is trained while others remain fixed. Our results reveal that increasing model width counteracts the lack of full training and significantly reduces oversmoothing, even in deep architectures. This approach matches or outperforms fully trained models in both standard and “cold start” scenarios. Building on this, we propose G-Init, a graph informed weight initialization strategy inspired by classical deep learning initialization techniques. G-Init accounts for graph topology and improves gradient flow in deep GNNs, reducing oversmoothing and enhancing classification performance across tasks. Finally, we investigate the impact of the activation function on oversmoothing. Our theoretical and empirical findings demonstrate that modifying the slope of ReLU leads to better representational diversity and improved performance in deep GNNs, without employing architectural changes or residual connections. Together, these contributions advance our understanding of depth-related challenges in GNNs and offer multiple scalable, theoretically grounded solutions to overcome oversmoothing. The findings support a rethinking of GNN design principles and pave the way for more robust architectures suited to real-world problems.