cs.LGOct 2, 2026
SaveEfficient Memory Crystallization for Graph Learning under Non-Stationary Distribution Shifts
Organizations: State Key Laboratory of Complex & Critical Software Environment, Beihang University · Shen Yuan Honors College, Beihang University
Abstract
Deep graph learning models deployed in real-world systems often need to cope with non-stationary environments, where the underlying graph distribution drifts continually over time. Prevailing solutions rely on training auxiliary generative modules to synthesize memory graphs for cross-domain adaptation, which incurs substantial computational overhead and scales poorly under prolonged distribution shifts. We argue that a more economical path exists: rather than generating memory, one can crystallize it. To this end, we propose Efficient Memory Crystallization (EMC), a training-free test-time framework that distills each incoming graph domain into a compact, semantically faithful memory through a closed-form solution to a memory-oriented distribution-matching objective, thereby eliminating redundant domain information under continual covariate shifts. To preserve both generalizability and adaptability as the model traverses a long sequence of target domains, EMC further models inter-domain dependencies through state-evolving memories and admits a theoretically grounded, tighter generalization error bound than direct adaptation. Extensive experiments demonstrate the superior performance of EMC over state-of-the-art baselines on graphs under non-stationary distribution shifts, while reducing average runtime by 87.4% and GPU memory consumption by 92.4% relative to the recent competitor, making continual graph adaptation practical at scale.
Figures & tables
Figure 1: A general paradigm of test-time adaptation under non-stationary distribution shifts. Compared with the first row, which directly adapts the model on the test data without modeling inter-domain relations or intra-domain redundancy , the second row illustrates our EMC, which crystallizes each domain into a compact memory and explicitly considers these factors to maintain both generalizability and adaptability, thereby ensuring efficiency and effectiveness.
Figure 2: Runtime and GPU memory cost comparison between baseline GCAL and EMC.
Figure 3: The framework of EMC. (1) Multi-hop feature propagation on the input graph . (2) A closed-form solution to the memory-oriented distribution-matching objective crystallizes the domain-specific memory . (3) The state evolving field models the correlation across consecutive domains. (4) Tighter generalization error upper bounds guarantee effectiveness. (5) The adaptation loss updates the parameters .
| Dataset | Methods | Backbone: GCN | Backbone: SAGE | ||||||||||
| AP ( ) | AF ( ) | TDG ( ) | TDA ( ) | Time ( ) | GPU ( ) | AP ( ) | AF ( ) | TDG ( ) | TDA ( ) | Time ( ) | GPU ( ) | ||
| Twitch | LEBED | 51.06±0.05 | 0.24±0.05 | 51.87±0.06 | 48.90±0.04 | 114.97 | 1440.57 | 56.37±0.03 | 0.58±0.04 | 57.55±0.02 | 55.08±0.04 | 252.80 | 3652.58 |
| GCAL | 55.65±0.09 | 0.42±0.13 | 54.78±0.60 | 53.20±0.62 | 217.51 | 11159.8 | 58.20±0.35 | 0.79±0.13 | 59.65±0.39 | 57.02±0.49 | 295.11 | 8580.63 | |
| EMC | 55.95±0.15 | 0.47±0.08 | 55.56±0.13 | 55.83±0.14 | 74.64 | 854.97 | 61.62±0.12 | 0.86±0.04 | 62.02±0.13 | 60.36±0.16 | 138.02 | 2833.18 | |
| LEBED | 46.90±0.00 | -0.25±0.00 | 47.72±0.00 | 46.38±0.00 | 93.59 | 3481.53 | 46.92±0.00 | -2.20±0.01 | 48.78±0.00 | 48.39±0.01 | 94.81 | 3718.50 | |
| GCAL | 52.72±0.36 | 0.72±0.19 | 49.37±0.28 | 48.96±0.29 | 1675.2 | 17107.84 | 51.87±0.12 | 0.04±0.11 | 52.34±0.17 | 51.55±0.08 | 1356.07 | 13633.79 | |
Table 1: Performance comparison ( , mean standard deviation for five runs) on different backbones with comprehensive metrics, Runtime (s) and GPU Memory Usage (MiB). We compare EMC with the most recent 2 baselines from two categories of domain adaptation methods. ‘ ’ indicates higher is better, and ‘ ’ indicates lower is better. ‘OOM’ implies Out-Of-Memory. The best results are highlighted with bold and the runner-ups are underlined .
| Methods / Datasets | Twitch-explicit | Facebook-100 | Elliptic | OGB-Arxiv | ||||
| AP@AUC ( ) | AF ( ) | AP@ACC ( ) | AF ( ) | AP@F1 ( ) | AF ( ) | AP@ACC ( ) | AF ( ) | |
| Base Model | 53.88±0.00 | NA | 50.55±0.00 | NA | 53.97±0.00 | NA | 42.43±0.00 | NA |
| One-step Test-Time Adaptation Methods | ||||||||
| DANN [ 9 ] | 51.50±0.39 | 0.19±0.55 | 50.63±0.64 | 0.38±1.13 | 53.84±0.56 | -0.95±0.54 | 42.62±0.23 | -1.28±0.16 |
| Norm [ 20 ] | 52.65±0.00 | -2.30±0.00 | 47.62±0.00 | 0.53±0.00 | 54.67±0.00 | 0.02±0.00 | 40.21±0.00 | 0.11±0.00 |
| TENT [ 36 ] | 52.84±0.98 | -1.83±1.05 | 46.63±0.00 | 0.61±0.00 | 46.54±0.00 | 0.55±0.00 | 36.72±0.37 | -0.02±0.18 |
Table 2: Performance comparison ( , mean standard deviation for five runs) across four datasets, evaluated against baseline methods and EMC. The results of baselines are derived from the published works. ‘NA’ is short for Not Applicable, and ‘OOM’ implies Out-Of-Memory. The best results are highlighted with bold and the runner-ups are underlined .
Figure 4: Performance matrices of EMC and GCAL on different datasets.
Figure 5: T-SNE visualization of representations of the original graph and its crystallized memory.
| Dataset | Method | AP( ) | TDG( ) | TDA( ) | Time( ) | GPU( ) |
| Twitch | w/o DM | 52.12 | 53.77 | 51.35 | 99.43 | 1486.81 |
| w/o EA | 51.50 | 52.31 | 51.21 | 60.13 | 783.14 | |
| EMC | 55.95 | 55.56 | 55.83 | 74.64 | 854.97 | |
| w/o DM | 48.78 | 48.96 | 48.92 | 85.45 | 13481.55 | |
| w/o EA | 51.30 | 50.85 | 50.34 | 17.65 | 2965.72 | |
| EMC | 53.10 | 53.49 | 52.30 | 18.84 | 3006.08 |
Table 3: Ablation study results of EMC and its variants with runtime (s) and GPU usage (MiB).
Appendix figures & tables26 assets
Supplementary material from the paper’s appendix.
Appendix
| Notations | Descriptions |
| Sequence of graphs from target domains | |
| Graph from the -th target domain | |
| Adjacency matrix of with nodes | |
| Node feature of with -dim features | |
| Model parameters adapted after -th domain | |
| Normalized adjacency matrix with self-loops |
Table 4: Summary of notations and descriptions.
| Metric / #Node | 1k | 2k | 5k | 10k | 20k | 40k | 50k | 100k | 200k |
| Matrix Inversion Time (s) | 0.0077 | 0.0096 | 0.0156 | 0.0234 | 0.0974 | 0.1142 | 0.1224 | 0.3211 | 0.7121 |
| Total Processing Time (s) | 0.6414 | 1.0703 | 2.8145 | 17.7121 | 54.2386 | 184.0252 | 271.6589 | 1158.5502 | 5580.7541 |
| GPU Memory (MiB) | 11.38 | 15.17 | 29.75 | 66.17 | 181.71 | 564.07 | 829.68 | 3358.29 | 12806.52 |
Table 5: Memory-construction scaling on a single graph up to 200k nodes (memory size ). The matrix inversion in Eq. ( 6 ) stays under 1 second even at k.
| Category | Datasets | #Nodes | #Edges | #Domains |
| Regional Shifts | Twitch-explicit | 1,912 - 9,498 | 31,299 - 153,138 | 7 |
| Facebook-100 | 769 - 41,554 | 33,312 - 2,724,458 | 12 | |
| Temporal Shifts | Elliptic | 1,089 - 7,880 | 1,168 - 9,164 | 41 |
| OGB-Arxiv | 4,427 - 39,711 | 1,225 - 38,735 | 11 |
Table 6: The statistics of datasets with distribution shifts.
Figure 10: An example of the performance matrix. For the current -th domain: TDG is computed as the mean of the green elements; TDA is the mean of the pink elements; AP is the average of the elements in the last row; AF is the average of the differences between each element in the last row (excluding the last one) and the corresponding element in the previous row.
| Dataset | Methods | Backbone: GCN | Backbone: SAGE | ||||||||||
| AP ( ) | AF ( ) | TDG ( ) | TDA ( ) | Avg. ( ) | GPU ( ) | AP ( ) | AF ( ) | TDG ( ) | TDA ( ) | Avg. ( ) | GPU ( ) | ||
| Node-level Adaptation | |||||||||||||
| Twitch-explicit | GCAL | 55.65 0.09 | 0.42 0.13 | 54.78 0.60 | 53.20 0.62 | 53.99 | 11159.80 | 58.20 0.35 | 0.79 0.13 | 59.65 0.39 | 57.02 0.49 | 58.34 | 8580.63 |
| STEM | 56.66 0.05 | -0.07 0.17 | 57.35 0.07 | 55.87 0.15 | 56.61 | 7393.27 | 59.49 0.06 | -0.45 0.02 | 63.56 0.01 | 56.33 0.05 | 59.95 | 7961.84 | |
| EMC | 55.95 0.15 | 0.47 0.08 | 55.56 0.13 | 55.83 0.14 | 55.70 | 854.97 | 61.62 0.12 | 0.86 0.04 | 62.02 0.13 | 60.36 0.16 | 61.19 | 2833.18 | |
| OGB-Arxiv | GCAL | 14.15 6.94 | -1.80 2.06 | 17.90 8.58 | 13.77 5.57 | 15.83 | 22342.47 | 45.22 0.17 | 0.76 0.05 | 42.40 7.74 | 41.80 6.59 | 42.10 | 22365.84 |
Table 7: Performance comparison ( , mean standard deviation for five runs) across node-level (Twitch-explicit, OGB-Arxiv) and graph-level (Mutagenicity, FRANKENSTEIN) datasets under continual distribution shifts. “Avg.” is computed uniformly as the mean of TDG and TDA. “ ” indicates higher is better and “ ” indicates lower is better. The best results are highlighted in bold and the runner-ups are underlined .
Figure 11: Performance matrices of EMC and GCAL on different datasets.
| Domain Order | Method | AP | AF | TDG | TDA | Time (s) | GPU (MiB) |
| ENGB, ES, FR, PTBR, RU, TW | GCAL | 55.65 | 0.42 | 54.78 | 53.20 | 217.51 | 11159.8 |
| EMC | 55.95 | 0.47 | 55.56 | 55.83 | 74.64 | 854.97 | |
| RU, FR, ES, ENGB, TW, PTBR | GCAL | 53.58 | 0.18 | 52.67 | 53.32 | 217.11 | 12225.69 |
| EMC | 57.04 | 0.36 | 55.69 | 57.46 | 75.92 | 832.58 | |
| FR, PTBR, TW, ENGB, RU, ES | GCAL | 53.37 | 0.12 | 52.47 | 53.93 | 216.35 | 10304.73 |
| EMC | 57.12 | 0.46 | 55.68 | 58.20 | 73.75 | 648.62 |
Table 8: Robustness to non-monotonic domain orderings on Twitch-Explicit.
| Domain Sequence | Method | AP | AF | TDG | TDA | Time (s) | GPU (MiB) |
| ENGB, ES, FR, ENGB, ES, FR | GCAL | 53.78 | -0.21 | 53.27 | 54.62 | 209.09 | 10116.01 |
| EMC | 54.00 | 0.06 | 53.39 | 54.94 | 56.67 | 605.80 | |
| PTBR, RU, TW, PTBR, RU, TW | GCAL | 52.84 | -0.06 | 52.03 | 54.04 | 223.54 | 14332.55 |
| EMC | 53.02 | -0.17 | 52.67 | 53.96 | 95.79 | 828.53 | |
| RU, FR, ES, RU, FR, ES | GCAL | 52.11 | 0.00 | 51.25 | 52.56 | 218.63 | 12559.53 |
| EMC | 52.22 | -0.06 | 51.39 | 52.80 | 77.21 | 774.43 |
Table 9: Robustness to cyclic domain shifts on Twitch-Explicit. Domains repeat to test stability under non-monotonic drift patterns.
| Method | AP ( ) | AF ( ) | TDG ( ) | Time ( ) | GPU ( ) |
| Base Model | 53.88 | NA | NA | NA | NA |
| GCAL with VGAE | 55.65 | 0.42 | 54.78 | 217.51 | 11159.8 |
| Random subgraph sampling | 51.26 | -1.45 | 51.32 | 67.81 | 800.96 |
| Feature averaging | 52.91 | -0.85 | 52.19 | 65.56 | 783.13 |
| EMC | 55.95 | 0.47 | 55.56 | 74.64 | 854.97 |
Table 10: Comparison with alternative training-free memory construction schemes on Twitch-Explicit with GCN backbone.
Figure 12: Structural visualization of the original graph and its crystallized memory on continuous-domain Twitch graphs with GCN backbone.
Figure 13: Structural visualization of the original graph and its crystallized memory on continuous-domain Elliptic graphs with GCN backbone (Part I).
Figure 14: Structural visualization of the original graph and its crystallized memory on continuous-domain Elliptic graphs with GCN backbone (Part II).
Figure 15: Structural visualization of the original graph and its crystallized memory on continuous-domain Elliptic graphs with GCN backbone (Part III).
Figure 16: Structural visualization of the original graph and its crystallized memory on continuous-domain Elliptic graphs with GCN backbone (Part IV).
Figure 17: Structural visualization of the original graph and its crystallized memory on continuous-domain Elliptic graphs with GCN backbone (Part V).
Figure 18: Structural visualization of the original graph and its crystallized memory on continuous-domain Elliptic graphs with GCN backbone (Part VI).
Figure 19: Structural visualization of the original graph and its crystallized memory on continuous-domain Elliptic graphs with GCN backbone (Part VII).
Figure 20: Structural visualization of the original graph and its crystallized memory on continuous-domain Elliptic graphs with GCN backbone (Part VIII).
Figure 21: Structural visualization of the original graph and its crystallized memory on continuous-domain OGB-Arxiv graphs with GCN backbone (Part I).
Figure 22: Structural visualization of the original graph and its crystallized memory on continuous-domain OGB-Arxiv graphs with GCN backbone (Part II).
| Methods | Metric / #Node | 1000 | 2000 | 5000 | 10000 | 15000 | 20000 | 25000 | 30000 | 40000 |
| GCAL | Runtime (s) | 25.41 | 33 | 97.77 | 391.87 | 918.07 | 1694.24 | OOM | OOM | OOM |
| GPU Memory (MiB) | 91.11 | 304.42 | 1754.81 | 6892.91 | 15472.69 | 27462.27 | OOM | OOM | OOM | |
| EMC | Runtime (s) | 1.75 | 2.72 | 25.89 | 210.52 | 407.95 | 593.20 | 792.00 | 1207.47 | 2213.20 |
| GPU Memory (MiB) | 20.72 | 25.06 | 42.2 | 81.02 | 131.6 | 200.07 | 278.16 | 366.92 | 597.48 |
Table 11: Node scaling efficiency evaluation with runtime (s) and GPU memory usage (MiB).
| Methods | Metric / #Domain | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| GCAL | Runtime (s) | 430.04 | 1056.97 | 1713.34 | 2460.46 | OOM | OOM | OOM | OOM |
| GPU Memory (MiB) | 6892.91 | 14239.83 | 21586.75 | 28933.67 | OOM | OOM | OOM | OOM | |
| EMC | Runtime (s) | 215.35 | 431.27 | 646.81 | 863.62 | 1079.35 | 1296.11 | 1513.47 | 1730.93 |
| GPU Memory (MiB) | 81.02 | 85.92 | 90.80 | 95.71 | 104.52 | 118.21 | 131.90 | 145.59 |
Table 12: Domain scaling efficiency evaluation with runtime (s) and GPU memory usage (MiB).
| #Domain | 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 |
| GCAL GPU (MiB) | 6892.91 | 14239.83 | 21586.75 | 28933.67 | OOM | OOM | OOM | OOM |
| EMC GPU (MiB) | 81.02 | 85.92 | 90.80 | 95.71 | 104.52 | 118.21 | 131.90 | 145.59 |
| Crystallized Memory (MiB) | 4.88 | 9.76 | 14.65 | 19.53 | 24.41 | 29.30 | 34.18 | 39.07 |
Table 13: Scaling efficiency of GPU memory consumption and crystallized memory storage.
Figure 25: The sensitivity of hyperparameter .
| Dataset | AP ( ) | TDG ( ) | TDA ( ) | Time ( ) | GPU ( ) | |
| Twitch | 0.01 | 55.95±0.15 | 55.56±0.13 | 55.83±0.14 | 74.64 | 854.97 |
| 0.05 | 54.57±0.15 | 55.46±0.15 | 53.90±0.12 | 74.92 | 854.98 | |
| 0.1 | 54.57±0.15 | 55.46±0.15 | 53.89±0.13 | 74.90 | 854.97 | |
| 0.2 | 54.57±0.16 | 55.46±0.15 | 53.90±0.12 | 74.84 | 854.97 | |
| 0.3 | 54.56±0.16 | 55.46±0.15 | 53.88±0.12 | 75.09 | 854.11 | |
| 0.5 | 54.59±0.16 | 55.47±0.15 | 53.88±0.12 | 74.67 | 854.97 |
Table 14: Performance comparison of EMC under different values of across multiple metrics, with corresponding runtime (s) and GPU memory usage (MiB). ‘ ’ indicates higher is better, and ‘ ’ indicates lower is better.
More in this topic
Continual Test-Time Adaptation
Continual test-time adaptation updates pretrained models on unlabeled, changing deployment data while retaining useful knowledge across shifts.
See all 66 papers