- 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
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:
- Theory. We characteerize addressability mathematically: sufficient conditions, leakage bounds, and the cost a non-addressable virtual node pays.
- Controlled experiments. Synthetic tasks, where oversquashing is known and controlled, validate these properties: Two-Radius, Tree-NeighborsMatch, and a new task, semantic Two-Radius.
- 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).
Anchors
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.
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 ↓:
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):
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):
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.