Replay-and-Forget-Free Graph Class-Incremental Learning: A Task Profiling and Prompting Approach

Authors: chaoxi  niu
guansong  pang
ling  chen
bing  liu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 06:54:45

Abstract: Class-incremental learning (CIL) aims to continually learn a sequence of tasks, with each task consisting of a set of unique classes. Graph CIL (GCIL) follows the same setting but needs to deal with graph tasks (e.g., node classification in a graph). The key characteristic of CIL lies in the absence of task identifiers (IDs) during inference, which causes a significant challenge in separating classes from different tasks (i.e., inter-task class separation). Being able to accurately predict the task IDs can help address this issue, but it is a challenging problem. In this paper, we show theoretically that accurate task ID prediction on graph data can be achieved by a Laplacian smoothing-based graph task profiling approach, in which each graph task is modeled by a task prototype based on Laplacian smoothing over the graph. It guarantees that the task prototypes of the same graph task are nearly the same with a large smoothing step, while those of different tasks are distinct due to differences in graph structure and node attributes. Further, to avoid the catastrophic forgetting of the knowledge learned in previous graph tasks, we propose a novel graph prompting approach for GCIL which learns a small discriminative graph prompt for each task, essentially resulting in a separate classification model for each task. The prompt learning requires the training of a single graph neural network (GNN) only once on the first task, and no data replay is required thereafter, thereby obtaining a GCIL model being both replay-free and forget-free. Extensive experiments on four GCIL benchmarks show that i) our task prototype-based method can achieve 100% task ID prediction accuracy on all four datasets, ii) our GCIL model significantly outperforms state-of-the-art competing methods by at least 18% in average CIL accuracy, and iii) our model is fully free of forgetting on the four datasets.

Main paper: 
 introduction: 
 Graph continual learning (GCL) [5, 28, 39, 43] aims to continually learn a model that not only accommodates the new emerging graph data but also maintains the learned knowledge of previous graph tasks, with each graph task comprising nodes from a set of unique classes in a graph. Due to privacy concerns and the hardware limitations in storage and computation, GCL assumes that the data of previous graph tasks is not accessible when learning new graph tasks. This leads to catastrophic forgetting of the learned knowledge, i.e., degraded classification accuracy on previous tasks due to model updating on new tasks. (a) Classification space of two graph tasks when no task ID is provided. The classification space is split into two separate spaces in Task 1 in (b) and Task 2 in (c) when the task ID can be accurately predicted. This helps alleviate the inter-task class separation issue. To mitigate catastrophic forgetting, we learn a graph prompt for each task that absorbs task-specific discriminative information for better class separation within each task, as shown in (d) and (e) respectively. This essentially results in a separate classification model for each task, achieving fully forget-free GCIL models.Graph class-incremental learning (GCIL) is one key setting of GCL, in which task identifiers (IDs) are not provided during inference. Graph task-incremental learning (GTIL) is another GCL setting where the task ID is given for each test sample. As a result, a set of separate classifiers can be learned for different graph tasks in GTIL and the task-specific classifier can be used for each test sample. Compared to GTIL, the absence of task IDs in GCIL presents an additional challenge, known as inter-task class separation [10, 11, 14] , i.e., the class separation in one graph task is obstructed by the presence of classes from other tasks. Consequently, the classification performance in GCIL is typically far below that in GTIL [15, 17, 20, 41, 42, 44] . This paper focuses on the GCIL setting -a more compelling GCL problem -aiming to bridge the performance gap between GCIL and GTIL.Existing GCL methods often alleviate the catastrophic forgetting through preserving important model parameters of previous tasks [15] , continually expanding model parameters for new tasks [37, 40] , or augmenting with a memory module for data replay [17, 20, 20, 41, 42, 44] . However, their ability to handle the inter-task class separation is limited, leading to poor GCIL classification accuracy, especially the accuracy of the previous graph tasks. Thus, existing GCL methods typically show substantially higher forgetting in GCIL than in GTIL.To address these issues, we introduce a novel GCIL approach, namely Task Profiling and Prompting (TPP). In particular, we reveal for the first time theoretically and empirically that the task ID of a test sample can be accurately predicted by using a Laplacian smoothing-based method to profile each graph task with a prototypical embedding. With the existence of edges between nodes, this task profiling method guarantees that the task prototypes of the same graph task are nearly the same with a large smoothing step, while those of different tasks are distinct due to differences in graph structure and node attributes. High task ID prediction accuracy helps confine the classification space of the test samples to the classes of the predicted task (e.g., Task 1 or 2 in Fig. 1b, c ) instead of all the learned tasks (e.g., both tasks as in Fig. 1a ), eliminating the inter-task class separation issue. There have been some studies on task ID prediction [10, 11, 14] , but they are designed for Euclidean data that are i.i.d. (independent and identically distributed). As a result, they fail to leverage the graph structure and node attributes in the non-Euclidean graph data and are not suited for graph task ID prediction.To address the catastrophic forgetting problem, we further propose a novel graph prompting approach for GCIL. Specifically, we optimize a single, small learnable prompt using a simple frozen pre-trained graph neural network (GNN) to capture the task-specific knowledge for each graph task during training. Despite being small, the task-specific knowledge learned in the prompts can ensure the intra-task class separation, as shown in Fig. 1d, e . At test time, given a test graph, the task prototype constructed with its structure and node attributes is utilized for task ID prediction, and the graph prompt of the predicted task is incorporated into the test graph for classification with the GNN. Since the graph prompts are learned task by task, no data replay is required in our TPP model. Further, the graph prompts are task-specific, so we essentially have a separate classification model for each graph task, i.e., no continual model updating, completely avoiding the forgetting problem (i.e., forget-free).Overall, this work makes the following main contributions. (1) : We propose a novel graph task profiling and prompting (TPP) approach, which is the first replay-and forget-free GCIL approach.(2): We reveal theoretically that a simple Laplacian smoothing-based graph task profiling approach can achieve accurate graph task ID prediction. To the best of our knowledge, it is the first work that leverages the non-Euclidean properties of graph data to enable graph task ID prediction. It achieves 100% prediction accuracy across all four datasets used, eliminating the inter-task class separation issue in GCIL. (3): We further introduce a novel graph prompting approach that learns a small prompt for each task using a frozen pre-trained GNN, without any data replay involved. With the support of our accurate task ID prediction, the graph prompts result in a separate classification model for each task, resulting in the very first GCIL model being both replay-free and forget-free. (4): Extensive experiments on four GCIL benchmarks show that our TPP model significantly outperforms state-ofthe-art competing methods by at least 18% in average CIL accuracy while being fully forget-free. It even exceeds the joint training on all tasks simultaneously by a large margin. 
