Efficient Memory Crystallization for Graph Learning under Non-Stationary Distribution Shifts

1 Introduction

• Test-time adaptation must address continual target-distribution drift without source data, while avoiding inductive bias, catastrophic forgetting, and degraded generalization to future domains.Existing continual replay methods often rely on labels, which are unavailable in the test-time setting; GCAL's separately trained generator adds computational overhead.Source: §1 · pp. 1–2
• Figure 1 contrasts direct test-data adaptation, which ignores inter-domain relations and intra-domain redundancy, with EMC's compact-memory approach.The EMC framework combines multi-hop propagation, closed-form memory construction, state evolution, generalization analysis, and parameter adaptation.Source: Figure 1 · p. 2, Figure 3 · p. 3
• EMC replaces separately trained memory generation with closed-form crystallization of each incoming graph domain into compact, semantically faithful memory.The framework also models inter-domain dependencies through state-evolving memories without additional model training at test time.Source: §1 · pp. 2–3
• EMC uses 87.4% less runtime and 92.4% less GPU memory on average than GCAL across datasets under continual drift.Figure 2 compares runtime and GPU memory cost between GCAL and EMC.Source: Figure 2 · p. 2, §1 · p. 2

2 Preliminaries

• The target data is a sequence of graph samples, each representing a domain in its arrival order, and the model is continually updated from Θt−1 to Θt.The pretrained GNN is trained on one or more source graphs; target labels are drawn from the label set.Source: §2 · p. 3
• The adaptation objective is to maintain generalizability and adaptability on target samples while mitigating catastrophic forgetting on previously encountered domains.The setup assumes source data is available for pretraining, while target domains arrive as a continual test-time sequence.Source: §2 · p. 3
• Under the covariate-shift assumption, source and target graph distributions differ while their conditional label distributions given graphs are equal.Formally, PS(G) ≠ PT(G) and PS(Y |G) = PT(Y |G).Source: §2 · p. 3

3.1 Efficient Memory Crystallization

• Non-parametric multi-hop propagation smooths node features and captures more global structural information before memory construction.The normalized adjacency includes self-loops, and the propagation can be replaced by alternatives such as SGC or personalized PageRank.Source: §3.1 · p. 4
• Class-wise partitioning uses predicted semantics as anchors and confidence-weighted aggregation to preserve semantic structure in a low-rank surrogate graph.The memory-oriented distribution-matching objective aligns essential semantic information; similarity thresholding constructs its graph structure, while a Dirichlet-energy constraint smooths reconstructed features.Source: §3.1 · pp. 4–5
• A closed-form solution reconstructs memory features from propagated class embeddings, with memory size set to 1% of the original graph in experiments.The solution uses Q = ˆA′K and a Laplacian smoothness term; its smaller system makes memory construction lightweight and scalable.Source: §3.1 · p. 5

3.2 Memory-Driven Adaptation with Tighter Bound

• The state-evolving field combines consecutive domain memories with a convex combination to model temporal correlations during adaptation.The weights are fixed non-negative hyperparameters selected by grid search; the stated bound holds for any valid choice.Source: §3.2 · p. 5
• Crystallized-memory and state-evolving-memory generalization bounds are tighter than direct-adaptation bounds; the former removes the explicit source–target H-divergence penalty.The adaptation loss also uses KL regularization on stored memories; under the stated assumptions, small parameter updates imply small predictive shifts on those memories, providing a theoretical rationale for mitigating forgetting.Source: §3.2 · p. 6

4.1 Experimental Setup

• Across four datasets, the evaluation treats each graph as a domain, pre-trains on selected source domains, and continually adapts on the remaining domains using dataset-specific metrics.The datasets cover regional shifts (Facebook-100 and Twitch-Explicit) and temporal shifts (OGB-Arxiv and Elliptic).Source: §4.1 · p. 7

4.2 Overall Performance Comparison (RQ1)

• EMC maintains strong generalizability and adaptability; on Elliptic it reduces runtime 96.78% and GPU memory 96.58%, and on OGB-Arxiv 98.19% and 98.25%, respectively.The Elliptic results use GCN, while OGB-Arxiv uses SAGE.Source: §4.2 · p. 8
• EMC extends comparisons to 10 representative baselines and other adaptation granularities, with results supporting strong effectiveness without sacrificing memory efficiency.The comparisons include GCAL and STEM on node-level and graph-level adaptation.Source: §4.2 · p. 8
• EMC mitigates forgetting across continual target domains, and its original-graph and memory embeddings are closely aligned in representation space.The t-SNE comparison is for continuous-domain Twitch graphs.Source: §4.2 · pp. 8–9, Figure 5 · p. 9

