Graph Neural Networks Exponentially Lose Expressive Power for Node Classification

By Kenta Oono, Taiji Suzuki. International Conference on Learning Representations, 2019

917 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/4ce9c20642dce5eb7930966053a1e3da4ef617f2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Adaptive Universal Generalized PageRank Graph Neural Network (2020, methodology): “This intuitive reasoning was first described for linear settings in Li et al. (2018) and has been recently studied in Oono & Suzuki (2020) for a setting involving nonlinear rectifiers.”
Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks (2021, background): “When the nonlinearities in the vanilla GCN are removed, it reduces to a linear model called SGC [17], which has competitive performance and is widely used in theoretical analyses [6, 7].”
Recipe for a General, Powerful, Scalable Graph Transformer (2022, background): “, over-smoothing [44], over-squashing [1], and expressiveness bounds [57, 42], by allowing nodes to attend to all other nodes in a graph (global attention).”
GRAND: Graph Neural Diffusion (2021, background): “This is a feat hard to achieve otherwise due to feature oversmoothing (NT & Maehara, 2019; Oono & Suzuki, 2020) and bottlenecks (Alon & Ya-hav, 2021) – phenomena that are recognised as a common plight of most graph learning architectures.”
On the Bottleneck of Graph Neural Networks and its Practical Implications (2020, background): “…The over-smoothing phenomenon is related, but not identical, to over-squashing: node representations become indistinguishable and prediction performance severely degrades when the number of layers increases (Li et al., 2018; Klicpera et al., 2019; Wu et al., 2020; Oono and Suzuki, 2020).”
Towards Deeper Graph Neural Networks with Differentiable Group Normalization (2020, background): “It has been reported that, as the number of graph convolutional layers increases, all node representations over a graph will converge to indistinguishable vectors, and GNNs perform poorly in downstream applications [16, 17].”
A Survey on Oversmoothing in Graph Neural Networks (2023, background): “This is related to several issues impairing the performance of deep GNNs in realistic graph-learning settings: graph bottlenecks (Alon & Yahav, 2021), over-squashing (Topping et al., 2021; Deac et al., 2022), and over-smoothing (Li et al., 2018; Nt & Maehara, 2019; Oono & Suzuki, 2020).”
Beyond Low-frequency Information in Graph Convolutional Networks (2021, background): “Secondly, it is well established that the node representation will becomes indistinguishable when we always utilize low-pass filter, causing over-smoothing (Oono and Suzuki 2020).”
Graph Few-shot Class-incremental Learning (2021, background): “However, most of the existing work on node classification primarily focuses on a single task, where the model is tasked to classify the unlabeled nodes to a fixed set of classes [13, 16, 25, 51].”
Graph Contrastive Learning with Augmentations (2020, background): “The reasons behind the intriguing phenomena could be that most studied graph datasets, as shown in [12], are often limited in size and GNNs often have shallow architectures to avoid over-smoothing [13] or “information loss” [14].”
Simple and Deep Graph Convolutional Networks (2020, background): “• (Oono & Suzuki, 2020) theoretically proves that the node features of a K -layer GCNs will converge to a subspace and incur information loss.”
Implicit Graph Neural Networks (2020, background): “, 2020) and theoretical (Oono and Suzuki, 2020; Zhao and Akoglu, 2020) works follows on the over-smoothing phenomenon.”
Structure-Aware Transformer for Graph Representation Learning (2022, background): “These include the limited expressiveness of GNNs (Xu et al., 2019; Morris et al., 2019), as well as known problems such as over-smoothing (Li et al., 2018; 2019; Chen et al., 2020; Oono & Suzuki, 2020) and oversquashing (Alon & Yahav, 2021).”
Graph Random Neural Networks for Semi-Supervised Learning on Graphs (2020, background): “However, most existing GNNs inherently suffer from the limitations of over-smoothing [6, 23, 24, 30], non-robustness [48, 45], and weak-generalization when labeled nodes are scarce.”