A Selective Learning Method for Temporal Graph Continual Learning

We greatly appreciate the reviewer's efforts in reviewing our paper. We thank the reviewer for recognizing our comprehensive coverage of the problem and method, detailed analysis and experiments, and clear presentation. Our responses to the comments on motivation, problem setting, and experiment are presented below:

Problem Setting and Motivation

W1: More concrete TGCL application examples are preferred to enhance the motivation.

Reply: Please kindly refer to our reply to Reviewer bJ1k Q1.

---

W2,Q1,Q2: The problem setting is not clear enough, like the availability of old class data in new periods and whether nodes change their labels.

Reply: We thank the reviewer for highlighting the need for a clearer explanation of our problem setting. Below, we provide the necessary clarification:

In our setting, consider a temporal graph $G_{N-1}$ at period $N-1$, whose node classes form the set $Y_{old}$. As the graph evolves into $G_N$ at the next period, new labels $Y_{new}$ emerge and bring in new nodes. At the same time, nodes from $Y_{old}$ also appear in $G_N$, but their data distribution is different from $G_{N-1}$ due to temporal and structural changes. Additionally, we assume that each node retains a fixed class label across time. In our paper, we illustrated this setting in Fig. 6 at Appendix A.

This reflects real-world dynamics such as user behavior graphs, where new users join over time and existing users remain active. Here, the node classes may correspond to behavior types, with new types emerging while old ones continue to recur. And user behavior is often persistent, with users maintaining their behavior types over time.

---

O1: Why is subset selection necessary for model training?

Reply: The subset selection and learning is necessary in three key points:

1. Efficiency: Replaying all previously seen data is computationally expensive. Subset selection significantly reduces the training time while maintaining competitive performance, as also evidenced in our comparison against Joint training in Tab. 2.

2. Effectiveness: Among various continual learning strategies, subset replay has consistently shown strong performance in preserving prior knowledge. Our experiments in Tab. 2 support this finding, where subset-based methods (Last 6 lines) are generally better than non-subset methods (LwF and EWC).

3. Generality: Our selection method is model-agnostic and can be easily applied to a wide range of temporal graph learning architectures, making it flexible and future-proof.

---

Experiment

O2: Comparison with more SOTA continual learning baselines.

Reply: We add a SOTA graph continual learning method TACO [1], which learns a coarsened old-class graph at a new period to achieve efficient update. We perform better because their coarsening procedure overly simplifies the evolving old-class distribution at a new period.

[1] NIPS 2024 - A TOPOLOGY-AWARE GRAPH COARSENING FRAMEWORK FOR CONTINUAL GRAPH LEARNING

---

Experiment Deaign and Analysis: The data segmentation approach requires clarification and experiments on a smaller training data ratio are suggested.

Reply: Our segmentation strategy follows a standard time-based approach widely adopted in the graph continual learning literature. Importantly, we address a common limitation in prior work by explicitly modeling the reappearance of old-class nodes in later periods, which better reflects real-world temporal dynamics where class distributions evolve over time.

To validate that training data ratio does not affect our conclusion, we conduct experiments on a lower train ratio of train/val/test = 60%/20%/20%. Results show that fewer training data reduces the overall model performance, yet our method still achieves the best performance over other baselines.

---

Q3: Why are the AP values below 0.15 in Tab. 2?

Reply: The AP values in Table 2 are below 0.15 primarily due to the challenging nature of our experimental setting:

1. Class Imbalance: The node classes in our datasets are imbalanced (from $10^3$ to $10^5$ in Yelp), which naturally suppresses the achievable AP scores.

2. Class-Incremental Evaluation: We adopt a single unified classifier to classify all nodes across time, rather than training separate classifiers per class. This setting, known as class-incremental learning in the continual learning literature, is more realistic for deployment but significantly more challenging.

Despite the lower absolute values, this setting provides a fair and rigorous evaluation in realistic, imbalanced scenarios.

We greatly appreciate the reviewer's efforts in reviewing our paper. We thank the reviewer for recognizing our novelty, sound theory, and good presentation. Our responses to the comments on motivation and more comprehensive experiments are presented below:

