Topology Survives Shuffling: Robust Long-Context Memory Access Prediction for Graph Analytics

Dongyan Sun; Neelesh Gupta; Rajgopal Kannan; Viktor K. Prasanna

cs.LGOct 29, 2026

Topology Survives Shuffling: Robust Long-Context Memory Access Prediction for Graph Analytics

Authors: Dongyan Sun, Neelesh Gupta, Rajgopal Kannan, Viktor K. Prasanna

Organizations: University of Southern California, USA · DEVCOM Army Research Office, USA

Abstract

Graph analytics generates irregular, topology-dependent memory-access streams via indirect traversals, limiting data prefetching. Accurate prediction enables timely prefetches that hide memory latency. However, ML predictors couple short histories with fixed horizons, fitting the training trace's node layout rather than learning transferable graph patterns. We propose LoCoMAP, a long-context representation-learning framework for memory-access prediction with independently controlled observation history and prediction horizon. We evaluate Connected Components (CC), PageRank (PR), and Single-Source Shortest Paths (SSSP) on six synthetic graph families, with Erdos-Renyi (ER) and Grid as random and deterministic controls. We test two interventions: same-family regeneration changes connectivity, while node shuffling disrupts layout but preserves connectivity. Across 18 graph-workload pairs, extending history from 8 to 128 accesses improves F1 by 7.8%, while extending prediction horizon from 8 to 512 improves F1 by 88.3%. For CC, regeneration is less disruptive than shuffling: without retraining, long context retains 95.4% of original F1 and outperforms short context in six families. Under full shuffle, long context improves CC F1 by 33.6% across ER, Barabasi-Albert, Copying Model, and Stochastic Block Model (SBM), with a 2.06x gain on SBM, but not on Watts-Strogatz or Grid, where near-zero delta mass shifts into heavy tails beyond the predictor's range. Long context outperforms short context on six real-world CC graphs. At full shuffle, long-context PR retains 57.6% of original F1 and averages 11.0% above short context. Both SSSP models retain about 30% of original F1 under full shuffle as distance updates access vertex data in a new order. Within these bounds, long-context predictors are robust across related graphs and layouts without retraining, enabling a generalizable graph prefetcher.

Figures & tables

Fig. 1: Graph Topologies of Synthetic Network Models.

Fig. 2: Overall Architecture of LoCoMAP .

Fig. 3: Visualization of memory access patterns in the benchmark applications.

Topology	# Vertices	# Edges	Avg. Degree	$\mathbf{S}_{\mathrm{order}}$
ER	1,000,000	2,400,000	4.8	0.0007
BA	1,000,000	4,999,985	10.0	0.0016
CM	1,000,000	2,952,366	5.9	0.2088
SBM	1,000,000	2,500,000	5.0	0.5188
WS	1,000,000	2,000,000	4.0	0.9002
Grid	1,000,000	1,998,000	4.0	0.9985

TABLE I: Graph statistics.

	Configuration	Value	Configuration	Value
Input/output	Delta bound	$\pm$ 128	Delta bitmap $B$	256
	History $N$	9	Look-forward $W$	256
Attention	Dimension $D$	64	MLP head layer	1
	Head number	4	Layer $L$	1

TABLE II: Model configuration.

Parameter	Value	Applications
		CC						PR						SSSP
		ER	BA	CM	SBM	WS	Grid	ER	BA	CM	SBM	WS	Grid	ER	BA	CM	SBM	WS	Grid
Look-back $L$ ( $W{=}256$ , $B{=}256$ )	8	0.466	0.561	0.660	0.590	0.690	0.641	0.472	0.658	0.684	0.609	0.733	0.668	0.075	0.256	0.683	0.057	0.363	0.639
	16	0.468	0.574	0.661	0.592	0.691	0.642	0.475	0.669	0.688	0.613	0.738	0.671	0.083	0.273	0.684	0.065	0.354	0.646
	32	0.503	0.568	0.664	0.593	0.714	0.645	0.492	0.661	0.690	0.616	0.740	0.665	0.086	0.303	0.696	0.066	0.365	0.653
	64	0.515	0.620	0.669	0.596	0.731	0.650	0.503	0.670	0.691	0.622	0.748	0.679	0.093	0.311	0.704	0.074	0.358	0.655

TABLE III: Ablation of Look-Back Length

L

and Look-Forward Window

W

Across Graph Topologies and Applications (F1-Score)

Fig. 4: Latency, FLOPs and memory cost as the look-back length $L$ scales from 8 to 128.

	Original ( $L=8$ )	Long ( $L=128$ )
Family	A/B (ret.)	A/B (ret.)
ER	.466/.393 (84.3%)	.514/.481 (93.6%)
BA	.561/.546 (97.3%)	.635/.589 (92.8%)
CM	.660/.560 (84.8%)	.674/.622 (92.3%)
SBM	.590/.569 (96.4%)	.587/.576 (98.1%)
WS	.690/.656 (95.1%)	.722/.705 (97.6%)

TABLE IV: Cross-instance CC generalization without retraining. Each entry reports Instance A F1/held-out same-family Instance B F1

Graph	Original Model	Long Context Model
ER	92.5%	93.8%
BA	62.4%	63.9%
CM	57.7%	67.5%
SBM	34.2%	70.7%
WS	31.6%	25.6%
Grid	40.9%	24.5%

TABLE V: F1-Score Retained Under Full Node Shuffling

Fig. 5: Memory-access delta distributions per graph family, before (blue) and after (orange) node shuffling for Connected Components (CC) workload.

