A Topology-aware Graph Coarsening Framework for Continual Graph Learning

Thank you for your insightful feedback! We are happy to address your concerns and questions. Detailed responses to your comments are provided below, along with new experimental results.

---

W1. The paper is not well structured

A: We are committed to making these improvements to enhance the readability and overall quality of the paper. We made modifications based on your specific comments.

---

W2, W3, Q2. Additional literature review/baselines

A: We have conducted additional literature review and compared with more baseline. Please refer to our global response.

---

Q1. Lack of discussion of related work

A: Thank you for the suggestion. We discussed different types of continual graph learning and the limitations of SOTA studies in related work section, which is included in Appendix A due to page limit. We will ensure to include the discussion in the main text of our revised version.

---

Q3. The reasoning behind using GNN embedding for calculating similarity

A: We use the embedding of the first layer of GNNs to calculate the similarity as we believe it embeds both the node feature and the topology information. As we discussed in section 3.2, two nodes are deemed similar based on three factors: 1) feature similarity; 2) neighbor similarity; and 3) geometry closeness. GNN embeddings capture the first two factors.

---

Q4. Section 4.4.3 is confusing

A: Thank you for pointing it out. We will rephrase this section as follows:

“We investigate the performance of the model when more tasks are learned on different CGL frameworks. We visualize the model’s performance (AP-F1) for all previous tasks after training on each new task on the Kindle dataset, as shown in Figure 4. This figure demonstrates that all CGL methods can mitigate the catastrophic forgetting problem on the Kindle dataset to varying degrees. Additionally, we observe that experience replay-based methods (SSM and TACO) maintain more stable performance, whereas the regularization-based method, TWP, experiences greater fluctuations. We deduce that this is because experience replay-based methods are better at preventing the model from drastically forgetting previous tasks, even when the current task has more distinct distributions.”

---

Q5. Performance of TACO on different ratio rates

A: We agree with you that investigating different reduction rates would be helpful. We conducted additional experiments on different reduction ratios (see attached PDF in global response). When the reduction rate is 1, TACO is equivalent to finetuning. The results show that Kindle, DBLP, and ACM exhibit different "saddle points," with a smaller reduction having a decreased marginal effect. However, we observe that DBLP and ACM are less sensitive and can still achieve decent performance at larger reduction rates, while the performance of Kindle significantly drops as the reduction rate increases further.

Besides, in the submitted version, to clearly demonstrate how the reduced graph can approximate the original graph with different reduction rates, we trained the GNN on reduced graphs with different reduction rates, and test on the original graphs in Section 4.4.2. Our intuition is that if learning on the reduced graphs can approximate learning on the original graphs, then using the reduced graphs as a replay buffer can also effectively consolidate old knowledge.

---

Q6. Description of graph coarsening methods

A: Thank you for the suggestions. We provide summaries of graph coarsening methods and their limitations in Appendix A.2 due to page limit.

Besides, we will further provide a more detailed description of the baseline graph coarsening methods as follows:

Alge. JC [8], Aff. GS [31], Var. Neigh [33], and Var. Edges [33] are all spectral-based methods that aim to preserve the graph spectral property (Laplacian consistency) when merging nodes.

• Alge. JC uses algebraic distance to measure the strength of connection between nodes and merges nodes with smaller algebraic distances to form a coarser graph.
• Aff. GS uses affinity, a normalized relaxation-based node proximity heuristic, during the aggregation process, merging nodes with higher affinity scores.
• Var. Neigh and Var. Edges are both local variation algorithms that contract edges (Var. Edges) or subsets of the neighborhood (Var. Neigh) with the smallest local variation.

Above approaches result in high computational complexity and rely solely on graph structures, ignoring node features.

• FGC [25] takes into account the node features and aims to integrate both graph structure and node features in a unified optimization-based approach to produce a coarser graph that retains the properties of the original graph. However, it models the two objectives as separate optimization terms, which means the efficiency problem from the spectral-based methods remains.

