Revealing an Overlooked Challenge in Class-Incremental Graph Learning
Authors: Daiqing Qi
Handong Zhao
Xiaowei Jia
Sheng Li
Venue: Accepted by TMLR ()

Abstract: Graph Neural Networks (GNNs), which effectively learn from static graph-structured data, become ineffective when directly applied to streaming data in a continual learning (CL) scenario. In CL, historical data are not available during the current stage due to a number of reasons, such as limited storage, GDPR1 data retention policy, to name a few. A few recent works study this problem, however, they overlook the uniqueness of continual graph learning (CGL), compared to well-studied continual image classification: the unavailability of previous training data further poses challenges to inference in CGL, in additional to the well-known catastrophic forgetting problem. While existing works make a strong assumption that full access of historical data is unavailable during training but provided during inference, which potentially contradicts the continual learning paradigm Van de Ven & Tolias (2019), we study continual graph learning without this strong and contradictory assumption. In this case, without being re-inserted into previous training graphs for inference, streaming test nodes are often more sparsely connected, which makes the inference more difficult due to insufficient neighborhood information. In this work, we propose ReplayGNN (ReGNN) to jointly solve the above two challenges without memory buffers: catastrophic forgetting and poor neighbor information during inference. Extensive experiments demonstrate the effectiveness of our model over baseline models and its effectiveness in different cases with different levels of neighbor information available.

Published in Transactions on Machine Learning Research (05/2024)
Revealing an Overlooked Challenge in Class-Incremental Graph Learning
Daiqing Qi University of Virginia Charlottesville, VA 22903
daiqing. bonginnggi@viiginii.cm
Handong Zhao
hazhao Radobe. com
Adobe Research San Jose, CA 95110
Xiaowei Jia
siaovei@yyttt.ed
University of Pittsburgh Pittsburgh, PA 15260
Sheng Li
shengli@virginiaa edu
University of Virginia Charlotteswille VA 22903
Reviewed on OpenReview: https: // openreview. net/ net/ forum? id- ScAc73Y10J
Abstract
Graph Neural Networks (GNNs), which effectively learn from static graph-structured data, become ineffective when directly applied to streaming data in contimual learning (CL) scenario. In CL, historical data are not available during the current stage due to a number of reasons, such as limited storage, GDPRT data retention policy, to name a few. A few recent works study this problem, however, they overlook the uniqueness of continual graph learning (CGL), compared to well-studied continual image classification: the unavailability of previous training data further poses challenges inference CGL, additional the well-known catastrophic forgetting problem. While existing works make strong assumption that full access of historical data is unavailable during training but provided during inference, which potentially contradicts the continual learning paradigm (Van de Ven & Tolias 2019), we study continual graph learning without this strong and contradictory assumption. In this case, without being re-inserted into previous training graphs for inference, streaming Lest nodes are often more sparsely connected, which makes the inference more difficult due to insufficient neighborhood information. In this work, we propose ReplayGNN (ReGNN) to jointly solve the above two challenges without memory buffers: catastrophic forgetting and poor neighbor information during inference. Fxtensive experiments demonstrate the effectiveness of our model over baseline models and its effectiveness in different cases with different levels of neighbor information available.
1 Introduction
Graph Neural Networks (GNNs) Kipf & Welling 2016a Hamilton al. 2017) have been recognized valid tool for graph learning, showing promising performance variety of tasks. In practical scenarios,
weneeerr////eeaaaalal Data Protection Regulation Protection_Regllaationn

---

