Online Continual Graph Learning

We appreciate your thoughtful review and the detailed feedback on the paper. Below, we address each identified weakness while clarifying our paper's contributions.

1. • a. The formulation of the OCGL framework is provided in section 3 of the paper. While we acknowledge that the formalism is limited, in section 3.1 the growing network is formally defined. Specific definitions of the learner are not provided as to accommodate multiple solutions, and the requirements for efficiency are explored in the considerations on mini-batching and neighborhood expansion. The objective we wanted to achieve with our framework was to maintain a general enough setting that can be applied in multiple scenarios, therefore a stringent formalism would have harmed the scope of the OCGL framework.
   • b. We acknowledge that a detailed comparison between CGL and OCGL is not provided, yet they are compared at the end of section 2 and in section 3.1: the key difference between the two is that in CGL the streams consist of graph snapshots (generally subgraphs induced by the current task) on which models are trained offline with multiple passes (possibly also with batching), while in OCGL the stream consists of small mini-batches of nodes, which are not used for training after a new batch arrives.
2. We respectfully disagree with the reviewer's statement that continual learning is an inherently online setting: while we agree on the points on continual learning and that even for online systems storing historical data is also allowed, there is a fundamental difference between standard continual learning and online continual learning. While in standard continual learning training on each task is performed offline, with multiple passes over the data until convergence, the requirements of online learning involve a single pass over the data. Such a distinction is clearly identified in the literature [1,2]. We would thus kindly invite the reviewer to point out the specific statements in our manuscript which are deemed factually incorrect, so that we may correct them. Regarding the task boundary, we agree that there have been studies that looked at online continual learning without them, yet this is missing in the CGL literature, as even the referenced paper only proposes it as future work, and the same authors identify it as an open research direction in their recent survey [3]. This further highlights the contribution of our work. As to the definition of task boundary, a clarifying sentence has been introduced in the manuscript.
3. We wish to clarify that the objective of our paper is not to propose novel techniques for continual learning on graphs, but rather our primary contribution is the introduction of the Online Continual Graph Learning setting, which has distinct peculiarities compared to standard CGL. This contribution holds particular significance because, although certain studies in the CGL literature describe their frameworks as streaming, they often lack direct comparability with the OCL domain. Moreover, a clear and consistent framework like the one we introduce is absent. By establishing a well-defined problem space, identifying potential challenges, and providing a comprehensive benchmark, our work serves as a foundation for creating and evaluating new methods for efficient online continual graph learning. While certainly the issue of changing graph structure has been documented in multiple surveys, we believe that it poses specific challenges associated with the online setting, in particular regarding mini-batching and neighborhood expansion. Similarly for neighborhood expansion and sampling, while this issue is not unique to our setting, here sampling is not simply a matter of efficiency, but a requirement of the online setting. We want to stress how our contribution does not lie in the introduction of new techniques (as we point out in section 3.2 that sampling is a simple solution for neighborhood expansion problem for scaling GNNs to large graphs), but the introduction of a previously ignored setting, alongside a consideration of the issue it presents and that need to be further addressed in future studies.

[1] Zheda Mai, Ruiwen Li, Jihwan Jeong, David Quispe, Hyunwoo Kim, and Scott Sanner, "Online continual learning in image classification: An empirical survey", Neurocomputing, 2022

[2] Albin Soutif–Cormerais, Antonio Carta, Andrea Cossu, Julio Hurtado, Vincenzo Lomonaco, Joost Van De Weijer, and Hamed Hemati, "A Comprehensive Empirical Evaluation on Online Continual Learning", in 2023 IEEE/CVF International Conference on Computer Vision Workshops (ICCVW), 2023

[3] Xikun Zhang, Dongjin Song, and Dacheng Tao, "Continual Learning on Graphs: Challenges, Solutions, and Opportunities", arXiv:2402.11565, 2024

We appreciate your thoughtful review and valuable feedback. Below, we provide point-by-point responses to address the weaknesses and questions raised while clarifying our paper's contributions and setting.