related work: 
 Graph Continual Learning. Various methods have been proposed for GCL [7, 15, 21, 22, 24, 25, 31, 37, 38, 41, 42, 44] and can be divided into three categories, i.e., regularization-based, parameter isolationbased, and data replay-based methods. Regularization-based methods typically preserve parameters that are important to the previous tasks when learning new tasks via additional regularization terms. For example, TWP [15] preserves the important parameters in the topological aggregation and loss minimization for previous tasks via regularization terms. Parameter isolation-based methods maintain the performance on previous tasks by continually introducing new parameters for new tasks such as [37] proposes to continually expand model parameters to learn new emerging graph patterns. Differently, replay-based methods [17, 20, 41, 42, 44] employ an additional memory buffer to store the information of previous tasks and replay them when learning new tasks. The ways to construct the memory buffer play a vital role in replay-based methods. Despite they have shown good performance in alleviating the forgetting problem, inter-class separation is still a significant challenge to these methods, especially for the CIL setting where the task IDs are not provided when testing.To improve the CIL performance, an emerging research direction focuses on performing task ID prediction during testing. For example, CCG [1] utilizes a separate network for task identification. HyperNet [30] and PR-Ent [8] use the entropy to predict the task of the test sample. More recently, [10] proves that OOD detection is the key to task ID prediction and proposed an identification method based on an OOD detector. TPL [14] further improves it by exploiting the information available in CIL for better task identification. Since these methods were designed for Euclidean data, they are not suited for GCIL. Following this line, we propose a task ID prediction method specifically for GCIL in this paper. Different from previous methods that rely on additional networks or OOD detectors, the proposed task identification is accomplished by using a Laplacian smoothing-based method to profile each graph task with a prototypical embedding. Despite its simplicity, this graph task profiling method can achieve accurate task ID prediction with theoretical support.Prompt Learning. Originating from natural language processing, prompt learning aims to facilitate the adaptation of frozen large-scale pre-trained models to various downstream tasks by introducing learnable prompts [16] . In other words, prompt learning designs task-specific prompts to instruct the pre-trained models to perform downstream tasks conditionally. The prompts capture the knowledge of the corresponding tasks and enhance the compatibility between inputs and pre-trained models. Recently, prompt-based graph learning methods have also been proposed [27] , which aims to unify multiple graph tasks [26] or improve the transferability of graph models [4] . Due to the ability to leverage the strong representative capacity of the pre-trained model and learn the knowledge of tasks in prompts, many prompting-based continual learning methods have been proposed [32] [33] [34] and achieved remarkable success without employing replaying memory or regularization terms. Despite that, no work is done on prompt learning for GCIL. The main challenge is the lack of pre-trained GNN models for all tasks in GCIL and the absence of task IDs to retrieve corresponding prompts during testing. In this work, we show that effective graph prompts can be learned for different tasks using a GNN backbone trained based on the first task with graph contrastive learning [36, 45] , and our task ID prediction method and the graph prompts can be synthesized to address the GCIL problem. 
the gcil problem: 
 Formally, GCL can be formulated as learning a model on a sequence of connected graphs (tasks) {G 1 , . . . , G T } where T is the number of tasks. Each G t = (A t , X t ) is a newly emerging graph, During training, for each graph task t, the task prototype p t is generated by applying Laplacian smoothing on the graph G t and added to P = {p 1 , . . . , p t-1 }. At the same time, the graph prompt Φ t and the classification head φ t for this task are optimized on G t through a frozen pre-trained GNN. During inference, the task ID of the test graph is first inferred (i.e., task identification). Then, the graph prompt and the classifier of the predicted task are retrieved to perform the node classification in GCIL. The GNN is trained on G 1 and remains frozen for subsequent tasks.where A t denotes the relations between N nodes of the current/new task, X t ∈ R N ×F represents the node attributes with dimensionality of F , and the labels of nodes can be denoted as Y t . Each task contains a unique set of classes in a graph, i.e., {Y t ∩ Y j = ∅|t ̸ = j}. When learning task t, the model trained from previous tasks only has access to the current task data G t . The goal is to accommodate the model to current graph G t while maintaining the classification performance on the previous graphs {G 1 , . . . , G t-1 }. In GCIL, the task IDs are not available during inference. Thus, assuming that each task has C classes, after learning all tasks, a GCIL model is required to classify a test instance into one of all the T × C classes.Inspired by prior studies [10, 11] , we decompose the class probability of a test sample x test belonging to the j-th class in task t in GCIL into two parts :EQUATIONwhere H(t|x test ) represents the task ID prediction probability of task t and H(y t j |x test , t) denotes the prediction within the task t. This indicates that accurate GCIL classification accuracy can be achieved when both accurate task ID prediction and intra-task class classification are achieved.To this end, in this paper, we propose the Task Profiling and Prompting (TPP) approach for GCIL. As shown in Fig. 2 , a novel Laplacian smoothing-based task profiling approach is first devised in TPP for graph task ID prediction, which can well guarantee the task prediction accuracy as we will demonstrate theoretically below. Moreover, to obtain accurate intra-task class classification within the identified task, a novel graph prompting approach is further proposed to learn a small prompt for each task using a frozen GNN pre-trained on the first graph task. By learning and storing task knowledge separately, there is no knowledge interference between tasks during training, resulting in a model being both replay-free and forget-free. During inference, given a test sample, TPP first performs the task ID prediction and then retrieves the corresponding task graph prompt to concatenate with the sample for the GCIL classification. Below we introduce the TPP approach in detail.To leverage the graph structure and node attribute information, we propose to use a Laplacian smoothing approach to generate a prototypical embedding for each graph task for task ID prediction. Specifically, for the task t with graph data G t = (A t , X t ), we construct a task prototype p t for this task based on the train set denoted as {x i |i ∈ V t train }, where V t train is the train set of G t . Given G t , the Laplacian smoothing is first applied on the graph G t to obtain the smoothed node embeddings Z t :EQUATIONwhere s denotes the number of Laplacian smoothing steps, I is an identity matrix, and Lt is the graph Laplacian [3] matrix of Ât = A t + I (i.e., Lt = Dt -Ât with Dt being the diagonal degree matrix of Ât and Dt ii = j âij ). Then, the task prototype p t is constructed by averaging the smoothed embeddings of train nodes:EQUATIONSimilarly, the task prototypes for all tasks can be separately constructed and stored, denoted as P = {p 1 , . . . , p T }. Given a test graph G test at testing time, we predict the task ID of G test by querying the task prototype pool P. Specifically, the task prototype of G test is obtained with the set of test nodes in a similar way as on training graphs via Eq. ( 2) and Eq. (3), i.e.,EQUATIONwhere V test denotes the set of nodes to be classified in G test and z test i is the smoothed embedding of the test node i after s-step Laplacian smoothing. Then, we query the task prototype pool P with the test prototype p test and return the task ID whose task prototype is most similar to p test :EQUATIONwhere d( EQUATIONTheorem 2. Suppose the test graph comes from task t, and let e and ϵ be the differences in node degrees and node attributes between two different tasks t and j respectively, which are defined by ( Dj )1 2 = ( Dt ) 1 2+ Diag(e) and X j = X t + ϵ. Then the distance between the task prototypes of task t and j obtained with large steps of Laplacian smoothing can be explicitly calculated as:EQUATIONwhere e t N = ( Dt ) Without loss of generality, we empirically investigate the differences between two randomly chosen graph tasks of the CorFull dataset in Fig. 3 . We can see that the two graphs of the tasks have a rather large difference in both graph structure and node attributes. The larger the differences in e and ϵ of the two graphs, the larger the gap is between d(p test , p t ) and d(p test , p j ). As a result, the task of the test graph can be predicted accurately with Eq. ( 5). In the experimental section, we empirically evaluate the proposed task ID prediction and report its accuracy on different datasets.Instead of utilizing regularization or replaying memory as in existing GCL methods, TPP aims to learn a task-specific prompt for each graph task. The information of each graph task can be explicitly modeled and stored in a separate task-specific graph prompt, with the GNN backbone being frozen. This effectively avoids the forgetting of knowledge of any previous tasks and the interference between tasks. To this end, the graph prompt in TPP is designed as a set of learnable tokens that can be incorporated into the feature space of the graph data for each task. Specifically, for a task t, the graph prompt can be represented asΦ t = [ϕ t 1 , . . . , ϕ t k ] T ∈ R k×Fwhere k is the number of vector-based tokens ϕ i . For each node in G t , the node attribute is augmented by the weighted combination of these tokens, with the weights obtained from k learnable linear projections:EQUATIONwhere α j denotes the importance score of the token ϕ j in the prompt and w j is a learnable projection.For convenience, we denote the graph modified by the graph prompt as Ḡt = (A t , X t + Φ t ). Then, Ḡt is fed into a frozen pre-trained GNN model f (•) to obtain the embeddings for classification. In TPP, we employ a single-layer MLP as the classifier attached to the GNN, denoting φ t for task t. The node classification at task t can be formulated as:EQUATIONTherefore, the graph prompt and the MLP-based classification head are optimized by minimizing a node classification loss: minEQUATIONwhere V t train is the train set of G t , y t i is the label of node i, ŷt i ∈ Ŷ t is the predicted label, and ℓ CE(•) is a cross-entropy loss. By minimizing Eq. ( 9), the graph prompt and the classifier are learned to leverage the generic, cross-task knowledge in the frozen GNN f (•) for the task t. Meanwhile, Φ t and φ t learn specific knowledge for the task t. This essentially results in a separate classification model for each task, and no data replay is required for all tasks. As a result, TPP is fully free of catastrophic forgetting for GCIL. An alternative approach to overcoming the forgetting is to learn a separate GNN model for each task. However, this would introduce heavy burdens on optimization and storage with the increasing number of tasks. By contrast, the proposed graph prompting only introduces minimal parameters for each task as the prompts are very small.Training. The training of TPP can be divided into two parts. First, for each task G t , the prototypical embedding p t is generated based on Laplacian smoothing and stored in P for task ID prediction. Then, the information of G t is explicitly modeled and stored with the proposed graph prompt learning, i.e., Eq. (11) . For the GNN backbone f (•) in graph prompt learning, we propose to learn it based on the first task G 1 = (A 1 , X 1 ) via graph contrastive learning due to its ability to obtain transferable models [36, 45] across graphs (see Appendix B). Despite being only learned on G 1 , f (•) can effectively adapt to all subsequent tasks with graph prompts. Overall, after learning all tasks in {G 1 , . . . , G T }, the task profiles and task-specific information are explicitly modeled in P = {p 1 , . . . , p T }, {Φ 1 , . . . , Φ T } and {φ 1 , . . . , φ T }.Inference. Given the test graph G test , the task prototype p test is constructed with Eq. ( 4) and then used to obtain the task ID t test by querying P = {p 1 , . . . , p T }, i.e., via Eq. ( 5). Finally, the test graph G test is augmented with the corresponding graph prompt Φ t test and fed into the GNN and the classification head constructed with f (•) and φ t test respectively to get the node classification results. Formally, the inference can be formulated as:EQUATION)The algorithms of the training and inference of TPP are provided in Appendix C.  
