N-ForGOT: Towards Not-forgetting and Generalization of Open Temporal Graph Learning

Thank you for your insightful comments. We have carefully revised the manuscript to address the concerns you raised regarding unclear writing in questions 5, 6, 7, 8, and 9. We appreciate your feedback as it has significantly contributed to improving the clarity and quality of our paper.

Comment 1: Thanks for your mention, we have included these two papers in the related work section. These works innovatively employ condensed graphs as replay data to prevent forgetting. The condensed graphs are significantly smaller than the original, yet they consist of synthetic node representations that preserve the complete informational content of the original structures.

Comment 2: Thank you for your suggestion. Open Temporal Graph Learning (OTGL) indeed stems from Graph Continual Learning (GCL) but is specifically tailored to address the unique challenges associated with temporal graphs. We have updated the 'Related Work' section of our manuscript to clearly delineate this.

Specifically, in OTGL, the issues of distribution shift and catastrophic forgetting are more complex and pronounced compared to traditional GCL due to the dynamic nature of temporal graphs. Specifically, temporal inconsistencies result in class characteristics that evolve over time, significantly complicating the preservation of previously learned information and intensifying the problem of catastrophic forgetting. Moreover, OTGL must address distribution shifts across multiple domains, a challenge that is uniquely demanding compared to the more static scenarios encountered in GCL. These nuances have been detailed in the Introduction section of our manuscript.

Comment 3: Thank you for your suggestion. We acknowledge the importance of including more recent continual graph learning methods for comparison. Accordingly, we will consider incorporating the newly published works, DeLoMe [1] and CaT [2], into our baseline comparisons to provide a more comprehensive analysis. We will update the experimental results accordingly in the final version of the manuscript. Notably, DeLoMe [1], as the latest published paper, introduces a novel lossless memory replay approach that captures the holistic information of entire graphs. This method distinctively utilizes gradient-based graph condensation methods in continual graph learning, moving beyond traditional data sampling techniques to preserve more comprehensive knowledge from previous data. This innovative strategy represents a significant advancement in addressing the challenges of catastrophic forgetting in graph neural networks.

Comment 4: Graph continual learning aims to continuously learn from new tasks in a sequence without needing to retrain all previous data. The goal is to maintain overall performance by integrating new knowledge while minimizing the forgetting of previously acquired knowledge. In this field, there is no strict prohibition against accessing data from previous tasks and classes. In fact, several studies [3][4] employ replay-based methods in graph continual learning, which selectively retrain data from previous tasks during the training of current tasks.

[1] Niu C, Pang G, Chen L. Graph Continual Learning with Debiased Lossless Memory Replay[J]. arXiv preprint arXiv:2404.10984, 2024.

[2] Liu, Y., Qiu, R., & Huang, Z. (2023, December). Cat: Balanced continual graph learning with graph condensation. In 2023 IEEE International Conference on Data Mining (ICDM) (pp. 1157-1162). IEEE.

[3] Kaituo Feng, Changsheng Li, Xiaolu Zhang, and Jun Zhou. Towards open temporal graph neural networks. In The Eleventh International Conference on Learning Representations, ICLR, 2023.

[4] Tian, Z., Zhang, D., & Dai, H. N. (2024). Continual Learning on Graphs: A Survey. arXiv preprint arXiv:2402.06330.

Comment 1: Thank you for your question. Our work adopts the open temporal graph learning framework as defined in "Towards Open Temporal Graph Neural Networks (OTGNet)" [1], a method highlighted among the top 5% at ICLR 2023. This formulation is grounded in continual graph learning principles [2], where each task incorporates 'unseen classes' that are new relative to previous tasks, thereby expanding the model's predictive capacity over time. However, this setting is distinct from the 'open-set' scenario in the Open-Set Recognition problem [3], where the model encounters classes at test time that were completely unseen during training

As illustrated in Figure 1(a), the exploration of temporal graphs progressively introduces new classes over time. These newly emerging classes, compared to the historical data, expand the prediction space and challenge the model to adapt continuously. For example, according to Figure 1(a), consider a scenario where Task 1 involves graph $\**G**_ 1$ with a corresponding label set $\\mathbf{Y}_ 1$, and Task 2 introduces a graph $\**G**_ 2$ with label set $\\mathbf{Y}_ 2$. The label sets are disjoint and $\**G**_ 2$ does not overlap $\**G**_ 1$. When task 2 arrives, the model is trained on the new graph $\**G**_ 2$, but it is also expected to maintain its ability to predict across the combined label sets of both tasks: $\\mathbf{Y}_ 1 \\cup \\mathbf{Y}_ 2$.

