Spectral Graph Pruning Against Over-Squashing and Over-Smoothing

• URL: http://arxiv.org/abs/2404.04612v1
• Date: Sat, 6 Apr 2024 12:40:21 GMT
• Title: Spectral Graph Pruning Against Over-Squashing and Over-Smoothing
• Authors: Adarsh Jamadandi, Celia Rubio-Madrigal, Rebekka Burkholz,
• Abstract summary: We argue that deleting edges can address over-squashing and over-smoothing simultaneously. This explains how edge deletions can improve, thus connecting spectral gap optimization to a seemingly disconnected objective of reducing computational resources.
• Score: 14.947660746690614
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Message Passing Graph Neural Networks are known to suffer from two problems that are sometimes believed to be diametrically opposed: over-squashing and over-smoothing. The former results from topological bottlenecks that hamper the information flow from distant nodes and are mitigated by spectral gap maximization, primarily, by means of edge additions. However, such additions often promote over-smoothing that renders nodes of different classes less distinguishable. Inspired by the Braess phenomenon, we argue that deleting edges can address over-squashing and over-smoothing simultaneously. This insight explains how edge deletions can improve generalization, thus connecting spectral gap optimization to a seemingly disconnected objective of reducing computational resources by pruning graphs for lottery tickets. To this end, we propose a more effective spectral gap optimization framework to add or delete edges and demonstrate its effectiveness on large heterophilic datasets.

Related papers

• Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification [81.06278257153835]
  We propose a graph rewiring method that balances structural bottleneck reduction and graph property preservation.<n>Our method generates graphs with enhanced connectivity while maintaining sparsity and largely preserving the original graph spectrum.
  arXiv  Detail & Related papers  (2025-06-19T08:01:00Z)
• Oversmoothing as Loss of Sign: Towards Structural Balance in Graph Neural Networks [54.62268052283014]
  Oversmoothing is a common issue in graph neural networks (GNNs) Three major classes of anti-oversmoothing techniques can be mathematically interpreted as message passing over signed graphs. Negative edges can repel nodes to a certain extent, providing deeper insights into how these methods mitigate oversmoothing.
  arXiv  Detail & Related papers  (2025-02-17T03:25:36Z)
• Countering adversarial perturbations in graphs using error correcting codes [7.553245365626645]
  adversarial perturbations occur during the transmission of the graph between a sender and a receiver. This study explores a repetition coding scheme with sender-assigned noise and majority voting on the receiver's end to rectify the graph's structure.
  arXiv  Detail & Related papers  (2024-06-20T12:14:01Z)
• Bypassing Skip-Gram Negative Sampling: Dimension Regularization as a More Efficient Alternative for Graph Embeddings [8.858596502294471]
  We show that when repulsion is most needed and the embeddings approach collapse, SGNS node-wise repulsion is more scalable than node operations.<n>We propose a flexible algorithm augmentation framework that improves the scalability of any existing algorithm using SGNS.
  arXiv  Detail & Related papers  (2024-04-30T19:43:01Z)
• ADEdgeDrop: Adversarial Edge Dropping for Robust Graph Neural Networks [53.41164429486268]
  Graph Neural Networks (GNNs) have exhibited the powerful ability to gather graph-structured information from neighborhood nodes. The performance of GNNs is limited by poor generalization and fragile robustness caused by noisy and redundant graph data. We propose a novel adversarial edge-dropping method (ADEdgeDrop) that leverages an adversarial edge predictor guiding the removal of edges.
  arXiv  Detail & Related papers  (2024-03-14T08:31:39Z)
• 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)
• Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvature [1.1126342180866644]
  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.
  arXiv  Detail & Related papers  (2023-09-17T21:43:18Z)
• BOURNE: Bootstrapped Self-supervised Learning Framework for Unified Graph Anomaly Detection [50.26074811655596]
  We propose a novel unified graph anomaly detection framework based on bootstrapped self-supervised learning (named BOURNE) By swapping the context embeddings between nodes and edges, we enable the mutual detection of node and edge anomalies. BOURNE can eliminate the need for negative sampling, thereby enhancing its efficiency in handling large graphs.
  arXiv  Detail & Related papers  (2023-07-28T00:44:57Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph Matching [68.35685422301613]
  We propose a novel non-parametric subgraph matching framework, dubbed MatchExplainer, to explore explanatory subgraphs. It couples the target graph with other counterpart instances and identifies the most crucial joint substructure by minimizing the node corresponding-based distance. Experiments on synthetic and real-world datasets show the effectiveness of our MatchExplainer by outperforming all state-of-the-art parametric baselines with significant margins.
  arXiv  Detail & Related papers  (2023-01-07T05:14:45Z)
• FoSR: First-order spectral rewiring for addressing oversquashing in GNNs [0.0]
  Graph neural networks (GNNs) are able to leverage the structure of graph data by passing messages along the edges of the graph. We propose a computationally efficient algorithm that prevents oversquashing by systematically adding edges to the graph. We find experimentally that our algorithm outperforms existing graph rewiring methods in several graph classification tasks.
  arXiv  Detail & Related papers  (2022-10-21T07:58:03Z)
• SoftEdge: Regularizing Graph Classification with Random Soft Edges [18.165965620873745]
  Graph data augmentation plays a vital role in regularizing Graph Neural Networks (GNNs) Simple edge and node manipulations can create graphs with an identical structure or indistinguishable structures to message passing GNNs but of conflict labels. We propose SoftEdge, which assigns random weights to a portion of the edges of a given graph to construct dynamic neighborhoods over the graph.
  arXiv  Detail & Related papers  (2022-04-21T20:12:36Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  multilayer graph clustering aims at dividing the graph nodes into categories or communities. We propose a clustering-friendly embedding of the layers of a given multilayer graph. Experiments show that our method leads to a significant improvement.
  arXiv  Detail & Related papers  (2021-03-30T17:36:40Z)

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.