experiments: 
 Datasets. Following the GCL performance benchmark [39] , four large public graph datasets are employed, including CoraFull [19] , Arxiv [9] , Reddit [6] and Products [9] . Specifically, CoraFull and Arxiv are citation networks, Reddit is constructed from Reddit posts, and Products is a co-purchasing network from Amazon. For all datasets, each task is set to contain only two classes [39] . Besides, for each class, the proportions of training, validation, and testing are set to be 0.6, 0.2, and 0.2 respectively.Competing Methods. Two categories of state-of-the-art (SOTA) continual learning methods are employed for comparison: (1) general CIL methods: EWC [12] , LwF [13] , GEM [18] and MAS [2] ;(2) graph CIL methods: ERGNN [44] , TWP [15] , SSM [41] , SEM [42] , CaT [17] and DeLoMe [20] .There are limited methods on task ID prediction for CIL, e.g., [10, 14] , but they are not suited for graph data. To compare with this type of methods, we adapt the OOD detection-based CIL methods [10, 14] for GCIL (named OODCIL) (Details are in Appendix D.2). In addition, we include two baseline methods: Fine-Tune and Joint. The Fine-Tune method is a baseline that simply fine-tunes the learned model from previous tasks without continual learning techniques, while the Joint method is an oracle model that can see all graphs at all times and performs GCL on the full graphs of all tasks. We also report the results of an enhanced Oracle Model that is an enhanced version of the Joint method with access to the task ID of every test sample during inference.Implementation Details. The proposed method is implemented under the GCL library [39] . TPP adopts a two-layer SGC [35] as the GNN backbone model with the same hyper-parameters as [42] . For task prototype construction, the number of steps s in Laplacian smoothing is set to 3 by default.The number of tokens in each graph prompt, k, is also set to 3 across the four datasets. For each dataset, we report the average performance with standard deviations after 5 independent runs with different random seeds.Evaluation Metrics. To evaluate the performance of continual learning methods, two commonly used metrics, average accuracy (AA) and average forgetting (AF) after all tasks have been learned, are adopted in our experiments. A larger AA/AF indicates better performance. An AF value of zero indicates a perfect performance involving no knowledge forgetting (i.e., forget-free). The detailed definitions of AA and AF are given in Appendix D.5.Comparison to SOTA Methods. The results of TPP and its competing methods under the GCIL setting are shown in Table 1 . From the table, we can draw the following key observations. (1) As demonstrated by the results of Fine-Tune, directly fine-tuning the learned model from previous tasks on the current task data leads to serious performance degradation because the knowledge of previous tasks could be easily overwritten by the new tasks. (2) CIL methods proposed for Euclidean data generally do not achieve satisfactory performance for GCIL, which verifies the fact that the unique graph properties should be taken into consideration for GCIL. (3) Replay-based methods generally achieve much better performance than the other baselines, showing the effectiveness of using an external memory buffer to overcome catastrophic forgetting. However, all of them still suffer from forgetting, in addition to the inter-task separation issue. ( 4) The performance of OODCIL demonstrates that despite achieving impressive AF performance, current OOD detection-based CIL methods are not effective for GCIL due to the overlook of graph properties in its OOD detector and classification model. ( 5) Different from the baselines that involve the forgetting problem to varying extents, the proposed method TPP is a fully forget-free GCIL approach, achieving an AF value of zero across all four datasets. TPP is also consistently the best performer in AA, outperforming the best-competing method by over 18% in AA averaged over the four datasets. This superiority is attributed to the highly accurate task ID prediction module in TPP and its effective task-specific graph prompt learning (see Sec. 4.2). ( 6) Our method lifts the SOTA AA performance by a large margin and even significantly outperforms the oracle baseline Joint in all cases. This is because although the Joint method can mitigate catastrophic forgetting due to its access to the data of all graphs, it is still challenged by the inter-task class separation issue since it is not given task ID during inference. TPP effectively tackles both catastrophic forgetting and inter-task class separation issues, thus achieving significantly better AA than Joint and very comparable AA to the Oracle Model.Enabling Existing GCIL Methods with Our Task ID Prediction Module. Existing GCIL Methods often suffer from a severe inter-task class separation issue. Our task ID prediction is devised as a module to tackle this issue. To show its effectiveness as an individual plug-and-play module, we evaluate its performance when combined with existing GCIL methods. Our task ID prediction method does not change the training process of existing GCIL models. It is directly incorporated into them at the inference stage only, i.e., our task ID predictor produces a task ID for each test sample and the existing GCIL models then perform intra-task classification in the predicted task. Without loss of generality, a parameter regularization-based method (TWP [15] ) and a memory-replay method (DeLoMe [20] ) are used as exemplars for this experiment. The results are shown in Table 2 . We can see that both AA and AF performance of the two existing GCIL models are largely enhanced by the proposed task identification module. For relatively weak GCIL models like TWP, the improvement is much more substantial than the strong ones like DeLoMe. The reason is that being able to predict the task ID accurately enables the subsequent CIL classification within the original task space of the test graph, not the space containing all the learned classes, significantly simplifying (reducing) the classification space. Essentially, such a task ID prediction converts the GCIL task into the GTIL task, so that much better AA and AF results are expected.Importance of Task ID Prediction. In GCIL, the test samples are required to be classified into one of all the learned classes. To evaluate the importance of task ID prediction that helps confine the classification space of the test samples to the classes of the predicted task, we conduct the experiments of TPP without the proposed task profiling approach and report the results in Table 3 . Specifically, we obtain the class probabilities of the test sample for all tasks and prompts, and the class with the highest probability is treated as the class for the test sample. As shown in the table, this TPP variant can barely work on all four datasets. This is mainly due to that the graph prompts are learned task by task during training. Without the guidance of task identification, the non-normalized within-task prediction probabilities obtained with corresponding prompts pose great challenges for classifying the test samples into the correct classes.Importance of Graph Prompting. Besides the task ID prediction, we also evaluate the importance of graph prompting. There are two modules for each task in the proposed graph promoting, i.e., graph prompt Φ t and classification head φ t . The results with and without each module are shown in 3 . We can see that the TPP variant without both Φ t and φ t , which is equivalent to the direct use of the GNN backbone learned only from the first task for all subsequent tasks, achieves the worst AA performance, though it is free of forgetting since there is no model updating. By incorporating either Φ t or φ t , the performance can be largely improved, which can be attributed to the transferable knowledge in the pre-trained GNN f and the effective adaptation of the prompts or the classifier to the subsequent tasks. Note that the variant with only Φ t obtains much better performance than that with only φ t , demonstrating that the learned graph prompts can more effectively model the task-specific information and bridge the gap between the first task and subsequent tasks. The results also explain the visualization of node embeddings with and without the graph prompt in Fig. 1 , where the graph prompt can largely enhance the intra-task separation. By integrating all the components, the full TPP model achieves the best performance across all datasets.Sensitivity w.r.t the Size of Graph Prompts. We evaluate the sensitivity of the proposed method w.r.t the size of the graph prompt, i.e., the number of tokens per prompt. We vary k in the range of [1, 6] to verify the sensitivity and report the results in Fig. 4(a) . It is clear that the performance of TPP increases quickly from k = 1 to k = 2 and remains stable when k > 2, demonstrating that TPP can be effectively adapted to different tasks with a small size of prompt for each task. This also demonstrates the transferability of the learned GNN backbone for all tasks. Accuracy of Task ID Prediction. We further evaluate the accuracy of the proposed task ID prediction method. We compare it to a variant of our method that constructs the task prototype based on the node attributes without considering the graph structure. In this variant, each task prototype is constructed by simply averaging the attributes of training nodes of each task. The task prototype of a test graph is constructed with the test nodes in the same way. The inference process remains the same as the proposed method. The results of these two methods are shown in Fig. 4(b) . We see that the task identification sorely based on node attributes achieves high accuracy for all datasets and even predicts all of the tasks correctly for Arxiv and Reddit. This is largely attributed to the discriminative node attributes between tasks in these datasets, as demonstrated in Fig. 3 . However, it fails to discriminate tasks with similar node attributes. By contrast, the proposed method based on Laplacian smoothing can handle all the cases, resulting in perfect task ID prediction for all tasks and datasets, which builds a strong foundation for superior GCIL performance of TPP.EQUATIONPerformance of TPP with different task formulations. For the task formulation, we set each task to contain two different classes of nodes and follow the commonly used task formulation strategy in [20, 39] to have fair comparisons with the baselines. Specifically, given a graph dataset with several classes, we split these classes into different tasks in numerically ascending order of the original classes, i.e., classes 0 and 1 form the first task, classes 2 and 3 form the second task, and so on.To evaluate the performance of TPP with different task formulations, we further perform the class splitting in two other manners, including numerically descending and random ordering of the two classes per task. In Table 4 , we report the average performance of the TPP and the Oracle Model with different task formulations. From the table, we observe that the proposed TPP method can still achieve comparable performance to the Oracle Model with different task formulations, highlighting the robustness and effectiveness of TPP w.r.t. the formulation of individual tasks. Note that the performances of TPP and the Oracle Model both drop on Products with random task formulation. This is attributed to the heavily imbalanced class distribution of Products and the performance is evaluated by the balanced classification accuracy. Specifically, for Products, some classes contain hundreds of thousands of nodes while the number of nodes in some classes is less than 100. The ascending and descending task formulations have a relatively balanced class distribution for each task. However, the random task formulation results in some tasks with heavily imbalanced class distribution. To address this problem, debiased learning is required and we leave it for future research. Please also note that TPP learns the GNN backbone only on the first task and is frozen during the subsequent prompt learning. Different task formulations result in the GNN backbone being learned with different first tasks. The above results also reveal that the proposed graph prompting enables the learned GNN backbone to effectively adapt to all subsequent tasks despite the backbone being learned on different initial tasks. 
