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

Problem

• GCIL omits task IDs during inference, so classes from different tasks obstruct one another and performance typically trails task-incremental learning.Previous-task accuracy is especially affected, and existing methods remain limited in handling inter-task separation.Source: §1 · p. 2

Task profiling

• Laplacian smoothing profiles each graph task with a prototype whose within-task embeddings converge while different tasks remain distinct through graph structure and node attributes.This graph-specific profiling is designed for non-Euclidean data unlike prior Euclidean task-identification methods.Source: §1 · p. 2

Graph prompting

• Task-specific prompts learned with one frozen pre-trained GNN capture discriminative knowledge for each task without replaying previous data.Using a separate prompt and classifier per task avoids continual model updating and catastrophic forgetting.Source: §1 · p. 2

Main results

• At least 18% higher average CIL accuracy than state-of-the-art methods, while remaining fully forget-free across four GCIL benchmarks.TPP also exceeds joint training on all tasks simultaneously by a large margin.Source: §1 · p. 3

Task profiling

• 100% task ID prediction accuracy across all four datasets eliminates the inter-task class separation issue in GCIL.Task prototypes enable classification within the predicted task’s class space rather than across all learned tasks.Source: §1 · pp. 2–3

Graph Continual Learning

• Regularization, parameter-isolation, and replay-based GCL methods mitigate forgetting but still struggle with inter-class separation when task IDs are unavailable.Replay methods can improve forgetting performance, but they retain the inter-task separation challenge.Source: §2 · p. 3

Task Identification

• Existing task-identification methods use separate networks, entropy, or OOD detection, but their Euclidean-data design does not suit graph task identification.TPP instead uses Laplacian smoothing and graph task prototypes to exploit graph structure and node attributes.Source: §2 · p. 3

Prompt Learning

• Prompt learning adapts frozen pre-trained models with task-specific prompts, but prior work had not addressed GCIL because task IDs and suitable all-task pre-trained GNNs are unavailable.TPP trains a GNN on the first task, then combines graph prompts with task ID prediction for GCIL.Source: §2 · p. 3

3.1 The GCIL Problem

• GCIL must classify samples across all task classes without task IDs while preserving performance on earlier graph tasks.Each task contains unique classes, and learning task t accesses only its current graph data.Source: §3.1 · p. 4

3.2 Overview of The Proposed TPP Approach

• TPP decomposes GCIL into task identification followed by within-task classification, using the predicted task to retrieve its prompt and classifier.The approach learns task knowledge separately, preventing task interference during training.Source: §3.2 · p. 4, Figure 2 · p. 4

3.3 Laplacian Smoothing-based Task Profiling for Graph Task ID Prediction

• Laplacian smoothing averages graph-structured node information into task prototypes, whose nearest-prototype comparison predicts the test graph’s task ID.Training prototypes are stored in a prototype pool, and a test prototype is matched using Euclidean distance.Source: §3.3 · pp. 4–5
• With sufficiently large smoothing, same-task prototypes converge while structural and attribute differences make prototypes from different tasks distinct.Theorem 1 supports convergence for the correct task, whereas Theorem 2 attributes cross-task separation to graph degree and attribute differences.Source: §3.3 · p. 5

3.4 Graph Prompt Learning for GCIL

• Each task receives a small learnable prompt and MLP head optimized through a frozen GNN, producing a separate classification model without replay.The backbone is learned once on the first task, while prompts and heads store subsequent task-specific information with minimal parameters.Source: §3.4 · p. 6, §3.5 · p. 6

3.5 Training and Inference in TPP

• During inference, TPP constructs a test prototype, predicts its task by querying the stored prototype pool, and applies the corresponding prompt and head.This sequence is repeated for each test graph after task-specific profiles, prompts, and classifiers have been stored.Source: §3.5 · p. 6

4.1 Main Results

• TPP achieves AF of zero across all four datasets and outperforms the best competing method by over 18% in average AA.It also outperforms the Joint baseline because it addresses both catastrophic forgetting and inter-task class separation.Source: §4 · p. 7, §4.1 · p. 8
• TPP consistently outperforms existing methods because accurate task ID prediction enables task-specific classification and graph prompts preserve task knowledge.The task ID module converts GCIL into classification within the predicted task’s class space, while prompting supports intra-task separation.Source: §4.1 · p. 8
• Adding the task ID module substantially improves both AA and AF for TWP and DeLoMe without changing their training procedures.The module is applied only at inference, where it restricts classification to the predicted task.Source: §4.1 · p. 8, Table 2 · p. 8

4.2 Ablation Study

• Removing task ID prediction makes TPP barely effective on all four datasets because independently learned prompts produce non-normalized probabilities across tasks.Without task identification, probabilities from different task-specific prompts are difficult to compare directly.Source: §4.2 · p. 8, Table 3 · p. 9
• The full TPP model performs best across datasets, while either graph prompts or classification heads improves over the unadapted backbone.The graph-prompt-only variant outperforms the classifier-only variant, indicating stronger task-specific adaptation from prompts.Source: §4.2 · pp. 8–9
• TPP accuracy rises quickly from one to two prompt tokens and remains stable for prompt sizes above two.This supports effective adaptation with small task-specific prompts and transferability of the frozen GNN backbone.Source: §4.2 · p. 9, Figure 4 · p. 9
• Laplacian smoothing predicts task IDs perfectly across all tasks and datasets, whereas node-feature-only profiling fails when tasks have similar node attributes.Node features alone nonetheless perform highly on Arxiv and Reddit, where task attributes are more discriminative.Source: §4.2 · p. 9, Figure 4 · p. 9
• TPP remains comparable to the Oracle Model under ascending, descending, and random task formulations, although both methods drop on imbalanced Products tasks.The authors attribute the Products drop to balanced-accuracy sensitivity and leave debiased learning for future work.Source: §4.2 · pp. 9–10, Table 4 · p. 10

