acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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- 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 for GATv2 to ; on Peptides-struct it reduces MAE from to . 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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Neural Networks, Graph Rewiring, Graph Attention Networks, Over-Squashing, Curvature, Long-Range Graph Learning, Heterophily

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_BefMOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes CARAT (Curvature- and Attention-Aligned Rewiring with Adaptive Topology), a graph-rewiring method for attention-based GNNs. Its central motivation is the rewiring-utilization gap: adding a structurally desirable shortcut edge does not mean that a GAT-style model will actually use it, because the new edge must compete with existing neighbors through attention normalization. CARAT addresses three questions: where to add shortcuts, which shortcuts are useful, and how strongly they should be used. The method has three main parts:

  1. Curvature-guided candidate generation. It computes exact Balanced Forman Curvature (BFC) on original edges, interprets strongly negative curvature as evidence of a bottleneck, and scores candidate two-hop shortcuts based on the curvature of the corresponding two-hop paths. Only the top-k candidates per source node are retained, bounding the number of new directed edges by roughly k|V|.
  2. Directional compatibility. For each candidate shortcut i -> j, CARAT learns separate query/key projections and computes a directional compatibility score cij=qi⊤kjc_{ij}=q_i^\top k_j. The motivation is that useful communication need not correspond to raw feature similarity, especially on heterophilous graphs.
  3. Soft task-adaptive gating. The topology score and compatibility score are combined, and a monotone sigmoid gate gijg_{ij} determines how strongly each shortcut is exposed to GATv2. The authors additionally use bridge and sparsity regularizers to encourage useful bottleneck shortcuts while discouraging excessive activation.
Critical strengths
  • The central motivation (i.e., the rewiring-utilization gap) is easy to understand
Critical weaknesses

W1. The novelty of the proposed “rewiring–utilization gap” appears somewhat overstated relative to prior task-adaptive and relational rewiring work. The distinction between adding a structurally desirable edge and actually using it downstream is intuitive for attention-based aggregation and has close precedents. In particular, FoSR (Karhadkar et al., ICLR 2023), which is already cited, explicitly distinguishes original and rewired edges through relation-specific learned parameters so that the model can suppress unhelpful rewired connections; however, the related-work discussion describes FoSR only in terms of spectral edge selection. Probabilistic Task-Adaptive Graph Rewiring (Qian et al., ICML DAE Workshop 2023) likewise learns to add task-relevant edges while omitting less beneficial ones, but is not discussed. Greener GRASS (ICLR 2025) further already combines rewiring and graph attention. The paper should more clearly distinguish this narrower contribution from the broader, established idea that structurally proposed edges should be selectively utilized according to the downstream task.

  • FoSR: First-order Spectral Rewiring for Addressing Oversquashing in GNNs. ICLR 2023.
  • Probabilistic Task-Adaptive Graph Rewiring. ICML DAE 2023.
  • Greener GRASS: Enhancing GNNs with Encoding, Rewiring, and Attention. ICLR 2025.

W2. The proposed soft gate does not necessarily control actual shortcut utilization. In Section 4.3, the learned gate $g_{ij}$ is passed to GATv2 as a structural edge attribute rather than directly multiplying the message or attention coefficient. Since GATv2 processes edge attributes through unconstrained learned transformations, increasing $g_{ij}$ does not necessarily increase attention, and a gate approaching zero does not guarantee that the corresponding shortcut is suppressed. Thus, the monotonicity of the gate with respect to the proposed shortcut score does not imply monotonicity of actual attention or message contribution.

W3. The learned directional compatibility score is not explicitly aligned with the downstream attention mechanism. Section 4.2 introduces a separately learned compatibility score $c_{ij}=q_i^\top k_j$ to estimate whether a candidate shortcut will be useful to GATv2. However, this score and GATv2's attention coefficients are computed using different learned parameters, without an explicit constraint ensuring their agreement. Consequently, a shortcut assigned high compatibility may still receive little attention, leaving the proposed rewiring–utilization gap unresolved. Moreover, since GATv2 already learns directional attention scores, the necessity of an additional compatibility network is unclear.

W4. The ablation experiments do not sufficiently isolate the contributions of the proposed components. In Table 1, the Topology-only variant differs from CARAT in three aspects simultaneously: directional compatibility, soft gating, and hard consolidation. Therefore, their performance difference cannot establish which component is responsible for the improvement. Similarly, Uniform-2Hop and CARAT differ in both shortcut selection and adaptive utilization, making it difficult to isolate the contribution of curvature-guided selection. This is particularly important because Uniform-2Hop already captures most of CARAT's performance gains on the Peptides benchmarks.

