A Topology-aware Graph Coarsening Framework for Continual Graph Learning

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 23:15:10

Abstract: Graph Neural Networks (GNNs) experience "catastrophic forgetting" in continual learning setups, where they tend to lose previously acquired knowledge and perform poorly on old tasks. Rehearsal-based methods, which consolidate old knowledge with a replay memory buffer, are a de facto solution due to their straightforward workflow. However, these methods often fail to adequately capture topological information, leading to incorrect input-label mappings in replay samples. To address this, we propose TACO, a topology-aware graph coarsening and continual learning framework that stores information from previous tasks as a reduced graph. Throughout each learning period, this reduced graph expands by integrating with a new graph and aligning shared nodes, followed by a "zoom-out" reduction process to maintain a stable size. We have developed a graph coarsening algorithm based on node representation proximities to efficiently reduce a graph while preserving essential topological information. We empirically demonstrate that the learning process on the reduced graph can closely approximate that on the original graph. We compare TACO with a wide range of state-of-the-art baselines, proving its superiority and the necessity of preserving high-quality topological information for effective replaying.

Main paper: 
 introduction: 
 Deep neural networks are known to be oblivious: they lack the ability to consider any pre-existing knowledge or context outside of the information they were trained on. In offline settings, this problem can be mitigated by making multiple passes through the dataset with batch training. However, in a continual learning setup (also known as incremental learning or lifelong learning) (Tang & Matteson, 2020; Kirkpatrick et al., 2017; Rusu et al., 2016; Rolnick et al., 2019) , this problem becomes more intractable as the model has no access to previous data, resulting in drastic degradation of model performance on old tasks. A variety of methods have been proposed to tackle the issue of "catastrophic forgetting". However, most of these approaches are tailored for Euclidean data, such as images and texts, which limits their effectiveness on non-Euclidean data like graphs. In this paper, we investigate continual graph learning (CGL) frameworks to address the forgetting problems in downstream tasks such as node classification on streaming graphs. Existing common CGL methods can be broadly categorized into regularization-based methods, expansion-based methods, and rehearsal-based methods. Regularization-based methods reserve old knowledge by adding regularization terms in training losses to penalize the change of model parameters (Liu et al., 2020) or the shift of node embeddings (Su & Wu, 2023) . However, they are generally vulnerable to the "brittleness" problem (Tang & Matteson, 2020; Pan et al., 2020) that restrains the models' ability to learn new knowledge for new tasks. Expansion-based methods Zhang et al. (2023) that assign isolated model parameters to different tasks are inherently expensive. In this work, we consider rehearsal-based methods (Rolnick et al., 2019; Chaudhry et al., 2018b; 2019; Tang & Matteson, 2020; Lopez-Paz & Ranzato, 2017) which use a limited extra memory to replay samples of old data to a learning model. Although there are several attempts (Kim et al., 2022; Zhou et al., 2020; Wei et al., 2022; Zhang et al., 2022a) to use memory buffers for saving graph samples in the rehearsal process of online graph training. They often face challenges such as inefficiency in employing topological information of graph nodes and ineffectiveness in capturing inter-task correlations.In this work, we focus on preserving the topological information of graph nodes with efficient memory in continual learning frameworks to improve downstream task performance. Downstream tasks play a pivotal role in many real-world applications. We notice that most existing research on CGL (Liu et al., 2020; Zhou et al., 2020; Zhang et al., 2022a) focuses on either task-incremental-learning (task-IL) (van de Ven & Tolias, 2019) or a tranductive (Zhang et al., 2022b; Carta et al., 2021) setting , where the sequential tasks are independent graphs containing nodes from non-overlapping class sets. In this setting, the model only needs to distinguish the classes included in the current task. For instance, if there are 10 classes in total, and this experimental setting divides these classes into 5 tasks. Task 1 focuses on classifying classes 1 and 2, while task 2 classifies classes 3 and 4, and so on. In this paper, we aim to tackle a more realistic inductive and Generalized Class-incremental-learning (generalized class-IL) (Mi et al., 2020) setting . 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. So we split a streaming graph into subgraphs based on time periods and train a model on each subgraph sequentially for the node classification task. In such cases, subgraphs are correlated with each other through the edges connecting them (e.g. a paper cites another paper from previous time stamps). The structural information represented by edges may change from previous tasks (inductive). Also, since the tasks are divided by time periods instead of class labels, new tasks could contain both old classes from previous tasks and new classes, so the model needs to perform classification across all classes (generalized class-IL). Unlike traditional class-incremental setting (van de Ven & Tolias, 2019) , where tasks often have entirely distinct class sets, generalized class-IL allows same classes to be shared across tasks, and previously encountered classes may reappear in new tasks. We further demonstrate the necessity of preserving old knowledge when learning on a streaming graph. We take the Kindle e-book co-purchasing network (He & McAuley, 2016; McAuley et al., 2015) as an example. We split the graph into 5 subgraphs based on the first appearing time of each node (i.e., an e-book). We observe a gradual shift of node class distribution over time, as shown in Figure 1 (a). Furthermore, even for nodes in the same class, their features and neighborhood patterns can shift (Kim et al., 2022) . Also, in real-life situations, tasks may have different class sets (e.g. new fields of study emerge and old fields of study become obsolete), which could exacerbate the forgetting problem. The F1 scores of node classification tasks using a Graph Convolutional Network (GCN) (Kipf & Welling, 2016) show that the model performs significantly worse on previous tasks when trained on new ones without any strategies to address the forgetting problem, as shown in Figure 1(b) .Motivated by these observations, we point out that despite the emergent research on Continual Graph Learning, two challenges still remain: 1) How to effectively and efficiently preserve the topological information of old tasks. 2) How to capture and take advantage of the correlation between old tasks and new tasks. In this work, we aim to address these two challenges by the following contributions.• A realistic CGL scheme. We consider a realistic continual learning paradigm on streaming graphs. In this online setting, the model (i.e., a GNN) is trained on a subgraph (i.e., task) comprising edges from the current time period. • A dynamic CGL framework. We propose a continual graph learning framework, TACO, that is efficient in memory and highly modular. By compressing a streaming graph online, TACO addresses the challenges of preserving topological information of nodes and taking into account the correlation between old and new tasks due to overlapping nodes among subgraphs. TACO does not introduce new learnable parameters besides the backbone GNN model. • A scalable graph reduction approach. As a component of the CGL framework, we propose an efficient graph reduction algorithm, RePro, which utilizes both graph spectral properties and node features to efficiently reduce the sizes of input graphs. Additionally, we present a strategy, Node Fidelity Preservation, to ensure that certain nodes are not compressed, thereby maintaining the quality of the reduced graph. We theoretically prove that Node Fidelity Preservation can mitigate the problem of vanishing minority classes in the process of graph reduction. • Evaluation. We conduct extensive experiments and perform comprehensive ablation studies to evaluate the effectiveness of TACO and RePro. We also compare our method with multiple state-of-the-art methods for both CGL and graph coarsening tasks. 
