QUALITY BEFORE QUANTITY: CURVATURE- AND ATTENTION-ALIGNED SPARSE REWIRING FOR GRAPH NEURAL NETWORKS

Graph rewiring can shorten communication paths in a message-passing graph, but a new edge is useful only if the downstream attention model actually uses it. This issue is especially important for graph attention networks, where added edges compete with existing neighbors for attention: a shortcut may be structurally attractive yet receive little attention. We call this mismatch the rewiring–utilization gap. We introduce CARAT (Curvature- and Attention-Aligned Rewiring with Adaptive Topology), a sparse rewiring framework that asks three questions: where should edges be added, which candidate edges are useful, and how strongly should they be used? First, exact Balanced Forman curvature identifies bottlenecked two-hop paths, while a top-$k$ budget per source node prevents uncontrolled graph growth. Second, a learned directional compatibility score estimates whether the endpoints of a candidate shortcut are useful to connect for an attention model. Third, a monotone soft gate lets the task adapt shortcut strength end-to-end while preserving all original edges. Across Cora, Citeseer, filtered Chameleon and Squirrel, and the Peptides-func/Peptides-struct long-range benchmarks, we find that rewiring is strongly regime-dependent: it can hurt graphs that already support effective local propagation, while it is valuable when long-range communication matters. On Peptides-func, CARAT improves average precision from $0.4747$ for GATv2 to $0.5412$; on Peptides-struct it reduces MAE from $0.4216$ to $0.3671$. A budget-matched uniform two-hop baseline captures much of this gain, but CARAT gives the best mean on both tasks. We also find that irreversible hard pruning is not consistently helpful. These results suggest a practical principle: for attention GNNs, shortcut quality and soft task adaptation matter more than simply adding more edges.