Inflation Improves Graph Neural Networks

Graph neural networks (GNNs) have gained significant success in graph representation learning and become the go-to approach for many graph-based tasks. Despite their effectiveness, the performance of GNNs is known to decline gradually as the number of layers increases. This attenuation is mainly caused by noise propagation, which refers to the useless or negative information propagated (directly or indirectly) from other nodes during the multi-layer graph convolution for node representation learning. This noise increases more severely as the layers of GNNs deepen, which is also a main reason of over-smoothing. In this paper, we propose a new convolution strategy for GNNs to address this problem via suppressing the noise propagation. Specifically, we first find that the feature propagation process of GNNs can be taken as a Markov chain. And then, based on the idea of Markov clustering, we introduce a new graph inflation layer (i.e., using a power function over the distribution) into GNNs to prevent noise propagating from local neighbourhoods to the whole graph with the increase of network layers. Our method is simple in design, which does not require any changes on the original basis and therefore can be easily extended. We conduct extensive experiments on real-world networks and have a stable improved performance as the network depth increases over existing GNNs.