acceptodds
Under review as a conference paper at ICLR 2027

Escaping Oversquashing: Addressable and Support-Aware Global Memory for Message Passing Networks

Abstract

Virtual nodes are a natural tool against oversquashing: they replace long message-passing paths by a two-hop global route. But when many nodes share one global state, that shortcut can become a bottleneck itself. We study two properties of this global memory. First, addressability: under constant-margin address codes and a nonlinearity that amplifies this margin, multiplicative write/read maps provide selectable memory rows with only address-code dimensions. Cross-attention slots and a constrained bilinear memory both satisfy these conditions. Second, support awareness: normalized cross-attention has no self-key for a latent query to use as a reference. A learned private anchor supplies this reference, keeps the read bounded, and exposes the strength of the matching source mass. We demonstrate the merits of such properties on several instances of Two-Radius and Tree-NeighborsMatch: both addressable realizations solve the controlled tasks through depth , where pooled VNs of comparable or larger size reach about .

Primary area:
learning on graphs and other geometries & topologies
Keywords:
virtual nodes, graphs, MPNNs, attention

Reviews

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

The paper studies how a graph model can retrieve the right information from global memory and keep track of how much matching input supports it. Under its stated assumptions, O(log M) address-code dimensions can distinguish M memory rows; a reference entry lets the model recover information that normalization would otherwise hide. The authors test two memory designs on controlled tasks and three LRGB graph benchmarks.

Critical strengths

Letting the model write to and read from specific memory slots makes learning much faster on the controlled lookup task. It reaches 100% accuracy by 500 updates, while a larger model without explicit slot reads reaches 94.3% after 5,000 updates and varies widely across runs.

The repeated-item test checks an important limitation of normalized attention: can the memory tell how many times an item appears? It changes the repetition counts while keeping the underlying item associations fixed, making the comparison easier to interpret.

Critical weaknesses

The paper does not show whether the reference entry needs to be learned. Table 2 does not test a fixed reference or simply giving the decoder the normalization denominator. The counting result also uses just one training seed.

The gains on real graph datasets are small: adding slots changes AP by 0.001, F1 by 0.002, and MAE by -0.009. These are five-seed averages without error bars, so it is hard to judge whether the gains are reliable. The bilinear memory performs worse on all three tasks.

Questions for authors

Would a fixed reference or giving the decoder the normalization denominator work as well across several seeds?

How much do the Table 6 results vary across training seeds?

How much runtime and peak memory do the two designs use on the real graph datasets?

3 comments
AuthorsOpenReview ↗

Author response to Reviewer WgbH

Thank you for the review. We agree with both weaknesses and ran new experiments (mean ± s.d., 3 seeds unless stated).

1. Does the reference need to be learned?

In theory, a learned anchor allows each query to adapt the scale at which it considers the incoming support meaningful, rather than relying on a common, predefined scale. In our experiments, it does not stand out. Explicit mass is generally slightly worse. New results on LRIM-16-hard (Mathys et al., ICLR 2026), a benchmark with provable long-range dependencies, LogMSE ↓:

BackboneGlobal memoryParamsLogMSE
GatedGCNnone99k−2.343 ± 0.053
GatedGCNwide pooled VN489k−2.513 ± 0.037
GatedGCNslots, fixed anchor150k−2.578 ± 0.052
GatedGCNslots, learned anchor158k−2.576 ± 0.047
GPS-Base–210k−2.681 ± 0.081 (2 seeds)
GINnone73k−1.685 ± 0.050
GINwide pooled VN463k−1.686 ± 0.019
GINslots, fixed anchor124k−1.730 ± 0.038
GINslots, learned anchor128k−1.730 ± 0.048
GIN, directednone1.21M+0.387 ± 0.003
GIN, directedwide pooled VN3.60M+0.373 ± 0.003
GIN, directedslots, learned anchor1.43M−0.692 ± 0.042

