Graph neural networks pass messages along edges, and on many real graphs they fail in two opposite ways. In over-squashing, information from far-away nodes is compressed through a few bottleneck edges until it is lost. In over-smoothing, repeated averaging across layers makes all node representations look alike. The best current fix of the edge-deletion kind, PROXYDELETE, removes edges chosen by a linear-algebra estimate of how much each deletion widens the graph's spectral gap. That gap is a single number measuring how well connected the graph is; a wider gap means fewer bottlenecks. The method works well, but it is greedy and global, it needs a tuned deletion budget, and its estimates break down when eigenvalues cluster. This note proposes a purely local alternative drawn from extremal graph theory. The idea is to delete edges so that the graph contains no short cycles (triangles and 4-cycles), while keeping every node's degree above a floor that a known theorem guarantees is achievable.
The core bet is easy to state. Many of the edges a spectral pruner chooses to delete are chords that close short cycles, so a rule of the form "forbid short cycles, protect minimum degree" should recover most of the benefit without computing any eigenvalues and without a free deletion budget. Biologists will recognize the logic as selective rather than bulk degradation, the distinction drawn in selective autophagy, where adapter proteins tag specific damaged structures for removal instead of degrading cytoplasm at random. We borrow that only as a design principle: tag motif instances first, then remove them under a protective guard. If the bet holds, the result is a faster and more robust pruner. It would also give a mechanistic explanation of why deletion can help at all, which the Braess-paradox argument of Spectral Graph Pruning Against Over-Squashing and Over-Smoothing shows to be possible but does not explain in structural terms.
Core Claim
Our claim is that removing short cycles from a graph, subject to a minimum-degree floor, reduces over-smoothing and does not worsen over-squashing. On standard long-range and heterophilic benchmarks, such pruning should match spectral-gap pruning in accuracy, while running without eigen-decomposition and choosing its own stopping point.
The theoretical anchor comes from Large Subgraphs without Short Cycles. That paper proves that any host graph with minimum degree $\delta$ and maximum degree $\Delta$ contains a spanning 4-cycle-free subgraph whose minimum degree is $\Omega(\delta/(\sqrt{\Delta}\log\Delta))$. The authors use random embeddings and the local lemma, and they give a matching upper-bound construction. This result does two jobs for us. It says how sparse we can make the graph before we are forced to strand nodes. It also replaces the deletion count, which is the hyperparameter both FoSR and PROXYDELETE must tune, with a degree floor that has a principled default.
The intuition for why this should help message passing has two parts. Short cycles create many redundant short walks between nearby nodes, and those walks speed up local averaging, which is the over-smoothing mechanism. High-girth graphs with good minimum degree are locally tree-like, and the best-known expanders have that shape, so removing short cycles need not shrink the spectral gap.
We also take seriously a known tension. Curvature-based rewiring counts triangles and 4-cycles as positive curvature, and treats edges with negative curvature as bottlenecks. Deleting cycles therefore makes edges more negatively curved, which curvature methods would read as creating bottlenecks. Which effect wins is an empirical question, and the experiments below are designed to settle it.
Research Program
The method has three steps. First, enumerate the triangles and 4-cycles through each edge; this is the tagging step. Second, score each edge by how many forbidden-motif instances it participates in. Third, delete edges in descending score order, but skip any deletion that would push an endpoint below the degree floor $d_{\min}(v) = c\,\deg(v)/(\sqrt{\Delta}\log\Delta)$. Here $\deg(v)$ is the node's original degree, so this is a per-node version of the Foucaud et al. bound, and $c$ is a constant that defaults to 1. Pruning stops when no forbidden motif remains or no deletion is allowed. We also implement the randomized version from the theorem, which assigns edges by random embedding into a known extremal 4-cycle-free graph. This tells us whether the greedy heuristic loses anything relative to the construction that carries the guarantee. Motif enumeration is local, and on sparse benchmark graphs it costs roughly the sum of squared degrees.
The analysis has two parts. The first is explanatory. We run PROXYDELETE on each benchmark and measure what fraction of its chosen edges lie on a triangle or 4-cycle, compared with the base rate among all edges. We also compute the rank correlation between its first-order gap-gain score and our motif score. The second part is diagnostic. For each pruned graph we track three quantities across layers: spectral gap, Dirichlet energy decay (a standard measure of over-smoothing, where slow decay means node features stay distinct), and girth. This lets us attribute any accuracy change to one of the two failure modes.
Baselines
The naive reference is the unmodified graph trained with the same GNN, either GCN or the relational GCN used by FoSR, with identical hyperparameter search. A second naive reference is random deletion of exactly as many edges as our method removes, on the same graphs. Because the counts match, any gain from our method cannot be attributed to sparsity alone. A third is degree-based pruning, which removes edges at hub nodes up to the same count. Phase Transition of Degenerate Turán Problems in p-Norms gives reason to expect hub deletion to fail in some regimes: below a critical exponent, the extremal structures are spread-out pseudorandom ones rather than star-like.
The strongest competitor is PROXYDELETE from Spectral Graph Pruning Against Over-Squashing and Over-Smoothing. It reports a test mean absolute error of 0.2470 on LRGB Peptides-struct and raises GCN accuracy on Roman-Empire from about 70% to about 78%. We run it with its published deletion-budget search, and we give our method the same total tuning budget, spent on $c$ and the choice of forbidden cycle set.
For the edge-adding approaches we include FoSR from FoSR: First-order spectral rewiring for addressing oversquashing in GNNs, which reports 84.45% on MUTAG with a relational GCN against 69.25% for the base model and 72.30% for curvature-based SDRF. We also run SDRF itself. As a non-rewiring reference we include the SAN graph transformer, which Long Range Graph Benchmark reports at 0.6439 test average precision on Peptides-func against 0.5930 for GCN.
Beating PROXYDELETE means matching or improving its accuracy or error, within seed variance, on Peptides-struct and Roman-Empire, while running faster than its roughly 7 seconds per 50 modifications on Squirrel. That speed figure is reported in the same paper, and our method must achieve this without a tuned deletion count.
Three ablations isolate the key ingredient. The first deletes only triangles, the second only 4-cycles, and the third removes the degree floor. A fourth ablation is the most important. It deletes the same number of edges at random but only among edges that lie on some short cycle. If this matches the full method, the gain comes from cycle membership itself rather than from our ordering.
Why not just…?
Why not just use PROXYDELETE as is? This is the real threat. If our method only ties it, the contribution shrinks to three things: speed, no budget to tune, and robustness on graphs with clustered eigenvalues, where the first-order estimates are acknowledged to degrade. The overlap analysis decides how much is left. A high overlap between its deletions and short-cycle chords means we have explained its behavior with a cheaper rule. A low overlap with comparable accuracy means two distinct mechanisms exist and might be combined. A low overlap with worse accuracy means the short-cycle hypothesis is wrong, and we would report that.
Why not just use a graph transformer and ignore the topology? Attention over all pairs of nodes does well on Peptides-func (SAN at 0.6439). However, Long Range Graph Benchmark notes that its cost grows quadratically with the number of nodes. We report SAN as an upper reference, and we report our method's accuracy per unit of compute rather than claiming to beat it outright.
Why not just prune randomly or at hubs? Random deletion generally shrinks the spectral gap, according to the PROXYDELETE analysis, and the p-norm phase-transition result argues against assuming hubs carry the problem. The matched-count random and degree baselines test this directly on our data rather than relying on those arguments.
Why not just add edges with curvature or spectral rewiring? On heterophilic graphs, added edges mix features across classes, which is the original motivation for pruning. FoSR and SDRF stay in the comparison so the add-versus-delete tension is measured on the same splits rather than argued.
Proposed Experiments
Node-level tasks are Roman-Empire, Amazon-Ratings and Squirrel, which are heterophilic, plus Cora and Citeseer, which are homophilic. Graph-level tasks are MUTAG, ENZYMES, IMDB-BINARY and REDDIT-BINARY. Long-range tasks are Peptides-struct, scored by mean absolute error, and Peptides-func, scored by average precision. Every method uses ten seeds, identical splits, and the same architecture search.
The decisive checks are four. First, the PROXYDELETE overlap statistic should sit well above the base rate. Second, the Dirichlet energy curve after our pruning should decay more slowly than on the original graph, while the spectral gap does not shrink. If the gap shrinks, the curvature view is right, and the method is an over-smoothing fix only. Third, our method should hold accuracy on symmetric synthetic graphs with clustered eigenvalues, such as grids and products of cycles, where PROXYDELETE's estimates are expected to fail. Fourth, the theory-default floor ($c=1$) should come within seed variance of the best tuned $c$. That last check is what supports the claim that the method needs no deletion budget.