A Note on Over-Smoothing for Graph Neural Networks

Abstract

Graph Neural Networks (GNNs) have achieved a lot of success on graph-structured data. However, it is observed that the performance of graph neural networks does not improve as the number of layers increases. This effect, known as over-smoothing, has been analyzed mostly in linear cases. In this paper, we build upon previous results \cite{oono2019graph} to further analyze the over-smoothing effect in the general graph neural network architecture. We show when the weight matrix satisfies the conditions determined by the spectrum of augmented normalized Laplacian, the Dirichlet energy of embeddings will converge to zero, resulting in the loss of discriminative power. Using Dirichlet energy to measure "expressiveness" of embedding is conceptually clean; it leads to simpler proofs than \cite{oono2019graph} and can handle more non-linearities.

Appeared at ICML 2020 Graph Representation Learning workshop. https://grlplus.github.io/cfp/

References in corpus (4)

• Semi-Supervised Classification with Graph Convolutional Networks
• Simplifying Graph Convolutional Networks
• Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning
• Network Representation Learning: Consolidation and Renewed Bearing

Cited by in corpus (7)

• Dirichlet Energy Constrained Learning for Deep Graph Neural Networks
• On Provable Benefits of Depth in Training Graph Convolutional Networks
• Evaluating Deep Graph Neural Networks
• Revisiting Graph Convolutional Network on Semi-Supervised Node Classification from an Optimization Perspective
• Stochastic Aggregation in Graph Neural Networks
• SoGCN: Second-Order Graph Convolutional Networks
• Graph Partner Neural Networks for Semi-Supervised Learning on Graphs