Q1: Clarify the motivation, especially on why using graphs to handle the proposed tasks.

Reply: We appreciate the suggestions on enhancing our motivation. To directly validate that TGCL method is necessary to address our task, we add a naive MLP backbone using only word embeddings as input (with parameter size matched to TGAT), which is also a common practice in GNN research.

We compare MLP with TGNN backbones (TGAT & DyGFormer) on Amazon using Joint (full-data training), Finetune (new-class-only training), and LTF (ours). The AP results show that the MLP backbone performs significantly worse than TGNNs (TGAT or DyGFormer), demonstrating the necessity of graph-based models for the task.

While our datasets are used as proof-of-concept benchmarks, they are carefully chosen to reflect key challenges in real-world settings. To further reinforce our motivation, we present two additional application scenarios where TGCL is highly applicable:

1. Attack Identification in Cybersecurity

   • Nodes: Network entities (e.g., IP addresses, devices)
   • Edges: Communication or interaction logs
   • Classes: Cyberattack types (e.g., phishing, ransomware, DDoS)
   • Description: Attack patterns evolve continuously, with new attack types emerging and existing ones adapting to evade detection. Modeling interactions over time is crucial to understanding and classifying these behaviors.

2. Illegal Behavior Detection in Social Networks

   • Nodes: Users
   • Edges: Historical interactions (e.g., messaging, reposting)
   • Classes: Misconduct types (e.g., hate speech, fraud, misinformation)
   • Description: As user behavior evolves and social norms shift, new categories of harmful behavior emerge, often in subtle and adaptive ways. Capturing both user history and temporal interactions is essential for effective detection.

Q2: Evaluation over longer sequences of incremental updates

Reply: We thank the reviewer for highlighting the importance of learning on a longer-sequence dataset. To evaluate the scalability of our approach in settings with significantly more incremental updates and larger scale, we constructed a new dataset, Reddit-Large, consisting of 344,630 nodes, 4,962,297 edges, and 16 time periods, with 2 new classes introduced per period (32 classes in total). Reddit-Large represents a substantial expansion over our previous largest dataset, Yelp, featuring 3× more time periods, 2× more classes, 20× more nodes, and 2× more events.

Our results below demonstrate that our method remains robust and effective as the task complexity increases.

---

Q3: More analysis on efficiency versus accuracy trade-off

Reply: Please kindly refer to our reply to Reviewer CBnU W1.

---

Q4: Additional experiments on other backbone models and temporal graph tasks

Reply: We thank the reviewer's suggestions on further validating our method. Our responses are presented below:

1. More Backbones:
   To further assess the generality of our method, we incorporate GraphMixer [1]—an MLP-based model designed for temporal graphs—as an additional backbone. The experimental results show that our method continues to outperform existing baselines even with this new architecture, further supporting the robustness and versatility of our approach.

[1] ICLR 2023 Do We Really Need Complicated Model Architectures For Temporal Networks?

2. Other Temporal Graph Tasks:

   The Temporal Graph Benchmark raises link prediction and node property prediction tasks. These settings also exhibit continual learning characteristics—e.g., in user–item interaction networks, new items appear over time, requiring the model to connect users to new items while remembering their old preferences.

   While these tasks can often be framed as binary classification between node pairs over time, adapting our framework to such settings would require task-specific modifications. Given that all prior graph continual learning studies have centered on classification tasks, we believe extending our method to prediction tasks is an important but non-trivial direction that goes beyond the current paper’s scope. We have discussed this as part of future work in Appendix M.

We greatly appreciate the reviewer's efforts in reviewing our paper. We thank the reviewer for recognizing our novel problem, well-developed method, and rigorous experiments. Our responses to the valuable feedback are presented below:

W1: Given various efficiency improvements in the proposed method, the trade-off to effectiveness is still unclear.

Reply: Our approximation techniques greedy selection algorithm, partitioning strategy, and regularization set simplification are crucial for making the training and selection phases computationally feasible. Without these approximations, it would be practically impossible to run the experiments under limited resources.

