Beyond Over-smoothing: Uncovering the Trainability Challenges in Deep Graph Neural Networks
This addresses the performance degradation problem in deep GNNs for researchers and practitioners, offering a new theoretical perspective that is incremental but clarifies misconceptions.
The paper identifies that the main challenge in deep Graph Neural Networks (GNNs) is not over-smoothing but the trainability issues of deep MLPs, and shows that constraining gradient flow bounds improves GNN performance across diverse datasets.
The drastic performance degradation of Graph Neural Networks (GNNs) as the depth of the graph propagation layers exceeds 8-10 is widely attributed to a phenomenon of Over-smoothing. Although recent research suggests that Over-smoothing may not be the dominant reason for such a performance degradation, they have not provided rigorous analysis from a theoretical view, which warrants further investigation. In this paper, we systematically analyze the real dominant problem in deep GNNs and identify the issues that these GNNs towards addressing Over-smoothing essentially work on via empirical experiments and theoretical gradient analysis. We theoretically prove that the difficult training problem of deep MLPs is actually the main challenge, and various existing methods that supposedly tackle Over-smoothing actually improve the trainability of MLPs, which is the main reason for their performance gains. Our further investigation into trainability issues reveals that properly constrained smaller upper bounds of gradient flow notably enhance the trainability of GNNs. Experimental results on diverse datasets demonstrate consistency between our theoretical findings and empirical evidence. Our analysis provides new insights in constructing deep graph models.