4.3 Scaling Efficiency Analysis (RQ2)

• When node counts exceed 40k, GCAL and LEBED encounter OOM, while EMC stays within GPU limits; crystallization alone takes 0.71s on a graph with up to 200k nodes.The scaling experiments vary node and domain counts and plot runtime and peak GPU memory.Source: §4.3 · p. 9, Figure 6 · p. 9, Figure 7 · p. 9

4.4 Ablation Studies (RQ3)

• EMC outperforms both ablated variants; removing domain-specific memory harms efficiency and effectiveness, while removing memory-driven adaptation saves resources but degrades adaptation.The ablations compare runtime and GPU usage alongside effectiveness.Source: §4.4 · p. 9, Table 3 · p. 9

4.5 Parameter Study (RQ4)

• EMC is robust to reasonable α choices, though tuning matters for optimal performance; performance is sensitive to β, which controls memory replay importance during adaptation.The α analysis varies it from 0.3 to 5.0.Source: §4.5 · pp. 9–10, Figure 8 · p. 10, Figure 9 · p. 10

Graph Continual Learning

• Graph continual learning methods include regularization, parameter isolation, and memory replay, but generally assume labeled training data.Examples include TWP and RieGrace, HPNs, and ER-GNN and SSM, respectively.Source: §5 · p. 10

Graph Domain Adaptation

• Graph domain adaptation transfers knowledge from labeled source domains to related targets, while continual test-time adaptation addresses continuously drifting target domains.GCAL trains an auxiliary VGAE to generate replay memories, adding costs that scale poorly under prolonged drift.Source: §5 · p. 10
• EMC instead crystallizes each incoming domain in closed form and models inter-domain relationships with state-evolving memories, without an auxiliary trainable test-time component.The paper identifies overlooked continual shifts and semantically irrelevant redundancy within domains as gaps in existing methods.Source: §5 · p. 10

• EMC crystallizes each incoming graph domain into compact, semantically faithful memory through a closed-form solution.Source: §6 · p. 10
• State-evolving memories model inter-domain dependencies and yield provably tighter generalization error bounds.Source: §6 · p. 10
• EMC outperforms state-of-the-art baselines while reducing average runtime 87.4% and GPU memory 92.4% relative to GCAL.Source: §6 · p. 10

A Notations

• The notation distinguishes G_t, the graph arriving at step t, from G_(t), a generic past or current domain graph.Source: A Notations · p. 14

B Algorithm

• At each step, EMC constructs a memory and state-evolved representation before updating parameters; a KL term regularizes predictive shifts on stored memories.The KL term serves as an anti-forgetting regularizer with the stability guarantee of Proposition 3.7.Source: B Algorithm · p. 14

B.1 Complexity Analysis

• Memory construction includes pairwise similarity at O(N′_t^2 d) and regularized least-squares inversion at O(N′_t^3); memory size can be only 1% of the original graph.The appendix describes feature propagation, redundancy-eliminated memory construction, state evolution, and parameter update.Source: §B.1 · p. 15

12 end

• GCAL adds per-step VGAE encoding and decoding, dual graph forwards, gradient matching, and inner-loop costs, making it less practical for long-horizon or resource-constrained settings.Source: §12 · p. 16

B.2 Analysis of Scalability on Memory Construction

• At Nt=200k, matrix inversion remains under 1 second, while total processing scales near-linearly in the dominant propagation term.The scaling experiment fixes memory size at 1% of input nodes.Source: §B.2 · p. 17, Table 5 · p. 17

B.3 Semantic-Anchor Aggregation at Test Time

• Four design choices stabilize test-time semantic aggregation: covariate-shift consistency, non-supervisory anchors, K-hop denoising, and Dirichlet regularization.EMC is reported to outperform baselines on all four datasets, including datasets with abrupt or year-by-year temporal shifts.Source: §B.3 · pp. 17–18

C.1 Reformulation of Distribution Matching

• EMC matches propagated representations of each graph and its memory, using similarity-thresholded memory structure and a Dirichlet-energy constraint to keep reconstructed features smooth.The threshold τ sparsifies the memory graph, while α controls smoothness.Source: §C.1 · pp. 18–19

C.2 Proof of Proposition C.2

• The memory-feature reconstruction objective has the closed-form solution X′ = (Q⊤Q + αL′)^−1Q⊤H′, with Q = Â′^K.The convex objective's solution operates on the compact memory system rather than the full input graph, decoupling construction cost from input scale.Source: §C.2 · p. 19