1. Thank you for this suggestion. While our primary focus was on node classification due to its prominence in graph learning literature, we agree that extending the framework to tasks like edge prediction would significantly broaden its applicability. We will revise the conclusion to explicitly outline these extensions as important steps for future research.
2. Thank you for suggesting the inclusion of more recent methods for continual graph learning. While we initially focused on widely recognized baselines to ensure a robust comparison within the established continual learning literature, we agree that evaluating newer methods is essential to accurately reflect state-of-the-art performance. We thank you for the pointers to recent literature. However, most recent methods in the CGL literature violate the constraints of the OCGL setting either due to expensive update steps between tasks (such as a costly neural architecture search) or due to inefficient use of past data. As an example, the referenced "Universal graph continual learning" proposed a global structure distillation which requires to compute node embeddings for the entire graph, and a local structure distillation which still requires to compute the full embedding of buffer nodes and all their neighbors. Most of these methods therefore are not applicable in our setting. We have nonetheless identified in "Sparsified Subgraph Memory" [1] a suitable additional baseline, for which we have already launched experiments, whose results we will include in the final version of the paper.
3. The proposed simple solution of sampling to address the issue of neighborhood expansion is only a first step in tackling the issue. As we observe at the end of section 7, the (expected) negative impact on model accuracy indicates that further research is required to fully address the issue. Rather than a contribution by itself, the proposal of the sampling method serves to bring the attention to the specific issue of neighborhood expansion, which requires more consideration in this setting.
4. We appreciate this observation and agree that a sound theoretical analysis of convergence and bounds on forgetting adds value to continual learning papers. Nonetheless, unfortunately such an analysis is not straightforward for most methods, and is not provided even in the papers that introduce them. Such a detailed model analysis is therefore out of the scope of our work, which introduces a new, challenging setting for continual learning on graphs, rather that proposing a new method, or proving theoretical properties of existing ones.

[1] Xikun Zhang, Dongjin Song, and Dacheng Tao, "Sparsified Subgraph Memory for Continual Graph Representation Learning", in 2022 IEEE International Conference on Data Mining (ICDM), 2022

I appreciate the authors for their efforts and responses. The OCGL framework and benchmark represent valuable foundational steps for exploring online continual graph learning. However, as a foundational framework, the evaluation should be more comprehensive, encompassing diverse graph-based tasks beyond node classification, such as link prediction or graph classification, to demonstrate the framework’s broader applicability. Additionally, the current work relies on a limited set of datasets, which restricts the generalizability of the proposed benchmark.

Given these limitations and the lack of immediate impact demonstrated by the framework, the contribution appears less significant compared to other works at this conference. Thus, I will maintain my original assessment.

We thank you for the review. Below, we respond to the identified weaknesses and questions while addressing the concerns that were raised.

Weaknesses:

1. We believe that the first and main weakness identified by the reviewer stems from a misunderstanding of our experimental setting. We rewrote a sentence to make it clearer. Specifically, with "the graph will gradually grow with nodes from two new classes at a time" we mean that we stream mini-batches of nodes from two classes at a time. In the conventional incremental setting, the data (nodes) of a single task (nodes of two classes) would be available all at once, allowing for multiple passes until convergence. On the contrary, in our experiments, for each pair of classes multiple small mini-batches are processed one by one in an online fashion (without revisiting them later), before passing to the next pair of classes. Therefore our experiments follow exactly the proposed setting, with a class-incremental node stream definition.
2. We appreciate the suggestion to incorporate more recent methods for continual graph learning. However, please note that the most recent methods in the CGL literature violate the constraints of the OCGL setting either due to expensive update steps between tasks or due to inefficient use of past data. Most of these methods therefore are not applicable in our setting. While we selected widely recognized baselines to provide a robust comparison within the continual learning literature, we agree that newer methods should be evaluated to reflect state-of-the-art performance. For this purpose, in the final version of the paper we will include results for "Sparsified Subgraph Memory" [1], for which we have already launched the experiments.

Questions:

1. We thank you for bringing up this point of confusion, which certainly requires a rewording. We intended to emphasize that aggregating multi-hop information does not fundamentally conflict with the evolving nature of the graph. Yet, this necessitates storage of past information (see next point) and raises the problem of neighborhood expansion.
2. The purpose of a Past Information Storage is to have access to multiple hops of neighboring nodes for message passing when new ones arrive. In this context, the "limited" usage is defined in the preceding sentence with the requirement of bounded complexity for processing each mini-batch, to ensure efficiency in the presence of the neighborhood expansion issue. The role of the PIS is thus distinct from the memory buffer of replay methods: it serves as a "database" where even a huge graph could be stored, and its use is similar to what is done in traditional CGL when accessing inter-task edges. In such CGL settings, while not explicitly stated, it is de-facto used nonetheless as multiple hops of past nodes are required. An alternative, equivalent formulation would be to require that each node arrives equipped also with its l-hop neighborhood, or a subset of it. The memory buffer instead is a more limited storage of samples that is not used for the construction of neighboring information of mini-batch nodes, but it is used by the continual learning method to preventing forgetting.
3. As clarified in response to the first identified weakness, given a new task with N nodes, the model will be trained on N/batch_size mini-batches in an online fashion. We consider multiple passes only on each mini-batch before passing to the next.

[1] Xikun Zhang, Dongjin Song, and Dacheng Tao, "Sparsified Subgraph Memory for Continual Graph Representation Learning", in 2022 IEEE International Conference on Data Mining (ICDM), 2022

We thank the reviewer for the detailed comments. Here are point-by-point answers to the identified weaknesses:

1. We acknowledge the importance of elaborating on the scenarios where OCGL can be impactful. Specifically, OCGL can be used in all the applications of graph continual learning where quick model adaptation is required for timely predictions after distribution shifts. To address this we expanded the beginning of section 3 on the introduction of the OCGL framework for streaming graph data.
2. While all the baselines for the paper are Continual Learning methods, we note how A-GEM and MAS are in fact "onlinable" by design, as the learning protocol of A-GEM involves a single pass over the training stream and the parameter importance of MAS is updated in an online fashion. While additional baselines could be considered, we believe that the current ones are a representative selection of Continual Learning strategies. As pointed out also by reviewers zdzj and gFtT, we would rather expand our selection of baselines with a more recent GCL methods. In particular, in the final version of the paper we will include results for "Sparsified Subgraph Memory" [1], for which we have alredy launched the experiments.
3. We recognize the value of diversity in benchmarking datasets. While our study already spans four well-established graph datasets (CoraFull, Arxiv, Reddit, and Amazon Computer), we plan to expand this suite in future work to include additional graph datasets. The number of considered dataset is nonetheless in line with similar literature in GCL and OCL [2,3,4].
4. We wish to clarify that the primary aim of this work is to formalize the OCGL framework and provide a foundational benchmark. We believe this is an essential first step for further exploration and innovation in this field. By defining the problem space, analyzing possible problems and offering a robust benchmarking environment, our paper lays the groundwork for developing and testing novel algorithms. We believe that this contribution is particularly relevant as in the CGL literature there are some studies that refer to their setting as streaming, yet they are arguably not comparable to the OCL literature, and there is no well defined setting such as the one we propose with our work.
5. While random sampling might appear straightforward, we adopted this as a first, pragmatic solution to highlight the neighborhood expansion problem and to demonstrate its impact. We acknowledge this limitation and propose in the conclusion that future research should develop more sophisticated strategies tailored to OCGL. In addition, we believe that issue is in need to be raised not only in the online setting, but also in standard CGL, where some methods implicitly use past data thanks to multiple hops of message passing into past task nodes. We hope therefore that raising the issue can lead to more careful and efficient design strategies for GCL.

[1] Xikun Zhang, Dongjin Song, and Dacheng Tao, "Sparsified Subgraph Memory for Continual Graph Representation Learning", in 2022 IEEE International Conference on Data Mining (ICDM), 2022

[2] Xikun Zhang, Dongjin Song, and Dacheng Tao, "CGLB: Benchmark Tasks for Continual Graph Learning", Advances in Neural Information Processing Systems, 2022

[3] Zheda Mai, Ruiwen Li, Jihwan Jeong, David Quispe, Hyunwoo Kim, and Scott Sanner, "Online continual learning in image classification: An empirical survey", Neurocomputing, 2022

[4] Albin Soutif–Cormerais, Antonio Carta, Andrea Cossu, Julio Hurtado, Vincenzo Lomonaco, Joost Van De Weijer, and Hamed Hemati, "A Comprehensive Empirical Evaluation on Online Continual Learning", in 2023 IEEE/CVF International Conference on Computer Vision Workshops (ICCVW), 2023

I thank the author for the response, which has resolved some of my concerns. However, I still think the technical and experimental contributions are somewhat insufficient, so I will maintain my score.