conclusion: 
 This paper proposes a novel approach for GCIL via task profiling and prompting. The absence of task IDs during inference poses significant challenges for GCIL. To address this issue, this paper proposes a novel Laplacian smoothing-based graph task profiling approach for GCIL, where each task is modeled by a task prototype based on Laplacian smoothing over the graph. We prove theoretically that the task prototypes of the same graph task are nearly the same with a large smoothing step and the prototypes of different tasks are distinct due to the differences in graph structure and node attributes, ensuring accurate task ID prediction for GCIL. To avoid catastrophic forgetting and achieve high within-task prediction, we further propose the first graph prompting method for GCIL which is learned to absorb the within-task information into the small task-specific graph prompts. This results in a memory-efficient TPP as i) no memory buffer is required for data replay due to its replay-free characteristic and ii) the graph prompting only requires the training of a single GNN once and a small number of tokens per prompt for each task. Extensive experiments show that TPP is fully forget-free and significantly outperforms the state-of-the-art baselines for GCIL. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: In the experiment section, we report the average performance of each method with standard deviations after 5 runs with different seeds. Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: Computer resources are provided in the appendix. Besides, the time complexity of the proposed method is provided in the Appendix .E Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: The broader impacts of this work are discussed in the Appendix G.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: The datasets and benchmarks used are all publicly available with licensees and are properly acknowledged in our paper.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: Theorem 1. If graphs for all tasks are not isolated and the test graph G test comes from the task t, i.e., G test and G t have the same set of classes, then the distance between p test and p t approaches to zero with a sufficiently large number of Laplacian smoothing steps s:EQUATIONProof. To prove the distance between p test and p t approaches 0 with a large Laplacian smoothing step s, we need to illustrate that the features of nodes in G t coverage to be proportional to the square root of the node degree after Laplacian smoothing and the proposed task prototype construction method transforms all node features to the same values. Note that the self-loop is added to each node in the graph, resulting in the graph being non-bipartile. Assuming the size of the graph G t is N , the Laplacian matrix ( Dt ) -1 2 Lt ( Dt ) -1 2 has N eigenvalues with different eigenvectors [29] . Recalling the Laplacian smoothing defined in Eq. ( 2), the eigenvalues and eigenvectors of I -( Dt ) -1 2 Lt ( Dt ) -1 2 can be represented as (λ 1 , . . . , λ N ) and (e 1 , . . . , e N ) respectively. With the property of symmetric Laplacian matrix for the non-bipartile graph, the eigenvalues of I -( Dt ) -1 2 Lt ( Dt ) -1 2 are all in the range of (-1, 1] [3], i.e.,EQUATION)Based on the eigenvalues and the eigenvectors, the result of applying Laplacian smoothing on the node features X t after s steps can be formulated as:EQUATIONwhere Xt = [e 1 , . . . , e N ] -1 X t . As the eigenvectors are orthogonal to each other, we can further rewrite Xt as Xt = [e 1 , . . . , e N ] T X t . Since the absolute values of the eigenvalues are less than 1 except λ N , λ s i would approach 0 as s go infinity, i.e., lim s→∞ λ s i = 0, ∀i ̸ = N . Then, we can formulate the smoothed node feature representations Z t as follows:EQUATIONwhere Xt [N, :] denotes the N -th row of Xt . Therefore, with a larger s, the feature of nodes in G t would converge to be proportional to the square root of the node degree. By multiplying the smoothed feature with ( Dt ii ) -1 2 for each node i in the proposed task prototype construction, p test and p t would both become to be Xt [N, :], despite that they utilize different nodes to construct the task prototypes. Therefore, the distance between p test and p t would become zero with a large s.Note that we assume that the graphs of all tasks are not isolated in Theorem 1. Having isolated nodes in real-world graphs would deviate from this assumption, resulting in unsatisfied task identification. To tackle this issue, we propose a simple graph augmentation when constructing the task prototypes, which adds an edge between the isolated nodes and the randomly chosen non-isolated nodes to make the graph more connected. This helps the proposed task ID prediction method predict the task of test graphs more accurately. Theorem 2. Suppose the test graph comes from task t, and let e and ϵ be the differences in node degrees and node attributes between two different tasks t and j respectively, which are defined by ( Dj )1 2 = ( Dt ) 1 2+ Diag(e) and X j = X t + ϵ. Then the distance between the task prototypes of task t and j obtained with large steps of Laplacian smoothing can be explicitly calculated as:EQUATIONwhere e t N = ( Dt )1 2 [1, 1, . . . , 1]T is the N -th eigenvector of task t and (e t N ) T denotes its transpose.Proof. As derived in Theorem 1, the task prototypes of task t and j with large steps of Laplacian smoothing are p test = Xt [N, :] and p j = Xj [N, :] respectively. Furthermore, the task prototype of task t can be represented as p t = (e t N ) T X t . Based on the difference in node degrees and node attributes between task t and j, the distance between the task prototypes can be represented as follows:EQUATIONWe propose to construct a GNN backbone f (•) for graph prompt learning so that the task-specific information can be absorbed into the prompts. Specifically, the model f (•) is constructed based on the first task G 1 = (A 1 , X 1 ) via graph contrastive learning due to its ability to obtain transferable models [36, 45] across graphs.To construct contrastive views for graph contrastive learning, two widely used graph augmentations are employed, i.e., edge removal and attribute masking [45] . Specifically, the edge removal randomly drops a certain portion of existing edges in G 1 and the attribute masking randomly masks a fraction of dimensions with zeros in node attributes, i.e.,EQUATIONwhere R ∈ {0, 1} N ×N is the edge masking matrix whose entry is drawn from a Bernoulli distribution controlled by the edge removal probability, m ∈ {0, 1} F is the attribute masking vector whose entry is independently drawn from a Bernoulli distribution with the attribute masking ratio, and • denotes the Hadamard product. By applying the graph augmentations to the original graph, the corrupted graph G1 = ( Ã1 , X1 ) forms the contrastive view for the original graph G 1 = (A 1 , X 1 ). Then, G1 and G 1 are inputted to the shared GNN f (•) followed by non-linear projection g(•) to obtain the corresponding node embeddings, i.e., Z1 = g(f ( G1 )) and Z 1 = g(f (G 1 )). For graph contrastive learning, the embeddings of the same node in different views are pulled closer while the embeddings of other nodes are pushed apart. The pairwise objective for each node pair (z 1 i , z 1 i ) can be formulated as:EQUATIONwhere sim(•) represents the cosine similarity and τ is a temperature hyperparameter. Therefore, the overall objective can be defined as follows:EQUATION)With the objective Eq. ( 22), the model f (•) is optimized to learn discriminative representations of nodes. Despite the limited size of the first task, the learned model f (•) can effectively adapt to other tasks with the proposed graph prompt learning method.The training and inference processes of the proposed method are summarized in Algorithm 1 and Algorithm 2, respectively.All the continual learning methods including the proposed method are implemented based on the GCL benchmark [39] 2 . For the memory-replay methods, we follow the settings in [20] . As in [42] ,Algorithm 1: Training of TPP 1: Input: A series of graph learning tasks: {G 1 , . . . , G T }, a graph neural network f (•). 2: Output: Graph neural network f (•), task prototype P = {p 1 , . . . , p T }, graph prompts {Φ 1 , . . . , Φ T }, and classifiers {φ 1 , . . . , φ T }. 3: Pre-train f (•) on G 1 with graph contrastive learning (Eq. ( 22)). 4: for t = 1, . . . , T do 5:Obtain the task prototype p t of task t (Eq. ( 3)).Obtain Ḡt with graph prompts Φ t (Eq. ( 9)). 7:Optimize Φ t and φ t by minimizing node classification loss (Eq. ( 11)). 8: end for Algorithm 2: Inference in TPP ) (Eq. ( 9)). 7:return φ t test (f (A test , X test + Φ t test ))we employ a two-layer SGC [35] model as the backbone. Specifically, the hidden dimension is set to 256 for all methods. The number of training epochs of each graph learning task is 200 with Adam as the optimizer and the learning rate is set to 0.005 by default.For graph contrastive learning, the probabilities of edge removal and attribute masking are set to 0.2 and 0.3 respectively for all datasets. Besides, the learning rate is set to 0.001 with Adam optimizer, the training epochs are set to 200 and the temperature τ is 0.5 for all datasets.The code is implemented with Pytorch (version: 1.10.0), DGL (version: 0.9.1), OGB (version: 1.3.6), and Python 3.8.5. Besides, all experiments are conducted on a Linux server with an Intel CPU (Intel Xeon E-2288G 3.7GHz) and a Nvidia GPU (Quadro RTX 6000).We adapt the OOD detection-based CIL methods in [10, 14] for empirical comparison under GCIL. To this end, following [10, 14] , we propose to build an OOD detector for each graph task to perform task ID prediction and within-task classification simultaneously. Specifically, for task t with C classes, we aim to learn an OOD detector f t o (•) with C + 1 classes. The extra class represents the OOD data for this task. In this paper, we implement the OOD detector as a two-layer SGC [35] model and take the data in replay buffer Buf <t as the OOD data for task t. Formally, the OOD detector is optimized by minimizing the following objective for task t:EQUATIONwhere Y Buf = C + 1 represents the labels of data in the replay buffer Buf <t . The buffer Buf <t is constructed via sampling previous graphs following ERGNN [44] . Note that there are no replay data for task 1 to train the OOD detector. To overcome this issue, we propose to generate OOD data for task 1 based on graph augmentation [45] .After learning all the tasks, we follow Eq. ( 1) to compute the class probabilities for the test samples. Specifically, a test sample is fed into all the learned OOD detectors to obtain the OOD score and class probabilities within the corresponding tasks. For example, for task t, the learned OOD detector would output the class and OOD probabilities {y t 1 , . . . , y t C , o t } for the test sample. As the OOD score indicates the probability of the test sample is OOD to this task, the final probabilities of the test sample w.r.t. the classes in task t can be calculated as {(1 -o t )y t 1 , . . . , (1 -o t )y t C }. Among all the class probabilities of all tasks, the class with the highest probability is predicted as the class for the test sample. Following [39] , four large GCIL datasets are used in our experiments.• CoraFull3 : It is a citation network containing 70 classes, where nodes represent papers and edges represent citation links between papers. • Arxiv4 : It is also a citation network between all Computer Science (CS) ARXIV papers indexed by MAG [23] . Each node in Arxiv denotes a CS paper and the edge between nodes represents a citation between them. The nodes are classified into 40 subject areas. The node features are computed as the average word-embedding of all words in the title and abstract. • Reddit5 : It encompasses Reddit posts generated in September 2014, with each post classified into distinct communities or subreddits. Specifically, nodes represent individual posts, and the edges between posts exist if a user has commented on both posts. Node features are derived from various attributes, including post title, content, comments, post score, and the number of comments. • Products6 : It is an Amazon product co-purchasing network, where nodes represent products sold in Amazon and the edges between nodes indicate that the products are purchased together. The node features are constructed with the dimensionality-reduced bag-of-words of the product descriptions.The statistics of the used graph datasets are summarized in Table 5 .• EWC [12] is a regularization-based method that adds a quadratic penalty on the model parameters according to their importance to the previous tasks to maintain the performance on previous tasks. • MAS [2] preserves the parameters important to previous tasks based on the sensitivity of the predictions to the changes in the parameters. • GEM [18] stores representative data in the episodic memory and proposes to modify the gradients of the current task with the gradient calculated on the memory data to tackle the forgetting problem. • LwF [13] employs knowledge distillation to minimize the discrepancy between the logits of the old and the new models to preserve the knowledge of the previous tasks. • TWP [15] proposes to preserve the important parameters in the topological aggregation and loss minimization for previous tasks via regularization terms. • ERGNN [44] is a replay-based method that constructs memory data by storing representative nodes selected from previous tasks. • SSM [41] incorporates the explicit topological information of selected nodes in the form of sparsified computation subgraphs into the memory for graph continual learning. • SEM [42] improves SSM by storing the most informative topological information via the Ricci curvature-based graph sparsification technique. • CaT [17] condenses each graph to a small synthesized replayed graph and stores it in a condensed graph memory with historical replay graphs. Moreover, graph continual learning is accomplished by updating the model directly with the condensed graph memory. • DeLoMe [20] learns lossless prototypical node representations as the memory to capture the holistic graph information of previous tasks. A debiased GCL loss function is further devised to address the data imbalance between the classes in the memory data and the current data.Specifically, average accuracy (AA) and average forgetting (AF) are calculated from the lower diagonal accuracy matrix M ∈ R T ×T , where T is the number of the tasks. The entry M tj (t ⩾ j) denotes the classification accuracy on task j after the model is optimized on task t. Therefore, the row in M t,: records the performance on all previous tasks after learning task t, and the column M :,j describes the dynamic of performance on task j when learning different tasks. After learning all the T tasks, the overall average accuracy (AA) and average forgetting (AF) can be calculated as follows:EQUATIONTo sum up, AA evaluates the average performance of the model on all the learned tasks after learning all the T tasks, and AF describes how the performance of previous tasks is affected when learning the current task. A positive AF indicates learning the current task would facilitate the previous tasks and vice versa. For both AA and AF, the higher value denotes better GCL performance.Accuracy of task prediction with different task formulations. We further evaluate the accuracy of task prediction with different task formulations, i.e., numerically descending and random ordering.The results are shown in Table 6 . The results demonstrate that the proposed TP can accurately predict the task IDs in terms of all formulations.Comparison to Task-Specific Models As discussed in the main paper, another straightforward way to overcome forgetting is to learn task-specific models for each task. We further compare the number of additional parameters and the performance of the proposed graph prompting with task-specific models besides the parameters of the backbone. The two methods can both achieve forget-free for GCIL with the proposed task identification. The results are reported in Table 7 where F is the dimensionality of the node attribute, d is the number of hidden units of SGC and T denotes the number of tasks. From the table, we can see that the proposed methods can achieve very close performance to task-specific models while introducing significantly small additional parameters for all tasks in GCIL.The proposed method first learns a GNN backbone based on the first task with graph contrastive learning. Then, the model remains frozen and the task-specific graph prompts and classifiers are optimized to capture the knowledge of each task separately. In experiments, we employ a two-layer SGC [35] as the GNN backbone model with the number of hidden units in all layers as d. Suppose all tasks contain the same number of nodes as N , the time complexity of the graph contrastive learning on the first task is O((4|A |F + 2N dF + 3N d 2 )E 1 + T i=1 (4|A 1 |F + 2N dF + 3N d 2 + 4kN F + 2dN C)E 2 ), which is linear to the number of nodes, the number of edges, and the number of node attributes involved in all the graph tasks.In Table 8 , we report the total training time and inference time of all tasks on the CoraFull dataset, with representative models TWP [15] , SSM [41] and DeLoMe [20] as the baselines, where TWP is a regularization-based method and the other two baselines are replay-based methods. From the table, we can see that replay-based methods require more time for training. This is because they typically need to construct the memory buffer based on different strategies for replaying with the new graph data. Moreover, these memory buffers accumulate to store information from all learned tasks, resulting in the size of them becoming larger with more tasks learned. Notably, our method requires the smallest amount of training time as it does not introduce replaying memory and regularization terms. As for the inference time, the three baselines require the same amount of time as they all learn a model for all tasks. Our method requires slightly more inference time due to its task ID prediction module. Thus, there is a computational overhead in the inference of our method TPP, but it is trivial.This paper investigates graph class-incremental learning with task identification and graph prompting. The task identification is achieved by modeling each graph task with task prototypes based on Laplacian smoothing. We theoretically and empirically demonstrate that task identification can be accurately performed across graphs. This helps address the inter-task class separation issue. To overcome the catastrophic forgetting problem, we propose a graph-prompting approach that absorbs within-task discriminative information into small task-specific graph prompts. The proposed method achieves significant performance improvement. One key limitation lies in the limited representative capacity and generalizability of the GNN backbone model in prompting. This paper constructs the GNN based on the first task for each dataset, resulting in the capacity of the model being constrained by the size of the first task and not applicable to other datasets directly, i.e., a different GNN backbone needs to be trained separately for each dataset. In our future work, we aim to explore approaches to learn more strong GNN backbones that are transferable across different datasets.Graph continual learning aims to continually learn a model that not only accommodates the new emerging graph data but also maintains the learned knowledge of previous tasks. It eliminates the need to retrain the model on all data when new data emerges, significantly reducing computational costs in real-world applications. This paper studies the challenging graph class-incremental learning and proposes a novel, memory-efficient, and forget-free method that is easy to learn and computationally efficient (and thus eco-friendly). Additionally, the proposed method does not require storing previous data for replay, thereby preserving data privacy. • The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. • The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material.Justification: The research conducted in the paper strictly conforms the code of ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).https://github.com/QueuQ/CGLB/tree/masterhttps://docs.dgl.ai/en/1.1.x/generated/dgl.data.CoraFullDataset.htmlhttps://ogb.stanford.edu/docs/nodeprop/#ogbn-arxivhttps://docs.dgl.ai/en/1.1.x/generated/dgl.data.RedditDataset.html#dgl.data. RedditDatasethttps://ogb.stanford.edu/docs/nodeprop/#ogbn-products 


