ON LEARNABILITY AND EXPERIENCE REPLAY METHODS FOR GRAPH INCREMENTAL LEARNING ON EVOLVING GRAPHS

Thank you for the feedback and comments. Please allow us to address and clarify the concerns as follows:

Q1. What does good $f$ mean in Theorem 2.3?

• In Theorem 2.3, the symbol $\mathcal{F}$, as defined in Section 2.1, represents the hypothesis space of the model, encompassing all possible parameters from the neural network. This is a standard notion employed in statistical learning theory.

Q2 & Q3. Retraining from scratch as a counter example and potential missing assumption in Theorem 2.3

Retraining from scratch is NOT a counterexample to Theorem 2.3, and we maintain that no essential assumptions have been overlooked for Theorem 2.3 to retain its validity.

• The implication of Theorem 2.3 lies in whether there exists a learning algorithm capable of training or updating the model in the prescribed incremental manner (as described in Section 2). Retraining from scratch stands apart as it does not align with the principles of incremental learning and, therefore, does not qualify as a counterexample to Theorem 2.3
• The objective of incremental learning is to devise an algorithm that achieves performance comparable to retraining from scratch, which is why we utilize it as a baseline for performance comparison in the empirical study.
• We intentionally omitted some minor technical details from Theorem 2.3, as indicated by our note that it is an informal version. The formal version is provided in the appendix. However, we do not believe we have overlooked any crucial assumptions for Theorem 2.3 to hold.

Q4. Why the proposed method can mitigate the structural shift? Isn’t this dependent on the data nature that we have no way to control?

We can not control structural shifts within the data but we can manage and mitigate the impact of structural shifts on the model's performance.

• The key concept underpinning our proposed approach to mitigating the effects of structural shifts is our replay strategy (as detailed in Section 3.2). This strategy employs the principle of importance reweighting, which works to reduce the distance between sample representations in the latent space. This approach is specifically engineered to counteract the adverse effects of structural shifts.

Q5. Does Theorem 2.3 contradict with graph unlearning literature [1,2]?

Theorem 2.3 does not contradict the graph unlearning literature.

• Graph unlearning and graph incremental learning represent two distinct problems, despite the presence of some shared terminology. Both research areas have extensive bodies of existing work. The objective of graph incremental learning is to update or train the model with new data without "forgetting" past knowledge. In contrast, graph unlearning seeks to remove specific target information from the model.
• Both the form and the objective of the learning algorithms sought by these two problems are different, and therefore, Theorem 2.3 does not contradict the graph unlearning literature.

Thank you once more for comments. We hope that our response has addressed your concerns and provided clarifications that further emphasize the significance and contributions of our work.

[1] Efficient Model Updates for Approximate Unlearning of Graph-Structured Data, Chien et al. ICLR 2023.

[2] Efficiently Forgetting What You Have Learned in Graph Representation Learning via Projection, Cong et al. AISTATS 2023.

Thank you again for the feedback on our paper. We hope that our responses have addressed your inquiries and concerns. If this is not the case, please inform us and we would be glad to engage in further discussion.

Thank you for the insightful feedback and comments. Please allow us to address and clarify the concerns as follows:

W1. the result can be traced back to cyclic dependencies of the node probabilities that are ultimately the contributors to the structural shift.

Our formulation and analysis do not neglect the "cyclic dependency of node probabilities" (dependency among the node distributions).

• A common approach for the theoretical analysis of graph neural networks (GNNs) is to formulate the problem from the perspective of ego graphs[2,3]. From the GNN perspective, this formulation provides sufficient information (input to the GNN) for inferring a target vertex and thus forms a Markov blanket. In this formulation, the dependency among node distributions is manifested by the shared underlying graph structure.
• In our paper, we embrace the ego-graph formulation and utilize the symmetric difference measure (defined in Section 2.2) to quantitatively capture and account for the dependency among different tasks or training sessions, which stems from the "cyclic dependency of node probability.”

In summary, our formulation and analysis does not neglect the "cyclic dependency of node probabilities" but rather adopts a common approach to formulate it differently for analytical purposes.

W2. Proof of Them 2.3 in the main paper

The decision to defer the proof of Theorem 2.3 to the Appendix is motivated by two main considerations:

• Space Constraint:

  • The impossibility result is just one of the two key contributions of this paper. We need to allocate space to describe the other contribution, which is our novel experience replay method tailored to address NGIL with structural shifts.

