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 2024 poster (2024)
Keywords: graph class-incremental learning
forget-free
graph prompting
task identification
Primary area: graph_neural_networks

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.

Replay-an--Porget-Free Graph Class-Incremental Learning: A Task Profiling and Prompting Approach
Chaoxi Niu', Guansong Pang"; Chen', ,ing Liu
AAII, University of Techhnolog Sydney, Australia
2 School of Computing and Information Systems, Singapore Management University, Singapore
Department of Computer Science, University of Illinois at Chicago, USA
chaoxi niuustudent. uts utt.edu........... edu. au, gspangêsmu. wer.gessuueduu.sgg..... edu..g ling. chen@uts. eewettt.edd.aar au, liubQuic.
Abstract
inssemnncremetall learning (CIL) aims to continually learn sequence of tasks, with each task consisting of 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 challenging problem. In this paper, we show theoretically that accurate task prediction on graph data can achieved by a Laplacian smoothing-bar -ased graph task profiling approach, in which each graph task is modeled by a task prototype based on Laplacian smoothing over the graph. guarantees that the task prototypes of the same graph task nearly the same with large smoothing step, while those of different tasks are distinct due to differences 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 small discriminative graph prompt for each task, essentially resulting in a separate classification model for each task. The prompt learning requires the training of single graph neural network (GNN) only once on the first task, and no data replay required thereafter, thereby obtaining a GCIL model being both replay-free and forget-free. Extensive experiments 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-ee accuracy, and iii) our model is fully free of forgetting on the four datasets. Code is wwt.eoolaaaaa////ee
four
competing methods by at least 18% in average CIL
available at https://github.. http://iihuubcoommmaaaaa
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 previous tasks due to model updating on new tasks.
*Correspondigg author: G. Pang geepag@emu.eedi edu.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Clax
Two lasks
(b) Task
(c) Task 2
(d) Task I with Prompt
(e) Task with Prompt
Figure I: (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 discriminative information
forgetting, we learn graph prompt for each task that absorbs task- 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 mask-incremental learning (GTIL) is another GCL setting where the task ID 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, 41,,4,44,,,, 42, 44J. This paper focuses the GCIL setting 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 memory module for data replay [17,20, 217,20,20,11 41,4,, 44J. 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 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 test sample can be accurately predicted by using 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. lb,c) instead of all the learned tasks (e.g., both tasks in Fig. la), 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 the prompts can ensure the intra-task class separation, as shown in Fig. dd,e. At test time, given 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 separate classification model for each graph task, i.e. no continual model updating, completely avoiding the forgetting problem (i.e., forget
Overall, this work makes the following main contributions. profiling and prompting (TPP) approach, which is the first replay- and forget-free GCIL approach. (2): We reveal theoretically that a simple Laplacian smoothing- can achieve accurate graph task ID prediction. To the best of our knowledge, it is the first work that leverages the non -uclldeid properties of graph data to enable graph task ID prediction. It achieves
(1): We propose a novel graph task
graph task profiling approach

---

100% prediction accuracy across all four datasets used, eliminating the inter-task class separation issue in GCIL. (3): We further introduce novel graph prompting approach that learns 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 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-of- the-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.
2 Related Work
Graph Continual Learning. Various methods have been proposed for GCL [7, 1,,1,
38, 38,41,42,,44 44] and can be divided into three categories, ie., regularization-based parameter isolation- based, 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,,0,,11,44 42,42,44 44] employ an additional memory buffer to store the information of previous tasks and replay them when learning new tasks. The ways 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 significant challenge these methods, especially for the CIL setting where the task IDs are not provided when testing.
To improve the CIL performance, emerging research direction focuses 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 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-trat traitrained 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 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 crompting-based continual learning methods have been proposed [32-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.
3 Methodology
3.1 The GCIL, Problem
Formally, GCL can be formulated as learning a model on a sequence of connected graphs (tasks) {G). ...., ......T)) GT} where T is the number of tasks. Each G' XA')'') is newly emerging graph,
3

---