---

Q7. Incomplete information in paper references

Q7. We will fix this and make sure all references are correctly formatted in our revised version.

Thank you for your positive feedback. We are happy to address your concerns and questions. Detailed responses to your comments are provided below.

---

Q1. Clarification on the setting of task splitting

A: We understand your concern. To clarify, $G_t$ contains nodes from task $t$ and old tasks, but the node attributes and labels of nodes from old tasks are not available. As we discussed in Section 2.2, "Node attributes and class labels are only available if the nodes belong to the current time period." To justify our setup, imagine a real-life situation in a citation network: when a new paper A is published in 2024, it cites paper B published the previous year. We can extract the title (ID) of paper B from paper A, but no further information because all raw data of papers from previous years may be unavailable due to limited memory.

---

Q2, Limitations. Additional related work on benchmarking / different CGL setting

A: We appreciate you bringing the additional related benchmarking studies to our attention. We briefly mentioned the CGLB work [1] in Section 2.1, noting that it focuses on transductive settings, while ours focuses on inductive setting. We believe BeGin [2] is a valuable study that provides a variety of benchmarks with diverse settings. Although they do not cover the inductive and generalized class-incremental learning (class-IL) settings used in our paper, it is an important related work to discuss, and we will include it in our revised version.

We also appreciate you mentioning AGALE [3]. Our current work focuses solely on multi-class classification. We will include a discussion of this limitation. However, we believe our method can be applied to multi-label classification with modifications, and we will discuss incorporating multiple labels as a potential direction for future work.

---

Q3, Q7. Small numbers of classes/new classes

A: In our main experiments, we adopt a realistic Generalized Class-Incremental Learning setup, where tasks are split by time. To mimic the scenario where each task has different class sets, we randomly drop some classes from each task, although this still cannot guarantee that each task contains entirely new classes not seen in previous tasks. We acknowledge that the datasets we used have a relatively small number of classes. However, there are fewer options for dynamic expanding graph datasets. Nevertheless, we also evaluated our method in the traditional Class-Incremental Learning setting on three additional datasets in Appendix E.6, where 1) The datasets can have as many as 70 classes, and 2) new tasks contain classes unseen in previous tasks, demonstrating the adaptability of our method to both scenarios.

---

Q4. Replay buffer

A: In the memory buffer, we keep a coarsened version of the previous graph, which contains the node attributes of the supernodes and the edges between them. The edges of the coarsened graph are expected to preserve the topology of the original graphs.

---

Q5. Ablation study on replay buffer

A: To clarify, we propose TACO as an experience-replay-based method to consolidate knowledge from old tasks, thus, when the experience replay buffer is removed, our method is reduced to finetune.

Our major contribution is the introduction of a dynamic graph coarsening framework that can efficiently preserve both node features and topology information in a coarsened graph, and the coarsening graph is stored in the memory buffer for replay. We compare our method with other experience-replay methods (e.g., ER-rs) to demonstrate how our approach better preserves knowledge from old tasks and thus more effectively alleviates forgetting.

---

Q6. Task size / smaller tasks

A: We provide the statistics of the datasets we use in Appendix Table 3, where the average task size can be calculated as the number of items divided by the number of tasks. We also investigated how the model performs when the graphs are split into smaller tasks, where each subgraph contains fewer nodes, and reported the results in Appendix E.2. Note that in such cases, all models tend to forget more because the number of tasks is also doubled. We claim that the size of the subgraphs alone should not have a significant effect on model performance, as it does not influence the model's forgetting behavior. The replay buffer size should also be adjusted accordingly with the size of the subgraphs.

Thank you for your positive feedback! We are happy to address your concerns and questions. Detailed responses to your comments are provided below.

---

W1. Additional related studies

A: Thank you for pointing it out. We have conducted additional literature review and compared with more baselines. Please refer to our response to all reviewers.

---