• Readability:

  • Proving Theorem 2.3 requires introducing additional formalism and definitions from statistical learning theory. This extra formalism can be demanding for some readers and may divert their attention from the main message of the paper.
  • We believe that the implications of Theorem 2.3 are more intriguing and valuable than the additional formalism we used to prove it.

  In light of these considerations, we believe that deferring the formal proof to the Appendix is the most effective approach to balance readability and comprehensiveness.

W3. description and properness of evaluation metric

• Firstly, we would like to highlight that the evaluation metrics used in our empirical study are standard and widely accepted for benchmarking NGIL [1].
• We appologize for the confusing wording and have it fixed in the revised version.
• We agree that, given the nature of graph data, there may exist more suitable evaluation metrics. The exploration of what constitutes a superior evaluation metric and its optimal form is indeed an interesting open question. However, it is not the focus of this paper.

C1. The caption for the Figure in page 8 is missing.

• Thank you for pointing out missing caption. We have revised this in the updated paper.

Thank you once more for comments. We hope that our response has addressed your concerns and provided clarifications that further emphasize the significance and contributions of our work.

[1] ZHANG, Xikun, Dongjin Song, and Dacheng Tao. "CGLB: Benchmark Tasks for Continual Graph Learning." Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track. 2022.

[2]Ma, Jiaqi, Junwei Deng, and Qiaozhu Mei. "Subgroup generalization and fairness of graph neural networks." Advances in Neural Information Processing Systems 34 (2021): 1048-1061.

[3] Wu, Qitian, et al. "Handling Distribution Shifts on Graphs: An Invariance Perspective." International Conference on Learning Representations. 2021.

Thank you again for the feedback on our paper. We hope that our responses have addressed your inquiries and concerns. If this is not the case, please inform us and we would be glad to engage in further discussion.

Thank you for the feedback and comments. Please allow us to address and clarify the concerns as follows:

W1 & W2. The problem setting is not novel.

The novelty of our works comes from the theoretical analysis of the learnability of NGIL and the proposed experience replay method.

• We discuss extensively in the introduction and related work sections that the NIGL problem has garnered increasing attention in the community and has been studied in other related works (see the related work section in the paper).
• Rather than diminishing the significance of our work, the increasing and existing attention to the NGIL problem should highlights the importance of our results. We provide the first impossibility result linking the learnability of NGIL and structural shift. Additionally, we introduce a novel experience replay method that outperforms other experience replay methods for NGIL under structural shift.

W2. The technical contributions, while sound, seem limited.

We respectfully disagree with the reviewer's assessment of the technical contributions of our study and would like to clarify a few points to assert that our contribution is not, in fact, limited.

• First, it's important to note that our paper has two main contributions: 1) the first impossibility result for NGIL (also see the response to W1) and 2) a novel experience replay method.
• Experience replay is a widely used framework for incremental learning, and there is a substantial body of work dedicated to exploring different experience replay strategies (as discussed in the related works and baselines of our empirical study).
• The experience replay method proposed in the paper is novel. It is designed with the insight from the theoretical analysis and tailored for NGIL with structural shift. It demonstrates state-of-the-art performance over other experience replay methods in the NGIL problem.

In conclusion, considering the heightened attention directed towards NGIL (as indicated by the reviewer), and considering the theoretical and methodological contributions of this paper to NGIL, we assert that the technical contribution of our paper is sufficient.

W3. Theoretical setting and IID data counterparts

The theoretical setting and problem formulation do not reduce to the I.I.D data counterparts

• Formulating the learning problem from the perspective of ego graphs is a common approach for the theoretical analysis of graph neural networks (e.g., [1-3]). In this formulation, the dependency among vertex is manifested by the shared underlying graph structure. Therefore, this can not be deemed as an I.I.D data setting.
• The ``NON. I.I.D ness'' of the setting is also reflected by the analysis of the structural shift, which is the dependency of data sampling across different tasks/training sessions. Such dependency does not occur in the I.I.D data setting (e.g., incremental learning in CV) and is unique to the NGIL problem.

W4. use of ``\bf'' to highlight and definition of distortion

• use of ``\bf''
  • The use of \bf was a deliberate choice to emphasize and draw the reader's attention to important results or concepts.
  • This formatting convention has been widely adopted and accepted in machine-learning conference papers to enhance readability.
• Definition of distortion
  • The definition and description of distortion presented in Section 3.3 are complete.
  • The definition of distortion was originally presented under the definition of environment and was later changed due to space constraints. This alteration resulted in some cross-referencing issues in the appendix. We appreciate your observation, and we have corrected this in the revised version of the paper.

W5. time complexity