related work: 
 Catastrophic forgetting. Regularization, Expansion, and Rehearsal are common approaches to overcome the catastrophic forgetting problem (Tang & Matteson, 2020) in continual learning. Regularization methods (Kirkpatrick et al., 2017; Chaudhry et al., 2018a; Zenke et al., 2017; Ebrahimi et al., 2019) penalize parameter changes that are considered important for previous tasks. Although this approach is efficient in space and computational resources, it suffers from the "brittleness" problem (Tang & Matteson, 2020; Pan et al., 2020) where the previously regularized parameters may become obsolete and unable to adapt to new tasks. Expansion-based methods (Rusu et al., 2016; Yoon et al., 2017; Jerfel et al., 2018; Lee et al., 2020) assign isolated model parameters to different tasks and increase the model size when new tasks arrive. Such approaches are inherently expensive, especially when the number of tasks is large. Rehearsal-based methods consolidate old knowledge by replaying the model with past experiences. A common way is using a small episodic memory of previous data or generated samples from a generative model when it is trained on new tasks. While generative methods (Achille et al., 2018; Caccia et al., 2019; Deja et al., 2021; Ostapenko et al., 2019) may use less space, they also struggle with catastrophic forgetting problems and over-complicated designs (Parisi et al., 2018) . Experience replay-based methods (Rolnick et al., 2019; Chaudhry et al., 2018b; 2019; Tang & Matteson, 2020; Lopez-Paz & Ranzato, 2017) , on the other hand, have a more concise and straightforward workflow with remarkable performance demonstrated by various implementations with a small additional working memory.Continual graph learning. Most existing CGL methods adapt regularization, expansion, or rehearsal methods on graphs. For instance, Liu et al. (2020) address catastrophic forgetting by penalizing the parameters that are crucial to both task-related objectives and topology-related ones. Su & Wu (2023) mitigate the impact of the structure shift by minimizing the input distribution shift of nodes.Rehearsal-based methods (Kim et al., 2022; Zhou et al., 2020; Wei et al., 2022) keep a memory buffer to store old samples, which treat replayed samples as independent data points and fail to preserve their structural information. Zhang et al. (2022a) preserve the topology information by storing a sparsified L-hop neighborhood of replay nodes. However, storing topology information of nodes through this method is not very efficient and the information of uncovered nodes is completely lost; also it fails to capture inter-task correlations in our setup. Besides, Feng et al. (2023) present an approach to address both the heterophily propagation issue and forgetting problem with a triad structure replay strategy: it regularizes the distance between the nodes in selected closed triads and open triads, which is hard to be categorized into any of the two approaches. Some CGL work (Wang et al., 2021; Xu et al., 2020) focuses on graph-level classification where each sample (a graph) is independent of other samples, whereas our paper mainly tackles the problem of node classification where the interdependence of samples plays a pivotal role. It is worth noting that dynamic graph learning (DGL) (Wang et al., 2020; Polyzos et al., 2021; Ma et al., 2020; Feng et al., 2020; Bielak et al., 2022; Galke et al., 2020) 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 differ fundamentally from those addressed in our paper.Graph coarsening. Scalability is a major concern in graph learning. Extensive studies aim to reduce the number of nodes in a graph, such that the coarsened graph approximates the original graph (Jin et al., 2020; Loukas, 2018; Chen & Safro, 2011; Livne & Brandt, 2012) . In recent years, graph coarsening techniques are also applied for scalable graph representation learning (Liang et al., 2018; Deng et al., 2019; Fahrbach et al., 2020; Huang et al., 2021) and graph pooling (Pang et al., 2021; Liu et al., 2023; Lee et al., 2019) . Most graph coarsening methods (Jin et al., 2020; Loukas, 2018; Chen & Safro, 2011; Livne & Brandt, 2012) aim to preserve certain spectral properties of graphs by merging nodes with high spectral similarity. However, such approaches usually result in high computational complexity especially when a graph needs to be repetitively reduced. Also, the aforementioned methods rely solely on graph structures but ignore node features. Kumar et al. (2022) propose to preserve both spectral properties and node features. However, it models the two objectives as separate optimization terms, thus the efficiency problem from the spectral-based methods remains. 
problem statement: 
 Our main objective is to construct a continual learning framework on streaming graphs to overcome the catastrophic forgetting problem. Suppose a GNN model is trained for sequential node classification tasks with no access to previous training data, but it can utilize a memory buffer with a limited capacity to store useful information. The goal is to optimize the prediction accuracy of a model on all tasks in the end by minimizing its forgetting of previously acquired knowledge when learning new tasks. In this work, we focus on time-stamped graphs, and the tasks are defined based on the time stamps of nodes in a graph. For each task, the GNN model is trained on a subgraph where source nodes belonging to a specified time period, and all tasks are ordered in time. Node attributes and class labels are only available if the nodes belong to the current time period. The aforementioned setup closely resembles real-life scenarios. We formulate the above problems as follows.Problem 1. Continual learning on time-stamped graphs We are given a time-stamped expanding graph G = (V, E, A, X), where V denotes the node set, E denotes the edge set, A ∈ R |V|×|V| and X ∈ R |V|×d X denote the adjacency matrix and node features, respectively; Each node v ∈ V is assigned to a time period τ (v). We define a sequence of subgraphs, G 1 , ..., G k , such that each subgraph G t = (V t , E t , A t , X t ) from G based on the following rules:• For edges inG t : e = (s, o) ∈ E t ⇔ e ∈ E and τ (s) = t, • For nodes in G t : v ∈ V t ⇔ τ (v) = t or ((s, v) ∈ E and τ (s) = t),where s is a source node and o (or v) is a target node. We can assume τ (o) ≤ τ (s) for (s, o) ∈ E (e.g. in a citation network, a paper can not cite another paper published in the future).Under this setting, we implement a GNN to perform node classification tasks and sequentially train the model on G 1 , ..., G k . The objective is to optimize the overall performance of the model on all tasks when the model is incrementally trained with new tasks. Note that each taks corresponds to a time period and its subgraph G t . When the model is trained with a new task T t , it has no access to G 1 , ..., G t-1 and G t+1 , ..., G k . However, a small memory buffer is allowed to preserve useful information from previous tasks.Problem 2. Graph coarsening Given a graph G = (V, E) with n = |V| nodes, the goal of graph coarsening is to reduce it to a target size n ′ with a specific ratio γ where n ′ = ⌊γ • n⌋, 0 < γ < 1.We construct the coarsened graph G r = (V r , E r ) through partitioning V to n ′ disjoint clusters (C 1 , ..., C n ′ ), so that each cluster becomes a node in G r . The construction of these clusters (i.e., the partition of a graph) depends on coarsening strategies. The node partitioning/clustering information can be represented by a matrix Q ∈ B n×n ′ . If we assign every node i in cluster C j with the same weight, thenQ ij = 1; If node i is not assigned to cluster C j , Q ij = 0. Let c j be the number of node in C j and C = diag(c 1 , ..., c ′ n ). The normalized version of Q is P = QC 1/2. It is easy to prove P has orthogonal columns (P P -1 = I), andP ij = 1/ √ c j if node i belongs to C j ; P ij = 0 if node idoes not belong to C j . The detailed coarsening algorithm will be discussed in the next section. 