Decision: This paper investigates a graph class-incremental learning problem with unknown task identities. The authors designed a novel graph task profiling and prompting (TPP) approach. They also provided theoretical analysis to show that a simple Laplacian smoothing-based graph task profiling approach can achieve accurate graph task ID prediction. Extensive experimental results are reported and discussed. All the reviewers recognized the technical contributions of this work. Also, during the post-rebuttal discussion, reviewers agreed that their previous concerns have been addressed in the rebuttal. The authors are highly encouraged to further improve their final version by incorporating the comments and suggestions from reviewers.

Reviews: review: paper_summary: paper_summary: The paper proposes a Replay-and-Forget-Free Graph Class-Incremental Learning (GCIL) approach called Task Profiling and Prompting (TPP). This method addresses the challenges of class-incremental learning in graph tasks without relying on task identifiers during inference. By using Laplacian smoothing-based task profiling for accurate task ID prediction and a novel graph prompting approach, TPP eliminates catastrophic forgetting and improves classification accuracy across multiple tasks.
strength_weakness: strength_weakness: - Although CIL problem is interesting, the problem definition in Section 3.1 requires some clarification. Are there any real setting that a sequence of connected graphs (tasks) appear during training, these graphs may be the same but the target tasks are different? 
Besides, during testing, why a GCIL model is required to classify a test instance into one of all the T × C classes? Should it be firstly identify its tasks (1 of T), then assign to C classes?


