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

Authors

  • Deli Chen Peking University
  • Yankai Lin Wechat Tencent
  • Wei Li Peking University
  • Peng Li Wechat Tencent
  • Jie Zhou Wechat Tencent
  • Xu Sun Peking University

DOI:

https://doi.org/10.1609/aaai.v34i04.5747

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.

Downloads

Published

2020-04-03

How to Cite

Chen, D., Lin, Y., Li, W., Li, P., Zhou, J., & Sun, X. (2020). Measuring and Relieving the Over-Smoothing Problem for Graph Neural Networks from the Topological View. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04), 3438-3445. https://doi.org/10.1609/aaai.v34i04.5747

Issue

Section

AAAI Technical Track: Machine Learning