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

By Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, Xu Sun. AAAI Conference on Artificial Intelligence, 2019

1,424 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/94194703e83b5447f519fd8bcbb903916e05aaf9

How researchers see this paper

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

In Artificial Intelligence

1. Xiangnan He
2. Philip S. Yu
3. Qiang Liu
4. Xia Hu
5. Hongzhi Yin
6. Uri Alon
7. Jie Tang
8. Shuiwang Ji

Citations in the corpus

• Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks (2021, methodology): “For the baselines that have multiple variants (Geom-GCN, GCNII, H2GCN), we 1(Pei et al., 2019) claims that the ratios are 60%/20%/20%, which is different from the actual data splits shared on GitHub.”
• Principal Neighbourhood Aggregation for Graph Nets (2020, methodology): “STD is not used in the GNN literature.”
• LightGCL: Simple Yet Effective Graph Contrastive Learning for Recommendation (2023, methodology): “GNN-based Collaborative Filtering: • GCCF (Chen et al., 2020c) strengthens the GNN-based collaborative filtering by implementing a residual network and reducing the non-linear transformation.”
• Graph Random Neural Networks for Semi-Supervised Learning on Graphs (2020, methodology): “However, recent studies show that such propagation procedure brings some inherent issues: First, most GNNs suffer from over-smoothing [23, 6, 24, 30].”
• Data Augmentation for Graph Neural Networks (2020, methodology): “…and GAUG-O (original-graph) performance with that achieved by standard GNN performance, as well as three state-of-the-art baselines: ADAEDGE (Chen et al. 2019) (modified-graph), BGCN (Zhang et al. 2019b) (modified-graph), and DROPEDGE (Rong et al. 2019) (original-graph) evaluating on Gm and…”
• Representing Long-Range Context for Graph Neural Networks with Global Attention (2022, background): “Often, “too deep” GNNs lead to node representations that collapse to be equivalent over the entire graph, a phenomenon sometimes called oversmoothing or oversquashing [21, 5, 2].”
• XSimGCL: Towards Extremely Simple Graph Contrastive Learning for Recommendation (2022, background): “We hypothesize that two issues cause this biased distribution: a fraction of items often account for most interactions in recommender systems [34], and the notorious over-smoothing problem [35] that makes embed-dings locally similar, thus aggravating the Matthew Effect.”
• Structure-Aware Transformer for Graph Representation Learning (2022, background): “, 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).”
• A Survey of Graph Neural Networks for Recommender Systems: Challenges, Methods, and Directions (2021, background): “5.1.1 Deeper GNN. Due to the over-smoothing problem, more and more studies focus on properly increasing GNN’s layers to capture higher-order connectivity correlations on graphs as well as improve models’ performance [20, 88, 150, 251].”
• Improve Vision Transformers Training by Suppressing Over-smoothing (2021, methodology): “Similar approaches have also been adopted for training improved representations in graph neural networks (Chen et al., 2020) and diversified word embeddings in language models (Gao et al., 2019).”
• SaProt: Protein Language Modeling with Structure-aware Vocabulary (2024, methodology): “(2)Prior work employs GNNs for protein structure modeling, but GNNs suffer from the over-smoothing issue (Huang et al., 2021; Chen et al., 2020), thereby hindering large and deep protein model development.”
• Language is All a Graph Needs (2023, methodology): “This operation also resembles graph regularization techniques like DropEdge (Rong et al., 2019) for preventing over-smoothing (Chen et al., 2020a).”
• On the Bottleneck of Graph Neural Networks and its Practical Implications (2020, positive): “Several approaches were proposed to mitigate over-smoothing, such as normalization (Zhao and Akoglu, 2020), edge-based dropout (Rong et al., 2020), and noise-reduction regularization (Chen et al., 2020).”
• Hypergraph Contrastive Collaborative Filtering (2022, methodology): “Furthermore, to transform users and items into the latent embeddings, Autoencoder has been utilized as the embedding function with the behavior reconstruction objective, such as AutoRec [30] and CDAE [39].”
• RESDSQL: Decoupling Schema Linking and Skeleton Parsing for Text-to-SQL (2023, background): “However, compared to PLMs, graph neural networks (GNNs) usually cannot be designed too deep due to the limitation of the over-smoothing issue (Chen et al. 2020), which restricts the representation ability of GNNs.”
• Enhancing Graph Neural Network-based Fraud Detectors against Camouflaged Fraudsters (2020, background): “Meanwhile, theoretical studies prove the limitations and vulnerabilities of GNNs when graphs have noisy nodes and edges [3, 4, 13, 33].”
• Towards Deeper Graph Neural Networks with Differentiable Group Normalization (2020, methodology): “One of the general solutions is to train GNN models regularized by the pair distance [18].”
• Towards Deeper Graph Neural Networks (2020, background): “Several studies [3, 15] attribute this performance degradation phenomenon to the over-smoothing issue.”