Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvature

• URL: http://arxiv.org/abs/2309.09384v3
• Date: Tue, 19 Mar 2024 20:11:25 GMT
• Title: Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvature
• Authors: Lukas Fesser, Melanie Weber,
• Abstract summary: We propose a rewiring technique based on Augmented Forman-Ricci curvature (AFRC), a scalable curvature notation. We prove that AFRC effectively characterizes over-smoothing and over-squashing effects in message-passing GNNs.
• Score: 1.1126342180866644
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While Graph Neural Networks (GNNs) have been successfully leveraged for learning on graph-structured data across domains, several potential pitfalls have been described recently. Those include the inability to accurately leverage information encoded in long-range connections (over-squashing), as well as difficulties distinguishing the learned representations of nearby nodes with growing network depth (over-smoothing). An effective way to characterize both effects is discrete curvature: Long-range connections that underlie over-squashing effects have low curvature, whereas edges that contribute to over-smoothing have high curvature. This observation has given rise to rewiring techniques, which add or remove edges to mitigate over-smoothing and over-squashing. Several rewiring approaches utilizing graph characteristics, such as curvature or the spectrum of the graph Laplacian, have been proposed. However, existing methods, especially those based on curvature, often require expensive subroutines and careful hyperparameter tuning, which limits their applicability to large-scale graphs. Here we propose a rewiring technique based on Augmented Forman-Ricci curvature (AFRC), a scalable curvature notation, which can be computed in linear time. We prove that AFRC effectively characterizes over-smoothing and over-squashing effects in message-passing GNNs. We complement our theoretical results with experiments, which demonstrate that the proposed approach achieves state-of-the-art performance while significantly reducing the computational cost in comparison with other methods. Utilizing fundamental properties of discrete curvature, we propose effective heuristics for hyperparameters in curvature-based rewiring, which avoids expensive hyperparameter searches, further improving the scalability of the proposed approach.

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)
• Revisiting Edge Perturbation for Graph Neural Network in Graph Data Augmentation and Attack [58.440711902319855]
  Edge perturbation is a method to modify graph structures. It can be categorized into two veins based on their effects on the performance of graph neural networks (GNNs) We propose a unified formulation and establish a clear boundary between two categories of edge perturbation methods.
  arXiv  Detail & Related papers  (2024-03-10T15:50:04Z)
• Revealing Decurve Flows for Generalized Graph Propagation [108.80758541147418]
  This study addresses the limitations of the traditional analysis of message-passing, central to graph learning, by defining em textbfgeneralized propagation with directed and weighted graphs. We include a preliminary exploration of learned propagation patterns in datasets, a first in the field.
  arXiv  Detail & Related papers  (2024-02-13T14:13:17Z)
• DeepRicci: Self-supervised Graph Structure-Feature Co-Refinement for Alleviating Over-squashing [72.70197960100677]
  Graph Structure Learning (GSL) plays an important role in boosting Graph Neural Networks (GNNs) with a refined graph. GSL solutions usually focus on structure refinement with task-specific supervision (i.e., node classification) or overlook the inherent weakness of GNNs themselves. We propose to study self-supervised graph structure-feature co-refinement for effectively alleviating the issue of over-squashing in typical GNNs.
  arXiv  Detail & Related papers  (2024-01-23T14:06:08Z)
• Accelerating Scalable Graph Neural Network Inference with Node-Adaptive Propagation [80.227864832092]
  Graph neural networks (GNNs) have exhibited exceptional efficacy in a diverse array of applications. The sheer size of large-scale graphs presents a significant challenge to real-time inference with GNNs. We propose an online propagation framework and two novel node-adaptive propagation methods.
  arXiv  Detail & Related papers  (2023-10-17T05:03:00Z)
• Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature [11.592567773739411]
  Our study reveals the key connection between the local graph geometry and the occurrence of over-smoothing and over-squashing. We propose the Batch Ollivier-Ricci Flow, a novel rewiring algorithm capable of simultaneously addressing both over-smoothing and over-squashing.
  arXiv  Detail & Related papers  (2022-11-28T21:21:31Z)
• Efficient Graph Neural Network Inference at Large Scale [54.89457550773165]
  Graph neural networks (GNNs) have demonstrated excellent performance in a wide range of applications. Existing scalable GNNs leverage linear propagation to preprocess the features and accelerate the training and inference procedure. We propose a novel adaptive propagation order approach that generates the personalized propagation order for each node based on its topological information.
  arXiv  Detail & Related papers  (2022-11-01T14:38:18Z)
• Optimization-Induced Graph Implicit Nonlinear Diffusion [64.39772634635273]
  We propose a new kind of graph convolution variants, called Graph Implicit Diffusion (GIND) GIND implicitly has access to infinite hops of neighbors while adaptively aggregating features with nonlinear diffusion to prevent over-smoothing. We show that the learned representation can be formalized as the minimizer of an explicit convex optimization objective.
  arXiv  Detail & Related papers  (2022-06-29T06:26:42Z)
• Understanding over-squashing and bottlenecks on graphs via curvature [17.359098638324546]
  Over-squashing is a phenomenon where the number of $k$-hop neighbors grows rapidly with $k$. We introduce a new edge-based curvature and prove that negatively curved edges are responsible for over-squashing. We also propose and experimentally test a curvature-based rewiring method to alleviate the over-squashing.
  arXiv  Detail & Related papers  (2021-11-29T13:27:56Z)
• Improved Analysis of Clipping Algorithms for Non-convex Optimization [19.507750439784605]
  Recently, citetzhang 2019gradient show that clipped (stochastic) Gradient Descent (GD) converges faster than vanilla GD/SGD. Experiments confirm the superiority of clipping-based methods in deep learning tasks.
  arXiv  Detail & Related papers  (2020-10-05T14:36:59Z)

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.