• We have provided the complexity analysis in Appendix F. It's worth noting that all the different experience replay methods exhibit the same order of complexity, O(N), where N represents the number of vertices.

Thank you once more for the comments. We hope that our response has addressed your concerns and provided clarifications that further emphasize the significance and contributions of our work.

[1] Zhu, Qi, et al. "Transfer learning of graph neural networks with ego-graph information maximization." Advances in Neural Information Processing Systems 34 (2021): 1766-1779.

[2]Ma, Jiaqi, Junwei Deng, and Qiaozhu Mei. "Subgroup generalization and fairness of graph neural networks." Advances in Neural Information Processing Systems 34 (2021): 1048-1061.

[3] Wu, Qitian, et al. "Handling Distribution Shifts on Graphs: An Invariance Perspective." International Conference on Learning Representations. 2021.

Thank you again for the feedback on our paper. We hope that our responses have addressed your inquiries and concerns. If this is not the case, please inform us and we would be glad to engage in further discussion.

Thank you for the feedback and comments. Please allow us to address and clarify your concerns as follows:

Firstly, we'd like to briefly reiterate the incremental problem (as described in Sec.1&2), and our understanding of the unlearning problem:

• Incremental learning is concerned with a setting that involves multiple training sessions or tasks. The objective is to develop a learning algorithm that can iteratively update the model with new data without "forgetting" previous knowledge. Hence, the incremental problem seeks an algorithm that takes a model parameter (already trained with some data) and new data, and outputs an updated model parameter that performs well on both new and old data.
• Conversely, the unlearning problem focuses on removing specific information or knowledge from a trained model. The goal here is to find a learning algorithm that inputs a model parameter and (possibly) descriptors of the information to be removed, and outputs an updated model parameter that ``forget'' on the targeted information but maintains performance on the rest of the data.

Although both paradigms concern the retention and removal of information, their settings, objectives, and forms of learning algorithms are distinctly different, making them orthogonal paradigms.

W1 & W2 Unnecessary formalism and straightforward presentation

We respectfully disagree that the formalism presented in the paper is unnecessary.

• A key motivation and contribution of this paper is to formally formulate the NGIL problem within the statistical learning framework. This formalism is essential for two reasons:
  • Given the inherent complexity and vague terminology associated with NGIL, formalism is crucial for precisely defining the problem and distinguishing it from similar settings, such as unlearning.
  • The formalism, rooted in elements from statistical learning, is a necessary foundation for formally deriving the learnability of the problem.
• We have made an effort to simplify the formalism for readability and believe its current presentation is essential.

We would appreciate it if the reviewer could specify which aspects of the formalism (definition or setting) could be considered unnecessary for our results, as this would help us make targeted improvements.

W3. The main concern is using some samples again and again. Although it may appear to be replay or revision but it has to be critically analysed how revisiting some samples is justified.

• Experience replay (revisiting or replaying a small set of important samples) is one of the most effective and standard frameworks for tackling catastrophic forgetting in incremental learning [2] (also see a detailed discussion in the related work section). Instead of retraining from scratch, experience replay only needs to replay or revisit a small set of samples for consolidating knowledge and information, achieving comparable performance to retraining the model with complete data. This is a huge gain in efficiency.
• Experience replay was originally inspired by human learning theory, which uses repeat visits to important samples to consolidate knowledge and information. The idea of experience replay has been widely adopted in incremental learning[2](also see a detailed discussion in the related work section for its application to incremental learning in CV and NLP). Many different experience methods have been developed to tailor incremental learning with different settings.

W4. It is not clear if there is some unlearning and relearning effect is there or not.

• Catastrophic forgetting (or ``unlearning'') is a well-documented phenomenon in incremental learning studies, including NGIL contexts [1, 2]. This is evidenced in Table 1 by comparing the difference between the Bare model and Joint Training, where the Bare model shows significant performance degradation due to catastrophic forgetting.
• Our proposed method's effectiveness (the ``relearning effect'') is demonstrated by performance retention in the NGIL setting (as defined in Eq. (1)) and is measured using standard NGIL evaluation metrics (described in Sec. 4). The performance of our proposed method, along with other experience replay methods, is also presented in Table 1 and is reflected by the improvement over the Bare model.

The above responses are based on our interpretation of what the reviewer means by "unlearning and relearning effect," as we have not used these terms anywhere in the paper. Please let us know if "unlearning and relearning effect" has a different interpretation.

Thank you again for the feedback on our paper. We hope that our responses have addressed your inquiries and concerns. If this is not the case, please inform us and we would be glad to engage in further discussion.