Training
Tusk Profiling
Graph Prompting
Task Identification
Retrieval & Classifictiion
g
glter
oiue
Photorspe
Clas ceneefactiinn
Laplacian
Clace
Smoothing
Qutry
GONN
Aid
Grrpp Procppe
Groph Prompi
Node
Attributes
Loamable
Figure 2: Overview of the proposed TPP approach. During training, for each graph task t, the task prototype p' is generated by applying Laplacian smoothing on the graph G and added to P= (p'....,.''' 1_ At the same time, the graph prompt &' and the classification head oo for this task are optimized on G' 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 and remains frozen for subsequent tasks.
where A denotes relations between N nodes of the current/new task, X NxF represents the node attributes with dimensionality of F, and the labels of nodes can be denoted as Y Each task contains a unique set of classes graph, i.e., (Y² y Ø + j). When learning task the model trained from previous tasks only has access to the current task data G The goal is to accommodate the model to current graph G while maintaining the classification performance on the previous graphs "G'....,,"* assuming that each task has classes, after learning all tasks, a GCIL model is required to classify a test instance into one of all the T x C' classes.
G.,1),, J. In GCIL, the task IDs are not available during inference. Thus,
3.2 Overview of The Proposed TPP Approach
Inspired by prior studies [10, we decompose the class probability of test sample xlstt belonging to the j-th class in task in GCIL into two parts
H(r5|x"**) = H (v/) lest , (I)(())
(1)
where (t represents the task ID prediction probability of task and (x 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.
.t) denotes the
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 we will demonstrate theoretically below. Moreover, to obtain accurate intra-task class classification within the identified task, novel graph prompting approach is further proposed to learn 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 model being both replay-free and forget-free free. During inference, given a test sample, TPP first performs the task ID prediction and then retrieves the corresponding task graph prompt concatenate with the sample for the GCIL classification. Below we introduce the TPP approach in detail.
3.3 Laplacian Smoothing-based Task Profiling for Graph Task ID Prediction
To leverage the graph structure and node attribute information, we propose to use 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 = (4'')'), we construct task prototype p' for this task based on the train set denoted as {z,li E train ). where yr is the train set of G³. Given G', the Laplacian smoothing is first applied on the graph G. obtain the smoothed node embeddings Z::
= (1- i' -
where denotes the number of Laplacian smoothing steps, / is an identity matrix, and i' is the graph Laplacian [3] matrix of À' A' + (i.e., L' D' -A' with D being the diagonal degree matrix
A

---

و,z)). of A' and = وك embeddings of train nodes:
azy).
Then, the task prototype p' is constructed by averaging the smoothed
p'
(((i))++
(3)
Irain
Similarly, the task prototypes for all tasks can be separately constructed and stored, denoted as P (p= ..... ,.''. Given test graph Glest at testing time, we predict the task ID of glest by querying the task prototype pool P. Specifically, the task prototype of glest is obtained with the set of test nodes in similar way on training graphs via Eq. (2) and Eq. (3), ie.,
test p
2, jest (D
XE 1ess
where Viest denotes the set of nodes to be classified in gtest and प, is the smoothed embedding of the test node after s-step Laplacian smoothing. Then, we query the task prototype pool P with the test prototype p plet and return the task II) whose task prototype is most similar to plst
jest arg min min(d(p (d(p test , .p')...., test .p")))
(5)
where d(-)) represents an Fuclidean distance function and fest is the predicted task ID of grest
As discussed in Sec. 3.2, more accurate task ID prediction leads to better classification performance for GCIL. Below show theoretically that the task IDD of the test graphs can be accurately predicted with our simple Laplacian smoothing based task profiling approach.
Theorem If graphs for all tasks are not isolated and the test graph gies comes from the task t, ie., n and G have the same set of classes, then the distance between ptss and pt approaches to zero with a sufficiently large number of Laplacian smoothing steps s:
lim d(p" .p') =0
(6)
Theorem 2. Suppose the test graph comes from task t, and ler e and e be the differences in node degrees and node attributes between two different tasks I and respectively, which are defined by (Doy1 = (Dt)3 Diag(e) and X = =x* +x. e. Then the distance between the task prototypes of task t andd) j obtained with large steps of Laplacian smoothing can be explicitly calculated as:
d(p jest pp) |[(ex)=e (e)) X2122,
(7)
where cjy = (1, 11 is the N-th eigenvector of task and (T denotes its transpose.
The two theorems indicate that i) if the test graph belongs to task L, with a large s, the distance between pest and p' would become zero with the proposed Lapla- cian smoothing and prototype construction method (Theorem 1); and ii) for graphs from different tasks, since they contain dif- ferent set of classes, they have large dif- ferences in graph structure and node at- tributes, which can lead to large distance between task prototypes p' and p (The- orem 2), thereby having the following in- equality hold if grest comes from task I:
Distribution of Node Degree
Visualization of Node Attributes
Task
Task
200
Task
Task
Fesquncy
159
Figure 3: The differences between two graphs struc- ture and node attributes.
d(p test p²) < d( test p') tt.
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 rather large difference in both graph structure and node attributes. The larger the differences of the two graphs, the larger the gap is between d(p test p²) and d( p²). As result, the task of the test graph can be predicted accurately with Eq. (5). the experimental section, we empirically evaluate the proposed task ID prediction and report its accuracy on different datasets.
e and
5

---

3.4 Graph Prompt Learning for GCIL
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 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 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 task t, the graph prompt can be represented as &' [of..... of)" E TR where & the number of vector- based tokens ø'. For each node in G", the node attribute augmented by the weighted combination of these tokens, with the weights obtained from k learnable linear projections:
e(w,))xx
x
x aj Oj Σ e(w))>x
(9)
where ay denotes the importance score of the token ei in the prompt and w, is learnable projection. For convenience, we denote the graph modified by the graph prompt as g (A x + F²). Then, g' is fed into a frozen pre-trained GNN model f(.) to obtain the embeddings for classification. In TPP, we employ single-layer MLP as the classifier attached to the GNN, denoting of for task t. The node classification at task t can be formulated as:
Y (((',,, X +')).
(10)
Therefore, the graph prompt and the MI.P-based classification head are optimized by minimizing a node classification loss:
min
ECE (cE(O vi),
(11)
VC
train
mit
where Vitinn is the train set of G*, y is the label of node i, of E ÿ is the predicted label, and (csr-) is 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. Mcanwhile, &' and yo learn specific knowledge for the task t. This essentially results in 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 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.
3.5 Training and Inference TPP
Training. The training of TPP can be divided into two parts. First, for each task G the prototypical embedding p' is generated based on Laplacian smoothing and stored in P for task ID prediction. Then, the information of G is explicitly modeled and stored with the proposed graph prompt learning, i.e., Eq. (1 For the GNN backbone f()) in graph prompt learning, we propose to learn it based on the first task g (A', ,X) 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! f()) can effectively adapt all subsequent tasks with graph prompts. Overall, after learning all tasks in (g+ gT) J. the task profiles and task-specific information are explicitly modeled in P (p- (p'....,pp'
{ ....., (") and (spt.... (pt.....,+")
Inference. Given the test graph gees, the task prototype pest is constructed with Eq. (4) and then used to obtain the task ID giest by querying P {p'.... ..... .p") i.e., via Eq. (5). Finally, the test graph grest augmented with the corresponding graph prompt de and fed into the GNN and the classification head constructed with f-) and ytth respectively to get the node classification results. Formally, the inference can be formulated as:
test yiss t (f / Xtea t
arg min (d(ptt pppptttt.).....) p'), ... dep pT))),
(12)
The algorithms of the training and inference of TPP are provided in Appendix C.

---

Table 1: Results (meandistd) under the GCIL setting on four large datasets. The best performance on each dataset is boldfaced. "1" denotes the higher value represents better performance. Oracle Model can get access to the data of all tasks and task IDs, ie., it obtains the upper bound performance. "v" Data Replay indicates the use of data replay in the model, and denotes no data replay involved.
Methods
Dara Replay
CoraFull
Atxiv
Roddit
Products
AA/S
AR%
AA/S
AF/%
AA/M
AF/
AA/S1
AF%
3.540..5
-9..220.5
4,y00.0
-89.1004
59112
97.923.
7.610.7
-88.7.0.88
Joint
81.210.
51,3.0.5
97.110.1
71.510.1
52.6+82
-38.5-1211
8.3-1.0
10.3+11.6
-35.2426.1
238+38
.2.777..
MAS
6.5.11.5
92.3.11.5
4.8 0.4
72.2 4.1
9.2.14455
23.1
16.7
-5.0013199
8.4+1.11
-88.4+1144
-89.8+0.3
11,5+5.5
92.445.9
1.5++L3
.4.7440.44
LwF
1.
59.6.12.2
9.9112.11
11.9
86.611.1
9.21111
48
-18.6.11.66
62.6+222
-30.6444.3
6.7-1.5
-5..6+13.2
8.0-5.22
-18.8-9.0
14.1+4.0
-11442.0
ERGNN
34.5.44.4
61.6.14.3
21.5.15.4
-70.015.55
82.710.4
17.310.4
48.31122
45.7.11.33
SSM
73.01:0.3
-14.8:10.5
-11.7115
94,320.1
62.0116
9921.
SSM degree
75.410..1
9.7.10.0
48.3.10.5
10,7.10.33
94.4.0.00
-1.310..0
63.310.1
9..
SEM-curvature
77.710.8
-10.0:11.2
-8.41133
96.320.1
65.1110
9.500
CaT
80.4
-5.3.0.4
48.2.10.4
12.61.0.7
97.310.1
0.410.0
70.310.9
4..10.8
DeLoMe
81.01022
-3320.3
97.420.1
67.520.7
-173310.3
OODCIL
71.310.55
111.0.11
19.3.1144
.1010..4
79.310.8
0.1
41.6100.9
-66.1044
(Ours)
93.4104
0.0:0.00
0.0:0.0
99.5-0.0
9..020.5
0.0:0.0
Oracle Model
95.51002
90.3104
99.510.0
95,310.3
Experiments
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 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.
Datasets.
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, but they are not suited for graph data. To compare with this type methods, we adapt the OOD detection- basedd 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 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 two-layer SGC [35] as the GNN backbone model with the same For task prototype construction, the number of steps in Laplacian smoothing is set to 3 by default. The number of tokens in each graph prompt, k, is also set to across the four datasets. For each dataset, we report the average performance with standard deviations after 5 independent runs with different random seeds.
[42].
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.
Evaluation Metrics.
4.1 Main Results
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 casily overwritten by the tasks. (2) CIL methods proposed for Euclidean
7

---

Table 2: AA and AF results of enabling existing GCIL methods with our task ID prediction (TP).
CoraFull AA7%T
Arxiv
Reddit
Products
Methods
A
A
AF7%T
AA7%T
AP7%
AA7%1
A17%T
TWP
62.6+2.2
-30.644.3
6.7+1.5
-5..6+13.2
8.0+5.2
-18.8+9.0
14.1+4.0
-11.4+2.0
+TP
94.3+0.9
-1.6+0.4
89,4+0.4
0.0+0.33
78.0+18.5
-0.2+0.44
81.8+3.3
-0.3+0.8
DeLoMe
81.0+0.2
-3.340.3
50.6+0.3
5.1+0.4
97.4=0.1
-0.1+0.11
67.5+0.7
-17.3+0.3
+TP
95.410.11
2.0.0.6
90.410.3
-1.110.2
99.410.0
-0.140.0
94.810.11
-2.210.2
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 CILL 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 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 the highly accurate task ID prediction module in TPP and its effective task musk-specific graph prompt learning (see Sec. 4.2). (6) Our method lifts the SOTA AA performance by 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 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 severe inter-task class separation issue. Our task ID prediction is devised module to tackle this issue. To show its effectiveness as an individual plug-and 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 predictor produces a task II) 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-bat
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 task ID prediction converts the GCIL task into the GTIL task, so that much better AA and AF results are expected.
4.2 Ablation Study
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, 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- 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 4' and classification head yp. The results with and without each module are shown in
8

---

Table 3; Results of TPP and its variants on ablating task ID prediction and graph prompting modules.
Task Prediction
Graph Prompling
CoraFull
Arsiv
Redali
Products
Prompt Classificttinn Head
AANRT
AF
AAR
AFP
AAP%
AFM
AAPWT
AF7
2.0
3.0
-10.9
2.8
-16.8
2.7
-8.2
X
50.7
0.0
54.0
0.0
47.4
0.0
51.8
0.0
73.8
76.3
X
92.8
0.0
82.9
0.0
99.0
0.0
90.7
0.0
93.4
0.0
85,4
99.5
94.0
0.0
Table 3. We can see that the TPP variant without both Ø' and sp,, 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 forgetting since there is no model updating. By incorporating either &' or yp", 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 of obtains much better performance than that with only yo, 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. I, 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.f 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 tokens per prompt. We vary l 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 & = 1 to k = 2 and remains stable when > 2, demonstrating that TPP can be effectively adapted to different tasks with small size of prompt for each task. This also demonstrates the transferability of the learned GNN backbone for all tasks.
Accuracy of Task ID Predic- tion. We further evaluate the accuracy of the proposed task ID prediction method. We com- pare variant of our method that constructs the task prototype based on the node attributes with- out considering the graph struc- ture. In this variant, each task prototype is constructed by sim- ply averaging the attributes of training nodes of each task. The task prototype of 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 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 IDD prediction for all tasks and datasets, which builds a strong foundation for superior GCIL performance of TPP.
NF
90
90
ComFall
ACC
Arxiv
70
Reddit
Product
CoraFull
Arxiv
Reddit
Products
Size of Prompt
Dataset
(b)
Figure 4: (a) The AA results of TPP w.r.t. the size of the graph prompts. (b) Task ID prediction accuracy on all four datasets using Laplacian smoothing (LS) and its variant based on solely node features (NF).
Performance 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 graph dataset with several classes, we split these classes into different tasks in numerically ascending order of the original classes, i... 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.

---

Table 4: Results of average performance of TPP and Oracle Model on datasets with various task formulations.
Task Formulation
Method
CoraFull
Arxiv
Reddit
Prodcuts
Ascending Order
TPP
93.4
85.4
99.5
94.0
Ascending Order
Oracle Model
95.5
90.3
99.5
95.3
Descending Order
TPP
94.5
85,9
99.4
93.9
Descending Order
Oracle Model
96.1
91.6
99.5
94.7
Random Order
TPP
94.8
86.9
99.5
85.9
Random Order
Oracle Model
95.3
91.3
99.7
86.8
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 imbal- anced class distribution of Products and the performance evaluated by the balanced classification accuracy. Specifically, for Products, some classes contain hundreds of thousands of nodes while the number 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 backbonn 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.
5
Conclusion
This paper proposes 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 amoothing-basee graph task profiling approach for GCIL, where each task is modeled by 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, 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 memory memory-effccient TPP i) no memory buffer is required for data replay due to its replay-fie 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 frrget-free and significantly outperforms the state-of-the-art baselines for GCIL.
Acknowledgments
In this work, the participation of Chaoxi Niu and Ling Chen was supported by Australian Research Council under Grant DP210101347, while the participation of Guansong Pang was supported part by Lee Kong Chian Fellowship. The work of Bing Liu was supported in part by four NSF grants (11S-2229866, 19-14444 183-883,770 and CNS 2225427).
References
[1] Davide Abati, Jakub Tomezak, Tijmen Blankevoort, Simone Calderara, Rita Cucchiara, and Babak Ehteshami Bejnordi. Conditional channel gated networks for task-aware continual learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3931-3940, 2020.
[2] Rahaf Aljundi, Francesca Babiloni, Mohamed Elhoseiny, Marcus Rohrbach, and Tinne Tuyte- laars. Memory aware synapses: Learning what (not) to forget. In Proceedings of the European conference computer vision (ECCV), pages 139-154, 2018. 7, 17
10

---

[3] Fan RK Chung. Spectral graph theory. volume 92, American Mathematical Soc., 1997. 4, 14
[4] Taoran Fang, Yunchao Zhang, Yang Yang, Chunping Wang, and Lei Chen, Universal prompt tuning for graph neural networks. In Advances in Neural Information Processing Systems, volume 36, pages 52464-52489, 2023. 3
[5] Falih Gozi Febrinanto, Feng Xia, Kristen Moore, Chandra Thapa, and Charu Aggarwal. Graph lifelong learning: survey, IEEE Computational Intelligence Magazine, 18(1):3,,,,, 2023.
[6] William I. Hamilton, Rex Ying. and Jure Leskovec. Representation learning on graphs: Methods and applications. arXiv preprint arXiv: 770900558, 2017.
[7] Bowei He, Xu He, Yingxue Zhang, Ruiming Tang, and Chen Ma. Dynamically expandable graph convolution for streaming recommendation. Proceedings the ACM Web Conference 2023, pages 1457-1467, 2023.
[8] Christian Henning, Maria Cervera, Francesco D' Angelo, Johannes Von Oswald, Regina Traber, Benjamin Ehret, Seijin Kobayashi, Benjamin Grewe, and Joao Sacramento. Posterior meta- replay for continual learning. Advances in neural information processing systems, 34:14135-
14149, 2021. 3
[9] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs Advances in neural information processing systems, 33:22118 11-11133,,,,,111 2020.
[10] Gyuhak Kim, Changnan Xiao, Tatsuya Konishi, Zixuan Ke, and Bing Liu. A theoretical study on solving continual learning, Advances in neural information processing systems, 55:5065-5079, 2022. 2, 3, 4, 7, 16
[11] Gyuhak Kim, Changnan Xiao, Tatsuya Konishi, and Bing Liu. Learnability and algorithm for continual learning. In International Conference on Machine Learning, pages 16877-16896.
PMLR, 2023. 2, 4
[12] James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 1 114(13):3521-322 2017. 7, 17
et al.
[13] Zhizhong Li and Derek Hoiem. Learning without forgetting. IEEE transactions on pattern analysis and machine intelligence, 40( 2):2935--22477 2017. 7, 17
[14] Haowei Lin, Yijia Shao, Weinan Qian, Ningxin Pan, Yiduo Guo, and Bing Liu. Class incremental learning via likelihood ratio based task prediction. In The Twelfth International Conference on Learning Representations, 2024. 2. 3, 7, 16
[15] Huihui Liu, Yiding Yang, and Xinchao Wang. Overcoming catastrophic forgetting in graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 8653-8661, 2021. 2, 3, 7, 8, 17, 19
[16] Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. Pre-train, prompt, and predict: systematic survey of prompting methods in natural language processing. ACM Computing Surveys, 55(9):1-35, 2023. 3
[17] Yilun Liu, Ruihong Qiu, and Zi Huang. Cat: Balanced continual graph learning with graph condensation. In 2023 IEEE International Conference on Data Mining (ICDM), pages 1157- 1162. IEEE, 2023. 2, 3, 7, 18
[18] David Lopez- Paz and Marc' Aurelio Ranzato. Gradient episodic memory for continual learning. Advances neural information processing systems, 30, 2017. 7, 17
[19] Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3:127-163,
2000.
[20] Chaoxi Niu, Guansong Pang, and Ling Chen. Graph continual learning with debiased lossless memory replay. arXiv preprint ar0iv:2404. 10984, 2024. 2, 8, 9, 15, 18, 19
[21] Massimo Perini, Giorgia Ramponi, Paris Carbone, and Vasiliki Kalavri. Learning streaming graphs with experience replay. In Proceedings of the 37th ACM/SIGAPP Symposium on Applied Computing, pages 470-478, 2022.
11

---

[22] Appan Rakaraddi, Lam Siew Kei, Mahardhika Pratama, and Marcus De Carvalho. Reinforced continual learning for graphs. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pages 1666-1674, 2022. 3
[23] Arnab Sinha, Zhihong Shen, Yang Song, Hao Ma. Darrin Eide, Bo-June Hsu, and Kuansan Wang. An overview of microsoft academic service (mas) and applications. In Proceedings of the 24th international conference on world wide web, pages 243-246, 2015. 17
[24] Junwei Su, Difan Zou, Zijun Zhang, and Chuan Wu. Towards robust graph incremental learning on evolving graphs. In Proceedings of the 40th International Conference on Machine Learning. volume 202 of Proceedings of Machine Learning Research, pages (2728-32748, PMLR, 23-29 Jul 2023. 3
[25] Li Sun, Junda Ye, Hao Peng, Feiyang Wang, and S Yu Philip. Self-supervised continual graph learning in adaptive riemannian spaces. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 4633-4642, 2023. 3
[26] Xiangguo Sun, Hong Cheng, Jia Li, Bo Liu, and Jihong Guan. All in one: Multi-task prompting for graph neural networks. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 21 2120-2131, 2023.
[27] Xiangguo Sun, Jiawen Zhang, Xixi Wu, Hong Cheng, Yun Xiong, and Jia Li. Graph prompt learning: A comprehensive survey and beyond. arXiv preprint arXiv:2311 136,6433,,,, 2023. 3
[28] Zonggui Tian, Du Zhang, and Hong-Ning Dai. Continual learning on graphs: A survey. arXiv preprint arXiv:2402.063: 06.300 2024. 1
[29] Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17:395-416.
2007. 14
[30] Johannes Von Oswald, Christian Henning, Benjamin F Grewe, and João Sacramento. Continual learning with hypernetworks. arXiv preprint arXiv:1906 00695, 2019. 3
[31] Chen Wang, Yuheng Qiu, Dasong Gao, and Sebastian Scherer. Lifelong graph learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 13719-13728, 2022.
[32] Liyuan Wang, Xingxing Zhang, Hang Su, and Jun Zhu. A comprehensive survey of continual learning: Theory, method and application. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
[33] Zifeng Wang, Zizhao Zhang. Sayna Ebrahimi, Ruoxi Sun, Han Zhang, Chen- Yu Lee, Xiaoqi Ren, Guolong Su, Vincent Perot, Jennifer Dy, et al. Dualprompt: Complementary prompting for rehearsal-free continual learning. In European Conference on Computer Vision, pages 631-648.
Springer, 2022. 3
[34] Zifeng Wang, Zizhao Zhang, Chen Yu Lee, Han Zhang, Ruoxi Sun, Xiaoqi Ren, Guolong Su, Vincent Perot, Jennifer Dy, and Tomas Pfister. Learning to prompt for continual learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 139-149, 2022. 3
[35] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning.
pages 6861-6871. PMLR, 2019. 7, 16, 19
[36] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in neural information processing systems, 33:5812-5823, 2020. 3, 6,
[37] Peiyan Zhang, Yuchen Yan, Chaozhuo Li, Senzhang Wang, Xing Xie, Guojie Song, and Sunghun Kim. Continual learning on dynamic graphs via parameter isolation. In Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '23, page 601-611, New York, NY, USA, 2023. Association for Computing Machinery. 2,3
[38] Peiyan Zhang, Yuchen Yan, Chaozhuo Li, Senzhang Wang, Xing Xie, Guojie Song, and Sunghun Kim. Continual learning on dynamic graphs via parameter isolation. In Proceedings the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 601-611,,022 2023. 3
12

---

[39] Xikun Zhang, Dongjin Song, and Dacheng Tao. Cglb: Benchmark tasks for continual graph learning. Advances in Neural Information Processing Systems, 15:13006-13021,2000 2022. 1,
15, 17
[40] Xikun Zhang, Dongjin Song, and Dacheng Tao. Hierarchical prototype networks for continual graph representation learning. IEEE Transactions Pattern Analysis and Machine Intelligence, 45(4):4622-4666, 2022.
[41] Xikun Zhang, Dongjin Song, and Dacheng Tao. Sparsified subgraph memory for continual graph representation learning. In 2022 IEEE International Conference Data Mining (ICDM), pages 1335-1340. IEEE, 2022. 2, 7, 19
[42] Xikun Zhang, Dongjin Song, and Dacheng Tao. Ricci curvature-based graph sparsification for continual graph representation learning. IEFE Transactions on Neural Networks and Learning
Systems, 2023. 2, 3, 7, 15, 17
[43] Xikun Zhang, Dongjin Song, and Dacheng Tao. Continual learning on graphs: Challenges, solutions, and opportunities. arXiv preprint arXiv:2402.11555 11565, 2024.
[44] Fan Zhou and Chengtai Cao. Overcoming catastrophic forgetting in graph neural networks with experience replay. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 4714 2021. 2, 3, 7, 16, 17
[45] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning, arXiv preprint arXiv:2006.0411 2020. 3, 6, 15, 16
13

---

A Proof of Theorems
Theorem 1. If graphs for all tasks are not isolated and the test graph glest comes from the task t, i.e. 9eD and G have the same set of classes, then the distance between ple and p' approaches to zero with sufficiently large number of Laplacian smoothing steps 8:
lim d(p" .p') 0.
Proof. To prove the distance between pl and p' approaches O with a large Laplacian smoothing step 8, we need to illustrate that the features of nodes in G' 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 is N, the
Laplacian matrix (D+)= à (D*) has N cigenvalues with different eigenvectors [29]. Recalling the Laplacian smoothing defined in Eq. (2), the eigenvalues and eigenvectors of -- - (D()))) can be represented as (AI,..., A and (ei.... eN) respectively. With the property of symmetric Laplacian matrix for the non- non-bipartile graph, the eigenvalues of I range of (-1, 1] [3], ie..
are all in the
-I<A <.. < AN 1, eN = (D') 11T E Nx1
(13)
Based on the eigenvalues and the cigenvectors, the result of applying Laplacian smoothing on the node features X after s steps can be formulated as:
(1-(0')
(D') +
[Afel,.... XgeN|X*
(14)
where X - (o..... oNl 'Xt As the eigenvectors orthogonal to each other, rewrite X as 8 = ei..... |x Since the absolute values of the eigenvalues are less than 1 except AN. X would approach O as go infinity, i.e., lim, X = 0, vi # N. Then, we can formulate the smoothed node feature representations Z' follows:
further
zº = (DWN) +
(15)
where {* :] denotes the N-th row of Xt, Therefore, with larger s, the feature of nodes in G would converge to be proportional to the square root of the node degree. By multiplying the smoothed for each node i in the proposed task prototype construction, test and p' would
feature with (D both become to be X { :]. despite that they utilize different nodes to construct the task prototypes. Therefore, the distance between p and p' 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 simple graph augmentation when constructing the task prototypes, which adds an edge between the isolated nodes and the randomly chosen non-isolated nodes 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 e be the differences in node degrees and node attributes between two different tasks t and respectively, which are defnedd by (fi)+ = ( + Diag(e) and X = =x Then the distance between the task prototypes of task t and j obtained with large steps of Laplacian smoothing can be explicitly calculated as:
d(p p2) 11(ex) + (e)
where ely- ( 1TT is the N-th eigenvector of task and (T denotes its transpose.
Proof. As derived in Theorem 1, the task prototypes of task i and with large steps of Laplacian smoothing are test X' and p' -X respectively. Furthermore, the task prototype
14

---

of task & can be represented as p" x² Based on the difference in node degrees and node attributes between task and j. the distance between the task prototypes can be represented follows:
d(p eest p¹) = Ip' -P'll2
(16)
|1(e\x) xxx
X -(el)) (el))=x'1 12
(17)
= =I(elr) (elx + te) (x +ell2
(18)
= 1I(e'r) (e)" 12112
(19)
B Details on Learning GNN Backbone
We 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 = (A', x )) via graph contrastive learning due to its ability to obtain transferable models [36,45] 45] across graphs.
To construct contrastive views for graph contrastive learning, two widely used graph augmentations are employed, ie., edge removal and attribute masking [45]. Specifically, the edge removal randomly drops a certain portion of existing edges in G and the attribute masking randomly masks a fraction of dimensions with zeros in node attributes, i.e.,
= A' R, X X- [x] m...... m....,xyy o m)"
(20)
where R E (0, 1JNNN is the edge masking matrix whose entry is drawn from Bernoulli distribution controlled by the edge removal probability, m E {0, 1 is the attribute masking vector whose entry independently drawn from Bernoulli distribution with the attribute masking ratio, and denotes the Hadamard product. By applying the graph augmentations to the original graph, the corrupted graph J (Á", (1) forms the contrastive view for the original graph G = (A² x²). Then, Č' and G are inputted to the shared GNN f(-) followed by non-linear projection g(-) to obtain the corresponding node embeddings. i.e.. ž )()()))) and Z g(f(G")) 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 (2) z!) can be formulated
as:
cim(()).))) +t//T
(Z. z = log (x) + Σiee sim(a
(21)
Σne e sim(k) 23)/T
where sim(.) represents the cosine similarity and is temperature hyperparameter. Therefore, the overall objective can be defined as follows:
N
L Leentrust
(((()) + E(2))
(22)
2N
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.
C Algorithm
The training and inference processes of the proposed method are summarized Algorithm 1 and Algorithm 2, respectively.
D Experimental Setup
D.1 More Implementation Details
All the continual learning methods including the proposed method are implemented based on the
GCL benchmark 2 For the memory-replay methods, we follow the settings [20]. As in [42],
htttp:://gte bttttp://github http://ggtaaab.cooo///////////ut Don//ueeu//CLLB/tre///e
15

---

Algorithm 1:
Training of TPP
1: Input: A series of graph learning tasks: {g) ...., ....,g'), g" graph neural network f(-). 2: Output: Graph neural network f()), task prototype P (p" ..... p'', graph prompts ( ....., 8²}.
and classifiers {sp " :.").
"....."'
3: Pre-train f() on G with graph contrastive learning (Eq. (22)).
4: for 1,..., do
Obtain the task prototype p' of task (Eq. (3)).
6: Obtain G with graph prompts 2' (Eq. (9)).
7: Optimize of and x by minimizing node classification loss (Eq. (11)).
8:
end for
Algorithm 2: Inference in TPP
1: Imput: Graph neural network f(-), task prototypes P (p'.... ..... ....... .p"). graph prompts (b'....,,0"" ")). classifiers ( s0"),
}, and the test graph glss.
2: Output: Prediction result.
3: Obtain the task prototype n (Eq. (4)).
Infer task s the test graph by querying with p jest (Eq, (5)).
5: Retrieve the corresponding graph prompt tt and classifier xp
6: Obtain gles (A Xttest 46 (Eq. (9)).
7: return (f(A x X + de
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 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 set to 0.001 with Adam optimizer, the training epochs are set to 200 and the temperature r 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 Nvidia GPU (Quadro RTX 6000).
D.2 Details the Design of the OODCIL Method
We adapt the OOD
CIL methods in [10, 14] for empirical comparison under GCIL, To this end, following [10, 14], propose to build OOD detector for each graph task to perform task ID prediction and within-task classification simultancously. Specifically, for task with C' classes, aim to learn OOD detector f((-) with C++ 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 Bufet the OOD data for task t. Formally, the OOD detector is optimized by minimizing the following objective for task l:
min Egg (LCE( Y*) + Len Y 850
(23)
where yBf C represents labels of data in the replay buffer Bufer. The buffer Buf 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 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 {yf.....24 Vc. o') } for the test sample. As the OOD score indicates the probability of the test sample OOD to this task, the final probabilities of the test sample w.r.t. the classes in task / can be calculated {(1 - o² o'))ii..... (1 - o²) o') Among all the class probabilities of all tasks, the class with the highest probability is predicted as the class for the test sample.
16

---

Table 5: Key statistics of the graph datasets.
Dafascts
CoraFull
Arxiv
Reddit
Products
nodes
19,793
169,343
227.853
2,449,028
edges
130,622
1616,,24
11,,615,92
61,859,036
I classes
70
40
40
46
# tasks
35
20
20
23
Avg. nodes per task
8,467
11,393
122,451
Avg. edges per task
4,354
58,312
5,730,794
2,689,523
D.3 Details on Datasets
Following [39], four large GCIL datasets are used in our experiments.
CoraFull': is a citation network containing 70 classes, where nodes represent papers and edges represent citation links between papers.
Arxiv It is also 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 citation between them. The nodes classified into 40 subject areas. The node features are computed as the average word-embedding of all words in the title and abstract.
Reddit 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 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.
Products 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 dimensionnlity-rrduced bag-of-words of the product descriptions.
The statistics the used graph datasets are summarized Table 5.
D.4 Descriptions of Baselines
EWC [12] is a regularization-basee method that adds a quadratic penalty on the model parameters according their importance the previous tasks 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 models 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 regularization terms.
method that constructs memory data by storing representative nodes selected from previous tasks.
ERGNN [44] is a replay-
SSM [41] incorporates the explicit topological information 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.
CoraFul html http://h.....aoooooooo/o//////// arxix arxiv
httppp//coocsta.aaaee////aaaaaat Redai modaaeDataset. htm1#dgl.
RedditDataset
17

---

Table 6: The accuracy of task prediction with other task formulations.
Task Formulation
CoraFull
Arxiv
Reddit
Prodcuts
Ascending Order (Reported)
100
100
100
100
Descending Order
100
100
100
100
Random Order
100
100
100
100
Table 7: Additional parameters and performance (AA%) the proposed graph prompting and
task-specific models.
Method
Additional Parameters
CoraFull
Arxiv
Reddit
Products
Task-specific Models
(F + djdl'
94.3
86.8
99.5
96.3
Graph Prompting
3FT
93.4
85.4
99.5
94.0
CaT [17] condenses each graph small synthesized replayed graph and stores in 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 the memory capture the holistic graph information of previous tasks. A debiased GCL loss function further devised to address the data imbalance between the classes in the memory data and the current data.
D.5 Evaluation Metries: Average Accuracy and Average Forgetting
Specifically, average accuracy (AA) and average forgetting (AF) are calculated from the lower diagonal accuracy matrix M E gT'xT, where 7' is the number of the tasks. The entry Mty(t j) denotes the classification accuracy on task after the model is optimized on task t. Therefore, the row in M,. records the performance on all previous tasks after learning task t, and the column M., 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:
Mrj T
AF E (Mrj M,3)
AA =
(24)
T-1
To sum up, AA evaluates the average performance of the model all the learned tasks after learning all the tasks, and AF describes how the performance of previous tasks 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.
D.6 More Experimental Results
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 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 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, the number of hidden units of SGC and denotes the number of tasks. From the table, performance to task-specific models while introducing significantly small additional parameters for all tasks in GCIL.
see that the proposed methods can achieve very close
E Time Complexity Analysis
The proposed method first learns GNN backbone based on the first task with graph contrastive learning. Then, the model remains frozen and the task-specific graph prompts and classifiers
18

---

Table 8: Total training time and inference time (seconds) for different methods on CoraFull.
Methods TWP
SSM
DcMoLe
(Ours)
Training Time
151.6 254.9
304.6
23.6
Inference Time
0.3
0.3
0.3
0.4
optimized to capture the knowledge of each task separately. In experiments, we employ a two-layer SGC [35] as the GNN backhone 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 ((4]AA 2N + 3 ) where |A||| returns of the number of edges of the G), F represents the dimensionality of node attributes and Ei is the number of training epochs. After that, propose freeze the learned model and learn graph prompts and classifiers for each task. In our experiments, we set the size of each graph prompt to and implement the classification head as a single-layer MLP outputting the probabilities of C' classes. Given the number of the training epochs E2,, the time complexity of optimizing the graph prompt and classifier is ((44NN F + 2dN C) F2), which includes both the forward and backward propagation. Despite the graph model being frozen, the forward and backward propagation of the model are still needed to optimize the task-specific graph prompts and classifiers. Given the number of tasks T in GCIL,, the overall time complexity of the proposed method is O((4AA' + 2N + 3 + 4kNF + E2), which is linear to the number of nodes, the number of edges, and the number of node attributes involved in all the graph tasks.
(4IA 2NdF + 3Nd
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] the baselines, where TWP is a regularization-base 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 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 computational overhead in the inference of our method TPP, but it is trivial.
F
Limitations
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 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.
G Broader Impacts
Graph continual learning aims to continually learn 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 all data when new data emerges, significantly reducing computational costs in real-world applications. This paper studies the challenging graph inaassincremettal learning and proposes novel, meforr-efficient, and forget-fre free method that is easy to learn and computationally efficient (and thus eco- roo-frienlly). Additionally, the proposed method does not require storing previous data for replay, thereby preserving data privacy.
19

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: This paper studies the graph insssinccremenal learning problem and proposes a novel approach. These claims are clearly made in the abstract and introduction sections.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of the work discussed in Appendix F
Guidelines:
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 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 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 few datasets or with 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, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
20

---

Justification:
The theorems stated in the main paper are proved in Appendix A.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
The proposed method implemented with public graph continual learning benchmark. All the implementation details are reported in the main paper and appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
21

---

Answer: [Yes]
Justification: The datasets used in this paper are publicly available and the code has been released.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
public/guides Stwps//oooeSSumisionnnnn
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https: //n /nipp..ccoom httppssccpppblcccceecccc
/eddeS/Seeub ssi assionoolicgi for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The experimental details are presented in both the main paper and the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to 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.
7. 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 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, confi- dence 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 capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall 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).
22

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 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 range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Computer resources are provided the appendix. Besides, the time complexity of the proposed method provided in the Appendix
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 (c.g., preliminary or failed experiments that NeurlPS Code of Ethics https: / /twrrieuuppp..e/ cc cc/public//eiiccccccccc http://thhhhitiieeteeeeeeeeeaaee
didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification:
The research conducted in the paper strictly conforms the code 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 deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. 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 no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact 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.
23

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is 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 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
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)?
Question:
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 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 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 dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.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, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
25


Reviews:
[{"review_id": "EXK2VBS37J", "reviewer": "Reviewer_4w4P", "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.", "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?\n\n\nPlease also check my comments above.", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The problem of obtaining a GCIL model being both replay-free and forget-free is interesting.\n\n- The presented empirical results are good. \n\n- The theoretical analysis is interesting.", "weaknesses": "- 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? \nBesides, 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?\n\n\n- Likewise, the datasets used in experiments, have been applied for routine scenarios. Why they should be considered into GCIL setting?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the constructive comments and questions. We are grateful for the positive comments on our design and empirical justification. Please see our detailed one-by-one responses below.\n\n>**Weaknesses #1:** The problem definition requires some clarification.\n\nIn the **Global Response to Shared Concerns**, we clarify the task formulation in our experiments. In our setting, we follow the widely-used GCIL setting in [Ref1], where a new graph $\\mathcal{G}^t$ that connects with previously occurred graphs emerges with a new set of target classes at each time step $t$. The setting may be applied to various real-world applications. For example, in a bank transaction network where each account is a node and the edge can be built when there are transactions between two accounts, the newly emerging graph can be formed by new accounts/transactions with new types (classes) of transactions.\n\nDuring inference, GCIL aims to classify a test instance into one of all the learned classes (i.e., $T\\times C$ classes). Most existing GCIL works directly perform the classification without identifying the task ID of test instances, so their class set for each test node includes $T\\times C$ classes. An alternative approach, as suggested by you, is to first identify its task ID, and then perform C-way classification. This is the approach we take in our proposed TPP. This type of methods requires accurate task prediction to guarantee good CIL performance. Inspired by this, we propose the TPP method in this paper, in which the proposed task profiling module shows remarkable task prediction accuracy. \n\n>**Weaknesses #2:** Why these datasets should be considered into the GCIL setting?\n\nFollowing [Ref1], we employ CoraFull, Arxiv, Reddit, and Products as the benchmark datasets for GCIL and follow the same task formulation. This ensures fair comparisons to all methods. The reason for choosing these datasets for GCIL can be attributed that they contain multiple classes so that a diverse set of tasks can be constructed to evaluate the performance of GCIL methods.\n\n>**Question #1:** The performance of TPP with different task formulations.\n\nOur method can achieve stable CIL performance with different starting and subsequent graph compositions. Please refer to our **Global Response to Shared Concerns** in the overall Author Rebuttal section above for newly added empirical results that justify this ability.\n\n**References**\n\n- [Ref1] CGLB: Benchmark Tasks for Continual Graph Learning. NeurIPS 2022 Datasets and Benchmarks Track.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "qzgE0KPHsx", "reviewer": "Reviewer_odiT", "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. \n\nBesides, 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.\n\nThe experiments are conducted on four datasets.", "questions": "1. How are the datasets split into different tasks? Will different splitting strategy affect the performance?\n\n2. 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": "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.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The proposed method can achieve 100% task identification accuracy.\n\nTheoretical analysis is also provided for the proposed method.\n\nThe proposed method is compared against multiple SOTA baselines and obtains consistent performance improvement.", "weaknesses": "The experimental setup is not introduced with details.\n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the constructive comments and questions. We are grateful for the positive comments on our design and empirical justification. Please see our detailed one-by-one responses below.\n\n>**Weaknesses #1/Questions #1:** Not clear experimental setup and the performance of TPP with different task formulations.\n\nPlease refer to our reply in **Global Response to Shared Concerns** in the overall Author Rebuttal section above for this concern.\n\n\n>**Weaknesses #2/Questions #2:** What is the relationship between identifying the tasks and overcoming the forgetting problem?\n\nIn class-incremental learning, the absence of task ID or identification information requires the test instance to be classified into one of all learned classes, leading to the challenge of inter-task class separation. This can exacerbate the forgetting problem in class-incremental learning. By accurately identifying the task ID, the classification is constrained within the task and the forgetting problem can be largely alleviated as shown in Table 2 in the paper. However, it cannot fully overcome the forgetting problem due to the knowledge interference between tasks when training a single model. In this paper, we further address this issue by learning and storing task-specific knowledge in graph prompts, resulting in the proposed method being forgetting-free.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "8hCDeeYNYh", "reviewer": "Reviewer_j8FV", "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.", "questions": "See Weaknesses", "limitations": "The authors addressed the limitations.", "rating": 5, "confidence": 3, "soundness": 1, "presentation": 3, "contribution": 2, "strengths": "- This paper highlights the significant challenge in graph class incremental learning (GCIL).\n- It introduces a novel approach in GCIL, task ID prediction, by devising Laplacian smoothing-based task profiling for graph task ID prediction, which shows surprisingly perfect performance.\n- Furthermore, extensive experiments are conducted to demonstrate the superiority of the proposed method.", "weaknesses": "- The proposed graph prompting method appears to merely apply the technique from [1] to the graph domain, lacking technical novelty.\n- The proposed TP method raises several significant concerns:\n  - 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.\n  - 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.\n \n- The absence of available source code to verify the results amplifies my suspicions about the experimental results.\n\n- 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.\n\n\n\n\n\n\n\n[1] Learning to Prompt for Continual Learning, CVPR 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the constructive comments and questions. We are grateful for the positive comments on our design and empirical justification. Please see our detailed one-by-one responses below.\n\n>**Weaknesses #1:** TPP is similar to L2P [Ref2].\n\nAlthough our TPP and L2P both adopt prompting for class-incremental learning, several major differences highlight our novelty.\n- **Data:** L2P focuses on continual learning in the vision domain where each instance is independent while TPP addresses the graph continual learning where different nodes are connected by edges and not independent. The complex connections make graph continual learning more challenging.\n- **Prompt learning:** L2P follows the key-valued query mechanism to select prompts for inputs and the selected prompts are concatenated with input embedding. In contrast, our prompts operate on raw attributes of nodes and modify them with weighted combinations of prompts. Moreover, L2P employs ViT-B/16 as the backbone, which contains excessive parameters and is well-trained on large-scale auxiliary datasets. However, there are no universal backbones for graph learning. To address this, we learn the GNN backbone based on the first task via graph contrastive learning due to its ability to obtain transferable models across graphs.\n- **Forgetting:** Most importantly, L2P does not have task prediction (TP), but TP is the critical mechanism that gives TPP superior performances. By performing TP and learning task-specific prompts, TPP is fully rehearsal-free and forgetting-free. However, the forgetting problem is still a major issue in L2P.\n\n>**Weaknesses #2.1** Why the GCN-based OOD detector (OODCIL) underperforms compared to the proposed TP and baselines.\n\nWe agree that Laplacian smoothing (LS) is similar to GCN. However, the proposed Laplacian smoothing-based task prediction (TP) is significantly different from the OOD detector-based method (OODCIL). First, we employ LS to construct the task prototypes without any training to profile each task. By contrast, OODCIL needs to fully train an OOD detector to discriminate the current task and OOD data of other tasks. Second, 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. In our experiments, the OOD detector is trained with the current task and OOD data from other tasks. As a result, the OOD detector cannot effectively output the correct OOD score for a test sample, leading to poor performance. Designing more advanced OODCIL may improve the performance, but it is out-of-scope for this paper.\n\nAs suggested, we conducted the experiments by changing the task prediction method in OODCIL and TPP and reported the results in the following table. When using our TP method for task prediction, the performance of OODCIL is significantly improved, similar to the performance of our full TPP method (Graph Prompting + TP). On the other hand, the performance of TPP drops significantly if the OOD-based method is used in TPP for task prediction, showing that accurate task prediction plays a critical role in GCIL’s impressive performance.\n```\nTable A1: The average performance of OODCIL and TPP with different task prediction methods.\n```\n|Method|Task Prediction|CoraFull|Arxiv|Reddit|Products|\n|---|---|---|---|---|---|\n|OODCIL|OOD|71.3|19.3|79.3|41.6|\n|OODCIL|TP|94.6|84.6|99.6|95.1|\n|Graph Prompting|OOD|1.5|4.3|6.0|8.0|\n|Graph Prompting|TP|93.4|85.4|99.5|94.0|\n\nNote that Graph Prompting+TP performs similarly to OOD-CIL+TP. It highlights the importance of our graph prompting learning from another perspective. This is because OODCIL has much more learnable parameters than our Graph Prompting as OODCIL trains a separate GNN for each task whereas Graph Prompting trains only a small GNN once and then learns small prompts for each task using a frozen GNN. Furthermore, OODCIL requires data replay, while our graph prompting is replay-free.\n\n\n\n>**Weaknesses #2.2:** Accuracy of task prediction with different task formulations.\n\nThe following table reports the accuracy of the proposed TP with other task formulations, i.e., descending and random orders, demonstrating that the proposed TP can accurately predict the task IDs in terms of all formulations.\n```\nTable A2: The accuracy of task prediction with other task formulations.\n```\n|Task Formulation|CoraFull|Arxiv|Reddit|Products|\n|---|---|---|---|---|\n|Descending|100|100|100|100|\n|Random|100|100|100|100|\n\n\n>**Weaknesses #3:** Absence of source code.\n\nThe source code will be released upon acceptance.\n\n>**Weaknesses #4:** Accuracy of TP with varying steps of Laplacian smoothing.\n\nIn Theorems 1 and 2, we assume a sufficiently large number of Laplacian smoothing (LS) steps for task prediction. Specifically, for different graph tasks $\\mathcal{G}_i$ and $\\mathcal{G}_j$ consisting of different graph data, larger steps result in the train and test prototypes of the same task being the same (Theorem 1) and ensure the prototypes of different graphs are distinct (Theorem 2) simultaneously. In other words, the over-smoothing problem of LS is not the problem that we aim to address but it is the property that we utilize for accurate task prediction. We report the accuracy of task prediction with varying LS steps in the following table. We can see that the task IDs can be perfectly predicted even with one step of LS. This is attributed to the discriminability among node attributes in different tasks, e.g., task identification can be well predicted even without LS.\n\n```\nTable A3. The accuracy of task prediction with different Laplacian smoothing steps.\n```\n|Steps|0|1|3|5|\n|---|---|---|---|---|\n|CoraFull|97.14|100|100|100|\n|Arixv |100 |100|100|100|\n|Reddit|100|100|100|100|\n|Products|95.65|100|100|100|\n\n\n**References**\n- [Ref2] Learning to Prompt for Continual Learning, CVPR 2022", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "y5ZxSeLoTB", "reviewer": "Reviewer_aHCQ", "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. \n   - 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. \n   - 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. \n- TPP shows significant performance improvements, as demonstrated by experiments on four graph datasets.", "questions": "- The authors should point out the key differences of task prediction between image and graph more clearly.\n- 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.\n- In Table 3, why is the performance of TPP without task prediction significantly low as the graph prompts learn task-specific knowledge?\n- 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.\n- 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": "Yes, they addresed.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The idea of using Laplacian smoothing to predict the task IDs and graph prompts to capture task-specific knowledge is interesting and new in graph class-incremental learning.\n- The proposed method, TPP, is novel, which not only predicts the task IDs of test graph tasks but also distills task-specific information into prompts.\n- The proposed method is both replay-free and forget-free and requires the training of a single GNN only once. \n- The task IDs of each graph task can be accurately predicted with theoretical support.\n- The paper is clearly motivated and well-written.", "weaknesses": "- 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.\n- 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.\n- Some ablation studies are missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the constructive comments and questions. We are grateful for the positive comments on our design and empirical justification. Please see our detailed one-by-one responses below. We will include the new results and discussions below into the paper.\n\n>**Questions #1:** Point out the key differences of task prediction between image and graph more clearly.\n\nThe major difference between images and graphs is that images are i.i.d while graphs are non-i.i.d due to the complex structure of graphs. The graph structure brings a unique challenge for the task prediction of graph continual learning. Most existing task prediction methods for images rely on an OOD detector by treating data from other tasks as the OOD data. In this paper, we utilize the graph structure to perform task prediction by using a Laplacian smoothing-based method to profile each graph task with a prototypical embedding and achieve accurate task prediction.\n\n>**Questions #2/Weaknesses #3:**  Include the comparisons between graph prompting and training separate GNNs for each task.\n\nIn the following table, we report the comparison of TPP and training separate GNNs for each task in terms of additional parameters and the average accuracy, where $F$ is the dimensionality of the node attributes, $d$ is the number of hidden units in an SGC layer and $T$ denotes the number of tasks. From the table, we can see that the proposed TPP method can achieve very close performance to its variant that trains separate GNNs for each task rather than task-specific prompts, while it involves a significantly smaller number of parameters for all tasks in GCIL. \n\n```\nTable A1. Additional parameters and the average performance of the proposed graph prompting and task-specific models.\n```\n|Method | Additional Parameters |CoraFull | Arxiv | Reddit | Products |\n|---|---|---|---|---|---|\n|Separate Models| $(F+d)dT$|94.3| 86.8| 99.5|96.3|\n|TPP|$3FT$ |93.4|85.4|99.5|94.0|\n\nThe proposed task prediction method cannot be directly used for other domains if there is an absence of graph structure information between data instances. A similar prototype-based task profiling approach can be explored for data types like images, but designs for generating more discriminative task profiles may be needed, which would be an interesting future research extension to our method TPP. \n\n\n\n>**Questions #3:** Why is the performance of TPP without task prediction significantly low as the graph prompts learn task-specific knowledge?\n\nDespite graph prompts capturing the task-specific knowledge, they are learned independently for each task and are not compatible with other tasks. Without the guidance of task identification, node classification is accomplished by concatenating the class probabilities of the test sample for all tasks and choosing the class with the highest probability as the predicted class. Specifically, assume there are $T$ tasks and each task contains $C$ classes, the predicted class of a test sample can be formulated as $c = \\arg \\max (c_1, c_2, \\ldots, c_{T \\times C})$. Suppose the test sample comes from task $i$, the incompatibility between the test sample and prompts from different tasks ($j, j\\neq i$) results in the class of the test sample being biased to one class of task $j$ with an extremely high probability. As a result, the class of the test sample cannot be predicted correctly.\n\n\n\n>**Questions #4/Weaknesses #1 and #3:** Explain the performance of TPP with the size of graph prompts and discuss the task prediction using all node attributes.\n\nIn our experiments, each task contains 2 classes (i.e., $C=2$) of nodes and we reported the performance of TPP with different sizes of the graph prompts in Figure 4. The figure shows that the performance of TPP increases quickly from $k = 1$ to $k = 2$ and remains stable for $k > 2$. We attribute this phenomenon to the intuition that the number of learnable tokens in graph prompts with a maximum number of $C$ is often sufficient to instruct the backbone to perform subsequent tasks conditionally. To further evaluate this intuition, we set the number of classes in each task to three ($C=3$) and report the performance of TPP with varying sizes of prompts in the following table. We can see that the performance becomes stable when $k=2$ and $k=3$ for CoraFull and Arxiv respectively, which supports our intuition.\n\n```\nTable A2. The average results with different sizes of the graph prompts when each task consists of nodes from three classes.\n```\n|Datasets|1|2|3|4|5|6|\n|---|---|---|---|---|---|--|\n|CoraFull|48.9|88.0|89.3|90.2|91.0|91.2|\n|Arxiv|64.3|72.2|75.9|76.1|77.0|76.7|\n\nFor task prediction by averaging all the node attributes as the task prototypes, it can also achieve good task prediction for most of the datasets (please see the results with the smoothing step set to zero in our response to the Weakness \\#4 of Reviewer \\#3), but it is not as effective as our proposed TP method. This may be attributed to various situations where this simpler alternative approach fails to work. For example, it cannot distinguish different tasks that may have distinct node attributes but have similar averaged attribute-based prototypes. Moreover, neglecting the graph structure would also result in failures in various other cases, e.g., when different tasks share similar node attributes but have different graph structures. In contrast, the proposed method can address all these cases as shown in Eq.(7). \n\n\n\n>**Questions #5/Weaknesses #2:** Include clear definitions of three categories of methods for graph continual learning and the descriptions of baselines.\n\nExisting GCL methods can be roughly divided into three categories, i.e., regularization-based, parameter isolation-based, and data replay-based methods. We will include more detailed definitions of these categories and the descriptions of the baselines in the revision.", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:
Dear all reviewers,

Thank you very much for the time and effort in reviewing our paper, and for the constructive and positive comments. Our rebuttal consists of two parts: **Global Response** where we address the shared concerns from two or more reviewers and **Individual Response** where we provide a detailed one-to-one response to address your questions/concerns individually.

>**Global Response to Shared Concerns**: The performance of TPP with different task formulations.

For the task formulation in our experiments, we set each task to contain two different classes of nodes and follow the commonly used task formulation strategy in [Ref1] to have fair comparisons with the baselines. Specifically, given a graph dataset with many 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 the following table, we report the average performance of the TPP and the Oracle Model with different task formulations. 
```
Table A1. Results of average performance of TPP and Oracle Model on datasets with various task formulations.
```
|Task Formulation | Method | CoraFull | Arxiv | Reddit | Prodcuts|
|----|----|----|----|----|----|
|Ascending Order (Reported)| TPP| 93.4|85.4|99.5|94.0|
|Ascending Order (Reported)| Oracle Model|95.5|90.3|99.5|95.3|
|Descending Order|TPP|94.5|85.9|99.4|93.9|
|Descending Order|Oracle Model|96.1|91.6|99.5|94.7|
|Random Order|TPP|94.8|86.9|99.5|85.9|
|Random Order|Oracle Model|95.3|91.3|99.7|86.8

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 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, de-biased learning is required. 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 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 datasets.


As for **Individual Response**, we have provided a detailed one-by-one response to answer/address your questions/concerns after the post of your review.

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

Best regards,

Authors of Paper 8497

**References**

- [Ref1] CGLB: Benchmark Tasks for Continual Graph Learning. NeurIPS 2022 Datasets and Benchmarks Track.

Meta-review: 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.
Decision: Accept (poster)