C.3 Proof of Proposition 3.3

• Marginal graph-memory alignment equals joint alignment if and only if the domains and their memories are temporally independent.Because continual-drift domains are generally correlated, marginal alignment alone is insufficient, motivating state-evolving memories.Source: §C.3 · p. 20

C.4 Proof of Error Upper Bounds

• The bounds characterize each adaptation step, while continual behavior across target domains is handled separately by state evolution and a stability bound.The analysis uses the empirical distribution of the current target graph for PT.Source: §C.4 · p. 21
• With state-evolving memories, the error bound remains tighter than the direct-adaptation bound throughout continual adaptation.The theorem considers a convex combination of hypotheses from consecutive target domains.Source: §C.4 · p. 23
• Crystallized-memory adaptation has a tighter error bound than direct source-to-target adaptation, with a gap of at least dH(ṔS, ṔT).The bound removes the explicit H-divergence penalty present in the direct-adaptation bound.Source: §C.4 · pp. 22–23

C.5 Proof of Proposition 3.7

• The stability bound assumes softmax predictions with temperature τ, class probabilities bounded below by γ, and parameter-space Lipschitz encoder and classifier.Under these assumptions, small parameter updates imply bounded changes in predictive behavior on stored memories.Source: §C.5 · pp. 23–24
• Entropy minimization targets confident predictions on the current graph, while KL regularization constrains prediction changes on previously stored memories.The two terms therefore address current-domain adaptation and stability on past domains, respectively.Source: §C.5 · pp. 24–25

D.1 Dataset Description

• Across datasets, a GNN is pretrained on a small set of labeled graphs and then adapted online to remaining unlabeled graphs.The four benchmarks cover regional and temporal shifts, and each graph is treated as an individual domain.Source: §D.1 · p. 25
• Facebook-100 and Twitch-Explicit provide regional shifts, with selected university graphs or the German Twitch graph used for pretraining and other unlabeled regional graphs used for adaptation.Facebook adaptation uses eleven other university graphs; Twitch adaptation uses the remaining regional graphs.Source: §D.1 · p. 25
• OGB-Arxiv and Elliptic provide temporal shifts through sequential adaptation across publication years or Bitcoin transaction snapshots.OGB-Arxiv pretraining uses papers published before 2011; Elliptic pretraining uses snapshots 7–9.Source: §D.1 · p. 25

D.2 Baseline Details

• Ten baselines span one-step methods and continual methods, with non-graph-specific approaches adapted to GNN architectures for comparison.Continual baselines include CoTTA, EATA, GCAL, and STEM; GCAL trains an auxiliary VGAE to generate memory graphs.Source: §D.2 · pp. 25–26

D.3 Experimental Setting

• Generalizability measures performance retention on previously seen domains, while adaptability measures performance gain on a newly encountered domain.Figure 10 illustrates these concepts; its caption defines AP from the last performance-matrix row and AF from differences between that row and the preceding row.Source: §D.3 · p. 26
• The experiments use a 2-layer GCN on three datasets and GraphSAGE on OGB-Arxiv, with memory size set to 1% of input nodes.Adaptation runs for 1–10 epochs per domain; results average five independent runs.Source: §D.3 · p. 26
• The protocol uses a performance matrix whose entries track performance on domain j after training on domain i, with ROC-AUC, Accuracy, or F1 Score selected by dataset.The reported metrics are derived from this matrix.Source: §D.3 · pp. 26–27

D.5 Performance Comparison under the GCAL Setting

• The comparison covers ten one-step and continual baselines under the GCAL setting, with STEM results available only for Twitch-explicit and OGB-Arxiv.The remaining two STEM dataset entries are marked Not Applicable.Source: §D.5 · p. 27
• EMC achieves the best AP on Facebook-100, Elliptic, and OGB-Arxiv and the best AF on all four datasets.On Twitch-explicit, STEM has slightly higher AP but negative AF, whereas EMC maintains positive AF across all datasets.Source: §D.5 · p. 27

D.6 Extended Performance Comparison across Node- and Graph-level Tasks

• EMC achieves the best Avg. on five of eight dataset-backbone combinations and runner-up on the other three, across node- and graph-level tasks.It also achieves the best AF in most settings.Source: §D.6 · p. 28
• On graph-level tasks, EMC uses a few hundred MiB while STEM exceeds 10,000 MiB on both Mutagenicity and FRANKENSTEIN.The paper attributes the gap to auxiliary-module costs that grow with graph size, unlike EMC's analytically solved memory.Source: §D.6 · p. 28

D.7 Additional Performance Matrices

