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

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.

Questions #1: Point out the key differences of task prediction between image and graph more clearly.

The 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.

Questions #2/Weaknesses #3: Include the comparisons between graph prompting and training separate GNNs for each task.

In 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.

Table A1. Additional parameters and the average performance of the proposed graph prompting and task-specific models.

The 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.

Questions #3: Why is the performance of TPP without task prediction significantly low as the graph prompts learn task-specific knowledge?

Despite 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.

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.

In 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.

Table A2. The average results with different sizes of the graph prompts when each task consists of nodes from three classes.

For 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).

Questions #5/Weaknesses #2: Include clear definitions of three categories of methods for graph continual learning and the descriptions of baselines.

Existing 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.

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.

Weaknesses #1: TPP is similar to L2P [Ref2].

Although our TPP and L2P both adopt prompting for class-incremental learning, several major differences highlight our novelty.

• 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.
• 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.
• 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.

Weaknesses #2.1 Why the GCN-based OOD detector (OODCIL) underperforms compared to the proposed TP and baselines.

We 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.

As 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.

Table A1: The average performance of OODCIL and TPP with different task prediction methods.

Note 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.

Weaknesses #2.2: Accuracy of task prediction with different task formulations.

The 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.

Table A2: The accuracy of task prediction with other task formulations.

Weaknesses #3: Absence of source code.

The source code will be released upon acceptance.

Weaknesses #4: Accuracy of TP with varying steps of Laplacian smoothing.

In 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.

Table A3. The accuracy of task prediction with different Laplacian smoothing steps.

References

• [Ref2] Learning to Prompt for Continual Learning, CVPR 2022

Thank you so much for the insightful comment.

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

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

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

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

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

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

Table A5. Task prediction accuracy of three different methods.

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.

Weaknesses #1/Questions #1: Not clear experimental setup and the performance of TPP with different task formulations.

Please refer to our reply in Global Response to Shared Concerns in the overall Author Rebuttal section above for this concern.

Weaknesses #2/Questions #2: What is the relationship between identifying the tasks and overcoming the forgetting problem?

In 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.

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.

Weaknesses #1: The problem definition requires some clarification.

In 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.

During 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.

Weaknesses #2: Why these datasets should be considered into the GCIL setting?

Following [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.

Question #1: The performance of TPP with different task formulations.

Our 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.

References

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