Fixed and learned anchors give the same result (also with GIN: −1.730 for both). Giving the decoder the normalization mass instead of the anchor also works as well (ECHO-Charge below: 0.00552 vs. 0.00548). We will revise the text: the read needs a reference or mass path, and the learned anchor is one cheap option. It only stands out on Tree-NeighborsMatch at depth 6: 51.3 ± 15.4% vs. 33.9 ± 13.8% without reference and chance level for Softmax1, with high variance because some runs do not converge.

Table 2: Over 3 seeds the result is nearly unchanged (accuracy %, entries without ± have zero variance):

ModelLabelCountBoth
MPNN7.9 ± 0.117.1 ± 0.31.3 ± 0.0
Additive VN8.8 ± 0.218.5 ± 0.31.4 ± 0.0
Normalized slots100.028.328.3
Anchored slots100.0100.0100.0
Anchored bilinear memory100.0100.0100.0

The fixed-reference and exposed-mass controls also displayed perfect accuracy, this will be mentioned in the manuscript.

2. Real-graph gains and variance (Table 6)

We agree: the Table 6 differences are too small to interpret. LRGB was run late, mainly to compare the two (bilinear vs bidir cross-att) realizations, without proper parameter matching or error bars. We redid it and added two better suited benchmarks.

PascalVOC-SP (same backbone and protocol; all memories use the anchor; OGB-style VN for reference):

ModelParamsTest F1 ↑
OGB-style VN585k0.3548 ± 0.0071
Non-persistent slots438k0.3536 ± 0.0151
Persistent slots491k0.3768 ± 0.0042
Bilinear memory623k0.3470 ± 0.0042

The key reading is cross-attention slots (0.377) vs. bilinear memory (0.347, with more parameters). Both are addressable in theory and solve the controlled tasks, so the realization matters a lot in practice. Your remark on the bilinear memory holds, and we now state it as a finding. Scores are lower than in Table 6 because all models were downscaled to similar budgets (width 96 instead of 128).

LRIM-16-hard (table above). In the undirected setting: about 1.7× lower MSE with GatedGCN, closer to GPS-Base (dense self-att + GNN); with GIN it is less clear (−1.730 vs. −1.685). Our models are small (8 layers, width 32), so absolute values are behind the LRIM paper. The directed setting tested in the ICLR paper is interesting (grid edges oriented top-left to bottom-right, so the local wiring is deficient), because we observe that when the GNN is weak, slots give more than 10× lower MSE, while a wide pooled VN does not help.

ECHO-Charge (Miglior et al., ICLR 2026; real molecules), MAE ↓: GNN 0.00572 ± 0.00009; OGB-style VN 0.00557 ± 0.00006; slots 0.00548 ± 0.00005; slots with exposed mass 0.00552 ± 0.00006. A small but consistent gain.

3. Runtime and peak memory

On LRIM-16 (M = 32 slots), slots vs. wide pooled VN: inference ~15 vs. ~12 ms per graph; peak memory ~16 vs. ~20 MB at inference and 32–38 vs. 26–32 MB in training. Slots are slower because of the per-layer attention over slots (non-optimized code). Ratios are similar on graphs up to 65k nodes (no memory 64.1 ms / 278.5 MB; slots 90.3 ms / 260.8 MB; wide VN 74.6 ms / 280.1 MB). On PascalVOC-SP, training times are of the same order.

Revision. The paper is mostly theoretical: it builds on the short-range oversquashing analysis of Mishayev et al. (2025) and asks what a virtual node needs to avoid becoming the bottleneck. The main results remain the theory and the controlled tasks (Two-Radius, especially its semantic variant, and Tree-NeighborsMatch). We will rebuild the real-graph section around these new results and keep cross-attention slots as the standard realization.

AuthorsOpenReview ↗

General comment

General comment: what the paper claims

The reviews made us realize that our claims were not stated clearly enough, so we restate them here and will rewrite the introduction accordingly.