methodology: 
 We propose TACO in a continual learning setting to consolidate knowledge learned from proceeding tasks by replaying previous "experiences" to the model. We observe that the majority of experience replay methods, including those tailored for GNN, do not adequately maintain the intricate graph topological properties from previous tasks. Moreover, in a streaming graph setup they fail to capture the inter-dependencies between tasks that result from the presence of overlapping nodes, which can be essential for capturing the dynamic "receptive field" (neighborhood) of nodes and improving the performance on both new and old tasks (Kim et al., 2022) . To overcome these limitations, we design a new replay method that preserves both the node attributes and graph topology from previous tasks. Our intuition is that, if we store the original graphs from the old task, minimal old knowledge from the last time period and the original graph G t from the current time period, and combine them into G c t ; for the same time period, the selected important node set is updated with the new nodes; the model is then trained on G c t with both the new nodes and the super-nodes from the past; finally G c t is coarsened to G r t for the next time period.𝐻 𝑢 𝐻 𝑤 𝑣 $"%$# $" $# -0.8 -0.1 -0.5 -0.6 $ $ %$ % $$ $% -𝜖would be lost, but it is also exceedingly inefficient and goes against the initial intention of continual learning. Thus, as an alternative, we coarsen the original graphs to a much smaller size which preserves the important properties (such as node features and graph topologies) of the original graphs.We propose an efficient graph coarsening algorithm based on Node Representation Proximity as a key component of TACO. Additionally, we develop a strategy called Node Fidelity Preservation for selecting representative nodes to retain high-quality information. An overview of the proposed framework is provided in Figure 2 . We provide the pseudo-code of TACO and RePro in Appendix A.We also provide the source code in Supplemental Materials.Overall framework We summarize the procedure of our framework as three steps: combine, reduce, and generate. At task t, we combine the new graph G t with the reduced graph G r t-1 from the last task. Then we reduce the combined graph G c t to a set of clusters. At last, we generate the contributions of nodes in each cluster to form a super-node in the reduced graph G r t . The last step decides the new node features and the adjacency matrix of the reduced graph. We convey the details of each step below.(1) Combine: We use M (e.g., a hash table) to denote the mapping of each original node to its assigned cluster (super-node) in a reduced graph G r . In the beginning, we initialize G r 0 as an empty undirected graph and M 0 as an empty hash table. At task t, the model holds copies of G r t-1 , M t-1 and an original graph G t for the current task. G t contains both new nodes from task t and old nodes that have appeared in previous tasks. We first "combine" G t with G r t-1 to form a new graph G c t by aligning the co-existing nodes in G t and G r t-1 and growing G r t-1 with the new nodes appeared in G t . By doing so, we connect the old graph and the new graph, and capture the inter-correlation among tasks. We train the model f to perform node classification tasks on the combined graphG c t = (A c t , X c t , Y c t ) with the objective arg min θ ℓ(f (A c t , X c t , θ), Y c t ), where f is a L-layer GNN model (e.g. GCN), θ denotes trainable parameters of the model, and ℓ is the loss function. In this work, each new node and old node in G c t contribute equally to the loss during the training process. However, it remains an option to assign distinct weights to these nodes to ensure a balance between learning new information and consolidating old knowledge. We describe a more detailed process in Appendix B.1.(2) Reduce: We decide how nodes are grouped into clusters and each cluster forms a new super-node in the reduced graph. We propose an efficient graph coarsening method, RePro, by leveraging the Representation Proximities of nodes to reduce the size of a graph through merging "similar" nodes to a super-node. Node representations are automatically learned via GNN models without extra computing processes. We think two nodes are deemed similar based on three factors: 1) feature similarity, which evaluates the closeness of two nodes based on their features; 2) neighbor similarity, which evaluates two nodes based on their neighborhood characteristics; 3) geometry closeness, which measures the distance between two nodes in a graph (e.g., the length of the shortest path between them). Existing graph coarsening methods concentrate on preserving spectral properties, only taking graph structures into account and disregarding node features. However, estimating spectral similarity between two nodes is typically time-consuming, even with approximation algorithms, making it less scalable for our applications where graphs are dynamically expanded and coarsened. Thus, we aim to develop a more time-efficient algorithm that considers the aforementioned similarity measures.To get started, we have the combined graph G c t to be coarsened. We train a GNN model with L (L = 2 in our case) layers on G c t , such that the node embedding of G c t at the first layer (before the activation function) is denoted byEQUATIONwhere d h is the size of the first hidden layer in GNN. The similarity between every connected node pair (u, v) = e ∈ E c t is calculated based on cosine similarity as β(e) = Hu•Hv ∥Hu∥∥Hv∥ , where β(e) is the similarity score between the two end nodes of the edge e, H i is the embedding for node i, and ∥ • ∥ is the second norm of a vector. We then sort all edges of G c t such that β(e 1 ) ≥ β(e 2 ) ≥ ... ≥ β(e m c t ), and we recursively merge (assign the nodes to the same cluster ) the two end nodes of the edges that have the largest similarity scores, until the target size is reached.Complexity The time complexity of such an approach is proportional to the number of levels which can be large, especially when the graph is sparse or the target size is small. In our algorithm, we relax this constraint and allow one node to be merged multiple times continuously. The time complexity of our method isO(d h • m c t )where m c t is the number of edges in the current graph G c t . Node Fidelity Preservation After multiple rounds of coarsening, the quality of a graph deteriorates as its node features and labels are repeatedly processed. Furthermore, the use of a majority vote to determine the label of a cluster can lead to the gradual loss of minority classes and cause a "vanishing minority class" problem. = p 2 = ... = p c , then E[p ′ k ] = p k . 2. When p k < 1/c, E[p ′ k ] < p k , and E[ p ′ k p k ] decreases as n ′ decreases.There exists a p min such that 0 < p min < 1, and when p k < p min , E[p ′ k p k ] decrease as p k decreases.The proof of Theorem 4.1 is provided in Appendix B.2. Theorem 4.1 shows that as the ratio of a class decreases, its decline becomes more severe when the graph is reduced. Eventually, the class may even disappear entirely from the resulting graph. To combat these issues, we suggest preserving representative nodes in a "replay buffer" denoted as V rb t . We adopt three strategies from Chaudhry et al. (2019) to select representative nodes, namely Reservoir Sampling, Ring Buffer, and Mean of Features. The replay buffer has a fixed capacity and is updated as new nodes are added. During the coarsening process, we prevent the selected nodes in V rb t from being merged by imposing a penalty on the similarity score β(e) such thatEQUATION)where ϵ is a constant and ϵ > 0. It is worth noting that we do not remove the edges of these nodes from the list of candidates. Instead, we assign a high value to the penalty ϵ. This is to prevent scenarios where these nodes play a critical role in connecting other nodes. Removing these nodes entirely may lead to the graph not being reduced to the desired size due to the elimination of important paths passing through them. We make the following observation: Observation 4.1. Node Fidelity Preservation with buffer size b can alleviate the declination of a minority class k when p k decreases and n ′ decreases, and prevent class k from vanishing when p k is small.See Appendix B.2 for further discussions.Note that RePro does not require any additional parameters or training time despite relying on the learned node embeddings. We train a GNN model on a combined graph at each time step for node classification tasks. The node embeddings learned from the GNN model at different layers are representative of the nodes' neighborhoods. We use this fact and propose to measure the similarity of two nodes based on the distance between their embedding vectors. However, it takes quadratic time to calculate the pair-wise distance among nodes, thus we make a constraint that only connected nodes can be merged. Since connectivity has also been used to estimate the geometry closeness of two nodes (Pan et al., 2010) , by doing so, we are able to cover the three similarity measures as well as reduce the time complexity to linear time in terms of the number of edges to calculate node similarities.Our proposed approach based on node representations seems to be distinct from spectral-based methods, but they share a similar core in terms of the preserving of graph spectral properties. See Appendix B.3 for more details.(3) Generate: From the last step, we get the membership matrix Q t ∈ B n c t ×n r t where n c t denotes the number of nodes in the combined graph, n r t = ⌊γ • n c t ⌋ denotes the number of nodes in the coarsened graph and γ is the coarsening ratio.Q t [i, j] = 1 denotes that node i is assigned to super-node j. Otherwise, Q t [i, j] = 0.A simple way to normalize Q t is assuming each node contributes equally to their corresponding super-node (e.g. Q t [i, j] = 1/ √ c j for all any node i that belongs to cluster/supernode j). However, nodes might have varying contributions to a cluster depending on their significance. Intuitively, when a node is identified as a very popular one that is directly or indirectly connected with a large number of other nodes, preserving more of its attributes can potentially mitigate the effects of the inevitable "information degrading" caused by the graph coarsening procedure. To address the above issue, we propose to use two different measures to decide a node's importance score: 1) node degree: the number of 1-hop neighbors of the node. 2) neighbor degree sum: the sum of the degrees of a node's 1-hop neighbors. In this step, we propose to normalize Q t to P t utilizing these node importance information. We calculate the member contribution matrix P t ∈ R n c t ×n r t . Let i be a node belonging to cluster C j at timestamp t, and s i > 0 be the importance score of node i (node degree or neighbor degree sum), then p t,(ij) = si v∈C j sv . It is straightforward to prove that P ⊤ t P t = I still holds. Once we have P t , we get the new reduced graph G r t = (A r t , X r t , Y r t ) as:EQUATIONwhere the label for each cluster is decided by a majority vote. Only partial nodes are labeled, and the rows of Y c t for those unlabelled nodes are zeros and thus do not contribute to the vote. Through training all tasks, the number of nodes in the reduced graph G r is upper-bounded by1-γ γ • (n MAX ), where n MAX is the largest number of the new nodes for each task (See Appendix B.4 for proof); when the reduction ratio γ is 0.5, the expression above is equivalent to n MAX , meaning the size of the reduced graph is roughly the same size with the original graph for each task. The number of edges m is bounded by n 2MAX , but we observe generally m ≪ n 2 MAX in practice. 
