On the Complexity of Optimal Graph Rewiring for Oversmoothing and Oversquashing in Graph Neural Networks

• URL: http://arxiv.org/abs/2603.26140v1
• Date: Fri, 27 Mar 2026 07:50:42 GMT
• Title: On the Complexity of Optimal Graph Rewiring for Oversmoothing and Oversquashing in Graph Neural Networks
• Abstract summary: Graph Neural Networks (GNNs) face two fundamental challenges when scaled to deep architectures.<n>Oversmoothing and oversquashing are intimately tied to the underlying graph structure.<n>This paper provides a theoretical investigation of the computational complexity of such graph structure optimization.
• Score: 2.8427946758947304
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph Neural Networks (GNNs) face two fundamental challenges when scaled to deep architectures: oversmoothing, where node representations converge to indistinguishable vectors, and oversquashing, where information from distant nodes fails to propagate through bottlenecks. Both phenomena are intimately tied to the underlying graph structure, raising a natural question: can we optimize the graph topology to mitigate these issues? This paper provides a theoretical investigation of the computational complexity of such graph structure optimization. We formulate oversmoothing and oversquashing mitigation as graph optimization problems based on spectral gap and conductance, respectively. We prove that exact optimization for either problem is NP-hard through reductions from Minimum Bisection, establishing NP-completeness of the decision versions. Our results provide theoretical foundations for understanding the fundamental limits of graph rewiring for GNN optimization and justify the use of approximation algorithms and heuristic methods in practice.

Related papers

• Emergent Problem-Graph Alignment in RL-Discovered Entanglement Topologies for QAOA [3.03715087930992]
  We investigate whether a reinforcement learning agent can discover more effective entanglement topologies for QAOA-based MaxCut optimization without direct access to the problem graph.<n>Our results reveal a trainability--express trade-off governed by topology density and suggest that the variational optimization landscape implicitly encodes structural information about the problem Hamiltonian.
  arXiv  Detail & Related papers  (2026-08-07T18:17:08Z)
• Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle [56.92868481531399]
  We propose a non-selfishness principle that prioritizes the collective interference of neighborhood in coarsening.<n>We derive a faster variant NOPE*, which reduces O(dot d) interference evaluation to O(d) based on the local isotropy assumption.<n>Learning on coarsened graphs yields comparable performance to original graphs, and can even show superior performance over LLM-based graph reasoning.
  arXiv  Detail & Related papers  (2026-05-13T05:24:35Z)
• GADPN: Graph Adaptive Denoising and Perturbation Networks via Singular Value Decomposition [6.24191713518868]
  GADPN is a graph structure learning framework that adaptively refines graph topology via low-rank denoising and generalized structural perturbation.<n>It achieves state-of-the-art performance while significantly improving efficiency.<n>It shows particularly strong gains on challenging disassortative graphs, validating its ability to robustly learn enhanced graph structures.
  arXiv  Detail & Related papers  (2026-01-13T05:25:32Z)
• A Spectral Interpretation of Redundancy in a Graph Reservoir [51.40366905583043]
  This work revisits the definition of the reservoir in the Multiresolution Reservoir Graph Neural Network (MRGNN)<n>It proposes a variant based on a Fairing algorithm originally introduced in the field of surface design in computer graphics.<n>The core contribution of the paper lies in the theoretical analysis of the algorithm from a random walks perspective.
  arXiv  Detail & Related papers  (2025-07-17T10:02:57Z)
• Statistical physics analysis of graph neural networks: Approaching optimality in the contextual stochastic block model [0.0]
  Graph neural networks (GNNs) are designed to process data associated with graphs.<n>GNNs can encounter difficulties in gathering information from nodes far apart by iterated aggregation steps.<n>We show how the architecture of the GCN has to scale with the depth to avoid oversmoothing.
  arXiv  Detail & Related papers  (2025-03-03T09:55:10Z)
• Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
  The ubiquity of large-scale graphs in node-classification tasks hinders the real-world applications of Graph Neural Networks (GNNs) This paper studies graph coresets for GNNs and avoids the interdependence issue by selecting ego-graphs based on their spectral embeddings. Our spectral greedy graph coreset (SGGC) scales to graphs with millions of nodes, obviates the need for model pre-training, and applies to low-homophily graphs.
  arXiv  Detail & Related papers  (2024-05-27T17:52:12Z)
• Robust Graph Neural Network based on Graph Denoising [10.564653734218755]
  Graph Neural Networks (GNNs) have emerged as a notorious alternative to address learning problems dealing with non-Euclidean datasets. This work proposes a robust implementation of GNNs that explicitly accounts for the presence of perturbations in the observed topology.
  arXiv  Detail & Related papers  (2023-12-11T17:43: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)
• Gradient scarcity with Bilevel Optimization for Graph Learning [0.0]
  gradient scarcity occurs when learning graphs by minimizing a loss on a subset of nodes causes edges between unlabelled nodes that are far from labelled ones to receive zero gradients. We give a precise mathematical characterization of this phenomenon, and prove it also emerges in bilevel optimization. To alleviate this issue, we study several solutions: we propose to resort to latent graph learning using a Graph-to-Graph model (G2G), graph regularization to impose a prior structure on the graph, or optimizing on a larger graph than the original one with a reduced diameter.
  arXiv  Detail & Related papers  (2023-03-24T12:37:43Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  We propose a graph gradual pruning framework termed CGP to dynamically prune GNNs. Unlike LTH-based methods, the proposed CGP approach requires no re-training, which significantly reduces the computation costs. Our proposed strategy greatly improves both training and inference efficiency while matching or even exceeding the accuracy of existing methods.
  arXiv  Detail & Related papers  (2022-07-18T14:23:31Z)
• 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)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)

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.