The question is: how can a GNN overcome oversquashing without dense node-to-node attention? Our answer is that the shared global state must be addressable (and, as a second property, support-aware). The paper has three parts:

  1. Theory. We characteerize addressability mathematically: sufficient conditions, leakage bounds, and the cost a non-addressable virtual node pays.
  2. Controlled experiments. Synthetic tasks, where oversquashing is known and controlled, validate these properties: Two-Radius, Tree-NeighborsMatch, and a new task, semantic Two-Radius.
  3. Transfer check. Real-graph benchmarks only test whether the mechanism transfers. It is not well established how much these tasks depend on oversquashing, so we do not expect large gains on all of them and we make no state-of-the-art claim (we use lower dimension than SoTA models anyway).

To go into further detail, the most comprehensive comparative experiment about different anchors in obtained using several support-aware mechanisms on LRIM-hard 16 using the GIN backbone:

Global memory (GIN, LRIM-16-hard undirected)Test LogMSE ↓
No global memory-1.685 ± 0.050
Wide pooled VN-1.686 ± 0.019
Slots (fixed anchor)-1.730 ± 0.038
Slots (learned anchor)-1.735 ± 0.039
Slots (exposed mass)-1.713 ± 0.048
Slots (self-key)-1.762 ± 0.052

(learned anchor progressed a bit since previous record)

In other experiments, learned then fixed anchors generally perform slightly better than self-key'd cross-att (learned anchor is the default for other experiment as it usually won by 2 or 3%). Exposed mass being a bit worse in general.

Reviewer_prfZOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to alleviate oversquashing in message-passing neural networks using global memory. The authors focus on two properties: addressability, which enables selective storage and retrieval through multiplicative write/read operations, and support awareness, which preserves information about the strength of matching sources through a learned private anchor. They provide theoretical analyses of these properties and explore two implementations based on cross-attention slots and bilinear memory. Experiments on Two-Radius and Tree-NeighborsMatch show that both approaches substantially outperform conventional pooled virtual nodes on controlled tasks.

Critical strengths
  1. Clear problem formulation and theoretical analysis. The paper distinguishes memory capacity from addressability and support awareness, and provides formal results characterizing these properties. This helps explain why shortening communication paths with virtual nodes alone may not resolve oversquashing.
  2. Strong empirical results. The proposed methods substantially outperform pooled virtual nodes on Two-Radius and Tree-NeighborsMatch.
Critical weaknesses
  1. The proposed memory mechanisms are closely related to existing work such as latent attention [1] and Softmax1 [2]. Although the paper provides theoretical bounds for addressability, new design insights beyond these established methods are not quite clear. More importantly, the experiments do not isolate the benefit of the learned anchor over a fixed reference or directly expose the normalization mass.
  2. The connection between theory and learned behavior is somehow weak. The theoretical guarantees rely on well-separated address codes and suitable nonlinear amplification, but the experiments do not assess whether the learned models satisfy these conditions. Performance also drops quickly from 100% at depth 5 to 26.2% at depth 6 (table 3), but the authors did not provide further analysis.

[1] Lee, Juho, et al. "Set transformer: A framework for attention-based permutation-invariant neural networks." International conference on machine learning. PMLR, 2019.

[2] https://www.evanmiller.org/attention-is-off-by-one.html

Questions for authors
  1. What are the key new insights beyond existing work such as latent-attention and Softmax1 methods? How does the learned anchor improve over a fixed reference or simply using the normalization mass?
  2. Do the learned models actually achieve the address separation and low routing leakage assumed in the theory? Can this help explain the performance drop at depth 6 (table 3)?
3 comments
AuthorsOpenReview ↗

Author response to Reviewer prfZ

Thank you for the careful review. Both points are very fair; we ran new experiments for each (mean ± s.d., 3 seeds unless stated) and led some experiments to explore the addressing margins empirically.

1. Relation to latent attention and Softmax1