- Likewise, the datasets used in experiments, have been applied for routine scenarios. Why they should be considered into GCIL setting?
questions: questions: - Why "Despite being only learned on G1, f(·) can effectively adapt to all subsequent tasks with graph prompts" as written on line 228-229? Will this lead to high fluctuation if we choose different G1? Could the authors provide some empirical results on that?


Please also check my comments above.
limitations: limitations: NA
paper_summary: paper_summary: This paper studies the graph class-incremental learning problem with unknown task identities. Specifically, the unknown task identity is the key challenge, and this work proposes a Laplacian smoothing-based graph task profiling approach that is theoretically justified capable of predicting the task identities. 

Besides, the forgetting problem is alleviated through a graph prompting approach. This approach learns a graph prompt for each task, such that the classification models for different tasks are separated.

The experiments are conducted on four datasets.
strength_weakness: strength_weakness: The experimental setup is not introduced with details.

The introduction on the background is not clear enough. For example, what is the relationship between identifying the tasks and overcoming the forgetting problem. Is recognizing the tasks correctly enough for avoiding the forgetting problem.
questions: questions: 1. How are the datasets split into different tasks? Will different splitting strategy affect the performance?

2. What is the relationship between identifying the tasks and overcoming the forgetting problem. Is recognizing the tasks correctly enough for avoiding the forgetting problem.
limitations: limitations: As mentioned by the authors, the main limitation of the work is the limited representative capacity and generalizability of the GNN backbone model in prompting.
paper_summary: paper_summary: This paper addresses the challenge of class-incremental learning (CIL) in graph data (GCIL) by proposing a novel Task Profiling and Prompting (TPP) approach. It leverages Laplacian smoothing-based task profiling to achieve accurate task ID prediction, thereby mitigating inter-task class separation issues, and introduces a graph prompting method to prevent catastrophic forgetting without the need for data replay. Extensive experiments on four benchmarks demonstrate that TPP achieves 100% task ID prediction accuracy and significantly outperforms state-of-the-art methods in average CIL accuracy while being fully forget-free.
strength_weakness: strength_weakness: - The proposed graph prompting method appears to merely apply the technique from [1] to the graph domain, lacking technical novelty.
- The proposed TP method raises several significant concerns:
  - The proposed TP method consists of Laplacian smoothing and average pooling without any training. Since Laplacian smoothing and GCN are significantly similar, there is no clear reason why the GCN-based OOD detector (in OODCIL) should underperform compared to the proposed TP. I kindly ask the authors to compare the performance of the GCN-based OOD detector and provide an explanation of the results, with exact numerical values rather than charts. For a similar reason, I do not understand why OODCIL significantly underperforms compared to most baselines. Therefore, please provide the following two sets of results: 1) replacing the task ID prediction module in OODCIL with TP, and 2) replacing the task ID prediction module in TPP with the OOD detector from OODCIL.
  - The zero AF scores indicate that the proposed TP perfectly classifies the task ID, which raises suspicions about the task formulation. Specifically, I suspect that each task was formulated in a way that gives TPP an advantage, making it easier to predict the task ID. Therefore, I kindly ask the authors to provide experiments under different task formulations, such as: 1) randomly sampling classes for each task, and 2) splitting the classes in numerical order by the given class number (e.g., (0,1), (2,3), (4,5),...,) and so on.
 
