Global Communication or Graph-Specific Memory?

Hamed Shirzad; Danica J. Sutherland

cs.LGOct 5, 2026

Global Communication or Graph-Specific Memory?

Authors: Hamed Shirzad, Danica J. Sutherland

Organizations: University of British Columbia

Abstract

Scalable Graph Transformers are commonly trained and evaluated on static large graphs in a transductive setup. Many scalable Graph Transformer components can be formulated as a constant-size shared memory, similar to virtual nodes, providing compressed information about the whole graph. The counterpart of these models in language models and other domains is justified as the input changes, and this mechanism learns to compress some useful information about the input. In transductive learning on a single fixed graph, however, any shared memory can be seen as a constant at test time. This raises the question of what exactly this shared memory does in this static setup. We give preliminary evidence that optimizing a shared memory directly performs similarly to global communication methods, and so normal local message-passing models can embed similar information in their weights. Thus, these settings may be a poor fit for evaluating global communication in graph neural networks.

Figures & tables

Figure 1: The role of a shared writer depends on the input domain. (a) In the inductive setting, the writer is trained across multiple graphs and must produce an input-specific memory for each new test graph. (b) In the static transductive setting, training and evaluation use the same graph input (

I^{*}

). After training, its memory (

c^{*}=c_{\theta}(I^{*})

) is fixed and can be recorded and reused at evaluation, while leaving the reader unchanged.

Figure 2: Original models versus learned shared memories. Bars show mean test accuracy over five matched seeds. Whiskers show marginal

95\%

Student-

t

confidence intervals. The learned-memory model has a higher mean in eleven of sixteen comparisons. Fourteen of the sixteen paired

95\%

intervals for the memory-minus-original difference contain zero. The two exceptions have opposite signs: DIFFormer-s on Cora favors the original model by

2.0

points, while NodeFormer on PubMed favors learned memory by

2.4

points.

Figure 3: Response to feature and topology changes. Solid lines recompute the current writer state. Dashed lines reuse the clean recorder state. Orange curves use one clean training input, purple curves use one checkpoint trained on

16

nearby inputs, and the blue and green curves show the aligned writer-only control. Shaded regions show variation across three optimization seeds. The dotted line marks the largest marginal perturbation used during multi-input training.

Figure 4: Learning one fixed long-range target. Lower normalized test RMSE is better. Bars compare the original model, directly optimized shared memory, and a two-hop GNN. The same GNN result is repeated within each model group. Horizontal lines show the train mean and nearest-training-node baselines. Whiskers are

95\%

confidence intervals over five optimization seeds.

Figure 5: Directly optimizing shared memory on City-Networks. Bars show mean test accuracy for the original model and its directly optimized shared-memory counterpart. Whiskers are marginal

95\%

Student-

t

confidence intervals.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Graph	Nodes	Diameter	Mass beyond two hops
Cora	$2{,}485$	$19$	$94.5\%$
Actor	$7{,}600$	$12$	$97.9\%$
Amazon-Photo	$7{,}487$	$11$	$77.6\%$
PubMed	$19{,}717$	$18$	$99.8\%$

Appendix

Table 1: Graph structures used by the static long-range task. Diameter is the exact unweighted diameter of the largest connected component. The last column is the median target-kernel mass outside two hops.

Model	Hidden width	Depth	Heads	RF	Additional setting
Polynormer-r	$64$	$1$ local $+$ $1$ global	$1$	–	Layer normalization
SGFormer	$64$	$4$ GCN $+$ $1$ global	$1$	–	Graph weight $0.8$
NodeFormer	$32$	$2$ kernel layers	$4$	$30$	Fixed RF basis, no Gumbel or edge loss
DIFFormer-s	$64$	$2$ simple-kernel layers	$1$	–	Local graph branch retained

Appendix

Table 2: Exact replay configurations. Depth lists local and global layers when both are present. RF is the number of NodeFormer random features.

Model	Graph	$d$	Layers	$H/\mathrm{RF}/r_{b}$	Dropout	LR	Weight decay	$E/P$	State LR/init.
SGFormer	Cora	64	$4+1$	$1/--/--$	$.5/.2$	$10^{-2}$	$5{\times}10^{-4}/10^{-3}$	$1000/200$	$.01/.10$
SGFormer	Amazon-Photo	64	$6+1$	$1/--/--$	$.5/.3$	$10^{-3}$	$5{\times}10^{-5}/5{\times}10^{-5}$	$1000/120$	$.01/.10$
SGFormer	PubMed	64	$4+1$	$1/--/--$	$.5/.3$	$5{\times}10^{-3}$	$5{\times}10^{-4}/10^{-2}$	$1000/200$	$.10/.10$
SGFormer	Actor	64	$2+1$	$1/--/--$	$.2/.2$	$10^{-3}$	$5{\times}10^{-4}/10^{-2}$	$1000/200$	$.01/.10$
NodeFormer	Cora	64	2	$4/64/3$	$.5$	$5{\times}10^{-3}$	$5{\times}10^{-4}$	$1000/200$	$.001/.01$
NodeFormer	Amazon-Photo	64	2	$4/64/0$	$.3$	$10^{-3}$	$5{\times}10^{-5}$	$1000/120$	$.001/.01$

Appendix

Table 3: Original and learned-memory hyperparameters.

E/P

gives the maximum number of epochs and early-stopping patience. For Polynormer-r, layers give local

+

global layers, dropout gives input/local/global dropout, and

E/P

gives local-stage epochs

+

global-stage maximum/patience. Its