We agree and will say it plainly: we do not claim a new layer. It was written in the paper but was not clear enough: the empirically experimented model is essentially ISAB with an anchor, on top of a GNN. The paper is mostly theoretical: it builds on the short-range oversquashing analysis of Mishayev et al. (2025) and asks what a virtual node needs so that it does not become the bottleneck. Node-to-node attention solves this trivially (Mishayev et al.) at quadratic cost; our question is about a shared global state. Our claims are:

  • sufficient conditions for addressability (as well as its utility for oversquashing), with leakage bounds, for a softmax and a non-softmax realization;
  • the cost of implicit addressing in an additive VN;
  • a latent cross-attention query has no self-key, so a normalized read loses support; the reference fixes this;
  • the semantic Two-Radius task, which tests oversquashing without fixed identifiers.

Learned vs. fixed anchor vs. exposed mass. New results on LRIM-16-hard (Mathys et al., ICLR 2026), LogMSE ↓:

BackboneGlobal memoryParamsLogMSE
GatedGCNnone99k−2.343 ± 0.053
GatedGCNwide pooled VN489k−2.513 ± 0.037
GatedGCNslots, fixed anchor150k−2.578 ± 0.052
GatedGCNslots, learned anchor158k−2.576 ± 0.047
GPS-Base–210k−2.681 ± 0.081 (2 seeds)
GIN, directednone1.21M+0.387 ± 0.003
GIN, directedwide pooled VN3.60M+0.373 ± 0.003
GIN, directedslots, learned anchor1.43M−0.692 ± 0.042

Fixed and learned anchors give the same result (also with GIN: −1.730 for both). On ECHO-Charge (Miglior et al., ICLR 2026), exposing the normalization mass instead of the anchor gives 0.00552 ± 0.00006 MAE vs. 0.00548 ± 0.00005. So the reference does not need to be learned, and we will say so. Learnable anchor allows each query to adapt the scale at which it considers the incoming support meaningful, helps on Tree-NeighborsMatch at depth 6 (below), but the big claim is only that the read needs a reference or mass path.

The memory itself matters most in the directed setting (grid edges oriented top-left to bottom-right, so the local wiring is deficient): slots give more than 10× lower MSE, while a wide pooled VN does not help. In the undirected setting, slots lower MSE by about 1.7× with GatedGCN; with GIN the gain is within noise.

2. Do trained models satisfy the theory? What happens at depth 6?

We measured routing on trained Tree-NeighborsMatch models (%):

ModelDepthAccuracyRouting top-1Correct mass
Slots + anchor599.98 ± 0.0275.5 ± 567.3 ± 5
Slots (normalized)598.89 ± 0.8877.7 ± 571.8 ± 5
Slots + Softmax1599.79 ± 0.2185.6 ± 481.1 ± 4
Slots + anchor651.31 ± 15.4162.5 ± 1248.5 ± 19
Slots (normalized)633.87 ± 13.8038.2 ± 728.0 ± 14
Slots + Softmax161.61 ± 0.181.8 ± 13.1 ± 2

Routing is end to end: for leaf i, p_i ∝ Σ_m att_m^read · att_{m,i}^write over candidate leaves (sorry for format). Top-1: the correct leaf has the largest p_i. Correct mass: p_i of the correct leaf.

Depth-6 accuracy is higher than in the submission (≈26%) thanks to a better cosine schedule; the task is very sensitive to optimization, and some runs still do not converge.

Softmax1 collapses on every seed at depth 6. Comparing depth 5 → 6 for it:

Write marginRegister overlapAddress RMS cosineWrite JSD
Depth 5+3.870.0930.3200.641
Depth 6−2.500.8320.3560.038
  • At depth 5, the routing is selective (positive margin, low overlap) but no one-hot, and accuracy is still near 100%. This fits bounds stated as bounded leakage.
  • At depth 6, accuracy follows routing across variants. With 64 rows for 64 candidates the task is still representable, so this is a routing failure, not a capacity limit.
  • In the collapse, addresses stay separated (RMS cosine 0.32 → 0.36), but all registers attend to the same nodes (JSD 0.64 → 0.04). Training fails to learn the query–address alignment. It looks like the degenerate regime of "Scope and trade-offs".

