A Topology-aware Graph Coarsening Framework for Continual Graph Learning

Summary:

A: We appreciate your positive feedback and valuable comments. We have carefully considered each of your comments and carried additional experience in response to your suggestions. We sincerely hope our response can address your concerns.
W1: In the first section, two issues related to CGL are mentioned: the problem of changing class distribution and the issue of correlation between old and new tasks. However, the subsequent chapters do not seem to clearly explain how coarsening addresses these two problems.

W1, Q1: How TACO addresses the problem of changing class distribution and the issue of correlation between old and new tasks

A:

• TACO addresses the catastrophic forgetting caused by the distribution shift. The change of class distribution is one of the reasons that caused the catastrophic forgetting: due to the distribution shift among different tasks, the model tends to forget the knowledge learned in old tasks when learning new tasks, and it would perform badly in old tasks. TACO addresses this forgetting problem by replaying experience from previous tasks in the form of reduced graphs to the model when training new tasks.

• How TACO captures the inter-correlation among tasks. TACO captures the inter-correlation between tasks in the combination step. In the process of building subgraphs described in the problem statement, the same node may exist in both the previous timestamp and current timestamp, and they form edges with other nodes in these timestamps. Since most CGL methods treat subtasks as independent graphs, the copies of the same nodes on different graphs are unidentified, and the connections between two graphs through their overlapping nodes are lost, thus they “fail to capture the inter-dependencies between tasks that result from the presence of overlapping nodes”. TACO addresses this problem by aligning the overlapping nodes in old and new graphs, and successfully connects two graphs and captures the inter-correlation between tasks. We make it more clear in the methodology part of the newest version of this paper.

W2, Q2: Running time and memory analysis

A: Per your recommendation, we have conducted an efficiency analysis of TACO and other rehearsal-based CGL baselines in terms of training time and memory usage. We report the averaged total training time (including the time to learn model parameters and the time to store the memory/coarsen graphs), and the averaged memory usage of the model (including the memory to store data for the current task and the memory buffer to store information from previous tasks) for each task in Table 10.

We include the discussion in Appendix E.4 in the newest version of this paper.

Q2: Will the proposed method be affected by the time interval of the dataset?

A: We appreciate your bringing up this significant issue for study. In response to your query, we have conducted an investigation into the performance of TACO and other baseline models when tasks are allocated shorter time intervals. For the DBLP and ACM datasets, we divided them into one-year time intervals, resulting in a total of 20 tasks. We have included the AP-f1 and AF-f1 scores of all baselines utilizing GCN as their backbone in Table 9. Our findings indicate that, compared to our previous dataset splitting approach, most CGL methods exhibit a slight decline in performance. but TACO continues to outperform the other baseline models.

Regarding the Amazon-Kindle dataset, as we have already divided the tasks based on the finest available granularity, we are unable to further reduce the time interval for each task.

We include the discussion in Appendix E.3 of the latest version of our paper.

Q3: Short-term forgetting

A: We concur with your observation that the forgetting matrices we have previously applied primarily assess the model's long-term forgetting behavior. In response to your suggestion, we have introduced a new metric, termed "short-term average forgetting" (AF-st), which measure the decline in model performance on the most recent task when it learns a new one. AF-st is formally defined as follows:

\begin{aligned} \text{AF-st} = \frac{1}{T} \sum_{j=2}^T{{a_{j-1,j-1}-a_{j,j-1}}}. \end{aligned}

Here, $T$ is the total number of tasks, and $a_{i,j}$ is the prediction metric of the model on the test set of task $j$ after training on task $i$. We report the AF-st in terms of F1 score using GCN on three datasets in Table 8. We include the discussion in Appendix E.2 of the latest version of our paper.

Additionally, in Appendix E.1, we have provided visualizations of the performance of TACO and three representative baselines on each test set after training on each task within the Amazon-Kindle dataset. These visualizations also serve to illustrate the short-term forgetting patterns exhibited by each model to our readers.

Minor issues:

A: We appreciate you pointing out the spelling mistake. We have now corrected this typo and conducted a thorough proofreading of the paper again.

Summary:

We are grateful for your positive feedback and the valuable insights you provided regarding our paper. We have given careful consideration to each of your comments and have carried out additional experiments to address your questions. We sincerely hope that our responses have effectively addressed any concerns you may have had.

W1: Additional computational efficiency analysis

A: Per your recommendation, we have conducted an efficiency analysis of TACO and other rehearsal-based CGL baselines in terms of training time and memory usage. We report the averaged total training time (including the time to learn model parameters and the time to store the memory/coarsen graphs), and the averaged memory usage of the model (including the memory to store data for the current task and the memory buffer to store information from previous tasks) for each task in Table 10.

It is worth noting that since all CGL methods are backboned with the same GNN models, the differences between these methods primarily affect the training process of the GNNs and do not impact the inference phase. Consequently, we anticipate that all CGL methods will have similar inference times.

We include the discussion in Appendix E.4 in the newest version of this paper.

W2: More applications of TACO

A: We conducted an evaluation of TACO on citation datasets as well as an Amazon Kindle co-purchasing dataset. At present, TACO primarily emphasizes the node classification task. We concur with the reviewer's suggestion that broadening the applicability of TACO to encompass a wider array of tasks, such as recommendation systems and link prediction, would be advantageous. We intend to address this aspect in our future work and will include a discussion of these extensions in our forthcoming research.

W3: Hyper-parameter tuning of baselines

A: We understand the reviewer’s concern about the hyperparameters tuning of the baselines. The GNN model hyperparameters for the backbone of CGL baselines are the same. When training a GNN, at each batch we update the model on the whole graph, so the batch size is not a tunable parameter here. For other hyperparameters of the CGL models, we took the reported value from their original papers as reference, and carefully searched for an optimized value from a wide range of values. For example, the memory strength is an important hyperparameter that decides the learning rates of the CGL baseline and controls the ratios between learning new tasks and consolidating old tasks. We notice its reported default value can have different scales for different CGL methods. Thus, we searched their values in {10^i|i ∈ [−5...5]} and {0.1, 0.2...0.9} and selected optimal value on the validation sets.

Q1: Using soft label an alternative of majority voting

A: I agree with you that assigning soft labels would be a simple solution to mitigate the vanishing minority class problem. However, we also have concerns that such an approach may come with several drawbacks. First, using hard labels is memory-efficient, and requires only a single digit to represent a sample's label. In contrast, soft labels use a vector for storage, with a size equivalent to the model's output dimension. This distinction in memory usage is negligible for models with few output classes. However, in scenarios where the model predicts among a large number of classes, the increased memory demand of soft labels becomes significant and cannot be overlooked.

Secondly, although a model can learn to predict a soft label during the training phase, most applications necessitate deterministic predictions in the testing or inference phase. We are concerned that training with soft labels might lead the model towards indeterministic and ambiguous predictions, potentially undermining its practical applicability.

The last concern is that when using soft labels, instead of a classification task, the model is performing a regression task. To predict single nodes with deterministic labels, it is considered a suboptimal approach to model it as a regression task due to the unaligned optimization objectives and loss functions. Also, regression is believed to be a less difficult task to learn compared to classification task as discrete optimization is generally harder than continuous optimization. Training the model with an easier task may restrict its performance during the test phase.

With the above concerns, we still believe majority voting is a reliable and convenient method to obtain the labels of super-nodes. Also, majority voting has been used in scalable graph learning (Huang et al., 2021). Nevertheless, we appreciate your thoughtful consideration and insightful view of this problem. We will add this discussion to the newest version of our paper and conduct empirical studies for this approach in the future.

Dear Reviewer A9ak

Thank you once more for your valuable feedback. If you have any additional questions or concerns, please feel free to share them with us before the end of the author discussion period. We are eager to address any further queries during our discussion.

Thank you!

Summary:

We appreciate your insightful suggestions. We hope our answers can address your concerns regarding the thoroughness of our literature review, the implications for the perceived contribution of our work, and the validity of our class-incremental learning setting.

W1, W2, Q1: completeness of the literature review, and the contribution of this work

A:

• Clarification of our claim. First, we would like to clarify that we are targeting at both class-incremental and an inductive setting, which is challenging. We found most existing works are either not class-incremental or not inductive [1] [2]. We acknowledge that our original expression could be misleading, and we will clarify it in the newest version.