Q1. Full name of CGL

A: Thank you for pointing it out. We will ensure the full name of CGL (Continual Graph Learning) is explicitly defined in our revised version.

---

Q2. Clarification of combine step

A: We would like to further clarify the process in the Combine step. When we combine the graphs, we align their co-existing nodes. A node (with a unique ID) that appeared in previous tasks was assigned to a cluster (supernode) during the coarsening. A hash table keeps track of the mapping between the original node ID and the cluster. When the same node appears again in the next task, the hash table directs it to and aligns it with the cluster it was originally assigned to.

---

Q3. Comparison with graph pooling

A: Thank you for this suggestion. Indeed, graph pooling and graph coarsening are highly related concepts. Similar to graph coarsening, the goal of graph pooling is to reduce the number of nodes in a graph while preserving the semantic information [1]. However, we recognize graph pooling as a much broader concept. According to [1], graph pooling can be roughly divided into readout pooling and hierarchical pooling. The former aims to obtain a single representation for the whole graph (e.g., for graph-level tasks) and does not fit our purpose. On the other hand, hierarchical pooling reduces the graph into a smaller-sized new graph, which is of our interest.

Two major categories of hierarchical pooling methods are often used: node dropping and node clustering.

• Node Dropping: This method deletes nodes from a graph, similar to the subgraph sparsifying method (SSM). Deleting most nodes significantly sparsifies the graph and could eventually make it equivalent to the experience replay methods.

• Node Clustering: This method merges connected nodes into clusters, highly similar to graph coarsening. Both build a cluster assignment matrix, and nodes assigned to the same cluster are merged. **Graph coarsening techniques can be applied to node clustering, and in a broader sense, they are equivalent. The graph coarsening techniques we focus on in this paper are heuristic approaches that do not require additional learning for efficiency. **

There are also widely-used Node Clustering methods specifically for such as DiffPool [2], HGP-SL [3], and SAGPool [4], which all require learning the cluster assignment matrix as a parameter. This could complicate the framework, making it computationally expensive and against the initial goal of efficient replay.

We believe that comparing graph coarsening and graph pooling can help readers better understand the concepts and the contribution of our work. We will include this discussion in the revised paper.

[1] Zhang, M., & Li, P. (2022). Graph Pooling for Graph Neural Networks: Progress, Challenges, and Opportunities. arXiv preprint arXiv:2204.07321.

[2] Ying, R., You, J., Morris, C., Ren, X., Hamilton, W., & Leskovec, J. (2018). Hierarchical Graph Representation Learning with Differentiable Pooling.

[3] Zhang, Z., Bu, J., Ester, M., Zhang, J., Yao, C., Yu, Z., & Wang, C. (2019). Hierarchical Graph Pooling with Structure Learning. arXiv preprint arXiv:1911.05954.

[4] Yuan, H., Huang, J., Zhang, X., Ji, S., & Xia, Y. (2020). StructPool: Structured Graph Pooling via Conditional Random Fields. arXiv preprint arXiv:2002.06565.

---

Q4. Preservation of knowledge from long time ago

A: We understand your concern. When we combine the new graph with the coarsened graph, we expect the coarsened graph to preserve knowledge from all previous tasks. Although the "strength" of old tasks may gradually decrease as more tasks are introduced, we argue that this can be somewhat counteracted by the consolidation of old knowledge through multiple runs. The main results show that even with as many as 10 tasks, the overall forgetting is relatively small, demonstrating the method's ability to preserve knowledge from old tasks. Additionally, in Section 4.4.3, we investigate the test performance of the model on each task after more tasks are learned. Figure 4 shows that the performance on the first task does not further drop when more tasks are learned, demonstrating that the model is able to retain knowledge from earlier tasks.

Thank you for your insightful feedback. We are happy to address your concerns and questions. Detailed responses to your comments are provided below.

---

W1. How to split datasets into different tasks