The main challenge of open temporal graph learning is to prevent catastrophic forgetting while continuously learning from new tasks in a sequence without needing to retrain previous data. Beyond this, our approach aims to balance knowledge retention from past data with effective adaptation to evolving data distributions. Based on the results theoretically analyzed in Theorem 1, we have proposed two plug-in modules specifically designed to address both forgetting and distribution shift problems.

Comment 2: Thank you for your thoughtful question. The dynamic graph distribution shifts mentioned in our paper encompass more than just shifts in class labels over time; they also include changes in node features, interaction frequencies, and overall graph structure.

In this work, we quantify the distribution shifts in open temporal graphs through two primary types: structure shift and temporal shift (as mentioned in lines 068-070). Structure shifts arise from differences in graph structures between old and new data, such as the emergence of new interactions or changes in connectivity patterns. Temporal shifts are driven by continuous evolution, including changes in the descriptions of classes and alterations in node features over time.

We introduce temporal Weisfeiler-Lehman (WL) subtree patterns to effectively model these two types of distribution shifts into our proposed method. As outlined in Definition 1, we have separately proposed the structure and temporal components within the temporal WL subtree patterns. These patterns form the foundation for the LTDO module, which provides a computationally efficient approach for quantifying and adapting to multi-domain distribution shifts, ensuring robustness and adaptability in open temporal graph learning.

[1] Kaituo Feng, Changsheng Li, Xiaolu Zhang, and Jun Zhou. Towards open temporal graph neural networks. In The Eleventh International Conference on Learning Representations, ICLR, 2023.

[2] Yuan, Q., Guan, S. U., Ni, P., Luo, T., Man, K. L., Wong, P., & Chang, V. (2023). Continual graph learning: A survey. arXiv preprint arXiv:2301.12230.

[3] Salehi, M., Mirzaei, H., Hendrycks, D., Li, Y., Rohban, M. H., & Sabokrou, M. (2021). A unified survey on anomaly, novelty, open-set, and out-of-distribution detection: Solutions and future challenges. arXiv preprint arXiv:2110.14051.

Comment 4: Thank you for highlighting this point. There is no constraint for $\\alpha$ and $\\beta$. In our experiments, both hyperparameters $\\alpha$ and $\\beta$ are settled to 1. To provide clear insights into the impact of these hyperparameters, we conducted an additional ablation study, with the results detailed in the Table below ( A better view is available in Appendix E.5). The findings show that the model achieves greater robustness when similar weights are assigned to each plug-in module in the final loss function calculation. Both plug-in modules are significant for managing the balance between retaining previous data distributions and adapting to new incoming data, thereby improving overall model robustness. We have included this in the experiment section.

Table: Hyperparameters Ablation Study

Thank you for your insightful feedback. We truly appreciate the care and attention you have given to our paper, and the detailed suggestions you have provided. We hope that our response has addressed your concerns. We will include the above discussion in the final version of our manuscript. We sincerely appreciate your reconsideration and kindly ask you to re-evaluate our work in light of these clarifications and additions.

Thank you very much for your meticulous review of our paper. We have carefully revised all the notations and writing details as per your suggestions. We truly appreciate your valuable insights. In the following, we will address each of your comments individually.

Comment 2: Thank you for your insightful comment. Theorem 1 is foundational to our method. This bounding robustly justifies the design of our two plug-in modules: the Temporal Interclass Connectivity Regularization Module (TICR), which minimizes forgetting, and the Localized Temporal Graph Discrepancy Optimization (LTDO), which manages discrepancies between task distributions. We will make sure to clarify these connections more explicitly in the paper. Detailed explanation as below:

$$\\mathcal{R}_ {\\mathbb{G}_ k}(f_ k(\\theta_ k)) \\leq \\hat{\\mathcal{R}}_ {\\mathbb{G}_ {1:k-1}}(f_ k(\\theta_ k)) + div_ {\\mathcal{H}}(\\mathbb{G}_ {1:k-1}, \\mathbb{G}_ {k}) + \\quad \\sqrt{\\frac{2d}{m} \\log\\left(\\frac{em}{d}\\right)} + \\sqrt{\\frac{1}{2m}\\log\\left(\\frac{1}{\\delta}\\right)} + \\xi$$