empirical evaluation: 
 We conduct experiments on time-stamped graph datasets: Kindle (He & McAuley, 2016; McAuley et al., 2015) , DBLP (Tang et al., 2008) and ACM (Tang et al., 2008) to evaluate the performance of TACO. See Appendix C.1 for the details of the datasets and C.2 for hyperparameter setup.We compare the performance of TACO with SOTA continual learning methods including EWC (Kirkpatrick et al., 2017) , GEM (Lopez-Paz & Ranzato, 2017) , TWP (Liu et al., 2020) , OTG (Feng et al., 2023) , ERGNN (Zhou et al., 2020) , SSM (Zhang et al., 2022a) , DyGrain (Kim et al., 2022) , IncreGNN (Wei et al., 2022) , and SSRM (Su & Wu, 2023) . EWC and GEM were previously not designed for graphs, so we train a GNN on new tasks but ignore the graph structure when applying continual learning strategies. ERGNN-rs, ERGNN-rb, and ERGNN-mf are ERGNN methods with different memory buffer updating strategies: Reservoir Sampling (rs), Ring Buffer (rb), and Mean of Features (mf) (Chaudhry et al., 2019) . SSRM is an additional regularizer We also compare RePro with five representative graph coarsening SOTA methods. We replace the coarsening algorithm in TACO with different coarsening algorithms. Alge. JC (Chen & Safro, 2011) , Aff.GS (Livne & Brandt, 2012) , Var. edges (Loukas, 2018) , and Var. neigh (Loukas, 2018) are graph spectral-based methods; FGC (Kumar et al., 2022) consider both graph spectrals and node features.We follow the implementation of Huang et al. (2021) for the first four coarsening methods.Evaluation metrics We use Average Performance (AP↑) and Average Forgetting (AF↓) (Chaudhry et al., 2019) to evaluate the performance on test sets. AP and AF are defined as AP = 1 T T j=1 a T,j , AF = 1 T T j=1 max l∈{1,...,T } a l,j -a T,j , where 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 it is trained on task i. The prediction performance can be measured with different metrics. In this paper, we use macro F1 and balanced accuracy score (BACC). F1-AP and F1-AF indicate the AP and the AF for macro F1 and likewise for BACC-AP and BACC-AF. We follow Grandini et al. (2020) to calculate the macro F1 and BACC scores for multi-class classification.We evaluate the performance of TACO and other baselines on three datasets and three backbone GNN models, including GCN (Kipf & Welling, 2016) , GAT (Veličković et al., 2017) , and GIN (Xu et al., 2019) . We only report the node classification performance in terms of F1-AP and F1-AF with GCN in Table 1 due to the space limit. See Appendix D.1 for complete results. We report the average values and the standard deviations over 10 runs. It shows that TACO outperforms the best state-of-the-art CGL baseline method with high statistical significance, as evidenced by p-values below 0.05 reported from a t-test. Additionally, we note that despite being Experience Replay-based methods, ER-rs, ER-rb, and ER-mf do not perform as well as SSM and TACO, highlighting the importance of retaining graph structural information when replaying experience nodes to the model. Furthermore, we infer that TACO outperforms SSM due to its superior ability to preserve graph topology information and capture task correlations through co-existing nodes.We evaluate the performance of RePro by replacing the graph coarsening module of TACO with five widely used coarsening algorithms, while keeping all other components unchanged. The overall results on GCN are presented in Table 2 . See Appendix D.2 for complete results. We report the average time in seconds consumed for each model to coarsen the graph for each task. The results demonstrate that RePro achieves better or comparable prediction performance compared with the best baseline while being considerably more efficient in computing time compared to all other models. 2021), we train GNNs from scratch on original and coarsened graphs, then compare their prediction performance on the test nodes from the original graph. Using subgraphs from the first task of three datasets as original graphs, we train GCN models on coarsened graphs with different coarsening rates 1 -γ. Figure 3 (a) shows that prediction performance is relatively stable as graphs are reduced for DBLP and ACM, but F1 scores are more sensitive to the reduction rate on Kindle. This may be due to overfitting on smaller datasets. Although reduced graphs may not preserve all information, they can still be used to consolidate learned knowledge and reduce forgetting in CGL paradigm. We also test if the model learns similar node embeddings on coarsened and original graphs. In Figure 3 (b)-(d), we visualize test node embeddings on the DBLP dataset for reduction rates of 0, 0.5, and 0.9 using t-SNE. We observe similar patterns for 0 and 0.5 reduction rates, and gradual changes as the reduction rate increases.Additional ablation studies We also study the performances of CGL models after training on each tasks E.1, the effectiveness of the Node Fidelity Preservation E.5, and the effects of different important node selection strategies E.6. We present those results in Appendix E for those readers who are interested. 
