On the Complexity of Optimal Graph Rewiring for Oversmoothing and Oversquashing in Graph Neural Networks
Mostafa Haghir Chehreghani · 2026
Read On the Complexity of Optimal Graph Rewiring for Oversmoothing and Oversquashing in Graph Neural Networks by Mostafa Haghir Chehreghani (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-26140.txt.
Introduction
Haghir Chehreghani studies whether rewiring a graph can fix two deep network flaws in graph neural networks. Oversmoothing blurs node features together, while oversquashing blocks signals from far nodes. Both flaws trace back to the graph's shape. He casts the fixes as optimization over spectral gap and conductance. Exact optimization for either goal is NP-hard, he proves, by reduction from minimum bisection. The decision forms are NP-complete. The results justify the use of approximations and heuristics in practice.
Catalog record
| CREATOR | Mostafa Haghir Chehreghani |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 26837 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.26140
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Complexity of Optimal Graph Rewiring for Oversmoothing and Oversquashing in Graph Neural Networks Mostafa Haghir Chehreghani 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. Keywords: Graph Neural Networks, oversmoothing, oversquashing, graph rewiring, NP‑hardness, spectral graph theory. 1 Introduction Graph Neural Networks (GNNs) [ 14 , 23 , 25 , 19 ] have become the de facto standard for learning on graph-structured data, achieving remarkable success in applications ranging from fake news detection [ 15 , 16 ] to drug discovery [ 13 ] and recommendation systems [ 9 ] . Their core operation, message passing, aggregates information from neighboring nodes, allowing the model to capture relational structure. However, as GNNs are scaled to deeper architectures, they suffer from two fundamental limitations that severely restrict their expressive power and performance: oversmoothing and oversquashing. Oversmoothing occurs when repeated message passing causes node representations to converge to a uniform vector, erasing discriminative information [ 17 , 21 , 12 ] . This phenomenon arises because GNN layers act as low‑pass filters on the graph; after many layers, the features become dominated by the principal eigenvector of the propagation matrix. The rate of oversmoothing is governed by the spectral gap of the graph’s propagation operator, and it has been shown that for any graph with a fixed spectrum, oversmoothing is inevitable as the number of layers grows [ 21 , 12 ] . Consequently, many modern GNN architectures incorporate skip connections or normalization to mitigate the effect, but the underlying graph structure remains a key determinant. Oversquashing describes the failure of information from distant nodes to reach a given node due to bottlenecks in the graph [ 1 , 18 ] . When messages must flow through a narrow cut, the message‑passing process compresses exponentially many messages into fixed‑size vectors, leading to information loss. Oversquashing is fundamentally a structural phenomenon: it is quantified by the graph’s conductance or effective resistance [ 22 , 20 ] . A graph with a bottleneck forces information to be squashed, no matter how many layers are used. Crucially, both oversmoothing and oversquashing are determined by the underlying graph topology, yet they often conflict. Graphs that mitigate oversquashing — such as expanders or dense graphs — tend to have high connectivity, which accelerates oversmoothing. Conversely, sparse, tree‑like graphs resist oversmoothing but create severe bottlenecks that cause oversquashing. This tension raises a natural question: can we optimize the graph structure itself to strike an optimal balance between these two opposing forces? Recent works have explored graph rewiring as a practical tool to improve GNN performance. Heuristic methods such as DIGL [ 8 ] and SDRF [ 22 ] iteratively add or remove edges based on diffusion or curvature, demonstrating empirical success. However, the fundamental computational complexity of such graph optimization problems has remained unexplored. Is it possible to efficiently find a graph that optimally mitigates oversmoothing or oversquashing? Or are these problems inherently intractable, justifying the use of approximations and heuristics? 1.1 Contributions This paper provides the first theoretical investigation of the complexity of graph structure optimization for GNN oversmoothing and oversquashing mitigation. Our main contributions are as follows. 1. Unified Formulations: We cast the mitigation of oversmoothing and oversquashing as graph optimization problems with natural objective functions. For oversmoothing we use the second eigenvalue of the propagation matrix (equivalently the spectral gap of the normalized Laplacian). For oversquashing we use conductance, which captures the worst‑case bottleneck. 2. NP‑Hardness Results: We prove that exact optimization for either problem is NP‑hard. For oversquashing we give a reduction from Minimum Bisection to deciding whether a graph can be modified (by a limited number of edge additions/deletions) to achieve conductance above a threshold. For oversmoothing we give a similar reduction using spectral gap. In both cases we establish NP‑completeness of the decision versions. 3. Practical Implications: We analyze the complexity of existing heuristic rewiring methods such as SDRF and DIGL, showing that they run in polynomial time. Our hardness results therefore provide a theoretical justification for their use: since exact optimization is intractable, heuristic approaches are not only pragmatically necessary but also theoretically well‑founded. 1.2 Related Work This work sits at the intersection of graph neural network theory, graph structure optimization, and computational complexity. We review the most relevant strands of research below. Oversmoothing in GNNs. The oversmoothing phenomenon was first identified in the context of graph convolutional networks by [ 17 ] , who observed that stacking many layers leads to uniform node representations. [ 21 ] provided a spectral analysis showing that the convergence rate is governed by the second eigenvalue of the propagation matrix, and that oversmoothing is inevitable for any GNN that repeatedly applies a linear filter. Subsequent works proposed various mitigation strategies, such as residual connections [ 14 ] , normalization layers [ 10 ] , and adaptive propagation schemes [ 4 ] . From a spectral perspective, [ 24 ] linked oversmoothing to the graph’s spectral gap and showed that graph rewiring can delay the effect. Our work complements these by formalizing oversmoothing minimization as a graph optimization problem and proving its NP-hardness. Oversquashing and graph bottlenecks. The term “oversquashing” was introduced by [ 1 ] , who demonstrated that bottlenecks in the graph cause exponential compression of information in message passing. [ 22 ] used effective resistance to quantify oversquashing and proposed the SDRF algorithm that adds edges with high effective resistance and removes edges with negative curvature. [ 20 ] further analyzed oversquashing through the lens of Ollivier-Ricci curvature. These works established the importance of graph structure for mitigating oversquashing, but they did not explore the computational complexity of optimizing the graph itself. Our paper fills this gap by showing that even deciding whether a given graph can be improved to reduce oversquashing (as measured by conductance) is NP-hard. Graph rewiring and structure learning for GNNs. Several heuristics have been proposed to augment or rewire the graph for better GNN performance. DIGL [ 8 ] uses graph diffusion to densify the graph, while SDRF [ 22 ] iteratively applies discrete Ricci flow. [ 6 ] introduced a bilevel optimization framework for learning the graph structure end-to-end. These methods are empirically effective but lack theoretical guarantees on the hardness of the underlying optimization. Our complexity results justify the use of approximation algorithms and heuristics, because exact optimization is intractable. Complexity of graph optimization problems. Our reductions rely on the classical NP-complete problem Minimum