The Unreasonable Effectiveness of Randomized Representations in Online Continual Graph Learning

Abstract 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. Similar content being viewed by others 1 Introduction In Online Continual Graph Learning (OCGL), nodes arrive sequentially, are observed only once, and undergo drifts in both distribution and task to solve (Donghi et al., 2025). Therefore, models must adapt to new operating conditions on the fly, while making anytime predictions and retaining past knowledge from limited observations, and under strict memory and latency constraints. This makes OCGL one of the most challenging continual learning scenarios. This setting poses several additional requirements to the traditional Continual Learning (CL) (Parisi et al., 2019; De Lange et al., 2022; Van De Ven et al., 2022), Online CL (Mai et al., 2022), and Continual Graph Learning (CGL) (Zhang et al., 2022a). Successfully handling these requirements would enable applications that require fast adaptations and anytime predictions (Koh et al., 2021) such as in healthcare (Le Baher et al., 2023), IoT intrusion detection (Lin et al., 2024) and financial markets (Weber et al., 2019), other than modeling citation networks (Liu et al., 2021; Zhou & Cao, 2021), transportation networks (Chen et al., 2021) and recommender systems (Caroprese et al., 2025). In this paper, we introduce a simple, yet surprisingly effective approach for node-level OCGL, decoupling node representations from the predictive model, and yielding excellent prediction accuracy while taming the forgetting of previously learned concepts. Our approach leverages the effectiveness of randomized and over-parametrized architectures to provide rich, untrained representations, combined with a lightweight trained classifier on top (Rahimi & Recht, 2008; Rudi & Rosasco, 2017; Scardapane & Wang, 2017). As demonstrated in related literature, fixed representations from pre-trained models help prevent forgetting at the feature extraction level even when used in CL for image classification (Hayes & Kanan, 2020; Pelosin, 2022; Mehta et al., 2023). The beneficial effect appears to be even more striking in graphs, where stable neighborhood embeddings eliminate the need to retain the entire topological information for replay strategies (Zhang et al., 2024a). Additionally, the literature on randomized models provides us results that ensure good approximation and generalization properties for this family of models, given that we use a sufficiently large embedding dimension (Scardapane & Wang, 2017). Coupled with a Streaming Linear Discriminant Analysis (SLDA) classifier (Hayes & Kanan, 2020), this approach generally outperforms state-of-the-art OCGL methods, without the need for a memory buffer. Our main contributions are the following. - 1. We propose a surprisingly strong OCGL method. A simple, yet effective method coupling principled untrained features with a lightweight streaming classifier, granting both expressivity and forgetting-resilience. - 2. We demonstrate how the approach achieves generally best results across seven OCGL benchmarks, in both class-incremental and time-incremental setups. - 3. We theoretically motivate our research findings, albeit without hard results or bounds, paving the way for the development of new, simpler CL methods without compromising on accuracy. Beyond providing a strong new method with said advantages, our findings suggest that future OCGL research should rethink model designs, emphasizing architectural simplicity and stability. 2 Related Works In this section, we first outline the specifics of Online Continual Learning for graphs, the setting used for our experiments, distinguishing it from related paradigms. We then discuss randomized neural models and other fixed feature extraction strategies in Continual Learning. These concepts provide context for the problem addressed in the paper and motivate our design choices. 2.1 Online Continual Learning for Graphs Continual Learning has been studied mainly in domains such as computer vision (Rebuffi et al., 2017; Lopez-Paz & Ranzato, 2017) or reinforcement learning (Kirkpatrick et al., 2017; Rolnick et al., 2019), with clearly defined task boundaries and no dependencies between successive tasks. In contrast, working on a node level in a graph domain introduces structural dependencies between data points, complicating the definition of the task. Continual Graph Learning (CGL) (Febrinanto et al., 2023; Yuan et al., 2023; Zhang et al., 2024b) extends CL to graph settings, and assumes that the graph is presented in blocks, that is, as subsets of nodes connected in subgraphs (Zhang et al., 2022a). Several methods for CL on graph data have been proposed (Zhou & Cao, 2021; Liu et al., 2021, 2023; Hoang et al., 2023; Sun et al., 2023; Cui et al., 2023), yet, similarly to traditional CL, state-of-the-art performance is achieved by replay-based methods which leverage a memory buffer tailored to graph topology (Zhang et al., 2022b, 2024a). However, the use of Graph Neural Network (GNN) (Scarselli et al., 2009; Micheli, 2009; Kipf & Welling, 2017) models poses an issue regarding task separation: nodes form connections also with nodes that were observed in past tasks, thus requiring access to past information due to message passing (Gilmer et al., 2017). This is sometimes addressed by ignoring inter-task edges (Zhang et al., 2022a), yet it is an unrealistic solution since it assumes supervisory information in the form of task identifiers also at test time. On the other hand, due to small-world nature of most real-world graphs, accessing the entire neighborhood information of the nodes would likely mean using the entirety of past data, rendering the use of the CL approach less meaningful. In this context, a more principled setting is Online Continual Graph Learning (OCGL) (Donghi et al., 2025), which bridges the gap between existing research on online CL and CGL. This setting addresses the issue of access to node neighborhoods with the use of neighborhood sampling, to keep a constant computational footprint even as the graph gets denser over time. In particular, the online setting for CL entails a single pass over the streaming data (Chaudhry et al., 2018; Mai et al., 2022; Soutif-Cormerais et al., 2023), in contrast to traditional offline CL where training is done offline in a batched setting on each task (De Lange et al., 2022). This constraint, together with stricter computational and memory requirements, is motivated by applications where quick model adaptation is necessary, and anytime predictions may be required (Koh et al., 2021), thus impeding the task-wise offline training. In this challenging OCGL setting, a simple baseline consisting of immediate neighborhood aggregation with a linear model and experience replay, LINEAR (Donghi et al., 2025), was shown to be competitive with the state-of-the-art due to its stability. 2.2 Randomized Representations In the literature on neural networks, multiple approaches have leveraged some form of randomization, due to training efficiency, and often theoretical guarantees (Scardapane & Wang, 2017). Notable examples for vector data are Random Vector Functional-Link networks (RVFL) (Pao & Takefuji, 1992; Pao et al.., 1994), Extreme Learning Machines (ELM) (Huang et al., 2006, 2015) and Echo State Networks (ESN) (Jaeger & Haas, 2004). These fix most network parameters randomly, from an appropriate distribution, training only lightweight readouts. Theoretical results such as universal approximation properties and generalization guarantees have been proved for some of these architectures (Liu et al., 2012). Randomized strategies have also been explored for kernel approximation, such as with Random Fourier Features (RFF) (Rahimi & Recht, 2007), a randomized projection that approximates the RBF kernel. Some works have also explored randomized strategies for graph data, such as with GESN (Gallicchio & Micheli, 2010) or MRGNN (Pasa et al., 2022). Different instantiations of untrained Graph Convolutional Networks (Kipf & Welling, 2017) have been proposed in recent years: GCELM (Zhang et al., 2020) uses a single GCN layer, with randomly initialized and fixed parameters. GCN-RW (Huang et al., 2023) improves on this approach by considering an increased receptive field, employing the square of the adjacency matrix for aggregation. The more recent UGCN (Navarin et al., 2023a) instead uses multiple GCN layers, followed by non-differentiable pooling, as the network does not need to be trained. Inspired by RFF, GRNF (Zambon et al., 2020) are derived from expressive GNN architectures, and constitute a family that can separate graphs. 2.3 Fixed Feature Extraction for CL Some works in the CL literature for image classification suggest the use of a frozen CNN backbone, pre-trained on a different dataset, and then training continually only a classifier such as a simple MLP (Van De Ven et al., 2022; Mehta et al., 2023). In the context of graph data, this approach is not currently feasible, as it is not trivial to obtain pre-trained GNNs that can handle graphs with different input feature domains, even though there is ongoing promising work on graph foundation models (Wang et al., 2025). Additionally, despite the many randomized approaches for representation extraction, only a very limited number of CL papers rely on them, and only with image classification tasks. CRNet (Li & Zeng, 2023) uses a randomly initialized network for feature enhancement, usually on top of a pre-trained network, training the classification head via closed-form solution on each task with regularization to ensure minimal forgetting. RanPAC (McDonnell et al., 2023) uses random projections of features extracted with a pre-trained model with the objective of increasing dimensionality to facilitate class separation. More recently, RanDumb (Prabhu et al., 2024) leverages Random Fourier Features (Rahimi & Recht, 2007) used with nearest class mean classification. While these works share a similar design philosophy to ours, questioning the necessity of continual representation learning, they focus on Euclidean domains with independent data, and only RanDumb is an online method. In this study we thus focus on the more challenging OCGL setting, where representations need to account also for neighboring information, as well as possible shifts of graph topology. On the other hand, there have been some works that investigated theoretically the use of linear models in simple CL setups (Evron et al., 2022, 2023; Ding et al., 2024), leading us to adopt these simple classifiers. Furthermore, it has been observed that prototype based classifiers, such as nearest class mean, are particularly suited for online CL, due to being schedule-robust, i.e. independent from stream ordering (Wang et al., 2022). 3 Method The OCGL setting (Donghi et al., 2025) considers an incremental graph \({\mathcal {G}}\), induced by a stream of nodes \(v_1, v_2, \ldots , v_t, \ldots\) that are added one by one. At each time step t, the graph is updated with neighborhood and attribute information about the incoming node \((v_t, \mathcal {N}(v_t), {\varvec{x}}^t)\), obtaining an updated graph snapshot \( {{\mathcal {G}}^{(t)} = ({\mathbb {V}}^{(t)}, \mathbb {E}^{(t)}, {\varvec{X}}^{(t)})}\). For example, in the Elliptic dataset (Weber et al., 2019), when a new transaction is processed, its information is captured as node features, and payment flows indicate connections. The goal is to learn a model \(F_{\Theta }\) to make node-level predictions \( {\hat{y}_{v}^{(t)}}\) for given node v at time step t given information coming from its neighboring nodes in \(\mathcal {G}^{(t)}\). Specifically, models are trained with a single pass over the node stream, using information from the associated l-hop ego-graph \( {{\mathcal {G}}^{(t,l)}_{v_t}}\). The online setting requests bounded memory and computational cost at each time steps, even as the graph grows. Accordingly, only a subset \( {\widetilde{\mathcal {G}}^{(t,l)}_{v}}\) of the ego-graph may be allowed to produce prediction In the context of CL, the node stream can encompass diverse drift patterns, such as those triggered by a class-incremental setting. Nonetheless, model predictions may be requested for nodes observed in the past, but with updated neighborhoods, therefore requesting the model not only to adapt to evolving graph conditions but also to preserve previously learned knowledge. While in the present paper we focus on node-level classification tasks, other formulations such as node regression, or edge-level tasks could be explored, which we leave as future works. A related scenario is also Continual Anomaly Detection (Cai et al., 2025; Zhang et al., 2026), where the goal is to identify deviations from a distribution, to which several of our motivating applications (such as intrusion detection and financial fraud, e.g. Elliptic) naturally map. In realistic deployments task boundaries are unknown, giving a task-agnostic CAD stream that mirrors our setting (Pezze et al., 2025; Coil et al., 2026). Our approach should adapt naturally, due to the already established use of the randomized backbones for anomaly detection (Zambon et al., 2022) and for the density-estimation based classifier we use. 3.1 Proposed Solution To address forgetting in the OCGL setting, we propose a decoupled approach to node prediction, inspired by the success of LINEAR for OCGL (Donghi et al., 2025) and of fixed feature extractors for CL (Sect. 2.3). In this setup, model \(F_\Theta = \Phi \circ \Psi\) decomposes as a node feature extractor \(\Psi\) followed by a node-level predictor \(\Phi\). Feature extraction is performed by a fixed (randomly initialized) backbone \(\Psi\): where \(\smash {{\varvec{z}}_v^{(t)}} \in \mathbb {R}^d\) denotes the node embedding that captures neighborhood information. As \(\Psi\) is untrained, it does not change over time and is inherently immune to forgetting. Secondly, it offers a clear advantage for experience replay methods, as storing \({\varvec{z}}_v^{(t)}\) is significantly more memory-efficient than storing the entire sampled neighborhood \( {\widetilde{\mathcal {G}}^{(t,l)}_{v}}\). Feature extractor \(\Psi\) also mitigates other sources of forgetting. Unlike trained models, which tend to produce task-specific representations that remove task-irrelevant information, a well-chosen \(\Psi\) can produce rich node embeddings suitable for multiple tasks. Notably, theoretical results (Rudi & Rosasco, 2017) show that for some families of model architectures, a random initialization of \(\Psi\) yields linearly separable embeddings, allowing to effectively solve the downstream task by simple linear predictive models which are less prone to forgetting than deep networks (Mirzadeh et al., 2022) and can be learned efficiently. 3.2 Randomized Feature Extraction We consider two different types of graph feature extractors \(\Psi\), or backbones, for our experiments, untrained GCN (Navarin et al., 2023a) and Graph Random Neural Features (Zambon et al., 2020) adapted to the node-level, which we discuss here. They were chosen as representative random feature extractors, yet, in general, any randomized graph network with sufficient expressivity and robustness to limited structural shifts can be adopted for our decoupled approach, bringing its own inductive biases that may be more effective for some datasets and less for others. 3.3 UGCN As first feature extractor, we use the recent UGCN (Navarin et al., 2023a), which uses multiple GCN layers \({\varvec{H}}^{(i)} = tanh(\tilde{{\varvec{A}}} {\varvec{H}}^{(i-1)} \Theta )\), where \(\tilde{{\varvec{A}}}\) is the normalized adjacency matrix, with \({\varvec{H}}^{(0)}={\varvec{X}}\) and with weights initialized with a Glorot uniform approach (Glorot & Bengio, 2010) regulated by a gain hyperparameter, and successively left untrained. In our case, since we adopt it for node-level predictions instead of graph-level ones, we do not use the entire adjacency matrix, but the efficient forward propagation limited to the node ego-graph of Hamilton et al. (2017). The output of the different layers is then concatenated to obtain an embedding that reflects information at multiple resolutions, i.e. In an over-parameterized regime, this model performs competitively with trained GCN counterparts on graph classification (Navarin et al., 2023b; Donghi et al., 2024). 3.4 GRNF Graph Random Neural Features (Zambon et al., 2020) define expressive embeddings for attributed graphs, derived from a GNN model which is a universal approximator of graph functions (Keriven & Peyré, 2019; Maron et al., 2019). Each GRNF is a parametric map \(\psi (\cdot , {\varvec{w}}): {\mathcal {T}}^2 \rightarrow \mathbb {R}\) defined by the composition of equivariant and invariant affine maps, interleaved with non-linearity: where \(\omega = (k, \theta _F, \theta _H)\), and k represents tensor order (formal definitions of \(F_{2,k}\) and \(H_k\), and more details can be found in Zambon et al. (2020)). Interestingly, the family of GRNF can separate graphs, meaning that for any non-isomorphic graphs \({\mathcal {G}}_1, {\mathcal {G}}_2\), there exists \(\omega\) such that \(\psi _{\omega }({\mathcal {G}}_1) \ne \psi _{\omega }({\mathcal {G}}_2)\). Thus, under suitable assumptions on the distribution of \({\varvec{w}}\), the family of GRNF induces a metric distance on graphs, with also results that hold in probability for a fixed number of features (Zambon et al., 2020). To adapt GRNF to make node level predictions, we use them on \( {\widetilde{\mathcal {G}}^{(t,l)}_{v}}\), and since the output is permutation invariant over the entire ego-graph, we concatenate it to the component relative to v of the output of the equivariant map, using d/2 independent draws of \(\omega\), resulting in a d-dimensional embedding (assuming even d). 3.5 Linear Classifier As indicated in Eq. (3), the extracted features are fed to a linear layer, which can be trained continually on the stream. Effectively, thanks to this strategy we have simplified the Continual Graph Learning problem by eliminating the graph specificity, relegating it to the fixed feature extractor, and reducing the problem to Continual Learning on vectors. A linear layer may thus be trained with gradient descent, supported by any standard CL learning strategy, such as experience replay which can now leverage informative node embeddings. Furthermore, we can also address forgetting in the linear classifier by adopting a specific form which does not require gradients: we use Streaming Linear Discriminant Analysis (SLDA) (Hayes & Kanan, 2020), which learns by accumulating class means, independently for each class. This choice makes training more efficient and provides further robustness against catastrophic forgetting risk, as further discussed in Sect. 3.6. Specifically, during training, SLDA keeps a cumulative mean \(\mu _k\) and count \(c_k\) for the features of each class k, and a shared covariance matrix \(\Sigma\) with streaming updates. With each new datapoint \(({\varvec{z}}_t, y)\), mean vector and counts are updates as while the covariance matrix is updated as To make predictions, using precision matrix \(\Lambda = [(1-\epsilon )\Sigma + \epsilon {\varvec{I}}]^{-1}\) with \(\epsilon =10^{-4}\), the parameters \({\varvec{w}}_k\) (rows of \({\varvec{W}}\)) and \({\varvec{b}}\) of Eq. (3) are computed as 3.6 Effectiveness of the Approach As the graph evolves, multiple sources of forgetting can impair the model’s prediction accuracy. This section elaborates on our method’s effectiveness in mitigating forgetting while yielding high anytime classification accuracy. One is a common challenge in all CL setups and stems from the continual update of the model’s parameters based on recent training signals, both for the feature extraction backbone (if trained) and for the classifier. A second, graph-specific issue arises from the evolving nature of the graphs and associated structural shifts (Su et al., 2023, 2024): predictions made for the same node at different time steps may rely on different and potentially inconsistent neighborhoods. To put our intuitions more formally, we consider time interval \(\delta t\) and define the forgetting risk for node v at time t as the increase in the loss from time \(t_0=t-\delta t\) to time t: with loss function \(\ell\) and where we made explicit the decomposition into feature extraction (\(\Psi _{\Theta }\)) and linear classifier (\(\Phi _{\mathbf{W}}\)); to avoid overwhelming notations, we omit the bias terms in \(\Phi _{\mathbf{W}}\) and use \( {{\mathcal {G}}^t_{v}}\) to indicate \( {\widetilde{\mathcal {G}}^{(t,l)}_{v}}\). Then, assuming that the loss is Lipschitz continuous with constant \(L_\ell\), and using the triangle inequality, we can isolate three components of forgetting risk: The first term is inherent in the data-generating process and therefore irreducible; we assess it empirically in Appendix G. A crucial advantage of using a fixed feature extractor is that it eliminates the second term, as \(\Theta _t = \Theta _{t_0}\). Furthermore, if we assume the norm of the embeddings to be bounded by \(B_z\), the third term is bounded by \(B_z \left\Vert {\varvec{W}}_t - {\varvec{W}}_{t_0} \right\Vert\). For SLDA, the term is expected to decrease as the number of observed examples of a class increases, due to the update scheme through separate, class-specific cumulative means; this is in contrast with SGD-based training, where weight updates are less separated by class. Therefore, SLDA with fixed feature extraction provides high stability, with decreasing forgetting risk as the node stream progresses. Higher stability compared to SGD-trained methods can be observed in Figs. 6 and 7 of Appendix I. This decomposition illustrates the robustness against forgetting of untrained feature extraction with SLDA. However, stability is not sufficient for good CL performance: the model must also remain plastic enough to acquire new knowledge as the node stream evolves. For this, we can rely on the over-parameterized randomized feature extractors, which give us expressive and general topological embeddings (Maron et al., 2019; Zambon et al., 2020) independently of task, allowing for training of just a simple linear classifier on top (Scardapane & Wang, 2017). While this analysis can give motivation and intuition behind the effectiveness of the proposed approach, we note that it does not provide formal guarantees on forgetting or generalization in OCGL, for which further future work would be required. 4 Experimental Setting For our experiments we adopt the OCGL setting described by Donghi et al. (2025). In particular, we follow the requirement of neighborhood sampling, and we consider small mini-batches of nodes instead of individual ones. We compare the use of randomized feature extractors, UGCN and GRNF, with linear classifier, either SLDA or coupled with CL strategies, across multiple benchmarks. 4.1 Benchmarks We use six node-classification graph datasets: CoraFull (Bojchevski & Günnemann, 2018), Arxiv (Hu et al., 2021), Reddit (Hamilton et al., 2017), Amazon Computer (Shchur et al., 2019), Roman Empire (Platonov et al., 2022) and Elliptic (Weber et al., 2019). On all except Elliptic (as it only has two classes) we consider a class-incremental stream: nodes in the graph arrive one by one in blocks consisting of two classes (each segment can be identified with a task in the context of CL, even though the models in this setting are agnostic to task boundaries). On Elliptic and Arxiv we consider a time-incremental stream: since real node timestamps are available, we use them for a realistic node stream (dividing the stream into 10 blocks simply for evaluation). We split the nodes in each graph into 60% for training, 20% for validation and 20% for testing, and we use a transductive setting. We consider the same mini-batch sizes as Donghi et al. (2025): 10 for the smaller CoraFull, Amazon Computer and Roman Empire, 50 for arXiv, Reddit and Elliptic. 4.2 Metrics To evaluate model predictions in the considered setting, we use three metrics: Average Performance (AP), Average Forgetting (AF) (Lopez-Paz & Ranzato, 2017), and Average Anytime Performance (AAP) (Caccia et al., 2021). The performance metric is accuracy for all datasets except for Elliptic, as it is highly unbalanced with only two classes, and therefore F1 score of the minority class is used. For anytime predictions, we obtain AAP by evaluating the model on the validation nodes after each training mini-batch. The metrics are described in detail in Appendix B. 4.3 Baselines In addition to the described SLDA, we couple the linear classifier on top of untrained features with some popular CL strategies: we consider A-GEM (Chaudhry et al., 2018), ER (Chaudhry et al., 2019), EWC (Kirkpatrick et al., 2017), LwF (Li & Hoiem, 2018) and MAS (Aljundi et al., 2018). Furthermore, we consider the bare baseline which consists of simply finetuning the linear layer on the stream without any CL method. We also provide the joint baseline consisting of jointly training the linear layer offline on the embeddings from all the nodes in the entire final graph. We do not consider graph-specific methods on the UGCN and GRNF backbones, as once the features are extracted graph-based models are no longer relevant. However, we provide a comparison with recent results for state-of-the-art graph methods for OCGL on a GCN trained end-to-end (Donghi et al., 2025) in Table 3. Specifically, in addition to the methods mentioned before we consider PDGNN (Zhang et al., 2024a), SSM (Zhang et al., 2022b) with both ER and A-GEM replay, TWP (Liu et al., 2021). We also consider two simple baselines: LINEAR (Donghi et al., 2025) and a simple SLDA model using only individual node features, without any aggregation, to verify by comparison the impact of coupling it with untrained feature extractors. 4.4 Implementation Details Following Donghi et al. (2025), we consider sparsified 2-hop node neighborhoods, sampling recursively 10 neighbors per layer for each node without replacement. For UGCN, we therefore use a 2-layer network with 1024 units per layer, resulting in a 2048-dimensional node embedding due to layer concatenation. For GRNF, we use 1024 features, which amount to a 2048-dimensional node embedding since we concatenate the equivariant and invariant components. In both cases, magnitude of weight initialization is regulated by a tunable gain hyperparameter. We use Adam optimizer (Kingma & Ba, 2015) without weight decay nor dropout, tuning the learning rate as a hyperparameter. Another hyperparameter is the number of passes on a mini-batch before passing to the next, as suggested by Aljundi et al. (2019). Hyperparameters are tuned following the protocol outlined by Chaudhry et al. (2018): they are selected according to validation performance (AP) only on a small section of the data stream. All training and method specific hyperparameters are reported in Appendix D. All experiments are performed with 5 different random initializations, and results are reported as average and standard deviation over them. 5 Results The results of our experiments in the OCGL setting with untrained feature extraction are reported in Table 1 for benchmarks with class-incremental node stream and Table 2 for those on which a time-incremental stream is defined. Additionally, we report a comparison with AP results obtainable by a model trained end-to-end in Table 3, together with the respective joint upper bound. 5.1 Class-Incremental Benchmarks We first observe from Table 1 that the upper bounds with randomized features are comparable to those obtained with a trained GCN model, as reported in Table 3. This proves that the extracted features are expressive enough for these tasks, confirming our approach’s viability. On Roman Empire specifically, which is highly heterophilic, we see a much higher upper bound with GRNF: this is due to the implicit bias of the GCN design, which smooths node embeddings with neighborhood information, while GRNF are more expressive, as they are derived from a universal approximator of graph functions. We also note how AF for the joint baseline represents the increasing difficulty of the classification task as new classes are added. From the results the superior performance of SLDA also emerges clearly, as it outperforms all considered CL methods on a linear layer trained with gradient descent, and in most cases with a wide margin. Additionally, the AP results of SLDA with both UGCN and GRNF closely approach their respective upper bounds. The results of the randomized feature extractors coupled with SLDA also significantly outperform the best results obtained with state-of-the-art replay methods tailored for graphs, as seen in Table 3, despite SLDA not using any memory buffer. The differences between UGCN and GRNF are in most cases limited, especially for the SLDA classifier, with UGCN showing a slight advantage on CoraFull, Amazon Computer and Arxiv benchmarks, while GRNF appears superior on Reddit and more significantly on Roman Empire, due to the heterophily of the graph as discussed above. In general, also most other CL strategies in most benchmarks report performance improvements compared to the use of a trained GCN, confirming the benefits of keeping a frozen feature extractor immune to forgetting. ER specifically is significantly better when coupled with randomized features compared to a trained GCN, in some cases approaching SLDA, due to the fact that in this setting the memory buffer is much more informative, as stored examples contain neighborhood information, albeit subject to structural shift. In most cases even SLDA only on node features overperforms the strategies on GCN trained end-to-end, highlighting the shortcomings of learnable aggregation in an OCGL setting. Using untrained feature extraction allows it to leverage richer embeddings, significantly improving performance (except on Roman Empire that is more problematic due to heterophily). 5.2 Time-Incremental Benchmarks The time-incremental setting naturally possesses more docile shifts in distribution, compared to the abrupt class changes of the class-incremental benchmark. Nonetheless, on Elliptic CL methods are still beneficial, with SLDA still outperforming all baselines, also compared to the trained GCN state-of-the-art (Table 3). Importantly, our results on Elliptic, which is a dataset of real Bitcoin transactions, highlight the feasibility and benefits of the proposed approach on realistic data streams, beyond the academic class-incremental setting. On the other hand, for the Arxiv time-incremental benchmark, we see little difference in the results of the various strategies, with SLDA no longer over-performing. In fact, we even see positive AF values for all methods, indicating that the classification becomes easier, rather than harder, as the node stream goes on. This is because Arxiv does not present a significant drift in class distribution throughout time. Therefore, a CL learning approach here is less meaningful, as the bare baseline is already close to the upper bound. Nevertheless, ER proves beneficial, and these high results are further proof that the feature extractors are robust to structural shifts that still remain. 5.3 Impact of Number of Features Given the overwhelming over-performance of randomized feature extraction with SLDA, we investigate the impact of the number of extracted features on model performance. In Fig. 1, we see that with a lower number of features AP decreases as well, even though on most benchmarks even as few as 64 randomized features are sufficient to obtain results on par with or even surpassing the state-of-the-art CL methods on trained GCN of Table 3. Also, for many benchmarks performance seems to not have reached saturation even at 4096 features, indicating that further gains could be achieved with a larger feature extractor. The number of features naturally implies a tradeoff between computational cost and effectiveness, but Fig. 1 shows that, coupled with SLDA, lightweight untrained models with fewer features than hidden units in the trained GCN counterpart can surpass the state-of-the-art. Finally, since UGCN and GRNF appear to have different strengths over the multiple benchmarks, we consider a hybrid feature extractor that extracts half of the features with UGCN, and half with GRNF. This mixed feature extractor shows a generally more robust performance over the benchmarks, with performance that is never lower than the individual two, except for one single point. Generally the hybrid extractor also does not improve over the best single one, indicating that the two types of feature do not benefit from integration. However, this strategy could be used to obtain a reliable feature extractor without the need to evaluate the two strategies. 6 Conclusion This work introduces a simple, yet surprisingly effective approach for Online Continual Graph Learning, addressing forgetting by decoupling representation learning from classification. We use randomized, fixed node feature extractors that encode neighborhood information, coupled with a lightweight linear classifier trained incrementally on the node stream. By leveraging two types of untrained feature extractors – UGCN and GRNF – the proposed method provides robust and expressive node embeddings, resistant to catastrophic forgetting. Extensive experiments in the OCGL setting demonstrate that when paired with SLDA, this approach significantly outperforms other Continual Learning strategies, including state-of-the-art replay-based methods tailored for graph data. The method achieves performance close to joint offline training across various benchmarks. Beyond strong performance, its efficient streaming updates and no reliance on memory buffers make it a scalable and practical approach to deal with real-time classification on graph node streams. 6.1 Limitations and Future Directions While we provide motivation and empirical evidence of the improved resistance to forgetting and higher prediction accuracy of our approach, a thorough theoretical analysis is yet to be developed. Secondly, we highlight how our results are specific for the challenging OCGL scenario, while for different, offline settings other methods can perform more favorably. Finally, our empirical conclusions are drawn for node-level classification; whether they extend to graph-level and edge-level tasks or streams, as well as regression or anomaly detection tasks, is left for future work. Data and Code Availability The datasets used for this research are publicly available. Code is available at https://github.com/giovannidonghi/OCGL. References Aggarwal, C. C., Hinneburg, A., & Keim, D. A. (2001). On the surprising behavior of distance metrics in high dimensional space. Database Theory - ICDT, (pp. 420–434). https://doi.org/10.1007/3-540-44503-X_27 Aljundi, R., Babiloni, F., Elhoseiny, M., Rohrbach, M., & Tuytelaars, T. (2018). Memory aware synapses: Learning what (not) to forget. Proceedings of the European Conference on Computer Vision (ECCV) (pp. 139–154). https://doi.org/10.1007/978-3-030-01219-9_9 Aljundi, R., Belilovsky, E., Tuytelaars, T., Charlin, L., Caccia, M., Lin, M., & Page-Caccia, L. (2019). Online continual learning with maximal interfered retrieval. Advances in Neural Information Processing Systems, 32. Bojchevski, A., & Günnemann, S. (2018). Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking. International Conference on Learning Representations. Caccia, L., Aljundi, R., Asadi, N., Tuytelaars, T., Pineau, J., & Belilovsky, E. (2021). New Insights on Reducing Abrupt Representation Change in Online Continual Learning. International Conference on Learning Representations. Cai, Y., He, X., Tong, A., & Bai, X. (2025). Dynamic Expert Routing for Unsupervised Continual Anomaly Detection. IEEE Transactions on Industrial Informatics,21(10), 7477–7486. https://doi.org/10.1109/TII.2025.3574429 Caroprese, L., Pisani, F. S., Veloso, B. M., Konig, M., Manco, G., Hoos, H., & Gama, J. (2025). Modelling concept drift in dynamic data streams for recommender systems. ACM Transactions on Recommender Systems. https://doi.org/10.1145/3707693 Chaudhry, A., Ranzato, M., Rohrbach, M., & Elhoseiny, M. (2018). Efficient Lifelong Learning with A-GEM. International Conference on Learning Representations. Chaudhry, A., Rohrbach, M., Elhoseiny, M., Ajanthan, T., Dokania, P. K., Torr, P. H. S., & Ranzato, M. (2019). On Tiny Episodic Memories in Continual Learning. arXiv arXiv:1902.10486. Chen, X., Wang, J., & Xie, K. (2021). TrafficStream: A Streaming Traffic Flow Forecasting Framework Based on Graph Neural Networks and Continual Learning. Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21 (pp. 3620–3626). https://doi.org/10.24963/ijcai.2021/498 Coil, C., Faber, K., Sniezynski, B., & Corizzo, R. (2026). Distance-based change point detection for novelty detection in concept-agnostic continual anomaly detection. Journal of Intelligent Information Systems,64, 37–75. https://doi.org/10.1007/s10844-025-00949-1 Cui, Y., Wang, Y., Sun, Z., Liu, W., Jiang, Y., Han, K., & Hu, W. (2023). Lifelong Embedding Learning and Transfer for Growing Knowledge Graphs. Proceedings of the AAAI Conference on Artificial Intelligence,37(4), 4217–4224. https://doi.org/10.1609/aaai.v37i4.25539 De Lange, M., Aljundi, R., Masana, M., Parisot, S., Jia, X., Leonardis, A., & Tuytelaars, T. (2022). A Continual Learning Survey: Defying Forgetting in Classification Tasks. IEEE Transactions on Pattern Analysis and Machine Intelligence,44(7), 3366–3385. https://doi.org/10.1109/TPAMI.2021.3057446 Ding, M., Ji, K., Wang, D., & Xu, J. (2024). Understanding forgetting in continual learning with linear regression. Proceedings of the 41st International Conference on Machine Learning235, 10978–11001. Donghi, G., Pasa, L., Oneto, L., Gallicchio, C., Micheli, A., Anguita, D., & Navarin, N. (2024). Investigating over-parameterized randomized graph networks. Neurocomputing. https://doi.org/10.1016/j.neucom.2024.128281 Donghi, G., Pasa, L., Zambon, D., Alippi, C., & Navarin, N. (2025). Online Continual Graph Learning. arXiv arXiv:2508.03283. Evron, I., Moroshko, E., Buzaglo, G., Khriesh, M., Marjieh, B., Srebro, N., & Soudry, D. (2023). Continual learning in linear classification on separable data. Proceedings of the 40th International Conference on Machine Learning202, 9440–9484. Evron, I., Moroshko, E., Ward, R., Srebro, N., & Soudry, D. (2022). How catastrophic can catastrophic forgetting be in linear regression? Proceedings of Thirty Fifth Conference on Learning Theory, 178, 028–4079. Febrinanto, F. G., Xia, F., Moore, K., Thapa, C., & Aggarwal, C. (2023). Graph Lifelong Learning: A Survey. IEEE Computational Intelligence Magazine,18(1), 32–51. https://doi.org/10.1109/MCI.2022.3222049 Gallicchio, C., & Micheli, A. (2010). Graph Echo State Networks. The 2010 International Joint Conference on Neural Networks (IJCNN). https://doi.org/10.1109/IJCNN.2010.5596796 Gilmer, J., Schoenholz, S.S., Riley, P.F., Vinyals, O., Dahl, G.E. (2017). Neural Message Passing for Quantum Chemistry. Proceedings of the 34th International Conference on Machine Learning (pp. 1263–1272). (ISSN: 2640-3498) Glorot, X., & Bengio, Y. (2010). Understanding the difficulty of training deep feedforward neural networks. Hamilton, W., Ying, Z., & Leskovec, J. (2017). Inductive Representation Learning on Large Graphs. Advances in Neural Information Processing Systems 30. Hayes, T. L., & Kanan, C. (2020). Lifelong Machine Learning with Deep Streaming Linear Discriminant Analysis. 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW) (pp. 887–896). https://doi.org/10.1109/CVPRW50498.2020.00118 Hoang, T. D., Tung, D. V., Nguyen, D. H., Nguyen, B. S., Nguyen, H. H., & Le, H. (2023). Universal Graph Continual Learning. Transactions on Machine Learning Research. Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., & Leskovec, J. (2021). Open Graph Benchmark: Datasets for Machine Learning on Graphs. arXiv arXiv:2005.00687. Huang, C., Li, M., Cao, F., Fujita, H., Li, Z., Wu, X., & Li, M. (2023). Are Graph Convolutional Networks With Random Weights Feasible? IEEE Transactions on Pattern Analysis and Machine Intelligence,45(3), 2751–2768. https://doi.org/10.1109/TPAMI.2022.3183143 Huang, G., Huang, G. B., Song, S., & You, K. (2015). Trends in extreme learning machines: A review. Neural Networks,61, 32–48. https://doi.org/10.1016/j.neunet.2014.10.001 Huang, G. B., Zhu, Q. Y., & Siew, C. K. (2006). Extreme learning machine: Theory and applications. Neurocomputing,70(1–3), 489–501. https://doi.org/10.1016/j.neucom.2005.12.126 Jaeger, H., & Haas, H. (2004). Harnessing Nonlinearity: Predicting Chaotic Systems and Saving Energy in Wireless Communication. Science,304(5667), 78–80. https://doi.org/10.1126/science.1091277 Keriven, N., & Peyré, G. (2019). Universal invariant and equivariant graph neural networks. Proceedings of the 33rd International Conference on Neural Information Processing Systems. Kingma, D. P., & Ba, J. (2015). Adam: A Method for Stochastic Optimization. International Conference on Learning Representations. Kipf, T. N., & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. International Conference on Learning Representations. Kirkpatrick, J., Pascanu, R., Rabinowitz, N., Veness, J., Desjardins, G., Rusu, A. A., & Hadsell, R. (2017). Overcoming catastrophic forgetting in neural networks. Proceedings of the National Academy of Sciences,114(13), 3521–3526. https://doi.org/10.1073/pnas.1611835114 Koh, H., Kim, D., Ha, J. W., & Choi, J. (2021). Online Continual Learning on Class Incremental Blurry Task Configuration with Anytime Inference. International Conference on Learning Representations. Le Baher, H., Azé, J., Bringay, S., Poncelet, P., Rodriguez, N., & Dunoyer, C. (2023). Patient Electronic Health Record as Temporal Graphs for Health Monitoring. Studies in Health Technology and Informatics,302, 561–565. https://doi.org/10.3233/SHTI230205 Li, D., & Zeng, Z. (2023). CRNet: A Fast Continual Learning Framework With Random Theory. IEEE Transactions on Pattern Analysis and Machine Intelligence,45(9), 10731–10744. https://doi.org/10.1109/TPAMI.2023.3262853 Li, Z., & Hoiem, D. (2018). Learning without Forgetting. IEEE Transactions on Pattern Analysis and Machine Intelligence,40(12), 2935–2947. https://doi.org/10.1109/TPAMI.2017.2773081 Lin, L., Zhong, Q., Qiu, J., & Liang, Z. (2024). E-GRACL: An IoT intrusion detection system based on graph neural networks. The Journal of Supercomputing,81(1), 42. https://doi.org/10.1007/s11227-024-06471-5 Liu, H., Yang, Y., & Wang, X. (2021). Overcoming Catastrophic Forgetting in Graph Neural Networks. Proceedings of the AAAI Conference on Artificial Intelligence,35(10), 8653–8661. https://doi.org/10.1609/aaai.v35i10.17049 Liu, X., Gao, C., & Li, P. (2012). A comparative analysis of support vector machines and extreme learning machines. Neural Networks,33, 58–66. https://doi.org/10.1016/j.neunet.2012.04.002 Liu, Y., Qiu, R., & Huang, Z. (2023). CaT: Balanced Continual Graph Learning with Graph Condensation. 2023 IEEE International Conference on Data Mining (ICDM) (pp. 1157–1162). https://doi.org/10.1109/ICDM58522.2023.00141 Lopez-Paz, D., & Ranzato, M. A. (2017). Gradient Episodic Memory for Continual Learning. Advances in Neural Information Processing Systems30. Mai, Z., Li, R., Jeong, J., Quispe, D., Kim, H., & Sanner, S. (2022). Online continual learning in image classification: An empirical survey. Neurocomputing,469, 28–51. https://doi.org/10.1016/j.neucom.2021.10.021 Maron, H., Fetaya, E., Segol, N., & Lipman, Y. (2019). On the Universality of Invariant Networks. Proceedings of the 36th International Conference on Machine Learning (pp. 4363–4371). McDonnell, M. D., Gong, D., Parvaneh, A., Abbasnejad, E., & van den Hengel, A. (2023). RanPAC: Random Projections and Pre-trained Models for Continual Learning. Advances in Neural Information Processing Systems,36, 12022–12053. McInnes, L., Healy, J., Melville, J. (2020). UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction. arXiv:1802.03426 Mehta, S. V., Patil, D., Chandar, S., & Strubell, E. (2023). An Empirical Investigation of the Role of Pre-training in Lifelong Learning. Journal of Machine Learning Research,24(214), 1–50. Micheli, A. (2009). Neural Network for Graphs: A Contextual Constructive Approach. IEEE Transactions on Neural Networks,20(3), 498–511. https://doi.org/10.1109/TNN.2008.2010350 Mirzadeh, S. I., Chaudhry, A., Yin, D., Hu, H., Pascanu, R., Gorur, D., & Farajtabar, M. (2022). Wide Neural Networks Forget Less Catastrophically. Proceedings of the 39th International Conference on Machine Learning (pp. 15699–15717). Navarin, N., Pasa, L., Gallicchio, C., & Sperduti, A. (2023a). An untrained neural model for fast and accurate graph classification. https://doi.org/10.1007/978-3-031-44216-2_23 Navarin, N., Pasa, L., Oneto, L., & Sperduti, A. (2023b). An Empirical Study of Over-Parameterized Neural Models based on Graph Random Features. ESANN 2023 proceedings (pp. 17–22). https://doi.org/10.14428/esann/2023.ES2023-145 Pao, Y. H., Park, G. H., & Sobajic, D. J. (1994). Learning and generalization characteristics of the random vector functional-link net. Neurocomputing,6(2), 163–180. https://doi.org/10.1016/0925-2312(94)90053-1 Pao, Y. H., & Takefuji, Y. (1992). Functional-link net computing: Theory, system architecture, and functionalities. Computer,25(5), 76–79. https://doi.org/10.1109/2.144401 Parisi, G. I., Kemker, R., Part, J. L., Kanan, C., & Wermter, S. (2019). Continual lifelong learning with neural networks: A review. Neural Networks,113, 54–71. https://doi.org/10.1016/j.neunet.2019.01.012 Pasa, L., Navarin, N., & Sperduti, A. (2022). Multiresolution Reservoir Graph Neural Network. IEEE Transactions on Neural Networks and Learning Systems,33(6), 2642–2653. https://doi.org/10.1109/TNNLS.2021.3090503 Pelosin, F. (2022). Simpler is Better: Off-the-shelf Continual Learning Through Pretrained Backbones. arXiv arXiv:2205.01586. Pezze, D. D., Anello, E., Masiero, C., & Susto, G. A. (2025). Continual learning approaches for anomaly detection. Evolving Systems. https://doi.org/10.1007/s12530-025-09732-7 Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., & Prokhorenkova, L. (2022). A critical look at the evaluation of GNNs under heterophily. Are we really making progress? International Conference on Learning Representations. Prabhu, A., Sinha, S., Kumaraguru, P., Torr, P., Sener, O., & Dokania, P. (2024). RanDumb: Random Representations Outperform Online Continually Learned Representations. Advances in Neural Information Processing Systems,37, 37988–38006. Rahimi, A., & Recht, B. (2007). Random Features for Large-Scale Kernel Machines. Advances in Neural Information Processing Systems20. Rahimi, A., & Recht, B. (2008). Weighted Sums of Random Kitchen Sinks: Replacing minimization with randomization in learning. Advances in Neural Information Processing Systems21. Rebuffi, S. A., Kolesnikov, A., Sperl, G., & Lampert, C. H. (2017). iCaRL: Incremental Classifier and Representation Learning. 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (pp. 5533–5542). https://doi.org/10.1109/CVPR.2017.587 Rolnick, D., Ahuja, A., Schwarz, J., Lillicrap, T., & Wayne, G. (2019). Experience Replay for Continual Learning. Advances in Neural Information Processing Systems32. Rudi, A., & Rosasco, L. (2017). Generalization Properties of Learning with Random Features. Advances in Neural Information Processing Systems30. Scardapane, S., & Wang, D. (2017). Randomness in neural networks: An overview. WIREs Data Mining and Knowledge Discovery. https://doi.org/10.1002/widm.1200 Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., & Monfardini, G. (2009). The Graph Neural Network Model. IEEE Transactions on Neural Networks,20(1), 61–80. https://doi.org/10.1109/TNN.2008.2005605 Shchur, O., Mumme, M., Bojchevski, A., & Günnemann, S. (2019). Pitfalls of Graph Neural Network Evaluation. arXiv arXiv:1811.05868. Soutif-Cormerais, A., Carta, A., Cossu, A., Hurtado, J., Lomonaco, V., Van De Weijer, J., & Hemati, H. (2023). A Comprehensive Empirical Evaluation on Online Continual Learning. IEEE/CVF International Conference on Computer Vision Workshops (ICCVW) (pp. 3510–3520). https://doi.org/10.1109/ICCVW60793.2023.00378 Su, J., Zou, D., & Wu, C. (2024). On the Limitation and Experience Replay for GNNs in Continual Learning. arXiv arXiv:2302.03534. Su, J., Zou, D., Zhang, Z., & Wu, C. (2023). Towards robust graph incremental learning on evolving graphs. Proceedings of the 40th International Conference on Machine Learning, 202, 32728–32748. Sun, L., Ye, J., Peng, H., Wang, F., & Yu, P. S. (2023). Self-Supervised Continual Graph Learning in Adaptive Riemannian Spaces. Proceedings of the AAAI Conference on Artificial Intelligence,37(4), 4633–4642. https://doi.org/10.1609/aaai.v37i4.25586 Van De Ven, G. M., Tuytelaars, T., & Tolias, A. S. (2022). Three types of incremental learning. Nature Machine Intelligence,4(12), 1185–1197. Wang, R., Ciccone, M., Luise, G., Yapp, A., Pontil, M., & Ciliberto, C. (2022). Schedule-Robust Online Continual Learning. arXiv:2210.05561. Wang, Z., Liu, Z., Ma, T., Li, J., Zhang, Z., Fu, X., & Ye, Y. (2025). Graph Foundation Models: A Comprehensive Survey. arXiv:2505.15116. Weber, M., Domeniconi, G., Chen, J., Weidele, D. K. I., Bellei, C., Robinson, T., & Leiserson, C. E. (2019). Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics. arXiv arXiv:1908.02591. Yuan, Q., Guan, S. U., Ni, P., Luo, T., Man, K. L., Wong, P., & Chang, V. (2023). Continual Graph Learning: A Survey. arXiv arXiv:2301.12230. Zambon, D., Alippi, C., & Livi, L. (2020). Graph Random Neural Features for Distance-Preserving Graph Representations. Proceedings of the 37th International Conference on Machine Learning (pp. 10968–10977). Zambon, D., Livi, L., & Alippi, C. (2022). Graph iForest: Isolation of anomalous and outlier graphs. 2022 International Joint Conference on Neural Networks (IJCNN) (pp. 1–8). https://doi.org/10.1109/IJCNN55064.2022.9892295 Zhang, X., Song, D., Chen, Y., & Tao, D. (2024a). Topology-aware Embedding Memory for Continual Learning on Expanding Networks. Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 4326–4337). https://doi.org/10.1145/3637528.3671732 Zhang, X., Song, D., & Tao, D. (2022a). CGLB: Benchmark Tasks for Continual Graph Learning. Advances in Neural Information Processing Systems,35, 13006–13021. Zhang, X., Song, D., Tao, D. (2022b). Sparsified Subgraph Memory for Continual Graph Representation Learning. 2022 IEEE International Conference on Data Mining (ICDM) (pp. 1335–1340). https://doi.org/10.1109/ICDM54844.2022.00177 Zhang, X., Song, D., & Tao, D. (2024b). Continual Learning on Graphs: Challenges, Solutions, and Opportunities. arXiv:2402.11565. Zhang, Z., Cai, Y., Gong, W., Liu, X., Cai, Z. (2020). Graph Convolutional Extreme Learning Machine. 2020 International Joint Conference on Neural Networks (IJCNN). https://doi.org/10.1109/IJCNN48605.2020.9206649 Zhang, Z., Zou, G., Chen, C., Qi, Z., Yu, X., Qi, J., & Tan, X. (2026). A Task-Aware Parameter Decoupling Framework for Continual Anomaly Detection. IEEE Transactions on Industrial Informatics,22(2), 1118–1128. https://doi.org/10.1109/TII.2025.3622997 Zhou, F., & Cao, C. (2021). Overcoming Catastrophic Forgetting in Graph Neural Networks with Experience Replay. Proceedings of the AAAI Conference on Artificial Intelligence,35(5), 4714–4722. https://doi.org/10.1609/aaai.v35i5.16602 Funding Open access funding provided by Università degli Studi di Padova within the CRUI-CARE Agreement. This research was supported by the European Union - NextGenerationEU as part of the Italian National Recovery and Resilience Plan (PNRR), the project “Lifelong Learning on large-scale and structured data” funded by the EC-funded OCRE project, and the Swiss National Science Foundation project FNS 204061: “HORD GNN: Higher-Order Relations and Dynamics in Graph Neural Networks”. Author information Authors and Affiliations Contributions Giovanni Donghi: Conceptualization, Investigation, Software, Visualization, Writing – original draft; Daniele Zambon: Conceptualization, Writing – original draft, Writing – review & editing; Luca Pasa: Conceptualization, Writing – review & editing; Cesare Alippi: Conceptualization, Funding acquisition, Supervision, Writing – review & editing; Nicolò Navarin: Conceptualization, Funding acquisition, Supervision, Writing – review & editing. Corresponding author Ethics declarations Conflict of interest The authors have no competing interests to declare. Additional information Editors: Zahraa S. Abdallah, Annalisa Appice, Przemyslaw Biecek, Andrea Tagarelli. Publisher''s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. Appendices Appendix A: Benchmarks The benchmarks for out experiments are obtained from six node-level classification graph datasets. The CoraFull dataset (Bojchevski & Günnemann, 2018) is a citation network where nodes represent research papers and edges denote citation links between them, with labels corresponding to paper topics. Amazon Computer (Shchur et al., 2019) is a co-purchase graph, with nodes representing products and edges indicating frequent co-purchases in the computer category on Amazon. Arxiv (Hu et al., 2021) is a larger citation network based on arXiv submissions in the Computer Science domain. The Reddit dataset (Hamilton et al., 2017) comprises posts from various Reddit communities, where each node represents a post, and edges connect posts that were commented on by the same user, capturing user interaction patterns. Roman Empire (Platonov et al., 2022) is an heterophilous dataset constructed from the corresponding Wikipedia page, where nodes are words linked through syntactic relationships or adjacency in the text. Lastly, the Elliptic dataset (Weber et al., 2019) is a graph of Bitcoin transactions, with edges representing the flow of funds. Only a subset of nodes are labeled as either licit (42,019 nodes) or illicit (4,545 nodes) transactions. Summary statistics for the six datasets are provided in Table 4. Appendix B: Metrics Due to the way the node stream is built, with a definition of task boundaries, we can make use of two commonly adopted continual learning (CL) metrics: Average Performance (AP) and Average Forgetting (AF) (Lopez-Paz & Ranzato, 2017). These metrics are both derived from the more general performance matrix \({\varvec{M}}\in \mathbb {R}^{T \times T}\), where T denotes the total number of tasks, and each element \(M_{i,j}\) corresponds to the test performance on task j after training on task i. The Average Performance is given by \(\text {AP} = \frac{1}{T} \sum _{i=1}^T M_{T,i}\), representing the model’s performance on all tasks after completing the full training stream. The Average Forgetting is computed as \(\text {AF} = \frac{1}{T-1} \sum _{i=1}^{T-1} M_{T,i} - M_{i,i}\), and quantifies how much the model’s performance on each task has deteriorated between its initial learning and the end of training. For evaluating performance, we rely on classification accuracy across all datasets, except for Elliptic, which is significantly imbalanced. For this dataset, we instead report the F1 score specific to the illicit class. To track model behavior throughout the node stream, we also employ anytime evaluation: the model is evaluated on validation nodes after each mini-batch update (Koh et al., 2021). This provides a fine-grained view of model performance over time, revealing its adaptability to distributional shifts. We quantify this using the Average Anytime Performance (AAP) metric (Caccia et al., 2021), a generalization of average incremental accuracy for the online scenario. Letting APt denote the average accuracy after processing the t-th mini-batch, and n be the total number of mini-batches, AAP is defined as \(\text {AAP} = \frac{1}{n}\sum {t=1}^n \text {AP}_t\). This metric can be interpreted as the area under the accuracy curve across the training process (Koh et al., 2021). Appendix C: Online Feature Centering Trick As in our experiments we consider also using a standard linear layer trained continually with gradient descent instead of SLDA, in this case it is beneficial to have featured centered in the origin. This is especially true due to the online setting, as having centered features can make the learning of bias parameters for newly observed classes faster, since we initialize the weights symmetrically around zero. Therefore, we adopt an online centering procedure, which allows us to keep the features centered at any point during the stream. Specifically, we maintain an updated global cumulative mean m of node embeddings, so that where for ease of notation we use \({\varvec{z}}^{(t)} = {\varvec{z}}_{v_t}^{(t)}\). With this, we then feed the centered embeddings \( {{\varvec{z}}_v^{(t)} - m^{(t)}}\) in equation (3) of the paper. To ensure consistency of model predictions with online feature centering under updates of the embedding mean as in Eq. (13), we want to correct the bias term \({\varvec{b}}\rightarrow {\varvec{b}}''\) to ensure that for any \({\varvec{z}}\in \mathbb {R}^d\) predictions don’t change, that is Simplifying and using the definition of the update of \(m^{(t)}\) in Eq. (13), we obtain: This is the bias update formula, and a similar one can be derived for mini-batch updates. We highlight how this bias correction is performed only for seen classes, as we grow the classification head when new classes are encountered. Also, this online centering procedure is not performed with SLDA, since it is a prototype-based classifier and is thus indifferent to feature centering. Empirically, we have observed that this trick greatly improves performance when the node embeddings are not centered, which is often the case with GRNF. Appendix D: Hyperparameters We perform model selection using a limited section of the node stream, approximately 20% of the tasks. Therefore, for class-incremental stream we validate over 7 out 35 tasks for CoraFull, 2 out of 5 for Amazon Computer (as considering 20% of the tasks would mean using only 1, thus without any CL aspect), 4 out of 20 for Arxiv and Reddit, and 2 out of 9 for Roman Empire. For the time-incremental stream, we validate over the first 20% of the nodes (i.e., 2 out of 10 tasks). The hyperparameters are selected by running a standard grid search, over the search space that we illustrate here. For all experiments and both backbones, we consider the gain hyperparameter for weight initialization in \(\{0.1, 1, 10\}\). For all methods, except SLDA, we select the learning rate from the set \(\{0.01, 0.001, 0.0001, 0.00001\}\), and the number of passes on each batch before going to the next one between 1 and 5. For ER and A-GEM, we consider the proportion of memories to use with respect to each training batch in \(\{1,2,3\}\). Additionally, we set the same memory buffer size as Donghi et al. (2025), as 4% of the total graph nodes. The regularization hyperparameter for EWC and MAS is selected in \(\{10^0, 10^2, 10^4, 10^6, 10^8, 10^{10}\}\). For LwF, we consider lambda_dist in \(\{1,10\}\), T in \(\{0.2,2\}\) and the number of mini-batches after which to update the teacher model in \(\{10,100\}\). We highlight how the only hyperparameter considered for SLDA is the gain of the backbone, making it even easier to use than other methods, avoiding expensive hyperparameter search. Additionally, we ablate the impact of the gain hyperparameters by reporting in Table 5 the results obtained by SLDA with all the considered values of gain for the two backbones. Performance is quite robust to the initialization, as generally even with suboptimal gain the results are superior to the other methods, except for the time-incremental benchmarks that appear more sensitive to initialization. Appendix E: Comparison with a Pre-trained Backbone To further isolate the contribution of randomized representations from that of the SLDA classifier, we compare the proposed approach with a task-specific pre-trained backbone. Specifically, we train offline on the validation portion of the stream the same GCN architecture used for UGCN, using a temporary linear classifier with cross-entropy loss. After training, the classifier is discarded and the frozen backbone is used to extract node embeddings for SLDA. We remark that this pre-training strategy does not comply with the online continual learning setting, and that it may often not be feasible in reality, but it allows us to assess the goodness of the task-free randomized embeddings against pre-trained task-specific ones. Results are reported in Table 6. Despite the advantage of supervised pre-training on approximately 20% of the stream, the pre-trained backbone does not outperform the randomized counterpart, except on Elliptic. These results suggest that the effectiveness of the proposed approach is not solely due to SLDA, but also to the properties of randomized representations. In the OCGL setting, fixed untrained embeddings appear to provide a more robust and stable representation space under structural and distribution shifts than task-specific pre-training, while also avoiding representation drift during the stream. Appendix F: Memory usage A key advantage of replay-free continual learning methods is the absence of a memory buffer. However, our approach still requires storing the parameters of the randomized backbone together with the statistics used by SLDA. Therefore, to provide a memory usage comparison with replay-based approaches, in Fig. 2 we analyze the tradeoff between predictive performance and total memory usage, comparing the proposed randomized approaches and with PDGNN, the best-performing training method that uses replay. For the proposed methods, we compute memory usage as the sum of the memory required by the fixed randomized backbone and the SLDA statistics. In particular, the dominant cost for SLDA is the covariance matrix, resulting in quadratic scaling with the number of extracted features. For PDGNN, instead, total memory usage is computed as the memory occupied by the trained network parameters together with the replay buffer. Despite this unfavorable scaling, the proposed approaches generally achieve a better tradeoff between memory and performance. In particular, with a relatively small number of random features, both UGCN+SLDA and GRNF+SLDA already outperform most replay-based methods while using limited memory. Furthermore, on most benchmarks they remain on the efficient frontier, achieving higher AP with lower memory consumption than PDGNN. These results indicate that storing a fixed randomized backbone together with lightweight streaming statistics can be more memory-efficient than maintaining replay buffers and training a full GNN online. We also note that the current SLDA implementation is not optimized for memory efficiency: using incremental updates of the precision matrix directly, or diagonal covariance approximations, would significantly reduce memory requirements with only limited impact on performance. Appendix G: Structural Drift In Sect. 3.6, we discussed a decomposition of forgetting into three terms:structural drift, backbone parameters drift and classifier parameter drift. Thanks to our proposed approach, backbone parameters drift is eliminated, and with SLDA the classifier parameter drift remains contained. Structural drift remains a possible source of forgetting, therefore here we investigate it empirically on one of the datasets used in the experiments. We use CoraFull, assessing the drift of node representations \(\Psi \left( \widetilde{\mathcal {G}}^{(t,l)}_{v}\right)\) extracted with UGCN for the nodes of the first 5 tasks, which are more subject to drift due to appearing early in the graph growth. In particular we are interested in the drift of the representation of each node from the one that was obtained when the node first appeared, that is where \(t_v\) is the time of v’s first appearance in the graph and d can be the Euclidean distance, the cosine distance, or other metrics to quantify drift. In Fig. 3 we plot for each t the average drift for the nodes of the first 5 tasks (after they appeared), with both cosine and Euclidean distance. The absolute value of the drift by itself is not necessarily informative: if the drift is sufficiently small relative to the distance between different nodes, it may not influence the classification. We therefore provide as a reference point the average distance between pairs of nodes of the same class, and between pairs from different classes, computed only for final embeddings due to the high computational cost of obtaining it for each time step. From Fig. 3b we see that the average Euclidean drift is lower than both the mean distance between nodes from the same class (mean within class) and the mean distance between nodes from different classes (mean between classes), yet they fall within one standard deviation from it. On the other hand, the cosine drift shown in Fig. 3a is significantly lower, indicating that the direction of the embeddings is mostly stable, which could be more relevant to the linear classification than the Euclidean distance, especially in high dimensional space (Aggarwal et al., 2001). To better visualize the drift of some example nodes, we selected four nodes among the first to appear, in pairs from the same class. For these, we computed the pairwise distances of the embeddings at each time step, visualized in Fig. 4. We clearly see that the distances among successive embeddings of the same node (blocks along the diagonal) are considerably lower than the distances between embeddings of different nodes (off-diagonal blocks), and we can also observe higher similarity between nodes of the same class. We note how the embeddings of the first two nodes appear to be stable across time steps, with uniformly low distances, while for the nodes of the other class we can see blocks in the respective submatrix, due to the appearance of new neighbors from successive tasks. Finally, to provide a better visualization of the trajectories of node embeddings through time without solely relying on distances, we reduce the dimensionality of the embeddings to two using UMAP (Mcinnes et al., 2020) fitted on final node embeddings, and plot the trajectories in this space in Fig. 5. We see that the embeddings are overall quite stable and contained within the region of the node’s class. The only exception is the fourth node, whose starting embedding is significantly different from its successive ones; this can also be faintly seen in the Euclidean distances in Fig. 4b, with the bright yellow line for its first time step, while this does not emerge with cosine distance in Fig. 4a, so this drift may not necessarily be harmful for classification. Appendix H: Other Results with Trained GCN In Table 3 we reported the AP of CL strategies when used with a trained GCN in the OCGL setting (Donghi et al., 2025). These results are obtained in the same configurations used for the other experiments, only with a trained 2-layer GCN with 256 hidden units instead of an untrained feature extractor. Here we include Table 7 for AAP results, and Table 8 with results on the Arxiv dataset with time-incremental stream, that were excluded from Table 3 due to lack of space and little informative content since all methods perform very similarly due to the minimal distribution drift. Appendix I: Performance plots We report here plots that show model performance along the node stream, to provide a more detailed understanding of the dynamics of training and forgetting. In Figs. 6 and 7 we plot for each benchmark a comparison of the performance using the considered methods, for UGCN and GRNF backbones respectively. We highlight the task boundaries with dotted vertical lines, with the thicker dashed one indicating the threshold at which hyperparameter selection is performed. The upper bound of joint training on data up to the present task is represented as a horizontal line over the batches of each task. In Figs. 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 and 21, we instead illustrate a more detailed breakdown of model performance: for each benchmark, backbone and considered method, we plot the results of anytime evaluation broken down on individual tasks, allowing a better understanding of when and where forgetting occurs. Rights and permissions Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. About this article Cite this article Donghi, G., Zambon, D., Pasa, L. et al. The Unreasonable Effectiveness of Randomized Representations in Online Continual Graph Learning. Mach Learn 115, 220 (2026). https://doi.org/10.1007/s10994-026-07128-5 Received: Revised: Accepted: Published: Version of record: DOI: https://doi.org/10.1007/s10994-026-07128-5