Fig. 6: F1-score under node shuffling (L=8 vs. L=128, CC workload).

Fig. 7: Memory-access delta distributions per graph family, before (blue) and after (orange) node shuffling for PageRank (PR) workload.

Fig. 8: F1-score under node shuffling (L=8 vs. L=128, PR workload).

Fig. 9: Memory-access delta distributions per graph family, before (blue) and after (orange) node shuffling for Single-Source Shortest Paths (SSSP) workload.

Fig. 10: F1-score under node shuffling (L=8 vs. L=128, SSSP workload).

Fig. 11: Memory-access delta distributions for CC on six real-world graphs under progressive node shuffling.

Fig. 12: F1-score on six real-world graphs under node shuffling(L=8 vs. L=128, CC workload).

Long-Context Modeling

Long-context modeling studies how AI systems process, retrieve, and reason over sequences that exceed ordinary context windows.

See all 139 papers

Oct 26, 2026

CoPE-CGL: Community-aware Prototype Extraction for Replay-Free Continual Graph Learning

Continual graph learning (CGL) maintains models as graphs evolve without retraining from scratch, while mitigating catastrophic forgetting. Existing methods typically target either transductive or inductive settings and often store past subgraphs or require task identifiers at inference. We propose Community-aware Prototype Extraction for Continual Graph Learning (CoPE-CGL), a replay-free framework that uses a parameter-free structural prior, precomputed by multi-hop Laplacian smoothing, to anchor learning, memory, and inference. CoPE-CGL combines topology-infused bottleneck adaptation, community-level prototypes, and dynamic routing by majority vote over node-to-prototype matches. The default protocol assumes each test graph comes from one learned task; a node-level variant handles mixed-task graphs. Each task adds at most a constant amount of storage, with no past graph data retained. At equal storage and without task identifiers, CoPE-CGL matches the strongest replay baseline even when it receives true task identifiers: average performance (AP) is 95.17% and 95.72% versus 94.28% and 95.82% on Arxiv and CoraFull, respectively, with 5.9-14.0 times faster runtime and zero forgetting. Across four transductive and three inductive benchmarks and mixed streams, CoPE-CGL exceeds the second-best of up to eleven baselines by up to 1.41, 6.32, and 9.33 AP percentage points, respectively. It runs 1.3-7.9 times faster end-to-end than the most accurate competitor on each benchmark and scales to the largest benchmark graph. On graphs mixing two tasks, its node-level variant achieves the best AP among CGL methods. The design targets homophilic graphs with community structure.

Bo-Young Lim, Seokhwan Kim, Kisung Lee +1

Graduate School of Data Science Seoul National University of Science and Technology Seoul, South Korea · Division of Computer Science and Engineering Louisiana State University Baton Rouge, Louisiana, USA

Incremental Learning

Ask PDF

Apr 28, 2026

Incremental Strongly Connected Components with Predictions

Algorithms with predictions is a growing area that aims to leverage machine-learned predictions to design faster beyond-worst-case algorithms. In this paper, we use this framework to design a learned data structure for the incremental strongly connected components (SCC) problem. In this problem, the

n

vertices of a graph are known a priori and the

m

directed edges arrive over time. The goal is to efficiently maintain the strongly connected components of the graph after each insert. Our algorithm receives a possibly erroneous prediction of the edge sequence and uses it to precompute partial solutions to support fast inserts. We show that our algorithm achieves nearly optimal bounds with good predictions and its performance smoothly degrades with the prediction error. We also implement our data structure and perform experiments on real datasets. Our empirical results show that the theory is predictive of practical runtime improvements.

Ronald Deng, Samuel McCauley, Aidin Niaparast +5

Williams College · Carnegie Mellon University

Learning-Augmented Algorithms

Ask PDF

Oct 20, 2026

From Complex Histories to Simple Predictors: Predictive Dimension in Dynamic Graph Learning

Existing continuous-time graph learning methods rely heavily on complex neural architectures to encode ever-expanding interaction histories. However, the future conditional distribution induced by complex histories can often be characterized by a low-dimensional predictive state manifold, implying that only a few predictive degrees of freedom are essential for future interactions. We therefore argue that continuous-time graph learning should identify low-dimensional states sufficient for future prediction rather than reconstruct the full history. To make this perspective measurable, we define and independently estimate the intrinsic predictive dimension, which quantifies the effective predictive degrees of freedom required by a given task. Specifically, we remove the history-independent marginal from the history-conditioned future distribution, decompose the resulting predictive residual operator, and estimate the minimum effective rank needed to preserve the predictive power of the full history. Experiments across datasets show that model performance saturation is largely determined by the intrinsic predictive dimension. Based on this finding, we propose PreDyG, a lightweight model whose capacity is matched to the intrinsic predictive dimension. PreDyG achieves superior predictive performance with only 0.07% of the parameters of a representative complex baseline.

Hantong Feng, Duxin Chen, Wenwu Yu

School of Cyber Science and Engineering, Southeast University. · School of Mathematics, Southeast University. · Frontiers Science Center for Mobile Information Communication and Security.

Dynamic Graph Learning Predictive Representation Learning Temporal Link Prediction

Ask PDF

Abstract

Long-Context Modeling

Explore similar work

CoPE-CGL: Community-aware Prototype Extraction for Replay-Free Continual Graph Learning

Incremental Strongly Connected Components with Predictions

From Complex Histories to Simple Predictors: Predictive Dimension in Dynamic Graph Learning