conclusion: 
 In this paper, we present a novel CGL framework, TACO, which stores useful information from previous tasks with a dynamically reduced graph to consolidate learned knowledge. Additionally, we propose an efficient embedding proximity-based graph coarsening method, RePro, that can preserve important graph properties. We present a Node Fidelity Preservation strategy and theoretically prove its capability in preventing the vanishing minority class problem. We demonstrate the effectiveness of TACO and RePro on real-world datasets with a realistic streaming graph setup.Limitations: This work only considers situations where nodes and edges are added to streaming graphs with a single relation type. In the future, we plan to investigate continual graph learning methods when nodes and edges can be deleted or modified. Moreover, we will generalize our method to complex graphs such as multi-relation graphs and broader graph tasks such as link prediction for recommendation systems. 
 
 Appendix: The pseudocode of the proposed CGL framework TACO is described in Algorithm 1, and the proposed graph coarsening module RePro is described in Algorithm 2.Algorithm 1 The Proposed Method TACO 1: Input: A sequence of graphs G 1 , ..., G k (G t is only accessible at task t) 2: Output: A trained GNN node classifier f with parameter θ 3: G r 0 , M 0 , V rb 0 ← ∅, {}, {} 4: for task t = 1 to k do 5:(G c t , M t-1 ) ← combine(G t , G r t-1 , M t-1 ) 6:for epoch=0 to num_epoch do 7:Train f on G c t and update θ 8:end for 9:V rb t ← SamplingStrategy(V rb t-1 , G t ) 10:Compute node embedding H t based on Eq. 1 11:P t , Q t , P(•) ← GraphCoarseningAlgorithm (G r t , H t , V rb t ) 12:Compute G r t based on Eq. 3.13: In the proposed framework, during the training process, we use a reduced graph G r as an approximate representation of previous graphs, and a function M(•) (e.g., a hash table) to map each original node to its assigned cluster (super-node) in G r (e.g., if an original node i is assigned to cluster j, then M(i) = j). Both G r t and M t (•) are updated after the t-th task. To get started we initialize G r 0 as an empty undirected graph and M 0 as an empty hash table. At task T t , the model holds copies of G r t-1 , M t-1 and an original graph G t for the current task. We combine G t with G r t-1 to form a new graph G c t according to the following procedure:M t ← M t (v) = P(M t-1 (v)) for v ∈ M t1. Initialize the combined graph It is worth noting that we use directed edges to better explain the above procedure. In our implementation, the combined graph is undirected since the directness of the edges of the combined graph is not critical in learning node embeddings in a graph like a citation network. G c t = (A c t , X c t , Y c t ) as G r t-1 such that A c t = A r t-1 , X c t = X r t-= p 2 = ... = p c , then E[p ′ k ] = p k . 2. When p k < 1/c, E[p ′ k ] < p k , and E[ p ′ k p k ] decreases as n ′ decreases.There exists a p min such that 0 < p min < 1, and when p k < p min , E[p ′ k p k ] decrease as p k decreases.Proof. We prove the theorem by deriving the value ofE[p ′ k ]. Since E[p ′ k ]is invariant to the order of the classes, for convenience, we consider i = 1 without losing generability. The probability of the first class after the partitioning is:EQUATIONwhere E[n a ] is the expectation of the number of clusters containing a nodes, and q(a, p) is the probability that class 1 is the majority class in a cluster with size a.Property B.1. The expectation of the number of clusters containing a node isE[n a ] = n ′ × n -n ′ + 1 a -1 1 n ′ a-1 1 - 1 n ′ n-n ′ -(a-1).Proof. Define I j to be the indicator random variable for the j th cluster, such that:I j =1 if the j th cluster contains exactly a samples, 0 otherwise. We first compute the expected value of I j for a single cluster. Let's calculate the probability that a -1 out of the n -n ′ samples are allocated to the j th cluster:(a) There are n-n ′ a-1 ways to choose a -1 samples from the n -n ′ remaining samples.(b) The probability that each of these a -1 samples is placed in the j th cluster is 1n ′ a-1 .(c) The remaining n -n ′ -a + 1 samples from our original pool of n -n ′ should not be allocated to the j th cluster. The probability that all of them avoid this cluster is 1 -1 n ′ n-n ′ -(a-1) .Thus, the probability that the j th cluster contains exactly x samples is:E[I j ] = n -n ′ a -1 1 n ′ a-1 1 - 1 n ′ n-n ′ -(a-1).(5)The expected number of clusters out of all n ′ clusters that contain exactly a samples is:EQUATIONGiven that each I j is identically distributed, we can simplify the sum:EQUATIONSubstituting the expression derived for E[I j ] from step 2, we obtain:EQUATION)It is easy to show that when p 1 = p 2 = ... = p c , it holds that q(a, p) = 1 c since all classes are equivalent and have equal chances to be the majority class. Thus:EQUATION)To compute q(a, p), we need to consider the situations in which class 1 is the exclusive majority class and the cases where class 1 ties with one or more other classes for having the most samples. In the second case, we roll a die to select the majority class from all the classes that have most samples.To start, we consider the situation when class 1 has the most nodes and no other classes tie with it. We enumerate all possible combinations of class assignments and calculate the probability of each.EQUATIONwhere i = i 1 , i 2 ...i c , andEQUATIONandEQUATION)We then consider the situation when class 1 ties with another class. We first select another class that ties in with class 1, and we enumerate the possibility of other classes. We multiply the whole term by 1 2 as there is an equal chance to select either class as the majority class.EQUATION)We extend the above equation to a general case where class 1 ties with k classes (1 ≤ k ≤ c -1).Here we need to select k classes that tie with class 1. Class 1 now shares a 1 k+1 chance to be selected as the majority class with the selected k classes.EQUATIONFinally, we combine all the cases, and the probability that class 1 is the majority class is:EQUATION)The expectation ofEQUATION)To study the behavior of E[p ′ 1 p1] when p 1 changes, we derive the following derivative:EQUATIONwhereEQUATION)To findd f (i,a,p) p 1 dp1, we first separate the terms that are independent of p 1 :EQUATION)where u is independent ofp 1 u = c k=1 a -i 1 ... -i k i k ( 1 c -1 ) c k=2 i k + c k=2 a-i2...-i k (30)We observe that f (i,a,p) p1 demonstrates different behaviors for a = 1 and a > 1 and discuss the two cases separately.(1) When a = 1, it holds that i 1 = 1, θ = 0, ϕ = 0, and ψ = 0:EQUATIONIn such case,d f (i,a,p) p 1 dp1is independent with p 1 and remain constant when p 1 changes.(2) When a > 1, it holds that i 1 ≤ 1, θ ≥ 0, ϕ ≥ 0, ψ ≥ 0, and θ + ϕ > 0:EQUATIONwhereEQUATIONWhen 0 < p 1 < 1 and u > 0,d f (i,a,p) p 1 dp1= 0 if and only if v = 0, and the corresponding value of p 1 is:EQUATIONEQUATIONwhereEQUATIONIt is easy to show that ∆ > 0, and sinceEQUATIONwhenEQUATIONThus it must be held that 0 < p 0 1 < 1 and p 1 1 ≤ 0, and for any (i, a > 1), there exist a 0 < p 1 (i, a > 1) 0 < 1 such that when p 1 < p 0 1 (i, a > 1),EQUATIONwhere I is all possible i, then it holds that 0 < p min 1 < 1, and when p 1 < p min 1 ,d q(a,p) p 1 dp1 > 0.Next, we show that E[p ′ 1 p1] decreases as n ′ decreases when p 1 < 1/c. We first rewrite E[EQUATIONEQUATIONFirst, we show that q(a, p) is smaller for larger a when p 1 < 1/c. The intuition is that when a new node is added to a cluster originally with a -1 nodes, the new node has a higher probability of being another class, and the likelihood of class 1 becoming the majority class decreases.Next, we show that when n ′ increases, n-n ′ a-11 n ′ a-1 1 -1 n ′ n-n ′ -(a-1)becomes more leftskewed, that it gives a smaller value for large a. The intuition is that, as the value of n ′ increases, the average cluster size is expected to decrease. As a result, a large a becomes farther from the average cluster size, and the probability of a cluster having exactly a nodes decreases, leading to a decrease in the ratio of clusters with size a.With the above observations, it can be concluded that when p 1 < 1/c, the value of E[p ′ 1 p1] decreases as n ′ decreases.Observation 4.1. Node Fidelity Preservation with buffer size b can alleviate the declination of a minority class k when p k decreases and n ′ decreases, and prevent class k from vanishing at small when p k is small.The mechanism of Node Fidelity Preservation is to "hold" b clusters such that each cluster only has 1 node. We already show that when a = 1, q(a,p) q1 is independent of q 1 and so E[p ′ 1 ] = p 1 . By doing so, we make sure that among the b nodes, class 1 does not decline as p 1 or n ′ decline.We demonstrate the effect of Node Fidelity Preservation with examples. We assign n = 1000, c = 2, 3, and b = ⌊n ′ /5⌋. we plot change of E[p ′ 1 p1 ] and E[p ′1 ] at different n ′ and p 1 separately in Figure 4 . We draw the trend with Node Fidelity Preservation (NFP) using dash lines and without NFP using solid lines. From the figure, we observe that without Node Fidelity Preservation being applied, the ratio E[p ′ 1 p1] approaches zero when n ′ is small, resulting in a vanishing minority class. The application of Node Fidelity Preservation prevents the ratio from approaching zero and makes sure class 1 won't disappear when p 1 is small. Spectral-based methods aim to preserve the spectral properties of a graph. Specifically, the Laplacian matrices of the original graph and the reduced graph are compared with each other (Loukas, 2018) . The combinatorial Laplacian of a graph G, L ∈ R n×n is defined as L = D -A, where A ∈ R n×n is the adjacency matrix of G, and D ∈ R n×n is its diagonal degree matrix. The combinatorial Laplacian of the reduced graph, L ′ ∈ R n ′ ×n ′ , is calculated as L ′ = P ∓ LP + , where P + is the pseudo inverse of the normalized coarsening matrix P ∈ R n×n ′ , and P ∓ is the transposed pseudo inverse of P . Since L and L ′ have different sizes, they can not be directly compared. Instead, the following induced semi-norms are defined:EQUATIONwhere x ∈ R n , and x ′ is the projection of x on n ′ -space such that x ′ = P x. The closeness between L to L ′ can be defined as how close ∥x∥ L is to ∥x ′ ∥ L ′ . L and L ′ are considered equivalent if it holds ∥x ′ ∥ L ′ = ∥x∥ L for any x ∈ R n . We next show that a partitioning made by merging nodes sharing the same neighborhood structure results in an equivalent Laplacian of the reduced graph as the original graph.Theorem B.1. Let i and j be two nodes of G, A ∈ R n×n be the adjacency matrix of G and Ã = A+I, D be the diagonal matrix of A and D = D + I, P ∈ R n×n-1 be the normalized coarsening matrix by merging i and j to one node, L and L ′ be the combinatorial Laplacian of G and the reduced graph. It holds that Ãi = Ãj , Di = Dj ⇒ ∥x ′ ∥ L ′ = ∥x∥ L for any x ∈ R n and x ′ = P x, where A i is the i-th row for a matrix A.Proof. For simplicity, we assume the original graph has 3 nodes. We assume i = 1 and j = 2 are permutation-invariant. It is easy to show that the following proof can be extended to the case when the graph has more than 3 nodes. The coarsening matrix P to merge the first two nodes is then:EQUATIONthen the pseudo inverse P + and the transpose pseudo inverse P ∓ of P isP + = 1 0 1 0 0 0 P ∓ = 1 1 0 0 0 1 .Given L as the combinatorial Laplacian of the original graph, the combinatorial Laplacian L ′ of the reduced graph isEQUATIONand for a x = [x 1 , x 2 , x 3 ] ⊤ , the corresponding x ′ is computed as:EQUATIONThen EQUATIONx ′⊤ L ′ x ′ =Given Ã1 = Ã2 , D1 = D2 ⇒ A 1 = A 2 , D 1 = D 2 and L = D -A, it is straightforward to prove that l 1a = l 2a and l b1 = l b2 which means l 11 = l 12 = l 21 = l 22 and l 13 = l 23 , l 31 = l 32 . Thus,EQUATIONProof. The number of nodes of the reduced graph at task t is:EQUATIONB.5 DISCUSSION ON UTILIZING SOFTLABEL AS AN ALTERNATIVE TO MAJORITY VOTING Another potential solution to address the "vanishing class" problem caused by the majority voting is to use softlabel to represent the cluster label instead. However, 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 We build a graph and make a constraint that the timestamp of the target node is not allowed to be larger than the source node, which should naturally hold for citation datasets as one can not cite a paper published in the future. Then we split each graph into subgraphs by edges based on the timestamps of the source nodes. To simulate a real-life scenario that different tasks may have different sets of class labels, at each task for the Kindle dataset, we randomly select one or two classes and mask the labels of the nodes from selected class(s) during the training and the test phase; for the DBLP and ACM datasets, we randomly select one class and mask the labels of the nodes from the selected class during the training and the test phase. The summary of each dataset is provided in Table 3 .For each task, we randomly split all nodes into training, validation, and test sets with the ratio of 30/20/50. For the baseline CGL models the memory strengths are searched from {10 i |i ∈ [-5...5]} or {0.1, 0.2...0.9}. For baselines that utilize a memory buffer, we calibrate their memory buffer sizes to ensure that their memory usage is on a similar scale to that of TACO. For TACO, by default the reduction ratio is 0.5; memory buffer size for Node Fidelity Preservation is 200; node degree is used to determine a node's importance score, and Reservoir Sampling is chosen as the node sampling strategy. We chose GCN and GAT as the GNN backbones. For both of them, we set the number of layers as 2 and the hidden layer size as 48. For GAT, we set the number of heads as 8. For each dataset, we generate 10 random seeds that split the nodes into training, validation, and test sets and select the masked class. We run all models on the same random seeds and the results are averaged over 10 runs. All experiments were conducted on a NVIDIA GeForce RTX 3090 GPU.We present more results of the performance of TACO and other baselines on three datasets and three backbone GNN models, including GCN (Table 4 ), GAT (Table 5 ), and GIN (Table 6 ). The results show that our proposed method outperforms other continual learning approaches consistently with different GNN backbone models. We present the result of the performance of TACO with its graph coarsening module RePro replaced by other four widely used graph coarsening algorithms with GCN as the backbone GNN model in Table 7 . two datasets, the model performs comparably or marginally better without Node Fidelity Preservation. Note that our proposal of Node Fidelity Preservation is intended as a preventative measure, not as a means of enhancing model performance. Node Fidelity Preservation aims to prevent the situation where minority classes vanish from the reduced graph due to unbalanced class distribution. Therefore, the improvement may not be noticeable if the class distribution is relatively balanced and node degradation is insignificant. In such cases, preserving the selected nodes may prevent the graph from coarsening to the optimized structure, which could even make the performance worse E.6 IMPORTANT NODE SAMPLING STRATEGIES We investigate how different important node sampling strategies affect the performance of the model. We report the average node classification performance of TACO with different node sampling strategies, Reservior-Sampling, Ring Buffer, and Mean Feature on the three datasets in Figure 8 . It shows that TACO achieves better performance with Reservior-Sampling and Mean Feature. We deduce that it is caused by the fact that Ring Buffer operates on a first in, first out (FIFO) basis, that it only retains the most recent samples for each class, making it fail to preserve information from the distant past. 