- The absence of available source code to verify the results amplifies my suspicions about the experimental results.

- In Theorems 1 and 2, the authors assume a sufficiently large number of Laplacian smoothing steps (i.e., $s \rightarrow \infty$). However, this assumption seems flawed because, as $s$ increases, the prototype will collapse due to the oversmoothing problem, making each task indiscriminative. Furthermore, the authors set the value of $s$ to 3 in their experimetns, which is far from a sufficiently large number of steps. I kindly ask the authors to provide experimental results for the accuracy of the task ID prediction module with the value of $s$ varying from {3, 5, 7, ...}. These results should demonstrate that as $s$ increases, the accuracy should increase as well.







[1] Learning to Prompt for Continual Learning, CVPR 2022
questions: questions: See Weaknesses
limitations: limitations: The authors addressed the limitations.
paper_summary: paper_summary: - The paper tackles the problem of graph class-incremental learning. The proposed TPP consists of two modules, that is, task profiling and graph prompting. 
   - The task prediction is accomplished by learning task prototypes based on graph Laplacian smoothing. Specifically, task profiling aims to accurately predict the task ID of each task during inference by constructing Laplacian smoothing-based task prototypes. 
   - Graph prompting aims to capture task-specific knowledge into graph prompts. Graph prompting is to avoid the catastrophic forgetting of the knowledge learned in previous graph tasks, which learns a small discriminative graph prompt for each task. 
- TPP shows significant performance improvements, as demonstrated by experiments on four graph datasets.
strength_weakness: strength_weakness: - The task prediction relies on the graph transduction setting. The paper focuses on the subgraph incremental learning without considering the inter-edges between graph tasks, resulting in the proposed method not generalizable to other settings effectively.
- Not clear definitions of different categories of methods for graph continual learning. The authors argue that graph prompting can reduce the heavy burdens on optimization and storage with the increasing number of tasks compared to training a separate GNN for each task. However, there are no empirical comparisons.
- Some ablation studies are missing.
questions: questions: - The authors should point out the key differences of task prediction between image and graph more clearly.
- The authors should include the comparisons between graph prompting and training separate GNNs for each task. Can the proposed task identification method be used for other domains like continual image classification? Since the authors argue that graph prompting can reduce the heavy burdens on optimization and storage compared to training a separate GNN for each task, the authors should include the comparisons between graph prompting and training separate GNNs for each task.
- In Table 3, why is the performance of TPP without task prediction significantly low as the graph prompts learn task-specific knowledge?
- In Fig. 4(a), the performance of TPP becomes stable when the size of the graph prompts is larger than one. The authors should provide a more detailed analysis on this phenomenon. The task prediction relies on the graph transduction setting and the accuracy of task prediction with training nodes can also achieve very high accuracy as shown in Fig. 4(b). Therefore, the task identification can be simply conducted by averaging all the node features as the task prototypes. The authors should compare the proposed method with this approach.
- The authors are encouraged to include clear definitions of three categories of methods for graph continual learning to make the paper more comprehensive. Besides, the descriptions of the baselines should be also included.
limitations: limitations: Yes, they addresed.

Comments: comment: Dear Reviewer j8FV,

Thank you so much for your time and great support on verifying our code and the task ID prediction accuracy, and for the increase to an acceptance score. We're very pleased to know that our response has addressed most of your concerns. Please kindly let us know if there are any further questions.
I have carefully reviewed the code and verified the 100% accuracy of task ID prediction. I appreciate your effort, and most of my concerns have been addressed. As a result, I will be raising my score.
Dear Reviewer j8FV,

We have provided detailed replies and newly added empirical results to address your concerns on why the OOD detection method are not as effective as our proposed prototype-based task prediction method. Per your request, we have also released our codes through an anonymous GitHub repository. Could you please kindly check whether they are helpful for answering your questions? We're ready to take any further questions you might have.
These two adverse effects lead to inaccurate task prediction of the OOD score-based approach, much less accurate than the proposed prototype-based approach (please see Table A5). This is mainly due to the fact that i) its training has a strong reliance on sufficient OOD data from the tasks other than the current task and ii) this training performance (or the access to other task data) is largely restricted due to the CIL nature. Designing an effective OOD detector for graph data has not been explored in the literature. It is challenging due to the limited access to OOD data. If we continuously update the OOD detector, we will need to handle catastrophic forgetting problem with the OOD detector and its interference with the CIL classifiers as well. So, in this work, we implement a simple approach for OOD detectors, but we agree that it is an important problem for GCIL.

