  The performance of GNNs degrades as they become deeper due to the
over-smoothing. Among all the attempts to prevent over-smoothing, residual
connection is one of the promising methods due to its simplicity. However,
recent studies have shown that GNNs with residual connections only slightly
slow down the degeneration. The reason why residual connections fail in GNNs is
still unknown. In this paper, we investigate the forward and backward behavior
of GNNs with residual connections from a novel path decomposition perspective.
We find that the recursive aggregation of the median length paths from the
binomial distribution of residual connection paths dominates output
representation, resulting in over-smoothing as GNNs go deeper. Entangled
propagation and weight matrices cause gradient smoothing and prevent GNNs with
residual connections from optimizing to the identity mapping. Based on these
findings, we present a Universal Deep GNNs (UDGNN) framework with cold-start
adaptive residual connections (DRIVE) and feedforward modules. Extensive
experiments demonstrate the effectiveness of our method, which achieves
state-of-the-art results over non-smooth heterophily datasets by simply
stacking standard GNNs.