• Figure 11 shows EMC retaining performance on earlier Twitch-Explicit and Elliptic domains as GCAL degrades; Facebook-100's sixth-domain dip recovers on subsequent domains.The dip is attributed to a larger covariate shift, while overall AP and AF remain ahead of baselines.Source: Figure 11 · p. 28, §D.7 · p. 28

D.8 Robustness to Different Domain-Shift Patterns

• Under reordered and cyclic target shifts, EMC outperforms GCAL with lower runtime and GPU memory; the theoretical result holds for any valid convex weights.The tests vary the order of six Twitch-Explicit target domains and repeat domains cyclically.Source: Table 8 · p. 29, Table 9 · p. 29, §D.8 · p. 29

D.9 Memory Construction Alternatives

• Table 10 compares training-free memory alternatives: random sampling and feature averaging have comparable costs to EMC but lower performance, with feature averaging below the base model.The authors conclude EMC's crystallized memories are inexpensive and semantically faithful.Source: §D.9 · p. 29, Table 10 · p. 30

D.10 Additional Visualizations of Crystallized Memories

• Structural renderings cover continuous-domain Twitch and Elliptic GCN graphs; crystallized layouts closely trace originals, while their embeddings remain aligned.Original graphs are sampled at a fixed rate for legibility, while crystallized memories are rendered in full.Source: §D.10 · pp. 29–30, Figure 12 · p. 30

Node Scaling Analysis

• When graphs exceed 40k nodes, GCAL runs out of memory, while EMC remains within GPU limits at the largest tested scale.The node-scaling analysis fixes 10 target domains and increases graph size from 1k to 40k nodes.Source: §D.11 · p. 30

Domain Scaling Analysis

• When the stream reaches 50 or more domains, GCAL runs out of memory, while EMC maintains stable runtime and GPU usage across tested scales.Table 12 reports runtime and GPU memory usage in MiB.Source: §D.11 · p. 30

Node Scaling Analysis

• The standalone crystallization step's closed-form inversion takes under one second on a single graph of up to 200k nodes.The authors report that this step is not the pipeline bottleneck.Source: §D.11 · p. 30

Storage Cost of Crystallized Memories

• At 80 domains, EMC requires 145.59 MB of GPU memory and 39.07 MB for crystallized-memory storage; GCAL runs out of GPU memory at 50 domains.Crystallized-memory storage grows with stream length but remains small in absolute size.Source: §D.11 · p. 30

Discussion on Memory Budgeting

• A capped memory buffer could use FIFO retention, similarity-based selection, weighted averaging, or low-cost merging and re-crystallization of older memories.The paper states that merging older memories can yield constant storage, unlike generative replay without generator retraining.Source: §D.11 · p. 31

D.12 Additional Results of Parameter Study

• EMC remains robust as τ varies from 0.5 to 1.0, although tuning τ can improve performance.τ controls graph sparsification; Figure 25 presents its sensitivity analysis.Source: §D.12 · p. 31, Figure 25 · p. 35
• Memory-size scaling has a minor effect on adaptation performance and negligible effect on runtime and GPU memory cost.The main paper uses λ = 0.01; the analysis varies λ to assess memory size.Source: §D.12 · p. 31, Table 14 · p. 35

E Broader Impacts

• EMC may support lower-cost graph-learning deployments under continual distribution shifts, and the authors foresee no specific negative societal impacts beyond those general to applied machine learning.The paper cites applications including social networks, recommendation systems, citation analysis, and financial transaction monitoring.Source: E Broader Impacts · p. 32
• EMC uses one fixed hyperparameter configuration per dataset and does not explicitly measure drift to set adaptation strength, which may limit adaptation when shifts vary substantially.The authors identify dynamic hyperparameter adjustment and drift-aware adaptation as future directions.Source: E Broader Impacts · p. 32

NeurIPS Paper Checklist

• The checklist states that experimental details are disclosed, datasets are public and code is available, and results are averaged over five random seeds with metric variance reported.Source: NeurIPS Paper Checklist · pp. 37–38

10. Broader impacts

• The checklist says the paper addresses potential positive and negative societal impacts in Appendix E and poses no special risk requiring release safeguards.Source: §10 · pp. 39–40
• The paper reports that it releases no new assets.The checklist marks documentation of new assets as not applicable because none are released.Source: §10 · p. 41
• The paper reports no crowdsourcing or human-subject research, and marks participant-risk and IRB reporting as not applicable.Source: §10 · p. 41
• The paper states that LLMs are not an important, original, or non-standard component of its core method development.Source: §10 · p. 42