  Increasing the depth of GCN, which is expected to permit more expressivity,
is shown to incur performance detriment especially on node classification. The
main cause of this lies in over-smoothing. The over-smoothing issue drives the
output of GCN towards a space that contains limited distinguished information
among nodes, leading to poor expressivity. Several works on refining the
architecture of deep GCN have been proposed, but it is still unknown in theory
whether or not these refinements are able to relieve over-smoothing. In this
paper, we first theoretically analyze how general GCNs act with the increase in
depth, including generic GCN, GCN with bias, ResGCN, and APPNP. We find that
all these models are characterized by a universal process: all nodes converging
to a cuboid. Upon this theorem, we propose DropEdge to alleviate over-smoothing
by randomly removing a certain number of edges at each training epoch.
Theoretically, DropEdge either reduces the convergence speed of over-smoothing
or relieves the information loss caused by dimension collapse. Experimental
evaluations on simulated dataset have visualized the difference in
over-smoothing between different GCNs. Moreover, extensive experiments on
several real benchmarks support that DropEdge consistently improves the
performance on a variety of both shallow and deep GCNs.