d

is the width per head. The final column gives the learned-state learning rate and initialization scale.

Parameter	Value
Graphs	Largest connected components of Cora and Actor, with $2485$ and $7600$ nodes
Split	Nearest-landmark-stratified $60/20/20$ ; train/validation/test counts are $1467/480/538$ and $4530/1526/1544$
Structural map	$64$ farthest-point landmarks, exponential scale $\tau=0.75$
Node signal	Eight-dimensional standard Gaussian
Feature shifts	$\sigma\in\{0,.1,.2,.4,.6,.8,1\}$ in Equation 22
Topology shifts	Connected degree-preserving swaps with requested severities $\{0,.01,.02,.05,.1,.2,.4,.8,1\}$ ; results use the realized changed-edge fraction

Appendix

Table 4: Perturbation-task hyperparameters.

Model	Width	Depth	Heads/RF	LR/weight decay	One-input budget
Polynormer-r	64	$1$ local $+$ $1$ global	$1/--$	$.005/10^{-5}$	$1500/50$
SGFormer	64	$4$ GCN $+$ $1$ global	$1/--$	$.005/10^{-5}$	$300/30$
NodeFormer	32	$2$ kernel layers	$4/30$	$.005/10^{-5}$	$1000/50$
DIFFormer-s	64	$2$ simple-kernel layers	$1/--$	$.005/10^{-5}$	$1000/30$
Writer-only control	8	$8{\times}8$ value map $+$ bias	–	$.05/0$	$3000/50$

Appendix

Table 5: Perturbation-model hyperparameters. One-input budget gives maximum epochs and patience in validation checks. Multi-input models use

1600

steps, validation every

80

steps, and patience

10

checks. All source-model rows use dropout

0

Setting	SGFormer	NodeFormer
Hidden width	$64$	$64$
Layers	$16$ local $+$ $16$ global	$16$
Attention heads	$1$	$1$
Dropout	$0.2$	$0.2$
Normalization / residual	on / on	on / on
Graph weight	$0.8$	–

Appendix

Table 6: Hyperparameters for the City-Networks experiment. State learning rates are listed as Paris/Shanghai/Los Angeles.

Explore similar work

Graph Memory Transformer (GMT)
Apr 26, 2026Nicola Zanarini, Niccolò Ferrari, Evelina LammaMultiplex Graph Transformers Transformer Encoder
Bonfiglioli Engineering s.r.l. · Department of Engineering, University of Ferrara, Via Saragat 1, 44122 Ferrara, Italy · NAIS s.r.l., Via Maria Callas 4, 40131 Bologna, Italy
MegaGraph: Towards Efficient Training of Large-Scale Graph Transformers with Automated Hybrid Parallelism
Sep 28, 2026Tong Qiao, Ao Zhou, Yingjie Qi +2Multiplex Graph Transformers Cpu-Gpu Hybrid Designs
School of Computer Science and Engineering, Beihang University, China · School of Software, Beihang University, China · State Key Laboratory of Complex and Critical Software Environment, Beihang University, China +1
Graph Neural Networks Applications Across Domains: All Insights You Need
Jun 25, 2026Abderaouf BahiGraph Neural Networks Neural Network
Computer Science and Applied Mathematics Laboratory (LIMA), Faculty of Science and Technology, Chadli Bendjedid University, P.O. Box 73, El Tarf 36000, Algeria

Apr 26, 2026, cs.LGJ/K move · Enter open · S save

Graph Memory Transformer (GMT)

Nicola Zanarini, Niccolò Ferrari, Evelina Lamma

Bonfiglioli Engineering s.r.l. · Department of Engineering, University of Ferrara, Via Saragat 1, 44122 Ferrara, Italy · NAIS s.r.l., Via Maria Callas 4, 40131 Bologna, Italy

Multiplex Graph Transformers Transformer Encoder Feed-Forward Peak Memory

Open paper AskPDF arXiv

We investigate whether the Feed-Forward Network (FFN) sublayer in a decoder-only transformer can be replaced by an explicit learned memory graph while preserving the surrounding autoregressive architecture. The proposed Graph Memory Transformer (GMT) keeps causal self-attention intact, but replaces the usual per-token FFN transformation with a memory cell that routes token representations over a learned bank of centroids connected by a learned directed transition matrix. In the base GMT v7 instantiation studied here, each of 16 transformer blocks contains 128 centroids, a 128 * 128 edge matrix, gravitational source routing, token-conditioned target selection, and a gated displacement readout. The cell therefore returns movement from an estimated source memory state toward a target memory state, rather than a retrieved value. The resulting model is a fully decoder-only language model with 82.2M trainable parameters and no dense FFN sublayers, compared with a 103.0M-parameter dense GPT-style baseline used in the evaluation. The base v7 model trains stably and exposes centroid usage, transition structure, and source-to-target movement as directly inspectable quantities of the forward computation. It remains behind the larger dense baseline in validation loss and perplexity (3.5995/36.58 vs. 3.2903/26.85), while showing close zero-shot benchmark behavior under the evaluated setting. These results are not intended as a state-of-the-art claim; they support the viability and structural interpretability of replacing dense within-token transformation with graph-mediated memory navigation. Broader scaling, optimized kernels, and more extensive benchmark evaluation are left for subsequent work.

Abstract

Explore similar work

Graph Memory Transformer (GMT)

MegaGraph: Towards Efficient Training of Large-Scale Graph Transformers with Automated Hybrid Parallelism

Graph Neural Networks Applications Across Domains: All Insights You Need