A: We split the original graph into different tasks (subgraphs) based on the timestamp of the source nodes. For instance, in a citation network, if paper A was published at timestamp t and cites paper B, which was published at timestamp t-1, the subgraph for task t contains both paper A and paper B. However, the node attributes of paper B are not available in task t since they belong to the previous timestamp. We discuss the details of task splitting in Section 2.2.

---

W2. Fine-tuning results and challenges of the tasks

A: We agree with you that the forgetting in fine-tuning may not appear as severe as reported in more extreme settings such as class-incremental setting. This is because we used a Generalized Class-Incremental Learning setup, where each task may have overlapping classes. We claim this is more realistic compared to the traditional Class-Incremental Learning setting. Please refer to Section 2.1 for further discussion.

Nevertheless, we consider the nearly 20% forgetting reported in our setting is significant and worth studying.

• First, in many critical domains, even a relatively small performance drop can be a significant concern. For instance, in scenarios such as diagnostic prediction [1], a false classification could potentially put a patient's life at risk. The difference between 99% and 80% accuracy is substantial; the latter could render the system's utility and trustworthiness completely questionable.

• Second, we emphasize that less forgetting is not equal to less challenging; rather, many catastrophic forgetting scenarios can be easily mitigated with simple strategies. For instance, prior work [59] (reference number in the paper) uses a Class-Incremental Learning setting and the model initially experiences around 90% forgetting in the fine-tune setting. However, after applying a lightweight regularization-based method, EWC, the forgetting drops to 30%. In contrast, in our setting, forgetting is not significantly alleviated with regularization methods and simple ER methods, highlighting the challenges of this setting and the necessity of proposing more sophisticated methods to address the problem.

Additionally, to demonstrate the generalizability of our method, we also evaluated it in the traditional Class-Incremental Learning setting and reported the results in Appendix E.6. These results show that forgetting in fine-tuning is more severe in this setting and that our method can effectively alleviate this forgetting.

[1] Luo, X., Huang, X., & Han, L. (2020). Artificial intelligence in disease diagnosis: A systematic literature review, synthesizing framework and future research agenda. Journal of Ambient Intelligence and Humanized Computing, 11(2), 432-450.

---

Q1. Extra computation of graph coarsening

A: We agree with you that graph coarsening incurs extra computation, so it is important to ensure that the method we used does not take too much time in training and inference. Therefore, we propose RePro, an efficient graph coarsening method with linear runtime complexity. We believe that a small extra time investment is necessary to accurately preserve topology for consolidating old knowledge. To demonstrate that our coarsening method can effectively alleviate forgetting with relatively small extra time, we reported a trade-off metric in Section 4.4.1. This metric is defined as the time required for coarsening the graph divided by the increase in prediction accuracy compared to the fine-tuning method. As shown in Table 2 in the paper, our coarsening method has the smallest trade-off value of extra time versus performance increase.

---

Q2. Comparison with subgraph rehearsal method

A: Although the subgraph rehearsal method can also preserve topology, we claim it is less efficient. In related work (Appendix A.1), we discuss a previous work [59] (reference number in the paper) that uses sparsified subgraph memory (SSM) to store the L-hop neighborhood of replay nodes. We argue that "storing topology information of nodes through this method is not very efficient, as the information of uncovered nodes is completely lost, and it fails to capture inter-task correlations in our setup." Also, as suggested by [1], sparsified subgraph methods “partially sacrifice topological information, especially when the computation ego-subnetworks are large and a majority of nodes/edges is removed after sparsification”.

We also compare this method, SSM, with ours in Table 1, which shows that it does not perform as well as our method when similar memory is used.

To better demonstrate the advantages of our method, we also provide a table comparing the characteristics of different methods in the attached PDF file.

[1] Zhang, X., Song, D., Chen, Y., & Tao, D. (2024). Topology-aware Embedding Memory for Learning on Expanding Graphs. arXiv preprint arXiv:2401.03077.