# The Unreasonable Effectiveness of Randomized Representations in Online Continual Graph Learning

arXiv: https://arxiv.org/abs/2510.06819 · HTML: https://mlsanity.com/paper/2510.06819/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 51 of its 89 references that are in the map.
- First posted on arXiv 8 Oct 2025.

## Builds on (most cited first, 30 of 51)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Overcoming catastrophic forgetting in neural networks](https://mlsanity.com/paper/1612.00796/) (2016)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [Learning without Forgetting](https://mlsanity.com/paper/1606.09282/) (2016)
- [iCaRL: Incremental Classifier and Representation Learning](https://mlsanity.com/paper/1611.07725/) (2016)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Gradient Episodic Memory for Continual Learning](https://mlsanity.com/paper/1706.08840/) (2017)
- [Continual Lifelong Learning with Neural Networks: A Review](https://mlsanity.com/paper/1802.07569/) (2018)
- [Memory Aware Synapses: Learning what (not) to forget](https://mlsanity.com/paper/1711.09601/) (2017)
- [Experience Replay for Continual Learning](https://mlsanity.com/paper/1811.11682/) (2018)
- [Efficient Lifelong Learning with A-GEM](https://mlsanity.com/paper/1812.00420/) (2018)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Online Continual Learning with Maximally Interfered Retrieval](https://mlsanity.com/paper/1908.04742/) (2019)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking](https://mlsanity.com/paper/1707.03815/) (2017)
- [Online Continual Learning in Image Classification: An Empirical Survey](https://mlsanity.com/paper/2101.10423/) (2021)
- [New Insights on Reducing Abrupt Representation Change in Online Continual Learning](https://mlsanity.com/paper/2104.05025/) (2021)
- [Universal Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/1905.04943/) (2019)
- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics](https://mlsanity.com/paper/1908.02591/) (2019)
- [RanPAC: Random Projections and Pre-trained Models for Continual Learning](https://mlsanity.com/paper/2307.02251/) (2023)
- [On the Universality of Invariant Networks](https://mlsanity.com/paper/1901.09342/) (2019)
- [An Empirical Investigation of the Role of Pre-training in Lifelong Learning](https://mlsanity.com/paper/2112.09153/) (2021)
- [Overcoming Catastrophic Forgetting in Graph Neural Networks](https://mlsanity.com/paper/2012.06002/) (2020)
- [Lifelong Machine Learning with Deep Streaming Linear Discriminant Analysis](https://mlsanity.com/paper/1909.01520/) (2019)
- [How catastrophic can catastrophic forgetting be in linear regression?](https://mlsanity.com/paper/2205.09588/) (2022)
- [Online Continual Learning on Class Incremental Blurry Task Configuration with Anytime Inference](https://mlsanity.com/paper/2110.10031/) (2021)

## Built on by (most cited first, 1 of 1)

- [Continual Graph Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2610.10302/) (2026)

## Abstract (arXiv)

Catastrophic forgetting is one of the main obstacles for Online Continual Graph Learning (OCGL), where nodes arrive one by one, distribution drifts may occur at any time and offline training on task-specific subgraphs is not feasible. In this work, we explore a surprisingly simple yet highly effective approach for OCGL: we use a fixed, randomly initialized encoder to generate robust and expressive node embeddings by aggregating neighborhood information, training online only a lightweight classifier. By freezing the encoder, we eliminate drifts of the representation parameters, a key source of forgetting, obtaining embeddings that are both expressive and stable. When evaluated across several OCGL benchmarks, despite its simplicity and lack of memory buffer, this approach yields consistent gains over state-of-the-art methods, with surprising improvements of up to 30% and performance often approaching that of the joint offline-training upper bound. These results suggest that in OCGL, catastrophic forgetting can be minimized without complex replay or regularization by embracing architectural simplicity and stability.