W5. The experimental comparisons do not sufficiently establish the practical competitiveness of CARAT, particularly on the LRGB benchmarks. Although the paper intentionally focuses on controlled GATv2 comparisons, CARAT's reported performance on Peptides-func (0.5412 AP) and Peptides-struct (0.3671 MAE) is below even the original GCN baselines reported by Dwivedi et al. (NeurIPS 2022), which achieve 0.5930 AP and 0.3496 MAE, respectively. Subsequent work by Tönshoff et al. (TMLR 2024) reports substantially stronger results from appropriately tuned conventional GNNs. While cross-paper comparisons are not directly controlled, these gaps raise questions about the strength of the underlying backbone and the practical significance of the reported improvements.

  • Dwivedi et al. (NeurIPS 2022): Long range graph benchmark
  • Tönshoff et al. (TMLR 2024): Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark

W6. The manuscript contains several presentation and implementation-consistency issues. Appendix E refers to "AFP-enabled" and "non-AFP" variants without clearly defining AFP, while the model-name correspondence table retains implementation-specific names such as "fecasa v3 without afp," suggesting that the final terminology has not been consistently applied. More importantly, Table 1 specifies that the Topology-only variant does not use soft gating but does perform hard consolidation, whereas Appendix C defines the consolidation criterion using the learned gate $g_{ij}$. It is unclear how this criterion is implemented for Topology-only.

Questions for authors

See weaknesses above.

Reviewer_pzbgOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper argues that shortcuts added by graph rewiring help an attention-based GNN only if attention actually uses them, a mismatch it calls the rewiring–utilization gap. It proposes CARAT, which combines Balanced Forman curvature-based selection of two-hop shortcuts, learned directional endpoint compatibility, and a differentiable scalar supplied to GATv2 as an edge feature. An optional variant subsequently prunes shortcuts. Experiments cover four node-classification datasets and two LRGB peptide tasks. Rewiring has mixed effects on node classification and substantially improves peptide performance. Uniform two-hop shortcuts explain most of the peptide improvement; CARAT provides smaller additional gains. Hard pruning is generally unhelpful on the peptide tasks.

Critical strengths

The uniform-shortcut control substantially improves the interpretation of the results. Comparing against shortcuts drawn under the same per-source candidate budget reveals that most of the peptide improvement comes from introducing shorter paths. The authors acknowledge this directly, making the empirical conclusions more credible.

Critical weaknesses

The experiments do not establish the contribution of CARAT’s distinctive components or its claimed utilization mechanism.

Uniform two-hop shortcuts recover approximately 95–96% of CARAT’s improvement over GATv2 on the peptide tasks. CARAT’s additional improvement is only 0.0032 AP on Peptides-func and 0.0023 MAE on Peptides-struct. On Cora, CARAT performs 1.78 percentage points below the uniform control.

The component comparisons leave attribution unresolved. Under hard consolidation, jointly adding compatibility and soft gating, Topology-only versus CARAT-H, produces worse mean performance on five of six datasets. This provides little support for that combination under pruning, while the corresponding comparison without pruning is missing. A random-candidate variant using CARAT’s compatibility and gating is also absent, preventing a clean assessment of curvature-based selection.

Furthermore, Section 4.3 supplies the “gate” as an edge feature rather than a multiplicative message weight. Its monotonicity therefore does not guarantee monotone control of actual shortcut utilization or suppression as the gate approaches zero. The reported gate/utilization means do not demonstrate that CARAT closes the proposed rewiring–utilization gap.

Why this matters: The results convincingly demonstrate benefits from shortcut availability in the tested peptide configuration. They provide substantially weaker support for CARAT’s particular mechanisms and for the abstract’s stronger conclusion that shortcut quality and soft adaptation matter more than adding edges.

The evaluation does not establish CARAT's value against stronger baselines or existing rewiring methods.

The peptide baseline is far below published results. GATv2 obtains 0.4747 AP / 0.4216 MAE, and CARAT reaches 0.5412 / 0.3671. A plain GAT on the same tasks reports 0.5800 / 0.3506, and GAT with LASER rewiring 0.6271 / 0.2971 (Barbero et al., ICLR 2024); a tuned GCN reaches 0.6860 / 0.2460 (Tönshoff et al., 2023). Configurations differ, but CARAT's best result is below even a plain GAT, which raises the question of whether its gains persist with a properly trained backbone.

