Rewiring Techniques to Mitigate Oversquashing and Oversmoothing in GNNs: A Survey

• URL: http://arxiv.org/abs/2411.17429v1
• Date: Tue, 26 Nov 2024 13:38:12 GMT
• Title: Rewiring Techniques to Mitigate Oversquashing and Oversmoothing in GNNs: A Survey
• Authors: Hugo Attali, Davide Buscaldi, Nathalie Pernelle,
• Abstract summary: Graph Neural Networks (GNNs) are powerful tools for learning from graph-structured data, but their effectiveness is often constrained by two critical challenges. Oversquashing, where the excessive compression of information from distant nodes results in significant information loss, and oversmoothing, where repeated message-passing iterations homogenize node representations, obscuring meaningful distinctions. In this survey, we examine graph rewiring techniques, a class of methods designed to address these structural bottlenecks by modifying graph topology to enhance information diffusion.
• Score: 0.0
• License:
• Abstract: Graph Neural Networks (GNNs) are powerful tools for learning from graph-structured data, but their effectiveness is often constrained by two critical challenges: oversquashing, where the excessive compression of information from distant nodes results in significant information loss, and oversmoothing, where repeated message-passing iterations homogenize node representations, obscuring meaningful distinctions. These issues, intrinsically linked to the underlying graph structure, hinder information flow and constrain the expressiveness of GNNs. In this survey, we examine graph rewiring techniques, a class of methods designed to address these structural bottlenecks by modifying graph topology to enhance information diffusion. We provide a comprehensive review of state-of-the-art rewiring approaches, delving into their theoretical underpinnings, practical implementations, and performance trade-offs.

Related papers

• The Effectiveness of Curvature-Based Rewiring and the Role of Hyperparameters in GNNs Revisited [0.7373617024876725]
  Message passing is the dominant paradigm in Graph Neural Networks (GNNs) Recent efforts have focused on graph rewiring techniques, which disconnect the input graph originating from the data and the computational graph, on which message passing is performed. While oversquashing has been demonstrated in synthetic datasets, in this work we reevaluate the performance gains that curvature-based rewiring brings to real-world datasets.
  arXiv  Detail & Related papers  (2024-07-12T16:03:58Z)
• Over-Squashing in Graph Neural Networks: A Comprehensive survey [0.0]
  This survey delves into the challenge of over-squashing in Graph Neural Networks (GNNs) It comprehensively explores the causes, consequences, and mitigation strategies for over-squashing. Various methodologies are reviewed, including graph rewiring, novel normalization, spectral analysis, and curvature-based strategies. The survey also discusses the interplay between over-squashing and other GNN limitations, such as over-smoothing.
  arXiv  Detail & Related papers  (2023-08-29T18:46:15Z)
• Learning Strong Graph Neural Networks with Weak Information [64.64996100343602]
  We develop a principled approach to the problem of graph learning with weak information (GLWI) We propose D$2$PT, a dual-channel GNN framework that performs long-range information propagation on the input graph with incomplete structure, but also on a global graph that encodes global semantic similarities.
  arXiv  Detail & Related papers  (2023-05-29T04:51:09Z)
• DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
  We propose DEGREE to provide a faithful explanation for GNN predictions. By decomposing the information generation and aggregation mechanism of GNNs, DEGREE allows tracking the contributions of specific components of the input graph to the final prediction. We also design a subgraph level interpretation algorithm to reveal complex interactions between graph nodes that are overlooked by previous methods.
  arXiv  Detail & Related papers  (2023-05-22T10:29:52Z)
• EEGNN: Edge Enhanced Graph Neural Networks [1.0246596695310175]
  We propose a new explanation for such deteriorated performance phenomenon, mis-simplification. We show that such simplifying can reduce the potential of message-passing layers to capture the structural information of graphs. EEGNN uses the structural information extracted from the proposed Dirichlet mixture Poisson graph model to improve the performance of various deep message-passing GNNs.
  arXiv  Detail & Related papers  (2022-08-12T15:24:55Z)
• Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
  We propose a graph convolutional relationship between the observed and latent graphs, and formulate the graph learning task as a network inverse (deconvolution) problem. In lieu of eigendecomposition-based spectral methods, we unroll and truncate proximal gradient iterations to arrive at a parameterized neural network architecture that we call a Graph Deconvolution Network (GDN) GDNs can learn a distribution of graphs in a supervised fashion, perform link prediction or edge-weight regression tasks by adapting the loss function, and they are inherently inductive.
  arXiv  Detail & Related papers  (2022-05-19T14:08:15Z)
• Towards Unsupervised Deep Graph Structure Learning [67.58720734177325]
  We propose an unsupervised graph structure learning paradigm, where the learned graph topology is optimized by data itself without any external guidance. Specifically, we generate a learning target from the original data as an "anchor graph", and use a contrastive loss to maximize the agreement between the anchor graph and the learned graph.
  arXiv  Detail & Related papers  (2022-01-17T11:57:29Z)
• A Graph Data Augmentation Strategy with Entropy Preserving [11.886325179121226]
  We introduce a novel graph entropy definition as a quantitative index to evaluate feature information among a graph. Under considerations of preserving graph entropy, we propose an effective strategy to generate training data using a perturbed mechanism. Our proposed approach significantly enhances the robustness and generalization ability of GCNs during the training process.
  arXiv  Detail & Related papers  (2021-07-13T12:58:32Z)
• Information Obfuscation of Graph Neural Networks [96.8421624921384]
  We study the problem of protecting sensitive attributes by information obfuscation when learning with graph structured data. We propose a framework to locally filter out pre-determined sensitive attributes via adversarial training with the total variation and the Wasserstein distance.
  arXiv  Detail & Related papers  (2020-09-28T17:55:04Z)
• 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)

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.