• Greedy selection avoids exhaustive searches which have factorial time complexity, making them intractable for real-world graphs.
• Partitioning, as analyzed in the paper, significantly reduces memory requirements. Without it, subset selection could demand over 100 GB of RAM, which is prohibitive in most settings.
• During training, we simplify the regularization dataset from $G^{old}_N$ (full old-class data) to a subset $G^{sim}_N$ $(|G^{old}_N| >> |G^{sim}_N|)$, greatly reducing the regularization loss complexity. This simplification is necessary to prevent GPU memory overflow and failed experiments.

Despite these constraints, we conducted further analysis to empirically characterize the trade-off between effectiveness and computational efficiency by varying the sizes of selected subsets $m$ (for $G_N^{sub}$) and $m'$ (for $G_N^{sim}$). The backbone model used is DyGFormer, and the dataset is Yelp.

Effect of Varying $m$: $G_N^{sub}$ is the major carrier of old-class knowledge, a larger $m$ will improve its knowledge quality yet takes more training time. Below experiments validate our claim, where increasing $m$ improves average precision (AP) and linearly increasing the training time.

Effect of Varying $m'$: $G_N^{sim}$ approximates the distribution of $G_N^{old}$, which helps generalize the learnt knowledge from $G_N^{sub}$. A larger $m'$ leads to a better distribution approximation at the cost of more training time. Experiments support our claim on $m'$: larger values improve AP at the cost of longer training time, again approximately linear due to the $O(mm')$ complexity of the regularization loss.

It is also worth noting that although our method achieves the best results among all baselines, this comes with an additional time cost due to the regularization term. However, since our selection and regularization modules are independent, users with stricter efficiency requirements can disable the regularization component. Our selection-only setup still achieves state-of-the-art performance while maintaining comparable time costs to other replay-based baselines.

---

Q1: Why use MSE instead of Cross-entropy for classification loss?

Reply: We employ MSE loss due to its strong theoretical alignment with domain adaptation theory. The key quantity in this framework, i.e., the $\mathcal{H} \Delta \mathcal{H}$ divergence measures disagreement between hypotheses[1]. MSE naturally captures this disagreement by penalizing squared geometric distances between model outputs. In contrast, cross-entropy focuses on prediction confidence (log-probabilities), making it less sensitive to inter-hypothesis disagreements. Additionally, MSE’s bounded gradients lead to more stable optimization and better adherence to generalization bounds in domain adaptation.

---

Q2: What are the limitations of the proposed method?

Reply: Our method is limited in two points:

1. Task Scope: Our current work focuses on the node classification task within temporal graphs. While this is an important and under-explored area, it is equally critical to address the continual learning problem on other key temporal graph tasks such as link prediction, which may pose different challenges to our approach. We discussed this limitation in Appendix M.

2. Class Dynamics Assumption: We assume that each node is associated with a single, static class label throughout its lifetime. However, node labels can also change over time in real life. For example, in epidemic transmission networks, an individual may transition between different states (e.g., infected to recovered), which our current formulation does not accommodate. Capturing such class-switching behavior is also important.

---

Q3: More repeated experiments are needed.

Reply: We agree with the reviewer that more repeated experiments are needed to address concerns about the influence of randomness in the results. We will conduct additional experiments and report the results in the final version of the paper.

We appreciate the reviewer's efforts in reviewing our paper. We thank the reviewer for recognizing our novel learning paradigm and the good correspondence between theory and experiments. Our responses to the valuable feedback are presented below:

Q1: Experiments on datasets with a longer duration of periods and larger scales are expected to reflect real-world scenarios.

Reply: We appreciate your suggestion on applying a more realistic dataset with longer periods and larger scales. Our datasets are mined and constructed by ourselves, and we have prepared a larger dataset Reddit-Long, which has the duration of 180 days per period, 558,486 nodes, 5,323,230 edges, and 24 classes evenly added over 4 periods. This is larger than Yelp (our largest dataset) and has a longer duration than Reddit and Amazon. Due to the larger scale of data, we will report the comparison results later in this rebuttal period.