Published in Transactions on Machine Learning Research (05/2024)
Degree rank plot
Degree histogram
les dxa Trahing cata
1200
Test
Traniig
oo Nodes
1000
Degree
800
600
530
1030
1500
2003
2500
3000
3500
12
20
Rank
Degree
Figure 1: Node degree statistics of training and test data from graph that records user interactions in Stack Exchange (an online platform). We extract data accunulated for month as the training graph and data from the following few days as the test data, Obvious difference between training and test data density can be observed under continual graph learning setting (previous training nodes are unavailable).
graphs can often evolve over time, and meanwhile, previous data (e.g., some nodes and edges) are inaccessible somctimes. For instance, in user interaction graphs of online platforms (Fig. D. history records can be unavailable due to customer data storage consent, for instance, the 30-days right-offerasure in General Data Protection Regulation (GDPR), or the users' preferences to hide their history records. Traditional graph learning models (Hamilton et al., 2017 Kipf & Welling 2016a). which are not designed for preserving good performance on all learnt tasks over time, often have limited performance in this setting because the unavailability of previous data leads to catastrophic forgetting (McCloskey & Cohen 1989).
Continual learning [Thrun 1995 aims to develop an intelligent system that can continuously learn from new tasks without forgetting learnt knowledge in the absence of previous data. Common continual learning scenarios can be roughly divided into two categories (Van de Ven & Tolias 2019): : task-incremental learning
(TT) and class-incremental learning (CI) (Rebuffi et al. 2017 Qi ct al.] 2023 . Recently, a few works {Liu
et al.
2021 Zhou & Cao 2021 Wang el al.j 2020 2022 Galke et al. 2021 | begin to study Continual
Graph Leaning (CGL), which is helpful when accumulating all history data over time is not feasible due to storage pressure or customer data storage consent, for instance, the 30-days right-of-crasure in GDPR. P Furthermore, even in scenarios where all prior data remains accessible, continual graph learning still holds significance. This is because it is advantageous for the model to incrementally learn from new data, rather than undergoing a complete retraining process from scratch.
However, in the context of graph learning, the unavailability of previous data further poses unique challenge in addition to the catastrophic forgetting problem during the inference. Specifically, existing graph-based models often consider nodes in both training and testing data when performing graph operations in the evaluation phase, e.g., aggregating neighbors for test nodes. However, this is not practical in the continual learning setting because a subset of the nodes and edges are from previous tasks and they may not be available for the following tasks.
When existing works evaluate their models under the continual graph learning setting with citation graphs, social networks, co-purchase graphs, during the inference, they re-insert test nodes into the previous training graph and then aggregate the neighborhood information of test nodes to make a prediction (Fig. 2 Such evaluation method is common in a traditional graph learning setting. Nevertheless, in continual graph learning, it is not always practical. This is because in continual learning, training data (previous nodes) from previous tasks are no longer available at the current stage, including both training and inference stage. In a typical continual graph learning scenario, on-the-fly inference is often required. For instance, in node classification, the model needs to infer the labels of streaming test. nodes once it receives them, instead of accumulating large number of test nodes to do inference. Without re-inserting back to the graph, the streaming lest nodes of a relatively smaller size are often very sparsely connected. It means while the model is trained on a dense graph, it is required to infer on a much sparser graph. Fig. ] showcases the above point
hhttps:/ hhlpps://gdlrriing //ppoooo.pp///ee////////
2

---

Published in Transactions on Machine Learning Research (05/2024)
Task
Task
Task 3
GNN
Existing works
GNN
Ours
Unavailable node Test node
Training stage
Inference stage
Figure 2: Different cases during the inference stage. Compared with existing works (Liu al. 2021 Zhou
& Cao 2021 Wang al.] 2022 ours more practical and strictly follows the continual learning paradigm: previous training nodes and edges no longer available during current stage, which includes both the training stage and the inference stage.
in real-world scenario. We study with the user interaction graph from the Stack Exchange platform g and observe notable difference between training and test data density under the continual graph learning setting. The above facts lead to key challenge in addition to catastrophic forgetting in continual graph learning: the neighborhood information available during the inference is very limited. Different from existing works, we consider this practical yet ignored case in our paper and solve this challenge.
Besides, different from existing works that either focus on task-incremental learning and data iata-incremental learning, or focus on class-incremental learning but use a buffer to store previous data for replay to prevent forgetting, in this paper, we focus CI graph learning problem without memory buffers. In light of the umavailability of history data, we are motivated by the success of generative replay based models in image classification tasks and further propose generative replay based GNN model, ReplayGNN (ReGNN), to solve the above challenges. Without requiring storing previous data, it outperforms baseline models including competitive baselines with memory buffers on several benchmark graph datasets.
The main contributions of this paper are as follows: (1) We find an interesting and important yet overlooked fact by existing works on continual graph learning: the unavailability of previous training nodes and edges further lead to the poor neighborhood information problem during the inference stage, in addition to the catastrophic forgetting problem. (2) Taking this ignored fact into account, study the class-incremental graph learning problem without the use of memory buffers. (3) We further propose ReplayGNN to address the problems and the experiments demonstrate its effectiveness in different cases given different levels of neighbor information.
2
Related Work
2.1 Graph Neural Networks
Graph neural networks are popular models for graph representation learning. The success of GNNs has boosted research on many real world tasks based on graph-structured data, ranging from node classifica- tion [Jiang et al. 2019 Rezayi et al. 2021 Jiang et al. 2023 Shi et al. 2023). knowledge graph basod question answering (Hua el al.] 2020), to recommender systems Sheu al. 2022 GNNs can be roughly categorized into two groups: spatial methods (Hamilton et al. 2017] and spectral methods (Kipf & Welling 2016a). GraphSAGE (Hamilton al.) (017)) is typical spatial method, which directly aggregates node representations from node's neighborhoods to obtain its representation, while graph convolutional network (GCN) (Kipf & Welling 2016a). typical spectral method, learns graph representation in the spectral do- main, which alleviates over-fitting on local neighbors via the Chebyshev expansion. To further effectively learn from the local structure, graph altention networks (GAT) (Velickovic el al. (017) adopt an atlention mechanism based on GCN. Both classic spatial and spectral methods need the entire graph during model training. To learn more effectively when scaling large evolving graphs. Some sampling stratogics have
"https//staaceexcannggcm
3

---

Published in Transactions on Machine Learning Research (05/2024)
been developed (Hamilton et al. 2017 Chen et al. 2018 so that only part of the graph is required for each iteration during training.
Although the GNNs have demonstrated their superiority in many graph-related tasks, most of them focus on graph learning on static graph-structured data. However, in real world applications, graphs are often evolving, either in form of data or classes, and history data might be no longer available due to privacy or storage concerns. Traditional GNNs often fail in such cases due to catastrophic forgetting. The performance previous tasks would drop significantly, if the standard GNNs are applied in this setting without any modification.
2.2 Continual Learning
Continual learning studies the problem of learning from streaming data, with the aim of continuously acquir- ing new knowledge while maintaining its learnt knowledge. Current most studied continual learning scttings can be roughly categorized into two calegories (Van de Ven & Tolias 2019) "Task-Incremental Learning (TI), and Class- Inssemmncremttlll Learning (CI). Note that in both TI and CI, number of classes can be increased as the number of task increases. The key difference is that, in TI, the task to which a test sample belongs is provided during the inference (i.e. the task- ID is available during inference). The change of data distribution can stem from different domains (Qi et al. 2024: Zhu et al.) 2024 2023) (i.e., domminn-incremental)) e.g., from the classification of handwritten digital numbers in MNIST (Deng) 2012) to the classification of street view house numbers (etzerr et al.] 2011). The change of data distribution can also be caused by different lasks (i.e., lask-incremental) e.g., from classifying handwrillen digital numbers 0-4 (Task 7) to 5-9 ( (Task 2) in MNIST. A more challenging setting is class-incrementee learning, where the data distribution shift is the result of new incoming classes and the model is required to classify both the previously learnt classes and new classes in all tasks at one time. While in insk-incremental learning, the model needs to distinguish classes within each task but is not required to distinguish classes in different tasks because task-IDs are available.
iaassinnrementll learning (CI) (Rebuffi et al. 2017 is harder continual learning problem due to the un- availability of task-IDs. Representative continual learning models, such as (Kirkpatrick et al.) 2017 and &Li& Hoiem 2017 ; achieve promising performance on Tl benchmarks, but suffer from notably forgetting on simple CI benchmarks. Existing approaches to solve the CT problem can be divided into three cate- gories EEbaahimi et al.) 2020), including the replay- based methods (Rolnick et al. 2019 Chaudhry et al. 2019). structure-based mothods (Yoon et al.] 2017); and rogularization-basee basod methods (Kirkpatrick et al.
2017 Aljundi et al., 2018). Progress has been made in continual learning in recent years, however, only a few of them study continual learning with GNNs.
2.3
Continual Graph Learning
Different continual graph learning settings are explored in recent studies, including Data Incremental Learn-
ing (DI) (Wang et al. 2020 Xu et al.]
2020 Cai et al.) 2022 Han et al.] 2020 Wang et al. 2022), Task-
Incremental Learning (TI) Liu et al.) 2021 Learning
Zhou & Cao 2021 Zhang et al. 2021) and Class- Incremennt
et al. neural architecture search, and (Xu et al. 20200) prevents the recommendation system from forgetting the long term user preference by knowledge distillation. (Daruna et al. 2021) and (Kou et al.) 2020) focus on the continual learning of knowledge graph embeddings. Their mots can be further considered in two scenarios by if they use a buffer to store raw data (Zhou & Cao 2021) or prototypes (Zhang et al. 2021) The most related work to ours includes (Zhou & Cao [0021), (Liu et al. 2021) (Wang et al. 2022) and (Zhang et al.) 2021). DI is not typical continual learning setting, but it is studied in the context of graph learning. In DI, all samples are streamed randomly, while in CT and TI, all samples from a group of classes are streamed before switching to the next group. TWP (Liu et al. 2021 p is a regularization-bast
2022). (Cai et al. 2022) studies continual learning in multi-modal graph with
mot without storing any data or protolypes while (Zhou & Cao 2021). (Zhang et al., 2021 and (Wang et al. 2022) need a buffer to store either raw data or prototypes to prevent forgetting.
However, existing works overlook an interesting and important fact that is unique in the context of continual graph learning compared to regular continual learning in image classification: the unavailability of previous
4

---

Published in Transactions on Machine Learning Research (05/2024)
training nodes and edges lead to limited neighborhood information during inference, in addition to the catastrophic forgetting. Our work differs from existing works in that 1. we consider this ignored fact and 2. we focus on Cl setting without the use of a memory buffer to store raw data or prototypes.
3 Methodology
3.1 Problem Formulation
Class-Incremental Graph Learning defined as follows. Demote a graph as = (V,E). A model learns from sequence of data D {D), ....... D"), where Di= = = Each D is the data distribution of the corresponding task T with 3 being its label space. When performing the task T we assume access to only D', i.e., all data {Dili t is unavailable. The goal is to effectively learn from D', while maintaining the model performance on learnt tasks. At the end of T (i.e., all m tasks are learnt), the model is required to map test samples from all seen data distributions to y U " without task-IDs. Buffers to store row dala or prolotypes are not allowed. More discussions about out setting available Appendix A.
3.2 An Ignored Fact During Inference Stage
In typical image classification scenarios, training data are not required for inference because test samples are assumed to be independent of training samples. In contrast, graph learning often leverages the dependencies between test nodes and training nodes for better inference when learning with large networks. For instance, in many cases, test nodes are re-inserted into the training graph to exploit the dependency by neighbor aggregation for better inference. However, most of existing graph learning models cannot be applied to the continual graph learning scenario the data from previous tasks become unavailable for inference. Besides, directly applying standard graph models often lead to the catastrophic forgetting problem over previous tasks.
2022 Liu et al. 2021 Zhou & Cao 2021 on Tl and CI graph learning However, existing works (Wang el al. overlook the challenge unavailable previous data during inference. Fig. Ollustrates different inference cases in inductive node classification task. We do not consider transductive learning because requires all test samples to appear the graph for training from the beginning, which not practical in CI graph learning, where streaming test samples often appear time. The scenario adopted by existing works not practical because in continual learning, data (i.e. nodes and edges) from previous tasks are no longer available once learned. However, in cxisting works, test nodes with labels from all learnt classes are re-inserted into the graph and connected to previous nodes for inference.
Considering the unavailability of previous training data, we introduce ours as the practical inference sconario in continual graph learning, where previous training nodes are unavailable and only connections among test nodes are kept. In this case, as discussed in section 1, the connections among nodes are very sparse. It leads to unique challenge in graph continual learning: the neighborhood information available for inference is very poor.
3.3 ReGNN
To solve the major challenges in continual graph learn- ing: (1) catastrophic forgetting and (2) limited neigh- borhood information during the inference stage, we pro- pose our model ReplayGNN (ReGNN). Fig. iillustrates how replay data is generated and used and Fig. illus- trates the detailed framework of ReGNN. The proposed GraphCVAE module is maintained to generate old data for replay to prevent forgetting, while the NodeAE mod- ule effectively learns from node attributes with little or no neighborhood information adapt to our introduced inference case in Fig.
Graph Decoder (t-1)
generated data
training data
real data
Figure 3: Composition of training data for current task t. It consists of replay data generated by the copy of the graph encoder from the last task L -- and the training data from the current task t.
5

---

Published in Transactions on Machine Learning Research (05/2024)
Graph Encoder
Graph Decoder
Classifier
Node
=
Encoder
Figure Overview of our ReplayGNN (ReGNN) model. ReGNN consists of three modules with shared components: GraphCVAE, classifier and NodeAE. The input in the figure is node (node,) in mini- batch with its sampled neighbors. The graph encoder consists of the convolution layer of GNN, which outputs low-dimensional embeddings (red) of noder. The GraphCVAE module consists of the graph encoder and graph decoder. The classifier is single classification layer. The NodeAE, which consists of the node encoder and the graph decoder (shared with GraphCVAE), takes a single node embedding as input and (1) tries to reconstruct the structure information and (2) yield node embedding (pink) that is distinguishable for classifier.
Conceptually, GraphCVAE and NodeAE are designed for two different purposes corresponding to two dif- lerent challenges in CGL, but they are inherently associated through a shared graph decoder, which further boosts the model performance as ablation study illustrates.
We use single-layer GNN in model for simplicity. More advanced graph generation techniques be integrated into our graph encoder and decoder if multiple layers are required. Experiments show lightweight model is already effective. More details are discussed in the future work part in Section 5
3.3.1 GraphCVAE
(details are available in Appendix A), we propose a Graph Con- ditional Variational Autoencoder (GraphCVAE) module, which consists of the graph decoder and graph encoder. During task GraphCVAE is trained with real data D' and generated replay data Dg, which is generated by the graph decoder D The generation is conditioned on class labels, which contains all classes learnt before the current task. Different from Variational Graph Auto-Encoders (Kipf & Welling 2016b), which reconstructs the whole adjacency matrix of a graph without node attributes (for link predic- tion during inference), our GraphCVAE, tries to predict the node attributes for the neighbors of target node given its attributes.
Based on VAE (Kingma & Welling 2013)
Graph Encoder. Given input nodes D' with sampled neighbors, the graph encoder first obtains the node embeddings with the forward propagation steps. Denote the input node and hir as the raw features of node u. The output embedding hout is calculated by:
out hN(w) < AGGREGATE (f F Yu (N))))
(1)
hout +- 10 (W (W. WCONCATT (g9t)))
(2)
where W is the learnable parameter and & is the activation function. Similar to the standard VAE, the mean 2, and standard deviation 2, the distribution are calculated from the embodding h by:
Zμ ReLU,W, hoat), 2n ReLU(W, hout
(3)

---

Published in Transactions on Machine Learning Research (05/2024)
where Rectified Linear Unit (ReLU) Nair & Hinton 2010) is the activation function. We and Wo are learnable parameters. With mean 2y and standard deviation Za, latent variable is sampled from the Gaussian distribution MZz zo).
The decoder tries to reconstruct the imput data from the latent variable z. It first generates embedding fo from latent variable z with learnable parameter B, then the input embedding is reconstructed:
Graph Decoder.
f. +B=
(4)
[ [N(o) (M fo);
(5)
where M is the learnable parameter and [a: bj is the concatenation of embedding a and b. The decoded embeddings [feet, JN try to match the input embedding [h." hovt N()) which is the return value of the CONCAT function i This embedding contains the neighbor information of v as well the feature of the node itself. We do not further decode it to obtain {h Vu E [(w)) because the current decoded value already can be the input of graph encoder and be helpful for replay. In other words, we replay the input embedding ! [n)] instead of (hi Yu E [[b) Then the loss functions in GraphCVAB are:
RReoon = -IIST( fout, (N [h. hout )1),
(6)
CKLD = DKLLN(Z =o)]l
(7)
where DIST measures the distance of the two embeddings. Specifically, binary cross entropy is used as the measure of distance here. and DKL is the Kullback-Leibler divergence. c is the class label of input data. The overall loss function is:
Levae C Recon + KLD.
(8)
3.4 NodeAE
Node Autoencoder (NodeAE) consists of the an encoder and a graph decoder. During the training, given node v, as graphSAGE aggregates the neighbors of to obtain its representation, the classifier learns to classify h in Eq. 1 i.c., c(W [h :2t,))) However, during the inference stage, the neighbors of v can be very sparse 2 In this case, the classifier fails to fully exploit its learnt knowledge with rich neighbor information on training graph for inference. Thus during the inference, given a node with only few neighbors, the extracted feature of this node, which fed to the classification layer, is also expected contain the neighbor information of the node. In this way, the node can be better classified by the classifier. We use autoencoder to achieve it.
Given node u, while the graph encoder takes node and its sampled neighbors as input, node encoder only takes the node attribute of node v as input. But the decoder is required to reconstruct the embeddings of the aggregation of its neighbors as well as its own embedding. Another option is to generate random masks to mask certain portion of neighbor nodes of the input node before the neighbor aggregation process, while the decoder also wants do the reconstruction. Here we simply mask all neighbors and only use the input node attribute, which is still effective. The forward propagation of the encoder is:
x (H [h
(9)
where H is the learnable parameter, whose size is the same as W. The loss function is:
_ DIST((((M 2²""), [h h We))
(10)
When trained properly, given an isolated node, the node encoder can map the node attribute into a com- pressed embedding an that contains its neighbor information and is then used for prediction.
7

---

Published in Transactions on Machine Learning Research (05/2024)
Table 1: Accuracy on different datasets under class-incremental learning scenario.
Scenario
Dataset
Model
No Memory Buffer
Memory
Citeseer
Cora
Amazon
M 1%
34.13 + 0.14
41.78 + 0.62
50.53 + 2.94
ER-GNN Zhou Cao
2021
x
41.46 + 2.32
51.96 +: 1.65
60.33 +: 2.85
5%
45.48 + 2.35
57.96 + 2.58
67.82 + 2.23
M 1%
35.94 = 0.28
38.48 = 0.17
49.53 = 1.74
ContimuaIGNN
Wang et al.
2020
X
3%
46.08 + 0.45
46.49 + 0.51
56.78 +: 2.04
M 5%
50.60 +: 0.49
60.41 + 1.91
60.79 +: 2.23
GraphSAGE Hamilton
2017
31.02 0.12
25.00 + 0.14
37.01 = 0.43
LwF [L & Hoiem 2017
36.74 + 1.15
42.27 + 1.54
50.01 + 1.83
ReGNN (Ours)
55.02 2.01
64.33 1.82
69.32 1.48
3.5 Classifier
The classifier is a single classification layer and takes the output of the graph encoder and the node encoder as input. The loss function for classification is:
Cdl = Loe (g(x h ),
(11)
where Lee is the cross entropy loss function, and g(-) is function that combines two embeddings, and we simply add them together. Note that the current training data are a mixture of real data and replay data as illustrates. y are their corresponding labels.
By summarizing the three modules together, the overall loss function for our ReGNN model is:
C RRGGNN Lole + Levae + Lee.
(12)
4 Experiments
4.1 Datasets
Following related works (Wang et al. 2022 Liu et al. 2021 Zhou & Cao
2021 we conduct experiments
on three benchmark datasets under the continual learning settings: Cora (en et al. 2008). CiteSeer (Sen
ett al. 2008), and Amazon (McAuley et al. 2015), which is a segment of Amazon co-purchasing graph.
We split each dataset into several tasks, following (Luu et al. 2021 Zhou Cao 2021 Wang et al. 2022
CoraFull (McCallum
al.) 22000) and Arxiv (Hu et al. 2020) are both citation networks. Red-
dit (Hamilton et al., (0017) the co-purchase network. Details about dataset information and how we build tasks for continual lcarning scenario are available in Appendix A.
post-to-post graph. The Products (Hu et al., (2020) dataset is
In our inaseenncelmttal setting, we divide Cora into three tasks. The first and second tasks consist of two classes, and the last task has three classes. Citesecr are split into three tasks with two classes cach task. The first. lask of Amazon has two classes. The second and third tasks on Amazon dataset have three classes. The model is required classify all learnt classes without using task-IDs.
4.2 Baselines
We adopt the following baselines in experiments. GraphSAGE (Hamilton al. 2017 is representa- tive GNN model, which is also used as the backbone for some other basclines for fair comparison. LwF (Li & Hoiem 2017) is a representative data-free continual learning model, which uses the history state of itself as the teacher for knowledge distillation to avoid forgetting. ER-GNN (Zhou Cao 2021) uses a buffer to store data for experience replay, in order to prevent from forgetting. ContinualGNN WWagg al. 2020) al- leviates forgetting by storing data for replay and adopts model regularization similar EWC (Kirkpatrick
et al. 2017). Finetuning is the lower bound baseline by updating the model only with newly incoming
8

---

Published in Transactions on Machine Learning Research (05/2024)
Table 2: Accuracy on Citeseer dataset at different levels of neighborhood information. Best results in bold.
Model
Default
3-hop
5-hop
Full
ER-GNN (M=1%)
34.13 + 0.14
36.44 = 0.42
36.64 0.25
38.65 0.93
ER-GNN (M=3%)
41.46 + 2.32
49.29 = 2.76
50.20 + 2.23
58.82 + 3.32
ER-GNN (M=5%)
45.48 + 2.35
55.82 = 0.56
57.53 1.27
61.44 + 2.18
ContinuaIGNN (M-1%)
35.94 + 0.28
40.06 = 0.85
41.67 0.99
41.46 1: 1.50
ContimualGNN (M=3%)
46.08 + 0.45
52.71 + 1.22
53.81 + 1.44
55.02 1 1.26
ContinualGNN (M=5%)
50.60 + 0.49
57.22 = 1.22
58.63 1.35
60.14 +: 1.35
GraphSAGE
31.02 + 0.12
31.02 = 0.19
30.72 + 0.39
31.92 + 0.46
LwF
36.74 + 1.15
40.65 = 1.06
42.85 + 1.34
48.97 + 1.03
ReGNN (Ours)
55.02 + 2.01
62.57 1. 2.12
64.57 1: 2.34
67.74 +: 2.12
graphs. Joint the ideal upper bound situation where the memory bank contains all historical incoming graphs. EWC (Kirkpatrick et al., 2017] applies quadratic penalties the model weights that are important to the previous tasks. MAS [Aljundi et al.) 2018) utillses regularisation term for parameters sensitive to the model performance of historical tasks. GEM (Lopez- Paze & Ranzato 2017) modifies the gradients using the informative data stored in memory. TWP (Liu et al.] 2021
preserves the topological information for distils the knowledge from the old model to the new model to keep the previous knowledge. ER-GNN (Zhou & Cao 2021 samples the informative
previous tasks by a regularisation term. LwF Li & Hoiem 2017
nodes from incoming graphs into the memory bank. SSM (Zhang et al., 2022) stores the sparsified incoming graph in the memory bank for future replay.
Although in data-free continual learning sctting, data be stored for replay, show that ReGNN outperforms ER-GNN (Zhou & Cao 2021 and ContinualGNN
al. 2020), which use memory buffers for replay. Because ER-GNN Zhou & Cao 2021) already outperforms continual learning models EWC (Kirkpatrick et al.) 2017) and GEM (Lopez- Paz & Ranzato 2017), we only report the results for ER-GNN. More discussions about choices of basclincs are available in Appendix A.
Experimental Setup. We use the neighborhood sampling strategy in GraphSAGE for all models when sampling available. Details of experiment settings are available in Appendix A.
4.3
Main Results
Table
shows the main results of our model and basclines. The proposed ReGNN outperforms LwF Li &
Hoiem 2017). which also does not require memory buffer as our model, by a large margin. ER-GNN Zhouu
& Cao 2021 is strong baseline modified from experience replay. Experience Replay, a typical memory based method, is a competitive baseline because it is able to access the old data during training by maintaining
memory buffer, and it often notably outperforms the regularization based methods in class- dlss-incremmntal
learning scenario (Buzzega et al. 2020 2021 with a small buller size (e.g., 2% in (Buzzega et al. 2021) The shortage of memory based methods is that they need memory buffer to store data, which is not always feasible. We experiment with memory size M = {1%, 3%, 5%} } for memory based models. Experiment results show the effectiveness of ReGNN in class incssmenceeeetall setting. Our model still outperforms ER-GNN ZZouu & Cao p021 and ContinualGNN (Wang et al., 22200) when they have a buffer with memory size M 5%.
This is considered to be relatively large buffer size in continual learning, given that the actual number of stored nodes, including the neighbor nodes for aggregation, is larger than reported M.
In Tab. we compare our model with more continual learning baselines on graph with larger scale. In Tab. we show detailed data statistics of the benchmarks. We consistently outperform baselines under the same memory-free scenario (i.e,, all previous data are dropped and are not allowed to be stored in a memory buffer).
In Tab. we show results of our model and memory-basee models. We show their results with (marked with 'Required' in the table) and without (marked with L in the table) memory buffers. We kindly remind that
9

---

Published in Transactions on Machine Learning Research (05/2024)
Table 3: Results of replay based models on Citeseer when neighbors of the stored old nodes are available in the memory buffer.
Model
Default
3-hop
5-hop
Full
GraphSAGE lamilton et al.
2017]
31.02
31.02 (J 0.00)
30.72 (4 0.30)
31.92 (1 0.90)
ContimalGNN (*) (Wang al.
2020
41.86
45.28 (U 3.42)
47.89 (L 6.03)
47.59 (J 5.73)
ER-GNN (*) Zhou & Cao
2021
43.37
41.56 ()) 1.81)
40.69 (1) 2.68)
42.21 (+ 1.13)
ER-MLP (*) Rolnick et al.
2019
39.23
37.17
(J 2.06)
36.32 (4 2.91)
36.74 (J 2.49)
ReGNN (Ours)
55.02
62.57 (1 7.55)
64.57 (1 9.55)
67.74 (f 12.72)
Table 4: Datasot Statistics.
Dataset
Nodes
Edges
Features
Classes
CoraFull (McCallum et al. 2000)
19,793
130,622
8,710
70
Arxiv (Hu et al.) 2020
169,343
1,166,243
128
40
Reddit Hamilton et al. 2017
227,853
114,615,89
602
40
Products (Hu 2020
2,449,028
61,859,036
100
46
they are not our baselines because (1) we work under different scenarios (memory-based v.s. memory-free), and (2) storing previous data in a memory buffer (i.e., memory-basee makes the problem significantly easier and is not a fair comparison.
Interestingly, even without a memory buffer, our method outperforms GEM, ER-GNN, SSM on all benchmarks, and CaT Products in Tab. 6 When evaluating the memory-based models under memory-free scenario, where their memory buffers are removed, they lose the ability to prevent forgetting and degrade to lower-bound performance.
Table 5: Comparison with Memory-free Baselines. CL Model refers to Continual Learning Model.
Methods
CL Model
Memory
CoraFull
Arxiv
Reddit
Products
Finetuning
No
1.9
4.3
4.2
3.6
GLNN
No
1.9
3.9
3.2
NOSMOC
No
1.9
4.3
3.6
EWC
Yes
2.3
4.0
4.2
6.1
MAS
Yes
1.8
3.9
8.7
8.2
TWP
Yes
3.1
7.4
5.2
LwF
Yes
1.9
4.3
4.2
3.6
ReGNN (Ours)
Yes
18.7
32.7
45.8
56.4
Inference at Different Levels of Neighbor Information. Table shows the effectiveness ReGNN in our practical scenario for continual graph learning illustrated Fig. and Fig. 2 where the neighbor- hood information for test nodes is poorly available or completely unavailable. A natural question is, whether ReGNN can also achieve good performance in different cases where the neighborhood information is provided at different levels. This could be valuable when additional information is available to help build richer con- nections between test nodes for more neighborhood information and better inference. We further investigate the performance of ReGNN in different cases.
Because we randomly split the data into training and test sets and also detach the test nodes from the original graph, we cannot control the level of neighborhood information among test nodes with the random partition process. Instead, we change the level of neighborhood information by manually linking test nodes according to their distance to each other in the original graph.
10

---

Published in Transactions on Machine Learning Research (05/2024)
Table 6: Comparison with Memory-based Baselines, CL Model refers Continual Learning Model.
Methods
CL Model
Memory
CoraFull
Arxiv
Reddit
Products
GEM
Yes
Required
2.1
4.1
4.0
3.3
1.9
4.3
4.2
3.6
ER-GNN
Yes
Required
3.1
23.8
22.9
31.0
1.9
4.3
4.2
3.6
SSM
Yes
Required
12.1
26.9
39.7
49.2
1.9
4.3
4.2
3.6
CaT
Yes
Required
50.4
53.8
78.9
54.9
1.9
4.3
4.2
3.6
ReGNN (Ours)
Yes
18.7
32.7
45.8
56.4
Specifically, given a pair of nodes (u, u) from detached test nodes, we denote the distance from v to u as (u u); which is calculated by the number of hops from v to u in the original graph. Original graph refers to the complete graph before the training-test split. In this way, we can increase the neighborhood information of test nodes by manually linking pairs of test nodes. For instance, (v.u) can be linked if Dist(u, u) is smaller than certain threshold k. After linking all node pairs {(e, u) Dist(r, u) < k E Viest, u E Veest) } in the test nodes, we denote the evaluation on the test data with this additional neighborhood information as k-hop evaluation. Note that the way we increase the neighborhood information can involve noise if is set to a very large number, which consequently leads to a performance drop. In our experiments, we empirically choose a proper that is smaller than a threshold, as larger & values fail to further improve the performance.
Experiments show that the manually added links are helpful for node classification. Because in k-hop evaluations, manually select proper k and add these links according to the original complete graph. An interesting future direction is to train an additional task, for instance, link prediction, to predict these links and then link them for better node classification. In this work, we just manually add these links and focus on analyzing the ReGNN model with h - hop evaluation.
Tab. shows the results of this study. Default means no additional links are added. & refers k-hop evaluation, and Full is the evaluation method adopted by existing works in Tab. 2 i.e., linking the detached test nodes back to the graph from which they detached for inference. Intuitively, Full should yield best results. Compared to the results of the default evaluation, increasing neighborhood information can indeed improve our model performance. ReGNN constantly outperforms other baselines under different settings, which manifests the reliability and effectiveness of our model and indicates that our model can work well in different cases with either rich or poor neighborhood information.
Preserving Neighbor Information via Generative Replay. Because each node is associated with a node attribute, simply replaying and using node attributes can also make predictions. Although ReGNN outperforms other baselines, remember the neighbor information and effectively exploit. them for inference, or it is just simply replaying the attribute of the input node.
curious to know whether generated replay data really help ReGNN
To study this problem, we conduct another experiment with different baseline models ER-GNN & Cao 202Tp. p ContinualGNN(*) (Wang et al.) (020) and MLP+ER (*) (Rolnick et al. 2019). where (*) indicates the memory buffer only store nodes without their neighbors, thus the neighbor information cannol be replayed. Different from other models, ER-MLP does not include GNN and uses MLP to learn from isolated node features without neighbor information. We add experiencer replay similar to ER-GNN for continual learning setting.
Zhou
We start with analyzing how ER-GNN remembers the neighborhood information. ER-GNN requires a memory buffer to store old training nodes from previous tasks for replay to prevent forgetting. When replaying stored old nodes from the buffer, the neighbor nodes of the old nodes need be sampled the sampling strategy in graphSAGE for aggregation to compute the embeddings of stored old nodes. Thus in earlier experiments, allow ER-GNN to store the neighbors of the stored old nodes to fulfill the model's
11

---

Published in Transactions on Machine Learning Research (05/2024)
Table 7: Ablation study results.
Method
Accuracy
Full Method
55.02 2.01
Ablate NodeAE
52.40 +: 2.14
Use separate GraphCVAE
51.21 +: 1.79
Ablate GraphCVAE (No replay)
31.02 + 0.12
potential. In this case, the memory size of the buffet is in fact larger than our reported 1% 3% 5%, because their neighbors are also stored for the neighbor aggregation process in GraphSAGE. In this way, when ER- GNN uses old data for training, the neighborhood information of the stored old nodes also replayed. Thus ER-GNN remember and exploit the neighbor information during inference, which is proved by results as k hop increases, ER-GNN achieves better performance by using the richer neighbor information.
in 2
Here we experiment with another version of ER-GNN and ContinualGNN, where the neighbors of stored old nodes are not available, which means only their own node attributes are used for replay. 3 shows, in this case, ContinualGNN (Wang et al. 2020) still has improvements as increases because also uses model regularization besides data replay. However, the performance of ER-GNN, which fully relies on data replay, fails to be improved & increases (i.e., richer neighborhood information is provided), which means ER-GNN cannot exploit neighborhood information anymore. This is because only isolated node attributes without neighbor aggregation thus model forgets how to exploit given neighbors. Note that only replaying node attributes helps to remember the features of isolated nodes, thus it still outperforms graphSAGE by a large margin. ContimuaGGNN (Wang et al., 2020 still has improvements as k increases because it also uses model regularization besides data replay.
replayed
The performance of our model consistently grows with richer neighborhood information, indicating that ReGNN remembers how exploit given neighbors for better inference by replaying our generated data. It further manifests our generated data contains helpful neighborhood information, which prevents ReGNN from forgetting it during generative replay.
4.4 Ablation Study
To simplify the model structure, we use the graph convolution layer in GNN as the graph encoder for the GraphCVAE. We are curious about whether sharing paramcters can further improve the performance. To study this point, we train a separate GraphCVAE that owns an separate graph encoder. In this way, the GraphCVAE becomes a separate model without any shared parameters with others. It follows the reprosentative generative replay based framework (Shin et al. 2017), where an scparate generative model is trained for replay without any interactions, such parameter sharing, with the classification module.
Through the ablation experiment, We find that sharing part of the parameters (i.e., the graph encoder) not only simplifics the model structure, but also improves the performance of the model. It indicates proper parameter sharing learns better than using two separate modules. The two reconstruction process can share some useful information with each other for better representation learning. Finally we ablate the GraphCVAE module to stop generative replay. The forgetting phenomenon becomes obvious.
A clear performance drop is observed after removing NodeAE in Tab. 7 It manifests the effectiveness of learning to reconstruct the neighbors from single node attribute embeddings with node AE module.
5 Conclusions and Future Work
In this paper, we find an important and practical case that has been ignored by existing works in continual graph learning: the unavailability of previous data leads to sparse neighborhood information during inference,
12

---

Published in Transactions on Machine Learning Research (05/2024)
in additional to the challenge of catastrophic forgetting. We further propose ReGNN to jointly solve the challenges, whose effectiveness is supported by the experiments.
More advanced graph generation techniques can also be integrated into our graph encoder and decoder modules for better graph generation, which we we leave for future work. It has rarely been studied to generate large graphs with different node attributes, and most of existing works on this topic focus on molecular graph generation (Simonovsky & Komodakis 2018) Mitton et al, 2021). Some other works (Bojchevski et al. 2018 Wang et al. 2018) learn to generate sub-graph for large graphs, which focus on the structure reconstruction. However, the node features, which are critical in many real applications, are not considered in these methods. Effective graph generation with node attributes is another under-explored topic and is beyond the scope of this paper. One promising future direction is to integrate such a generation process with the proposed method in this paper. k hop evaluations have better performance but we mamually set & and build links with ground truth. We will also explore automating this process so that the model can infer the connections by itself improve model performance.
Acknowledgement
The work is in part supported by the the U.S. Army Research Office Award under Grant Number W911NF- 21-1-0109, the National Science Foundation under Grants ITS-2316305 and I1S-2316306, the Cisco Faculty Award, and the Adobe Data Science Research Award.
References
Rahaf Aljundi, Francesca Babiloni, Mohamed Elhoseiny, Marcus Rohrbach, and Tinne Tuytclaars. Memory aware synapses: Learning what (not) to forget. Proceedinggs of the European Conference on Compuler Vision (ECCV), pp. 139 154, 2018.
Aleksandar Bojehevski, Oleksandr Shehur, Daniel Zügner, and Stephan Günnemann. Netgan: Generating graphs via random walks. In International Conference on Machine Learning, pp. 610-619. PMLR, 2018.
Pietro Buzzega, Matteo Boschini, Angelo Porrello, Davide Abati, and Simone Calderara. Dark experience for general continual learning: strong, simple baseline. Advonces in neural information processing systems, 18:15920-15930 2020.
Pietro Buzzega, Matteo Boschini, Angelo Porrello, and Simone Calderara. Rethinking experience replay: a bag of tricks for continual learning. In 2020 25th International Conference on Pattern Recognition (ICPR), pp. 2180 2187. IEEE, 2021.
Jie Cai, Xin Wang, Chaoyu Guan, Yateng Tang, Jin Xu, Bin Zhong, and Wenwu Zhu. Multimodal continual graph learning with neural architecture search. In Proceedings of the ACM Web Conference 2022, pp. 1292-1300, 2022.
Arslan Chaudhry, Marcus Rohrbach, Mohamed Elhoseiny, Thalaiyasingam Ajanthan, Puneet K Dokania, Philip HS Torr, and Mare' Aurclio Ranzato. On tiny cpisodic memories in continual learning. arXiv preprint ar Xiv:119902 10486, 2019.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. Xixiv preprint or 1=X.::1801.1044 2018.
Angel Daruna, Mehul Gupta, Mohan Sridharan, and Sonia Chernova, Continual learning of knowledge graph embeddings. IEEE Robotics and Automation Letters, 6(2):1128 1135, 2021.
Li Deng. The mnist database of handwritten digit images for machine learning rescarch. IEEE Signal Processing Magazine, 29(6):141 111141111111111111 2012.
Sayna Ebrahimi, Franziska Meier, Roberto Calandra, Trevor Darrell, and Mareus Rohrbach. Adversarial continual learning. In European Conference Computer Vision, pp. 386-40 686-402. Springer, 2020.
13

---

Published in Transactions on Machine Learning Research (05/2024)
Lukas Galke, Benedikt Franke, Tobias Zielke, and Ansgar Scherp. Lifelong learning of graph neural networks for open-workd node classification. In 2021 International Joinl Conference Newral Networks (IJCNN), pp. 1- 8. LEEE, 2021.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Yi Han, Shanika Karunasckora, and Christopher Leckic. Graph noural networks with continual learning for lake news detection from social media. arXiv preprinl ar WxXiv:2007.03316 2020.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In NewrIPS, 2020.
Yuncheng Hua, Yuan-Fang Li, Guilin Qi, Wei Wu, Jingyao Zhang, and Daiqing Qi. Less is more: Data- efficient complex question answering over knowledge bases. Journal of Web Semantics, 65:100612, 2020.
Xiaodong Jiang, Pengsheng Ji, and Sheng Li. Censnet: convolution with edge-node switching in graph neural networks. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 2656 2662, 2019.
Xiaodong Jiang, Ronghang Zhu, Pengsheng Ji, and Sheng Li. Co-embedding of nodes and edges with graph neural networks. IEEE Transaclions on Pollern Analysis and Machine Intelligence, 45(6):7075- 7086, 2023.
Diederik P Kingma and Max Welling. Auto-encoding variational bayes. ar preprint drXiv:1312.6114, 2013.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint 1609 02907, 2016a.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. NewrIPS, 2016b.
James Kirkpatrick, Razvan Pascamu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei Rusu, Barnnkaa-a-aiiskaa,aaa al. Overcoming catastrophic
Kieran Milan, John Quan, Tiago Ramalho, Aguieszka forgetting in neural networks. Proceedings of the national academy of sciences, 114(13):3521-35 --226,, 2017.
Xiaoyu Kou, Yankai Lin, Shaobo Liu, Peng Li, Jie Zhou, and Yan Zhang. Disentangle-basee contimual graph representation learning. arXiv preprint "XXi:2010.02506 2020.
Zhizhong Li and Derek Hoiem. Learning without forgetting. IEFE transactions on pattern analysis and machine intelligence, 40(12):2935 2947, 2017.
Huihui Liu, Yiding Yang, and Xinchao Wang. Overcoming catastrophic forgetting in graph neural networks. AAAI, 2021.
David Lopez-Paz and Mare' Aurelio Ranzato. Gradient episodic memory for continual learning. Advances in neural information processing systems, 30, 2017.
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image- recommen- dations styles and substitutes. In Proceedings of the 38th international ACM SIGIR conference research and development in information retrievol, pp. 43 52, 2015.
Andrew McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Inf. Retr., 2000.
Michael McCloskey and Neal J Cohen. Catastrophic interference in connectionist networks: The sequential learning problem. In Psychology of learning and motivation, volume 24, pp. 109-165. Elsevier, 1989.
Joshua Mitton, Hans M Senn, Klaas Wynne, and Roderick Murray-Smith. A graph vae and graph transformer approach to generating molecular graphs. arXio preprint or orXin:2104.04346 2021.
14

---

Published in Transactions on Machine Learning Research (05/2024)
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In Icml, 2010.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011.
Daiqing Qi, Handong Zhao, and Sheng Li. Better generative replay for continnal federated learning, 2023.
Daiqing Qi, Handong Zhao, Aidong Zhang, and Sheng Li. Extending to new domains without visual and textual oracles, 2024. URL httpp////ppaareeeeeeeeee////rerp ottp:///ww....e///ooooooooooooaa
Sylvestre-Alvise Rebuffi, Alexander Kolesnikov, Georg Sperl, and Christoph H Lampert. icarl: Incremental classifier and reprosentation learning. In Proceedings of the IEEE conference Computer Vision and Pallern Recognilion, pp. 2001 2010, 2017.
Saed Rezayi, Handong Zhao, Sungchul Kim, Ryan Rossi, Nedim Lipka, and Sheng Li. Edge: Enriching knowledge graph embeddings with external text. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 2767 2776, 2021.
David Rolnick, Arun Ahuja, Jonathan Schwarz, Timothy Lillicrap, and Gregory Wayne. Experience replay for continual learning. Advances in Newral Information Processing Systems, 32, 2019.
Prithviraj Sen, Galilco Namata, Mustafa Bilgic, Lisc Getoor, Brian Galligher, and Tina Eliassi-Rad. Collec- live classification in network data. Al magazine, 29(3): 93, 2008.
Heng-Shiou Sheu, Zhixuan Chu, Daiqing Qi, and Sheng Li. Knowledge-guided article embedding refinement for session-based news recommendation. IEEE Transactions on Neural Networks and Learning Systems, 33(12):7911-7927, 2022. doi: 10.1109/TNNISS TENLNNNNNSSOO 122.4.99995.
Weili Shi, Xueying Yang, Xujiang Zhao, Haifeng Chen, Zhiqiang Tao, and Sheng Li. Calibrate graph neural networks under nut-of-distribution nodes via deep q-learning. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pp.
2023.
Hanul Shin, Jung Kwon Lee, Jachong Kim, and Jiwon Kim. Continual learning with deep generative replay. Advances in newral information processing systems, 30, 2017.
Martin Simonovsky and Nikos Komodakis. Graphvac: Towards generation of small graphs using variational autoencoders. In International conference on artificial newral networks, pp. 412 422. Springer, 2018.
Sebastian Thrun. Is learning the n-th thing any easier than learning the first? Advances in neural information processing systems, 8, 1995.
Gido M Van de Ven and Andreas S Tolias. Three scenarios for continual learning. arXiv:1904.0799: 2019.
arXiv preprint
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.
Graph attention networks. stat, 1050:20, 2017.
Chen Wang, Yuheng Qiu, Dasong Gao, and Sebastian Scherer. Lifelong graph lcarning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 13719-13728, 2022.
H Wang, Wang, J Wang, et al. Graph representation learning with generative adversarial nets. AAAT, Graphgan, 2018.
Junshan Wang, Guojic Song, Yi Wu, and Liang Wang. Streaming graph neural networks via continual learn- ing. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pp. 1524, 2020.
15

---

Published in Transactions on Machine Learning Research (05/2024)
Yishi Xu, Yingxue Zhang, Wei Guo, Huifeng Guo, Ruiming Tang, and Mark Coates. Graphsail: Graph struc- ture aware incremental learning for recommender systems. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pp. 2861 2868, 2020.
Jachong Yoon, Funho Yang, Jeongtae Lee, and Sung Ju Hwang. Lifelong learning with dynamically expand- able networks. arXic preprint arXiv: 1eo.00108011 01547, 2017.
Xikun Zhang, Dongjin Song, and Dacheng Tao. Hierarchical prototype networks for continual graph repre- sentation learning. orXiv preprint ar arXiv:2111.15422, 2021.
Xikun Zhang, Dongjin Song, and Dacheng Tao. Sparsified subgraph memory for continual graph represen- tation learning. 2022 IEEE International Conference on Data Mining (ICDM), pp. 1335 1340. IEEE, 2022.
Fan Zhou and Chengtai Cao. Overcoming catastrophic forgetting in graph neural networks with experience replay. AAAI, 2021.
Ronghang Zhu, Dongliang Guo, Daiqing Qi, Zhixuan Chu, Xiang Yu, and Sheng Li. Trustworthy represen- tation learning across domains, 2023.
Ronghang Zhu, Dongliang Guo, Daiqing Qi, Zhixuan Chu, Xiang Yu, and Sheng Li. A survey of trustworthy representation learning across domains. ACM Trans. Knowl. Discou. Data, apr 2024. ISSN 1556-4681. doi: 10.1145/3657300 URL httph::///oo/ /t////...00/1111114/////777000 Just Accepted.
A Appendix
A.1 Dataset
To evaluate the performance of ReGNN in our continual graph lcarning scenario, we conduct experiments on three benchmark datasets that are also used build datasets for continual learning settings in related
works (Wang et al. 2022: Liu et al. 2021 Zhou & Cao 2021): : Cora (Sen et al. 2008), CiteSeer (Sen et al.
2008), and use Amazon (McAuley et al. 2015) to refer to AoazooCoBuyyPhotoe
segment of Amazon
co-purchasing graph. We split each dataset into several tasks, following (Liu et al. 2021 Zhou & Cao 2021
Wang et al. 2022).
Cora (Sen et al. 2008 is a citation network consisting of and 5429 links and 2708 nodes classified into one of seven classes. Each node has a vector of size 1433 as attribute.
CiteSeer (Sen et al.
2008 consists of 3312 publications classified into of six classes. The citation
network consists of 4732 links. Each node has vector of size 3073 its attribute.
Amazon (McAuley et al.
2015) to refer to AmazonCoBuyPhoto, segment of Amazon co- co-purchasing graph.
It consists of 119,043 links with 7,650 nodes of 8 classes.
To construct datasets for inas-inncementll graph learning, we follow (Liu el al., 2021 Zhou Cao, 2021 Wang et al. 2022) and divide each dataset into several tasks, where each task contains several non-overlapping classes. For Cora, we divide it into three tasks. The first and second tasks consist of two classes, and the last task contains three classes. Citeseer are split into three tasks with two classes in each task. The first task of Amazon contains two classes. The second and third tasks on Amazon contain three classes.
A.2 Experiments
A.2.1
Experimental setup
SGD optimizer used and the initial learning rate is set to 0.01 for Cora and Citeseer and 0.005 for Amazon. The batch size it set 128 and run 100 epochs for each datasct. For baselines, the number of layers GNN is set the default value according to their papers. A standard two layer GNN is used if the information is not provided. We run each experiment five times and report the results with mean and standard deviation.
16

---

Published in Transactions on Machine Learning Research (05/2024)
Note that otherwise specified, the buffer size M of the baseline modes (if buffer required) is the number of stored nodes withoul their neighbors. We also store their neighbors for aggregation process so that the structure information can also be replayed, which fulfills their model potential. Thus the total number of stored nodes in buffer actually larger than M (It equals to M + the number of their neighbor nodes).
A.2.2 Baselines
As ER-GNN is a strong baseline for graph class incremental learning, which already outperforms baselines such as EWC, GEM, we only compare with most competing baselines. Note that even ER-GNN is not necessarily our baseline because it uses memory buffers to store history data (it is a 'cheat"), while we do not have any history data. For fair comparison, we should compare with models without memory buffers. Because we are the first study graph class incremental learning without buffers, we make concessions and compare our model with competing baselines with bullers.
A.3 Variational Autoencoders
Autoencoders (AE). An autoencoder is a type of a neural network, which aims to encode the input into compressed and meaningful representation, and then decode it back such that the reconstructed input is similar as possible to the original onc. The main purpose is to learn an informative representation of the data that can be used for various implications in unsupervised manner. A typical AE learns two functions A: I" + R and B: I + R² that satisfy:
arg mim E| B A(x)) A,B
(13)
where E' is the expectation over the distribution of and A is the reconstruction loss function, which measures the distance between the output of the decoder and the input.
Variational Autoencoders (VAE). (Kingma Welling 2013) VAE is a generative model that similar AE in structure. Tt provides a formulation which the encoding 2 interpreted as latent variable in probabilistic generative model. And a probabilistic decoder defined by a likelihood function ps(x, z) parameterized by 6. Alongside prior distribution pz(z) over the latent variables, the posterior distribution (z|x) x (x|2) can then be interpreted as a probabilistic encoder.
To avoid the huge complexity, the approach simultaneously learns both the parameters of px(2))) as well as those of a posterior approximation qo (z/x). This is achieved by maximizing the evidence lower bound (EIBO)):
L(o. 8: x) (xs() (x z) go
(14)
with L(o, x;x) < (x)) Wide flexibility in choice of encoder and decoder models is allowed because the ELBO can be maximized via gradient descent as long as (x(zz) and (z(x))) can be computed point wise, and are differentiable with respect to their parameters. Conditional VAE (CVAE) is slightly different from VAE in that, the encoder and decoder are conditioned on x and another given variable c. our case, is the class label of
A.4 Continual Graph Learning
In this section, we disuess the motivation of our setting.
We first illustrate (1) the differences of our motivation and previous works, then explain (2) why also evaluate on two citation graphs, in addition to the AmazonCoBuying network, which is real-world case for our motivation.
In short, our proposed scenario strictly follows continual learning, where training data are dropped once used (thus not available at both training and inference stage) due to multiple reasons like GDPR data regulation, privacy issues.
This motivation is very different from existing works such as ContimalGNN WWagg et al. 2020 where training nodes are available during both training and inference stage, and they simply choose to avoid using
17

---

Published in Transactions on Machine Learning Research (05/2024)
previous training data at current training stage for efficiency. In our case, previous training data are unavail- able due to multiple reasons mentioned above, which strictly follows the continual learning scenario (Van de Ven & Tolias 2019). Note that although existing works mentioned "continual learning" (in general sense) in their presentation, in fact it is not a standard continual learning setting because their history data are actually not unavailable. That is why we propose our scenario, where history data are actually unavailable due practical reasons.
We do not use citation networks real-world examples, instead, we use them to build class-incremental tasks evaluation of our model, which are also adopted in related works (Liu et al. 2021 Zhou & Cao. 2021 We just follow them to evaluate our model performance.
Besides, we also experiment with the AnazonCoBuying network, where it is natural that history nodes are not available after use due to storage constraints, privacy issues (for example, transaction records have to be deleted due to data regulation or user preference), etc. In these cases, training data have be dropped after training and not available across future training and test slages.
In the following, We summarize the motivation of our practical scenario from three aspects.
(1) Comparison with Existing Works
Let us start from continual learning (CL), in typical CL, previous training data are not available due to a series of reasons, such as privacy issues, deletion by users, storage pressure, etc. Graph continual learning, is a type of continual learning (CI.) but on graph. Therefore, existing works follow CL and assume that previous training data are already dropped and not available during training. However, the uniquenoss of graph learning is, the training data could be used during inference.
Here is the problem: existing typical continual learning works often focus on image classification, thus dropping previous training data does not influence the inference (because in image classification, training data not required during inference). However, in graph learning, training data is often required during inference. But according to the standard setting in continual learning, training data is already dropped and no longer available.
However, existing graph continual learning works simply ignored the fact that "training data is al- ready dropped and no longer available" and still use them for inference, which is contradictory. Our work corrects this contradiction.
(2) Practical Scenarios
In practice, frequently, historical data is unavailable due to privacy issue, deletion by users, storage pressure, etc. For instance, in social networks or user interaction graphs, history records (nodes and links) will be deleted and thus become unavailable due to customer data storage consent, such as the 30-days rigat-of-erasure in General Data Protection Regulation (GDPR). Besides, they can also be unavailable if users choose to hide or delete their history records.
Besides citation networks, have also used the Amazon Co-purchasing networks, which could be more practical because historical data could be hidden or deleted by users, and they could also become unavailable due to customer data storage consent (such as 30-days right-of-crasure in GDPR). In this case, previous training data is no longer available no matter for current training or testing.
(3) Citation Benchmarks as Simulator
In public citation networks such as Cora, existing papers are always available for inference. In fact they even always available for training well. Although in public citation networks, papers are in fact always available for both training and inference, existing works still assume that previous papers are not available for training because they just want to use citation networks to simulate the cases where the
18

---

Published in Transactions on Machine Learning Research (05/2024)
previous data is unvaillabl. Citation networks are commonly used because they are prevalent.
We also use citation networks for the same purpose: to simulate the cases where previous data is dropped and unavailable due to privacy issues, deletion by users, storage pressure, etc.
19


Reviews:
[{"review_id": "Wgz40vVBGR", "reviewer": "Reviewer_QCHX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The proposed model is well-motivated (and simple which is bonus) to handle the challenges stemming from the more realistic learning scenario.\n- ReGNN outperforms the baselines with a good margin, includes baselines that additionally use a memory buffer\n- The experimental evaluation is thorough and convincing (although I'm not very familiar with the graph CL literature).\n\nWeaknesses:\n-  Manually linking test nodes based on distance in the original graph seems like an odd choice. A different way to control the level of neighborhood information (e.g. a more \"stratified\" train-test split) might be more informative. However, I believe this can be left for future work.\n- The datasets are not a good representative of real-world graph CL problems (even though they are often used as benchmarks). For example, citation networks are not likely to \"evolve\" in a class-incremental manner. This may lead to overly optimistic methods for all baselines.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies class-incremental graph learning under (what they argue to be) a more realistic assumption: historical data may be unavailable during both training and inference. This poses additional challenges for graph learning, e.g. stemming from (neighborhood) sparsity. The authors propose a generative replay based model that does not (explicitly) rely on memory buffers. Their model has to key modules: a conditional (on class labels) VAE to generate old data for replay, and NodeAE that directly maps node attributes. The two modules share a shared graph decode.\n\nThey main contribution is highlighting the more realistic learning setting and proposing a model that tackles the challenges that come with it.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "None.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "2Wzq4F99yz", "reviewer": "Reviewer_pB6o", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper proposes a novel setting, with a reasonable model to tackle this new setting.\n\n\nWeaknesses\n\n1. The proposed setting assumes that the streaming testing nodes are typically isolated from the previously observed training graph, which is seemingly reasonable, but lacks real-world correspondence. For example, the citation networks used in this paper (cora and citeseer), when new papers appear, why couldn't they be connected to existing papers with citation relationship? It seems that inserting the new paper into the existing citation network does not incur much computational cost, since the citation information are already included in the paper's data (e.g. biblography). Therefore, it is necessary to justify that the so called 'overlooked problem' is indeed practically important.\n\n2. The baselines are a bit old. Actually there is only one method designed for continual learning on graphs included in this paper (ER-GNN). This paper is a branch of to continual learning on graph data, which has multiple publications in 2022 and 2023. The authors are encouraged to compare or discuss the recent literature.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper focus on a scenario, in which the testing nodes are accompanied with very sparse edge connections, which is inconsistent with the training phase with full neighborhood information. \n\nBesides the novel setting, the proposed method contains one graph encoder, one node encoder, one classifier, and one graph decoder. The encoder encode the node and structure information into laten space. The decoders serve to guide the model to encode the node information in the latent representations, and provides structural information during testing, when the graph structure is sparse.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Justification of the practical importance of the proposed setting.\n\n2. More thorough discussion on the related works.", "broader_impact_concerns": "The studied problem should not have significant ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "gQQf2zbGwS", "reviewer": "Reviewer_Cw9c", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n- Interesting problem. It is critical to study the graph continual learning without accessing the past data at the inference stage.\n\n## Weaknesses\n\n- The paper should be better polished with improved clarity.\n\n- The experiment is not extensive. Not only some reasonable baselines are not compared, but also the used graph datasets are rather simple. \n\nWhile I like the problem that the authors study, I think several weaknesses can be improved for the current manuscript. First, the paper should be better polished with improved clarity. For instance, the problem formulation is not clear to me, especially the description after performing $T^m$ tasks. Do the authors mean there are test nodes from each $D^t$ and they want to predict their label at inference? \n\nRegarding the experiment, while the authors demonstrate some positive results compared to the tested baselines, it is only for rather simple graph datasets such as Cora. I wonder if this is common for graph continual learning and if more (challenging) benchmark datasets can be used. Also, according to the current setting, I feel it is natural to compare with the distillation-based methods (i.e., MLP distill from GNNs) [1,2]. Is there any reason why this type of method is not included as baselines? I think it is critical to compare these approaches in order to verify that constructing a \"graph\" for test nodes and then applying GNNs is reasonable (i.e., the proposed ReplayGNN). Based on the current experiment, it is hard for me to advocate for this work.\n\n##References:\n\n[1] Graph-less neural networks: Teaching old mlps new tricks via distillation, Zhang et al. ICLR 2022.\n\n[2] Learning MLPs on Graphs: A Unified View of Effectiveness, Robustness, and Efficiency, Tian et al. ICLR 2023.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors study the graph continual learning problem, where they identify the problem that prior works assume the past graph data is available at inference. The authors propose ReplayGNN as a solution for this challenge.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Compare with distillation-based methods [1,2]. If they are not applicable, please explain the reason in detail.\n\n- Test with more benchmark datasets, such as those in Open Graph Benchmark or datasets that can be found in the PyTorch geometric library. If they are not applicable, please explain the reason.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper addresses a significant issue in the domain of class-incremental graph learning (CGL), where historical data may not be available during both training and inference due to constraints like storage or privacy regulations. This absence of historical data poses unique challenges, unlike in continual image classification where past data's unavailability affects only the training phase but not inference. The authors introduce ReplayGNN (ReGNN), a model designed to tackle catastrophic forgetting and the scarcity of neighbor information during inference without relying on memory buffers. The reviewers were leaning positive on the submission and appreciated the identification of previously unexplored setting. However, there were some concerns about experiment design and comparison with baselines. Post-rebuttal many of these were addressed by the additional experimental results, although some reviewers felt more comparisons might still be beneficial.
Decision: Accept (poster)