All experimental comparisons are internal variants. The paper cites FoSR, ComFy and JDR but compares with none of them. LASER, a close prior work, is not cited. It adds a per-node budget of two-hop (and farther) shortcuts, a step close to CARAT's candidate selection, and it is evaluated on Peptides with several backbones, including GAT. DRew (Gutteridge et al., ICML 2023), also uncited, already showed large Peptides gains from multi-hop communication.

Why this matters: without a gain over stronger baselines or an established rewiring method, the evaluation cannot show that CARAT adds a useful mechanism or new understanding, or that its gains justify its additional machinery.

Questions for authors

Q1. Can you provide two focused comparisons under the same soft training protocol and edge-budget convention?

  • Curvature-selected candidates with unit gates and no learned compatibility, compared with CARAT, to assess the joint contribution of compatibility and gating.
  • Uniformly selected two-hop candidates using CARAT’s full scoring and gating mechanism, compared with CARAT, to assess curvature-based candidate ranking.

Please keep other edge attributes identical and report the final shortcut counts after symmetrization and deduplication. These comparisons would materially affect my assessment of which proposed components contribute.

Q2. Can you directly compare shortcut attention between Uniform-2Hop and CARAT on representative tasks driving the positive conclusions, such as Peptides-func and Squirrel-F? Please report degree-normalized attention rij=djαijr_{ij}=d_j\alpha_{ij}, without multiplying it by the gate, and specify how heads and layers are aggregated. In addition, with model weights fixed, does increasing or decreasing a shortcut’s gate consistently change its attention in the intended direction? This would clarify how the gate feature affects actual shortcut attention and whether it supports the proposed utilization interpretation.

Q3. Do the shortcut gains and CARAT’s additional margin persist under a stronger, validation-selected GATv2 training configuration? A focused Peptides-func comparison of GATv2, Uniform-2Hop, CARAT, and one relevant established rewiring method, such as LASER, under a shared protocol would directly address this concern. Please clarify whether any existing experiments already provide this evidence.

Q4. Do Uniform-2Hop and CARAT receive identical edge-type information, including the is-original flag and, on LRGB, the learned shortcut-edge token, apart from their intended gate differences? Otherwise, their comparison may conflate shortcut selection with edge encoding.

For Peptides, please also clarify whether candidates are symmetrized, report the overlap between the final Uniform-2Hop and CARAT shortcut sets, and explain how k=3k=3 was chosen. In particular, what fraction of nodes have at most three eligible two-hop candidates? This would establish how much opportunity the experiment provides for candidate ranking to make a difference.

Reviewer_MoWFOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies graph rewiring, where adding a shortcut to the graph structure does not mean that the downstream attention model will actually use it. The paper proposes CARAT, a sparse rewiring framework whose main contribution is to separate where to add edges, which edges to select, and how strongly to use them into three controllable stages, and to use controlled experiments to disentangle the benefit of short paths themselves from the benefit of shortcut selection. Validation uses GATv2 as a fixed backbone, with node classification (10 runs) on Cora, Citeseer, and the filtered versions of Chameleon-F and Squirrel-F, and long-range graph tasks (5 runs) on Peptides-func and Peptides-struct; the comparisons include a budget-matched random two-hop baseline (Uniform-2Hop), a topology-only selection variant (Topology-only), and CARAT-H.

Critical strengths

The controlled experimental design distinguishes between possessing short paths and identifying and adapting shortcuts; candidate budgets for node tasks are selected solely on the validation set and frozen prior to testing, enabling us to identify the source of the performance gains when reconnected graphs exhibit better performance in trained GNNs.

Critical weaknesses

W1. The paper does not compare against any published rewiring baselines (e.g., SDRF, FoSR, DiffWire, ComFy, and JDR), nor against simpler alternatives for long-range communication such as a virtual node, GraphGPS, a fully-adjacent layer, or two-hop aggregation schemes like MixHop/SIGN. W2. The only ablation-like comparison, Topology-only versus CARAT, changes three factors at once, namely the compatibility module, the soft gate, and hard pruning, so no experiment in the paper demonstrates that BFC-based candidate selection or directional compatibility yields any benefit on its own.

Questions for authors

Q1. On the separability of the ablation (Table 1): Topology-only and CARAT differ simultaneously in the compatibility module, the soft gate, and hard pruning. Could you add the two missing conditions, namely random candidates + compatibility + soft gate (no BFC), and BFC + soft gate without compatibility, to establish the independent contribution of each factor? Q2. On the actual role of the gate (Section 4.3): in what form does it enter the GATv2 scoring function? Could you also report, for each dataset, the share of attention mass allocated to shortcut edges versus original edges, as well as the full distribution of gate values rather than only their mean?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.