Graph Elimination Networks
Shuo Wang Ge Cheng Yun Zhang
Graph Neural Networks (GNNs) are widely applied across various domains, yet
they perform poorly in deep layers. Existing research typically attributes this
problem to node over-smoothing, where node representations become
indistinguishable after multiple rounds of propagation. In this paper, we delve
into the neighborhood propagation mechanism of GNNs and discover that the real
root cause of GNNs' performance degradation in deep layers lies in ineffective
neighborhood feature propagation. This propagation leads to an exponential
growth of a node's current representation at every propagation step, making it
extremely challenging to capture valuable dependencies between long-distance
nodes. To address this issue, we introduce Graph Elimination Networks (GENs),
which employ a specific algorithm to eliminate redundancies during neighborhood
propagation. We demonstrate that GENs can enhance nodes' perception of distant
neighborhoods and extend the depth of network propagation. Extensive
experiments show that GENs outperform the state-of-the-art methods on various
graph-level and node-level datasets.