5 Conclusion

• TPP uses Laplacian smoothing to construct graph task prototypes that support accurate task ID prediction from graph structure and node attributes.The paper states that same-task prototypes become nearly identical while different-task prototypes remain distinct under the theoretical analysis.Source: §5 · p. 10
• Graph prompting stores within-task information in small task-specific prompts, requiring one GNN training stage and no replay buffer.The resulting model is described as memory-efficient, replay-free, and forget-free.Source: §5 · p. 10
• Experiments show that TPP is fully forget-free and significantly outperforms state-of-the-art GCIL baselines.These conclusions are reported across the paper’s four benchmark datasets.Source: §5 · p. 10

A Proof of Theorems

• Large-step Laplacian smoothing makes test and training prototypes from the same task converge, enabling accurate task identification.The proof uses spectral convergence and the prototype construction to show their distance approaches zero.Source: A Proof of Theorems · p. 13
• Different tasks remain distinguishable because their task-prototype distance depends on differences in node degrees and node attributes.Theorem 2 formulates this cross-task distance using degree differences e and attribute differences ϵ.Source: A Proof of Theorems · p. 14
• Isolated nodes can violate the theorem’s assumption, so graph augmentation connects them to randomly selected non-isolated nodes before prototype construction.This augmentation makes the graph more connected and improves task prediction accuracy.Source: A Proof of Theorems · p. 14

B Details on Learning GNN Backbone

• The backbone is pretrained only on the first task with graph contrastive learning to obtain transferable node representations.Edge removal and attribute masking create two views whose same-node embeddings are pulled together while other-node embeddings are separated.Source: B Details on Learning GNN Backbone · pp. 14–15

C Algorithm

• For each task, the algorithm constructs a prototype, learns a graph prompt and classifier, and stores them for later inference.Training outputs one GNN, a prototype set, task prompts, and task classifiers.Source: C Algorithm · p. 15
• At inference, the test prototype selects a task, after which the corresponding prompt and classifier produce the node-class prediction.The selected prompt modifies node attributes before the shared GNN and task-specific classifier are applied.Source: C Algorithm · p. 15

• All methods use a two-layer SGC backbone with hidden dimension 256, 200 epochs per task, Adam, and default learning rate 0.005.Source: §D.1 · p. 15
• Graph contrastive pretraining uses edge-removal probability 0.2, attribute-masking probability 0.3, learning rate 0.001, 200 epochs, and temperature τ=0.5.Source: §D.1 · p. 15
• Experiments are implemented with PyTorch 1.10.0, DGL 0.9.1, OGB 1.3.6, and Python 3.8.5 on a Linux server with an RTX 6000 GPU.Source: §D.1 · p. 15

• Each task-specific OOD detector has C+1 classes, with the extra class representing data outside that task.Source: §D.2 · pp. 15–16
• OOD detectors use replay-buffer data as OOD examples for later tasks, while augmented graph data supplies OOD examples for task 1.Source: §D.2 · p. 16
• At inference, each detector’s class probabilities are weighted by one minus its OOD probability, and the globally largest resulting class probability is selected.Source: §D.2 · p. 16

D.3 Details on Datasets

• The benchmarks are CoraFull, Arxiv, Reddit, and Products, spanning citation, social, and product co-purchasing graphs with task-specific node classes and features.CoraFull has 70 classes, Arxiv has 40 subject areas, and Reddit and Products use community and product-network labels respectively.Source: §D.3 · p. 16

D.4 Descriptions of Baselines

• ERGNN stores representative nodes, while SSM, SEM, and CaT preserve or synthesize graph structure for replay-based continual learning.DeLoMe instead stores lossless prototypical node representations as memory.Source: §D.4 · p. 17

D.5 Evaluation Metrics: Average Accuracy and Average Forgetting

• Average accuracy measures performance across all learned tasks after the final task, whereas average forgetting measures how previous-task performance changes during continual learning.Source: §D.5 · p. 17
• Positive average forgetting indicates that learning the current task improves previous-task performance, and higher values of both metrics indicate better performance.Source: §D.5 · p. 17

Accuracy of task prediction with different task formulations

• Task prediction remains accurate under both numerically descending and random task orderings.Source: §D.6 · p. 17, Table 6 · p. 18

• TPP incurs a trivial inference-time overhead from task ID prediction but requires the smallest training time because it avoids replay memory and regularization terms.Table 8 compares total training and inference time on CoraFull against TWP, SSM, and DeLoMe.Source: Table 8 · p. 18

Comparison to Task-Specific Models

• The proposed graph prompting achieves performance close to task-specific models while introducing significantly fewer additional parameters across GCIL tasks.The comparison reports additional parameters and performance in Table 7.Source: §D.6 · pp. 17–18, Table 7 · p. 18

• The method trains a GNN backbone on the first task, freezes it, and separately optimizes graph prompts and classifiers for subsequent tasks.The backbone uses a two-layer SGC, while prompts have size k and classifiers are single-layer MLPs.Source: E Time Complexity Analysis · p. 18
• Although the backbone is frozen, forward and backward propagation remain necessary to optimize each task-specific prompt and classifier.Source: E Time Complexity Analysis · p. 18
• Its overall training complexity is linear in the nodes, edges, and node attributes involved across all graph tasks.The stated complexity combines first-task backbone training with per-task prompt and classifier optimization.Source: E Time Complexity Analysis · p. 18
• On CoraFull, TPP has the smallest training time because it avoids replay memory and regularization terms, while task ID prediction adds only trivial inference overhead.Source: E Time Complexity Analysis · p. 18