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

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) AdaGraph 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.

Accepted by AAAI 2020. This complete version contains the appendix

References in corpus (8)

• Graph Neural Networks: A Review of Methods and Applications
• Fast Graph Representation Learning with PyTorch Geometric
• Pitfalls of Graph Neural Network Evaluation
• Predicting multicellular function through multi-layer tissue networks
• Graph Neural Networks with convolutional ARMA filters
• Revisiting Graph Neural Networks: All We Have is Low-Pass Filters
• Batch Virtual Adversarial Training for Graph Convolutional Networks
• Just Jump: Dynamic Neighborhood Aggregation in Graph Neural Networks

Cited by in corpus (9)

• DropMessage: Unifying Random Dropping for Graph Neural Networks
• Learning from the Dark: Boosting Graph Convolutional Neural Networks with Diverse Negative Samples
• A DRL-based Multiagent Cooperative Control Framework for CAV Networks: a Graphic Convolution Q Network
• Finite Volume Graph Network(FVGN): Predicting unsteady incompressible fluid dynamics with finite volume informed neural network
• Understanding and Resolving Performance Degradation in Graph Convolutional Networks
• Finite-difference-informed graph network for solving steady-state incompressible flows on block-structured grids
• Spectral Graph Attention Network with Fast Eigen-approximation
• Network representation learning: A macro and micro view
• Alleviating Over-Smoothing via Aggregation over Compact Manifolds