Measuring and Relieving the Over-Smoothing Problem for Graph Neural Networks from the Topological View

TLDR

Graph Neural Networks achieve strong performance on many graph tasks, yet they suffer from over‑smoothing, where node representations become indistinguishable across classes. The authors conduct a systematic, quantitative investigation of the over‑smoothing problem in GNNs. They introduce MAD and MADGap metrics to quantify smoothness, and propose MADReg and AdaEdge techniques to mitigate over‑smoothing via regularization and topology optimization. The study confirms that GNN smoothing arises from low information‑to‑noise ratios governed by graph topology, and shows that MADReg and AdaEdge substantially reduce over‑smoothing and improve performance across seven datasets and ten GNN models.

Abstract

Graph Neural Networks (GNNs) have achieved promising performance on a wide range of graph-based tasks. Despite their success, one severe limitation of GNNs is the over-smoothing issue (indistinguishable representations of nodes in different classes). In this work, we present a systematic and quantitative study on the over-smoothing issue of GNNs. First, we introduce two quantitative metrics, MAD and MADGap, to measure the smoothness and over-smoothness of the graph nodes representations, respectively. Then, we verify that smoothing is the nature of GNNs and the critical factor leading to over-smoothness is the low information-to-noise ratio of the message received by the nodes, which is partially determined by the graph topology. Finally, we propose two methods to alleviate the over-smoothing issue from the topological view: (1) MADReg which adds a MADGap-based regularizer to the training objective; (2) AdaEdge which optimizes the graph topology based on the model predictions. Extensive experiments on 7 widely-used graph datasets with 10 typical GNN models show that the two proposed methods are effective for relieving the over-smoothing issue, thus improving the performance of various GNN models.