Decision: This paper presents a topology-aware graph coarsening framework for continual graph learning. In particular, the proposed framework stores information from previous tasks as a reduced graph, which expands by integrating with a new graph and aligning shared nodes. Promising results are observed on benchmark datasets against various baselines. Reviewers agreed that this paper studies an important problem and the paper is well written. Meanwhile, reviewers provided some comments regarding problem setting, technical details, paper writing and experiments. During post-rebuttal discussion, reviewers found that most of these concerns have been well addressed in the rebuttal. The authors should update their final version accordingly.

Reviews: review: paper_summary: paper_summary: This paper studies the continual learning of Graph Neural Networks. Specifically, the de facto rehearsal based methods fail to adequately capture the topological information. Accordingly, in this work, the authors propose to develop a graph coearsening based method, which stores the topological information into the zoomed-out graphs. The authors empirically justified that the proposed methods can closely approximate the original graph.

Experiments are conducted on three datasets against multiple SOTA baselines.
strength_weakness: strength_weakness: It is unclear how the adopted datasets split into different tasks. 

It seems that fintune also works well on the three adopted datasets, maybe this indicates that the adopted datasets and tasks are not challenging enough.
questions: questions: 1. graph coarsening will incur extra computation. will this result in significant extra resource consumption.

2. subgraph rehearsal methods also exist, can they also preserve the topology? What is the advantage of the proposed method?
limitations: limitations: As mentioned by the authors, this paper does not cover the scenario in which nodes and edges can be deleted or modified.
paper_summary: paper_summary: This paper presents TACO, a novel framework designed to address the issue of catastrophic forgetting in Graph Neural Networks (GNNs) during continual learning. The framework proposes a method to store information from previous tasks as a reduced graph. This graph expands with new tasks and undergoes a reduction process to maintain a manageable size while preserving topological information. The authors introduce a graph coarsening algorithm, RePro, which uses node representation proximities to effectively reduce graph size while retaining essential features. Extensive experiments demonstrate TACO's superiority over existing methods.
strength_weakness: strength_weakness: The choice of baseline methods for comparison might not cover all recent advances in continual learning and graph coarsening, potentially overlooking some relevant techniques.
questions: questions: 1. The full name of GCL is not explicit defined.
2. In the Combine step, graphs are combined using a hash table. Are the graphs labeled?
3. Graph pooling is highly related to graph coarsening. Why not add some comparisons with graph pooling methods?
4. At each timestamp, the model only aggregate information from last timestamp. Then what is preventing the model from forgetting information happened long ago?
limitations: limitations: yes.
paper_summary: paper_summary: The paper proposes a continual learning framework for the node classification task. The key idea is to learn a compressed form of graph from previous task and train the model by combining (and further compressing) the  reduced graph from previous stage  and the new graph. The graph compression step solves the research gap of sampling isolated nodes in the buffer and losing the topological structure in the previous works.  The authors also propose a generalised class-il setting in which tasks are based on time steps rather than classes.  Experimental results show improvements with the proposed technique.
strength_weakness: strength_weakness: Please see questions. Overall I liked the paper. what is missing is a nuanced discussion on a few important aspects. Other important thing is to show empirically that replay buffer is not the most important booster of the performance. I am happy to raise my score if my concerns are addressed.
questions: questions: 1. The **step 1 : Combine** is a bit unclear. In lines 162-163 it is stated that G_t contains nodes from task t and old task. Is it correct ? Why is it allowed?
2. A few related works specifically on  setups of different settings [1,2,3] are missing. Please include them in your discussion and in particular state the differences among the proposed settings and yours. For example, [3] specifically focuses on the case when does have multiple labels. For that scenario the settings described in [3] cover scenarios with overlapping labels even if the tasks are divided based on labels.  is your study limited to multi-class classification or would it also include multi-label classification? 
3. In realistic settings it could also happen that new labels emerge over time. Would your model perform as well? In that case the information from the past might not be very useful for the current task. 
4. In the replay buffer did you only keep the nodes or also their neighborhood structures?
5. It would be useful to see an ablations study by removing the replay buffer to verify if it is not the main component that affects the performance too much.
6. I am wondering how large the original subgraphs are at each time step and whether their sizes affect the performance?
7. What would be effect of total number of classes on the performance of your method? In the experiments all datasets have a small number of classes. 