```
Table A5. Task prediction accuracy of three different methods.
```
|Method|CoraFull|Arxiv|Reddit|Products|
|---|---|---|---|---|
|Laplacian Smoothing|100|100|100|100|
|Node Attributes|97.14|100|100|95.65|
|OOD|62.86|10.00|80.00|78.26|

Besides, the reason for GraphPrompt+OOD barely working is that GraphPrompt+OOD has significantly fewer learnable parameters than OODCIL, which leads to less accurate node classification per task. Combined with less inaccurate task prediction by the OOD detection method, the overall CIL performance is remarkably degraded.

We very much hope the source code and our responses have addressed your concerns. We're more than happy to take any further questions if otherwise. Please kindly advise. Thank you very much!

Best regards,

Authors of Paper 8497
Thank you so much for the insightful comment. 

The source code of TPP is provided at https://anonymous.4open.science/r/TPP-1B07/README.md, where we provide the implementations of TPP and OODCIL in "Baselines/tpp\_model" and "Baselines/ood\_model" respectively.

To explain why the proposed prototype-based methods can achieve higher task prediction accuracy than the OOD-based method, we'd like to clarify the key differences between them despite they share similar neighborhood aggregation strategies. 

Given a sequence of connected graphs (tasks) $(\mathcal{G}^1, \ldots, \mathcal{G}^T)$, where each task contains a set of unique $C$ classes of graph data, TPP constructs task prototypes for each task at its training stage, denoted as $\mathcal{P} = (\mathbf{p}^1,\ldots,\mathbf{p}^T)$. During inference, the prototype $\mathbf{p}^{\text{test}}$ for the test task is constructed, and task prediction is performed by identifying the most similar prototype in $\mathcal{P}$. Note that **this process in TPP does NOT involve any training and data reply**. Despite the simplicity, the prototype-based task prediction can achieve surprisingly good performance. This is attributed to the discrimination of the graph structure and node attributes between different tasks, as shown in Figure 3 in the paper.

**Different from our training-free and reply-free method, OODCIL requires training an OOD detector for each task using data from the current task as in-distribution (ID) data and the rehearsal data from the other tasks as OOD data, and it then utilizes the OOD score to perform task prediction**. This means there are $T$ OOD detectors after learning $T$ tasks. During inference, a test graph is fed into all the $T$ detectors that obtain an OOD score for each task, and the test graph is predicted to belong to the task with the lowest OOD score. Specifically, let $f_o^t(\cdot)$ be an OOD detector trained for task $t$ and there will be $T$ detectors: $(\{ f_o^1(\cdot), \ldots, f_o^T(\cdot)\})$ after sequentially learning $T$ tasks. Then, for a test graph $\mathcal{G}^{\text{test}}$, ideally, the learned OOD detector $f_o^t(\cdot)$ should yield the lowest OOD score if $\mathcal{G}^{\text{test}}$ comes from task $t$ and output a high OOD score if otherwise. To endow OOD detector $f_o^t(\cdot)$ with such an ability, the ideal case is that we have ID data from task $t$ and the OOD data from all other tasks. However, due to the sequential emergence of graph tasks and the restriction of access to previous tasks, we treat the current graph at task $t$ as ID data and construct the OOD data by a data replay approach (i.e., sampling subgraphs from all previous $t-1$ tasks) in our experiments. The detector $f_o^t(\cdot)$ is then optimized to perform a $(C+1)$-way classification, where the first $C$ entries of the classification probabilities are for ID classes at task $t$ and the $(C+1)$-th probability output is used to define the OOD score. 

However, the OOD detector $f_o^t(\cdot)$ can get only limited access to the graph data from all $(t-1)$ previous tasks (i.e., having access to the replay data only). Moreover, when training $f_o^t(\cdot)$, we also do not have any access to graph data of unseen task $j\in(t, T]$. Thus, *due to the lack of sufficient training samples for seen tasks and the absence of the samples of unseen task $j$*, the trained $f_o^t(\cdot)$ can yield a lower score for the task $j$ than the OOD score yielded by $f_o^j(\cdot)$. This means that $f_o^j(\cdot)$ can often produce a lower OOD score for task $j$ than for the other tasks, but the lowest OOD score yielded by  $f_o^j(\cdot)$ is still smaller than the OOD score yielded by the other detectors for the same task $j$, leading to incorrect task prediction. For example, in Table A4 below, the OOD score for task 3 yielded by $f_o^1(\cdot)$ is lower than that yielded by $f_o^3(\cdot)$ (note that task $3$ has the lowest OOD score among the OOD scores yielded by $f_o^3(\cdot)$), and the OOD scores for task 4 and task 5 yielded by $f_o^1(\cdot)$ is lower than that yielded by $f_o^4(\cdot)$ and $f_o^5(\cdot)$ respectively. As a result, the OOD scores yielded by OOD detectors trained at earlier tasks are generally very low, e.g., the OOD scores in columns "$f_o^1(\cdot)$" and "$f_o^2(\cdot)$" in Table A4, leading to incorrect prediction of the tasks 3, 4 and 5 to be task 1.

```
Table A4. OOD scores of each test task which are yielded by all OOD detectors on the Arxiv dataset with 5 tasks. The test graph is predicted to be the task ID whose OOD detector yields the smallest OOD score. 
```

|Test Graph|$f_o^1$|$f_o^2$|$f_o^3$|$f_o^4$|$f_o^5$|
|---|---|---|---|---|---|
|Task 1|**0.08**|0.92|0.90|0.89|0.94|
|Task 2|0.16|**0.07**|0.86|0.87|0.89|
|Task 3|**0.13**|0.31|0.17|0.92|0.85|
|Task 4|**0.16**|0.42|0.82|0.34|0.96|
|Task 5|**0.10**|0.37|0.48|0.93|0.29|
I appreciate the thorough response of the authors. However, I'm still suspicious about your task prediction performance. 

Specifically, the authors claimed that "given a test sample, TP explicitly predicts the task ID by finding the most similar prototype while OODCIL relies on the OOD score to predict the task probability. As a result, the task prediction of OODCIL heavily relies on the performance of the detector." However, this explanation does not fully address my concerns. The proposed TP is essentially a neighborhood normalized aggregation using their raw node features. On the other hand, the GCN-based OOD detector includes a GCN encoder that functions similarly through neighborhood aggregation. Moreover, the GCN encoder is trained specifically to discriminate between the current task and other tasks—a step that the proposed TP lacks. Therefore, it remains unclear to me why TP significantly outperforms the GCN-based OOD detectors by such a wide margin. The results presented in the third row of Table A1 (i.e., GraphPrompt + OOD) seem particularly questionable, as the performance is inexplicably low (nearly equivalent to that of a random classifier). The authors should clarify and convince readers of the specific factors that enable TP to outperform a seemingly similar approach (GCN-based OOD detector) so dramatically.

My skepticism is further heightened by the results in Table A3. For the Arxiv and Reddit datasets, the performance reaches "100%" accuracy without any Laplacian steps, which implies that simply utilizing node features can perfectly discriminate between tasks. In other words, task prediction appears to be an exceptionally easy problem that can be fully resolved by merely calculating the similarity of raw node features. If that is the case, why does the GCN-based OOD detector struggle with such an apparently straightforward problem?

In summary, I still have significant concerns regarding the perfect performance reported for the proposed TP:

What specific factors allow the proposed TP to significantly outperform the GCN-based OOD detector?
How does the method achieve perfect prediction performance by merely using raw node features and their prototypes for similarity search?
Given these concerns, I strongly urge the authors to provide the source code, as it is the most effective way to address these issues.
I am very open to discussing these concerns further with the authors.

Best regards,
Reviewer j8FV