Effect of Cluster-based Sampling on the Over-smoothing Issue in Graph Neural Network

Graph neural networks (GNNs) are among the dominated approaches for learning graph structured data and are used in various applications such as social network or product recommendation. The GNN operates mainly on the message passing mechanism which a node receives related nodes information to improve its internal representation. However, when the depth of the GNN increases, the message passing mechanism cut-offs the high-frequency component of the nodes’ representation, thus leads to the over-smoothing issue. In this paper, we propose the usage of cluster-based sampling to reduce the smoothing effect of the high number of layers in GNN. Given each nodes is assigned to a specific region of the embedding space, the cluster-based sampling is expected to propagate this information to the node’s neighbour, thus improve the nodes’ expressivity. Our approach is tested with several popular GNN architecture and the experiments show that our approach could reduce the smoothing effect in comparison with the standard approaches using the Mean Average Distance metric.