• Discussion on related work [1][2]. We value your contribution in providing [1][2] as benchmarks, and we intend to incorporate them into the discussion in the latest version of this paper. However, it's worth noting that in [1][2], the tasks are split based on classes rather than time steps, making them substantially different than our goal and less suitable for integration into our experiments.

• Discussion on related work [3]. We agree that [3] is a related work and it does not split the growing graphs into independent graphs. However, as we mentioned in the related work, [3] studies the Dynamic Graph Learning that “focuses on learning up-to-date representations on dynamic graphs instead of tackling the forgetting problem. They assume the model has access to previous information. The challenges explored in the DGL fundamentally differ from those addressed in our paper.”

• Discussion on related work [4]. It seems that the goal of [4] is to denoise an expanding graph. We kindly ask the reviewer to elucidate the connection or similarity between [4] and our work, and we are willing to add [4] to the discussion of our paper.

• Contribution and novelty of our work. We would like to explicitly clarify that the core contribution of our work lies in the development of a dynamic and efficient graph coarsening framework. The framework is designed to adeptly address the challenges of preserving graph topology and inter-task correlation within an experience-replay-based Continual Graph Learning (CGL) setting. We assert that our contributions remain unchallenged by any existing literature we have encountered, and the works mentioned by the reviewers. Also, our approach has been recognized for its novelty by reviewers 9rSM, A9ak, and Tw7D.

• Completeness of literature review. In preparing our work, we conducted extensive literature reviews of existing state-of-the-art CGL methods, particularly those centered on experience replay and targeted the challenges we address. However, we are open to and welcome any additional literature the reviewer might suggest that addresses the same challenges or employs similar ideas.

W3, Q2, Q3: problems of dataset splitting and class-incremental setting

A:

• Traditional class-incremental setting. We agree with you that our setup is different from the traditional class-incremental setting. As we mentioned, we observe the most existing work split tasks by different classes, thus each task would have a distinct set of classes, and a new task must contain new classes.

• Our class-incremental setting. However, in our split-by-time setup, it is very likely that the tasks have overlapping classes among each other. As we demonstrate in the introduction part, the class distribution across time shifts. Moreover, “in real-life situations, tasks may have different class sets (e.g. new fields of study emerge and old fields of study become obsolete)”. Thus, as mentioned in the paper, we simulate a real-life scenario that different tasks may have different sets of class labels; at each task, we randomly select one or two classes and mask the labels of the nodes from selected class(s) during the training and the testing phase. Thus, with our setup, a new task does not necessarily contain new classes that have never appeared before; instead, previously encountered classes may reappear in new tasks, and same classes can be shared across tasks.

• Generalized Class-Incremental setting. To this end, we clarify that our experimental setup is more appropriately characterized as a Generalized Class-Incremental setting (Mi et al., 2020). In this setting, tasks do not necessarily have entirely distinct class sets. Instead, same classes can be shared across tasks, and previously encountered classes may reappear in new tasks. This setting precisely matches the class-incremental setting we use. We will clarify this in the newest version of this paper.

Thanks for the detailed responsed provided by the authors.

I appreciate that the authors have made revision to improve their paper. After reading the rebuttal, my main concern is on the dataset splitting and task construction.

The authors claim that the continual learning scenario is the real world scenario would be that the classes in different tasks have overlap, which is true. However, constructing the tasks in this way has certain problems.

When splitting the datasets into tasks, the classes are randomly chosen. However, different combinations of the classes and different orders may causes significant difference in the task difficulty. For example, when the class overlap between tasks is large, then continually learning on these tasks may not cause significant forgetting issue, and it would be hard to check whether the applied method can indeed resolve the forgetting issue.

In traditional splitting, in which the tasks are constructed with different classes, it not only better ensure that different tasks follow different distribution, but also make it easier for different papers to follow a consistent setting (or different papers may have different randomly constructed tasks, with different learning difficulty).

The other concerns are mostly resolved, and I could increase my rating to 5. Since the experimental setting is an important issue, I'm afraid that I would not increase the rating to a positive level.

Dear Reviewer sD2m

