Paper deep dive
On the Complexity of Optimal Graph Rewiring for Oversmoothing and Oversquashing in Graph Neural Networks
Mostafa Haghir Chehreghani
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 96%
Last extracted: 3/31/2026, 1:39:01 AM
Summary
This paper investigates the computational complexity of optimizing graph topology to mitigate oversmoothing and oversquashing in Graph Neural Networks (GNNs). The author formulates these mitigation tasks as graph optimization problems—specifically, maximizing the spectral gap for oversmoothing and maximizing conductance for oversquashing—and proves that both are NP-complete via reductions from the Minimum Bisection problem. These findings provide a theoretical foundation for the necessity of heuristic and approximation-based graph rewiring methods in GNN practice.
Entities (7)
Relation Signals (4)
Graph Rewiring → isnphard → Oversmoothing Mitigation
confidence 100% · We prove that exact optimization for either problem is NP-hard
Graph Rewiring → isnphard → Oversquashing Mitigation
confidence 100% · We prove that exact optimization for either problem is NP-hard
Oversmoothing → mitigatedby → Spectral Gap Optimization
confidence 90% · For oversmoothing we use the second eigenvalue of the propagation matrix (equivalently the spectral gap of the normalized Laplacian).
Oversquashing → mitigatedby → Conductance Optimization
confidence 90% · For oversquashing we use conductance, which captures the worst-case bottleneck.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2603.26140v1
- Canonical: https://arxiv.org/abs/2603.26140v1
Trouble viewing inline? Open PDF directly →
Full Text
33,711 characters extracted from source content.
Expand or collapse full text
On the Complexity of Optimal Graph Rewiring for Oversmoothing and Oversquashing in Graph Neural Networks Mostafa Haghir Chehreghani Department of Computer Engineering Amirkabir University of Technology (Tehran Polytechnic) Tehran, Iran mostafa.chehreghani@aut.ac.ir 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 Bisection [7]. Expander embeddings, which we use to relate graph cuts, are a standard tool in hardness of approximation [11, 3]. Our work extends these classic results to the specific objective functions arising from GNN analysis. In summary, while previous work has identified oversmoothing and oversquashing as critical limitations and proposed heuristic rewiring strategies, our paper is the first to provide a unified complexity analysis of the underlying graph optimization problems, establishing NP-hardness for natural formulations and justifying the use of approximations in practice. 2 Preliminaries 2.1 Basic Graph Notation Let G=(V,E)G=(V,E) be an undirected, unweighted graph with n=|V|n=|V| vertices and m=|E|m=|E| edges. Let A∈0,1n×nA∈\0,1\^n× n be the adjacency matrix, D=diag(d1,…,dn)D=diag(d_1,…,d_n) the degree matrix where dv=∑uAuvd_v= _uA_uv. Let L=D−AL=D-A denote the combinatorial Laplacian. 2.2 Spectral Graph Theory and Conductance The normalized Laplacian is defined as ℒ=I−D−1/2AD−1/2L=I-D^-1/2AD^-1/2. Its eigenvalues satisfy 0=λ1(ℒ)≤λ2(ℒ)≤⋯≤λn(ℒ)≤20= _1(L)≤ _2(L)≤·s≤ _n(L)≤ 2, and λ2(ℒ) _2(L) (the Fiedler value) measures the algebraic connectivity of the graph. For a GNN layer we use the symmetric normalized propagation matrix P=D~−1/2A~D~−1/2P= D^-1/2 A D^-1/2, where A~=A+I A=A+I and D~=D+I D=D+I. Its eigenvalues are 1=μ1(P)≥μ2(P)≥⋯≥μn(P)≥−11= _1(P)≥ _2(P)≥·s≥ _n(P)≥-1. For regular graphs, P=D−1/2AD−1/2P=D^-1/2AD^-1/2. Conductance (or Cheeger constant) is a classic measure of bottlenecks. For a subset S⊂VS⊂ V, define ∂S=(u,v)∈E:u∈S,v∉S∂ S=\(u,v)∈ E:u∈ S,v∉ S\ and vol(S)=∑v∈Sdeg(v)vol(S)= _v∈ S (v). The conductance of S is: ϕ(S)=|∂S|min(vol(S),vol(V∖S)),φ(S)= |∂ S| (vol(S),vol(V S)), and the conductance of G is: ϕ(G)=minS⊂V, 0<vol(S)≤vol(V)/2ϕ(S).φ(G)= _S⊂ V,\,0<vol(S) (V)/2φ(S). Cheeger’s inequality relates the spectral gap of the normalized Laplacian to the conductance: ϕ(G)22≤λ2(ℒ)≤2ϕ(G). φ(G)^22≤ _2(L)≤ 2φ(G). 3 Graph Rewiring for Oversquashing via Conductance 3.1 Problem Formulation The worst-case bottleneck is captured by the conductance ϕ(G)φ(G). Maximizing ϕ(G)φ(G) minimizes oversquashing: ℒsquash(cond)(G)=−ϕ(G).L_squash^(cond)(G)=-φ(G). Definition 1 (Graph Rewiring for Oversquashing via Conductance (GROC)). Given an undirected graph G=(V,E)G=(V,E), an integer K≥0K≥ 0, and a threshold ϕ0∈[0,1] _0∈[0,1], does there exist a graph G′=(V,E′)G =(V,E ) with |E′△E|≤K|E E|≤ K such that the conductance ϕ(G′)≥ϕ0φ(G )≥ _0? 3.2 Expander Embedding We need a construction that maps a graph H to a new graph G such that the conductance of G is small if and only if H has a small bisection. The following lemma provides such a construction; its proof is standard in hardness of approximation [3, 11]. Lemma 2 (Expander Embedding). There exists a polynomial‑time algorithm that, given a graph H=(V,EH)H=(V,E_H) with n vertices (assumed large enough, n≥n0n≥ n_0), outputs a 33-regular graph G=(V′,EG)G=(V ,E_G) with |V′|=2n|V |=2n and constants c1,c2>0c_1,c_2>0, c3∈(0,1)c_3∈(0,1) satisfying: 1. V⊂V′V⊂ V and H is an induced subgraph of G on V. 2. For any subset S⊆VS V with |S|≤n/2|S|≤ n/2, let U=V′∖VU=V V (so |U|=n|U|=n). Then the conductance of the cut (S∪U,V′∖(S∪U))(S∪ U,V (S∪ U)) in G satisfies ϕG(S∪U)≤c1⋅|δH(S)|+n. _G(S∪ U)≤ c_1· | _H(S)|+nn. 3. Conversely, if there exists a cut (X,V′∖X)(X,V X) in G with conductance ϕG(X)≤ϵ _G(X)≤ε, then there exists a subset S⊆VS V such that |δH(S)|≤c2⋅ϵn.| _H(S)|≤ c_2·ε n. Moreover, if ϵε is sufficiently small, S can be chosen to satisfy |S|=n/2|S|=n/2 after a polynomial‑time balancing procedure, and the number of crossing edges increases by at most a factor c3c_3. The constants c1,c2,c3c_1,c_2,c_3 can be made arbitrarily small (or large) by choosing a sufficiently strong (or weak) expander. We fix one such expander once and for all. Its constants c1,c2,c3c_1,c_2,c_3 are absolute numbers that we will use throughout. In the reductions we will need certain inequalities to hold; these can be satisfied by choosing the expander appropriately (e.g., a very strong expander makes c1c_1 and c2c_2 very small, and c3c_3 close to 11). We assume the expander is chosen so that: c1<16,c2c3<12,c3<1.c_1< 16, c_2c_3< 12, c_3<1. These are achievable by taking a sufficiently strong expander. 3.3 Pre‑processing Minimum Bisection Instances Before applying the embedding, we transform the Minimum Bisection instance to have convenient bounds on B relative to n. The following lemma provides explicit polynomial-time constructions. Lemma 3 (Instance Scaling). Let (H,B)(H,B) be a Minimum Bisection instance with n even. 1. There exists a polynomial-time construction of an equivalent instance (H1,B1)(H_1,B_1) with n1n_1 vertices such that B1≥2n1B_1≥ 2n_1 and B1=O(n1)B_1=O(n_1). 2. There exists a polynomial-time construction of an equivalent instance (H2,B2)(H_2,B_2) with n2n_2 vertices such that n2/2≤B2≤2n2n_2/2≤ B_2≤ 2n_2. In both cases, the construction preserves the answer (i.e., H has a bisection with ≤B≤ B edges iff the new instance does). The proof is by adding isolated vertices and universal vertices; details are omitted for brevity but follow standard techniques. 3.4 NP-Completeness of Conductance Maximization Theorem 4. GROC is NP-complete. Proof. Membership in NP: Given a candidate graph G′G , we can compute its conductance ϕ(G′)φ(G ) exactly by solving a min-cut problem (via max-flow) in polynomial time. Hence the decision problem is in NP. NP-hardness: We reduce from Minimum Bisection. Let (H,B)(H,B) be an instance with n even. First, if n is bounded by a constant, we solve the instance directly in constant time and output a trivial YES/NO instance of GROC. Otherwise, we use part 2 of Lemma 3 to transform (H,B)(H,B) into an equivalent instance (H0,B0)(H_0,B_0) with n0n_0 vertices such that n0/2≤B0≤2n0n_0/2≤ B_0≤ 2n_0. For simplicity, rename (H0,B0)(H_0,B_0) as (H,B)(H,B). Now construct the 33-regular graph G from Lemma 2. The constants satisfy c1<1/6c_1<1/6, c2c3<1/2c_2c_3<1/2, c3<1c_3<1. Set K=0K=0 (no edge modifications) and define ϕ0=1−c1⋅B+n. _0=1-c_1· B+nn. Because B≤2nB≤ 2n, we have (B+n)/n≤3(B+n)/n≤ 3, so ϕ0≥1−3c1 _0≥ 1-3c_1. With c1<1/6c_1<1/6, we get ϕ0>1/2 _0>1/2. We claim that H has a bisection with ≤B≤ B edges if and only if ϕ(G)<ϕ0φ(G)< _0 (i.e., (G,0,ϕ0)(G,0, _0) is a NO instance). The reduction then maps YES instances of Minimum Bisection to NO instances of GROC and vice versa; since GROC is a decision problem, we can invert the answer in polynomial time. Forward direction: Suppose H has a bisection S with |δH(S)|≤B| _H(S)|≤ B. By Lemma 2(2), the cut X=S∪UX=S∪ U (where U=V′∖VU=V V) satisfies ϕG(X)≤c1⋅|δH(S)|+n≤c1⋅B+n=1−ϕ0. _G(X)≤ c_1· | _H(S)|+nn≤ c_1· B+nn=1- _0. Since ϕ0>1/2 _0>1/2, we have 1−ϕ0<ϕ01- _0< _0, and therefore ϕ(G)≤ϕG(X)≤1−ϕ0<ϕ0φ(G)≤ _G(X)≤ 1- _0< _0. Thus ϕ(G)<ϕ0φ(G)< _0, so (G,0,ϕ0)(G,0, _0) is a NO instance. Reverse direction: Suppose H has no bisection with ≤B≤ B edges. Assume for contradiction that ϕ(G)<ϕ0φ(G)< _0. Then there exists a cut X in G with ϕG(X)<ϕ0 _G(X)< _0. By Lemma 2(3), there exists S⊆VS V such that |δH(S)|≤c2⋅ϕG(X)⋅n<c2ϕ0n.| _H(S)|≤ c_2· _G(X)· n<c_2 _0n. Applying the balancing procedure, we obtain a bisection S′S with |δH(S′)|≤c3⋅|δH(S)|<c3c2ϕ0n.| _H(S )|≤ c_3·| _H(S)|<c_3c_2 _0n. Because c2c3<1/2c_2c_3<1/2 and ϕ0<1 _0<1, we have c3c2ϕ0n<n/2c_3c_2 _0n<n/2. Since B≥n/2B≥ n/2, we get c3c2ϕ0n<Bc_3c_2 _0n<B. Hence |δH(S′)|<B| _H(S )|<B, contradicting the assumption that every bisection has width at least B+1B+1. Therefore our assumption ϕ(G)<ϕ0φ(G)< _0 is false, so ϕ(G)≥ϕ0φ(G)≥ _0, and (G,0,ϕ0)(G,0, _0) is a YES instance. Thus the reduction is correct. Since Minimum Bisection is NP-complete [7], GROC is NP-hard, and with membership in NP it is NP-complete. ∎ 4 Graph Rewiring for Oversmoothing 4.1 Spectral Formulation For a regular graph, the symmetric normalized propagation matrix P=D−1/2AD−1/2P=D^-1/2AD^-1/2 has eigenvalues 1=μ1(P)≥μ2(P)≥⋯≥μn(P)≥−11= _1(P)≥ _2(P)≥·s≥ _n(P)≥-1. The Dirichlet energy after L layers decays as ℰ(X(L))≤(μ2(P))2Lℰ(X(0))E(X^(L))≤( _2(P))^2LE(X^(0)). Thus, to prevent oversmoothing, we wish to minimize μ2(P) _2(P). Since μ2(P)=1−λ2(ℒ) _2(P)=1- _2(L), minimizing μ2(P) _2(P) is equivalent to maximizing λ2(ℒ) _2(L). Definition 5 (Graph Rewiring for Oversmoothing (GROS)). Given an undirected graph G=(V,E)G=(V,E), an integer K≥0K≥ 0, and a threshold τ∈[0,1]τ∈[0,1], does there exist a graph G′=(V,E′)G =(V,E ) with |E′△E|≤K|E E|≤ K such that μ2(PG′)≤τ _2(P_G )≤τ, where PG′P_G is the symmetric normalized propagation matrix? 4.2 NP-Completeness of Oversmoothing Minimization We use the same expander embedding as in the previous section, with constants chosen to satisfy c1<1/48c_1<1/48, 2c23c1<1/22c_2 3c_1<1/2, c3<1c_3<1. (These are compatible with the earlier conditions and can be achieved by a sufficiently strong expander.) Theorem 6. GROS is NP-complete. Proof. Membership in NP: A certificate is the target graph G′G . We verify |E′△E|≤K|E E|≤ K and μ2(PG′)≤τ _2(P_G )≤τ. The matrix PG′P_G has rational entries; its characteristic polynomial has integer coefficients. The eigenvalues are algebraic numbers whose bit‑length is polynomial in the input size. Using standard root isolation (e.g., Sturm sequences) we can decide whether the second largest eigenvalue (in absolute value) is at most a given rational τ in polynomial time [5]. Hence the problem is in NP. NP-hardness: We reduce from Minimum Bisection. Let (H,B)(H,B) be an instance with n even. Use part 1 of Lemma 3 to transform it into an equivalent instance (H0,B0)(H_0,B_0) with n0n_0 vertices such that B0≥2n0B_0≥ 2n_0 and B0=O(n0)B_0=O(n_0). (If the instance is small, we solve it directly in polynomial time; otherwise we proceed.) For simplicity, rename (H0,B0)(H_0,B_0) as (H,B)(H,B). Now construct the 33-regular graph G from Lemma 2 (with the fixed expander satisfying the constant conditions). Set K=0K=0 and define τ=1−2c1⋅B+n−ε,τ=1-2c_1· B+nn- , where ε is a small positive rational chosen so that τ is rational and ε<1−2c1(B+n)/n <1-2c_1(B+n)/n (which holds because the right‑hand side is positive; we can take ε=12(1−2c1(B+n)/n) = 12(1-2c_1(B+n)/n) after scaling). For the forward direction we will need that if H has a bisection ≤B≤ B, then μ2(PG)>τ _2(P_G)>τ; for the reverse direction, if H has no such bisection, then μ2(PG)≤τ _2(P_G)≤τ. Forward direction: If H has a bisection S with |δH(S)|≤B| _H(S)|≤ B, then by Lemma 2(2) there is a cut in G with conductance ϕG(S∪U)≤c1(B+n)/n _G(S∪ U)≤ c_1(B+n)/n. Cheeger gives λ2(ℒG)≤2c1(B+n)/n _2(L_G)≤ 2c_1(B+n)/n, so μ2(PG)=1−λ2(ℒG)≥1−2c1(B+n)/n. _2(P_G)=1- _2(L_G)≥ 1-2c_1(B+n)/n. Since τ=1−2c1(B+n)/n−ετ=1-2c_1(B+n)/n- and ε>0 >0, we have μ2(PG)>τ _2(P_G)>τ. Thus (G,0,τ)(G,0,τ) is a NO instance. Reverse direction: Suppose H has no bisection with ≤B≤ B edges. Assume μ2(PG)>τ _2(P_G)>τ. Then λ2(ℒG)<1−τ=2c1(B+n)/n+ε. _2(L_G)<1-τ=2c_1(B+n)/n+ . Let δ=2c1(B+n)/n+εδ=2c_1(B+n)/n+ . By Cheeger, there exists a cut X in G with ϕG(X)≤2λ2(ℒG)<2δ. _G(X)≤ 2 _2(L_G)< 2δ. We now bound 2δ 2δ. Since B≥2nB≥ 2n, we have (B+n)/n≤(B+B/2)/n=(3B)/(2n)(B+n)/n≤(B+B/2)/n=(3B)/(2n). Then δ≤2c1⋅3B2n+ε=3c1Bn+ε.δ≤ 2c_1· 3B2n+ = 3c_1Bn+ . For sufficiently small ε (we can choose ε≤c1B/n ≤ c_1B/n, for instance), we obtain 2δ≤6c1Bn+2ε≤8c1Bn=22c1B/n. 2δ≤ 6c_1Bn+2 ≤ 8c_1Bn=2 2c_1B/n. To simplify, we use the bound 2δ≤23c1B/n 2δ≤ 2 3c_1B/n (since 6c1B/n≤6c1B/n6c_1B/n≤ 6c_1B/n, and the extra 2ε2 can be absorbed into the constant by a slightly larger factor). More directly, we set ϵ=23c1B/nε=2 3c_1B/n; then for sufficiently small ε we have ϕG(X)<ϵ _G(X)<ε. Now apply Lemma 2(3) with ϵ=23c1B/nε=2 3c_1B/n. There exists S⊆VS V such that |δH(S)|≤c2ϵn=2c23c1Bn.| _H(S)|≤ c_2ε n=2c_2 3c_1Bn. Because 2c23c1<1/22c_2 3c_1<1/2, we have |δH(S)|<12Bn.| _H(S)|< 12 Bn. Since B≥2nB≥ 2n, we obtain |δH(S)|<122n2=n2| _H(S)|< 12 2n^2= n 2. Using B≥2nB≥ 2n, we also have |δH(S)|<B| _H(S)|<B (because n/2<2n/ 2<2n for n>0n>0). Applying the balancing procedure gives a bisection S′S with |δH(S′)|≤c3|δH(S)|<c3B| _H(S )|≤ c_3| _H(S)|<c_3B. Since c3<1c_3<1, we have |δH(S′)|<B| _H(S )|<B, contradicting the assumption that every bisection has width ≥B+1≥ B+1. Therefore μ2(PG)≤τ _2(P_G)≤τ, making (G,0,τ)(G,0,τ) a YES instance. Thus a polynomial algorithm for GROS would solve Minimum Bisection, proving NP-hardness. Since GROS is in NP, it is NP-complete. ∎ 5 Inapproximability and Practical Algorithms 5.1 Inapproximability Considerations The underlying graph properties we optimize are known to be hard to approximate: • Conductance ϕ(G)φ(G) cannot be approximated within a factor of O(logn)O( n) unless = P= NP [3]. • The spectral gap λ2(ℒ) _2(L) cannot be approximated within any constant factor for regular graphs [2]. These results suggest that any algorithm that attempts to optimize the graph structure to improve these measures (with a limited budget of edge changes) will also be hard to approximate, though a formal proof for the rewiring problems themselves remains open. Nevertheless, the NP‑hardness results already justify the use of heuristics. 5.2 Heuristic Algorithms Given the hardness results, practical approaches must resort to heuristics. Two widely used methods are SDRF [22] and DIGL [8]. They operate in polynomial time: • SDRF iteratively removes edges with most negative curvature and adds edges with highest effective resistance. Each iteration computes curvatures (via linear programming) and effective resistances (via matrix inversion or sampling) and runs in O~(n2) O(n^2) time. With O(n)O(n) iterations, total complexity is O~(n3) O(n^3). • DIGL uses graph diffusion to add edges based on personalized PageRank, running in O(n2logn)O(n^2 n). Our complexity results justify the use of such heuristics, showing that exact optimization is intractable and that approximation algorithms with guarantees are unlikely to exist. 6 Discussion The analysis presented in this paper reveals a fundamental duality between the two graph optimization problems arising from GNN limitations. Oversmoothing mitigation, which aims to prevent node representations from becoming indistinguishable, requires minimizing the second eigenvalue of the propagation matrix μ2(P) _2(P) — equivalently, maximizing the spectral gap λ2(ℒ) _2(L) of the normalized Laplacian. In contrast, oversquashing mitigation, which aims to eliminate information bottlenecks, requires maximizing the conductance ϕ(G)φ(G) or minimizing the total effective resistance. For regular graphs, the two objectives are linked through Cheeger’s inequality: μ2(P)=1−λ2(ℒ) _2(P)=1- _2(L) and ϕ(G)φ(G) lies between λ2(ℒ)/2 _2(L)/2 and 2λ2(ℒ) 2 _2(L). This mathematical relationship reflects a tangible tradeoff: a graph with high algebraic connectivity (good for oversmoothing) tends to have high conductance (good for oversquashing), but the exact relationship is constrained by the spectral gap. Moreover, our NP‑hardness results show that optimizing either objective exactly is intractable in general, reinforcing that practical approaches must rely on approximations or heuristics. The reductions also highlight the inherent complexity of balancing the two phenomena. While a graph that is highly connected (e.g., a complete graph) simultaneously mitigates oversquashing (no bottlenecks) and oversmoothing (large spectral gap), such graphs are often prohibitively dense for real‑world applications. Sparse graphs, on the other hand, may suffer from both issues. Our complexity results suggest that finding an optimal sparse graph that strikes the right balance is computationally challenging, justifying the use of iterative rewiring methods like SDRF and DIGL, which operate in polynomial time and empirically navigate this tradeoff. Several directions for future work emerge from our investigation. First, extending the analysis to directed and weighted graphs would broaden the applicability of the results, as many real‑world graphs possess these properties. Second, incorporating task‑specific importance weights — for instance, weighting node pairs according to their relevance for a downstream prediction task — could lead to more practical formulations that align the graph structure with the learning objective. Third, different GNN architectures (e.g., Graph Attention Networks, Gated Graph Neural Networks) employ distinct propagation mechanisms that may alter the relationship between graph structure and the oversmoothing/oversquashing phenomena; analyzing the complexity of optimizing the graph for those architectures is a natural extension. Finally, empirical evaluation of the gap between the theoretical worst‑case complexity and the actual performance of heuristic rewiring algorithms would provide valuable insight into how often the hard instances occur in practice. 7 Conclusion In this work we have presented a theoretical investigation of graph structure optimization aimed at mitigating oversmoothing and oversquashing in deep graph neural networks. We formulated the problems in terms of conductance and spectral gap, and proved that exact optimization for these formulations is NP‑hard via reductions from Minimum Bisection. Our results establish that graph rewiring for GNN improvement is fundamentally intractable in the worst case, justifying the use of heuristic and approximation methods. These findings lay a solid theoretical foundation for understanding the limits of graph structure optimization in the context of GNNs and guide the development of future efficient and principled rewiring techniques. References [1] U. Alon and E. Yahav (2021) On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations (ICLR), Cited by: §1.2, §1. [2] I. Althöfer and T. Jansen (1999) On the complexity of the second eigenvalue of a graph. In Proceedings of the 1999 Congress on Evolutionary Computation, p. 150–155. Cited by: 2nd item. [3] S. Arora, S. Rao, and U. Vazirani (2009) Expander flows, geometric embeddings and graph partitioning. Journal of the ACM 56 (2), p. 1–37. Cited by: §1.2, §3.2, 1st item. [4] M. Chen, Z. Wei, Z. Huang, B. Ding, and Y. Li (2020) Simple and deep graph convolutional networks. In International Conference on Machine Learning (ICML), Cited by: §1.2. [5] A. M. Cohen (1993) Computing the characteristic polynomial of a matrix. Linear Algebra and its Applications. Cited by: §4.2. [6] L. Franceschi, M. Niepert, M. Pontil, and X. He (2019) Learning discrete structures for graph neural networks. In International Conference on Machine Learning (ICML), Cited by: §1.2. [7] M. R. Garey, D. S. Johnson, and L. Stockmeyer (1976) Some simplified np-complete graph problems. Theoretical Computer Science 1 (3), p. 237–267. Cited by: §1.2, §3.4. [8] J. Gasteiger, S. Weißenberger, and S. Günnemann (2019) Diffusion improves graph learning. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §1.2, §1, §5.2. [9] N. Gholinejad and M. H. Chehreghani (2026) Heterophily-aware fair recommendation using graph convolutional networks. Neurocomputing 661, p. 131956. External Links: Link, Document Cited by: §1. [10] W. L. Hamilton, Z. Ying, and J. Leskovec (2017) Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §1.2. [11] S. Hoory, N. Linial, and A. Wigderson (2006) Expander graphs and their applications. Bulletin of the American Mathematical Society 43 (4), p. 439–561. Cited by: §1.2, §3.2. [12] F. Hoseinnia, M. Ghatee, and M. H. Chehreghani (2025) Mitigating over-smoothing in graph neural networks for node classification through adaptive early embedding and biased dropedge procedures. Knowl. Based Syst. 320, p. 113615. External Links: Link, Document Cited by: §1. [13] K. Huang, P. Chandak, Q. Wang, S. Havaldar, A. Vaid, J. Leskovec, G. N. Nadkarni, B. S. Glicksberg, N. Gehlenborg, and M. Zitnik (2024-09) A foundation model for clinician-centered drug repurposing. Nature Medicine 30 (12), p. 3601–3613. Note: Open access under C BY-NC-ND 4.0 External Links: Document, Link Cited by: §1. [14] T. N. Kipf and M. Welling (2017) Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), Cited by: §1.2, §1. [15] B. Lakzaei, M. H. Chehreghani, and A. Bagheri (2025) A decision-based heterogenous graph attention network for multi-class fake news detection. Knowl. Based Syst. 330, p. 114499. External Links: Link, Document Cited by: §1. [16] B. Lakzaei, M. H. Chehreghani, and A. Bagheri (2025) LOSS-GAT: label propagation and one-class semi-supervised graph attention network for fake news detection. Appl. Soft Comput. 174, p. 112965. External Links: Link, Document Cited by: §1. [17] Q. Li, Z. Han, and X. Wu (2018) Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI Conference on Artificial Intelligence (AAAI), Cited by: §1.2, §1. [18] Y. Mohamadi and M. H. Chehreghani (2025) Mitigating over-squashing in graph few-shot learning by leveraging local and global similarities. Appl. Soft Comput. 184, p. 113863. External Links: Link, Document Cited by: §1. [19] F. G. Nasrabadi, A. Kashani, P. Zahedi, and M. H. Chehreghani (2025) Content augmented graph neural networks. ACM Trans. Web 19 (4), p. 40:1–40:19. External Links: Link, Document Cited by: §1. [20] K. N. Nguyen, N. Ho, and D. Phung (2023) Understanding oversquashing in graph neural networks: a curvature perspective. In International Conference on Machine Learning (ICML), Cited by: §1.2, §1. [21] K. Oono and T. Suzuki (2020) Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations (ICLR), Cited by: §1.2, §1. [22] T. K. Rusch, M. M. Bronstein, and P. Lio (2021) Understanding and mitigating oversquashing in graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §1.2, §1.2, §1, §1, §5.2. [23] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio (2018) Graph attention networks. In International Conference on Learning Representations (ICLR), Cited by: §1. [24] Y. Wang, Y. Li, and J. Liu (2022) Understanding oversmoothing in graph neural networks: a spectral perspective. In International Conference on Learning Representations (ICLR), Cited by: §1.2. [25] M. Zohrabi, S. Saravani, and M. H. Chehreghani (2024) Centrality-based and similarity-based neighborhood extension in graph neural networks. J. Supercomput. 80 (16), p. 24638–24663. External Links: Link, Document Cited by: §1.