To elaborate, Theorem 1 derives from the generalization error $|\\mathcal{R}_ {\\mathbb{G}_ k} - \\mathcal{R}_ {\\mathbb{G}_ {1:k-1}}|$. Specifically, this error measures the deviation between the performance on the current task $\\mathbb{G}_ k$ and the previous task $\\mathbb{G}_ {1:k-1}$. Based on Theorem 1, minimizing the terms on the right-hand side reduces this generalization error, thereby optimizing the population risk for the current task $\\mathcal{R}_ {\\mathbb{G}_ k}(f_ k(\\theta_ k))$ (in the left-hand side of Theorem 1's equation).

Accordingly, we focus on minimizing $\\hat{\\mathcal{R}}_ {\\mathbb{G}_ {1:k-1}}(f_ k(\\theta_k))$ and the divergence $div_{\\mathcal{H}}(\\mathbb{G}_ {1:k-1}, \\mathbb{G}_ {k})$ (key terms on the right-hand side of Theorem 1's equation), leading to the corresponding proposal of two specific plug-in modules: TICR and LTDO.

Comment 3: Thank you for your suggestion. We calculate and present the task-to-task distributional shifts, computed by Maximum Mean Discrepancy (MMD), in the following Table. These results represent the average outcomes derived from the MMD calculations on the learned node representations. For further details, we will provide log files as supplementary material.

Furthermore, we have depicted the distributional shifts across different tasks using a heatmap to visually represent the structural and temporal shifts [1], which is illustrated in Figure 1(b). These shifts were quantified using the Amazon dataset. For comprehensive transparency, detailed calculations will be included in the accompanying code implementation.

The data presented in the following table and the heatmap (Figure 1(b)) clearly illustrate the inherent challenges posed by structural and temporal shifts in open temporal graph learning. These visualizations show how these shifts manifest across tasks, with MMD values highlighting the extent of distributional changes as new tasks are introduced. In reference to the ablation study shown in Table 2, we found that the LTDO module significantly enhances the model's effectiveness and robustness across four datasets, particularly in the context of the distribution shifts noted.

Table: Task-to-task distributional shifts (measured by MMD)

[1] Gui, S., Li, X., Wang, L., & Ji, S. (2022). Good: A graph out-of-distribution benchmark. Advances in Neural Information Processing Systems, 35, 2059-2073.

We hope that these additional experiments and clarifications have sufficiently addressed your concerns. Please let us know if you have any further questions or require additional information.

Thank you once again for your valuable time and input.

One immediate strategy to address the trade-off between efficiency and accuracy is the adaptive application of the LTDO module and traditional MMD-based methods according to the task's graph size. As demonstrated in Figure 5, the computational overhead of traditional MMD-based methods increases significantly with the number of nodes, showing that a key factor affecting the time cost is the size of the dataset.

For tasks with larger graph sizes, N-ForGOT can adaptively deploy the LTDO module to ensure efficiency without substantially compromising accuracy. Specifically, we can design a hyperparameter that dynamically adjusts the proportion of traditional and LTDO methods based on the dataset size. For instance, through a threshold-based mechanism, the model could prioritize traditional MMD-based methods for smaller graph sizes below a certain threshold to maximize accuracy. Conversely, for larger graph sizes above this threshold, the proportion of the LTDO module could be increased to enhance computational efficiency. This adaptive approach ensures an optimal balance between efficiency and accuracy, tailored to the specific demands of each task.

Another strategy involves optimizing the structure of temporal Weisfeiler-Lehman (WL) subtree patterns by adjusting their depth and the number of nodes at the leaf level. Utilizing relatively smaller temporal WL subtree patterns could enhance the efficiency of the LTDO module, whereas more comprehensive patterns might improve its accuracy. We can consider applying methods like pruning to refine the structure of these temporal WL subtree patterns further. For example, selecting more significant nodes as leaf nodes could allow the LTDO module to achieve a better balance between accuracy and efficiency.

Thank you for your insightful comments. We will include the discussion in our final manuscript. We will also carefully consider the weaknesses you have highlighted, as they offer valuable insights for our future work.