A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks

• URL: http://arxiv.org/abs/2212.10701v1
• Date: Wed, 21 Dec 2022 00:33:59 GMT
• Title: A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks
• Authors: Xinyi Wu, Zhengdao Chen, William Wang, Ali Jadbabaie
• Abstract summary: We characterize the mechanism behind the phenomenon via a non-asymptotic analysis. We show that oversmoothing happens once the mixing effect starts to dominate the denoising effect. Our results suggest that while PPR mitigates oversmoothing at deeper layers, PPR-based architectures still achieve their best performance at a shallow depth.
• Score: 33.35609077417775
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A central challenge of building more powerful Graph Neural Networks (GNNs) is the oversmoothing phenomenon, where increasing the network depth leads to homogeneous node representations and thus worse classification performance. While previous works have only demonstrated that oversmoothing is inevitable when the number of graph convolutions tends to infinity, in this paper, we precisely characterize the mechanism behind the phenomenon via a non-asymptotic analysis. Specifically, we distinguish between two different effects when applying graph convolutions -- an undesirable mixing effect that homogenizes node representations in different classes, and a desirable denoising effect that homogenizes node representations in the same class. By quantifying these two effects on random graphs sampled from the Contextual Stochastic Block Model (CSBM), we show that oversmoothing happens once the mixing effect starts to dominate the denoising effect, and the number of layers required for this transition is $O(\log N/\log (\log N))$ for sufficiently dense graphs with $N$ nodes. We also extend our analysis to study the effects of Personalized PageRank (PPR) on oversmoothing. Our results suggest that while PPR mitigates oversmoothing at deeper layers, PPR-based architectures still achieve their best performance at a shallow depth and are outperformed by the graph convolution approach on certain graphs. Finally, we support our theoretical results with numerical experiments, which further suggest that the oversmoothing phenomenon observed in practice may be exacerbated by the difficulty of optimizing deep GNN models.

Related papers

• Unifying over-smoothing and over-squashing in graph neural networks: A physics informed approach and beyond [45.370565281567984]
  Graph Neural Networks (GNNs) have emerged as one of the leading approaches for machine learning on graph-structured data. critical computational challenges such as over-smoothing, over-squashing, and limited expressive power continue to impact the performance of GNNs. We introduce the Multi-Scaled Heat Kernel based GNN (MHKG) by amalgamating diverse filtering functions' effects on node features.
  arXiv  Detail & Related papers  (2023-09-06T06:22:18Z)
• Explaining and Adapting Graph Conditional Shift [28.532526595793364]
  Graph Neural Networks (GNNs) have shown remarkable performance on graph-structured data. Recent empirical studies suggest that GNNs are very susceptible to distribution shift.
  arXiv  Detail & Related papers  (2023-06-05T21:17:48Z)
• Dynamic Causal Explanation Based Diffusion-Variational Graph Neural Network for Spatio-temporal Forecasting [60.03169701753824]
  We propose a novel Dynamic Diffusion-al Graph Neural Network (DVGNN) fortemporal forecasting. The proposed DVGNN model outperforms state-of-the-art approaches and achieves outstanding Root Mean Squared Error result.
  arXiv  Detail & Related papers  (2023-05-16T11:38:19Z)
• Addressing Heterophily in Node Classification with Graph Echo State Networks [11.52174067809364]
  We address the challenges of heterophilic graphs with Graph Echo State Network (GESN) for node classification. GESN is a reservoir computing model for graphs, where node embeddings are computed by an untrained message-passing function. Our experiments show that reservoir models are able to achieve better or comparable accuracy with respect to most fully trained deep models.
  arXiv  Detail & Related papers  (2023-05-14T19:42:31Z)
• Resisting Graph Adversarial Attack via Cooperative Homophilous Augmentation [60.50994154879244]
  Recent studies show that Graph Neural Networks are vulnerable and easily fooled by small perturbations. In this work, we focus on the emerging but critical attack, namely, Graph Injection Attack. We propose a general defense framework CHAGNN against GIA through cooperative homophilous augmentation of graph data and model.
  arXiv  Detail & Related papers  (2022-11-15T11:44:31Z)
• Effects of Graph Convolutions in Deep Networks [8.937905773981702]
  We present a rigorous theoretical understanding of the effects of graph convolutions in multi-layer networks. We show that a single graph convolution expands the regime of the distance between the means where multi-layer networks can classify the data. We provide both theoretical and empirical insights into the performance of graph convolutions placed in different combinations among the layers of a network.
  arXiv  Detail & Related papers  (2022-04-20T08:24:43Z)
• SkipNode: On Alleviating Performance Degradation for Deep Graph Convolutional Networks [84.30721808557871]
  We conduct theoretical and experimental analysis to explore the fundamental causes of performance degradation in deep GCNs. We propose a simple yet effective plug-and-play module, Skipnode, to overcome the performance degradation of deep GCNs.
  arXiv  Detail & Related papers  (2021-12-22T02:18:31Z)
• Unrolling of Deep Graph Total Variation for Image Denoising [106.93258903150702]
  In this paper, we combine classical graph signal filtering with deep feature learning into a competitive hybrid design. We employ interpretable analytical low-pass graph filters and employ 80% fewer network parameters than state-of-the-art DL denoising scheme DnCNN.
  arXiv  Detail & Related papers  (2020-10-21T20:04:22Z)
• Towards Deeper Graph Neural Networks [63.46470695525957]
  Graph convolutions perform neighborhood aggregation and represent one of the most important graph operations. Several recent studies attribute this performance deterioration to the over-smoothing issue. We propose Deep Adaptive Graph Neural Network (DAGNN) to adaptively incorporate information from large receptive fields.
  arXiv  Detail & Related papers  (2020-07-18T01:11:14Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  Graph representation learning has achieved a remarkable success in many graph-based applications, such as node classification, prediction, and community detection. However, for some kind of graph applications, such as graph compression and edge partition, it is very hard to reduce them to some graph representation learning tasks. In this paper, we propose to attack the graph ordering problem behind such applications by a novel learning approach.
  arXiv  Detail & Related papers  (2020-01-18T09:14:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.