[1] Xikun Zhang, Dongjin Song, and Dacheng Tao. Cglb: Benchmark tasks for continual graph learning. In Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022. 
[2] Jihoon Ko, Shinhwan Kang, and Kijung Shin. Begin: Extensive benchmark scenarios and an easy-to-use framework for graph continual learning. arXiv preprint arXiv:2211.14568, 2022. 
[3] Tianqi Zhao and Alan Hanjalic and Megha Khosla. AGALE: A Graph-Aware Continual Learning Evaluation Framework. In Transactions on Machine Learning Research, 2024.
limitations: limitations: The authors might additionally want to clearly state the scope of the study for example the current study seems not to cover the multi-label scenario.
paper_summary: paper_summary: This paper proposes a novel rehearsal-based continual graph learning method, TACO, which stores the information of previous tasks as a reduced graph. TACO performs graph coarsening based on node representation proximities to reduce a graph while preserving essential topological information. TACO shows significant performance improvements, as demonstrated by experiments on three graph datasets.
strength_weakness: strength_weakness: The paper is not well structured, and some statements are confusing.

The authors are encouraged to have a more complete comparison to better validate their proposed method.

Some important existing works are missing.
questions: questions: 1.	In the introduction, the authors are encouraged to discuss different types of methods for continual graph learning to highlight the motivation and contribution of the proposed method.