Our guarantees are 'representational', why depth 6 fails is an interesting follow-up, outside the scope of the paper, it is clearly on the optimization side.

Revision. The main results remain the theory and the controlled tasks to measure how a simple addressable VN solves oversquashing. We will rebuild the real-graph section around LRIM, ECHO and PascalVOC-SP, and keep cross-attention slots as the standard realization, since the bilinear memory was worse in almost all real-graph tests.

AuthorsOpenReview ↗

General comment

To go into further detail, the most comprehensive comparative experiment about different anchors in obtained using several support-aware mechanisms on LRIM-hard 16 using the GIN backbone:

Global memory (GIN, LRIM-16-hard undirected)Test LogMSE ↓
No global memory-1.685 ± 0.050
Wide pooled VN-1.686 ± 0.019
Slots (fixed anchor)-1.730 ± 0.038
Slots (learned anchor)-1.735 ± 0.039
Slots (exposed mass)-1.713 ± 0.048
Slots (self-key)-1.762 ± 0.052

(learned anchor progressed a bit since previous record)

In other experiments, learned then fixed anchors generally perform slightly better than self-key'd cross-att (learned anchor is the default for other experiment as it usually won by 2 or 3%). Exposed mass being a bit worse in general.

To go into further detail, the most comprehensive comparative experiment about different anchors in obtained using several support-aware mechanisms on LRIM-hard 16 using the GIN backbone:

Global memory (GIN, LRIM-16-hard undirected)Test LogMSE ↓
No global memory-1.685 ± 0.050
Wide pooled VN-1.686 ± 0.019
Slots (fixed anchor)-1.730 ± 0.038
Slots (learned anchor)-1.735 ± 0.039
Slots (exposed mass)-1.713 ± 0.048
Slots (self-key)-1.762 ± 0.052

In other experiments, learned then fixed anchors generally perform slightly better than self-key'd cross-att (learned anchor is the default for other experiment as it usually won by 2 or 3%). Exposed mass being a bit worse in general.

Reviewer_LpgJOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This work studies two aspects of virtual node method: addressability, that the global memory should have enough volume for identifying all nodes' information; and support-aware, that the global memory is needed in attention for exposing the strength of the matching source mass rather than keeping normalized do to attention softmax. In experiment, this work conducts experiment on Two-Radius, Tree-NeighborsMatch, and LRGB tasks to show the effectiveness of two properties.

Critical strengths
  1. The Two-Radius and Tree-NeighborsMatch tasks are good synthetic tasks for evaluating the squashing.
Critical weaknesses
  1. Connection to previous work is not clear. Previous work on virtual node also uses attention and larger dimension for virtual nodes, this work neither clarify its contribution compared with previous work, nor including previous works as experiment baseline.
  2. Graph Transformer methods also address the over-squashing problem, but not mentioned at all in this work.
  3. The experiments are mainly conducted on synthetic datasets with no previous strong baseline.
  4. The performance on LRGB is weak compared with current top models on the leaderboard.
Questions for authors

Please use more datasets like open graph benchmark and include more baselines like graph transformer and previous advanced VN methods.

1 comment
AuthorsOpenReview ↗

Author response to Reviewer LpgJ

Thank you for the review. It showed us that our claim, and what we mean by addressability, were not clear enough. We clarify both here, with new results. The full graph-transformer comparison is still running and we will post it when it finishes.

1. What the paper claims

The question is: how can a GNN overcome oversquashing without dense node-to-node attention? A virtual node (VN) shortens every path to two hops, but all nodes then share one global state, which becomes the new bottleneck. Our claim is that this global state must be addressable. The paper (i) characterizes this property mathematically, building on the short-range oversquashing analysis of Mishayev et al. (2025), (ii) validates it on controlled tasks where oversquashing is known, including a new one (semantic Two-Radius), and (iii) uses real-graph benchmarks only as a transfer check.