We would like to thank you for your time and effort in reviewing our work. Your feedback on our responses has been very helpful in improving our paper. We hope we've managed to address the concerns you raised. If there's anything else you would like to discuss, please feel free to let us know before the author discussion period closes. We're here to respond to any further questions during the discussion.

Thank you!

Summary

We value your insightful suggestions, and we appreciate your endorsement of the novelty, evaluation comprehensiveness, and technical soundness of our paper. We have carefully considered each of your comments. We sincerely hope our answers address your concerns.

W1-1: Common CGL methods

A: We agree with you that Parametric isolation-based (same as expansion-based) methods are also one of the approaches in Continual Learning literature, as we mentioned in the Related work: “Regularization, Expansion, and Rehearsal are common approaches to overcome the catastrophic forgetting problem (Tang & Matteson, 2020) in continual learning”. We observed most expansion-based methods (Rusu et al., 2016; Yoon et al., 2017; Jerfel et al., 2018; Lee et al., 2020) are not tailored to graph-structured learning. When we did literature review for this paper, we found very limited expansion-based methods in CGL literature, and we made the observation that “most existing CGL methods adapt regularization and rehearsal methods on graphs”. As suggested by the reviewer, we found a recently published paper (Zhang et al., 2023) that proposed a parametric isolation approach for CGL. We change the statement and add this paper to the discussion in the newest version of our paper.

W1-2 and W2: Problem setting and the necessity of Kindle showcase

A:

• Incremental learning setting. Most CGL papers split data into different tasks by their labels (which can be done in either a class-incremental manner, or a task-incremental manner, with their differences explained in the introduction part). In such cases, it’s more obvious that each task would have completely different class distributions, and the models tend to forget the previously learned knowledge drastically. However, we argue such a setting is not very realistic. As we mentioned in the introduction part, “Real-world graphs often form in an evolving manner, where nodes and edges are associated with a time stamp indicating their appearing time, and graphs keep expanding with new nodes and edges. For instance, in a citation network, each node representing a paper cites (forms an edge with) other papers when it is published. Each year more papers are published, and the citation graph also grows rapidly. In such cases, it is necessary to train a model incrementally and dynamically because saving or retraining the model on the full graph can be prohibitively expensive in space and time.” Thus, the pre-existing nodes will not necessarily “disappear”, but the model would have no access to them due to the cost in storing their information.

• Necessity of using Kindle showcase in the introduction. We use the showcase to explain the motivation of this paper. Since we split the full graph into different tasks by time, instead of class labels, it became less obvious that nodes from different tasks may have different distributions. Thus, we believe it is necessary to demonstrate to readers that such distribution shift may happen across time, and catastrophic forgetting on old tasks exists when model learn new tasks.

W3: The process of merging supernodes

A: The process of merging nodes into super-nodes is the same process as partitioning the nodes in a graph into clusters. When two nodes are merged, they are assigned to the same cluster (or the super-node). As it is defined in Problem Statement- Graph Coarsening, a matrix P is used to represent the node partitioning assignment of a graph. The adjacency matrix of the reduced graph, the features, and the labels of the super-nodes are decided by equation (3). We make it clearer in the methodology part to eliminate the confusion in the newest version.

W4: Node sampling strategies

A: The motivation of the node fidelity preservation is to overcome the “vanishing minority class” problem by making sure certain nodes won’t be merged to a cluster. We apply different strategies that may select nodes with different characteristics and are representative in different manners. Reservoir Sampling randomly selects nodes from all nodes across all time, and it tends to preserve the class distribution. Ring buffer represents the most recent samples from each class. MoF selects the nodes that are closer to the average feature of each class. All three are commonly used sampling strategies and are implemented following Chaudhry et al. (2019).

In appendix c.2, we mentioned that “Reservoir Sampling is chosen as the node sampling strategy”. Also, we perform ablation studies on the effect of different sampling strategies in E.6.

Dear Reviewer 9rSM

Thank you once again for your thorough reviews and insightful feedback. We appreciate the time and effort you've dedicated to reviewing our paper. Your comments have been helpful in enhancing the paper's quality, and we've tried our best to address your concerns in the paper. If there are any further concerns or questions, please feel free to let us know before the author discussion period ends. We will be happy to answer them during the discussion.

Thank you!