2.	The paper aims to reduce the current graph into a compressed form that maximally preserves its properties. This idea is similar to existing works [1][2] which employ graph condensation to capture the holistic semantics of original graphs. However, these works are missing.

3.	When calculating the node similarities, the used features are the output of the first layer of GNNs. Is there a special reason to utilize this feature?

4.	The section 4.4.3 is very confusing. The authors should rephrase this part to make it easier to understand.

5.	The authors should further include an ablation study to investigate the overall performance of TACO with different reduction rates.

6.	The authors are encouraged to include descriptions of other graph coarsening methods used in the paper.

7.	The information of some references is incomplete such as [47] and [54] in the reference section.

[1] Liu, Yilun, Qiu,Ruihong, & Huang, Zi. 2023b. CaT: Balanced Continual Graph Learning with Graph Condensation. In: Proc. of ICDM.

[2] Niu, Chaoxi, Guansong Pang, and Ling Chen. "Graph Continual Learning with Debiased Lossless Memory Replay." arXiv preprint arXiv:2404.10984 (2024).
limitations: limitations: The authors have discussed the limitations and societal impacts of the proposed method which are adequate.

Comments: title: Thank you
Thank you
Thank you
Thanks for the response
comment: We greatly appreciate your positive evaluation and the insightful suggestions provided!
We sincerely value your feedback and are grateful for your recognition of our efforts!
Your recognition and constructive feedback are much appreciated. Thank you for your support!
Thanks for clarifying my doubts. I maintain my positive score and hope to further improve it in the discussion period.
Dear reviewer AUFc, 

We would like to further clarify the task splitting by providing a step-by-step procedure. We use the DBLP dataset as an example. We hope this is helpful. 

1. We collected and selected papers from 1995-2014 from the DBLP database. The papers were then divided into 10 intervals, each spanning 2 years. For each task, we constructed a subgraph consisting of the nodes (with their features and labels) representing the papers published within the given time interval. 

2. For each paper $i$ in interval $t$, we examined each paper $j$ it cites: 
- If $j$ is from the same interval, we add an edge between the two nodes. 

- If $j$ is from a previous interval, we add paper $j$ to the subgraph and connect it to paper $i$. In this case, the ID of paper $j$ is available, but its attributes and labels are not. **We only use their id to align them with super nodes in the coarsened graph in the combine step. Please note that only the nodes that are connected to the nodes in the current time interval appear in G_t.** 

- If $j$ is from a future interval (which is unlikely in a citation network), we ignore it.
Dear reviewer HprJ, 

We think it would be helpful to illustrate how task splitting works with a step-by-step procedure. We use the DBLP dataset as an example.  

1. We collected and selected papers from 1995-2014 from the DBLP database. The papers were then divided into 10 intervals, each spanning 2 years. For each task, we constructed a subgraph consisting of the nodes (with their features and labels) representing the papers published within the given time interval. 

2. For each paper $i$ in interval $t$, we examined each paper $j$ it cites: 

- If $j$ is from the same interval, we add an edge between the two nodes. 

- If $j$ is from a previous interval, we add paper $j$ to the subgraph and connect it to paper $i$. In this case, the ID of paper $j$ is available, but its attributes and labels are not. 

- If $j$ is from a future interval (which is unlikely in a citation network), we ignore it.
Thanks for all the authors' efforts to address my concerns.  I have no further questions and vote an acceptance.
I appreciate the authors' effort in addressing my questions in their responses.  As reflected in my scores, my overall assessment is positive, and I maintain my current scores.
Thank you for pointing it out. First, we emphasize that **the goal of these node clustering algorithms is different from graph coarsening**. The main goal of node clustering is to **partition the graph and find strongly connected communities** (where the number of clusters is significantly smaller than the number of nodes). In contrast, our goal with graph coarsening is to **approximate the original graph with a smaller graph that preserves the original graph topological properties** at a moderate reduction rate (e.g., 10% to 50%) for efficient computation. Thus, their objectives are fundamentally different. **Applying graph clustering for our goal does not guarantee the preservation of topology properties.**

Furthermore, we point out that these **node clustering methods are less efficient when applied to coarsening**. We clarify that our coarsening algorithm RePro only merges connected nodes, so we only need to calculate cosine similarity between node pairs sharing edges between them. As a result, it takes  $O(E)$ to compute cosine similarity and $O(E \log (E))$ to sort, so the overall complexity is $O(E \log (E))$. Note that $E$ is much smaller than $N^2$ in practice. 


Graclus [1] is a heuristic graph clustering method. It uses a kernel k-means algorithm that requires multiple iterations, and the complexity for each iteration is $O(N^2K)$, where $N$ is the number of nodes, and $K$ is the number of clusters. Applying this to our case, $K$ is a constant ratio of $N$, making the time complexity $O(N^3)$. Thus, RePro is more efficient than even one iteration of Graclus. 

As for MinCutPool [2], it learns the cluster assignment matrix with an MLP that minimizes cut loss, and the time complexity for each iteration to calculate the loss, as stated in the paper, is $O(K(E + NK))$, where $N$ is the number of nodes, $E$ is the number of edges, and $K$ is the number of clusters. Applying this to our case, $K$ is a constant ratio of $N$, making the time complexity $O(NE + N^3)$. Note that this is just the time complexity for each iteration, and it could take a large number of iterations for the MLP to converge. Thus, RePro has advantages over MinCutPool in terms of efficiency.  

Similarly, the efficiency problem for other learning-based graph pooling methods also exists when applying them to graph coarsening, as they require learning and updating the models with multiple iterations.
Thanks to the authors for the response. However, I still have some concerns towards the following statement.

“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.”

One should note not all clustering based graph pooling methods require learning the assignments. E.g. Graclus [1] is also an efficient heuristic approach that widely used in graph pooling. Furthermore, I am not convinced that efficiency is the major reason for not choosing learning-based clusters. E.g., in MinCutPool [2], clusters are learned by applying MLP to node features, which I believe is more efficient than your method, since you require computing cosine similarity of all nodes and sorting edges.

[1] Dhillon, Inderjit S., Yuqiang Guan, and Brian Kulis. "Weighted graph cuts without eigenvectors a multilevel approach." IEEE transactions on pattern analysis and machine intelligence 29.11 (2007): 1944-1957.
[2] Bianchi, Filippo Maria, Daniele Grattarola, and Cesare Alippi. "Spectral clustering with graph neural networks for graph pooling." International conference on machine learning. PMLR, 2020.s