2. What addressability is

Addressability is not about the size of the memory. It means that different sources or semantics can write to distinct parts of the memory, and that each target can select the part it needs. A large state that every node writes to and reads from in the same way is not addressable, however wide it is. Our results show this directly:

  • Tree-NeighborsMatch, depth 5: a wide pooled VN with 2.33M parameters reaches 10.7%; addressable slots with 37.5k parameters reach 100%.
  • Two-Radius experiments show that even a wide VN struggle to match the addressable VN performance.
  • Real benchmarks show that the addressable VN usually outperforms than a wide VN with much larger capacity for standard graph problems.

3. Prior VN work and graph transformers

We do not claim a new architecture. The implemented model is essentially ISAB (Set Transformer) with an anchor, on top of a GNN, and we will say it more clearly (or a Perceiver with inputs=outputs w/o self-att). The contribution is to explain why and when such a memory helps: conditions for addressability with leakage bounds, and the cost a non-addressable VN pays.

On graph transformers: node-to-node attention removes the bottleneck trivially (Mishayev et al.), at quadratic cost. Our question is how to reduce oversquashing using a shared global state with O(nM) cost. We will add this discussion, it was not clear enough. As a first comparison, on LRIM-16-hard (Mathys et al., ICLR 2026), a benchmark with provable long-range dependencies (LogMSE ↓, 3 seeds, 8 layers of dim 32 as undirected backbones, 12/128 for directed GINs, the wide VN is equipped with a dim 768 MLP):

LRIM-16-hard — Test LogMSE (↓), mean ± std over 3 seeds (2 for GPS).

BackboneGlobal memoryParamsLogMSE ↓
Undirected (8 layers, width 32)
GINNone73k-1.685 ± 0.050
GINWide pooled VN463k-1.686 ± 0.019
GINSlots (fixed anchor)124k-1.730 ± 0.038
GINSlots (learned anchor)128k-1.735 ± 0.039
GINSlots (exposed mass)128k-1.713 ± 0.048
GINSlots (self-key)128k-1.762 ± 0.052
GatedGCNNone99k-2.343 ± 0.053
GatedGCNWide pooled VN489k-2.513 ± 0.037
GatedGCNSlots (fixed anchor)150k-2.578 ± 0.052
GatedGCNSlots (learned anchor)158k-2.576 ± 0.047
GPS-Base—210k-2.681 ± 0.081
Directed (12 layers, width 128)
GINNone1.21M+0.387 ± 0.003
GINWide pooled VN3.60M+0.373 ± 0.003
GINSlots (learned anchor)1.43M-0.692 ± 0.042

Slots close most of the gap between the local GNN and the graph transformer (we implemented GPS-Base as in the benchmark paper, in our experiments the GT from A Generalization of Transformer Networks to Graphs from Dwivedi et al. seemed to perform worse for the 3 seeds). In the directed setting proposed by the ICLR paper (grid edges oriented top-left to bottom-right, the local wiring is deficient), only the addressable memory helps.

4. Benchmarks

The previous LRGB table in the submission was run late, without good parameter matching or error bars, and LRGB is not a clean test of oversquashing. We redid PascalVOC-SP properly (3 seeds, dim 96 vs previous 128):

ModelParamsTest F1 ↑
OGB-style VN585k0.3548 ± 0.0071
Persistent slots491k0.3768 ± 0.0042

Instead of OGB, we added LRIM and ECHO-Charge (Miglior et al., ICLR 2026), two recent benchmarks built to test long-range propagation, which fit our question better. On ECHO-Charge (3 seeds):

ModelMAE ↓
GNN (no global memory)0.00572 ± 0.00009
GNN + OGB-style VN0.00557 ± 0.00006
GNN + slots0.00548 ± 0.00005

Topping the LRGB leaderboard is not the goal of the paper. The main results are the theory and the controlled experiments; the real-graph results show that the mechanism transfers, with gains that depend on how much a task relies on long-range communication.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.