Random Weights Beat Trained Networks in Online Learning on Graphs

Machine learning researchers have long assumed that the road to better performance runs through more training, bigger models, and increasingly sophisticated learning algorithms. A new study published in the journal Machine Learning turns that assumption on its head for one of the most demanding settings in artificial intelligence: learning continuously from streams of graph data. A team led by Giovanni Donghi of the University of Padua, together with Daniele Zambon, Luca Pasa, Cesare Alippi and Nicolò Navarin, has shown that a neural network whose weights are fixed at random values, never trained at all, can outperform state-of-the-art systems on online continual graph learning tasks, with improvements of up to 30 percent in some benchmarks. The finding, published as volume 115, article 220 of the journal, suggests that in this domain the key to remembering old knowledge may not be cleverer learning but deliberate refusal to learn at all.

The setting the researchers tackled, known as Online Continual Graph Learning, or OCGL, is among the harshest in machine learning. Nodes of a graph, which might represent Bitcoin transactions, scientific papers, social media posts or products on a shopping site, arrive one at a time in a continuous stream. Each new node brings its own attributes and connections to previously seen nodes, and the distribution of the data can shift at any moment, for instance when new classes of objects begin to appear. The model must make accurate predictions at every instant, adapt on the fly, and retain what it learned about earlier data, all under strict limits on memory and computation. Crucially, the model sees each node only once, so there is no possibility of the repeated offline training passes that standard deep learning relies on.

This streaming regime makes the phenomenon known as catastrophic forgetting especially damaging. When neural networks are updated sequentially on new data, the parameter changes that help with the new information often overwrite the representations that supported old tasks, erasing previously acquired knowledge. Graph data add a second, structural source of forgetting: because graph neural networks aggregate information from neighbors, the embedding of a node changes as new nodes attach to it, so even a perfectly stable classifier faces inputs that drift over time. Existing state-of-the-art methods typically fight forgetting with replay buffers that store examples of past data, or with regularization schemes that penalize changes to important weights, and both strategies carry substantial memory and computational costs in the graph setting.

The new approach, by contrast, decouples representation from prediction in a strikingly simple way. The authors split the model into two parts: a feature extractor that converts each node and its sampled neighborhood into a fixed-length embedding vector, and a lightweight classifier that maps embeddings to predictions. The feature extractor is a graph neural network whose weights are randomly initialized from an appropriate distribution and then frozen forever. Because the encoder never changes, the representations it produces cannot drift, and one of the two major sources of forgetting, the drift of backbone parameters, is eliminated by construction. Only the classifier is trained, and even that can be done without gradient descent using a streaming statistical method.

The researchers tested two flavors of randomized encoder. The first, called UGCN, is an untrained graph convolutional network with two layers of 1024 units each, whose layer outputs are concatenated into a 2048-dimensional node embedding that captures neighborhood information at multiple resolutions. The second, Graph Random Neural Features or GRNF, draws on theory showing that random samples from a universal family of graph neural networks can approximate kernel functions on graphs, and can provably separate any two non-isomorphic graphs. Both encoders operate on sparsified two-hop neighborhoods sampled around each node, keeping the computational footprint constant even as the graph grows denser. On top of either encoder, the team placed a Streaming Linear Discriminant Analysis classifier, which maintains running class means and a shared covariance matrix updated incrementally with each new example, requiring no memory buffer of past data at all.

The theoretical intuition behind the method is elegant. The authors formally decompose forgetting risk into three components: structural drift arising from the evolving graph itself, which no model can remove; backbone parameter drift, which the frozen encoder eliminates entirely; and classifier parameter drift, which for the streaming classifier shrinks as more examples of each class accumulate. Stability alone is not enough, of course, since a model must also remain plastic enough to absorb new classes and shifted distributions. That is where the over-parameterized random encoders earn their keep. Results from randomized network theory guarantee that, given a sufficiently large embedding dimension, randomly initialized features are expressive enough to make the downstream classification problem linearly separable, so a simple linear readout suffices.

The experimental results across seven benchmarks are remarkable. On six node-classification datasets, including the citation networks CoraFull and Arxiv, the co-purchase graph Amazon Computer, the Reddit post network, the heterophilic Roman Empire Wikipedia graph, and the Elliptic Bitcoin transaction network, the combination of randomized features and the streaming classifier generally beat every alternative considered, including experience replay, A-GEM, EWC, LwF and MAS applied to a conventionally trained graph network, as well as recent graph-specific replay methods such as PDGNN, SSM and TWP. In class-incremental streams, where new classes arrive in blocks, the approach approached the upper bound of joint offline training on the complete final graph, a ceiling that no online method can normally reach. Notably, the method needs no memory buffer, whereas replay-based competitors must store a substantial fraction of past nodes tailored to graph topology.

The robustness of the result is underlined by several control experiments. Even with as few as 64 random features, performance on most benchmarks matched or exceeded state-of-the-art trained methods, and gains had not saturated even at 4096 features. A frozen graph network pre-trained in a supervised way on part of the stream did not outperform the purely random encoder on most datasets, indicating that the advantage stems from the stability and richness of random representations rather than from any task-specific preparation. On the heterophilic Roman Empire dataset, where standard graph convolutions smooth neighboring features together, the more expressive GRNF encoder proved clearly superior. A hybrid extractor mixing features from both encoders delivered consistently robust performance across benchmarks. In memory terms, the fixed backbone plus streaming statistics occupied less space than the replay buffers of competing methods while sitting on the efficient frontier of the accuracy-versus-memory tradeoff.

The practical implications reach well beyond academic benchmarks. The Elliptic experiments, conducted on real Bitcoin transaction data with genuine timestamps in a time-incremental stream, demonstrate that the method works on realistic financial fraud detection problems where new transaction patterns emerge continuously. The same properties make the approach attractive for intrusion detection in Internet of Things networks, healthcare monitoring on temporal patient graphs, and recommendation systems, all applications the authors cite as motivation. Because the classifier updates are cheap streaming statistics and the encoder requires no training whatsoever, the method is naturally suited to deployment where latency is critical and predictions must be available at any moment. The authors caution that their conclusions are specific to the online setting, that a full theoretical analysis of forgetting remains future work, and that extensions to graph-level and edge-level tasks, regression and anomaly detection are still open. But the central message is already provocative: sometimes the most effective way for an artificial intelligence to remember is to stop changing its mind.

Subject of Research: Randomized fixed representations for mitigating catastrophic forgetting in online continual graph learning

Article Title: The Unreasonable Effectiveness of Randomized Representations in Online Continual Graph Learning

Article References: The Unreasonable Effectiveness of Randomized Representations in Online Continual Graph Learning. (n.d.). https://doi.org/10.1007/s10994-026-07128-5

Image Credits: AI Generated

DOI: 10.1007/s10994-026-07128-5

Keywords: continual learning, graph neural networks, catastrophic forgetting, online learning, randomized representations, streaming linear discriminant analysis, node classification, experience replay, graph representation learning, concept drift, machine learning, Bitcoin fraud detection